数据结构 复 习

第一章 绪论 1.1 什么是数据结构（理解） 1.2 基本概念和术语（掌握） 1.3 抽象数据类型的表示与实现（了解） 1.4 算法与算法分析（运用）

计算机求解问题的步骤： 数据结构包括那些内容？ 数学模型 算法设计 程序设计 程序调试 与数据库有什么区别？ 数据库存放数据，存储，表达他们的关系。算法——解决问题的步骤。程序结果调试发现问题，反过来查找 程序调试

“算法+数据结构=程序设计” 《数据结构》的范畴 《数据结构》是研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作等等的学科 《数据结构》研究的主要内容 现实世界中数据的逻辑结构 描述计算问题的数学模型不是数学方程。 1968年美国克努特教授开创了数据结构的体系 数组存放冒泡例子的4个数。最简单的结构。如果数据的顺序乱放，我们可以用链表的指向信息（带后继单元的地址），恢复或者保持这钟逻辑的关系 第一节下课。 在计算机中的存储结构 各种非数值运算的算法 Niklaus Wirth (瑞士) “算法+数据结构=程序设计”

线性结构 逻辑结构 非线性结构 顺序存储方法 链式存储方法 数据结构 存储结构 索引存储方法 散列存储方法 数据结构 与算法 数据运算（查找，插入，修改、删除， 排序等） 算法特性 线性结构，线性表、堆栈、队列 非线性：树形、图形 标红色的也会介绍 算法描述 算法 算法设计方法 时间复杂度 算法分析 空间复杂度

数据 数据（Data） 数值 声音 文字 表格 图象 数据：是描述客观事物的符号。能被计算机加工的对象,或者说能被计算机输入、存储、处理和输出的一切信息。 数值 声音 数据 文字 表格 图象 数据是广义的概念

数据元素（Data Element) 关键字 数据元素：组成数据的、有一定意义的基本单元，在计算机中通常作为整体处理，也被称为记录。 比如：人类的数据元素是人。畜类的数据元素包括牛、马、羊、猪、鸡 等动物。 一个数据元素可由一个或多个数据项（Data Item）组成。 数据项是数据不可分的最小单元。 数据项是不可分割的最小单元 数据元素相当于C语言里的结构体struct，很多书就好像结构体数组 关键字

数据对象：性质相同的数据元素的集合，是数据的一个子集。 什么叫性质相同？指数据元素具有相同数量和类型的数据项。 数据对象（Data Object) 数据对象：性质相同的数据元素的集合，是数据的一个子集。 什么叫性质相同？指数据元素具有相同数量和类型的数据项。 比如，人都有姓名、生日、性别等相同的数据项。 有时也简称为数据。 字母字符数据对象： C={‘A’,’B’,,’Z’}

结构：简单理解就是“关系”。各个组成部分相互搭配和排列的方式。 数据结构（Data Structure） 结构：简单理解就是“关系”。各个组成部分相互搭配和排列的方式。 分子结构－组成分子的原子之间的排列方式。 组织结构－组成组织的人员之间的配合关系。 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 相互存在一种或多种关系的数据元素的集合 前面提到的主要针对这门课程，这里是对于这个概念 提问，看这些图，每种结构都有什么特点。集合：元素间没有关系，线性结构：一对一排列，收尾相连，树形：一对多，图：多对多 本节课20分钟时间点*

线性结构 逻辑结构 非线性结构 顺序存储方法 链式存储方法 数据结构 存储结构 索引存储方法 散列存储方法 数据结构 与算法 数据运算（查找，插入，修改、删除， 排序等） 算法特性 线性结构，线性表、堆栈、队列 非线性：树形、图形 标红色的也会介绍 算法描述 算法 算法设计方法 时间复杂度 算法分析 空间复杂度

集合 线性结构 树形结构 图状结构 数据结构（Data Structure） 逻辑结构 数据对象中数据元素之间的相互关系。也是本课最关注的问题。 集合 线性结构 相互存在一种或多种关系的数据元素的集合 前面提到的主要针对这门课程，这里是对于这个概念 提问，看这些图，每种结构都有什么特点。集合：元素间没有关系，线性结构：一对一排列，收尾相连，树形：一对多，图：多对多 本节课20分钟时间点* 树形结构 图状结构

