数据结构复习提纲
第一章：
1.数据结构的逻辑结构：集合结构、线性结构、树形结构、图状结构
2.数据结构的物理（存储）结构：顺序结构、链式结构
3.抽象数据类型的两个重要特性：数据抽象、数据封装
4.算法的五个重要特性：有穷性、确定性、可行性、输入、输出
5.算法设计原则：正确的、可读性、健壮性、高效率与低存储量
第二章
1.线性表存储结构的公式：
Loc(a i+1)=Loc(a i )+L
Loc(a i )=Loc(a 1)+(i-1)*L
2.线性表的顺序存储结构“在表中任何位置(1≦i ≦n+1)上插入结点”算法时间复杂度： O(n)
3.线性表的顺序存储结构“在表中任何位置(1≦i ≦n)上删除结点”算法时间复杂度： O(n)
4.域的定义：举例
data ：数据域，用来存放结点的值。
next ：指针域（亦称链域），用来存放结点的直接后继的地址。
5.线性表的链式表示和实现（建表）：
头插法：该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。、 尾插法：该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r ，使其始终指向当前链表的尾结点。
6.线性表的链式表示和实现（查找）：
按序号查找：在链表中，当知道被查找结点的序号pos 时，只能从链表的头指针出发，顺链域next 个结点往下搜索，直到搜索到第i 个结点为止。因此，链表不是随机存取结构。
按值查找：按值查找是在链表中，查找是否有结点值等于给定值key 的结点，若有的话，则返回首次找到的其值为key 的结点的存储位置；否则返回NULL 。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key 作比较。
7.线性表的链式表示和实现（插入和删除运算的实现代码略）
8.涉及遍历操作时，其终止条件：非循环链表判断p 或p —>next 是否为空
9.循环链表：涉及遍历操作时，其终止条件：
判断它们是否等于某一指定指针，如头指针等。
data next
10.双向链表结构的对称性可用下式描述：
p->prior->next = p = p->next->prior
11.双向链表的前插操作、删除操作步骤算法（略）
第三章：
1. 栈：限定仅只能在表尾端进行插入和删除的线性表。
栈顶：表尾端被称之为栈顶。
栈底：和表尾相对应的另一端，称之为栈底。
特点：后进先出（LIFO）。
2.顺序栈的表示和实现
栈满时的处理方法：
1、提示出错，返回操作系统。
2、分配更大的空间。
链式栈的表示和实现：
算法实现，自己看（略）
3. 队列：在表的一端进行插入，而在另一端进行删除的线性表。
队尾：进行插入的一端。
队首：进行删除的一端。
特点：先进先出（FIFO）。
4.顺序表示的队列(循环队列)：
队空标志: front == rear
队满标志: rear>=MAXQSIZE
(假溢出)
第四章：
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( )函数：求子串（模式）在主串的位置。
第五章：
1.数组是n(n>1)个相同类型数据元素构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。
2.多维数组是一维数组的推广。
3.两种顺序存储方式：
行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i 个行向量后面。 在PASCAL 、C 语言中，数组就是按行优先顺序存储的。
列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j 个列向量之 后。在FORTRAN 语言中，数组就是按列优先顺序存储的。
4.
5.三角矩阵 a 00 a 01 … a 0 n-1 a 00 c … c
c a 11 … a 1 n-1 a 10 a 11 … c
………………...….. ……………................
c c … a n-1 n-1 a n-1 0 a n-1 1 … a n-1 n-1
6.对角矩阵
k=2+3*(i-1)+j-i+1=2*i+j
7.稀疏矩阵
8.矩阵转置算法（略）
9.矩阵的压缩存储 d i m i LOC d i m i m m m i m m m i LOC i i i LOC n n j n j k k j n n n n n n *)()0,,0,0( *)( )0,,0,0(),,,(111143232121+⎪⎪⎭⎫ ⎝⎛*+=+*++****+****+
=∑∏-=+=-ΛΛΛΛΛΛΛ⎪⎪⎩⎪⎪⎨⎧>+*≤-++-*=j i n n j i i j i n i k 当当,2)1(,2)12(⎪⎪⎩⎪⎪⎨⎧>+*≤++*=j i n n j i j i i k 当当,2)1(,2)1(i （行）j （列）v （值）
