数据结构C语言版复习攻略
第一章:绪论
一、基础知识
概念和术语(黑体字部分)。
另外，注意:
1、数据元素是数据的基本单位。P4
2、数据项是数据不可分割的最小单位。P5
3、数据结构及其形式定义。P5
四种基本结构:?集合?线性结构?树形结构?图(网)状结构 4、数据结构的
逻辑结构(抽象的，与实现无关)
物理结构(存储结构) 顺序映像(顺序存储结构)位置“相邻”
非顺序映像(链式存储结构)指针表示关系P6 5、数据类型 P7
抽象数据类型(ADT)P7
ADT=(数据对象，数据关系，基本操作)
ADT细分为原子类型，固定聚合，可变聚合类型。P8 6、算法的概念 P13
7、算法的五个特征
?有穷性 ?确定性 ?可行性 ?输入(0个或多个) ?输出(1个或多个) 8、算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
的要求:?正确性?可读性?健壮性?效率与低存储量
其中正确性的四个层次(通常要求达到C层)。
9、算法的时间复杂度 P15 21n)，O(logn)，O(n logn)，O(2) 常见有: O(1)，O(n)，O(n22
语句频度，用归纳法计算。
10、算法的空间复杂度 P17
二、算法
起泡排序。P16
另一种形式
void BubbleSort ( DataType a[], int n )
{
for ( i=0; i
a[j+1] )
a[j]<—>a[j+1];
}
或
void BubbleSort ( DataType a[], int n )
{
for ( i=1; ia[j+1] )
a[j]<—>a[j+1];
}
或
1
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
算法的时间复杂度时，logn常简单记作log n。 2
void BubbleSort ( DataType a[], int n )
{
for ( i=0; ia[j+1] ) {
a[j]<—>a[j+1];
change = true;
}
if ( !change ) break;
}
}
说明:
a) 考试中要求写算法时，可用类C，也可用C程序。
b) 尽量书写算法说明，言简意赅。
c) 技巧:用“边界值验证法”检查下标越界错误。
如上第一个: 第二个循环条件若写作j
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
有序)，时间复杂度为O(n)。
第二章、线性表
一、基础知识和算法
1、线性表及其特点
线性表是n个数据元素的有限序列。 2线性结构的特点: ?“第一个” ?“最后一个” ?前驱 ?后继。 2、顺序表—线性表的顺序存储结构
(1)特点:a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。 (2)类型定义 3简而言之，“数组+长度”。
const int MAXSIZE = 线性表最大长度;
typedef struct{
DataType elem[MAXSIZE];
int length;
} SqList;
注:a) SqList为类型名，可换用其他写法。
b) DataType是数据元素的类型，根据需要确定。
c) MAXSIZE根据需要确定。如
const int MAXSIZE=64;
d) 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以
e) 课本上的SqList类型定义中listsize表示已经分配的空间大小(容纳数据元素的个
数)。当插入元素而遇到L.length==L.listsize时，用realloc (L.elem, L.listsize+增
2 这里太简炼了，只是为了便于记忆。 3 不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。
量) 重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。
(3)基本形态
1?. 顺序表空
条件 L.length==0 0 1 ... MAXSIZE-1 不允许删除操作 L.elem[L.length==0
] 2?. 顺序表满 L.elem[L.length==MAXSIZ 条件 L.length==MAXSIZE ] E 不允许插入操作 L.elem[0
步骤
新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤
第i至最后所有元素后移一个元素
在第i个位置插入元素x
表长增1
4?. 算法 4bool ListInsert ( SqList& L, int i, DataType x )
{
if ( L.length==MAXSIZE || i<1 || i>L.length+1 ) return false; // 失败
// 元素后移
for ( j=L.length-1; j>=i-1; j-- ) // 这里j为下标，从L.length-1到i-1
L.elem[j+1] = L.elem[j]; // 若作为位序，有如何修改,
// 插入x
L.elem[i-1] = x;
// 表长增1
L.length++;
4 这里返回true表示正确插入，返回false表示插入失败。以下常用来区分操作是否正确执行。
return true; // 插入成功
}
(3) 删除算法 ListDelete(&L,i,&x) 1?. 前提:表非空
2?. 合理的删除范围:1?i?L.length
3?. 步骤
取出第i个元素
第i个元素之后的元素向前移动一个位置
表长减1
4?. 算法
bool ListDelete ( SqList& L, int i, DataType& x )
{
if ( L.length==0 || i<1 || i>L.length ) return false; // 失败
x = L.elem[i-1];
for ( j=i; jnext == 0 L /\ 2?. 单链表不空
/\ L a ... a 条件:L->next != 0 1n
C
(10) 基本算法 (遍历) B
1?. 顺序访问所有元素 A 借助指针，“顺藤摸瓜”(沿着链表访问结点)。 (((((
bp = L->next; // 注意起始位置的考虑
) while ( p!=NULL ) { // 判表尾，另外 (p!=0)或(p)均可 (a visit( p->data ); // 访问:可以换成各种操作 ) p = p->next; // 指针沿着链表向后移动 E }
例:打印单链表中的数据。
void PrintLinkList ( LinkList L ) {
p = L->next;
while ( p!=NULL ) {
print ( p->data ); // 访问:打印数据域
p = p->next;
}
}
2?. 查找元素x
// 在单链表L中查找元素x
5 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
// 若找到，返回指向该结点的指针;否则返回空指针 LinkList Find ( LinkList L, DataType x )
{
p = L->next;
while ( p!=NULL ) {
if ( p->data == x ) return p; // 找到x
p = p->next;
}
return NULL; // 未找到
}
// 在单链表L中查找元素x
// 若找到，返回该元素的位序;否则返回0 int Find ( LinkList L, DataType x )
{
p = L->next; j = 1;
while ( p!=NULL ) {
if ( p->data == x ) return j; // 找到x
p = p->next; j++; // 计数器随指针改变
}
return 0; // 未找到
}
前一个算法的另一种写法:
p = L->next;
while ( p && p->data!=x )
p = p->next;
if ( p && p->data==x ) return p;
else return 0;
或者
p = L->next;
while ( p && p->data!=x ) p = p->next;
return p; // 为什么
3?. 查找第i个元素
LinkList Get ( LinkList L, int i )
{
p = L->next; j = 1;
while ( p && jnext; j++;
}
if ( p && j==i ) return p;
else return 0;
}
4?. 查找第i-1个元素
p = L; j = 0;
while ( p && jnext; j++;
}
if ( p && j==i-1 ) return p; else return 0;
(11) 插入算法 ListInsert(&L,i,x)
技巧:画图辅助分析。
思路:
先查找第i-1个元素
若找到，在其后插入新结点
6bool ListInsert ( LinkList &L, int i, DataType x )
{
// 查找第i-1个元素p
p = L; j = 0;
while ( p && jnext; j++; a ??i-1 } - - // 若找到，在p后插入x p s x
if ( p && j==i-1 ) {
执行?之后 s = (LinkList) malloc(sizeof(LNode));
a ?? s->data = x; i-1
- - s->next = p->next; // ? p s x ? ? p->next = s; // ? - return true; // 插入成功 执行?之后 } a ? ??i-1 else - - return false; // 插入失败 p s x ? ?} -
注意:
a) 要让p指向第i-1个而不是第i个元素(否则，不容易找到前驱以便插入)。
b) 能够插入的条件: p && j==i-1 。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。
c) 新建结点时需要动态分配内存。
s = (LinkList) malloc(sizeof(LNode));
若检查是否分配成功，可用
if ( s==NULL ) exit(1); // 分配失败则终止程序
d) 完成插入的步骤:??。技巧:先修改新结点的指针域。
6 这里返回true表示正确插入，返回false表示插入失败。
(12) 删除算法 ListDelete(&L,i,&x)
思路:
先查找第i-1个元素
若找到且其后存在第i个元素，则用x返回数据，并删除之
bool ListDelete ( LinkList &L, int i, int &x ) 删除前 {
a a???i-1i // 查找第i-1个元素p
- - - p = L; j = 0; p while ( p && jnext; j++; 执行?之后 } a a ???i-1i //若存在第i个元素，则用x返回数据，并删除之 - - - if ( p && j==i-1 && p->next ) { // 可以删除 p s ?
s = p->next; // ?
执行?之后 p->next = s->next; // ?
x = s->data; a a ???i-1i? - - - free (s); p s ? return true;
}
else
return false;
}
注意:
a) 要求p找到第i-1个而非第i个元素。为什么,
b) 能够进行删除的条件: p && j==i-1 && p->next 。条件中的p->next就是要保证第i个元素存在，否则无法删除。若写成p->next && j==i-1也不妥，因为此时(循环结束时)可能有p==NULL，所以必须先确定p不空。技巧:将条件中的“大前提”放在前面。该条件也不可以写成p->next && p && j==i-1，因为先有p!=0才有p->next，上式颠倒了这一关系。
c) 释放结点的方法。 free(s);
d) 完成删除的步骤:??。
(13) 建立链表的两种方法
思路:
建立空表(头结点);
依次插入数据结点(每次插入表尾得(a,a,„,a)，每次插入表头得(a,„,a,a))。 12nn211?. 顺序建表
void CreateLinkList ( LinkList &L, int n) {
// 建立空表
L = (LinkList) malloc(sizeof(LNode));
L->next = NULL; // 空表
p = L; // 用p指向表尾
// 插入元素
for ( i=0; idata = x;
// 插入表尾
s->next = p->next;
p->next = s;
p = s; // 新的表尾
}
}
2?. 逆序建表
void CreateLinkList ( LinkList &L, int n) {
// 建立空表
L = (LinkList) malloc(sizeof(LNode));
L->next = NULL; // 空表
// 插入元素
for ( i=0; idata = x;
// 插入表头
s->next = L->next;
L->next = s;
}
}
循环链表
(14) 特点
最后一个结点的指针指向头结点。
(15) 类型定义
同单链表。
(16) 基本形态 L 空表:L->next == L。
非空表。
... L a a 1n
C (17) 与单链表的联系 判断表尾的方法不同:单链表用p==NULL;循环链表用p==L。 B 其余操作相同。 双向循环链表 A
(
b
)
(a
)
E
(18) 特点
一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链表。
(19) 类型定义
typedef struct DuLNode {
DataType data;
data struct DuLNode *prior, *next; // 两个指针 prior next } DuLNode, *DuLinkList;
(20) 基本形态
空表:用后向指针判断L->next == L，或者用前向指针判断L->prior == L。 非空表。
L L ... ... a a a 12n
(21) 与单链表和循环链表的联系
最大不同:前驱容易求得，可以向前遍历。
判断表尾的方法与循环链表相同:p==L。
插入和删除时需要修改两个方向的指针。
(22) 插入和删除
需要修改两个方向的指针。例如:(见下表)
表 错误～文档中没有指定样式的文字。2.2 双向循环链表的插入和删除 p之后插入s p之前插入s 删除p之后继s 删除p s->next = s->prior = s = p->next; p->prior->next = p->next; p->prior; p->next = p->next; p->next = s; p->prior = s; s->next; p->next->prior =
s->prior = p; s->next = p; p->next->prior = p->prior; s->next->prior s->prior->next = p;
= s; s;
顺序表与单链表的比较
表 错误～文档中没有指定样式的文字。2.3 顺序表和单链表的比较
顺序表 单链表 以地址相邻表示关系 用指针表示关系 随机访问，取元素O(1) 顺序访问，取元素O(n) 插入、删除需要移动元素O(n) 插入、删除不用移动元素O(n)(用于查找
位置)
总结:需要反复插入、删除，宜采用链表;反复提取，很少插入、删除，宜采用顺序表。
第三章、栈和队列
栈
栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。 顺序栈:栈的顺序存储结构;链栈:栈的链式存储结构。
链栈
存储结构
用不带头结点的单链表实现。 S a a ... /\ ann-11
类型定义
同单链表。
基本形态
1?. 栈空
条件: S == NULL S /\ 2?. 栈非空
S ... a a /\ a3?. 栈满(一般不出现) nn-11
基本算法
4?. 入栈 Push (&s, x)
bool Push ( LinkList &s, DataType x )
{
// 新建结点
p = (LinkList) malloc (sizeof(LNode));
if ( !p ) return false; // 失败
p->data = x;
// 插入栈顶
p->next = s;
s = p;
return true;
}
5?. 出栈 Pop (&s, &x)
前提:栈非空。
bool Pop ( LinkList &s, DataType &x )
{
if ( s==NULL ) return false; // 栈空
// 删除栈顶元素
p = s;
s = s->next;
x = p->data;
free ( p );
return true;
}
6?. 栈顶元素
前提:栈非空。
bool Top ( LinkList &s, DataType &x )
{
if ( s==NULL ) return false; // 栈空
x = s->data;
return true;
}
顺序栈
存储结构
类似于顺序表，插入和删除操作固定于表尾。 类型定义 7简单说，“数组 + 长度”。
const int MAXSIZE = 栈的最大容量;
typedef struct {
DataType elem[MAXSIZE];
int top;
} SqStack;
基本形态
7?. 栈空
条件 s.top == 0;
8?. 栈满
条件 s.top == MAXSIZE 9?. 栈不空、不满
基本算法
10?. 入栈 Push (&s, x)
前提:栈不满
bool Push ( SqStack& s, DataType x )
{
if ( s.top == MAXSIZE ) return false; // 栈满
s.elem[top] = x; // 或者s.elem[top++] = x;
top++; // 代替这两行
return true;
}
11?. 出栈 Pop (&s, &x)
前提:栈非空
bool Pop ( SqStack &s, DataType &x )
{
if ( s.top==0 ) return false;
top--; // 可用x=s.elem[--top];
x = s.elem[top]; // 代替这两行
return true;
}
7 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
12?. 栈顶元素
前提:栈非空
s.elem[top-1] 即是。
队列
队列，队头，队尾，空队列，先进先出(FIFO)。 链队列:队列的链式存储结构。
循环队列:队列的顺序存储结构之一。 链队列
存储结构 8。 简而言之，“单链表 + 尾指针”
类型定义
课本P61。
typedef struct { Q.front /\ LinkList front; Q.rear LinkList rear; } LinkQueue; Q.front ... a a a /\ ???12n
- - - Q.rear 基本形态
队列空:Q.front==Q.rear。
非空队列。
基本算法
13?. 入队列
课本P62。插入队尾，注意保持Q.rear指向队尾。 14?. 出队列
课本P62。删除队头元素，
特别注意:如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改
队尾指针。
循环队列
存储结构 9简单说，“数组 + 头、尾位置”。
类型定义
const int MAXSIZE = 队列最大容量; typedef struct {
DataType elem[MAXSIZE];
int front, rear; // 队头、队尾位置 } SqQueue;
8 不准确的说法，只为便于理解和记忆，不要在正式场合引用。 9 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
基本形态
通常少用一个元素区分队列空和队列满，也可以加一标志。约定front指向队头元素的位置，rear指向队尾的下一个位置，队列内容为 [front, rear)。 15?. 队列空
条件:Q.front == Q.rear。
不能出队列。
16?. 队列满
条件:(Q.rear+1)%MAXSIZE == Q.front (少用一个元素时)。 不能入队列。
17?. 队列不空也不满
front rear front rear tag:0
aa a a a a a1323412
rear front rear front
aa a a a a a a a 134234512
rear front rear front tag:1 18?. 加一标志区分队列空和队列满的情况
可以用满所有空间。队列空和队列满时都有Q.front==Q.rear，再用标志区分。 队列空:Q.front==Q.rear and Q.tag==0;队列满:Q.front==Q.rear and Q.tag==1。 基本算法
19?. 入队列
前提:队列不满。
bool EnQueue ( SqQueue &Q, DataType x ) {
if ( (Q.rear+1)%MAXSIZE==Q.front ) return false; // 队列满
// 入队列
Q.elem [Q.rear] = x;
Q.rear = (Q.rear+1)%MAXSIZE;
return true;
}
20?. 出队列
前提:队列非空。
bool DeQueue ( SqQueue &Q, DataType &x ) {
if ( Q.front==Q.rear ) return false; // 队列空
// 出队列
x = Q.elem [Q.front];
Q.front = (Q.front+1)%MAXSIZE;
return true;
}
21?. 队列中元素个数
结论:(Q.rear-Q.front+MAXSIZE)%MAXSIZE。
注:Q.rear-Q.front可能小于0，需要加上MAXSIZE。
int QueueLength ( SqQueue Q ) {
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; }
22?. 用标志区分队列空和满
用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下: void InitQueue ( SqQueue &Q ) {
Q.front = Q.rear = 0; Q.tag = 0; }
bool EnQueue ( SqQueue &Q, DataType x ) { if ( Q.front==Q.rear and Q.tag==1 ) return false;
Q.elem[ Q.rear ] = x;
Q.rear = (Q.rear+1)%MAXSIZE;
if ( Q.tag==0 ) Q.tag = 1; // 队列非空
return true;
}
bool DeQueue ( SqQueue &Q, DataType &x ) {
if ( Q.front==Q.rear and Q.tag==0 ) return false;
x = Q.elem[ Q.front ];
Q.front = (Q.front+1)%MAXSIZE;
if ( Q.front==Q.rear ) Q.tag = 0; // 队列空
return true;
}
int QueueLength ( SqQueue Q ) {
if ( Q.front==Q.rear and Q.tag==1 )
return MAXSIZE; // 队列满
else
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; // 队列不满(包含队列空的情况) }
栈和队列比较
都是线形结构，栈的操作LIFO(后进先出)，队列操作FIFO(先进先出)。 简化的栈和队列结构
在算法中使用栈和队列时可以采用简化的形式。
表 错误～文档中没有指定样式的文字。3.4 简化的栈和队列结构
简化栈 简化队列 结构 “s[] + top” 结构 “q[] + front + rear” 初始化 top = 0; 初始化 front=rear=0; 入栈 s[top++] = x; 入队列 q[rear] = x;
rear = (rear+1)%MAXSIZE; 出栈 x = s[--top]; 出队列 x = q[front];
front = (front+1)%MAXSIZE; 栈顶 s[top-1] 队列头 q[front] 栈空 top == 0 队列空 front == rear 说明:只要栈(队列)的容量足够大，算法中可以省去检查栈(队列)满的情况。 栈和队列的应用
23?. 表达式求值
参见课本P53。
24?. 括号匹配
例:检查表达式中的括号是否正确匹配。如{ ( ) [ ] }正确，( [ ) ] }则错误。 分析:每个左括号都“期待”对应的右括号，匹配成功则可以消去。 思路:遇到左括号则入栈，遇到右括号则与栈顶括号相比较，如果匹配则消去，否则匹配失败。当然，如果栈中没有括号可以匹配，或者最后栈中还有未匹配的左括号，也都是匹配错误。
// 检查输入的表达式中括号是否匹配
bool MatchBrackets ()
{
const int MAXSIZE = 1024; // 栈的最大容量
char s [MAXSIZE]; // 简化的栈结构
int top; // 栈顶
// 栈初始化
top = 0;
// 检查括号是否匹配
ch = getchar();
while ( ch!=EOF ) {
switch ( ch ) {
case ‘(‘, ‘[’, ‘{’:
s [top++] = ch; // 所有左括号入栈
break;
’: case ‘)
if ( top==0 or s [--top]!=’(’ ) return false; // 栈空或右括号与栈顶左括号失配
case ‘]’:
( top==0 or s [--top]!=’[’ ) return false; if
case ‘}’:
if ( top==0 or s [--top]!=’{’ ) return false;
}
ch = getchar(); // 取下一个字符
}
if ( top==0 ) return true; // 正好匹配
else return false; // 栈中尚有未匹配的左括号 }
25?. 递归程序的非递归化
将递归程序转化为非递归程序时常使用栈来实现。
26?. 作业排队
如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队列。 27?. 按层次遍历二叉树
void LevelOrder ( BinTree bt, VisitFunc visit )
{
const int MAXSIZE = 1024; // 队列容量(足够大即可)
BinTree q [MAXSIZE]; // 简化的队列结构
int front, rear; // 队头、队尾
if ( ! bt ) return ;
// 初始化队列，根结点入队列
front = rear = 0;
q [rear] = bt;
rear = (rear+1)%MAXSIZE;
// 队列不空，则取出队头访问并将其左右孩子入队列
while ( front!=rear ) {
p = q [front];
front = (front+1)%MAXSIZE;
if ( p ) {
visit ( p->data ); // 访问结点
q [rear] = p->lchild;
rear = (rear+1)%MAXSIZE;
q [rear] = p->rchild;
rear = (rear+1)%MAXSIZE;
}
}
}
第四章串
基础知识和算法
概念
串，空串，空格串，串的长度;子串，子串在主串中的位置，主串;串相等。 串的基本操作
表 错误～文档中没有指定样式的文字。4.5 串的基本操作 Assign (s, t), Create Assign(s,t)将变量t赋值给s，Create(s,cs)根据字串创(s, cs) 建变量s。
Equal (s, t), Length 判断串相等，求串长度。如Length(“”)=0。 (s)
Concat (s, t) 串连接。如Concat(“ab”,”cd”)=”abcd”。 Substr (s, pos, len) 取子串，pos为开始位置，len为子串长度。 Index (s, t) 求子串t在主串s中的位置。如Index(“abc”,”ab”)=1，
Index(“a bc”,”bc”)=3。
Replace (s, t, v) 把串s中的字串t替换成v。如Replace(“aaa”,”aa”,”
a”)=”aa”。
Delete (s, pos, len) 删除串s的一部分。
注:完成习题集4.1~4.6。
串的存储结构
表 错误～文档中没有指定样式的文字。4.6 串的存储结构 定长顺序串 最大长度固定，超过最大长度则作截断处理 堆分配存储表示 串的长度几乎没有限制
块链存储表示 块内存储空间连续，块间不连续
树和二叉树
基础知识和算法
树及有关概念
树，根，子树;结点，结点的度，叶子(终端结点)，分支结点(非终端结点)，内部结点，
树的度;孩子，双亲，兄弟，祖先，子孙，堂兄弟;层次(根所在层为第1层)，深度，高
度;有序树，无序树，二叉树是有序树;森林。
二叉树
二叉树(二叉树与度为2的树不同，二叉树的度可能是0，1，2);左孩子，右孩子。
二叉树的五种基本形态。
二叉树的性质
10i-128?. 二叉树的第i层上至多有2个结点。
k29?. 深度为k的二叉树至多有2-1个结点。 k 满二叉树:深度为k，有2-1个结点。
完全二叉树:给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结
点在对应满二叉树中的编号正好是从1到n。
30?. 叶子结点n，度为2的结点为n，则n= n+1。 020 2
考虑结点个数:n = n + n + n012
考虑分支个数:n-1 = 2n + n 21
可得n= n+1 0 2
例:1) 二叉树有n个叶子，没有度为1的结点，共有 个结点。 2) 完全二叉树的第3
层有2个叶子，则共有 个结点。
分析:1) 度为2的结点有n-1个，所以共2n-1个结点。 2) 注意考虑到符合条件的二叉
树的深度可能是3或4，所以有5、10或11个结点。 31?. n个结点的完全二叉树深度为。 logn，1，，
32?. n个结点的完全二叉树，结点按层次编号
有: i的双亲是，如果i = 1时为根(无双亲); n/2，，
i的左孩子是2i，如果2i>n，则无左孩子;
i的右孩子是2i + 1，如果2i + 1>n则无右孩子。 二叉树的存储结构
33?. 顺序存储结构
用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。
10 本书中约定根结点在第1层，也有约定根在第0层的，则计算
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
会有所不同。
34?. 链式存储结构
二叉链表:
typedef struct BTNode {
DataType data;
struct BTNode *lchild, *rchild;
} BTNode, *BinTree;
三叉链表:
typedef struct BTNode {
DataType data;
struct BTNode *lchild, *rchild, *parent;
} BTNode, *BinTree;
lchild data rchild lchild data parent rchild
例:用二叉链表存储n个结点的二叉树(n>0)，共有(_a_)个空指针域;采用三叉链表存储，11b_)个空指针域。 共有(_
二叉树的五种基本形态
? ? ? ? ? ?空树:bt==NULL ?左右子树均空:bt->lchild==NULL and bt->rchild==NULL
?右子树为空:bt->rchild==NULL ?左子树为空:bt->lchild==NULL
?左右子树均非空。
前两种常作为递归结束条件，后三者常需要递归。 遍历二叉树
35?. 常见有四种遍历方式
按层次遍历，先序遍历，中序遍历，后序遍历。 - 按层次遍历:“从上至下，从左至右”，利用队列。 + / 先序遍历:DLR;中序遍历:LDR;后序遍历LRD。
a * e f 例:写出a+b*(c-d)-e/f的前缀、中缀和后缀表达式。 画出二叉树，分别进行前序、中序、后序遍历即可得到。 b - 前缀表达式:- + a * b - c d / e f c d 中缀表达式:a + b * c - d - e / f 后缀表达式:a b c d - * + e f / -
36?. 先序遍历算法
void Preorder ( BinTree bt ) {
if ( bt ) {
visit ( bt->data );
11 答案:(a) n+1 (b) n+2。提示:只有根结点没有双亲。
Preorder ( bt->lchild );
Preorder ( bt->rchild );
}
}
37?. 中序遍历算法
void Inorder ( BinTree bt ) {
if ( bt ) {
Inorder ( bt->lchild );
visit ( bt->data );
Inorder ( bt->rchild );
}
}
38?. 后序遍历
void Postorder ( BinTree bt ) {
if ( bt ) {
Postorder ( bt->lchild );
Postorder ( bt->rchild );
visit ( bt->data );
}
}
39?. 按层次遍历
思路:利用一个队列，首先将根(头指针)入队列，以后若队列不空则取队头元素p，如果
p不空，则访问之，然后将其左右子树入队列，如此循环直到队列为空。 void LevelOrder ( BinTree bt ) {
// 队列初始化为空
InitQueue ( Q );
// 根入队列
EnQueue ( Q, bt );
// 队列不空则继续遍历
while ( ! QueueEmpty(Q) ) {
DeQueue ( Q, p );
if ( p!=NULL ) {
visit ( p->data );
// 左、右子树入队列
EnQueue ( Q, p->lchild );
EnQueue ( Q, p->rchild );
}
}
}
若队列表示为“数组q[] + 头尾 front, rear”有:
void LevelOrder ( BinTree bt ) {
const int MAXSIZE = 1024;
BinTree q[MAXSIZE];
int front, rear;
// 队列初始化为空
front = rear = 0;
// 根入队列
q[rear] = bt; rear = ( rear+1 ) % MAXSIZE;
// 队列不空则循环
while ( front != rear ) {
p = q[front]; front = ( front+1 ) % MAXSIZE;
if ( p ) {
visit ( p->data );
// 左、右子树入队列
q[rear] = p->lchild; rear = ( rear+1 ) % MAXSIZE;
q[rear] = p->rchild; rear = ( rear+1 ) % MAXSIZE;
}
}
}
40?. 非递归遍历二叉树
一般借助栈实现。设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。 (a) 中序非递归遍历
指针p从根开始，首先沿着左子树向下移动，同时入栈保存;当到达空子树后需要退栈访问结点，然后移动到右子树上去。
void InOrder ( BinTree bt, VisitFunc visit ) {
InitStack ( S );
p = bt;
while ( p || ! StackEmpty(S) ) {
if ( p ) {
Push ( S, p );
p = p->lchild;
} else {
Pop ( S, p );
visit ( p ); // 中序访问结点的位置
p = p->rchild;
}
}
}
(b) 先序非递归遍历
按照中序遍历的顺序，将访问结点的位置放在第一次指向该结点时。 void Preorder ( BinTree bt, VisitFunc visit )
{
InitStack ( S );
p = bt;
while ( p || ! StackEmpty(S) ) {
if ( p ) {
visit ( p ); // 先序访问结点的位置
Push ( S, p );
p = p->lchild;
} else {
Pop ( S, p );
p = p->rchild;
}
}
}
或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。 void Preorder ( BinTree bt, VisitFunc visit )
{
InitStack ( S );
Push ( S, bt );
while ( ! StackEmpty(S) ) {
Pop ( S, p );
if ( p ) {
visit ( p );
Push ( S, p->rchild ); // 先进栈，后访问，所以
Push ( S, p->lchild ); // 这里先让右子树进栈
}
}
}
(c) 后序非递归遍历
后序遍历时，分别从左子树和右子树共两次返回根结点，只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。
void PostOrder ( BinTree bt, VisitFunc visit )
{
InitStack ( S ), InitStack ( tag );
p = bt;
while ( p || ! StackEmpty(S) ) {
if ( p ) {
Push ( S, p ), Push ( tag, 1); // 第一次入栈
p = p->lchild;
} else {
Pop ( S, p ), Pop ( tag, f );
if ( f==1 ) {
// 从左子树返回，二次入栈，然后p转右子树
Push ( S, p ), Push ( tag, 2 );
p = p->rchild;
} else {
// 从右子树返回(二次出栈)，访问根结点，p转上层
visit ( p );
p = NULL; // 必须的，使下一步继续退栈
}
}
}
}
注:后序非递归遍历的过程中，栈中保留的是当前结点的所有祖先。这是和先序及中序遍
历不同的。在某些和祖先有关的算法中，此算法很有价值。 41?. 三叉链表的遍历算法
下面以中序遍历为例。
// 中序遍历三叉链表存储的二叉树
void Inorder ( BinTree bt, VisitFunc visit )
{
if ( bt==NULL ) return; // 空树，以下考虑非空树
// 找到遍历的起点
p = bt; // Note: p!=null here while ( p->lchild ) p = p->lchild;
// 开始遍历
while ( p ) {
// 访问结点
visit ( p );
// p转下一个结点
if ( p->rchild ) { // 右子树不空，下一个在右子树
p = p->rchild;
树的最左下结点 while ( p->lchild ) p = p->lchild; // 转右子
} else { // 右子树为空，下一个在上层
f = p->parent;
( p == f->rchild ) { // 若p是右子树则一直上溯 while
p = f; f = f->parent;
}
}
}
}
A 遍历二叉树的应用 B C 42?. 写出遍历序列(前、中、后序)
D E F 43?. 根据遍历序列画出二叉树
(a) 已知前序和中序序列，唯一确定二叉树。 H G 例:前序:ABDEGCFH，中序:DBGEAFHC，画出二叉树。
分析:前序序列的第一个是根，这是解题的突破口。
步骤:?前序序列的第一个是根 ?在中序序列中标出根，分成左右子树 ?在前序序列中
标出左右子树(根据结点个数即可) ?分别对左右子树的前序和中序序列重复以上步骤直
至完成。
(b) 已知后序和中序序列，唯一确定二叉树。
例:后序:DGEBHFCA，中序:DBGEAFHC，画出二叉树。
分析:后序序列的最后一个是根，这是解题的突破口。
步骤:?后序序列的最后一个是根 ?在中序序列中标出根，分成左右子树 ?在后序序列中标出左右子树(根据结点个数即可) ?分别对左右子树的后序和中序序列重复以上步骤直至完成。
(c) 已知前序和后序序列，不存在度为1的结点时能唯一确定二叉树。 例:前序:ABDEC，后序:DEBCA，画出二叉树。又前序AB，后序BA则不能唯一确定二叉树。 注:对于不存在度为1的结点的二叉树，首先确定根结点，然后总可以将其余结点序列划分成左右子树，以此类推即可确定二叉树。
说明:画出二叉树后可以进行遍历以便验证。
44?. 编写算法
思路:按五种形态(?--?)分析，适度简化。
例:求二叉树结点的个数。
分析:? 0; ? 1; ? L+1; ? 1+R; ? 1+L+R。
简化:? 1+L+R ? 1+L+R ? 1+L+R ? 1+L+R 可合并成?一种情况。 =0=0=0=0
int NodeCount ( BinTree bt )
{
if ( bt==0 ) return 0;
else return 1 + NodeCount(bt->lchild) + NodeCount(bt->rchild);
}
例:求二叉树叶子结点的个数。
分析:? 0; ? 1; ? L; ? R; ? L+R。简化:???可合并成?。 int LeafCount ( BinTree bt )
{
if ( bt==0 ) return 0;
else if ( bt->lchild==0 and bt->rchild==0 ) return 1;
else return LeafCount(bt->lchild) + LeafCount(bt->rchild);
}
例:求二叉树的深度。
0; ? 1; ? 1+L; ? 1+R; ? 1+max(L,R)。简化:????可合并成?。 分析:?
int Depth ( BinTree bt )
{
if ( bt==0 ) return 0;
else return 1 + max(Depth(bt->lchild), Depth(bt->rchild));
}
线索二叉树
45?. 线索
n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。
lchild ltag data rtag rchild
0/1 0/1
lchild 有左子树，则指向左子树，标志ltag == 0;
没有左子树，可作为前驱线索，标志ltag == 1。 rchild 有右子树，则指向右子树，标志rtag == 0;
没有右子树，可作为后继线索，标志rtag == 1。 46?. 线索化二叉树
利用空指针作为线索指向前驱或后继。左边空指针可以作为前驱线索，右边空指针可以作
为后继线索，可以全线索化或部分线索化。
表 错误～文档中没有指定样式的文字。6.7 线索化二叉树的类型
前驱、后继线索 前驱线索 后继线索 中序线索化 中序全线索 中序前驱线索 中序后继线索 前序线索化 前序全线索 前序前驱线索 前序后继线索 后序线索化 后序全线索 后序前驱线索 后序后继线索
47?. 画出线索二叉树
思路:先写出遍历序列，再画线索。
步骤: 标出必要的空指针(前驱,左指针;后继,右指针，要点:“不要多标，也不要少标”)。
写出对应的遍历序列(前序，中序或后序)。
对照遍历结果画线索。
A A 例:画出图中二叉树的后序后继线索。
步骤:先标出所有空的右指针(DGCH);写出后序B C B C
遍历结果:DGEBHFCA;标出后继线索:D,G, G,E,
D E F D E F ,A, H,F。如图。 C
G G H H
48?. 遍历线索二叉树
反复利用孩子和线索进行遍历，可以避免递归。
树和森林
49?. 树的存储结构
双亲表示法，孩子表示法，孩子兄弟表示法。
特点:双亲表示法容易求得双亲，但不容易求得孩子;孩子表示法容易求得孩子，但求双
亲麻烦;两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，
也可以增加指向双亲的指针来解决。
50?. 树与二叉树的转换
表 错误～文档中没有指定样式的文字。6.8 树和二叉树的对应关系
树 对应的二叉树
根 根
第一个孩子 左孩子
下一个兄弟 右孩子
特点:由树转化成的二叉树，根结点没有右孩子
例:树转换成二叉树。
A
A B
B G I C G
C D F H J K D H I
E E F J
K
51?. 森林与二叉树的转换
森林中第1棵树的根作为对应的二叉树的根;其他的树看作第1棵树的兄弟;森林中的树转换成对应的二叉树。则森林转换成对应的二叉树。
例:将森林转换成对应的二叉树。参见课本P138。
52?. 树的遍历
树的结构:?根，?根的子树。
先根遍历:??。例:ABCDEFGHIJK。
后根遍历:??。例:CEDFBHGJKIA。
53?. 遍历森林
森林的结构:?第一棵树的根，?第一棵树的根的子树森林，? 其余树(除第一棵外)组成的森林。
先序遍历:???。例:ABCDEFGHIJ。
中序遍历:???。例:BDCEAGFIJH。
注:先序遍历森林，相当于依次先根遍历每一棵树;中根遍历森林相当于后根遍历每一棵树。
? ? ? A A F H
? B G I B C E G I J
C D F H J K D ? E
树的结构划森林的结构划分 分 54?. 遍历树、森林与遍历二叉树的关系
表 错误～文档中没有指定样式的文字。6.9 遍历树、森林和二叉树的关系
树 森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历
赫夫曼树及其应用
55?. 最优二叉树(赫夫曼树，哈夫曼树)
树的带权路径长度:所有叶子结点的带权路径长度之和。
n WPL,wl,kkk,1
路径长度l按分支数目计算。 k
带权路径长度最小的二叉树称为最优二叉树，或赫夫曼树(哈夫曼树)。 56?. 构造赫夫曼树
算法:参见课本P145。 12简单说，“每次取两个最小的树组成二叉树”。
57?. 赫夫曼编码(前缀码)
向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。
例:字符及其权值如下:A(6), B(7), C(1), D(5), E(2), F(8)，构造哈夫曼树和哈夫曼编码，计算带权路径长度。
ABCDE2 F8 ABDF8 3
6 7 1 5 6 7 5 CE2 1 ABF8 8 F8 8 13
6 7 D D AB
5 5 6 7 CE2 CE2 1 1 13 16 ABF8 ABF8 6 7 D 6 7 D 5 CE2 5 CE2 1 1 哈夫曼编码: 0 1 A:00
B:01 1 0 1 0 C:1110
A B F D:110 0 1 E:1111
D F:10 0 1 哈夫曼树 WPL = (6+7+8)*2+5*3+(1+2)*4 = 69 C E 或采用课本上的算法计算，如下。
表 错误～文档中没有指定样式的文字。6.10 赫夫曼算法
weighparelchirchi weighparelchirchi
t nt ld ld t nt ld ld 1 A 6 0 0 0 1 A 6 9 0 0 2 B 7 0 0 0 2 B 7 9 0 0 3 C 1 0 0 0 3 C 1 7 0 0 4 D 5 0 0 0 4 D 5 8 0 0 5 E 2 0 0 0 5 E 2 7 0 0 6 F 8 0 0 0 6 F 8 10 0 0 7 0 0 0 0 7 3 8 3 5
12 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
8 0 0 0 0 8 8 10 4 7 9 0 0 0 0 9 13 11 1 2 1 0 0 0 0 1 16 11 6 8 0 0
1 0 0 0 0 1 29 0 9 10 1 1
结果同上。
说明:同样的一组权值可能构造出不同的哈夫曼树，结果不一定唯一，但带权路径长度都是最小的。
技巧:要使前一种方法构造出的赫夫曼树和课本上算法产生的一样，只要把每次合并产生的二叉树放在树的集合的末尾，并且总是用两个最小树的前者作为左子树后者作为右子树。
图
基础知识和算法
图的有关概念
图，顶点，弧，弧头，弧尾;有向图(顶点集+弧集)，0?e?n(n-1)，无向图(顶点集+边集)，0?e?n(n-1)/2;稀疏图(e=0; w=NextAdjVex(G,v,w) )
if ( ! visited[w] ) DFS ( G, w ); // 分别从每个未访问的邻接点开始DFS }
其中的FirstAdjVex(G,v)表示图G中顶点v的第一个邻接点，NextAdjVex(G,v,w)表示图G中顶点v的邻接点w之后v的下一个邻接点。
深度优先搜索算法有广泛的应用，以上算法是这些应用的基础。
广度优先搜索
遍历方法
从图中某顶点出发，访问此顶点之后依次访问其各个未被访问的邻接点，然后从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问，直至所有已被访问的顶点的邻接点都被访问。若图中尚有顶点未被访问，则另选图中未被访问的顶点作为起始点，重复以上过程，直到图中所有顶点都被访问为止。
广度优先搜索从某顶点出发，要依次访问路径长度为1，2，„ 的顶点。 分析方法
方法:画一棵“广度优先搜索树”。
例:下图从A出发广度优先遍历的结果是:ABCED。
分析:画“广度优先搜索树”。与深度优先搜索树类似，A为根，其邻接点为其孩子，访问一个顶点，则扩展出其孩子。不过广度优先搜索的访问次序是对该树按层遍历的结果。
A A
B C B E
E B D
B A D C D
算法
利用队列(类似按层遍历二叉树)。
BFSTraverse ( Graph G ) void
{
visited [0 .. G.vexnum-1] = false; // 初始化访问标志为未访问(false)
InitQueue ( Q );
for ( v=0; v=0; w=NextAdjVex(G,u,w) )
if ( ! visited[w] ) {
visit ( w ); visited [w] = true;
EnQueue ( Q, w );
}
}
}
}
时间复杂度分析
观察搜索树可以看出，无论是深度优先搜索还是广度优先搜索，其搜索过程就是对每个顶点求所有邻接点的过程。当用邻接表存储图时，其时间复杂度为O(n+e);当采用邻接矩阵2作为存储结构时，时间复杂度是O(n) (因为求一个顶点的所有邻接点就是搜索邻接矩阵的2一行中的n个数，而顶点的个数为n，总共就是n)。
最小生成树
最小生成树及MST性质
最小生成树。MST性质。
注意:同一个连通网的最小生成树可能是不唯一的，但其代价都是最小(唯一的)。 克鲁斯卡尔算法 18一句话，“不构成环的情况下，每次选取最小边”。
18 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
A A A 2 2 2 5 5 5 3 3 3
6 6 6 B E D B E D B E D 3 3 3 3 3 3 1 1 1 7 7 7 (a) (b) (c) C C C
A A A 2 2 2 5 5 5 3 3 3 6 6 6 B E D B E D B E D 3 3 3 3 3 3 1 1 1 7 7 7 (f) (d) (e) C C C
A (a) 无向网 2 5 3 (b)-(e) 克鲁斯卡尔算法计算最小生成树6 B E D 3 的过程 (f) 得到的最小生成树 3 1 7 (g) 另一个可能的最小生成树 (g) C
提示:在不要步骤、只要结果的情况下可采用，边较少时特别有效。 普里姆算法
记V是连通网的顶点集，U是求得生成树的顶点集，TE是求得生成树的边集。 普里姆算法:
(a) 开始时，U={v}，TE=Φ; 0
(b) 计算U到其余顶点V-U的最小代价，将该顶点纳入U，边纳入TE;
(c) 重复(b)直到U=V。
例:用普里姆算法计算下图的最小生成树。
最小U到V-U中各顶点的最小代A 2 4 U V-U 代价价1 B C D E F 边 3 B E 3 F {A} {B,C,D,E,AB/2 ? ? AE/4 AF/1 AF/1
5 F} 1 4 2 {A,F} {B,C,D,E} AB/2 FC/5 FD/4 FE/3 AB/2 3 C D {A,F,B} {C,D,E} BC/1 FD/4 FE/3 BC/1
{A,F,B,C} {D,E} CD/3 FE/3 CD/3 {A,F,B,C,D{E} DE/2 DE/2
两种算法的比较 }
表 错误～文档中没有指定样式的文字。7.11 普里姆算法和克鲁斯卡尔算法的比较 {A,F,B,C,D,{}
E} 算法 普里姆算法 克鲁斯卡尔算法 2 时间复杂O(n) O(e loge)
度
特点 只与顶点个数n有关 只与边的数目e有关
与边的数目e无关 与顶点个数n无关
适用于稠密图 适用于稀疏图
拓扑排序
有向无环图(DAG)，AOV网;拓扑排序。 19拓扑排序，一句话“每次删除入度为0的顶点并输出之”。
例:以下DAG图拓扑排序的结果是:ABCDE。
B D A B D D D
C E E C E C E E 注意:拓扑排序的结果不一定是唯一的。如:ACBDE也是以上DAG图的拓扑有序序列。 关键路径
AOE网，关键路径
AOE 网(活动在边上)，边代表活动或任务，顶点代表事件。 a(i,*) a(*,j) 事件i发生后，其后继活动a(i,*)都可以开始;只有所有先导i j a(i,j) 活动a(*,j)都结束后，事件j才发生。
关键路径算法
问题:a) 整个工程完工需要多长时间, b) 哪些活动影响工程的进度,或求关键路径。 事件(顶点) i: 最早发生时间ve(i)，最晚发生时间vl(i); 活动(边) a(i,j): 最早开始时间e(i,j)，最晚开始时间l(i,j)。 于是，整个工程完工的时间就是终点的最早发生时间;关键路径就是路径长度最长的路径。
求关键路径的算法:
(a) 按拓扑有序排列顶点:对顶点拓扑排序;
(b) 计算ve(j):
ve(1),0,, 其中*为任意前驱事件; ,ve(j),max{ve(*)，a(*,j)},
(c) 计算vl(i):
vlnven(),(),, 其中*为任意后继事件; ,(),min{(*),(,*)}vlivlai,
(d) 计算e(i,j)和l(i,j):
eijvei(,),(),
(,),(),(,)lijvljaij
(e) 结论:工程总用时ve(n)，关键活动是e(i,j)=l(i,j)的活动a(i,j)。 说明: 01. 若只求工程的总用时只要进行步骤(a)-(b)即可求得。 02. 如何理解计算ve(j)和vl(i)的公式:
事件j在所有前驱活动都完成后发生，所以其最早a(*,j) a(i,*) j i 发生时间ve(j) = max{ve(*)+a(*,j)}，即取决于
最慢的前驱活动。另一方面，事件i发生后所有后
继活动都可以开始了，所以其最晚发生时间vl(i) = min{vl(*)-a(i,*)}，即不耽误最
慢的后继活动。
19 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
例:某工程的AOE网如下，求1) 整个工程完工需要多长时间，2) 关键路径。说明:图中的虚线仅表示事件的先后关系，不代表具体活动。
1 5 2 5 7 2 6 1 3 9 4 1 3 8 4
4 5 1 4 6
分析:按照拓扑有序排列顶点，然后“从前往后”计算事件的最早发生时间得到总时间，再“从后往前”计算事件的最晚发生时间，最后计算活动的最早和最晚开始时间得到关键活动和关键路径。
表 错误～文档中没有指定样式的文字。7.12 关键路径
事件 最早发生时间最晚发生时间活动 最早开始时间最晚开始时间
ve vl e l v1 0 0 a(1,2) 0 0 v2 6 6 a(1,3) 0 2 v3 4 6 a(1,4) 0 1 v4 5 6 a(2,5) 6 6 v5 7 7 a(3,5) 4 6 v6 7 7 a(4,6) 5 6 v7 12 13 a(5,6) 7 7 v8 11 11 a(5,7) 7 8 v9 15 15 a(5,8) 7 8
a(6,8) 7 7
a(7,9) 12 13
a(8,9) 11 11 所以，1) 工程完工需要时间15，2) 关键路径是1,2,5,6,8,9。 最短路径
迪杰斯特拉算法
求一个顶点到其他各顶点的最短路径。
算法:(a) 初始化:用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为?; (b) 从未求得最短路径的终点中选择路径长度最小的终点u:即求得v到u的最短路径; (c) 修改最短路径:计算u的邻接点的最短路径，若(v,„,u)+(u,w)<(v,„,w)，则以(v,„,u,w)代替。
(d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。
特点:总是按照从小到大的顺序求得最短路径。
例:用迪杰斯特拉算法求下图中A到其余顶点的最短路径。
终点 从A到各顶点的最短路径 8 6 8 6 A B B AB ACB ACB 6 2 4 3 2 C F C AC 3 2 6 ? 8 7 7 5 D ACD ACFD ACFD E D 1 ? 10 9 8 E ACFE ACBE ACFDE
6 5 F AF ACF
2 5 6 7 8 最短
AC ACF ACB ACFD ACFDE 路径 说明:求得v,u的最短路径后，只要计算u到其余顶点是否(比原来)有更短路径即可，这
样可以减少计算量。另外，注意合并路径。
弗洛伊德算法
求每对顶点之间的最短路径。 (0)(1)(n)(0)(k)(k)(k-1)依次计算A，A，„，A。A为邻接矩阵，计算A时，A(i,j)=min{A(i,j), (k-1)(k-1)A(i,k)+A(k,j)}。 (k)技巧:计算A的技巧。第k行、第k列、对角线的元素保持不变，对其余元素，考查A(i,j)20与A(i,k)+A(k,j) (“行+列”)，如果后者更小则替换A(i,j)，同时修改路径。
例:用弗洛伊德算法计算图中各顶点之间的最短路径。 (0)(1)2 0 3 ? A A2 0 3 ? 3 AB AC AB AC A B ? 0 4 ? ? 0 4 ? 2 BC BC 6 4 ? ? 0 5 ? ? 0 5 1 CD CD D C
6 1 ? 0 5 6 1 8 0 DA DB DA DB DAC (2)(3)(4) AAA0 3 2 0 3 2 0 3 2 ? 7 7 AB AC AB AC ACD AB AC ACD
? 0 4 9 15 0 4 9 ? 0 4 ? BC BCD BCDA BC BCD BC
11 6 0 5 ? ? 0 5 ? ? 0 5 CDA CDB CD CD CD
6 1 5 0 6 1 5 0 6 1 5 0 DA DB DBC DA DB DBC DA DB DBC 技巧:当不变行或不变列(即第k行、第k列)某元素为?时，其所在的列或行元素也不变。(1)例如:计算A时，A(2,1) = A(3,1) = ?，所以第2、3行都不变，而A(1,4) = ?，所以
第4列也不变，这样，只剩下A(4,2)和A(4,3)需要计算。
查找
基础知识和算法
20 第k列i“行”元素加上第k行j“列”元素。
有关概念
查找表，静态查找表(只进行“查找”)，动态查找表(可“查找”，“插入”，“删除”)。 关键字，平均查找长度 n ASL,pc,iii1,
p第i个关键字出现的概率，c比较的关键字的个数。 ii
静态查找表，顺序查找表，折半查找表，静态树表，次优查找树，索引顺序表。 动态查找表，二叉排序树，平衡二叉树(AVL树)，B-树，B+树，键树，哈希表。 顺序查找
思路
按顺序逐个比较，直到找到或找不到。
算法
程序，要灵活应用。
例如:在数组a的前n个元素中查找x
int Search ( int a[], int n, int x ) {
for ( i=n-1; i>=0; i-- )
if ( a[i]==x ) return i;
return -1; // -1表示找不到
}
编程技巧:所有执行路径都要有正确的返回值，不要忘记最后那个return语句。 应试技巧:题目要求不明确时，按照方便的方法做，用适当的注释说明。 分析
顺序查找特点:思路简单(逐个比较)，适用面广(对查找表没有特殊要求)。 平均查找长度
一般在等概率情况下，查找成功时，平均查找长度
1，2，...，nn，1 ASL,,n2
思路:假设对每个元素进行1次查找，共进行n次查找，计算出进行比较的关键字的个数，然后除以查找次数n，就求得平均查找长度。
例:10个元素的表等概率情况下查找成功时的平均查找长度
1，2，...，10 ASL,,5.510
判定树
判定树是一种描述查找中比较过程的直观形式，每个关键字所在层次就是其查找长度，有利于分析查找过程。顺序查找的判定树是一棵深度 aan1为n的单分支的树。课本上顺序查找从a开始，当n a an-12然也可以从a开始。 1
a a 1n时间复杂度
从平均查找长度看顺序查找的时间复杂度是O(n)。
折半查找
思路
待查找的表必须是有序的，先从中间开始比较，比较一次至少抛弃一半元素，逐渐缩小范
围，直到查找成功或失败。
算法
要熟练掌握该算法。设a[]升序有序，有以下算法:
int BinarySearch ( DataType a[], int n, DataType x )
{
low = 0; high = n-1;
while ( low <= high ) {
mid = ( low + high )/2; // 折半
if ( a[mid]==x )
return mid; // 找到
else if ( xhigh ) return -1; // 查找失败
mid = (low+high)/2; // 折半
if ( a[mid]==x )
return mid; // 找到
else if ( xa[m] e: m-1 f: j=m+1
分块的最佳长度是多少,规定条件:每块的大小相同，对块索引表和块内查找均采用顺序查找。
设表长为n，等分成b块，采用顺序查找确定块需要比较(b+1)/2次，块内顺序查找比较(n/b+1)/2次，总共C(b)=(b+1)/2+(n/b+1)/2，要使C(b)最小，有。 b,n二叉排序树
二叉排序树
二叉排序树或为空树;或者是这样一棵二叉树，若左子树不空，则左子树上所有结点均小于根结点，若右子树不空，则右子树上所有结点均大于根结点，其左、右子树也是二叉排序树。
技巧:如果中序遍历二叉排序树，得到的结果将从小到大有序。手工判别二叉排序树的方法之一。
例:判断对错:二叉排序树或是空树，或是这样一棵二叉树，若左子树不空，则左孩子小于根结点，若右子树不空，则右孩子大于根结点，左、右子树也是这样的二叉排序树。(×)请自己举反例。
查找
思路:?若二叉树为空，则找不到，?先与根比较，相等则找到，否则若小于根则在左子树上继续查找，否则在右子树上继续查找。
递归算法:
BstTree BstSearch ( BstTree bst, DataType x ) {
if ( bst==NULL )
return NULL;
else if ( bst->data==x )
return bt;
else if ( xdata )
return BstSearch ( bst->lchild, x);
else
return BstSearch ( bst->rchild, x); }
非递归算法:
BstTree BstSearch ( BstTree bst, DataType x ) {
p = bst;
while ( p ) {
if ( p->data==x )
return p;
else if ( xdata )
p = p->lchild;
else
p = p->rchild;
}
return NULL; // not found
}
插入
思路:先查找，若找不到则插入结点作为最后访问的叶子结点的孩子。 新插入的结点总是叶子。
建立
经过一系列插入操作可以建立二叉排序树。
给定关键字序列，建立二叉排序树。方法:?开始二叉树为空，?对每一个关键字，先进
行查找，如果已存在，则不作任何处理，否则插入。 22一句话，“从空树开始，每次插入一个关键字”。
例:给定关键字序列{53，45，12，24，90，45，80}，建立二叉排序树。
53 53 53 53 53 53 45 45 45 45 90 45 90
12 12 12 12 80
24 24 24
删除
叶子
直接删除即可。
53 53
删除24 45 90 45 90
12 50 12 50
24 24
左子树或右子树为空
“移花接木”:将左子树或右子树接到双亲上。
53 53
删除12 45 90 45 90
12 50 12 50 24 24
左右子树都不空
“偷梁换柱”:借左子树上最大的结点替换被删除的结点，然后删除左子树最大结点。(或
者借用右子树上最小结点然后删除之亦可。)
53 53 53
删除45 45 90 24 90 24 90
12 50 12 50 12 50
24 24 24
分析
判定树和二叉排序树相同。结点的层次等于查找时比较关键字的个数。
22 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
53
等概率情况下查找成功时 45 90 n11，2，2，3，3，412 50 ASL,h,,2.5,in6,i124
若按照关键字有序的顺序插入结点建立二叉排序树，将得到一棵单支树，对其进行查找也退化为顺序查找，平均查找长度为(1+n)/2。一般地，如果在任一关键字k之后插入二叉排序树的关键字都大于或都小于k，则该二叉排序树是单分支的，深度是n，查找效率和顺序查找相同。
平衡二叉树
平衡因子和平衡二叉树(AVL树)
平衡因子:左子树深度 – 右子树深度。
平衡二叉树中各个结点的平衡因子只能是0，1，-1。
构造平衡二叉排序树
思路:按照建立二叉排序树的方法逐个插入结点，失去平衡时作调整。 23失去平衡时的调整方法:
1) 确定三个代表性结点。(A是失去平衡的最小子树的根;B是A的孩子;C是B的孩子，
也是新插入结点的子树)。关键是找到失去平衡的最小子树。
2) 根据三个代表性结点的相对位置(C和A的相对位置)判断是哪种类型(LL, LR, RL,
RR)。
3) 平衡化。“先摆好三个代表性结点(居中者为根)，再接好其余子树(根据大小)”。
+2 +2 -2 -2
A A A A
B B B B 1 1 4 4
C C C C 1 2 4 3
1 2 2 3 3 4 2 3
LL LR RR RL
B B C C
C A B A A C A B
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
例:给定关键字的序列{13，24，37，90，53，40}，建立平衡二叉排序树。 注意:失去平衡时先确定失去平衡的最小子树，这是关键，然后判断类型(LL，LR，RL，RR)，再平衡化处理。
-2
13 13 RR 13 24 24 24 24 13 37 13 37 37 90
23 这里没有使用课本上“旋转”的概念，这只是做题的方法，并不是正规的算法描述。
-2 -2
24 24 24 37 -2 RL RL 13 37 13 53 13 53 24 53
90 37 90 37 90 13 40 90
53 40 分析
查找 (同二叉排序树)
平均查找长度ASL
结论:平均查找性能O(log n)。
为求得n个结点的平衡二叉树的最大高度，考虑高度为h的平衡二叉树的最少结点数。
0, h,0 ,, N, 1, h,1,h, N，N，1, h,2k-1k-2,
部分结果如下，F表示斐波纳契数列第h项。 h
表 错误～文档中没有指定样式的文字。9.13 平衡二叉树的高度和结点个数
h N F h N F hhhh
0 0 0 6 20 8
1 1 1 7 33 13
2 2 1 8 54 21
3 4 2 9 88 34
4 7 3 10 143 55
5 12 5 11 232 89 24观察可以得出N = F – 1, h?0。解得 hh+2
h,log(5(n，1)),2,1.44 log (n，1)-0.328,
其中。 ,,(5，1)/2
时间复杂度
一次查找经过根到某结点的路径，所以查找的时间复杂度是O(log n)。 +B-树和B树
B-树
一棵m阶B-树，或为空树，或满足:
(1) 每个结点至多有m棵子树;
(2) 若根结点不是叶子，则至少有两棵子树;
(3) 除根之外的所有非终端结点至少有棵子树; m/2，，
(4) 所有非终端结点包含n个关键字和n+1棵子树:(n, A, K, A, ..., K, A)，其中关011nn键字满足Ahigh; j-- )
a[j+1] = a[j];
a [high+1] = x; // 完成插入
}
}
分析 2时间复杂度O(n)。比直接插入排序减少了比较次数。折半插入排序是稳定的排序算法。
希尔排序(缩小增量排序)
思路
先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进
行直接插入排序。
步骤: 01. 分成子序列(按照增量dk); 02. 对子序列排序(直接插入排序); 03. 缩小增量，重复以上步骤，直到增量dk=1。
增量序列中最后一个增量一定是1，如:... 9, 5, 3, 2, 1和... 13, 4, 1。如没有明确 说明增量序列可以选择... 3, 2, 1或... 5, 3, 2, 1。
例:希尔排序(52，49，80，36，14，58，61)。
52 49 80 36 14 58 61
dk=3
52 36 14 58 49 80 61
dk=2
52 36 14 49 58 80 61
dk=1
52 14 36 49 58 61 80 3/2 注意:希尔排序是不稳定的。时间复杂度大约为O(n)。 程序
void ShellSort ( T a[], int n )
{
dk = n/2;
while ( dk>=1 ) {
// 一趟希尔排序，对dk个序列分别进行插入排序
for ( i=dk; i=0 and x= pivot ) j--;
a[i] = a[j];
while ( i=high ) return;
else {
mid = (low+high)/2;
MergeSort ( a, low, mid );
MergeSort ( a, mid+1, high ); Merge ( a, low, mid, high );
}
}
自底向上的归并排序:
void MergeSort ( T a[], int n ) {
t = 1;
while ( t
本文档为【数据结构C语言版复习攻略】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483