《数据结构(C语言版)》复习重点要点

1、数据结构 (C 语言版 )复习重点 重点在二、三、六、七、九、十章，考试内容两大类：概念，算法 第 1 章、绪论 1. 数据 ：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机 中并被计算机程序处理的符号的总称。 2. 数据元素 ：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑 和处理。 3. 数据结构 ：是相互之间存在一种或多种特定关系的数据元素的集合。 其 4类基本结构 ：集合、线性结构、树形结构、图状结构或网状结构 4. 逻辑结构 ：是数据元素之间的逻辑关系的描述。 5. 物理结构 (存储结构 )：是数据结构在计算机中的表示(又称映像)。 其 4种存储结构 ：顺序存

2、数结构、链式存数结构、索引存数结构、散列存数结构 6. 算法 ：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一 条指令表示一个或多个操作。 其 5个重要特性 ：有穷性、确定性、可行性、输入、输出 7. 时间复杂度：算法中基本操作重复执行的次数是问题规模 n的某个函数f(n), 算法的时间度量记作，T(n)=O(f(n)；他表示随问题规模n的增大，算法执行时 间的增长率和 f(n) 的增长率相同，称做算法的 渐进时间复杂度 ，简称时间复杂度 。 例如 ： (a) +x;s=0; (b) for(i=1;i=n;+i)+x;s += x; (c) for(j=1;j=n;+j) fo

3、r(k=1;knext为第一个结点地址，L-next=NULL为空表。 生成结点:p=(LinkList)malloc(sizeof(LNode) 回收结点：free(q) (b) 图乙7帯头结点的单链表 (a)养空表；(b)空表 图N8在单链表中插人结点时指针变化状况 (a)插人ffh (b)桶人后 s next = p next j p next = s； 图2在单链表中删除结点时指針 变化状况 P next = p next 一 next ； 2) 循环链表特点：表中最后一个结点的指针域指向头结点，整个链表形成一个 环。 循环链表的操作与线性链表基本一致，差别仅在于算法中的循环条件不是P

4、或 P-next是否为空，而是它们是否等于头指针。 (b) 图单循环链表 (a)非空Sh (b)空表 (a (h) IS 2.13仅设尾指针的循环链表 3)舸个桂表* 0)合井后的表 3) 双向链表特点：有2个指针域，其一指向直接后继，另一指向直接前趋 prior element next (b) 图2.1其每个分量的初始状态都是空指针。凡哈希地址为i的记 录都插入到头指针为 ChainHashi 的链表中。在链表中的插入位置可以在表头 或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。 d) 建立一个公共溢出区：假设哈希函数的值域为0,m-1，则设向量 HashTable0.m

5、-1 为基本表， 每个分量存放一个记录， 另设立向量 OverTable0.v 为溢出表。所有关键字和基本表中关键字为同义词的记录，不 管它们有哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。 例9-4已知例9-3中所示的一组关靄宇按哈希函数H(keyy=key MOD 13和线性 探测社理冲罠构遗所得哈希表a. elem：0. . 15如图P 27所示。 01234567 B 910 11121314 L5 U 01 27 5S 19 20 S4 79 23 11 10 图 9. 27elemO15 其昭柏函购为如y MUD】蘇处理冲宾为啟性探阀再散列 给定值K-84的査找过程为首

6、先求得哈希地址H(84) = 6t因a. dem：6不空且 够护84.见J找第一次冲突处理后的地址Wi=(6 + 1) MOD 16 = 7.而乩dem 门不空且乩已狂亡yH84.则找第二次冲突处理后的地址H= = (5-2) MOD 16 = 8皿el8不空且a. ekm8, key=84：W找成功，返回记录宦表中序号乩 给定值K=S8的査找过程为；先求哈需地址H(38) = 12ta.eleniri2不空且a. elem 】2yH3驰则找下一地址! = (12+1) MOD 16-13.1于孔ckmUS是空记录则 表明表中不存在关键宇等于辭的记录。 从哈希叢曲査找过程可见 (1)虽魅哈需*

7、在关键字与记录的存储位置之间建亚了直接映像但由于亠冲突协的 产生，使得哈希表的査找过程仍然是一个给定值和关键字进行比较的过程.因此*仍需取 平均査找悅度作为衡览哈希表的査找效率的蛍度* 査找过程中需和给定值进行比较的关镀字的个数取决于下列三个因素：哈希函 数，处理冲突的方法和哈希表的装填因子. 哈希函数的“好坏円首先影响出现冲突的频繁程度.但是，对于均匀的”哈希爾数可 以假定：不同的哈希雷数对同一组随机的关犍宇，产生冲突的可能性相同因为一録悄况 下设定的哈希函数是均匀的则可不考虑它对乎均査找长度的影响* 对同样一组关键字，设定相同的哈希函数，则不同的处理冲突的方法得到的喑希表不 同，它们的平均

8、査找长度也不同.如例9-3和例9-4中的两令哈希表，在记录的査找槪率 相等的前提下+前者链地址法)的平均査找悅度为 ASL(12) 士 1 6 + 2 U + 3 + 4) = 1.75 肓者(统性探测再燉列的乎均査找長度为 ASLC12) = (1 - 6 + 2 + 3*3 + 4 + 9) = 2.5 容易看出，线性探测再散列在处理冲突的过程中易产生记录的二欢聚集如既使得哈 需地址不相同的记录又产生新的冲夷，而琏地址法处理冲夷不会发生类似情况，因为呛希 地址不同的记录在不同的链轰中. 在一般情况下处理冲突方袪相同的哈希表+苴乎均査找长度依赖于哈希表的装 填因孔 呛希浪的装境園于定义为 表

