南开19秋《数据结构》课程期末复习资料

南开19秋《数据结构》课程期末复习资料满分答案

《数据结构》课程期末复习资料
第一章：绪论
一、基础知识
概念和术语(黑体字部分)。
另外，注意：
1、数据元素是数据的基本单位。
2、数据项是数据不可分割的最小单位。
3、数据结构及其形式定义。
四种基本结构：①集合②线性结构③树形结构④图（网）状结构
4、数据结构的
逻辑结构（抽象的，与实现无关）
物理结构（存储结构）  顺序映像（顺序存储结构）位置“相邻”
        非顺序映像（链式存储结构）指针表示关系
5、数据类型
  抽象数据类型（ADT）
  ADT=（数据对象，数据关系，基本操作）
  ADT细分为原子类型，固定聚合，可变聚合类型。
6、算法的概念
7、算法的五个特征
  ①有穷性 ②确定性 ③可行性 ④输入（0个或多个） ⑤输出（1个或多个）
8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量
其中正确性的四个层次（通常要求达到C层）。
9、算法的时间复杂度
  常见有： O(1)，O(n)，O(n2)，O(log2n) ，O(n log2n)，O(2n)
  语句频度，用归纳法计算。
10、算法的空间复杂度
二、算法
起泡排序。
另一种形式
void BubbleSort ( DataType a[], int n )
{
for ( i=0; i<n-1; i++ )
for ( j=0; j<n-i-1; j++ )
if ( a[j]>a[j+1] )
        a[j]<—>a[j+1];
}
或
void BubbleSort ( DataType a[], int n )
{
for ( i=1; i<n; i++ )
for ( j=0; j<n-i; j++ )
if( a[j]>a[j+1] )
        a[j]<—>a[j+1];
}
或
void BubbleSort ( DataType a[], int n )
{
for ( i=0; i<n-1; i++ ) {
    change = fasle;
for ( j=0; j<n-i-1; j++ )
if ( a[j]>a[j+1] ) {
        a[j]<—>a[j+1];
        change = true;
      }
if ( !change ) break;
  }
}

说明：
a) 考试中要求写算法时，可用类C，也可用C程序。
b) 尽量书写算法说明，言简意赅。
c) 技巧：用“边界值验证法”检查下标越界错误。
  如上第一个： 第二个循环条件若写作j<n-i，则当i=0时 a[j+1]会越界。
d) 时间复杂度为O(n2)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。
第二章、线性表
一、基础知识和算法
1、线性表及其特点
线性表是n个数据元素的有限序列。
线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。
2、顺序表—线性表的顺序存储结构
（1）特点：a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。
（2）类型定义
简而言之，“数组+长度” 。

constint MAXSIZE = 线性表最大长度;
typedefstruct{
DataType elem[MAXSIZE];
int length;
} SqList;

注：a) SqList为类型名，可换用其他写法。
    b) DataType是数据元素的类型，根据需要确定。
    c) MAXSIZE根据需要确定。如
  constint MAXSIZE=64;
    d) 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以
  e) 课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.length==L.listsize时，用realloc (L.elem, L.listsize+增量) 重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。
（3）基本形态
a) 顺序表空
条件  L.length==0
不允许删除操作
b) 顺序表满
条件  L.length==MAXSIZE
不允许插入操作
c) 不空也不满
可以插入，删除
（4）基本算法——遍历
d) 顺序访问所有元素for ( i=0; i<L.length; i++ )    visit ( L.elem[i] );                  5 查找元素x
for ( i=0; i<L.length; i++ )
if ( L.elem[i]==x )  break;
if ( i<L.length )
  找到;
else
  未找到;
2. 插入算法 ListInsert(&L,i,x)
a) 前提：表不满
b) 合理的插入范围：1≤i≤L.length+1
注：位序i在C/C++中对应于下标i-1。
c) 步骤
    第i至最后所有元素后移一个元素
    在第i个位置插入元素x
    表长增1
d) 算法
bool  ListInsert ( SqList& L, int i, DataType x )
{
if ( L.length==MAXSIZE || i<1 || i>L.length+1 )  returnfalse; // 失败
  // 元素后移
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++;
returntrue;  // 插入成功
}
3. 删除算法 ListDelete(&L,i,&x)
a) 前提：表非空
b) 合理的删除范围：1≤i≤L.length
c) 步骤
取出第i个元素
第i个元素之后的元素向前移动一个位置
表长减1
d) 算法
bool ListDelete ( SqList& L, int i, DataType& x )
{
if ( L.length==0 || i<1 || i>L.length )  returnfalse; // 失败
  x = L.elem[i-1];
for ( j=i; j<L.length; j++ )
        L.elem[j-1] = L.elem[j];
  L.length--;
returntrue;  // 删除成功
}

4. 算法分析
表 2.1 顺序表插入和删除算法的分析
插入 删除
基本操作
平均移动次数 移动元素

移动元素


时间复杂度 O(n) O(n)
尾端操作 插入第n+1个元素，不移动 删除第n个元素，不移动
插入、删除需移动大量元素O(n)；但在尾端插入、删除效率高O(1)。
5. 其他算法
a) InitList (&L), ClearList (&L)
        L.length = 0;
b) ListEmpty (L)
return L.length == 0;
c) ListLength (L)
return L.length;
d) GetElem (L, i, &e)
        e = L.elem[i-1];
单链表——线性表的链式存储结构之一
6. 概念
线性链表，单链表，结点；数据域，指针域；头指针，头结点。
7. 特点
用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）。
8. 类型定义
简而言之，“数据 + 指针” 。
typedefstruct LNode {
        DataType data;
struct LNode *next;
} LNode, *LinkList;
9. 基本形态
带头结点的单链表的基本形态有：
a) 单链表空
条件： L->next == 0
b) 单链表不空
条件：L->next != 0

10. 基本算法（遍历）
a) 顺序访问所有元素
借助指针，“顺藤摸瓜”(沿着链表访问结点)。
p = L->next;   // 注意起始位置的考虑
while ( p!=NULL ) {   // 判表尾，另外 (p!=0)或(p)均可
  visit( p->data );   // 访问:可以换成各种操作
  p = p->next;   // 指针沿着链表向后移动
}

例：打印单链表中的数据。
void PrintLinkList ( LinkList L )
{
  p = L->next;
while ( p!=NULL ) {
    print ( p->data );  // 访问：打印数据域
    p = p->next;
  }
}
b) 查找元素x
// 在单链表L中查找元素x
// 若找到，返回指向该结点的指针；否则返回空指针
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;
elsereturn 0;

或者
p = L->next;
while ( p && p->data!=x )  p = p->next;
return  p;  // 为什么
c) 查找第i个元素
LinkList Get ( LinkList L, int i )
{
  p = L->next;  j = 1;
while ( p && j<i ) {
    p = p->next;  j++;
  }
if ( p && j==i ) return p;
elsereturn 0;
}
d) 查找第i-1个元素
p = L;  j = 0;
while ( p && j<i-1 ) {
  p = p->next;  j++;
}
if ( p && j==i-1 ) return p;
elsereturn 0;
11. 插入算法 ListInsert(&L,i,x)
技巧：画图辅助分析。
思路：
  先查找第i-1个元素
  若找到，在其后插入新结点

bool  ListInsert ( LinkList &L, int i, DataType x )
{
  // 查找第i-1个元素p
  p = L;  j = 0;
while ( p && j<i-1 ) {
    p = p->next;  j++;
  }
  // 若找到，在p后插入x
if ( p && j==i-1 ) {
    s = (LinkList) malloc(sizeof(LNode));
    s->data = x;
    s->next = p->next;   // ①
    p->next = s;   // ②
returntrue;  // 插入成功
  }
else
returnfalse;  // 插入失败
}

注意：
  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) 完成插入的步骤：①②。技巧：先修改新结点的指针域。

12. 删除算法 ListDelete(&L,i,&x)
思路：
  先查找第i-1个元素
  若找到且其后存在第i个元素，则用x返回数据，并删除之

