C语言版数据结构知识点汇总.doc

1、。引言用计算机解决问题一般步骤：数学具体问题算法 编程、调试 得到答案模型一般来说，用计算机解决一个具体问题时，大致经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试调整知道的到最终解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。三种经典的数学模型图书书目自动检索系统线性关系博弈问题树城市道路问题图数据结构（ data structure）简单的解释：相互之间存在一种或多种特定关系的数据元素的集合。数据间的联系有逻辑关系、存储联系，通常的数据结构指的是逻辑结构。前

2、面提到的三种经典的数学模型体现了数据结构的基本结构，数据结构通常有如下四种关系：（ 1 ）集合结构（ 2 ）线性结构（ 3 ）树形结构（ 4）图状结构 线性表（一）N 个数据元素的有限序列存储结构：顺序存储结构、链式存储结构（1）（2）（3）（4）（5）（6）（7）（8）1213152234384320当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个合适的位置放置新元素。删除元素呢？ 线性表（二）链式存储-可编辑修改 -。题目描述：已知N*(N+1)/ 2 个数据，按行的顺序存入数组b1,b2, 中。其中第一个下标表示行， 第二个下标表示列。若 aij (i=

3、j ,j=1,2,n) 存于 bk 中，问： k,i,j 之间的关系如何表示？给定 k 值，写出能决定相应i,j 的算法。插入新元素的时候只需要改变指针所指向的地址。 二维数组与线性表如果某一线性表，它的每一个数据元素分别是一个线性表，这样的二维表在数据实现上通常使用答案二维数组。 K=i*(i-1)/2+j二维数组的一个形象比喻 Read(k);多个纵队形成的方块m * nFor i:=1 to k dofor j:=1 to i doif k=(trunc(I*(I-1)/2)+j) then writeln(k,对应的 i,j 为：,i, , ,j) 栈特殊的线性表操作特点：后进先出（L

4、ast In First Out） 数组地址计算问题栈顶表尾-可编辑修改 -。栈底表头 队列空栈先进先出 栈 （考题分析）允 许 插 入 的 一 端 称 为 队 尾 (rear)， 允 许 删 除 的 一 端 称 为 队 头 (front)。（1998 ） 栈 S 初始状态为空，现有5 个元素组成的序列1 ， 2 ， 3 ， 4 ， 5 ，对该序列在栈S 上一次进行如下操作（从序列中的1 开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是_D 循环队列(A) 5,4,3,2,1(B) 2,1 (C) 2,3 (D) 3,4头指针指向队列中队头元素的前一个位置，

5、尾指针指示队尾元素在队列中的当前位置。 树根、叶子、子树结点的度：结点拥有的子树数二叉树 二叉树-可编辑修改 -(R-F+N) mod N特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。第 i 层至多有2 i-1 个结点（ i=1 ）深度为 K 的二叉树最多有 2k-1 个结点（ K=1） 二叉树的遍历先（根）序遍历ABDFGCEH中（根）序遍历BFDGACHE后（根）序遍历FGDBHECA。 例题分析给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。 图 图的存储结构邻接矩阵-可编辑修改 -。 初始关键字 49 38 65 97 76 13

6、 27 49J=2(38) 38 49 65 97 76 13 27 49J=3(65) 38 49 65 97 76 13 27 49J=4(97) 38 49 65 97 76 13 27 49J=5(76) 38 49 65 76 97 13 27 49有向图、无向图、带权图的邻接矩阵J=6(13) 13 38 49 65 76 97 27 49 排序J=7(27) 13 27 38 49 65 76 97 49冒泡排序J=8(49) 13 27 38 49 49 65 76 97选择排序快速排序二、选择排序希尔排序1.基本思想：一、插入排序 (Insertion Sort)每一趟从待排

7、序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的1. 基本思想：最后，直到全部待排序的数据元素排完。每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序； 2.排序过程：直到待排序数据元素全部插入完为止。【示例】：2. 排序过程：初始关键字49 38 65 97 76 13 27 49【示例】：第一趟排序后13 38 65 97 76 49 27 49-可编辑修改 -。第二趟排序后13 27 65 97 76 49 38 4938 49 27 27 27 27 27 27第三趟排序后13 27 38 97 76 49 65 4965 38 49

