1、02243计算机软件基础(一)第一章 C语言基础1.算法的描述方法很多，常用的有自然语言、类语言、流程图、N-S结构图等。2.C语言中的常量有：整型、实型、字符型和字符串型等。3.计算机解题基本过程包括：提出问题、构造模型、选择方法、编写程序、上机调试。4. 整型、实型、字符型属于C语言中基本数据类型。5为了识别各个变量，C语言规定，变量名只能由字母、数字和下划线三种字符组成。6实型常量只使用十进制，有定点实数和浮点实数两种书写形式。 1自定义标识符中，符合C语言规定的是_123。2. 按照C语言规定的用户标识符命名规则，减号不能出现在标识符中。3. 设变量a,b,c,d依次为字符型、整型、单
2、精度型、双精度型，则表达式“a+b/c*d”的数据类型为双精度型。4. a_3是C语言正确标识符。符号串GOTO可以作为C语言的标识符。5. 设变量x,y为实型，x/y*z表达式不能正确表达数学公式。6. 在C语言中，x10是合法的字符常量。1.程序：算法写出之后，用某种计算机语言表示出来就形成了程序。2定点实数：即一般形式的实数，它是由整数、小数点和小数三部分组成的。3浮点实数：即带指数的实数，它是由前置数、小写字母e或大写字母E、指数三部分组成的。4算法与程序的主要区别有：1）算法是有穷的，即每一步执行的次数都是有限的，而程序可以是无穷的。2）算法和程序的描述方法不一样。程序是用计算机语言
3、描述的。3）算法一般情况下是不可执行的，而程序是可执行的。5整型变量和实型变量的类型与类型名表示：整型变量有：1）基本变量，用int表示。2）长整型，用long表示。3）短整型，用short表示。实型变量有：1）单精度实型，用float表示。2）双精度实型，用double表示。6C 语言中的算术表达式书写要注意要点：1).所有字符必须写在同一行。2).乘号“*”不能省。3).所有括号为圆括号，且配对。4).函数的自变量用圆括号括起来，三角函数的自变量用弧度。第二章 顺序结构、选择结构和循环结构的程序设计1程序的基本结构包括：顺序结构、选择结构和循环结构三种。2.顺序结构：用来表示一个操作序列，
4、它的执行过程是按顺序执行各序列。3.选择结构：也称分支结构，根据给定条件，选择执行某个分支操作。4循环结构有三种形式：条件（当型）虚幻、直到型循环和次数型循环。5break语句可用于switch语句和循环语句中。6 . 一个C程序的执行是从main()函数开始，直到main()函数结束。第三章 数组1多维数组:当数组中的数据元素有两个或两个以上的下标时，这种数组称为多维数组。2一维数组:当构成数组的各个元素的下标（在数学中称为下脚或脚码）只有一个时，我们称这样的数组为一维数组。3当数组名作为参数传递给函数时，作为实际参数的数组名被处理为该数组的首地址。第四章 函数1.函数:在一个大的程序中，有
5、一段操作或运算反复多次出现，这一段操作或运算提出来作为一个独立的程序，这个程序在C语言中称为函数。2.递归调用：C程序中，调用一个函数的过程中有出现直接或间接地调用该函数本身，称为函数的递归调用。3.全局变量：是在函数外部定义的量，可以为程序中各个函数所引用，其作用域是整个程序。4.变量的作用域：是指该变量在程序中的有效范围。5、C语言中数据传递方式有：单向值传递方式、地址传递方式、返回值传递方式和全局变量传递方式等四种。6C语言中数组名作为函数参数时，其中数据传递方式是地址传递。7. 当调用函数时，实参是一个数组名，则向对应形参传送的是数组的首地址。8. 设有定义“float a=5.0,b
6、=2.5;”，则表达式(int)b+a/b的值是4.0。9. 在C语言中，main()函数的位置可以任意，但必须要在函数之外。1形式参数和实在参数及它们之间的关系：形式参数：在函数定义的首部出现的参数为形式参数；实在参数：在调用函数时，使用的参数为实在参数。形参和实参的关系：1).个数相等；2).顺序一致；3).类型相同（或实参可以给形参正确的赋值）。2单向值传递方式的调用过程与特点有：调用过程：1).形参和实参各占1个独立的存储空间。2).形参的存储空间是在函数调用时才分配的，调用前是不占存储的。3).函数执行完返回时，形参的临时存储区被回收。特点：1).函数中对形参的操作不会影响到主调函数
7、中的实参。2).单向值传递时实参可以是常数、已有值的变量和表达式。3在函数调用情况中，没有返回值调用的特点：1).被调函数max为空类型。2).主调函数main中用“max（a，b）；”语句来调用，因此没有返回值。3).被调函数max执行完后直接输出结果，最后一个“”相当于return语句。4).由于是语句调用，所以max函数执行完后，程序返回到调用语句“max（a，b）；”的下一句，即主函数的最后一个“”，含义是整个程序结束。4在函数调用情况中，有返回值调用的特点：1).这种调用为表达式调用。2).有返回值调用时，被调函数中一定有“return表达式；”语句。3).“return表达式；”中
8、，若表达式值的类型和所在函数类型不一致时，以函数类型为准。第五章 指针1.指针变量：如果一个变量中要存放另一个变量的地址，就必须定义一个存放地址的变量，即指针变量。2,指针数组：是指数组的元素类型是指针类型。指针数组是用来存放一批地址的，经常用于处理多个字符串数据。3.C语言中访问地址的方式有两种：直接存取方式和间接存取方式。4 .指针变量是指存放变量地址的变量。5指针变量赋值的方法与注意要点：赋值方法：1).在定义指针变量的同时给指针变量赋初值。2).先定义指针变量，然后赋值。注意要点：1).C语言规定，同类指针可以相互赋值。2).不同类型不可以相互赋值。3).一个指针变量只能指向同一类型的
9、变量。第七章 数据结构概论1.数据：我们把计算机加工的对象（原料）叫数据。如字符（含数字、字母、符号等）、声音、光、图形、图像等。2.数据节点：数据节点是数据的基本单位，一个数据节点通常由一个或若干个数据项组成。3.数据结构：是相互有关连的的数据节点之间的集合。4.语句的频度:数据结构中用类C语言描述算法，类C语言有好多可执行语句构成，每一个语句的执行次数，称为语句的频度。1逻辑结构与数据元素本身的形式、内容、相对位置、个数无关。2计算机内部数据处理的基本单位是数据元素。3. 算法分析的两个主要方面是空间复杂度和时间复杂度。4. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为链
10、式存储结构。5. 在一个具有n个结点的有序顺序表中插入一个新结点并仍然有序的时间复杂度是O(n2) 。6 算法分析的两个主要方面是空间的复杂度和时间的复杂度。7. 顺序存储的表格中有10000个元素，以按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值皆不相同，用顺序查找法查找时，平均比较次数约为5000。8.数据结构的三个层次：数据、数据节点和数据项。他们三者间的关系是：数据是由若干数据节点构成；数据节点是由若干个数据项构成的9.数据的逻辑结构是数据之间的外在联系，又分为线性结构和非线性结构两类。10.数据的物理结构是数据在计算机内的存储表示，也称存储结构，可分为
11、顺序存储和非顺序存储。11数据结构类型研究的内容：1).数据的逻辑结构。2).数据的物理结构。3).数据的逻辑结构和物理结构之间的相互运算。12算法的时间复杂度：求解问题的算法所耗时间的程度。影响因素：1).算法中语句的频度；2).问题规模n；3).数据的状态第八章 线性表1.线性表:是由n(n=0)个节点、组成的优先序列。当n=0时线性表为空表。2.顺序表:把线性表中的数据节点按其逻辑顺序依次存放到计算机中一连续空间中去，我们把存放线性表的这一连续空间称为顺序表。3单链表的一个存储结点包含数据域和链域。4线性表的长度是数组元素的个数。5. 在表长为n的顺序表中，实施顺序查找，在查找不成功时，
12、与关键字比较的次数为n+1。6线性表的存储结构有两种：顺序存储结构和链式存储结构。7线性表特点：1).对非空表的线性表，有且仅有一个开始节点和一个终端节点。2).同一个线性表中的数据节点具有相同属性。3).线性表数据节点的个数为线性表的长度。8顺序表和链表的比较：1).时间性能：若经常进行的运算为查找运算，以顺序存储为宜；若经常进行的运算为插入、删除运算，以链式存储为宜。2).空间性能：对数据量事先固定的问题用顺序存储为好，对数据量变化较大的动态问题，用链式存储为好；顺序存储空间利用率高，而链式相应差一些。第九章 栈、队列和数组1栈是一种特殊的线性表，它的存储结构分别称为顺序栈和链栈。2.队列
13、:是一种先进先出的线性表，它的加入在表的一端进行，这一端叫队尾；删除在表的另一端进行，这一端叫表头3队列是一种具有先进先出特性的结构。4一个栈的入栈序列是a,b,c,d，则栈的不可能的输出序列是dcab。5st.top=m-1是判断一个体积为m的顺序栈st栈满的条件。6栈和队列等数据结构属于线性结构。7. 一个队列的输入列序为1,2,3,4，则该队列的输出序列是1,2,3,4。8. Head-next=NULL是带头结点的单链表Head为空的判定条件。9栈的运算过程：1).进栈push(s，x)。若栈s不满，则将节点x插入s栈栈顶。2).退栈pop(s)。若栈s非空，则将s栈栈顶元素删去。3)
14、.读取栈顶元素stacktop(s)。4).置栈空initstack(s)。5).判断栈是否为空stackempty(s)。10顺序队列的有关符号约定有：1）.sq代表队列。2）.设队列的体积m为所能容纳元素的个数；3）.用front代表队头指针，约定队头指针指向队头元素的前一个位置。4）.用rear表示尾指针，直接指向队尾元素。第十章 树和二叉树1.树形结构:是一种重要的非线性数据结构，树中各节点之间有明确的层次关系。2.树的高度：树的层数（根为第1层）为树的高度。3.哈弗曼树：是带权路径长度最小的二叉树，也称最优二叉树。4二叉树的遍历就是访问二叉树各个节点的过程。5深度为5的二叉树最多结点
15、数有31个。6. 深度为6的二叉树最多有63个结点。7. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是deabc，它的前序遍历序列是c e d b a。8二叉树中序遍历的特点：1).二叉树的遍历是一个递归过程。2).左右子树为遍历，根节点为访问。3).中序遍历的过程就是不断执行左、根、右的过程。4).遍历是按二叉树的基本结构进行的。9哈弗曼树的性质：1）.给定权值的哈弗曼树不唯一，但是WPL为定值。2.）权值越大的节点离根节点就越近。3）.哈弗曼树中无度为1的节点（n1=0）。4.）哈弗曼树节点总个数n=2叶子节点数1=2权值个数1=2 n01。第十一章 图1.图的邻接矩阵:是描述图中两顶点之间邻接关系的矩阵。从矩阵中可以看出，哪两个顶点之间有边，哪两个之间没边。2邻接表:图的邻接链表简称邻接表，它是由n个单链表组成的，每个单链表又由表头节点和表节点两部分构成。3最小生成树:如果给连通图边上加上权值，则