bool ListDelete ( LinkList &L, int i, int&x )
{
  // 查找第i-1个元素p
  p = L;  j = 0;
while ( p && j<i-1 ) {
    p = p->next;  j++;
  }
  //若存在第i个元素，则用x返回数据，并删除之
if ( p && j==i-1 && p->next ) { // 可以删除
    s = p->next;   // ①
    p->next = s->next;   // ②
    x = s->data;
    free (s);
returntrue;
  }
else
returnfalse;
}

注意：
  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. 建立链表的两种方法
思路：
   建立空表（头结点）；
   依次插入数据结点（每次插入表尾得(a1,a2,…,an)，每次插入表头得(an,…,a2,a1)）。
a) 顺序建表
void CreateLinkList ( LinkList &L, int n)
{
  // 建立空表
  L = (LinkList) malloc(sizeof(LNode));
  L->next = NULL;   // 空表
  p = L;   // 用p指向表尾
  // 插入元素
for ( i=0; i<n; i++ ) {
    scanf ( x );
    s = (LinkList) malloc(sizeof(LNode));
    s->data = x;
    // 插入表尾
    s->next = p->next;
    p->next = s;
    p = s;   // 新的表尾
  }
}
b) 逆序建表
void CreateLinkList ( LinkList &L, int n)
{
  // 建立空表
  L = (LinkList) malloc(sizeof(LNode));
  L->next = NULL;  // 空表
  // 插入元素
for ( i=0; i<n; i++ ) {
    scanf ( x );
    s = (LinkList) malloc(sizeof(LNode));
    s->data = x;
    // 插入表头
    s->next = L->next;
    L->next = s;
  }
}
循环链表
14. 特点
最后一个结点的指针指向头结点。
15. 类型定义
同单链表。
16. 基本形态
空表：L->next == L。
非空表。

17. 与单链表的联系
判断表尾的方法不同：单链表用p==NULL；循环链表用p==L。
其余操作相同。
双向循环链表
18. 特点
一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链表。
19. 类型定义
typedefstruct DuLNode {
    DataType data;
struct DuLNode *prior, *next;  // 两个指针
} DuLNode, *DuLinkList;
20. 基本形态
空表：用后向指针判断L->next == L，或者用前向指针判断L->prior == L。
非空表。

21. 与单链表和循环链表的联系
最大不同：前驱容易求得，可以向前遍历。
判断表尾的方法与循环链表相同：p==L。
插入和删除时需要修改两个方向的指针。
22. 插入和删除
需要修改两个方向的指针。例如：(见下表)
表 2.2 双向循环链表的插入和删除
p之后插入s p之前插入s 删除p之后继s 删除p
s->next = p->next;
p->next = s;
s->prior = p;
s->next->prior = s; s->prior = p->prior;
p->prior = s;
s->next = p;
s->prior->next = s; s = p->next;
p->next = s->next;
p->next->prior = p; p->prior->next = p->next;
p->next->prior = p->prior;
顺序表与单链表的比较
表 2.3 顺序表和单链表的比较
顺序表 单链表
以地址相邻表示关系 用指针表示关系
随机访问，取元素O(1) 顺序访问，取元素O(n)
插入、删除需要移动元素O(n) 插入、删除不用移动元素O(n)(用于查找位置)
总结：需要反复插入、删除，宜采用链表；反复提取，很少插入、删除，宜采用顺序表。

第三章、栈和队列
栈
栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。
顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。
链栈
存储结构
用不带头结点的单链表实现。
类型定义
同单链表。
基本形态
a) 栈空
条件: S == NULL
b) 栈非空
c) 栈满（一般不出现）
基本算法
d) 入栈 Push (&s, x)
bool Push ( LinkList &s, DataType x )
{
  // 新建结点
  p = (LinkList) malloc (sizeof(LNode));
if ( !p )  returnfalse; // 失败
  p->data = x;
  // 插入栈顶
  p->next = s;
  s = p;
returntrue;
}
e) 出栈 Pop (&s, &x)
前提：栈非空。
bool Pop ( LinkList &s, DataType &x )
{
if ( s==NULL )  returnfalse;  // 栈空
  // 删除栈顶元素
  p = s;
  s = s->next;
  x = p->data;
  free ( p );
returntrue;
}
f) 栈顶元素
前提：栈非空。
bool Top ( LinkList &s, DataType &x )
{
if ( s==NULL )  returnfalse;  // 栈空
  x = s->data;
returntrue;
}
顺序栈
存储结构
类似于顺序表，插入和删除操作固定于表尾。
类型定义
简单说，“数组 + 长度” 。
constint MAXSIZE = 栈的最大容量；
typedefstruct {
  DataType elem[MAXSIZE];
int top;
} SqStack;
基本形态
g) 栈空
条件  s.top == 0;
h) 栈满
条件  s.top == MAXSIZE
i) 栈不空、不满

基本算法
j) 入栈  Push (&s, x)
前提：栈不满
bool Push ( SqStack& s, DataType x )
{
if ( s.top == MAXSIZE )  returnfalse;  // 栈满
  s.elem[top] = x;   // 或者s.elem[top++] = x;
  top++;           //   代替这两行
returntrue;
}
k) 出栈  Pop (&s, &x)
前提：栈非空
bool Pop ( SqStack &s, DataType &x )
{
if ( s.top==0 )  returnfalse;
  top--;  // 可用x=s.elem[--top];
  x = s.elem[top];   //   代替这两行
returntrue;
}
l) 栈顶元素
前提：栈非空
s.elem[top-1] 即是。
队列
队列，队头，队尾，空队列，先进先出(FIFO)。
链队列：队列的链式存储结构。
循环队列：队列的顺序存储结构之一。
链队列
存储结构
简而言之，“单链表 + 尾指针” 。
类型定义

typedefstruct {
    LinkList front;
    LinkList rear;
} LinkQueue;
基本形态
队列空：Q.front==Q.rear。
非空队列。
基本算法
m) 入队列
插入队尾，注意保持Q.rear指向队尾。
n) 出队列
删除队头元素，
特别注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。
循环队列
存储结构
简单说，“数组 + 头、尾位置” 。
类型定义
constint MAXSIZE = 队列最大容量;
typedefstruct {
    DataType elem[MAXSIZE];
int front, rear;   // 队头、队尾位置
} SqQueue;
基本形态
通常少用一个元素区分队列空和队列满，也可以加一标志。约定front指向队头元素的位置，rear指向队尾的下一个位置，队列内容为 [front, rear)。
o) 队列空
条件：Q.front == Q.rear。
不能出队列。
p) 队列满
条件：(Q.rear+1)%MAXSIZE == Q.front （少用一个元素时）。
不能入队列。
q) 队列不空也不满

r) 加一标志区分队列空和队列满的情况
可以用满所有空间。队列空和队列满时都有Q.front==Q.rear，再用标志区分。
队列空：Q.front==Q.rear and Q.tag==0；队列满：Q.front==Q.rear and Q.tag==1。
基本算法
s) 入队列
前提：队列不满。
bool EnQueue ( SqQueue &Q, DataType x )
{
if ( (Q.rear+1)%MAXSIZE==Q.front )  returnfalse;  // 队列满
  // 入队列
  Q.elem [Q.rear] = x;
  Q.rear = (Q.rear+1)%MAXSIZE;
returntrue;
}
t) 出队列
前提：队列非空。
bool DeQueue ( SqQueue &Q, DataType &x )
{
if ( Q.front==Q.rear )  returnfalse;  // 队列空
  // 出队列
  x = Q.elem [Q.front];
  Q.front = (Q.front+1)%MAXSIZE;
returntrue;
}
u) 队列中元素个数
结论：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。
注：Q.rear-Q.front可能小于0，需要加上MAXSIZE。
int QueueLength ( SqQueue Q )
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
v) 用标志区分队列空和满
用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下：
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 )  returnfalse;
  Q.elem[ Q.rear ] = x;
  Q.rear = (Q.rear+1)%MAXSIZE;
if ( Q.tag==0 )  Q.tag = 1;   // 队列非空
returntrue;
}
bool DeQueue ( SqQueue &Q, DataType &x ) {
if ( Q.front==Q.rear and Q.tag==0 )  returnfalse;
  x = Q.elem[ Q.front ];
  Q.front = (Q.front+1)%MAXSIZE;
if ( Q.front==Q.rear )  Q.tag = 0;   // 队列空
returntrue;
}
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.1 简化的栈和队列结构
简化栈 简化队列
结构 “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
说明：只要栈(队列)的容量足够大，算法中可以省去检查栈(队列)满的情况。
栈和队列的应用
w) 表达式求值

