2022年C语言版数据结构知识点汇总 .pdf

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

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

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

3、队形成的方块m * n 数组地址计算问题题目描述：已知N*(N+1) / 2 个数据，按行的顺序存入数组b1,b2, 中。其中第一个下标表示行，第二个下标表示列。若aij (i=j ,j=1,2,n)存于 bk 中，问： k,i,j 之间的关系如何表示？给定 k 值，写出能决定相应i,j 的算法。具体问题数学模型算法编程、 调试得到答案20 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 8 页 - - - - - - - - - - 名师整理精华知识点答案 K=i*(i-1)/2+j Rea

4、d(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 First 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

5、队列先进先出允 许 插 入 的 一 端 称 为 队 尾 (rear) ， 允 许 删 除 的 一 端 称 为 队 头 (front) 。 循环队列头指针指向队列中队头元素的前一个位置，尾指针指示队尾元素在队列中的当前位置。 树根、叶子、子树结点的度：结点拥有的子树数二叉树 二叉树特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。第 i 层至多有2i-1个结点（ i=1）深度为 K 的二叉树最多有2k-1个结点（ K=1 ） 二叉树的遍历先（根）序遍历ABDFGCEH 中（根）序遍历BFDGACHE 后（根）序遍历FGDBHECA (R-F+N) mod N 精品资料 - - - 欢迎

6、下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 8 页 - - - - - - - - - - 名师整理精华知识点 例题分析给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历： DGEBHIFCA ，画出此二叉树。 图 图的存储结构邻接矩阵有向图、无向图、带权图的邻接矩阵 排序冒泡排序选择排序快速排序希尔排序一、插入排序 (Insertion Sort) 1. 基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2. 排序过程：【示例】：

7、初始关键字 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. 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在

8、已排好序的数列的最后，直到全部待排序的数据元素排完。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 38 49 49 76 76 97 最后排序结果13 27 38 49 49 7

9、6 76 97 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 8 页 - - - - - - - - - - 名师整理精华知识点三、冒泡排序 (BubbleSort) 1. 基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。2. 排序过程：设想被排序的数组R1.N垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上漂浮，如此反复进行，直至最后任何两个气泡

10、都是轻者在上，重者在下为止。【示例】：49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 四、快速排序（Quick Sort）1. 基本思想：在当前无序区R1.H 中任取一个数据元素作为比较的基准(不妨记为 X)，用此基准将当前无序区划分为左右两个较小的无序区：R1.

11、I-1 和 RI+1.H ，且左边的无序子区中数据元素均小于等于基准元素， 右边的无序子区中数据元素均大于等于基准元素，而基准 X 则位于最终排序的位置上，即R1.I-1 X.Key RI+1.H(1 IH)，当 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 49J 向左扫描，位置不变，第三次交换后27 38 13 97 76 49

12、65 49I 向右扫描，位置不变，第四次交换后27 38 13 49 76 97 65 49J 向左扫描27 38 13 49 76 97 65 49 （一次划分过程）初始关键字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 看成是一颗完全二叉树的

13、顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。2. 堆的定义 : N 个元素的序列K1,K2,K3,.,Kn. 称为堆，当且仅当该序列满足特性：Ki K2i Ki K2i+1(1 I N/2) 六、几种排序算法的比较和选择1. 选取排序方法需要考虑的因素：(1) 待排序的元素数目n；(2) 元素本身信息量的大小；(3) 关键字的结构及其分布情况；(4) 语言工具的条件，辅助空间的大小等。2. 小结：(1) 若 n 较小 (n = 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接

14、选择排序较好。(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。(3) 若 n 较大，则应采用时间复杂度为O(nlog2n)的排序方法： 快速排序、 堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n 个关键字随机分布时，任何精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 8 页 - - - - -

15、- - - - - 名师整理精华知识点借助于 比较 的排序算法，至少需要O(nlog2n)的时间。(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。线性结构：串、栈、队列串一、串的概念串又称为字符串，是由0 个或多个字符组成的有限序列。长度为0 的串称为空串，它不包含任何字符。串用 和括起来。二、串的运算1.串的定义：一般用一维数组实现串的运算，由此串的定义也用数组的形式来实现：type stringtype=packed array1.80 of char; var s:stringtype; 另外，还有一种更简便的定义方法，利用turbo pascal 中

16、的 string 类型：var s:string; 但是 string 类型有一个限制：运用string 类型定义的数据长度只能是1 255，也就是说不能超过 255 个字符。2.串的标准函数在 turbo pascal 中有如下标准函数可实现串的运算：copy(s,x,y)：获取从s 的第 x 个位置开始的y 个字符concat(s1,s2,.,sn)：相等于 s1+s2+.+sn delete(s,x,y)：将 s 中从第 x 个位置开始的y 个字符删去insert(s1,s,x)：将 s1 插到 s 中的第 x 个位置length(s)：获取 s的长度3.串的基本运算(1)赋值(2)连接

17、(3)求串长(4)取子串(5)求子串序号(6)插入(7)删除(8)置换三、串的匹配算法示例：四、练习题：1.读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。 (句子末尾不一定用.结束 ) (word1) 2.一个句子，只含英文字母，单词间用空格或逗号作为分隔符。统计句子中的单词数，如果含有其他的字符，则只要求输出错误信息及错误类型。(word2) 含有大写字母错误类型error 1 数字（ 0-9) 错误类型error 2 其他非法字符错误类型error 3 如 输入：It is 12! 输出：error 1 2 3 输入：i am ,a student

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

19、 两两交换 CdcCeEDazZbBA/-1,. 最后编码 解码过程为编码的逆过程。栈1.栈的特点：栈是一种线性表， 对于它所有的插入和删除都限制在表的同一端进行，这一端叫做栈的 “顶”，另一端则叫做栈的“底” ，其操作特点是“后进先出”。2.栈的一般定义：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 8 页 - - - - - - - - - - 名师整理精华知识点type stack=record data:array1.m of datatype; t:0.m end; var s:s

20、tack; 3.栈的基本运算：(1)栈的插入push(s,x)：往栈 st 中推入一个值为x 的项目；若 t=m 则 print(overflow) 否则 t:=t+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)时，称它为空栈，函数取真值，否则值为假。若

21、t=0 则 sempty:=true 否则 sempty:=false; 4.栈的应用之一计算表达式的值(1)表达式的三种形式：中缀表达式：运算符放在两个运算对象中间，如：(2+1)*3 ；后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 * ；前缀表达式：同后缀表达式一样，不包含括号，运算符放在两个运算对象的前面，如：* + 2 1 3 。(2)表达式的计算：由于后缀表达式中没有括号，不需判别优先级，计算严格从左向右进行，故计算一个后缀表达式要比计算机一个中缀表达式简单得多。将中缀表达式转换为后

22、缀表达式的算法思想：当读到数字直接送至输出队列中当读到运算符t 时，a.将栈中所有优先级高于或等于t 的运算符弹出，送到输出队列中；b.t 进栈读到左括号时总是将它压入栈中读到右括号时， 将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号。运用后缀表达式进行计算的具体做法：建立一个栈S 从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y 和 X，然后以“ X 运算符Y”的形式计算机出结果，再压加栈S 中如果后缀表达式未读完，就重复上面过程，最后输出栈顶的数值则为结束5.栈的应用之二递归算法的非递归实现示例：队列1.队列

23、的特点：队列也是一种线性表，对于它所有的插入都在队列的一端进行，所有的删除都在另一端进行，进行删除的一端叫队列的“头”，进行插入的一端叫队列的“尾”，其操作特点是“先进先出”。2.队列的一般定义：type queue=record data:array1.m of datatype; head,tail:1.m end; var q:queue; 3.队列的基本操作：(1)队列的插入enq(q,x)：在队列 q 中插入一个值为x 的元素，也称为进队；qtail:=x; 若 tail=m 则 tail:=1 否则 tail:=tail+1; 若 tail=head 则 print(overflo

24、w) (2)队列的删除deq(q)：从队列q 中删除一个元素，也称为出队；精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 8 页 - - - - - - - - - - 名师整理精华知识点若 tail=head 则 print(underflow) 否则若 head=m 则 head:=1 否则 head:=head+1; (3)读队头元素head(q,x)：将队列 q 中头部元素的值读到x 中；若 tail=head 则 print(error) 否则 x:=qhead; (4)判队列是否为

25、空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)可以建立两种队列，

26、一种队列是存放数值的数值队列Q1，并有 Q1A 到 Q1Z 共 26 条数值队列，另一种队列Q2 存放字母，表示将要向该字母所对应的数值队列输入数值的事件队列。(2)根据题目要求，事件队列Q2 中应先放入字母L，表示首先输入L 数值队列的数据。(3)从事件队列Q2 中取出一个字母，并招待该字母对应的数值队列的数值输入，如果输入的数据中包含字母，则把字母放入事件队列中，并记录输入的数值中的最大值。(4)重复 (3)步骤，直到事件队列中为空。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 8 页 - - - - - - - - - - 文档编码：KDHSIBDSUFVBSUDHSIDHSIBF-SDSD587FCDCVDCJUH 欢迎下载 精美文档欢迎下载 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 8 页 - - - - - - - - - -