9、中填人的记录数 - 哈希表的长度 标志怆雅丢的装構程度.直观地看卫越小，发生冲突的可能性就越小：反之卫越夫表 中旦填入的记录越塞再填记录时*发生冲突的可能性就越大则査找时，绪定值需与之进 行比较的关讎字的个数也就越參“ 可以证明凹 线性探測再散列的喑希表査找成功时的平均査找长度为 艮卞和1卡古)(9価 随机探测再锻列、二次探圏再戰列和再哈希的哈希表査找咸功时的平均查找氏度为 S -ilnCl-a)(928) a 链地址法飪理冲突的哈需表查找成功时的平均査找长度为 $41+于9-29) 由于哈希表在住找不成功时所用比较次数也和给定值有羌则可类似地定义哈希表 在査找不成功时的平均査找氏谨为匕査找不

10、应功时需和给定值进冇比较的关键字牛数的 期里值同样可证明不同的处理冲窝方雀构曲的盼羽农査找不加功时的平均査找怏度 分别为 g右) E线性操冏再散列 9-30) U1 3 if (9-31) 1 ft 伪鬧机探测再散列辱 U# 5 + 厂 链地址 (9-32) 第10章、内部排序 1. 排序：是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或 记录)的任意序列，重新排列成一个按关键字有序的序列。 2. 直接插入排序：将一个记录插入到已排好序的有序表中，从而得到一个新的、 记录数增1的有序表。 void InsertSort ( SqList 8lL) /对顺序衷L作直接摘人排序. f

11、or ( i = 2( i= L. lengthi + i ) if (LTL.ri.keyT U ri-l.key) / 化需将 L.ri插人有序子表 r0 = Urit/复制为呻兵 L+ ri = L,ri - for ( j = i - 2 LT(L, r0, key)tey) j - j) L.弓j +叮=L, rjj/记录后移 L.rr*l = L.t/j播人到正确位置 ) / InsertSort 初始关鬣字二 (49) 38 I 65 f=禺 (38) 将比根轴记录大的记录移到高端 L, rEloH.l = L. r0 return low； # Partition pivotkey 初始关键字 49 38 65 97 76 13 2749 U A i J -1 j 进行1次交换之后 27 38 65 97 76 13 49 A G H |T 亠J 片 进行2次交换之后 27 38 | 97 76 13 il 65 A 49 进行3次交换之后 27 38 i 13 97 G 76 -f j 65 49 P. A 进行4次交换之后 27 38 13 Hi. 76 97 !： 65 49 1 1 J. J 完成一越排序 27 亦 U 49 76 97 65 49 (a) 初始状态 (49 38 65 97 76 13 27 49 一次划分之后 27