云南大学--软件学院---数据结构复习提纲1-6.doc

数据结构复习提纲第1章 ：1. 数据结构的逻辑结构：集合结构、线性结构、树形结构、图状结构2. 数据结构的物理（存储）结构：顺序结构、链式结构3. 抽象数据类型的两个重要特性：数据抽象、数据封装4. 算法的五个重要特性：有穷性、确定性、可行性、输入、输出5. 算法设计原则：正确的、可读性、健壮性、高效率与低存储量第二章1. 线性表存储结构的公式：Loc(ai+1)=Loc(ai)+L Loc(ai)=Loc(a1)+(i-1)*L 2. 线性表的顺序存储结构“在表中任何位置(1in+1)上插入结点”算法时间复杂度：O(n) data next3. 线性表的顺序存储结构“在表中任何位置(1in)上删除结点”算法时间复杂度：O(n)4. 域的定义：举例data：数据域，用来存放结点的值。next：指针域（亦称链域），用来存放结点的直接后继的地址。5. 线性表的链式表示和实现（建表）：头插法：该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。、尾插法：该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。6. 线性表的链式表示和实现（查找）：按序号查找：在链表中，当知道被查找结点的序号pos时，只能从链表的头指针出发，顺链域next个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。按值查找：按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。7. 线性表的链式表示和实现（插入和删除运算的实现代码略）8. 涉及遍历操作时，其终止条件：非循环链表判断p或pnext是否为空9. 循环链表：涉及遍历操作时，其终止条件：判断它们是否等于某一指定指针，如头指针等。10.双向链表结构的对称性可用下式描述：p-prior-next = p = p-next-prior11. 双向链表的前插操作、删除操作步骤算法（略）第3章 ：1.栈：限定仅只能在表尾端进行插入和删除的线性表。栈顶： 表尾端被称之为栈顶。栈底： 和表尾相对应的另一端，称之为栈底。特点：后进先出（LIFO）。2. 顺序栈的表示和实现栈满时的处理方法： 1、提示出错，返回操作系统。 2、分配更大的空间。链式栈的表示和实现：算法实现，自己看（略）3.队列：在表的一端进行插入，而在另一端进行删除的线性表。队尾：进行插入的一端。队首：进行删除的一端。特点：先进先出（FIFO）。4. 顺序表示的队列(循环队列)：队空标志: front = rear队满标志: rear=MAXQSIZE (假溢出)第4章 ：1.串类型的定义串的定义：串(String)是零个或多个字符组成的有限序列。串的长度：串中所包含的字符个数称为该串的长度。串的长度：串中所包含的字符个数称为该串的长度。空格串：将仅由一个或多个空格组成的串称为空格串(Blank String)。注意：空串和空格串的不同，例如“ ”和“”分别表示长度为1的空格串和长度为0的空串。子串与主串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。相等：当且仅当两个串的长度相等，并且每个对应位置的字符都相等时，称两个串相等。串常量和串变量：串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。串变量的值在程序中可以改变，即可以读也可以写。 2.求串长(length)：int strlen(char *s);串复制(copy)：char *strcpy(char *to,char *from);串复制(copy)：char strcat(char *to,char *from);串比较(compare)：int strcmp(char *s1,char *s2);字符定位(index)：char strchr(char *s,char c);3.串的块链存储表示Index( )函数：求子串（模式）在主串的位置。第5章 ：1. 数组是n(n1)个相同类型数据元素构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。2. 多维数组是一维数组的推广。3. 两种顺序存储方式：行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后。在FORTRAN语言中，数组就是按列优先顺序存储的。4.5. 三角矩阵a00 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c . . c c an-1 n-1 an-1 0 an-1 1 an-1 n-1 6. 对角矩阵k=2+3*(i-1)+j-i+1=2*i+j7. 稀疏矩阵稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。8. 矩阵转置算法（略）9. 矩阵的压缩存储10. 十字链表（仅作了解）11. 广义表a) 概念：n ( 0 )个表元素组成的有限序列，记作： LS = (a0, a1, a2, , an-1)LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)，n为表的长度。n = 0 的广义表为空表。 b) 与树对应的广义表称为纯表，它限制了表中成分的共享和递归允许结点共享的表称再入表 允许递归的表称为递归表c) 广义表不仅是线性表的推广，也是树的推广。 d)e) 广义表的第一个元素称为广义表的表头(head)，除此之外，其它元素组成的表称为广义表的表尾(tail)。f) 注意广义表( )和( )不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表，只不过该表中唯一的一个元素是空表( )，对其可进行分解，得到表头和表尾均为空表( )。第六章： 1.树的定义 ： 树是由n(n 0)个结点组成的有限集合。如果n = 0，称为空树；2.有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；3.除根以外的其它结点划分为m (m 0)个互不相交的有限集合T0,T1,Tm-1，每个集合又是一棵树，并且称之为根的子树。4.结点(node)：数据元素及其分支结点的度(degree)：结点拥有的子树的个数树的度(degree)：树中结点的度的最大值分支(branch)结点：度不为0的结点叶子(leaf)结点：度为0的结点子(child)结点：结点子树的根双亲(parent)结点：子结点的直接前驱结点兄弟(sibling)结点：同一双亲的子结点互称兄弟结点结点的层次(level)：根为第一层；子结点的层次比双亲结点的层次加1树的深度(depth)：树中结点的最大层次有序树：子树从左到右有序无序树：子树无序森林(forese)：m（0）棵互不相交的树的集合5. 二叉树的性质a) 在二叉树的第 i 层上至多有 2 i-1个结点b) 深度为 K 的二叉树至多有2 k- 1 个结点c) 二叉树的叶子结点数 n0 等于度为 2 的结点数n2 + 1d) 具有n个结点的完全二叉树的深度为 log2n 1。符号x 表示不大于x的最大整数。e) 如果对一棵有n个结点的完全二叉树的结点按层序编号（从上到下，从左到右),则对任一结点i（1=i1，则其双亲是结点i/2 。（2）如果2in，则结点i无左孩子；否则其左孩子是结点2i。（3）如果2i1n，则结点i无右孩子；否则其右孩子是结点2i1。6. .二叉树的存储结构顺序存储结构：顺序存储缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为h且只有h个结点的右单支树确需要2h-1个结点存储空间。a) 链式存储结构：b) 静态链式存储结构：（仅作了解）7. 遍历二叉树（非线形关系，需确定先后次序。）顺序表的遍历：for(i=1; inext; p!=NULL; p=p-next) visit(p-data);b) 按对根