x) 括号匹配
例：检查表达式中的括号是否正确匹配。如{ ( ) [ ] }正确，( [ ) ] }则错误。
分析：每个左括号都“期待”对应的右括号，匹配成功则可以消去。
思路：遇到左括号则入栈，遇到右括号则与栈顶括号相比较，如果匹配则消去，否则匹配失败。当然，如果栈中没有括号可以匹配，或者最后栈中还有未匹配的左括号，也都是匹配错误。
// 检查输入的表达式中括号是否匹配
bool MatchBrackets ()
{
constint 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]!=’(’ ) returnfalse;   // 栈空或右括号与栈顶左括号失配
    case ‘]’:
if ( top==0 or s [--top]!=’[’ ) returnfalse;
    case ‘}’:
if ( top==0 or s [--top]!=’{’ ) returnfalse;
    }
    ch = getchar();   // 取下一个字符
  }
if ( top==0 )  returntrue;   // 正好匹配
elsereturnfalse;   // 栈中尚有未匹配的左括号
}
y) 递归程序的非递归化
将递归程序转化为非递归程序时常使用栈来实现。
z) 作业排队
如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队列。
aa) 按层次遍历二叉树
void LevelOrder ( BinTree bt, VisitFunc visit )
{
constint 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.1 串的基本操作
Assign (s, t), Create (s, cs) Assign(s,t)将变量t赋值给s，Create(s,cs)根据字串创建变量s。
Equal (s, t), Length (s) 判断串相等，求串长度。如Length(“”)=0。
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.2 串的存储结构
定长顺序串 最大长度固定，超过最大长度则作截断处理
堆分配存储表示 串的长度几乎没有限制
块链存储表示 块内存储空间连续，块间不连续
树和二叉树
基础知识和算法
树及有关概念
树，根，子树；结点，结点的度，叶子（终端结点），分支结点（非终端结点），内部结点，树的度；孩子，双亲，兄弟，祖先，子孙，堂兄弟；层次（根所在层为第1层），深度，高度；有序树，无序树，二叉树是有序树；森林。
二叉树
二叉树（二叉树与度为2的树不同，二叉树的度可能是0，1，2）；左孩子，右孩子。
二叉树的五种基本形态。
二叉树的性质
bb) 二叉树的第i层 上至多有2i-1个结点。
cc) 深度为k的二叉树至多有2k-1个结点。
  满二叉树：深度为k，有2k-1个结点。
  完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。
dd) 叶子结点n0，度为2的结点为n2，则n0 = n2+1。
考虑结点个数：n = n0 + n1 + n2
考虑分支个数：n-1 = 2n2 + n1
可得n0 = n2+1
例：1) 二叉树有n个叶子，没有度为1的结点，共有个结点。 2) 完全二叉树的第3层有2个叶子，则共有个结点。
分析：1) 度为2的结点有n-1个，所以共2n-1个结点。 2) 注意考虑到符合条件的二叉树的深度可能是3或4，所以有5、10或11个结点。
ee) n个结点的完全二叉树深度为 。
ff) n个结点的完全二叉树，结点按层次编号
有：  i的双亲是 ，如果i = 1时为根（无双亲）；
      i的左孩子是2i，如果2i>n，则无左孩子；
      i的右孩子是2i + 1，如果2i + 1>n则无右孩子。
二叉树的存储结构
gg) 顺序存储结构
用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。
hh) 链式存储结构
二叉链表：
typedefstruct BTNode {
  DataType data;
struct BTNode *lchild, *rchild;
} BTNode, *BinTree;
三叉链表：
typedefstruct BTNode {
  DataType data;
struct BTNode *lchild, *rchild, *parent;
} BTNode, *BinTree;

例：用二叉链表存储n个结点的二叉树(n>0)，共有(_a_)个空指针域；采用三叉链表存储，共有(_b_)个空指针域。
二叉树的五种基本形态

①空树：bt==NULL  ②左右子树均空：bt->lchild==NULL and bt->rchild==NULL
③右子树为空：bt->rchild==NULL  ④左子树为空：bt->lchild==NULL
⑤左右子树均非空。
前两种常作为递归结束条件，后三者常需要递归。
遍历二叉树
ii) 常见有四种遍历方式
按层次遍历，先序遍历，中序遍历，后序遍历。
按层次遍历：“从上至下，从左至右”，利用队列。
先序遍历：DLR；中序遍历：LDR；后序遍历LRD。

例：写出a+b*(c-d)-e/f的前缀、中缀和后缀表达式。
画出二叉树，分别进行前序、中序、后序遍历即可得到。
前缀表达式：- + a * b - c d / e f
中缀表达式：a + b * c - d - e / f
后缀表达式：a b c d - * + e f / -

jj) 先序遍历算法
void Preorder ( BinTree bt )
{
if ( bt ) {
    visit ( bt->data );
    Preorder ( bt->lchild );
    Preorder ( bt->rchild );
  }
}
kk) 中序遍历算法
void Inorder ( BinTree bt )
{
if ( bt ) {
    Inorder ( bt->lchild );
    visit ( bt->data );
    Inorder ( bt->rchild );
  }
}
ll) 后序遍历
void Postorder ( BinTree bt )
{
if ( bt ) {
    Postorder ( bt->lchild );
    Postorder ( bt->rchild );
    visit ( bt->data );
  }
}
mm) 按层次遍历
思路：利用一个队列，首先将根（头指针）入队列，以后若队列不空则取队头元素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 )
{
constint 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;
    }
  }
}
nn) 非递归遍历二叉树
一般借助栈实现。设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。
(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;   // 必须的，使下一步继续退栈
      }
    }
  }
}
注：后序非递归遍历的过程中，栈中保留的是当前结点的所有祖先。这是和先序及中序遍历不同的。在某些和祖先有关的算法中，此算法很有价值。
oo) 三叉链表的遍历算法
下面以中序遍历为例。
// 中序遍历三叉链表存储的二叉树
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;
while ( p == f->rchild ) {   //   若p是右子树则一直上溯
        p = f;  f = f->parent;
      }
    }
  }
}

遍历二叉树的应用
pp) 写出遍历序列（前、中、后序）
qq) 根据遍历序列画出二叉树
(a) 已知前序和中序序列，唯一确定二叉树。
例：前序：ABDEGCFH，中序：DBGEAFHC，画出二叉树。
分析：前序序列的第一个是根，这是解题的突破口。
步骤：①前序序列的第一个是根 ②在中序序列中标出根，分成左右子树 ③在前序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的前序和中序序列重复以上步骤直至完成。
(b) 已知后序和中序序列，唯一确定二叉树。
例：后序：DGEBHFCA，中序：DBGEAFHC，画出二叉树。
分析：后序序列的最后一个是根，这是解题的突破口。
步骤：①后序序列的最后一个是根 ②在中序序列中标出根，分成左右子树 ③在后序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的后序和中序序列重复以上步骤直至完成。
(c) 已知前序和后序序列，不存在度为1的结点时能唯一确定二叉树。
例：前序：ABDEC，后序：DEBCA，画出二叉树。又前序AB，后序BA则不能唯一确定二叉树。
注：对于不存在度为1的结点的二叉树，首先确定根结点，然后总可以将其余结点序列划分成左右子树，以此类推即可确定二叉树。

说明：画出二叉树后可以进行遍历以便验证。
rr) 编写算法
思路：按五种形态(①--⑤)分析，适度简化。
例：求二叉树结点的个数。
分析：① 0; ② 1; ③ L+1; ④ 1+R; ⑤ 1+L+R。
简化：② 1+L=0+R=0 ③ 1+L+R=0 ④ 1+L=0+R ⑤ 1+L+R 可合并成⑤一种情况。
int NodeCount ( BinTree bt )
{
if ( bt==0 )  return 0;
elsereturn 1 + NodeCount(bt->lchild) + NodeCount(bt->rchild);
}

