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

数据结构（datastructure）第1页共7页1引言用计算机解决问题一般步骤：一般来说，用计算机解决一个具体问题时，大致经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试调整知道的到最终解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。三种经典的数学模型图书书目自动检索系统——线性关系博弈问题——树城市道路问题——图数据结构（datastructure）简单的解释：相互之间存在一种或多种特定关系的数据元素的集合。数据间的联系有逻辑关系、存储联系，通常的数据结构指的是逻辑结构。前面提到的三种经典的数学模型体现了数据结构的基本结构，数据结构通常有如下四种关系：（1）集合结构（2）线性结构（3）树形结构（4）图状结构☆线性表（一）N个数据元素的有限序列存储结构：顺序存储结构、链式存储结构（1）（2）（3）（4）（5）（6）（7）（8）12131522343843当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个合适的位置放置新元素。删除元素呢？☆线性表（二）链式存储插入新元素的时候只需要改变指针所指向的地址。☆二维数组与线性表如果某一线性表，它的每一个数据元素分别是一个线性表，这样的二维表在数据实现上通常使用二维数组。二维数组的一个形象比喻——多个纵队形成的方块m*n☆数组地址计算问题题目描述：已知N*(N+1)/2个数据，按行的顺序存入数组b[1],b[2],…中。其中第一个下标表示行，第二个下标表示列。若aij(i=j,j=1,2,…,,n)存于b[k]中，问：k,i,j之间的关系如何表示？给定k值，写出能决定相应i,j的算法。具体问题数学模型算法编程、调试得到答案20数据结构（datastructure）第2页共7页2答案①K=i*(i-1)/2+j②Read(k);Fori:=1tokdoforj:=1toidoifk=(trunc(I*(I-1)/2)+j)thenwriteln(k,’对应的i,j为：‘,i,’,’,j)☆栈特殊的线性表操作特点：后进先出（LastInFirstOut）栈顶——表尾栈底——表头空栈☆栈（考题分析）（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)。☆循环队列头指针指向队列中队头元素的前一个位置，尾指针指示队尾元素在队列中的当前位置。☆树根、叶子、子树结点的度：结点拥有的子树数二叉树☆二叉树特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。第i层至多有2i-1个结点（i=1）深度为K的二叉树最多有2k-1个结点（K=1）☆二叉树的遍历先（根）序遍历ABDFGCEH中（根）序遍历BFDGACHE后（根）序遍历FGDBHECA(R-F+N)modN数据结构（datastructure）第3页共7页3☆例题分析给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。☆图☆图的存储结构邻接矩阵有向图、无向图、带权图的邻接矩阵☆排序冒泡排序选择排序快速排序希尔排序一、插入排序(InsertionSort)1.基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2.排序过程：【示例】：[初始关键字][49]38659776132749J=2(38)[3849]659776132749J=3(65)[384965]9776132749J=4(97)[38496597]76132749J=5(76)[3849657697]132749J=6(13)[133849657697]2749J=7(27)[13273849657697]49J=8(49)[1327384949657697]二、选择排序1.基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2.排序过程：【示例】：初始关键字[4938659776132749]第一趟排序后13［38659776492749]第二趟排序后1327［659776493849]第三趟排序后132738[9776496549]第四趟排序后13273849[49976576]第五趟排序后1327384949[979776]第六趟排序后132738494976[7697]第七趟排序后13273849497676[97]最后排序结果1327384949767697数据结构（datastructure）第4页共7页4三、冒泡排序(BubbleSort)1.基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。2.排序过程：设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上漂浮，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。【示例】：49131313131313133849272727272727653849383838383897653849494949497697654949494949137697656565656527277697767676764949497697979797四、快速排序（QuickSort）1.基本思想：在当前无序区R[1..H]中任取一个数据元素作为比较的基准(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。2.排序过程：【示例】：初始关键字[4938659776132749］第一次交换后［2738659776134949］第二次交换后［2738499776136549］J向左扫描，位置不变，第三次交换后［2738139776496549］I向右扫描，位置不变，第四次交换后［2738134976976549］J向左扫描［2738134976976549］（一次划分过程）初始关键字［4938659776132749］一趟排序之后［273813］49［76976549］二趟排序之后［13］27［38］49［4965］76［97］三趟排序之后1327384949［65］7697最后的排序结果1327384949657697各趟排序之后的状态五、堆排序(HeapSort)1.基本思想：堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。2.堆的定义:N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：Ki≤K2iKi≤K2i+1(1≤I≤[N/2])六、几种排序算法的比较和选择1.选取排序方法需要考虑的因素：(1)待排序的元素数目n；(2)元素本身信息量的大小；(3)关键字的结构及其分布情况；(4)语言工具的条件，辅助空间的大小等。2.小结：(1)若n较小(n=50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。(2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4)在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何数据结构（datastructure）第5页共7页5借助于比较的排序算法，至少需要O(nlog2n)的时间。(5)当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。线性结构：串、栈、队列串一、串的概念串又称为字符串，是由0个或多个字符组成的有限序列。长度为0的串称为空串，它不包含任何字符。串用'和'括起来。二、串的运算1.串的定义：一般用一维数组实现串的运算，由此串的定义也用数组的形式来实现：typestringtype=packedarray[1..80]ofchar;vars:stringtype;另外，还有一种更简便的定义方法，利用turbopascal中的string类型：vars:string;但是string类型有一个限制：运用string类型定义的数据长度只能是1——255，也就是说不能超过255个字符。2.串的标准函数在turbopascal中有如下标准函数可实现串的运算：copy(s,x,y)：获取从s的第x个位置开始的y个字符concat(s1,s2,...,sn)：相等于s1+s2+...+sndelete(s,x,y)：将s中从第x个位置开始的y个字符删去insert(s1,s,x)：将s1插到s中的第x个位置length(s)：获取s的长度3.串的基本运算(1)赋值(2)连接(3)求串长(4)取子串(5)求子串序号(6)插入(7)删除(8)置换三、串的匹配算法示例：四、练习题：1.读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用.结束)(word1)2.一个句子，只含英文字母，单词间用空格或逗号作为分隔符。统计句子中的单词数，如果含有其他的字符，则只要求输出错误信息及错误类型。(word2)含有大写字母错误类型error1数字（0-9)错误类型error2其他非法字符错误类型error3如输入：Itis12!输出：error123输入：iam,astudent输出：43.编码解码：从键盘输入一个英文句子，设计一个编码、解码程序。(string)编码过程：先键入一个正整数N(1=N=26)。这个N决定了转换关系。例如当N=1，输入的句子为ABCXYZ时，则其转换码为ABCXYZ不变。当N=2时，其转换码为BCDYZA，其它的非字母字符不变。为使编码较于破译，将转换码的信息自左而右两两交换，若最后仅剩单个字符则不换。然后，将一开始表示转换关系的N根据ascii表序号化成大写字母放在最前面。如：abcABCxyzXYZ-/,1.n=3①cdeCDEzabZAB-/,1.{根据N的值转换}②dcCeEDazZbBA/-1,.{两两交换}③CdcCeEDazZbBA/-1,.{最后编码}解码过程为编码的逆过程。栈1.栈的特点：栈是一种线性表，对于它所有的插入和删除都限制在表的同一端进行，这一端叫做栈的“顶”，另一端则叫做栈的“底”，其操作特点是“后进先出”。2.栈的一般定义：数据结构（datastructure）第6页共7页6typestack=recorddata:array[1..m]ofdatatype;t:0..mend;vars:stack;3.栈的基本运算：(1)栈的插入push(s,x)：往栈st中推入一个值为x的项目；若t=m则print('overflow')否则t:=t+1;data[t]