8、 38 38 38 38 38第四趟排序后13 27 38 49 49 97 65 7697 65 38 49 49 49 49 49第五趟排序后13 27 38 49 49 97 97 7676 97 65 49 49 49 49 49第六趟排序后13 27 38 49 49 76 76 9713 76 97 65 65 65 65 65第七趟排序后 13 27 38 49 49 76 76 9727 27 76 97 76 76 76 76最后排序结果13 27 38 49 49 76 76 9749 49 49 76 97 97 97 97三、冒泡排序 (BubbleSort)1. 基本

9、思想：四、快速排序（ Quick Sort ）两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反1. 基本思想：序的数据元素为止。在当前无序区 R1.H 中任取一个数据元素作为比较的 基准 ( 不妨记为 X) ，用此基准将当前2. 排序过程：无序区划分为左右两个较小的无序区：R1.I-1 和 RI+1.H，且左边的无序子区中数据元素均小设想被排序的数组 R 1.N 垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不于等于基准元素， 右边的无序子区中数据元素均大于等于基准元素，而基准 X 则位于最终排序的能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原

10、则的轻气泡，就使其向上 漂位置上，即 R1.I-1 X.Key RI+1.H(1 I H) ，当 R1.I-1 和 RI+1.H 均非空时，分别对它浮 ，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。【示例】：2. 排序过程：49 13 13 13 13 13 13 13【示例】：-可编辑修改 -。初始关键字49 38 65 97 76 13 27 49堆排序是一树形选择排序，在排序过程中，将R1.N 看成是一颗完全二叉树的顺序存储结构，第一次交换后27 38 65 97 76 13 49 49利用完全二叉树中双亲

11、结点和孩子结点之间的内在关系来选择最小的元素。第二次交换后27 38 49 97 76 13 65 492.堆的定义 : N 个元素的序列K1,K2,K3,.,Kn. 称为堆，当且仅当该序列满足特性：J 向左扫描，位置不变，第三次交换后27 38 13 97 76 49 65 49Ki K2i Ki K2i+1(1 I N/2)I 向右扫描，位置不变，第四次交换后27 38 13 49 76 97 65 49J 向左扫描 27 38 13 49 76 97 65 49（一次划分过程）初始关键字 49 38 65 97 7613 27 49六、几种排序算法的比较和选择一趟排序之后27 38 13

12、 49 76 97 65 491.选取排序方法需要考虑的因素：二趟排序之后 13 2738 4949 65 7697 (1)待排序的元素数目 n ；三趟排序之后13 27 38 49 49 6576 97(2)元素本身信息量的大小；最后的排序结果1327 3849 49 65 76 97(3)关键字的结构及其分布情况；各趟排序之后的状态(4)语言工具的条件，辅助空间的大小等。2.小结：五、堆排序 (Heap Sort)(1)若 n 较小 (n = 50) ，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的1. 基本思想：记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直