例：求二叉树叶子结点的个数。
分析：① 0; ② 1; ③ L; ④ R; ⑤ L+R。简化：③④⑤可合并成⑤。
int LeafCount ( BinTree bt )
{
if ( bt==0 )  return 0;
elseif ( bt->lchild==0 and bt->rchild==0 )  return 1;
elsereturn 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;
elsereturn 1 + max(Depth(bt->lchild), Depth(bt->rchild));
}
线索二叉树
ss) 线索
n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。
 
lchild 有左子树，则指向左子树，标志ltag == 0；
没有左子树，可作为前驱线索，标志ltag == 1。
rchild 有右子树，则指向右子树，标志rtag == 0；
没有右子树，可作为后继线索，标志rtag == 1。
tt) 线索化二叉树
利用空指针作为线索指向前驱或后继。左边空指针可以作为前驱线索，右边空指针可以作为后继线索，可以全线索化或部分线索化。
表 6.1 线索化二叉树的类型
前驱、后继线索 前驱线索 后继线索
中序线索化 中序全线索 中序前驱线索 中序后继线索
前序线索化 前序全线索 前序前驱线索 前序后继线索
后序线索化 后序全线索 后序前驱线索 后序后继线索

uu) 画出线索二叉树
思路：先写出遍历序列，再画线索。
步骤： 标出必要的空指针（前驱左指针；后继右指针，要点：“不要多标，也不要少标”）。
写出对应的遍历序列（前序，中序或后序）。
对照遍历结果画线索。
例：画出图中二叉树的后序后继线索。
步骤：先标出所有空的右指针(DGCH)；写出后序遍历结果：DGEBHFCA；标出后继线索：DG, GE, CA, HF。如图。

vv) 遍历线索二叉树
反复利用孩子和线索进行遍历，可以避免递归。
树和森林
ww) 树的存储结构
双亲表示法，孩子表示法，孩子兄弟表示法。
特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。
xx) 树与二叉树的转换
表 6.2 树和二叉树的对应关系
树 对应的二叉树
根 根
第一个孩子 左孩子
下一个兄弟 右孩子
特点：由树转化成的二叉树，根结点没有右孩子
例：树转换成二叉树。
 
yy) 森林与二叉树的转换
森林中第1棵树的根作为对应的二叉树的根；其他的树看作第1棵树的兄弟；森林中的树转换成对应的二叉树。则森林转换成对应的二叉树。
例：将森林转换成对应的二叉树。参见课本P138。
zz) 树的遍历
树的结构：①根，②根的子树。
先根遍历：①②。例：ABCDEFGHIJK。
后根遍历：②①。例：CEDFBHGJKIA。
aaa) 遍历森林
森林的结构：①第一棵树的根，②第一棵树的根的子树森林，③ 其余树(除第一棵外)组成的森林。
先序遍历：①②③。例：ABCDEFGHIJ。
中序遍历：②①③。例：BDCEAGFIJH。
注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。

bbb) 遍历树、森林与遍历二叉树的关系
表 6.3 遍历树、森林和二叉树的关系
树 森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历

赫夫曼树及其应用
ccc) 最优二叉树(赫夫曼树，哈夫曼树)
树的带权路径长度：所有叶子结点的带权路径长度之和。
 
路径长度lk按分支数目计算。
带权路径长度最小的二叉树称为最优二叉树，或赫夫曼树(哈夫曼树)。
ddd) 构造赫夫曼树
算法：
简单说，“每次取两个最小的树组成二叉树” 。
eee) 赫夫曼编码(前缀码)
向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。

例：字符及其权值如下：A(6), B(7), C(1), D(5), E(2), F(8)，构造哈夫曼树和哈夫曼编码，计算带权路径长度。




或采用课本上的算法计算，如下。
表 6.4 赫夫曼算法
  weight parent lchild rchild    weight parent lchild rchild
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
8  0 0 0 0  8  8 10 4 7
9  0 0 0 0  9  13 11 1 2
10  0 0 0 0  10  16 11 6 8
11  0 0 0 0  11  29 0 9 10
结果同上。
说明：同样的一组权值可能构造出不同的哈夫曼树，结果不一定唯一，但带权路径长度都是最小的。
技巧：要使前一种方法构造出的赫夫曼树和课本上算法产生的一样，只要把每次合并产生的二叉树放在树的集合的末尾，并且总是用两个最小树的前者作为左子树后者作为右子树。
图
基础知识和算法
图的有关概念
图，顶点，弧，弧头，弧尾；有向图（顶点集+弧集），0≤e≤n(n-1)，无向图（顶点集+边集），0≤e≤n(n-1)/2；稀疏图（e<nlogn），稠密图；完全图e=n(n-1)/2，有向完全图e=n(n-1)；网，有向网，无向网。子图，邻接点，顶点的度，入度，出度；路径，路径长度（经过边或弧的数目），简单路径，回路（环），简单回路（简单环）；连通图，连通分量，强连通分量。

例：有6个顶点组成的无向图构成连通图，最少需要(_a_)条边；当边的数目大于(_b_)时，该图必定连通。
分析：a. 5。最少有n-1条边就可以构成连通图。 b. 10。考虑将n个顶点分成两组，一组有n-1个顶点，另一组只有1个顶点。首先在第一组中添加边，直到n-1个顶点构成全连通子图，共(n-1)(n-2)/2条边，此后若再在图中任意添加一条边将必定连通两组顶点，从而构成连通图。
思考：对有向图有何结论。
图的存储结构
图的存储结构
常见图的存储结构有：邻接矩阵，邻接表，逆邻接表，十字链表，邻接多重表。
邻接多重表只适用于存储无向图，其他存储结构可以存储无向图和有向图。

例：画出图的邻接矩阵、邻接表、逆邻接表和十字链表。

邻接矩阵
简言之，“数组(顶点)+二维数组(弧)+个数” 。
constint MAX_VERTEX = 最大顶点个数;
typedefstruct Graph {  // 图
  VertexType  vexs[MAX_VERTEX]; // 顶点向量
  ArcType  arcs[MAX_VERTEX] [MAX_VERTEX];  // 邻接矩阵
int vexnum, arcnum; // 顶点和弧的个数
} Graph;

图：有边(弧)为1；否则为0。网：有边(弧)为权值；否则为∞。
存储空间个数为n2，与边的数目无关。
无向图的邻接矩阵是对称的。
 
邻接表
简言之，“数组(弧尾顶点)+链表(邻接点)+个数” 。
typedefstruct ArcNode {  // 弧结点
int adjvex; // 邻接点
struct ArcNode *nextarc; // 下一个邻接点
} ArcNode;

typedefstruct VexNode {  // 顶点结点
  VertexType  data; // 顶点信息
  ArcNode *firstarc; // 第一个邻接点
} VexNode;

constint MAX_VERTEX = 最大顶点个数;
typedefstruct Graph {  // 图
  VexNode  vexs[MAX_VERTEX]; // 顶点向量
int vexnum, arcnum; // 顶点和弧的个数
} Graph;

边(弧)多则需要存储空间多。
 
逆邻接表
简言之，“数组(弧头顶点)+链表(逆邻结点)+个数” 。
类型定义类似邻接表。
 
十字链表
简言之，“数组(顶点)+弧结点(含头和尾)+个数” 。边可以看作两条弧。
typedefstruct ArcNode {  // 弧结点
int vtail, vhead; // 弧尾和弧头顶点编号
struct ArcNode  *nexttail, *nexthead; // 指向同弧尾和同弧头的弧结点
} ArcNode;

typedefstruct VexNode {  // 顶点结点
  VertexType  data; // 顶点信息
  ArcNode  *firstin, *firstout; // 指向第一条入弧和第一条出弧
} VexNode;

constint MAX_VERTEX = 最大顶点个数;
typedefstruct Graph {  // 图
  VexNode  vexs[MAX_VERTEX]; // 顶点向量
int vexnum, arcnum; // 顶点和弧的个数
} Graph;

弧结点中包含两个指针分别指向同一弧头的下一个弧和同一个弧尾的下一个弧。顶点结点则指向第一个同弧头和弧尾的弧。十字链表相当于邻接表和逆邻接表的结合。
 