Data Structure=(D,S) 二元组 逻辑结构的形式定义 数据结构（Data Structure） D----数据元素的有限集 形式化定义，把数据和关系从逻辑上分开。 举例：教务处人事表 二元组

线性结构 逻辑结构 非线性结构 顺序存储方法 链式存储方法 数据结构 存储结构 索引存储方法 散列存储方法 数据结构 与算法 数据运算（查找，插入，修改、删除， 排序等） 算法特性 线性结构，线性表、堆栈、队列 非线性：树形、图形 标红色的也会介绍 算法描述 算法 算法设计方法 时间复杂度 算法分析 空间复杂度

z2= -0.7 + 4.8i z1= 3.0 – 2.3i 顺序存储结构 链式存储结构 数据的表示 地址 … -2.3 3.0 0415 0611 0613 … 0300 3.0 0302 -2.3 … 两个字长的位串表示一个实数，则Z1=3.0-2.3i 对于链式结构，用实部、虚部的关系用值为0415的指针表示 复数需要自己定义一个数据类型：Complex = {D,S} D={real,reg}, S={<real,reg>}. Reg 翻译的不对，黑板没看清楚，重写 0632 -0.7 0634 4.8 … 地址 顺序存储结构 链式存储结构

C语言中，按照取值的不同，有两种数据类型： 数据类型（Data Type） C语言中，按照取值的不同，有两种数据类型： 原子类型：值不可分解 基本类型（整型、实型、字符型、枚举类型） 指针类型 空类型 结构类型：值可以分解，成分可以是非结构或结构的 回顾C语言的数据类型，int，float、double、char，数组、结构体、联合体，空类型：void 联合（板书）： 定义结构体，含short int x, char y; char z; Short两个字节，int和计算机字长有关系，char是1个字节，结构体大小是4个字节 如果是联合，共用一个存储单元，占用最长的那个来算，所以占用2个字节 结构体横起来算，联合体竖起来算，按最长的计算 指针占几个字节？和基类型无关，和平台有关，16位机，能访问到2的16次方即可，2字节。32位机，占4个字节 数组 结构 联合

抽象数据类型（ADT）

ADT=（D, S, P) 三元组 ADT 的表示 数据对象:(数据对象的定义) 数据关系:(数据关系的定义) 基本操作:(基本操作的定义) 抽象数据类型名{ 数据对象:(数据对象的定义) 数据关系:(数据关系的定义) 基本操作:(基本操作的定义) }ADT抽象数据类型名 三元组

算法的设计要求 1.4 算法及算法分析 算法：对特定问题求解步骤的一种描述，它是指令的有限序列。 正确性(Correctness) 可读性(Readability) 鲁棒性(Robustness) 效率(Efficiency and Low Storage Requirement)

1.4 算法及算法分析 时间复杂度

第二章线性表 2.1 线性表定义（理解） 2.2 线性表抽象数据类型（了解） 2.3 线性表顺序存储结构及操作（运用） 2.4 线性表链式存储结构及操作（运用） 2.5 一元多项式求解（了解）

用一组地址连续的存储单元依次存储线性表的数据元素. 2.3 线性表的顺序存储结构和操作 用一组地址连续的存储单元依次存储线性表的数据元素. 数组是最直接的一种线性表，逻辑相邻地址也相邻 数组操作优点——有位序，减一即是它的位置关系。随机存取，找第几个元素所需的时间一样

2.3 线性表的顺序存储结构和操作 特点 逻辑上相邻的元素在物理位置上也相邻 能对任何元素进行随机存取 存储位置可用简单、直观的公式来表示

复 习 线性表的顺序表示和实现 优点：元素存取非常方便； （随机存取） 缺点： 需要时时注意溢出问题 插入、删除操作复杂

顺序表的存储结构定义 顺序结构体的三要素： #define LIST_SIZE 100 //线性表存储空间的分配量 ElemType SqList[LIST_SIZE]; //存放线性表元素的一维数组 int length; //线性表长度 #define LIST_SIZE 100 //线性表存储空间的分配量 typedef struct{ ElemType elem[LIST_SIZE]; //存放线性表元素的一维数组 int length; //线性表长度 }SqList; typedef 定义一个新的类型

