下载文档原格式
《数据结构》第五版清华大学自动化系李宛洲2004年5月目录第一章数据结构--概念与基本类型 (6)1.1概述 (6)1.1.1数据结构应用对象 (6)1.1.2学习数据结构的基础 (7)1.1.2.1 C语言中的结构体 (7)1.1.2.2 C语言的指针在数据结构中的关联作用 (8)1.1.2.3 C语言的共用体(union)数据类型 (12)1.1.3数据结构定义 (15)1.2线性表 (17)1.2.1 顺序表 (18)1.2.2 链表 (20)1.2.2.1链表的基本结构及概念 (20)1.2.2.2单链表设计 (22)1.2.2.3单链表操作效率 (29)1.2.2.4双链表设计 (30)1.2.2.5链表深入学习 (32)1.2.2.6稀疏矩阵的三元组与十字链表 (36)1.2.3 堆栈 (41)1.2.3.1堆栈结构 (41)1.2.3.2基本操作 (42)1.2.3.3堆栈与递归 (44)1.2.3.4递归与分治算法 (45)1.2.3.5递归与递推 (49)1.2.3.6栈应用 (52)1.2.4 队列 (57)1.2.4.1队列结构 (57)1.2.3.2队列应用 (59)1.3非线性数据结构--树 (64)1.3.1 概念与术语 (64)1.3.1.1引入非线性数据结构的目的 (64)1.3.1.2树的定义与术语 (65)1.3.1.3树的内部节点与叶子节点存储结构问题 (66)1.3.2 二叉树 (66)1.3.2.1二叉树基本概念 (66)1.3.2.2完全二叉树的顺序存储结构 (68)1.3.2.3二叉树遍历 (69)1.3.2.4二叉树唯一性问题 (71)1.3.3 二叉排序树 (72)1.3.3.1基本概念 (72)1.3.3.2程序设计 (73)1.3.4 穿线二叉树 (79)1.3.4.1二叉树的中序线索化 (80)1.3.4.2中序遍历线索化的二叉树 (81)1.3.5 堆 (82)1.3.5.1建堆过程 (83)1.3.5.2在堆中插入节点 (85)1.3.6 哈夫曼树 (86)1.3.6.1最佳检索树 (86)1.3.6.2哈夫曼树结构与算法 (88)1.3.6.3 哈夫曼树应用 (90)1.3.6.4哈夫曼树程序设计 (92)1.3.7 空间数据结构----二叉树深入学习导读 (95)1.3.7.1k-d树概念 (96)1.3.7.2k-d树程序设计初步 (97)1.4非线性数据结构--图 (100)1.4.1图的基本概念 (100)1.4.2图形结构的物理存储方式 (103)1.4.2.1相邻矩阵 (103)1.4.2.2图的邻接表示 (104)1.4.2.3图的多重邻接表示 (106)1.4.3图形结构的遍历 (107)1.4.4无向连通图的最小生成树（minimum-cost spanning tree:MST） (110)1.4.5有向图的最短路径 (113)1.4.5.1单源最短路径（single-source shortest paths） (113)1.4.5.2每对顶点间最短路经（all-pairs shortest paths） (116)1.4.6拓扑排序 (117)第二章检索 (123)2.1顺序检索 (123)2.2对半检索 (124)2.2.1 对半检索与二叉平衡树 (124)2.2.2对半检索思想在链式存储结构中的应用---跳跃表 (127)2.3分块检索 (133)2.4哈希检索 (134)2.4.1哈希函数 (135)2.4.2闭地址散列 (136)2.4.2.1线性探测法和基本聚集问题 (136)2.4.2.2删除操作造成检索链的中断问题 (138)2.4.2.3随机探测法 (139)2.4.2.4平方探测法 (140)2.4.2.5二次聚集问题与双散列探测方法 (141)2.4.3开地址散列 (142)2.4.4哈希表检索效率 (142)第三章排序 (145)3.1交换排序方法 (145)3.1.1直接插入排序 (145)3.1.2冒泡排序 (147)3.1.3 选择排序 (148)3.1.4 树型选择排序 (149)3.2S HELL排序 (150)3.3快速排序 (152)3.4堆排序 (154)3.5归并排序 (156)3.6数据结构小结 (159)3.6.1 数据结构的基本概念 (159)3.6.2 数据结构分类 (159)3.6.2.1数据结构中的指针问题 (160)3.6.2.2线性表的效率问题 (161)3.6.2.3二叉树 (161)3.6.3排序与检索 (161)3.7算法分析的基本概念 (162)3.7.1基本概念 (162)3.7.2上限分析 (164)3.7.3下限分析 (164)3.7.4空间代价与时间代价转换 (165)第6章高级数据结构内容--索引技术 (167)6.1基本概念 (167)6.2线性索引 (168)6.2.1 线性索引 (168)6.2.2 倒排表 (169)6.32-3树 (170)6.3.1 2-3树定义 (172)6.3.2 2-3树节点插入 (173)6.4B+树 (178)6.4.1 B+树定义 (178)6.4.2 B+树插入与删除 (180)6.4.3 B+树实验设计 (182)第一章数据结构--概念与基本类型1.1概述1.1.1数据结构应用对象计算机应用可以分为两大类，一类是科学计算和工业控制，另一类是商业数据处理。
第一章绪论1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。
凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。
2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据元素的组成：一个数据元素通常由一个或若干数据项组成。
数据项：指具有独立含义的最小标识单位。
3.数据对象：性质相同的数据元素的集合，是数据的一个子集。
4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。
5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。
算法应满足以下性质：1)输入性：具有零个或若干个输入量；2)输出性：至少产生一个输出；3)有穷性：每条指令的执行次数是有限的；4)确定性：每条指令的含义明确，无二义性；5)可行性：每条指令都应在有限的时间内完成。
6.评价算法优劣的主要指标：1)执行算法后，计算机运行所消耗的时间，即所需的机器时间；2)执行算法时，计算机所占存储量的大小，即所需的存储空间；3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。
7.会估算某一算法的总执行时间和时间复杂度。
8.熟悉习题P32:3(5)-(9)、4(2)(3)第二章线性表1.线性表(P7)：是性质相同的一组数据元素序列。
线性表的特性：1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。
2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。
3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。
线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。
线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。
数据结构知识点概括第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。
·线性结构：一对一关系。
·线性结构：多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。
·顺序存储结构：如数组。
·链式存储结构：如链表。
·索引存储结构：·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·数据运算。
·对数据的操作。
定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT：·是抽象数据的组织和与之的操作。
相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。
算法取决于数据结构。
算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
评价算法的好坏的因素：·算法是正确的；·执行算法的时间；·执行算法的存储空间（主要是辅助存储空间）；·算法易于理解、编码、调试。
时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。
渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。
算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
期末复习 第一章 绪论 复习1、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。
2、算法分析的两个主要方面是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
4、数据项是数据的最小单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。
数据结构算 法数据：计算机处理的信息总称数据项：最小单位 数据元素：最基本单位数据对象：元素集合数据结构：相互之间存在一种或多种特定关系的数据元素集合。
概念：数据元素之间的关系 线性结构：一对一非线性结构 树：一对多 图：多对多顺序存储结构 链表存储结构 索引。
散列。
算法描述：指令的有限有序序列有穷性 确定性 可行性 输入 输出 时间复杂度 空间复杂度第二章 线性表 复习1、在双链表中，每个结点有两个指针域，包括一个指向前驱结点的指针 、一个指向后继结点的指针2、线性表采用顺序存储，必须占用一片连续的存储单元3、线性表采用链式存储，便于进行插入和删除操作4、线性表采用顺序存储和链式存储优缺点比较。
5、简单算法第三章 栈和队列 复习定义逻辑关系：前趋 后继节省空间 随机存取 插、删效率低 插入 删除1、 栈和队列的异同点。
2、 栈和队列的基本运算3、 出栈和出队4、 基本运算第四章 串 复习存储结构栈的概念：在一端操作的线性表 运算算法栈的特点：先进后出 LIFO初始化 进栈push 出栈pop顺序队列 循环队列队列概念：在两端操作的线性表 假溢出链队列队列特点：先进先出 FIFO基本运算顺序：链队：队空：front=rear队满：front=(rear+1)%MAXSIZE队空：rear 初始化 判空 进队 出队取队首元素第五章 数组和广义表 复习定义：由n(≥1)个字符组成的有限序列 S=”c 1c 2c 3 ……cn ”串长度、空白串、空串。
紧缩格式 非紧缩格式以字节为单位的存储格式 （C 语言用数组或指针表示） 基本运算strlen(s) 串长度 strcat(s1,s2) 联接 strcmp(s1,s2) 比较 strcpy(s1,s2) 复制 strstr(s1,s2) 子串查询模式匹配失败链接值匹配算法单字符链表串 多字符链表串串变量的存储映像：串名、串值对应关系表顺序存储方式压缩存储方式行优先顺序存放列优先顺序存放C语言数组：行优先下标从[0]开始，公式变化稀疏矩阵应用表达式程序调用广义表定义：n(≥0)个元素的有限序列表头：Head(A)= a1概念：长度、深度、原子、子表表尾：Tail(A)=(a2,a3,…,a n)表结点特殊矩阵对称矩阵三角矩阵对角矩阵三元组存储：三元组m n t链表存储：十字链表原子结点第六章 树 复习1、三个结点可以组成2种不同形态的树。
数据结构（C语言版）考研复习题第1 页共19 页第一章绪论1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
1.2 常用的存储表示方法有哪几种?1.3 算法的时间复杂度仅与问题的规模相关吗?1.4 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。
例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。
请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?函数大"O"表示优劣(1) T1(n)=5n22-3n+60lgn 5n22+O(n)(2) T2(n)=3n22+1000n+3lgn 3n22+O(n)(3) T3(n)=8n22+3lgn 8n22+O(lgn)(4) T4(n)=1.5n2+6000nlgn 1.5n2+O(nlgn)第二章线性表2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?2.3 为什么在单循环链表中设置尾指针比设置头指针更好?2.4 下述算法的功能是什么?LinkList Demo(LinkList L){ // L 是无头结点单链表ListNode *Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;}return L;}// Demo2.5设线性表的n个结点定义为(a0,a1,...a n-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList.2.6 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