技巧：把弧结点按行排整齐，然后画链表。同弧尾的弧组成链表，同弧头的弧组成链表。
邻接多重表
简言之，“数组(顶点)+边结点” 。
typedefstruct EdgeNode {  // 边结点
int vexi, vexj; // 边的两个顶点
struct EdgeNode  *nexti, *nextj; // 两个顶点所依附的下一条边
} EdgeNode;

typedefstruct VexNode {  // 顶点结点
  VertexType  data; // 顶点信息
  EdgeNode  *firstedge; // 指向第一条边
} VexNode;

constint MAX_VERTEX = 最大顶点个数;
typedefstruct Graph {  // 图
  VexNode  vexs[MAX_VERTEX]; // 顶点向量
int vexnum, edgenum; // 顶点和边的个数
} Graph;

只适合存储无向图，不能存储有向图。
 
技巧：把边结点按列排整齐，然后画链表。相同顶点组成链表，这里没有起点和终点的区别。
图的遍历
深度优先搜索
遍历方法
从图中某个顶点出发，访问此顶点，然后依次从其未被访问的邻接点出发深度优先遍历图；若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问为止。
分析方法
方法：画一棵“深度优先搜索树”。

例：下图从A出发深度优先搜索的结果是：ABEDC。
分析：画“深度优先搜索树”。从A出发，访问A(画圈作标记)，A的邻接点有B和C(作为A的孩子)，B未访问，访问B(画圈)，B的邻接点有E(作B的孩子)，...，以此类推，画出搜索树。深度优先搜索的过程就是沿着该搜索树先根遍历的过程。
技巧：顶点的邻接点是无所谓次序的，所以同一个图的深度优先遍历序列可能不同，但在遍历时(除非邻接点的次序有明确规定)一般按照编号顺序安排邻接点的次序。
 
算法
课本上的算法稍加改动：
void DFSTraverse ( Graph G )
{
  visited [0 .. G.vexnum-1] = false;   // 初始化访问标志为未访问(false)
for ( v=0; v<G.vexnum; v++ )
if ( ! visited[v] )  DFS ( G, v );   // 从未被访问的顶点开始DFS
}

void DFS ( Graph G, int v )
{
  visit ( v );  visited [v] = true;   // 访问顶点v并作标记
for ( w=FirstAdjVex(G,v); w>=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为根，其邻接点为其孩子，访问一个顶点，则扩展出其孩子。不过广度优先搜索的访问次序是对该树按层遍历的结果。
 
算法
利用队列(类似按层遍历二叉树)。
void BFSTraverse ( Graph G )
{
  visited [0 .. G.vexnum-1] = false;   // 初始化访问标志为未访问(false)
  InitQueue ( Q );
for ( v=0; v<G.vexnum; v++ )
if ( ! visited[v] )  {
      // 从v出发广度优先搜索
      visit ( v );  visited [v] = true;
      EnQueue ( Q, v );
while ( ! QueueEmpty(Q) )  {
        DeQueue ( Q, u );
for ( w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w) )
if ( ! visited[w] )  {
            visit ( w );  visited [w] = true;
            EnQueue ( Q, w );
          }
      }
    }
}
时间复杂度分析
观察搜索树可以看出，无论是深度优先搜索还是广度优先搜索，其搜索过程就是对每个顶点求所有邻接点的过程。当用邻接表存储图时，其时间复杂度为O(n+e)；当采用邻接矩阵作为存储结构时，时间复杂度是O(n2) (因为求一个顶点的所有邻接点就是搜索邻接矩阵的一行中的n个数，而顶点的个数为n，总共就是n2)。
最小生成树
最小生成树及MST性质
最小生成树。MST性质。
注意：同一个连通网的最小生成树可能是不唯一的，但其代价都是最小(唯一的)。
克鲁斯卡尔算法
一句话，“不构成环的情况下，每次选取最小边”。



提示：在不要步骤、只要结果的情况下可采用，边较少时特别有效。
普里姆算法
记V是连通网的顶点集，U是求得生成树的顶点集，TE是求得生成树的边集。
普里姆算法：
(a) 开始时，U={v0}，TE=Φ；
(b) 计算U到其余顶点V-U的最小代价，将该顶点纳入U，边纳入TE；
(c) 重复(b)直到U=V。

例：用普里姆算法计算下图的最小生成树。

两种算法的比较
表 7.1 普里姆算法和克鲁斯卡尔算法的比较
算法 普里姆算法 克鲁斯卡尔算法
时间复杂度 O(n2) O(e loge)
特点 只与顶点个数n有关
与边的数目e无关
适用于稠密图 只与边的数目e有关
与顶点个数n无关
适用于稀疏图
拓扑排序
有向无环图(DAG)，AOV网；拓扑排序。
拓扑排序，一句话“每次删除入度为0的顶点并输出之” 。

例：以下DAG图拓扑排序的结果是：ABCDE。

注意：拓扑排序的结果不一定是唯一的。如：ACBDE也是以上DAG图的拓扑有序序列。
关键路径
AOE网，关键路径
AOE 网(活动在边上)，边代表活动或任务，顶点代表事件。
事件i发生后，其后继活动a(i,*)都可以开始；只有所有先导活动a(*,j)都结束后，事件j才发生。
关键路径算法
问题：a) 整个工程完工需要多长时间？ b) 哪些活动影响工程的进度？或求关键路径。
事件(顶点) i： 最早发生时间ve(i)，最晚发生时间vl(i)；
活动(边) a(i,j)： 最早开始时间e(i,j)，最晚开始时间l(i,j)。
于是，整个工程完工的时间就是终点的最早发生时间；关键路径就是路径长度最长的路径。

求关键路径的算法：
(a) 按拓扑有序排列顶点：对顶点拓扑排序；
(b) 计算ve(j)：
  其中*为任意前驱事件；
(c) 计算vl(i)：
  其中*为任意后继事件；
(d) 计算e(i,j)和l(i,j)：
 
(e) 结论：工程总用时ve(n)，关键活动是e(i,j)=l(i,j)的活动a(i,j)。
说明：
10. 若只求工程的总用时只要进行步骤(a)-(b)即可求得。
20. 如何理解计算ve(j)和vl(i)的公式：
事件j在所有前驱活动都完成后发生，所以其最早发生时间ve(j) = max{ve(*)+a(*,j)}，即取决于最慢的前驱活动。另一方面，事件i发生后所有后继活动都可以开始了，所以其最晚发生时间vl(i) = min{vl(*)-a(i,*)}，即不耽误最慢的后继活动。

例：某工程的AOE网如下，求1) 整个工程完工需要多长时间，2) 关键路径。说明：图中的虚线仅表示事件的先后关系，不代表具体活动。
 
分析：按照拓扑有序排列顶点，然后“从前往后”计算事件的最早发生时间得到总时间，再“从后往前”计算事件的最晚发生时间，最后计算活动的最早和最晚开始时间得到关键活动和关键路径。
表 7.2 关键路径
事件 最早发生时间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到其余顶点的最短路径。

说明：求得vu的最短路径后，只要计算u到其余顶点是否(比原来)有更短路径即可，这样可以减少计算量。另外，注意合并路径。
弗洛伊德算法
求每对顶点之间的最短路径。
依次计算A(0)，A(1)，…，A(n)。A(0)为邻接矩阵，计算A(k)时，A(k)(i,j)=min{A(k-1)(i,j), A(k-1)(i,k)+A(k-1)(k,j)}。
技巧：计算A(k)的技巧。第k行、第k列、对角线的元素保持不变，对其余元素，考查A(i,j)与A(i,k)+A(k,j) （“行+列” ），如果后者更小则替换A(i,j)，同时修改路径。

例：用弗洛伊德算法计算图中各顶点之间的最短路径。



技巧：当不变行或不变列(即第k行、第k列)某元素为∞时，其所在的列或行元素也不变。例如：计算A(1)时，A(2,1) = A(3,1) = ∞，所以第2、3行都不变，而A(1,4) = ∞，所以第4列也不变，这样，只剩下A(4,2)和A(4,3)需要计算。
查找
基础知识和算法
有关概念
查找表，静态查找表（只进行“查找”），动态查找表（可“查找”，“插入”，“删除”）。
关键字，平均查找长度
 