void *malloc(size_t size); 动态内存分配的有关函数 void *malloc(size_t size); void free(void *block); void *realloc(void *block, size_t size); realloc,malloc,calloc的区别 三个函数声明分别是: void* realloc(void* ptr, unsigned newsize); 申请一定长度空间 void *realloc(void ） 已分配的飞过来，再分配相应的空间 void* malloc(unsigned size); 分配的空间释放掉，参数传的是指针 void* calloc(size_t numElements, size_t sizeOfElement); 都在stdlib.h函数库内 它们的返回值都是请求系统分配的地址,如果请求失败就返回NULL malloc用于申请一段新的地址,参数size为需要内存空间的长度,如: char* p; p=(char*)malloc(20); calloc与malloc相似,参数sizeOfElement为申请地址的单位元素长度,numElements为元素个数,如: char* p; p=(char*)calloc(20,sizeof(char)); 这个例子与上一个效果相同 realloc是给一个已经分配了地址的指针重新分配空间,参数ptr为原有的空间地址,newsize是重新申请的地址长度 如: char* p; p=(char*)malloc(sizeof(char)*20); p=(char*)realloc(p,sizeof(char)*40); 注意，这里的空间长度都是以字节为单位。

(10)顺序表的插入 ? ai

插入操作的时间复杂性分析 T(n)=O(n) Pi是在第i个元素前插入一个元素的概率 在顺序表中插入元素，平均约移动一半元素

(11)顺序表的删除

删除操作的时间复杂性分析 T(n)=O(n) 在顺序表中删除元素，平均约移动一半元素

2.4 线性表链式存储结构及操作 基本概念 结点（Node） 结点的组成 单链表或线性链表 头指针VS头结点

data next LinkList p; LNode *p; 2.4 线性表链式存储结构及操作 带头结点的单链表的存储结构定义 typedef struct Lnode{ ElemType data; //数据域 struct Lnode *next; //指针域 }LNode, *LinkList; data next LinkList p; LNode *p;

X s->next=p->next; p->next=s 带头结点单链表的操作 (8)单链表的插入 a b p b a p s x （a）插入前 （b）插入后 s->next=p->next; p->next=s X p->next=s; s->next=p->next

p->next=q->next 带头结点单链表的操作 (9)单链表的删除 q q->next a b ... p c q = p->next p->next=q->next p->next = p->next->next

单链表与顺序表的对比 顺序表 单链表 存储分配方式 用一段连续的存储单元，依次存储线性表的元素。 用一组任意的存储单元存储线性表的元素。 时间复杂度 查找操作顺序表的时间复杂度为O(1) 插入和删除操作顺序表平均移动一般的元素，复杂度为O(n) 查找操作单链表的时间复杂度为O(n) 插入和删除操作单链表找到位置i的指针后，插入和删除操作的复杂度仅为O(1) 空间复杂度 需要考虑溢出问题。顺序表的最大长度的难以设置。 （套餐） 只要内存还有空间，随用随取，不限个数。 （自助餐）

通过上述对比，我们可以得出一些经验性结论： 单链表与顺序表的对比 通过上述对比，我们可以得出一些经验性结论： 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构； 例如，用户账户管理，除了注册时是插入，大多数情况是读取。 反之，若插入和删除操作频繁，查找少，宜采用单链表结构。 例如，游戏中玩家的武器装备。 当线性表中元素个数变化大，或者不知道有多大时，宜采用单链表结构 总之，要视情况选择。

静态链表 1 ZHAO 2 QIAN 3 SUN 4 LI 5 ZHOU 6 WU 7 ZHENG 8 WANG 9 10

循环链表 (Circular Linked List) H->next=H (b) 空循环链表表

双向链表(Double Linked List) typedef struct DuNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList data next prior data next

d->next->prior = d->prior->next = d 双向循环链表 (a) 空双向循环链表 d (b) 双向循环链表 d->next->prior = d->prior->next = d

线性链表存储方式的比较 Lnext O(1) 单重循环 O(n) 顺p结点的next无法找到其前驱 顺p结点的next可找到其前驱 找表头结点 找表尾结点 找P结点前驱结点 带头结点单链表L 带头结点循环单链表L 带尾指针的循环单链表R 带头结点的双向循环链表 操作名称 链表名称 Lnext O(1) 单重循环 O(n) 顺p结点的next无法找到其前驱 顺p结点的next可找到其前驱 O(n) Lnext O(1) 单重循环 O(n) 顺p结点的next可找到其前驱 O(n) 尾指针：指针指向后部 Rnext O(1) R O(1) Lnext O(1) Lprior O(1) pprior O(1)

总结与提高 1. 线性表的特征 线性结构 2. 线性表的存储方式 顺序存储（顺序表）：静态分配，C数组，适合于查找操作 3. 单链表的操作特点 顺链操作技术：从“头”开始访问 指针保留技术：对第i个结点进行插入、删除，需修改第i-1个结点的指针域 4. 链表处理中的相关技术 如何判断当前结点p是否为表尾 链表的判空条件

2.4 一元多项式的表示及相加

多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 pa pb -1 7 3 1 9 8 5 17 3 1 9 8 5 17 22 -9 A B pb

第三章栈和队列 3.1 栈的概念（掌握） 3.2 栈的抽象数据类型（了解） 3.3 顺序存储结构及操作（运用） 3.4 链式存储结构及操作（运用） 3.6 队列的定义（掌握） 3.7 队列的抽象数据类型（了解） 3.8 队列的链式存储结构（运用） 3.9 队列的顺序存储结构（运用）

LIFO 3.1 栈(Stack) … … … 栈顶 栈底 栈是限定在表尾进行插入和删除操作的线性表。 允许进行插入和删除操作的一端成为栈顶(top)， 另一端称为栈底(bottom)。 出栈 进栈 … … a n a 2 a 1 a 1 a 2 a n a1 --- 栈底元素 an --- 栈顶元素 栈顶 a n … LIFO Last In First Out a 2 栈底 a 1

3.6 队列(Queue) 队列是一种先进先出(First In First Out--FIFO) 的线性表。 它只允许在表的一端进行插入,而在另一端删除元素。 出队列 ... 入队列 a1 a2 a3 an an+1 队头 队尾 队尾

3.3 顺序存储结构及操作 … typedef struct{ SElemType *base; //栈底指针 SElemType *top; //栈指针 int stacksize; //当前分配的存储容量 //以元素为单位 }SqStack; S.stacksize S.top S.base a0 a1 … an SqStack S; S base top stacksize

顺序栈的操作 栈顶指针指向栈顶元素的下一个位置！ Overflow (上溢) Overflow是常见的问题 Underflow (下溢)

(2)销毁顺序栈 Status DestroyStack (SqStack &S){ free(S.base); S.base=NULL; S.top=NULL; S.stacksize=0; return OK: }// DestroyStack Base、top置为空（null）是为什么？防止野指针，无人管的指针 Free操作后，base地址不变，free给出信号给操作系统，告诉它这个区域不用了，其它程序再申请的话，可以给其它程序，其它程序中这个指针还是有效的，误操作可能导致错误 S NULL NULL

(4)顺序栈判空 栈的判空条件是什么？ Status StackEmpty (SqStack S){ return (S.top==S.base); //空栈条件 }// StackEmpty

(5)求顺序栈长度 int StackLength (SqStack S){ return (S.top-S.base); }// StackLength S.top 指针可以加减，指针加1跳几个？和基类型有关，char1格，短整形2格，长整形4格 an … a1 S.top-S.base S.base a0

e=*(S.top-1) (6)取顺序栈顶元素 if(S.top==S.base) return ERROR; … Status GetTop(SqStack S, SElemType &e){ if(S.top==S.base) return ERROR; e=*(S.top-1); return OK; }//GetTop S.top S.top - -以吗？不可以，- - 就把top给修改了，而取元素不改变top an … e=*(S.top-1) a1 S.base a0

e=*(S.top-1) S.top-- (7)顺序栈出栈 … Status Pop(SqStack &S,SElemType &e){ if(S.top==S.base) return ERROR; e=*--S.top; return OK; }//Pop S.top S.top =*--S.top先减再取内容 =*S.top- - 先去内容再减 an e=*(S.top-1) S.top-- … a1 S.base a0

(8)顺序栈入栈 *S.top=e S.top++ … Status Push(SqStack &S,SElemType e){ if(S.top-S.base>=S.stacksize){ //栈满,追加存储空间 S.base=(SElemType *)realloc(S.base,(S.stacksize+ STACKINCREMENT)*sizeof(SElemType)); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }//Push S.top e S.top Realloc重新分配空间 S.top=S.base+S.stacksize;满了之后，再其它地方从新分配一个空间同时将原来的内容搬家过去。新的top不能用原来的了 这个操作均摊到所有元素了 an *S.top=e S.top++ … a1 S.base a0

栈顶 栈底 栈的链式存储结构及操作 栈的链式存储结构简称栈链。 LinkStack S; an an-1 a1 typedef struct{ LinkList Head; //栈顶指针 int length; //长度 }LinkStack; . 用链表表示堆栈。操作的对象是top，操作头结点比较容易 课堂练习：写两个简单的程序：堆栈push、pop操作 第1个节点：S.head Push和单链表一样，新建一个节点，malloc空间，插入并链接 Pop是删除第一个节点，即直接p=S.head->next; 如果p为空，则返回error S.head->next = p->next *注意status的作用 栈底 a1 LinkStack S;

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列。 队列的链式存储结构——链队列 队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列。 为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。 头结点 队头 队尾 L front … a1 a2 an rear

基本操作（3） 入队列 … p->data=e p->next=NULL Q.rear->next=p Q.rear=p Status EnQueue(LinkQueue &Q,QElemType e){ p=(QueuePtr)malloc(sizeof(QNode)); if(!p) return ERROR; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; }//EnQueue p->data=e p->next=NULL Q.rear->next=p Q.rear=p Q.rear 2 e p 1 Q.front Q.rear … a1 a2 an

基本操作 出队列 … p=Q.front->next Q.front->next=p->next p an a1 a2 Status DeQueue (LinkQueue &Q,QElemType &e){ if(Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); return OK; }//DeQueue p=Q.front->next Q.front->next=p->next Q.front Q.rear p an Q.rear Q.front … a1 a2

“假溢出” “逻辑上”删除 3.4.4 队列的顺序存储结构 入队： Q.rear=Q.rear+1 出队： J7 6 入队： J6 5 Q.rear=Q.rear+1 J5 4 J4 3 出队： Q.front J3 2 Q.front=Q.front+1 J2 1 J1 “逻辑上”删除

循环队列 入队列： 出队列： 队列长度： J4 Q.rear=(Q.rear+1) % N J5 J3 J6 Q.front 入队列： J4 Q.rear=(Q.rear+1) % N J5 3 J3 4 出队列： 2 J6 5 1 Q.front=(Q.front+1) % N J2 6 J7 J1 队列长度： (Q.rear-Q.front+N) % N Q.rear

队列的“判空”，“判满” Q.front=(Q.rear+1)%N； （1）使用一个计数器记录队列队列长度； （3）人为“浪费”一个单元，令队满特征为 Q.front=(Q.rear+1)%N；

(7)入队列 e Q.base[Q.rear]=e Q.rear=(Q.rear+1)%N Status EnQueue(SqQueue &Q,QElemType e){ if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;//队列满 Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; return OK; }//EnQueue Q.rear Q.rear e Q.base[Q.rear]=e Q.rear=(Q.rear+1)%N Q.front

(8)出队列 e=Q.base[Q.front] Q.front=(Q.front+1)%MAXSIZE Status DeQueue (LinkQueue &Q,QElemType &e){ if(Q.front==Q.rear) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return OK; }//DeQueue Q.rear Q.front e=Q.base[Q.front] Q.front=(Q.front+1)%MAXSIZE Q.front

线性表、栈与队的异同点？ 相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点： ① 运算规则不同： 线性表为随机存取； 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO； 队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。

线性表、栈与队的异同点？ 相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点： ① 运算规则不同： 线性表为随机存取； 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO； 队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。

第四章 串 4.1 串的定义（掌握） 4.2串的抽象数据类型（了解） 4.3串的存储结构（运用） 4.4 串的模式匹配算法（难点）

4.1串的定义 串(String)：零个或多个字符组成的有限序列。 零个字符的串称为空串，它的长度为0，可以直接用双引号“”表示，也可以用希腊字母Φ表示。 字符位置：字符在序列中的序号 子串位置：子串的第一个字符在主串中的位置 空格串：由一个或多个空格组成的串 定位操作index的返回值是目标串在给定位置后第一次在主串中出现的位置。

4.1串的定义 串的比较 串相等的条件

4.1串的定义 串的比较 串的比较规则

基本操作:  (1) StrAssign (&T, *chars) //生成一个其值等于字符串常量chars的串T  (2) StrCompare (S,T) //若S>T，返回值>0，S=T，返回0，S<T，返回值<0  (3) StrLength (S) //求串长 (4) Concat(&T,S1,S2) //串联接，用T返回S1和S2联接而成的新串 (5) SubString(&Sub,S,pos,len) //求子串，用Sub返回串S的第pos个字符起 长度为len的子串 串的最小操作子集

T S V 课堂练习——串替换 S[0] (1) i=Index(S, T, i); Status Replace(SString S, SString T, SString V) T S S[0] (1) i=Index(S, T, i); (2) StrDelete(S, i, StrLength(T)); (3) StrInsert(S, i, V); V V[0]

课堂练习——串替换 Status Replace(SString S,SString T,SString V) { // 用V替换主串S中出现的所有与T相等的不重叠的子串 int i=1; // 从串S的第一个字符起查找串T if(StrEmpty(T)) return ERROR; // T是空串 do{ i=Index(S,T,i); // 结果i为从上一个i之后找到的子串T的位置 if(i){// 串S中存在串T StrDelete(S,i,StrLength(T)); // 删除该串T StrInsert(S,i,V); // 在原串T的位置插入串V i+=StrLength(V); // 在插入的串V后面继续查找串T } }while(i); return OK;

4.3串的存储结构 顺序存储结构 定长顺序表示 #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串长 SString T; MAXSTRLEN+1 T[0]

4.3串的存储结构 顺序存储结构 堆分配存储表示 typedef struct{ char *ch; //若串非空,则按串长分配存储区, //否则ch为NULL int length; //串长度 }HString;

4.3串的存储结构 链式存储结构 #define CHUNKSIZE 80 typedef struct{ typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; typedef struct{ Chunk *head,*tail; //串的头指针和尾指针 int curlen; //串的当前长度 }LString;

KMP算法

第六章 树和二叉树 6.1 树的定义（理解、运用） 6.2 树的抽象数据类型（了解） 6.3 树的存储结构（了解） 6.4 二叉树（重点） 6.3.1 二叉树的定义（掌握） 6.3.2 二叉树的性质（运用、重点） 6.3.3 二叉树的存储结构（掌握） 6.5 二叉树的遍历（掌握） 6.6 树和森林（了解） 6.7 赫夫曼树（了解）

6.4.1 二叉树的定义 二叉树特点

6.1 树的定义 树(Tree)：n(n≥0)个结点的有限集。 n=0时称为空树。 在任意一棵非空树中： 有且仅有一个特定的称为根结点的结点； 当n>1时，其余结点可分为m个互不相交的有限集合T、T2、…、Tm，其中每一个集合本身又是一棵树，并且称为根的子树

基本术语 结点（Node） 叶子（Leaf)或终端结点 分支结点或非终端结点 结点的度 (Degree) 树的度 孩子（Child) 双亲（Parent) 兄弟 (Sibling) 祖先 (Ancestor) 子孙 (Offspring) 层次 (Level) 有序树 无序树 森林(Forest) 堂兄第 树的深度 (Depth) 层次 1 2 3 4

6.3 树的存储结构 树的结点逻辑关系表示法： 双亲表示法 孩子表示法 孩子兄弟表示法

6.3.1双亲表示法 问题1：无法表达多个兄弟之间的长幼关系。如何解决呢？ 可以增加一个右兄弟域。记录右兄弟的下标。如果右兄弟不存在，则赋值为－1。 问题2: 如果同时关注结点的双亲、孩子和兄弟，则遍历算法时间复杂度较高。如何解决？ 继续扩展为双亲域＋长子域＋右兄弟域。 1 2 3 4 5 6 7 8 9

6.3.2 孩子表达法 把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中。 1 2 3 4 5 6 7 8 9

6.3.3 孩子兄弟表达法 任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，可以设置两个指针，分别指向该结点的第一个孩子和此节点的右兄弟。

二叉树

6.4.1 二叉树的定义 二叉树特点

特殊形态的二叉树 满二叉树 完全二叉树 非完全二叉树 完全二叉树-最后一层不满，所有节点都靠左对齐

6.2.2 二叉树的性质 性质1 满二叉树 完全二叉树 等比数列求和 性质2

性质3 N=n0+n1+n2-1

性质3

性质4 k-1层 k层 n

性质5

X 完全二叉树 1 2 3 4 5 6 7 8 9 10 11 12 i 2i 2i+1 非完全二叉树 2i+1 i 2i 假的顺序存储结构，只是用数组存放，关系不是线性相邻的关系 i 2i 顺序存储结构比较适合于完全二叉树或近似完全二叉树

二叉树的链式存储结构 typedef struct BiNode{ TElemType data; struct BiNode *lchild,*rchild; //左右孩子指针 }BiNode,*BiTree; PARENT 像双向链表，一个数据域，一个指针域 二叉链表 DATA LCHILD RCHILD 三叉链表

A B C D A B C D E F G A B C D E F G 二叉链表 三叉链表

6.5 二叉树的遍历 遍历方法 D L R 二叉树的遍历方式可以很多，如果我们习惯从左到右的顺序，那么主要有四种： 前序遍历 中序遍历 后序遍历 层序遍历 DLR LDR LRD DRL RDL RLD D 访问根结点 L 访问左子树 R 访问右子树

练习 先序： 中序： 后序： A B C D E F 都是在绕着遍历走一个包络，可以称为“周游” 根节点饶了三次，可以根据这三次的顺序确定先序/中/后序 边往下走，边访问 先序： 中序： 后序：

练习 先序： A B D E C F 中序： D B E A F C 后序： D E B F C A A B C D E F 都是在绕着遍历走一个包络，可以称为“周游” 根节点饶了三次，可以根据这三次的顺序确定先序/中/后序 边往下走，边访问 先序： A B D E C F 中序： D B E A F C 后序： D E B F C A

7.3 图的遍历（掌握，会求解深度优先生成树和广度优先生成树） 7.4 图的连通性问题 第七章 图 7.1 图的定义和术语（理解） 7.2 图的存储结构（掌握） 7.3 图的遍历（掌握，会求解深度优先生成树和广度优先生成树） 7.4 图的连通性问题 无向图的连通分量和生成树(理解) 有向图的强连通分量（理解） 最小生成树（重点掌握掌握） 7.5 有向无环图及其应用（理解）

7.2 图的存储结构 图的存储远比树和线性表复杂 前人总结出了五种“招式” “定点”或“邻接点”的位置是相对的。任何一个顶点都可以作为第一个定点，同一个定点的邻接点之间没有次序关系。 任意两个顶点之间都可能存在逻辑关系，所以不能用简单的顺序存储表达。 前人总结出了五种“招式” 邻接矩阵（重点） 邻接表（重点） 十字链表 邻接多重链表 边集数组

7.2.1 邻接矩阵

如果G是无向图则，邻接矩阵具有如下特性： 7.2.1 邻接矩阵 如果G是无向图则，邻接矩阵具有如下特性： 邻接矩阵是对称矩阵 顶点Vi的度是第i行的元素之和 定点Vi的所有邻接顶点就是将第i行遍历一遍

如果G是有向图则，邻接矩阵具有如下特性： 7.2.1 邻接矩阵 如果G是有向图则，邻接矩阵具有如下特性： 顶点Vi的出度是第i行的元素之和 顶点Vi的入度是第i列的元素之和

7.2.1 邻接矩阵 如果G是简单网图，则邻接矩阵定义为： 无穷大在程序中如何表示？

7.2.2 邻接表 邻接矩阵的问题 仿效树的孩子表示法，用数组与链表相结合的存储方式，这种图的表示法称为邻接表。 如果边数远远小于定点个数，则浪费空间 仿效树的孩子表示法，用数组与链表相结合的存储方式，这种图的表示法称为邻接表。 图的顶点用一维数组存储。 图中每个顶点Vi的所有邻接点构成一个线性表，用单链表存储。无向图称为顶点Vi的边表，有向图称为顶点Vi作为弧尾的出边表

有向图的邻接表

网图的邻接表

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

7.3.1 深度优先搜索(DFS) Depth First Search V1 V2 V3 V4 V5 V6 V7 V8

Depth First Search 在DFS过程中， 每条边被检查两次 7.3.1 深度优先搜索(DFS) V1 V2 V3 V4 V5

Depth First Search 7.3.1 深度优先搜索(DFS) V1 V2 V4 V8 V5 V3 V6 V7 V1 V2 V3

7.3.2 广度优先搜索(BFS) 与树的层序遍历类似。首先，将图中的顶点分层排列。 从某个顶点开始访问它的所有邻接顶点，再从最左端的邻接顶点开始，重复上述过程。

最小生成树的算法

第九章 查找 查找的概念（理解） 查找，静态查找表，动态查找表，平均查找长度 静态查找（掌握） 动态查找（掌握） 哈希表（了解）

9.1 查找的概念 查找按照操作方式可以分为两大类： 静态查找：使用静态查找表进行查找操作。 动态查找：使用动态查找表进行查找操作。

9.2 静态查找 查找的概念 静态查找 动态查找 哈希表 顺序查找 有序查找 折半查找（过程，算法及折半查找树的分析） 斐波那契查找 插值查找 线性索引查找 动态查找 哈希表

9.3 动态查找 查找的概念 静态查找 动态查找 二叉排序树（重点） 平衡二叉树（难点） 多路查找树（略） 哈希表

性能分析 平均查找长度（Average Search Length）

第十章 排序 10.1 排序的概念 10.2 交换排序 10.3 选择排序 10.4 插入排序 10.2.1 冒泡排序 10.2.2 快速排序 10.3 选择排序 10.3.1 简单选择排序 10.3.2 树形选择排序（锦标赛排序） 10.3.3 堆排序 10.4 插入排序 10.4.1 直接插入排序 10.4.2 希尔排序

10.2.1 冒泡排序 基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时“部分理顺”其他元素；一旦下趟没有交换发生，还可以提前结束排序。 前提：顺序存储结构

10.2.1 冒泡排序 从底向上

10.2.1 冒泡排序 性能分析 时间效率：O（n2) —因为要考虑最坏情况 空间效率：O（1） —只在交换时用到一个缓冲单元 稳 定 性： 稳定 详细分析： 最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。 最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟(1 i n) 做了n- i 次关键码比较，执行了n-i 次对象交换。此时的比较总次数KCN和记录移动次数RMN为：

10.2.2 快速排序 基本思想：通过一趟排序将待排序记录序列分割成成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！ 前提：顺序存储结构

快速排序 1 2 3 4 快速排序 第 1 趟 找大于49的关键字 找小于49的关键字 pivotkey=49 49 27 49 38 49 13 65 49 65 49 97 97 76 13 27 49+ high low high high high high low low low 1 2 3 4 第 1 趟

快速排序 快速排序 第 2 趟 pivotkey=49 pivotkey=27 pivotkey=76 27 49 49 38 49 13 65 65 97 49 97 76 13 27 49+ pivotkey=27 pivotkey=76 27 13 27 38 27 38 13 49 76 49+ 76 76 65 97 97 76 65 49+ low low high low low high high 第 2 趟

分别进行快速排序 快速排序 首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。 一次划分 无 序 的 记 录 序 列 一次划分 枢轴 无序记录子序列(1) 无序子序列(2) 分别进行快速排序

该方法实质上是一种分组插入方法 比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比[2]  较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。 一般的初次取序列的一半为增量，以后每次减半，直到增量为1。 给定实例的shell排序的排序过程 假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次为： 5，2，1[3]