13、接选择排序较好。-可编辑修改 -。(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。type(3) 若 n 较大，则应采用时间复杂度为O(nlog 2 n) 的排序方法： 快速排序、 堆排序或归并排序。快stringtype=packed array1.80 of char;速排序是目前基于比较的内部排序法中被认为是最好的方法。var(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此s:stringtype;可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n 个关键字随机分布时，任何另外，还有一种更简便的定义方法，利用tu

14、rbo pascal中的 string类型：借助于 比较 的排序算法，至少需要O(nlog 2n) 的时间。var(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。s:string;线性结构：串、栈、队列但是 string类型有一个限制： 运用 string类型定义的数据长度只能是1 255 ，也就是说串不能超过 255 个字符。一、串的概念2.串的标准函数串又称为字符串，是由 0 个或多个字符组成的有限序列。长度为 0 的串称为空串，它不包含在 turbo pascal中有如下标准函数可实现串的运算：任何字符。copy(s,x,y)：获取从 s 的第 x 个

15、位置开始的y 个字符串用 和 括起来。concat(s1,s2,.,sn)：相等于 s1+s2+.+sndelete(s,x,y)：将 s 中从第 x 个位置开始的y 个字符删去二、串的运算insert(s1,s,x)：将 s1 插到 s 中的第 x 个位置1.串的定义：length(s)：获取 s 的长度一般用一维数组实现串的运算，由此串的定义也用数组的形式来实现：3.串的基本运算-可编辑修改 -。(1)赋值含有其他的字符，则只要求输出错误信息及错误类型。(word2)(2)连接含有大写字母错误类型error 1(3)求串长数字（ 0-9)错误类型error 2(4)取子串其他非法字符错误类

16、型error 3(5)求子串序号如 输入： It is 12!(6)插入输出： error 1 2 3(7)删除输入： i am ,a student(8)置换输出： 43.编码解码：从键盘输入一个英文句子，设计一个编码、解码程序。(string)三、串的匹配算法编码过程：先键入一个正整数N(1=N=26)。这个 N 决定了转换关系。例如当 N=1 ，示例：输入的句子为ABCXYZ 时，则其转换码为ABCXYZ 不变。当N=2时，其转换码为BCDYZA ，其它的非字母字符不变。为使编码较于破译，将转换码的信息自左而右两两交换，若最后仅剩单四、练习题：个字符则不换。然后，将一开始表示转换关系的N

17、 根据 ascii 表序号化成大写字母放在最前面。1.读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现如： abcABCxyzXYZ-/,1. n=3的频率。 (句子末尾不一定用. 结束 ) cdeCDEzabZAB-/,1. 根据 N 的值转换 (word1) dcCeEDazZbBA/-1,. 两两交换 2.一个句子，只含英文字母，单词间用空格或逗号作为分隔符。统计句子中的单词数，如果 CdcCeEDazZbBA/-1,. 最后编码 -可编辑修改 -。解码过程为编码的逆过程。否则 t:=t+1;datat:=x;(2)栈的弹出pop(s) ：从栈 st 中弹出

18、一个项目；栈若 t=0则 print(underflow)1.栈的特点：否则 t:=t-1;栈是一种线性表， 对于它所有的插入和删除都限制在表的同一端进行，这一端叫做栈的 “顶”，(3)读栈顶元素 top(s,x) ：把栈顶元素的值读到变量x 中，栈保持不变；另一端则叫做栈的“底” ，其操作特点是“后进先出”。若 t=0则 print(error)2.栈的一般定义：否则 x:=datat;type(4)判栈是否为空 sempty(s) ：这是一个布尔函数，当栈st 中没有元素 (即 t=0) 时，称它为空stack=record栈，函数取真值，否则值为假。data:array1.m of da

19、tatype;若 t=0则 sempty:=truet:0.m否则 sempty:=false;end;4.栈的应用之一计算表达式的值var(1)表达式的三种形式：s:stack;中缀表达式：运算符放在两个运算对象中间，如：(2+1)*3 ；3.栈的基本运算：后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现(1) 栈的插入 push(s,x) ：往栈 st 中推入一个值为x 的项目；的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：21+3* ；若 t=m 则 print(overflow)前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面

20、，如：-可编辑修改 -。* + 2 1 3。次弹出两个数分别到Y 和 X ，然后以“ X 运算符Y”的形式计算机出结果，再压加栈S 中(2) 表达式的计算：如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算机一个中缀表达式简单得多。5.栈的应用之二递归算法的非递归实现将中缀表达式转换为后缀表达式的算法思想：示例：当读到数字直接送至输出队列中当读到运算符 t 时，队列a.将栈中所有优先级高于或等于t 的运算符弹出，送到输出队列中；1.队列的特点：b.t 进栈队列也是一种线性表，对于它所有的插

21、入都在队列的一端进行，所有的删除都在另一端进行，读到左括号时总是将它压入栈中进行删除的一端叫队列的“头”，进行插入的一端叫队列的“尾”，其操作特点是“先进先出”。读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，2.队列的一般定义：再丢弃左括号。typequeue=record运用后缀表达式进行计算的具体做法：data:array1.m of datatype;建立一个栈 Shead,tail:1.m从左到右读后缀表达式，读到数字就将它转换为数值压入栈S 中，读到运算符则从栈中依end;-可编辑修改 -。var若 tail=head则 qempty:=trueq:queue;否则 qempty:=false;3.队列的基本操作：3.队列的应用：(1)队列的插入 enq(q,x) ：在队列 q 中插入一个值为x 的元素，也称为进队；例：设有一个表，记为L=(a1,a2,a3,.,an) ，其中qtail:=x;L