pi第i个关键字出现的概率，ci比较的关键字的个数。
静态查找表，顺序查找表，折半查找表，静态树表，次优查找树，索引顺序表。
动态查找表，二叉排序树，平衡二叉树（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次查找，共进行n次查找，计算出进行比较的关键字的个数，然后除以查找次数n，就求得平均查找长度。
例：10个元素的表等概率情况下查找成功时的平均查找长度
 
判定树
判定树是一种描述查找中比较过程的直观形式，每个关键字所在层次就是其查找长度，有利于分析查找过程。顺序查找的判定树是一棵深度为n的单分支的树。课本上顺序查找从an开始，当然也可以从a1开始。

时间复杂度
从平均查找长度看顺序查找的时间复杂度是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;  // 找到
elseif ( x<a[mid] )   // x位于低半区 [low..mid-1]
      high = mid – 1;
else // x位于高半区 [mid+1..high]
      low = mid + 1;
  }
return -1;  // -1表示未找到
}
或者有递归版本：
int BinarySearch ( DataType a[], int low, int high, DataType x )
{
if ( low>high )  return -1;    // 查找失败
  mid = (low+high)/2;   // 折半
if ( a[mid]==x )
return mid;  // 找到
elseif ( x<a[mid] )
return BinarySearch (a, low, mid-1, x);
else
return BinarySearch (a, mid+1, high, x);
}
另外，程序可有多种写法。
例：a[]递减有序，折半查找，请填空。
int bs ( T a[], int n, T x )
{
  i = n-1; j = 0;
while (____a____) {
    m = ____b____;
if (____c____)
return m;  // succeeded
elseif (____d____)
      i = ____e____;
else
      ____f____;
  }
return -1;  // not found
} 
分析
特点：速度很快，要求查找表是有序的，而且随机访问(以便计算折半的下标)。所以，链表不能进行折半查找(但可以采用二叉排序树等形式进行快速的查找)。
判定树
折半查找的判定树类似于完全二叉树，叶子结点所在层次之差最多为1，其深度为 。
查找过程就是走了一条从根到该结点的路径。
如：表长n=10的有序表折半查找的判定树如下。

平均查找长度
结论：等概率查找成功时的平均查找长度

分析方法：对等概率情况，假设查找n次，且每个查找1次，共比较关键字c次，则平均c/n次。
例：表长为n = 10，平均查找长度如下。

时间复杂度
结论：O(logn)，根据平均查找长度计算。

有时对需要反复查找的数据预先排序，再折半查找也是划算的。比如有1000个数据，顺序查找100次，平均比较约100×500=50000次；快排大约比较1.44nlogn = 1.44×1000×10 = 14400，100次折半查找比较不超过100×9×2=1800次(考虑到同一关键字的两次比较)，排序后折半查找合计比较不超过大约16200次。
索引顺序表
分块，块间有序 + 块内无序，对应索引表有序 + 顺序表（无序）。
索引顺序表的查找性能介于顺序查找与折半查找之间。

分块的最佳长度是多少？规定条件：每块的大小相同，对块索引表和块内查找均采用顺序查找。
设表长为n，等分成b块，采用顺序查找确定块需要比较(b+1)/2次，块内顺序查找比较(n/b+1)/2次，总共C(b)=(b+1)/2+(n/b+1)/2，要使C(b)最小，有 。
二叉排序树
二叉排序树
二叉排序树或为空树；或者是这样一棵二叉树，若左子树不空，则左子树上所有结点均小于根结点，若右子树不空，则右子树上所有结点均大于根结点，其左、右子树也是二叉排序树。
技巧：如果中序遍历二叉排序树，得到的结果将从小到大有序。手工判别二叉排序树的方法之一。

例：判断对错：二叉排序树或是空树，或是这样一棵二叉树，若左子树不空，则左孩子小于根结点，若右子树不空，则右孩子大于根结点，左、右子树也是这样的二叉排序树。（×）请自己举反例。
查找
思路：①若二叉树为空，则找不到，②先与根比较，相等则找到，否则若小于根则在左子树上继续查找，否则在右子树上继续查找。
递归算法：
BstTree BstSearch ( BstTree bst, DataType x )
{
if ( bst==NULL )
return NULL;
elseif ( bst->data==x )
return bt;
elseif ( x<bst->data )
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;
elseif ( x<p->data )
      p = p->lchild;
else
      p = p->rchild;
  }
return NULL;  // not found
}
插入
思路：先查找，若找不到则插入结点作为最后访问的叶子结点的孩子。
新插入的结点总是叶子。
建立
经过一系列插入操作可以建立二叉排序树。
给定关键字序列，建立二叉排序树。方法：①开始二叉树为空，②对每一个关键字，先进行查找，如果已存在，则不作任何处理，否则插入。
一句话，“从空树开始，每次插入一个关键字”。
例：给定关键字序列{53，45，12，24，90，45，80}，建立二叉排序树。

删除
叶子
直接删除即可。
 
左子树或右子树为空
“移花接木”：将左子树或右子树接到双亲上。
 
左右子树都不空
“偷梁换柱”：借左子树上最大的结点替换被删除的结点，然后删除左子树最大结点。（或者借用右子树上最小结点然后删除之亦可。）
 
分析
判定树和二叉排序树相同。结点的层次等于查找时比较关键字的个数。
 
若按照关键字有序的顺序插入结点建立二叉排序树，将得到一棵单支树，对其进行查找也退化为顺序查找，平均查找长度为(1+n)/2。一般地，如果在任一关键字k之后插入二叉排序树的关键字都大于或都小于k，则该二叉排序树是单分支的，深度是n，查找效率和顺序查找相同。
平衡二叉树
平衡因子和平衡二叉树(AVL树)
平衡因子：左子树深度 – 右子树深度。
平衡二叉树中各个结点的平衡因子只能是0，1，-1。
构造平衡二叉排序树
思路：按照建立二叉排序树的方法逐个插入结点，失去平衡时作调整。
失去平衡时的调整方法：
1) 确定三个代表性结点。(A是失去平衡的最小子树的根；B是A的孩子；C是B的孩子，也是新插入结点的子树)。关键是找到失去平衡的最小子树。
2) 根据三个代表性结点的相对位置(C和A的相对位置)判断是哪种类型(LL, LR, RL, RR)。
3) 平衡化。“先摆好三个代表性结点(居中者为根)，再接好其余子树(根据大小)”。


例：给定关键字的序列{13，24，37，90，53，40}，建立平衡二叉排序树。
注意：失去平衡时先确定失去平衡的最小子树，这是关键，然后判断类型（LL，LR，RL，RR），再平衡化处理。


分析
查找 (同二叉排序树)
平均查找长度ASL
结论：平均查找性能O(log n)。
为求得n个结点的平衡二叉树的最大高度，考虑高度为h的平衡二叉树的最少结点数。
 
部分结果如下，Fh表示斐波纳契数列第h项。
表 9.1 平衡二叉树的高度和结点个数
h Nh Fh  h Nh Fh
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
观察可以得出Nh = Fh+2 – 1, h≥0。解得
 
其中 。
时间复杂度
一次查找经过根到某结点的路径，所以查找的时间复杂度是O(log n)。
B-树和B+树
B-树
一棵m阶B-树，或为空树，或满足：
(1) 每个结点至多有m棵子树；
(2) 若根结点不是叶子，则至少有两棵子树；
(3) 除根之外的所有非终端结点至少有 棵子树；
(4) 所有非终端结点包含n个关键字和n+1棵子树：(n, A0, K1, A1, ..., Kn, An)，其中关键字满足A0<K1<A1<...<Kn<An，关键字的个数 。
(5) 所有叶子在同一层，不含信息，表示查找失败。
B+树
B+树和B-树的差异：n棵子树的结点中含有n个关键字；所有叶子结点中包含了全部关键字，且按大小顺序排列；所有非终端结点都是索引。
对B+树既可以进行顺序查找又可以进行随机查找。
键树
又叫数字查找树。
常见的两种存储结构：孩子兄弟链表，多重链表。
哈希表
哈希表(散列表，杂凑表)
根据设定的哈希函数和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置，这种表称为哈希表，又叫散列表，杂凑表。
哈希函数
常用除留余数法。H(key) = key MOD p。
冲突
什么是冲突？H(key1)=H(key2)，且key1≠key2，称冲突。
处理冲突的方法：当H(key)处已有记录，出现冲突，如何处理？
开放定址法
试用H(key)⊕di，常见以下三种。
(1) 线形探测再散列：试用H(key)⊕1，H(key)⊕2，...
(2) 二次探测再散列：试用H(key)⊕12，H(key)⊕-12，H(key)⊕22，H(key)⊕-22，...
(3) 伪随机探测再散列：试用H(key)⊕f(1)，H(key)⊕f(2)，...
再哈希法
H1(key)冲突，试用H2(key)，H3(key)，...
链地址法
发生冲突的记录链成单链表。
建立公共溢出区
所有冲突记录存入溢出区。
装填因子
 
