C语言版数据结构知识点汇总(共7页).doc

《C语言版数据结构知识点汇总(共7页).doc》由会员分享，可在线阅读，更多相关《C语言版数据结构知识点汇总(共7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、指的是逻辑结构。 前面提到的三种经典的数学模型体现了数据结构的基本结构，数据结构通常有如下四种关系：（1）集合结构 （2）线性结构 （3）树形结构 （4）图状结构 线性表（一）N个数据元素的有限序列存储结构：顺序存储结构、链式存储结构（1）（2）（3）（4）（5）（6）（7）（8）1213152234384320当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个合适的位置放置新元素。删除元素呢？ 线性表（二）链式存储插入新元素的时候只需要改变指针所指向的地址。 二维数组与线性表如果某一线性表，它的每一个数据元素分别是一个线性表，这样的二维表在数据实现上通常使用二

3、维数组。二维数组的一个形象比喻多个纵队形成的方块 m * n 数组地址计算问题题目描述：已知N*(N+1) / 2个数据，按行的顺序存入数组b1,b2,中。其中第一个下标表示行，第二个下标表示列。若aij (i=j ,j=1,2,n)存于bk中，问：k,i,j之间的关系如何表示？给定k值，写出能决定相应i,j的算法。答案 K=i*(i-1)/2+j Read(k);For i:=1 to k do for j:=1 to i do if k=(trunc(I*(I-1)/2)+j) then writeln(k,对应的i,j为：,i,j) 栈特殊的线性表操作特点：后进先出（Last In Fi

4、rst Out）栈顶表尾栈底表头空栈 栈 （考题分析）（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 队列先进先出允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。 循环队列头指针指向队列中队头元素的前一个位置，尾指针指示队尾元素在队列中的当前位置。专心-专注-专业 树根、叶子、子树结点的度：结点拥有的子树数二叉树 二叉树(R-F+N)

5、mod N特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。第i层至多有 2i-1 个结点（i=1）深度为K的二叉树最多有 2k-1 个结点（K=1） 二叉树的遍历先（根）序遍历ABDFGCEH中（根）序遍历BFDGACHE后（根）序遍历FGDBHECA 例题分析给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA ，画出此二叉树。 图 图的存储结构邻接矩阵有向图、无向图、带权图的邻接矩阵 排序冒泡排序选择排序快速排序希尔排序一、插入排序(Insertion Sort)1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列

6、依然有序；直到待排序数据元素全部插入完为止。2. 排序过程： 【示例】：初始关键字 49 38 65 97 76 13 27 49 J=2(38) 38 49 65 97 76 13 27 49 J=3(65) 38 49 65 97 76 13 27 49 J=4(97) 38 49 65 97 76 13 27 49 J=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. 基

7、本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2. 排序过程： 【示例】： 初始关键字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 3

8、8 49 49 76 76 97最后排序结果 13 27 38 49 49 76 76 97三、冒泡排序(BubbleSort)1. 基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。2. 排序过程：设想被排序的数组R1.N垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上漂浮，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。 【示例】：49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 2765 38

9、 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97 四、快速排序（Quick Sort）1. 基本思想：在当前无序区R1.H中任取一个数据元素作为比较的基准(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R1.I-1和RI+1.H，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R1.I-1

10、X.KeyRI+1.H(1IH)，当R1.I-1和RI+1.H均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。2. 排序过程： 【示例】：初始关键字 49 38 65 97 76 13 27 49第一次交换后 27 38 65 97 76 13 49 49 第二次交换后 27 38 49 97 76 13 65 49 J向左扫描，位置不变，第三次交换后 27 38 13 97 76 49 65 49 I向右扫描，位置不变，第四次交换后 27 38 13 49 76 97 65 49J向左扫描 27 38 13 49 76 97 65 49（一次划分过程） 初始

11、关键字 49 38 65 97 76 13 27 49一趟排序之后 27 38 13 49 76 97 65 49 二趟排序之后 13 27 38 49 49 6576 97三趟排序之后 13 27 38 49 49 6576 97最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态五、堆排序(Heap Sort)1. 基本思想： 堆排序是一树形选择排序，在排序过程中，将R1.N看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。2. 堆的定义: N个元素的序列K1,K2,K3,.,Kn.称为堆，当且仅当该序列满足

12、特性：KiK2i Ki K2i+1(1 I N/2)六、几种排序算法的比较和选择 1. 选取排序方法需要考虑的因素：(1) 待排序的元素数目n；(2) 元素本身信息量的大小；(3) 关键字的结构及其分布情况；(4) 语言工具的条件，辅助空间的大小等。2. 小结：(1) 若n较小(n = 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排

13、序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于比较的排序算法，至少需要O(nlog2n)的时间。(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。线性结构：串、栈、队列 串一、串的概念串又称为字符串，是由0个或多个字符组成的有限序列。长度为0的串称为空串，它不包含任何字符。串用和括起来。二、串的运算1.串的定义：一般用一维数组实现串的运算，由此串的定义也用数组的形式来实

14、现：type stringtype=packed array1.80 of char;vars:stringtype;另外，还有一种更简便的定义方法，利用turbo pascal中的string类型：vars:string;但是string类型有一个限制：运用string类型定义的数据长度只能是1255，也就是说不能超过255个字符。2.串的标准函数在turbo pascal中有如下标准函数可实现串的运算：copy(s,x,y)：获取从s的第x个位置开始的y个字符concat(s1,s2,.,sn)：相等于s1+s2+.+sndelete(s,x,y)：将s中从第x个位置开始的y个字符删去in

15、sert(s1,s,x)：将s1插到s中的第x个位置length(s)：获取s的长度3.串的基本运算(1)赋值(2)连接(3)求串长(4)取子串(5)求子串序号(6)插入(7)删除(8)置换三、串的匹配算法示例：四、练习题：1.读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用.结束)(word1) 2.一个句子，只含英文字母，单词间用空格或逗号作为分隔符。统计句子中的单词数，如果含有其他的字符，则只要求输出错误信息及错误类型。(word2)含有大写字母 错误类型 error 1数字（0-9) 错误类型 error 2其他非法字符 错误类型

16、 error 3 如 输入： It is 12!输出： error 1 2 3输入： i am ,a student输出： 43.编码解码：从键盘输入一个英文句子，设计一个编码、解码程序。(string)编码过程：先键入一个正整数N(1=N=26)。这个N决定了转换关系。 例如当N=1，输入的句子为ABCXYZ时，则其转换码为ABCXYZ不变。当N=2时，其转换码为BCDYZA，其它的非字母字符不变。为使编码较于破译，将转换码的信息自左而右两两交换，若最后仅剩单个字符则不换。然后，将一开始表示转换关系的N根据ascii表序号化成大写字母放在最前面。如：abcABCxyzXYZ-/,1. n=3

17、 cdeCDEzabZAB-/,1. 根据N的值转换 dcCeEDazZbBA/-1,. 两两交换 CdcCeEDazZbBA/-1,. 最后编码解码过程为编码的逆过程。栈1.栈的特点：栈是一种线性表，对于它所有的插入和删除都限制在表的同一端进行，这一端叫做栈的“顶”，另一端则叫做栈的“底”，其操作特点是“后进先出”。2.栈的一般定义：typestack=recorddata:array1.m of datatype;t:0.mend;vars:stack;3.栈的基本运算：(1)栈的插入push(s,x)：往栈st中推入一个值为x的项目；若t=m则print(overflow)否则t:=t+

18、1;datat:=x;(2)栈的弹出pop(s)：从栈st中弹出一个项目；若t=0则print(underflow)否则t:=t-1;(3)读栈顶元素top(s,x)：把栈顶元素的值读到变量x中，栈保持不变；若t=0则print(error)否则x:=datat;(4)判栈是否为空sempty(s)：这是一个布尔函数，当栈st中没有元素(即t=0)时，称它为空栈，函数取真值，否则值为假。若t=0则sempty:=true否则sempty:=false;4.栈的应用之一计算表达式的值(1)表达式的三种形式：中缀表达式：运算符放在两个运算对象中间，如：(2+1)*3；后缀表达式：不包含括号，运算符

19、放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 *；前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，如：* + 2 1 3。(2)表达式的计算：由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算机一个中缀表达式简单得多。 将中缀表达式转换为后缀表达式的算法思想：当读到数字直接送至输出队列中当读到运算符t时，a.将栈中所有优先级高于或等于t的运算符弹出，送到输出队列中； b.t进栈读到左括号时总是将它压入栈中读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部

20、依次弹出，送至输出队列后，再丢弃左括号。 运用后缀表达式进行计算的具体做法：建立一个栈S从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X 运算符 Y”的形式计算机出结果，再压加栈S中如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束5.栈的应用之二递归算法的非递归实现 示例：队列1.队列的特点：队列也是一种线性表，对于它所有的插入都在队列的一端进行，所有的删除都在另一端进行，进行删除的一端叫队列的“头”，进行插入的一端叫队列的“尾”，其操作特点是“先进先出”。2.队列的一般定义：typequeue=recordda

21、ta:array1.m of datatype;head,tail:1.mend;varq:queue;3.队列的基本操作：(1)队列的插入enq(q,x)：在队列q中插入一个值为x的元素，也称为进队；qtail:=x;若tail=m则tail:=1否则tail:=tail+1;若tail=head则print(overflow)(2)队列的删除deq(q)：从队列q中删除一个元素，也称为出队；若tail=head则print(underflow)否则若head=m则head:=1否则head:=head+1;(3)读队头元素head(q,x)：将队列q中头部元素的值读到x中；若tail=he

22、ad则print(error)否则x:=qhead;(4)判队列是否为空qempty(q)：这是一个布尔函数，当q是空队列时，取真值，否则取假值。若tail=head则qempty:=true否则qempty:=false;3.队列的应用：例：设有一个表，记为L=(a1,a2,a3,.,an)，其中L表名a1,a2,a3,.,an表中元素。当ai为数值时表示元素，当ai为大写字母时，表示另一个表，但不能循环定义。例如，下列的定义是合法的（约定L是第一个表的表名）：L=(3.4,3,4,K,8,0,8)K=(15,5,8,P,9,4)P=(4,7,8,9)程序要求：当全部表给出后，示出所有元素的最大元素。思路：(1)可以建立两种队列，一种队列是存放数值的数值队列Q1，并有Q1A到Q1Z共26条数值队列，另一种队列Q2存放字母，表示将要向该字母所对应的数值队列输入数值的事件队列。(2)根据题目要求，事件队列Q2中应先放入字母L，表示首先输入L数值队列的数据。(3)从事件队列Q2中取出一个字母，并招待该字母对应的数值队列的数值输入，如果输入的数据中包含字母，则把字母放入事件队列中，并记录输入的数值中的最大值。(4)重复(3)步骤，直到事件队列中为空。