n个记录，m个地址空间。
哈希表的平均查找长度与记录个数n不直接相关，而是取决于装填因子和处理冲突的方法。
举例
例：已知一组关键字{19, 14, 23, 1, 68, 20, 85, 9}，采用哈希函数H(key)=key MOD 11，请分别采用以下处理冲突的方法构造哈希表，并求各自的平均查找长度。
1) 采用线性探测再散列；
2) 采用伪随机探测再散列，伪随机函数为f(n) = - n；
3) 采用链地址法。

思路：开始时表为空，依次插入关键字建立哈希表。

1) 线性探测再散列

key 19 14 23 1 68 20 85 9  关键字
H(key) 8 3 1 1 2 9 8 9  H(key)
    2 3  9 10  冲突时计算下一地址
     4  10 0 
查找长度 1 1 1 2 3 1 3 3  每个关键字的查找长度

ASL = (1+1+1+2+3+1+3+3)/8 = 15/8

2) 伪随机探测再散列

key 19 14 23 1 68 20 85 9
H(key) 8 3 1 1 2 9 8 9
    0   7 8
        7
        6
查找长度 1 1 1 2 1 1 2 4

ASL = (1+1+1+2+1+1+2+4)/8 = 13/8

3) 链地址法


ASL = (1×5+2×3)/8 = 11/8
注：关键字在链表中的插入位置可以在表头或表尾，也可以在中间以便保持关键字有序。

最后，此哈希表的装填因子是α= 8/11。
内部排序
基础知识和算法
排序的有关概念
排序（按关键字大小顺序排列数据）。
排序方法：内部排序，外部排序；简单的排序方法O(n2)，先进的排序方法O(nlogn)，基数排序O(dn)；插入排序，交换排序，选择排序，归并排序，计数排序。
排序方法的稳定性：取决于该方法采取的策略，不是由一次具体的排序结果决定的。但是通过列举不稳定的排序实例可以说明该排序算法的不稳定性。
直接插入排序
思路
将待排序记录插入已排好的记录中，不断扩大有序序列
一句话，“将待排序记录插入有序序列，重复n-1次” 。
例：52，49，80，36，14，58，61 进行直接插入排序。
 
分析
表 10.1 直接插入排序
比较 移动
记录顺序有序时 n-1 0 最好
记录逆序有序时 ((n+2)(n-1))/2 ((n+4)(n-1))/2 最坏
平均n2/4，算法的时间复杂度O(n2)。直接插入排序是稳定的排序算法。
折半插入排序
思路
在直接插入排序中，查找插入位置时采用折半查找的方法。
程序
void BinInsertSort ( T a[], int n )
{
for ( i=1; i<n; i++ ) {
    // 在a[0..i-1]中折半查找插入位置使a[high]≤a[i]<a[high+1..i-1]
    low = 0;  high = i-1;
while ( low<=high ) {
      m = ( low+high )/2;
if ( a[i]<a[m] )
        high = m-1;
else
        low = m+1;
    }
    // 向后移动元素a[high+1..i-1]，在a[high+1]处插入a[i]
    x = a[i];
for ( j=i-1; j>high; j-- )
      a[j+1] = a[j];
    a [high+1] = x;  // 完成插入
  }
}
分析
时间复杂度O(n2)。比直接插入排序减少了比较次数。折半插入排序是稳定的排序算法。
希尔排序（缩小增量排序）
思路
先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。
步骤：
10. 分成子序列(按照增量dk)；
20. 对子序列排序(直接插入排序)；
30. 缩小增量，重复以上步骤，直到增量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)。
 
注意：希尔排序是不稳定的。时间复杂度大约为O(n3/2)。
程序
void ShellSort ( T a[], int n )
{
  dk = n/2;
while ( dk>=1 ) {
    // 一趟希尔排序，对dk个序列分别进行插入排序
for ( i=dk; i<n; i++ ) {
      x = a[i];
for ( j=i-dk; j>=0 and x<a[j]; j-=dk )
        a[j+dk] = a[j];
      a[j+dk] = x;
    }
    // 缩小增量
    dk = dk/2;
  }
}
起泡排序
思路
一句话，“依次比较相邻元素，‘逆序’则交换，重复n-1次” 。
例：冒泡排序(52，49，80，36，14，58，61)。
 
程序
分析
比较和交换总是发生在相邻元素之间，是稳定的排序算法。时间复杂度O(n2)。
快速排序
思路
一趟排序把记录分割成独立的两部分，一部分关键字均比另一部分小，然后再分别对两部分快排。
例：{52  49  80  36  14  58  61} 快速排序。
下面是一次划分的详细步骤：
 

整个快速排序过程如下：
 
程序
void QuickSort ( T a[], int low, int high )
{
if ( low < high ) {
    // 划分
    pivot = a[low];
    i = low; j = high;
while ( i < j ) {
while ( i<j && a[j] >= pivot )  j--;
      a[i] = a[j];
while ( i<j && a[i] <= pivot )  i++;
      a[j] = a[i];
    }
    a[i] = pivot;
    // 对子序列快排
    QuickSort ( a, low, i-1);
    QuickSort ( a, i+1, high); 
  }
}
分析
平均情况下，时间复杂度O(nlogn)。记录本来有序时为最坏情况，时间复杂度为O(n2)。
空间复杂度(考虑递归调用的最大深度)在平均情况下为O(logn)，在最坏情况下为O(n)。
快速排序是不稳定的。
简单选择排序
思路
第i趟排序过程是在剩余的待排记录中选一个最小（大）的，放在第i个位置。
一句话，“在待排记录中选取最小的，交换到合适位置，重复n-1次” 。
例：{52  49  80  36  14  58  61}简单选择排序。

程序
void SelectionSort ( T a[], int n )
{
for ( i=0; i<n-1; i++ ) {
    k = i;
for ( j=i+1; j<n; j++)
if ( a[j]<a[k] )  k=j;  // 最小记录
if ( k!=i )  a[i]a[k];
  }
}
分析
时间复杂度O(n2)，耗费在比较记录上，比较次数始终为n(n-1)/2，移动次数最小为0，最大3(n-1)，即n-1次交换。
注意：简单选择排序是不稳定的。反例：(101，102，9)  (9，102，101)。
堆排序
堆及其特点
堆，小顶堆，大顶堆。
序列{K1,K2, ..., Kn}满足Ki≤K2i，Ki≤K2i+1，称为小顶堆；若满足Ki≥K2i，Ki≥K2i+1，称为大顶堆，其中i=1, 2, ..., n/2。
特点：小顶堆的堆顶(第一个元素)为最小元素，大顶堆的堆顶为最大元素。
判断序列是否构成堆
方法：用Ki作为编号为i的结点，画一棵完全二叉树，比较双亲和孩子容易判断是否构成堆。
例：判断序列(12,36,24,85,47,30,53,91)是否构成堆。
 
根据上图判断，该序列构成小顶堆。
建立堆
一句话，“‘小堆’变‘大堆’，从 变到1” 。第 个是最后一个分支结点。
例：把(24,85,47,53,30,91,12,36)调整成小顶堆。


堆排序
思路：
 

例：(24,85,47,53,30,91,12,36)进行堆排序。





整个排序步骤如下：
 
堆排序是不稳定的。时间复杂度是O(nlogn)。
归并排序
思路
归并，两个或多个有序表合并成一个有序表。归并排序。

例：对{24, 85, 47, 53, 30, 91}归并排序。

程序
归并排序：
void MergeSort ( T a[], int low, int high )
{
if ( low>=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<n ) {
    s = t;  t = s*2;
    for ( i=0; i+t<=n; i+=t )
      Merge ( a, i, i+s-1, i+t-1 );
    if ( i+s<n )
      Merge ( a, i, i+s-1, n-1 );
  }
}

附：Merge()，将有序序列a[low..mid]和a[mid+1..high]归并到a[low..high]。
void Merge ( T a[], int low, int mid, int high )
{
  // 归并到b[]
  i = low;  j = mid+1;  k = low;
while ( i<=mid and j<=high ) {
if ( a[i]<=a[j] ) { b[k] = a[i];  i++; }
else  { b[k] = a[j];  j++; }
    k++;
  }
  // 归并剩余元素
while ( i<=mid )  b[k++] = a[i++];
while ( j<=high )  b[k++] = a[j++];
  // 从b[]复制回a[]
  a[low..high] = b[low..high];
}
分析
时间复杂度O(nlogn)。需要空间多，空间复杂度O(n)。归并排序是稳定的排序。
基数排序
思路
多关键字排序
最高位优先（MSD），最低位优先（LSD）。
链式基数排序
链式基数排序采用“分配”和“收集”策略。
例：{503，087，512，061，908，170，897，275，653}
分析：数字0~9共10种情况，rd=10。
      每个关键字都有3位数字，d=3。
      共有9个记录，n=9。
先“收集”成一个链表，
按最低位（个位）“分配”到10个链表中（0号~9号）：

按个位顺序“收集”成一个链表：
( 170, 061, 512, 503, 653, 275, 087, 897, 908 )
再按第2位数字（十位）“分配”到10个链表中：

“收集”成一个链表：
( 503, 908, 512, 653, 061, 170, 275, 897 )
按第3位数字（百位）“分配”到10个链表中：

“收集”成一个链表：
( 061, 170, 275, 503, 512, 653, 897, 908 )
完成排序。
分析
对n个数据进行基数排序，每个数据基数为rd，有d位数字。那么，一趟分配和收集用时n+rd(分配用n，收集用rd)，共需d趟，总的时间复杂度为O(d(n+rd))。
基数排序是稳定的排序算法。
各种排序方法比较
表 10.2 排序方法的比较
排序方法 时间复杂性 空间
复杂性 稳定 特点
平均 最好 最坏  
简单插入排序 O(n2) O(n) O(n2) O(1) 是 元素少或基本有序时高效
希尔排序 O(n3/2) O(1) 否
冒泡排序 O(n2) O(n) O(n2) O(1) 是
快速排序 O(nlogn) O(nlogn) O(n2) O(logn) 否 平均时间性能最好
简单选择排序 O(n2) O(1) 否 比较次数最多
堆排序 O(nlogn) O(1) 否 辅助空间少
归并排序 O(nlogn) O(n) 是 稳定的
基数排序 O(d(n+rd)) O(rd) 是 适合个数多关键字较小

基于关键字比较的排序方法，在最坏情况下所能达到的最好的时间复杂度是O(nlogn)。























《数据结构》复习大纲
1. 两者的区别在于插入和删除的位置不同，但都是在端点进行。
2. 线性结构包含线性表、栈和队列
3. 关于树结构的描述
4. 二叉树的根节点为第1层，以此类推
5. 详细分析
6. 用所有的元素对9取模
7.   顺序表与链表在存储和插入删除方面的区别
8.   考查二叉树的遍历问题，包括前序中序和后序遍历
9.   考查完全无向图顶点和边的关系
10.   考查二叉树的节点数与高度之间的关系
11.   考查图的邻接表存储
12.   考查快速排序的原理
13.   考查线性结构、树结构以及图结构之间的区别
14.   考查算法效率的度量
15.   考查链表的删除操作
16.   考查堆排序问题
17.   考查快速排序的原理
18.   考查二叉排序树的平均查找长度
19.   考查无向图的邻接表存储
20.   考查强连通图的基本概念
21.   考查堆排序算法处理查找问题的效率
22.   考查排序算法的空间复杂度
23.   考查二叉树深度与结点数的关系
24.   考查无向图的相关性质
25.   考查二叉排序树的插入操作
26.   考查有向图的相关性质
27.   考查基数排序
28.   考查链式栈的退栈操作
29.   考查排序算法的空间复杂度比较
30.   考查二叉树的相关性质
31.   考查折半查找法的比较次数
32.   考查数据的基本概念和性质
33.   考查希尔排序
34.   考查归并排序
35.   考查单链表的有序插入时间复杂度
36.   考查m叉树结点读书问题
37.   考查折半查找法的比较次数
38.   考查连通图的深度优先遍历过程
39.   考查栈结构的基本操作
40.    考查快速排序的原理
41.  考查赫夫曼树的带权路径长度和
42.  考查单链表判空条件
43.  考查排序算法性质和时间复杂度
44.  考查二叉树先序遍历与后序遍历的性质
45.  考查排序算法的性质
46.  考查m叉树结点数量与高度之间的关系
47.  考查顺序查找的时间复杂度
48.  考查二路归并的时间复杂度
49.  考查完全二叉树结点数量与高度之间的关系
50.  考查链式队列的入队列顺序
51.  考查无向图建立邻接表的时间复杂度
52.  考查赫夫曼树结点和叶结点的性质
53. 考查二叉排序树查找的平均时间复杂度
54.  考查邻接矩阵存储有向图的相关性质
55.   考查无向图顶点与其邻接表表头结点的关系
56.   考查无向图顶点与其最小生成树上边的关系
57.   考查快速排序基本原理
58.   考查二叉排序树的基本性质
59.   考查完全二叉树的基本性质
60.   考查循环结构的时间复杂度
61.   考查单向循环链表的判空条件
62.   考查二叉树高度与叶节点数量之间的关系
63.  考查折半查找的性质
64.  考查链式栈删除栈顶元素的操作序列
65.   考查字符串基本概念
66.   考查有序单链表的时间复杂度
67.   考查两字符串相等的充分必要条件
68.   考查哈希函数的相关性质
69.   考查二叉排序树插入操作时间复杂度
70.   考查顺序表的折半查找问题
71.   考查完全二叉树结点数和树高度的关系
72.   考查m叉树结点的相关性质
73.   考查无向图的深度优先遍历过程
74.   考查队列的基本概念
75.   考查循环结构的时间复杂度
76.   考查顺序表删除元素的操作
77.   考查森林与其对应二叉树之间结点数的关系
78.   考查直接插入排序的时间复杂度
79.   考查双向链表插入结点操作
80.   考查排序算法的时间复杂度
81.   考查栈结构的输入输出顺序
82.   考查哈希函数的基本概念
83.   考查树的结点数目相关性质
84.   考查无向图顶点和边数量的关系
85.   考查顺序表的平均比较次数
86.   考查折半查找的元素比较次数
87.   考查顺序表分块茶轴的平均查找长度
88.   考查有向无环图拓扑排序问题
89.   考查二叉排序树的深度
90.   考查循环结构的时间复杂度
91.  考查不同类型链表相关性质
92.  考查单向链表插入指定结点的步骤
93.  考查栈结构的输入输出
94.  考查m叉树结点度数与叶节点数量的关系
95.  考查二叉排序树结点数量的相关性质
96. 考查赫夫曼树带全路径长度计算方法
97. 考查使用线性探测法处理冲突的次数
98.  考查二叉树度数与结点数之间的关系
99.  考查插入排序次数与关键字长度的关系
100.  考查冒泡排序的基本原理
二、判断题
1.   递归调用深度优先算法可访问图的全部顶点
2.   满二叉树和完全二叉树的性质
3.   先序序列和后序序列无法确定树及其子树的根结点，因此无法确定二叉树形状
4.   链式存储结构的插入删除效率高于顺序存储
5.   关于栈和队列的讲解
6. 建立堆的过程
7.   根据完全二叉树的概念，叶结点的上一层必须满
8.   非循环结构的头尾元素无前驱或后继，参见教材第2章线性表相关内容
9. 算法2.5，算法2.10
10.   二叉树不同遍历顺序的特点
11.   关于链式栈和链式队列特点的讲解

南开19秋《数据结构》课程期末复习资料历年参考题目如下：