[TOC]
1 绪论
2 线性表
2.1 线性表的逻辑结构
- 线性结构
线性结构的基本特征为：一个数据元素的有序（次序）集
- 线性表的抽象数据类型
线性表是一种最简单的线性结构，线性表的抽象数据类型定义如下：
ADT List{
数据对象：
D={ai|ai∈ElemSet,i=1,2,...n，n>=0}
称n为线性表的表长，称n=0时的线性表为空表
数据关系：
R1={<ai-1,ai>|ai-1,ai∈D，i=2,...,n}
{ 设线性表为（a1,a2,...,ai,....,an}称i为ai在线性表中的位序}
基本操作：
结构初始化操作
结构销毁操作
引用型操作
销毁操作
}ADT；线性表的基本操作
(1)结构初始化操作 InitList（&L） （2）结构销毁操作 DestroyList(&L) （3）引用型操作 ListEmpty（L） （线性表判空） ListLength（L） （求线性表的长度） PriorElem（L，cur_e,&pre_e)(求数据元素的前驱) NextElem(L,cur_e,&next_e)（求数据元素的后继） GetElem(L,i,&e)（求线性表某个数据元素，返回线性表中第i个元素的值） LocateElem(L,e,compare()) （定位函数，返回L中第一个与e相等的位序） ListTraverse(L,visit())（遍历线性表，初始条件是线性表L存在） （4）结构初始化操作 ClearList（&L）（线性表置空） PutElem（&L，i，e）（将e的值赋给第i个元素） ListInsert（&L，i，e）（插入数据元素，在第i个元素前插入新的元素e，L的长度增1） ListDelete（&L，i,&e)（删除L的第i个元素，并用e返回其值，L的长度减1）
2.1.1 例题
- 选修同一门课的学生是线性结构（√）
- 农贸市场的人群是线性结构（x）
- 将线性表置为空表，就是销毁这个线性表（x）
- 线性表的长度必然大于零（X）
- 线性表中的每个元素，既有前驱，又有后继（X)
2.2 线性表的操作
2.2.1 合并集合
假设有两个集合A和B分别用两个线性表LA和LB表示，即线性表中的数据元素即为集合中的成员，现在求一个新的集合，要求
A=A∪B
A={1,2,4,6,7}
B={1,3,9,8}
- 操作步骤
- 从线性表LB中依次查看每个数据元素
- 依值在线性表LA中进行查访
- 若不存在，则插入之
void union(List &la,List lb){
la_len=listlength(la);
lb_len=listlength(lb);
for(i=1;i<lb_len;i++){
GetElem(lb,i,e);
if(!LocateElem(la,e,equal()))
ListInsert(la,++la_len,e);
}
}2.2.2 过滤集合中的重复元素
已知一个非纯集合B，试构造一个纯集合A，使A 中只包含B中所有各不相同的数据元素
初始：A={ }，B={6,2,9,3,6}
结果： A={6,2,9,3}
上述问题可以演绎为：
将存在于集合B中的元素逐个放入空集合A中，但A中不能有重复元素，算法策略与例1相同。
void union(List&la,list lb){
InitList(la);
la_len=ListLength(la);
lb_len=listlength(lb);
for(i=1;i<=lb_len;i++){
GetElem(lb,i,e);
if(!LocateElem(la,e,equal()))
ListInsert(la,++la_len,e);
}
}2.2.3合并有序表
- 有序表
若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或者非递增有序排列，则称改线性表为有序表（Ordered List）
A={1,4,5,7,9,12,15,17,20}
B={2,3,6,6,8}
C=A∪B={1,2,3,4,5,6,6,7,8,9,12,151,7,20}
void MergeList(List la,List lb,List&lc){
//本算法将非递减的有序表la和lb归并为lc
InitList(LC);//构造空的线性表lc
i=j=1;
k=0;
la_len=listlength(la);
lb_le=listlength(lb);
while((i<=la_len)&&(j<=lb_len)){//la和lb均不为空
//la和lb均不为空
GetElem(la,i,ai);
GetElem(lb,j,bj);
if(ai<=bj){
ListInsert(lc,++k,ai);//将ai插入到lc中
++i;
}
eles{
ListInsert(lc,++k,bj);//将bj插入到lc中
++j;
}
}
while(i<=la_len){//当la不为空时
GetElem(la,i++,ai);
ListInsert(lc,++k,ai);
}//插入la表中的剩余元素
while(j<=lb_len){//当lb不为空时
GetElem(lb,++j,bj);
ListInsert(lc,++k,bj);
}//插入lb表中的剩余元素
}2.3 顺序表
LOC(ai)=LOC(a1)+（i-1）xl
2.3.1线性表的顺序存储结构
2.3.1.1 顺序表初始化
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct{
ElemType *elem; //存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList; //称为 顺序表
//顺序表的初始化
Status InitList_Sq(SqList& L){
L.elem=(ElemType*)malloc(LIST_init_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}//Init_Sq
//算法时间复杂度O（1）
2.3.1.2 顺序表的查找
int LocateElem_Sq(SqList L,ElemType e,Status (*compare)(ElemType,ElemType)){
//在顺序表中查询第一个满足判定条件的数据元素
//若存在，则返回它的位序，否则返回0
i=1; //i 的初值为第1元素的位序
p=L.elem;
while(i<=L.length&&!(*compare)(*p++,e))++i;
if(i<=L.length)return i;
else return 0;
}//LocateElem_Sq
//算法时间复杂度O（ListLength(L)2.3.1.3 例题
- 编程时如何定义顺序表
typedef struct{
int *elem;//存储空间基址
int length;//当前长度
int listsize; //当前分配的存储容量，以sizeof(ElemType)为单位
}SqList; //称为顺序表- malloc函数如何使用
L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));- 如何引用顺序表中的变量
// 第一个元素a0: L->elem[0]//第i个元素ai: L->elem[i-1]//第n个元素an： L->elem[n-1] 或者L->elem[L->length-1]2.3.2 顺序表的插入
Status LisInsert_Sq(SqList&L,int i,ElemType e){ if(i<1||i>L.length+1)return ERROR; //插入位置不合法 if(L.length>=L.listsize){//分配存储空间 newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]);//q指示插入位置 for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p; //插入位置及之后位置向后移位 *q=e; //插入e ++L.length; //表长增1 return OK}//时间性能 若在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为： n/22.3.2.1例题
长度为n的顺序表，一共有 n+1 个插入位置，在第i个元素前插入一个新的元素，要移动的元素个数是 n-i+1
指针q指向顺序表的第i个元素用c语言程序表示：
q=&（L.elem[i-1]);在顺序表中，指针p所指向的元素后移一位：
*(p+1)=*p;
2.3.3 顺序表的删除
ListDelete(&L,i,&e);Status ListDelete_Sq(SqList &L,int i,ElemType &e){ if((i<1)||(i>L.length))return ERROR;//删除位置不合法 p=&(L.elem[i-1]);// p为被删除元素的位置 e=*p; //被删除元素的值赋给e q=L.elem+L.length-1; //表尾元素的位置 for(++p;p<=q;++p)*(p-1)=*p;//被删除元素之后的元素左移 --L.length;//表长减1 return OK}//删除算法的时间性能// E=qi(n-i) 求和（i-1到n）//若假定在线性表中任何一个位置上进行删除的元素概率相等 则 E=n-1/22.3.3.1 例题
- 长度为n的顺序表，一共有 n 个删除位置，如果要删除第i个元素，要移动的元素个数是 n-i个
- 指针q指向顺序表（表长为n）的元素用c语言程序表示
q=&(L.elem[n-1]);//或q=L.elem+L.length-1;在顺序表中，指针p所指向的元素前移一位如何用c语言程序表示：
*(p-1)=*p;
2.3 单链表
用一组地址任意的存储单元存放线性表中的数据元素
结点和单链表的类C语言描述
Typedef struct LNode{ ElemType data; //数据域 struct LNode *next //指针域}LNode,*LinkList;LinkList L; //L为单链表的头指针2.3.1 生成链表
生成链表的过程是结点逐个插入的过程
void CreateList_L(LinkList& L,int n){ //逆序输入n个数据元素，建立带头结点的单链表 L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; //先建立一个带头结点的单链表 for(i=n;i>0;--i){ p=(LinkList)malloc(sizeof(LNode)); scanf(&p->data); //输入元素值 p->next=L->next; L->next=p; //插入 }}//插入2.3.2 获取元素
GetElem(L,i,&e)Status GetElem(LinkList L,int i,ElemType &e){ p=L->next; j=1; while(p&&j<i){ p=p->next; ++j; } if(!p||j>i)return ERROR;//第i个元素不存在 e=p->data; //取得第i个元素 return OK; }//算法时间复杂度 O（n） n为单链表的长度2.3.3 单链表存储结构改进
typedef struct LNode{ ElemType data; struct LNode *next; }*Link,*Position;typedef struct{ Link head,tail;//分别指向头结点和最后一个结点的指针 int len;//指示链表长度 Link current;//指向当前被访问的结点的指针，初始位置指向头结点}LinkList;2.3.4 例题
- L是单链表的头指针，L指向头结点，单链表的第一个元素如何指向
L->next;- 指针p指向单链表中的第i个元素ai，ai+2如何指向？
p->next->next;- 欲在单链表的尾部增加一个新结点，必须遍历整个链表？
要看单链表的结构而定
2.3.5 单链表的插入
- 找到线性表中第i-1个结点
- 修改其指向后继的指针
Status ListInsert_L(LinkList L,int i,ElemType e){ //本算法在链表中第i个结点之前插入新的元素e p=L; j=0; while(p&&j<i-1){ p=p->next; ++j; //寻找第i-1个结点 } if(!p||j>i-1)return ERROR; //i大于表长或者小于1 S=(LinkList)malloc(sizeof(LNode)); //生成新结点 s->data=e; s->next=p->next; p->next=s; //插入}//算法时间复杂度 O(n)2.3.5.1 例题
- 指针p指向单链表的第i个元素ai，欲在ai后面连续插入两个元素m和n，写出主要算法
s=(LinkList)malloc(sizeof(LNode));s->data=m;s->next=p->next;p->next=s;p=s;s=(LinkList)malloc(sizeof(LNode));s->data=n;s->next=p->next;p->next=s;2.3.6 单链表的删除
ListDelete(&L,i,&e);//将链表第i个元素删除Status ListDelte(LinkList L,int i,Elmetype &e){ p=L; j=0; while(p->next&&j<i-1){ p=p->next; ++j; } if(!(p->next)||j>i-1)return ERROR; q=p->next; p->next=q->next; e=q->data; free(q); return OK;}//清空链表void ClearList(&L){ while(L->next){ p=L->next; L->next=p->next; free(p); }}//算法时间复杂度 O(n)2.3.6.1 例题
- 连续删除两个元素
q=p->next;p->next=q->next;free(q);q=p->next;p->next=q->next;free(q);2.4 单循环链表
最后一个结点的指针域的指针又指回头结点的链表
判别链表最后一个结点的条件是： 后继结点是否指向头结点
Typedef struct LNode{ ElemType data; //数据域 struct LNode *next //指针域}LNode,*LinkList;void CreatList(LinkList L,int n){ int i; Lnode *p,*s; p=L; for(i=1;i<n;i++){ s=(LinkList)malloc(sizeof(LNode)); s->data=i+1; s->next=p->next; p->next=s; p=s; }}2.7 双向链表
typedef struct DuLNode{ ElemType data; //数据域 struct DuLNode *prior; //指向前驱的指针域 struct DuLNode *next; //指向后继的指针域}DuLNode, *DuLinkList;void CreatListHead(DuLinkList L,int n){ int i; LNode *p,*s; p=L; for(int i=0;i<n;i++){ printf("请输入第%d个元素：",i+1); s=(DuLinkList)malloc(sizeof(LNode)); scanf("%d",&s->data); s->next=p->next; s->prior=p; p->next=s; if(s->next)s->next->prior=s; }}2.7.1 双向链表的插入
s->next=p->next;p-next=s;s->next->prior=s;s->prior=p;2.7.2例题
在双向链表中的元素ai前插入一个新元素e，指针p指向结点ai，写出相应的算法语句
s=(DuLinkList)malloc(sizeof(DulNode));s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;2.7.3双向链表的删除
q=p->nextp->next=p->next->next;q->next->prior=p;free(q);2.7.3.1 例题
- 删除双向链表中的元素ai，指针p指向结点ai，写出相应的算法语句
e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);2.7.2 双向链表的删除
2.4.1例题
- 单循环列表的转置
Status Contrary(LinkList &L){t=L; //t指向单循环链表的头结点p=t->next; //p指向单循环链表的第一个结点q=p->next; //q指向单循环链表的第二个结点while(p!=L){p->next=t; //让p结点next域指针指向其前驱t=p; //顺链向后移动指针tp=q; //顺链向后移动指针pq=p->next; //顺链向后移动指针q}L->next=t; //让L的next域指针指向新链表的第一个结点return OK;}- 约瑟夫环
3. 栈
3.1 栈的逻辑结构
栈是限定插入和删除只能在“固定端”进行的线性表。
ADT Stack{ 数据对象： D={ai|ai∈ElemSet，i=1,2,....n,n>=0} 数据关系： R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n} 基本操作： InitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(S) GetTop(S,&e) ClearStack(&S) Push(&S,e) Pop(&S,e) StackTravers(S,visit())}ADT Stack3.1.1 例题
- 栈中的元素是先进先出，后进后出（x)
- 栈有1个插入位置和2个删除位置（x)
- 栈底不进行元素的删除操作（X)
3.2 栈的顺序存储表示
#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;//栈的顺序存储表示typedef struct{ SElemType *base; SElemType *top; int stacksize;}SqStack;//顺序栈的初始化Status InitStack(SqStack &S){ //构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base)exit(OVERFLOW);//存储分配失败 S.top=S.base;//栈空的标志 S.stacksize=STACK_INIT_SIZE; return OK;}//顺序栈的插入Status Push(SqStack &S,SElemType e){ if(S.top-S.base>=S.stacksize){ S.base=(ElemType*)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(ElemType); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK;}//顺序栈的删除Status Pop(SqStack &S,SElemType e){ //若栈不空，则删除S的栈顶元素,用e返回其值，并返回OK //否则返回ERROR if(S.top==S.base)return ERROR; e=*--S.top; return OK;}3.2.1例题
顺序栈中的元素进制的顺序是 1、2、3、4、5、6，那么元素出栈的顺序不可能是
2 3 5 1 4 6
3.3 栈的应用
3.3.1 编辑命令行
“每接受一个字符即存入存储器” 并不恰当！
在用户输入一行的过程中，运行用户输入出 差错，并在发现有误时可以即时更正。
合理的作法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。
假设从终端接受了这样两行字符：
whli##ilr#e(s#*s)
outcha@putchar(*s=#++);
实际有效的是这两行：
while(*s)
putchar(*s++);
编辑命令行的算法
void LineEdit(){ InitStack(S); ch=getchar(); //从终端接受下一个字符 while(ch!=EOF){ //以EOF为全文结束符 while(ch!=EOF&&ch!='\n'){ //读入每一行 switch(ch){ case'#':Pop(S,c);break; case'@':ClearStack(S);break; default:Push(S,ch);break; } ch=getchar();//从终端接受下一字符 } //将从栈底到栈顶的字符传送至调用过程的数据区 ClearStack(S); //重置S为空栈 if(ch!=EOF)ch=getchar(); } DestroyStack(S);}//LineEdit3.3.1.1 例题
假设从终端接受了这样两行字符：
*s.#.top####-+#>s#top:=##=x;
top+@o#s-><#top++;
实际的有效输入：
*s->top=x;
s->top++;
3.3.2 数值转换
算法原理：N=(N div d)x d+N mod d
//数值转换算法void conversion(){ InitStack(S); scanf("%d",N); while(N){ Push(S,N%8); N=N/8; } while(!StackEmpty(S)){ Pop(S,e); printf("%d",e); }}3.3.3 括号匹配
原理：
凡是出现左括弧，则进栈
凡是出现右括弧：
若栈空： 则多余
若栈不空，则与栈顶元素比较，若相匹配，则左括弧出栈，否则不匹配
表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。
3.3.3.1 例题
< ( { [ ] } ( [ ( ) ] ) ) > √
{ ( ( ) [ < >]){ } { } X
( ( ) } [ < >]){ } { } X
3.3.4 迷宫求解
常用穷举求解的方法
若当前位置“可通”，则纳入路径，继续前进;
若当前位置“不可通”，则后退，换方向继续探索;
若四周“均无通路”，则将当前位置从路径中删除出去。
求迷宫中一条从入口到出口的路径的算法：设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； ｝ 否则 { …… ｝｝while (栈不空）；若栈空，则表明迷宫没有通路。 // …… 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则｛删去栈顶位置； // 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ｝3.3.5 表达式求值
- 运算符的优先级等级比较
| c1\c2 | + | - | * | / | ( | ) | # |
|---|---|---|---|---|---|---|---|
| + | > | > | < | < | < | > | > |
| - | > | > | < | < | < | > | > |
| * | > | > | > | > | < | > | > |
| / | > | > | > | > | < | > | > |
| ( | < | < | < | < | < | = | |
| ) | > | > | > | > | > | > | |
| # | < | < | < | < | < | > |
OperandType EvaluateExpression(){ InitStack(OPTR，"#");//OPTR是运算符栈 InitStack(OPND);c=getchar();//OPND是运算符栈 while(c!='#'||GetTop(OPTR)!='#'){ if(!ln(c,OP)){ Push(OPND,c); c=getchar(); else{ }//while return GetTop(OPND) } } Push(OPTR)}//switch(Precede(GetTop(OPTR),c)){ case'<':Push(OPTR,c);c=getchar();break; case'=':Push(OPTR,x);c=getchar();break; case'>':Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);//退栈 Push(OPND,Operate(a,theta,b));break;//将运算符结果入栈}//switch3.3.5.1 前缀表达式
3.3.5.2 中缀表达式
3.3.5.3 后缀表达式
2.3 用栈实现递归
当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：
将所有的实在参数、返回地址等信息传递给被调用函数保存；
为被调用函数的局部变量分配存储区；
将控制转移到被调用函数的入口。
从被调用函数返回调用函数之前，应该完成下列三项任务：
保存被调函数的计算结果；
释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。
后调用先返回 ！
汉诺塔问题：
void hanoi (int n, char x, char y, char z) {// 将塔座x上按直径由小到大且至上而下编号为1至n// 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 if (n==1) move(x, 1, z); // 将编号为１的圆盘从x移到z else { hanoi(n-1, x, z, y); // 将x上编号为１至n-1的圆盘移到y, z作辅助塔 move(x, n, z); // 将编号为n的圆盘从x移到z hanoi(n-1, y, x, z); // 将y上编号为１至n-1的圆盘移到z, x作辅助塔 } }void hanoi (int n, char x, char y, char z) { if (n==1) move(x, 1, z); else { hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); }}3.8 八皇后问题
#include<stdio.h>#define n 8 // n为皇后个数，m为摆法计数int m=0,a[n]; // a[i]存放第i个皇后放置的行号int ok(int i, int j) //检查(i,j)上能否放棋子{ j1=j; i1=i; ok1=1; //检查第i行上能否放棋子 while( (j1>1)&&ok1) {j1--; ok1=a[j1]!=i ;} j1=j; i1=i; //检查对角线上能否放棋子 while( (j1>1)&&(i1>1)&&ok1) {j1--; i1--; ok1=a[j1]!=i1 ;} j1=j; i1=i; //检查另一对角线上能否放棋子 while( (j1>1)&&(i1<n)&&ok1) {j1--; i1++; ok1=a[j1]!=i1 ;} return ok1}Void queen(int j) //从第j列开始逐个试探{ if (j>n) { m++; printf("m=%d ",m); for (i=1;i<=n;i++) printf(" %d",a[i]); printf(“\n”); } else for( i=1; i<=n;i++) if(ok(i,j)) //检查(i,j)上能否放棋子 { a[j]=i; //在(i,j)上放一个棋子 queen(j+1) ; } }main() {queen(1);}3.9 四色问题
“四染色”定理是计算机科学中著名的定理之一。使地图中相邻的国家或行政区域不重色，最少可用四种颜色对地图着色。利用栈采用回溯法对地图着色。
思想：对每个行政区编号：1-7；对颜色编号；a、b、c、d。从第一号行政区开始逐一染色，每一个区域逐次用四种颜色进行试探，若所取颜色与周围不重，则用栈记下来该区域的色数，否则依次用下一色数进行试探。若出现a-d均与周围发生重色，则需退栈回溯，修改当前栈顶的色数。
void mapcolor(int R[ ][ ],int n,int s[ ]){ s[1]=1; // 1号区域染1色 a=2; J=1; // a为区域号，J为染色号 while ( a<=n) { while(( J<=4)&&(a<=n)) { k=1; // k表示已经着色的区域号 while(( k<a)&&(s[k]R[a-1][k-1]!=J)) k=k+1; // 若不相邻，或若相邻且不重色，对下一个相邻已染色区域判断 if (k<a) J=J+1； //相邻且重色 else { s[a]=J; a=a+1; J=1; } //相邻且不重色 } if (J>4) { a=a-1; J=s[a]+1 } //回到上一个区域，选择下一号颜色试探 } }4. 队列
队列是限定插入在表尾和删除在表头进行的线性表。
ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ <a i-1,ai > | ai-1, ai ∈D, i=2,...,n} //约定其中a1 端为队列头， an 端为队列尾 基本操作： InitQueue(&Q) DestroyQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q, &e) ClearQueue(&Q) EnQueue(&Q, e) DeQueue(&Q, &e) QueueTravers(Q, visit())} ADT QueueInitQueue(&Q)//操作结果：构造一个空队列Q。 DestroyQueue(&Q)//初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)//初始条件：队列Q已存在。操作结果：将Q清为空队列。4.1 队列的链式实现
介绍队列的链表实现方式
typedef struct QNode { // 结点类型 QElemType data; struct QNode *next;} QNode, *QueuePtr;typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针} LinkQueue;//链队列的初始化Status InitQueue(LinkQueue &Q){ //构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW);//存储分配失败 Q.front->next=NULL; return OK;}//链队列的删除Status DeQueue(LinkQueue &Q, QElemType &e){ //若队列不为空，则删除Q的队头元素 //用e返回其值，并返回OK，否则返回ERROR 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;}4.2 队列的顺序实现
#define MAXQSIZE 100 //最大队列长度 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 头指针，若队列不空，指向队列头元素 int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置 } SqQueue;//循环队列的插入Status EnQueue (SqQueue &Q, ElemType e) { // 插入元素e为Q的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;}//循环队列的删除Status DeQueue (SqQueue &Q, ElemType &e) { // 若队列不空，则删除Q的队头元素， // 用e返回其值，并返回OK; 否则返回ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK;}//循环队列的长度4.2.1 例题
1.循环队列存储在数组A[0..9]中，其头、尾指针分别是front=3和rear=1，则队列中的元素个数为__8___。
- 设数组A[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行出队操作时修改指针的语句是（A）。
sq.front=( sq.front+1)%m
sq.front=( sq.front+1)%(m+1 )
sq.rear=( sq.rear+1)%m
sq.rear=( sq.rear+1)%(m+1)
4.2.2 斐波那契序列
void fb(int k){ int i,j;for(i=0;i<=k-2;i++) { f[i]=0 ; cq.elem[i]=0 ; } //为前k-1个元素赋初值0，并放入队列cq cq.elem[k-1]=f[k-1]=1; //为第k个元素赋值，并放入队列cq cq.rear=k-1; n=k; while(cq.elem[cq. rear]<max) //利用循环队列依次求f[n] {f[n]=0; for(j=0;j<k;j++) f[n]=f[n]+cq.elem[j]; cq.rear=(cq.rear +1) % k; cq.elem[cq.rear]=f[n]; n++; } //利用循环队列依次求f[n] if(cq.elem[cq.rear]>max) n=n-2; else n=n-1;}5 串
5.1 串的逻辑结构
串时有限长的字符序列，由一对单括号相括，如’a string’
串的逻辑结构与线性表相似，区别仅在于串的数据对象约束为字符集
串的基本操作和线性表有很大差别：
在线性表的基本操作中，大多以“单个元素”作为操作对象；
在串的基本操作中，通常以“串的整体”作为操作对象。
ADT String{数据对象：D={ai|ai∈CharacterSet, i=1,2,....,n, n>=0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,....,n}基本操作：StrAssign(&T,chars)DestroyString(&S)StrCopy (&T, S) StrLength(S)StrCompare (S, T) Concat (&T, S1, S2)StrEmpty (S) SubString (&Sub, S, pos, len)ClearString (&S) Index (S, T, pos)Replace (&S, T, V) StrInsert (&S, pos, T)StrDelete (&S, pos, len)}ADT String5.1.1 例题
- 串的数据对象约束为 字符集
- 空串‘’的长度为零
- 在串的基本操作中，通常以 串的整体 作为操作对象
StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。StrEmpty(S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE，否则返回 FALSE。 （'' 表示空串，空串的长度为零。）StrCompare(S,T) 初始条件：串 S 和 T 存在。 操作结果： 若S > T，则返回值 > 0； 若S = T，则返回值 = 0； 若S < T，则返回值 < 0 。例如：StrCompare('data', 'state') < 0 StrCompare('cat', 'case') > 0StrLength(S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。Concat(&T,S1,S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2联接而成的新串。例如： Concat( T, 'man', 'kind') 求得 T = 'mankind' SubString (&Sub, S, pos, len)初始条件：串 S 存在，1≤pos≤StrLength(S)，且0≤len≤StrLength(S)-pos+1。操作结果： 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串，子串为“串” 中的一个字符子序列。Index (S, T, pos) 初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置；否则函数值为0。（ “子串在主串中的位置”意指子串中的第一个字符在主串中的位序。）假设 S = 'abcaabcaaabc', T = 'bca' Index(S, T, 1) = 2；Index(S, T, 3) = 6；Index(S, T, 8) = 0 。5.1.2 例题
- Concat( T, ‘human’, ‘bing’), 求得 T = ‘humanbing’ 。
- SubString( sub, ‘discovery’, 4, 5), 求得 sub = ‘cover’。
- 假设 S = ‘alphaphazero’, T = ‘pha’ , Index(S, T, 2) = 3。
- 假设 S = ‘alphaphamaster’,
StrDelete (&S, 6, 3), 则S= 'alphamaster'。 - 若串S1=‘ABCDEFG’,S2= ‘1223’,S3=‘###’,执行Substring(&Sub, S1, Strlength(S3) ,Index(S2, ‘2’,1))，
则Sub= ‘CD’。
5.2串的定长顺序表示
#define MAXSTRLRN 255//用户可在255内定义最大串长typedef unsigned char SString [MAXSTRLEN+1];//0号单元存放串的长度Status Concar(SString S1,SString S2,SString &T){ //用T返回S1和S2联结而成的新串。若未截断，则返回TRUE，否则返回Flase if(S1[0]+S2[0]<=MAXSTRLEN){//未截断 T[1...S1[0]]=S1[1....S1[0]]; T[S1[0]+1...S1[0]+S2[0]]=S2[1...S2[0]]; T[0]=S1[0]+S2[0]; uncut=TRUE; } else if(S1[0]<MAXSTRLEN)//截断 { T[1...S1[0]]=S1[1..S1[0]]; T[S1[0]+1...MAXSTRLEN]=S2[1...MAXSTRLEN-S1[0]]; T[0]=MAXSTRLEN; uncut=FALSE;} else{ T[0...MAXSTRLEN]=S1[0...MAXSTRLEN]; uncut=FALSE; } return uncut;}//Concat5.3 串的堆分配存储表示
typedef struct{ char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL int length; //串长度}Hstring Status Concat(HString &T, HString S1, HString S2) { // 用T返回由S1和S2联接而成的新串 if (T.ch) free(T.ch); // 释放旧空间 if (!(T.ch = (char *) malloc((S1.length+S2.length)*sizeof(char)))) exit (OVERFLOW); T.ch[0..S1.length-1] = S1.ch[0..S1.length-1]; T.length = S1.length + S2.length; T.ch[S1.length..T.length-1] = S2.ch[0..S2.length-1]; return OK;} // Concat Status SubString(HString &Sub, HString S, int pos, int len) { // 用Sub返回串S的第pos个字符起长度为len的子串 if (pos < 1 || pos > S.length || len < 0 || len > S.length-pos+1) return ERROR; if (Sub.ch) free (Sub.ch); // 释放旧空间 if (!len) { Sub.ch = NULL; Sub.length = 0; } // 空子串 else { Sub.ch = (char *)malloc(len*sizeof(char)); Sub.ch[0..len-1] = S[pos-1..pos+len-2]; Sub.length = len; } // 子串的长度 return OK;} // SubString5.4 串的块链存储表示
5.4.1 用链表存储串
也可用链表来存储串值，由于串中的每一个字符是只有 8 位的二进制数，因此用链表存储串时，通常一个结点中存放的不是一个字符，而是一个子串。
存储密度 = 数据元素所占存储位/实际分配的存储位
存储密度小，处理方便，但是存储量大。
#define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链表结构 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString;5.5 串的模式匹配*
5.5.1 一般算法
int Index(SStirng S,SString T,int pos){i=pos;j=1; while(i<=S[0]&&j<=T[0]){ if(S[i]==T[j]){++i;++j;}//继续比较后继字符 else{ i=i-j+2; //指针后退重新开始匹配 j=1;} } if(j>T[0])return i-T[0]; else return 0;}5.5.2 KMP
KMP算法的时间复杂度可以达到O(m+n), 基本思想是每当字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配的结果”将模式向右“滑动”尽可能远的距离，继续进行比较。
int Index_KMP(SString S, SString T, int pos){ // 1≤pos≤StrLength(S) i = pos; j = 1; while (i <= S[0] && j <= T[0]) { if (j = 0 || S[i] == T[j]) { ++i; ++j; } // 继续比较后继字符 else j = next[j]; // 模式串向右移动 } if (j > T[0]) return i-T[0]; // 匹配成功 else return 0;} // Index_KMP void get_next(SString &T, int &next[] ) { // 求模式串T的next函数值并存入数组next i = 1; next[1] = 0; j = 0; while (i < T[0]) { if (j = 0 || T[i] == T[j]) {++i; ++j; next[i] = j; } else j = next[j]; } } // get_nextvoid get_nextval(SString &T, int &nextval[]) { i = 1; nextval[1] = 0; j = 0; while (i < T[0]) { if (j = 0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } } // get_nextval6.数组和广义表
6.1 数组
介绍数组的抽象数据类型
ADT Array{ 数据对象： D={aj1,j2...ji|ji=0,....bi-1,i=1,2,....n,n(>0)是数组的维数，bi是数组第i维的长度} 数据关系： R={R1,R2,....,RN} RI={<aj1,j2,...,aji,j+1,...jn|0<=jk<=bk-1,1<=k<=n且k≠i，0<=j1<=bi-2,i=1,2,...,n} 基本操作： InitArray() 若维数n和各维长度合法，则构造相应的数组A，并返回OK。 DestroyArray(&A) 销毁数组A Value(A,&e,index1,...,indexn) 初始条件：A是n维数组，e为元素变量，随后是n个下标值 操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK Assign(&A,e,index1,...,indexn) 初始条件：A是n维数组，e为元素变量，随后是n个下标值。 操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK}ADT Array6.1.1数组的顺序实现
两种顺序映像方式：
以行序为主序（低下标优先）
二维数组A中任一元素ai,j 的存储位置
LOC(i,j) = LOC(0,0) + (b2×i＋j)×L以列序为主序（高下标优先）
推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系。
LOC(j1, j2, …, jn ) = LOC(0,0,…,0) + ∑ ci ji
其中 cn = L，ci-1 = bi ×ci , 1 < i <= n
称为 n 维数组的映象函数, 数组元素的存储位置是其下标的线性函数。
6.1.1.1 例题
- 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( B )。
A．BA+141 B．BA+180 C．BA+222 D．BA+225 - 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为（232）。
- 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。
A. 808 B. 818 C. 1010 D. 1020
6.2 特殊矩阵
6.2.1 稀疏矩阵
假设 m 行 n 列的矩阵含 t 个非零元素，则称
σ=t/(m*n)
为稀疏因子，通常认为 σ<= 0.05 的矩阵为稀疏矩阵。
以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:
- 零值元素占了很大空间;
- 计算中进行了很多和零值的运算，遇除法还需判别除数是否为零。
6.2.1.1 特殊矩阵
三角矩阵
对称矩阵
对角矩阵
6.2.1.2 随机稀疏矩阵
非零元在矩阵中随机出现。
6.2.2 稀疏矩阵的转置
6.2.2.1 常规算法
//用常规的二维数组表示时的算法 for (col=1; col<=nu; ++col) for (row=1; row<=mu; ++row) T[col][row] = M[row][col];//其时间复杂度为: O(mu×nu)6.2.2.2 三元组顺序表
#define MAXSIZE 12500 typedef struct { int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值 } Triple; // 三元组类型typedef union { Triple data[MAXSIZE + 1]; int mu, nu, tu; } TSMatrix; // 稀疏矩阵类型//快速转置算法Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){ T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j]; cpot[1] = 1; for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1] + num[col-1]; for (p=1; p<=M.tu; ++p) {转置矩阵元素} } // if return OK;} // FastTransposeSMatrix// O(M.nu+M.tu)6.3 广义表
广义表是递归定义的线性结构，
LS = ( a1, a2,…, an )
其中：i 或为原子 或为广义表。
例如: A = ( )
F = (d, (e))
D = ((a,(b,c)), F)
C = (A, D, F)
B = (a, B) = (a, (a, (a, … , ) ) )
//广义表的抽象数据类型ADT Glist { 数据对象：D＝{ei | i=1,2,..,n; n≥0; ei∈AtomSet 或 ei∈GList, AtomSet为某个数据对象 } 数据关系： LR＝{<ei-1, ei >| ei-1 ,ei∈D, 2≤i≤n} 基本操作： //结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); //状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); //插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); //遍历 Traverse_GL(L, Visit());} ADT Glist6.3.1 例题
- 广义表（（a,b,c,d））的表头是（ C ），表尾是（ B ）。
A. a B.（） C.（a,b,c,d） D.（b,c,d） - 下面说法不正确的是( A )。
A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 - 当广义表中的每个元素都是原子时，广义表便成了_______。线性表
- 广义表的表尾是指除第一个元素之外，_______。其余元素组成的表
- 设广义表L=（（a,b,c）），则L的长度和深度分别为（ C ）。
A. 1和1 B. 1和3 C. 1和2 D. 2和3
6.3.2 广义表的实现
介绍广义表的头尾链表存储表示以及子表分析法存储表示。
6.3.2.1 头尾链表存储表示
表结点：
| tag=1 | hp | tp |
|---|
原子结点：
| tag=0 | data |
|---|
6.3.2.2 子表分析法
6.3.2.3 例题
- 广义表A=((a) , ((b,c),d))，画出头尾链表存储结构，求其长度和深度。
长度2，深度3。
- 已知广义表 LS=((a,b), (c,d,e,f), g)， head 和 tail 分别是求表头和表尾，则tail( tail( head( tail(LS)))) 的运算结果是_____。(e , f）
- 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是_______。(x,y,z)
6.3.3 广义表的递归操作
内容：介绍广义表的递归操作
- 递归函数
一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：
1)在每一次调用自己时，必须是(在某种意义上)更接近于解;
2)必须有一个终止处理或计算的准则。
- 用分治法设计递归函数
对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成k (1<k≤n)个子集，从而产生 l 个子问题，分别求解这 l 个问题，得出 l 个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。
在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。
- 对广义表进行分解
广义表从结构上可以分解成
广义表 = 表头 + 表尾
或者
广义表 = 子表1 + 子表2 + ··· + 子表n
因此常利用分治法求解之。
算法设计中的关键问题是，如何将 l 个子问题的解组合成原问题的解。
- 求广义表的深度
将广义表分解成 n 个子表，分别(递归)求得每个子表的深度，
广义表的深度=Max {子表的深度} +1
可以直接求解的两种简单情况为：
空表的深度 = 1
原子的深度 = 0
/*广义表的深度=Max {子表的深度} +1空表的深度 = 1， 原子的深度 = 0例：D=( A,B,C )=( ( ),(e),(a,(b,c,d)))DEPTH(D)=1+MAX{ DEPTH(A),DEPTH(B),DEPTH(C)}DEPTH(C)=1+MAX{ DEPTH(a),DEPTH((b,c,d))}=2DEPTH(D)=1+MAX{ 1,1,2}=3*/typedef enum {ATOM, LIST} ElemTag; // ATOM==0:原子, LIST==1:子表typedef struct GLNode { ElemTag tag; // 标志域 union{ AtomType atom; // 原子结点的数据域 struct {struct GLNode *hp, *tp;} ptr; };} *GListint GlistDepth(Glist L) { // 返回指针L所指的广义表的深度 if (!L) return 1; if (L->tag == ATOM) return 0; for (max=0, pp=L; pp; pp=pp->ptr.tp){ dep = GlistDepth(pp->ptr.hp); if (dep > max) max = dep; } return max + 1; } // GlistDepth 7. 树
7.1 树的逻辑结构
树的类型定义
数据对象D： D是具有相同特性的数据元素的集合数据关系R： 若D 为空集，则称为空树，否则： (1)在D中存在唯一的称为根的数据元素root。 (2)当n>=1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,...Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 - 查找类的操作：
Root(T)//求树的根结点Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的最右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,visit())//变量- 插入类的操作
InitTree(&T)//初始化置空树CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树- 删除类的操作
ClearTree(&T)//将树清空DestroyTree(&T)//销毁树的结果DeleteChild(&T,&p,i)//删除结点p的第i棵子树- 树型结构和线性结构的比较
| 线性结构 | 树型结构 |
|---|---|
| 第一个数据元素（无前驱） | 根结点（无前驱） |
| 最后一个数据元素（无后继） | 多个叶子结点（无后继） |
| 其它数据元素（一个前驱，一个后继） | 其它数据元素（一个前驱，多个后继） |
7.1.1 例题
- 树一定有唯一的根结点（X)
- 树的根结点有若干棵子树，则除树的根结点外的任一结点只能属于一棵子树（√）
- 树中结点最多只能有一个前驱，但可能有多个后继（√）
7.2 树的基本术语
结点：数据元素+若干指向子树的分支。
结点的度：分支的个数。
树的度：树中所有结点的度的最大值
叶子结点：度为零的结点
分支结点：度大于零的结点
有向树：
（1）有确定的根
（2）树根和子树根为有向关系
- 有序树：
子树之间存在确定的次序关系
- 无序树：
子树之间不存在确定的次序关系
- 结点的层次：
假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1
- 树的深度：
树中叶子结点所在的最大层次
- 森林：m棵互不相交的树的集合。
任何一棵非空树是一个二元组：Tree=(root,F)
其中：root被称为根结点。
F被称为子树森林。
7.2.1 例题
树的度：3
$n_0$=6
$n_1$=2
$n_2$=1
$n_3$=2
$n$=11
- 结点F的祖先结点包括：E,C,J
- 结点G 的子孙结点包括：D,H,I,B
- 从结点J到结点H的路径包括：结点J,G,D,H；路径：JG,GD,DH
- 树的深度为：4
- 非叶子/非终端结点包括J,C,G,E,D，内部结点包括C,G,E,D
- 树中每个结点有唯一的双亲结点，根结点除外（x）
7.3 二叉树的性质
7.3.1 二叉树的性质1
在二叉树的第i层上至多有 $ 2^{i-1} $个结点
7.3.2 二叉树的性质2
深度为$ k $的二叉树至多含$2^{k-1}$个结点（k>=1)
7.3.3 二叉树的性质3
对于任何一棵二叉树，若它含有$n_0$个叶子结点，$n_2$个度为2的结点，则必存在关系式：$n_0=n_2+1$。
7.3.4 二叉树的性质4
满二叉树：指的是深度为$k$,且含有$2^k-1$个结点的二叉树。
完全二叉树：树中所含的$n$个结点和满二叉树中编号为1至$n$的结点相对应。
具有n个结点的完全二叉树的深度为：$[log_2n]+1$(向下取整)
7.3.5 二叉树的性质5
若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为$i$的结点：
（1）若$i=1$,则该结点是二叉树的根，无双亲，否则，编号为[i/2]（向下取整）的结点为其双亲结点。
（2）若$2i>n$，则该结点无左孩子，否则，编号为$2i$的结点为其左孩子结点。
（3）若$2i+1>n$则该结点无右孩子，否则编号为$2i+1$的结点为其右孩子结点。
7.3.6 例题
- 在结点个数为n(n>1)的各种形态的树中，深度最小的树有 2 层。
- 在一棵深度为6的完全二叉树中，最少可以有多少结点，最多可以有多少个结点？ 最少：32 最多：63
- 在完全二叉树中，结点总数$n$为999，求叶子结点数$n_0$为多少？ 500
- 在完全二叉树中，结点总数为n，求叶子结点数为多少？
$n_0=n_2+1$
$n=2n_0+n1-1$
在完全二叉树中，$n_1$只能为1或0
当$n_1$为1时，$n$只能是偶数，$n_0=n/2$
当$n_1$为0时，$n$只能是奇数，$n_0=(n+1)/2$
所以$n_0=[(n+1)/2]$ （向下取整）
7.4 二叉树的存储表示
7.4.1 二叉树的二叉链表存储表示
#define MAX_TREE_SIE 100//二叉树的最大结点树typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTree bt;
typedef struct BiTNode{//结点结构 TElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode，*BiTree;
7.4.2 二叉树的三叉链表存储表示
typedef struct TriTNode{//结点结构 TElemType data; struct TriTNode *lchild,*rchild;//左右孩子指针 struct TriTNode *parent;//双亲指针}TriTNode, *TriTree;
7.4.3 二叉树的双亲链表存储表示
| data | parent | LRTag |
|---|
typedeg strcut BPTNode{//结点结构 TElemType data; int *parent;//指向双亲的指针 char LRTag;//左、右孩子标志域}BPTNode;typedef struct BPTree{//树结构 BPTNode nodes[MAX_TREE_SIZE]; int num_node;//结点数目 int root;//根结点的数模}BPTree;7.4.1 例题
- 如果二叉树用二叉链表表示，有多少个空链域？
空链域：
$$
2 n0+n1=n0+n0+n1=n2+1+n0+n1=n+1
$$
- 如果二叉树用三叉链表表示，有多少个空链域？
每个结点的双亲指针都不空，但根结点的双亲指针为空，所以有n+2个空链域。
- 二叉树不能用顺序结构来储存。
7.5 二叉树的遍历
介绍二叉树的各种递归和非递归的遍历方法，以及如何建立二叉树的存储结构。
二叉树遍历的搜索路径
对“二叉树”而言，可以有三条搜索路径：
1．先上后下的按层次遍历；
2．先左（子树）后右（子树）的遍历；
3．先右（子树）后左（子树）的遍历。
先左后右的遍历算法
先（根）序的遍历算法
中（根）序的遍历算法
后（根）序的遍历算法
先（根）序的遍历算法
若二叉树为空树，则空操作；否则，
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树。
$-+a*b-cd/ef$
中（根）序的遍历算法
若二叉树为空树，则空操作；否则，
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
$a+b*c-d-e/f$
后（根）序的遍历算法
若二叉树为空树，则空操作；否则，
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
$abcd-*+ef/-$
//递归void Preorder (BiTree T, void( *visit)(TElemType &e)){ // 先序遍历二叉树 if (T) { visit(T->data); // 访问结点 Preorder(T->lchild, visit); // 遍历左子树 Preorder(T->rchild, visit); // 遍历右子树 }}//先序非递归Status InOrderTraverse(BiTree T, Status (*Visit)(TElemType e)) { InitStack(S); Push(S,T); //根指针进栈 while (!StackEmpty (S)) { while(GetTop(S, p) && p) Push (S,p->lchild); Pop(S, p); //空指针退栈 if (!StackEmpty(S)){ //访问节点，退后一步 Pop (S, p); if (!Visit(p->data)) return ERROR; Push(S,p->rchild); } //if } //while return OK; }
//层次遍历算法的非递归描述void translevel(BinNode *bt) { struct BinNode *b; q.front=0; q.rear=0; if (!bt) return; q.elem[q.rear]=bt; q.rear=q.rear+1; while (q.front < q.rear) { b=q.elem[q.front]; q.front=q.front+1; printf("%c ",b->data); if (b->lch!=0) { q.elem[q.rear]=b->lch; q.rear=q.rear+1; } if (b->rch!=0) { q.elem[q.rear]=b->rch; q.rear=q.rear+1; } }}7.5.1 例题
先序遍历：JCEMFNGDHIB
中序遍历：MFNECJHDIBG
后序遍历：NFMECHBIDGJ
- 若二叉树先序遍历的扩展序列为ABDECF,其中代表空链域，则二叉树的后序遍历序列为CFEDBA。
- 已知一棵二叉树的中序遍历序列为DBACFEGM，后序遍历序列为DAFGECBM，画出这棵二叉树，并给出先序遍历序列。
先序遍历序列：MBDCAEFG
7.5 二叉树遍历算法的应用
7.5.1 建立二叉树的存储结构
Status CreateBiTree(BiTree &T){ Scanf(&ch); if(ch=='#')T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; CreateBiTree(T->lchild);//构造左子树 CreateBiTree(T->rchild);//构造右子树 } return OK；}//CreateBiTree
7.5.2 统计二叉树中叶子结点个数
算法基本思想:
先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。
由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。
void CountLeaf(BiTree T,int& count){ if(T){ if((!T->lchild)&&(!T->rchild)_ count++; CountLeaf(T->lchild,count); CountLeaf(T->rchild,count); }}7.5.3 求二叉树的深度
算法基本思想:
首先分析二叉树的深度和它的左、右子树深度之间的关系。
从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作改为：二叉树的深度为其左、右子树深度的最大值加1。
int Depth(BiTree T){ if(!T)depthval=0; else{ depthleft=Depth(T->lchild); depthright=Depth(T->rchild); depthval=1+(depthleft>depthright?depthleft:depthright); } return depthval;}7.5.4 复制二叉树（后序遍历）
//生成一个二叉树的结点//(其数据域为item,左指针域为lptr,右指针域为rptr)BiTNode *GetTreeNode(TElemType item, BiTNode *lptr, BiTNode *rptr ){ if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(1); T-> data = item; T-> lchild = lptr; T-> rchild = rptr; return T;}BiTNode *CopyTree(BiTNode *T) { if (!T ) return NULL; if (T->lchild ) newlptr = CopyTree(T->lchild);//复制左子树 else newlptr = NULL; if (T->rchild ) newrptr = CopyTree(T->rchild);//复制右子树 else newrptr = NULL; newT = GetTreeNode(T->data, newlptr, newrptr); return newT;} // CopyTree7.5.5 交换二叉树的左右子树
Void exchange (BinNode *T ) { BinNode *q; //中间变量 if ( T ) { q = T->lchild ; T->lchild= T->rchild; T->rchild = q; exchange(T->lchild); exchange(T->rchild); } }7.6 线索二叉树
内容：介绍线索二叉树的特性、中序线索二叉树的遍历和构建。
先序序列:
A B C D E F G H K
指向该线性序列中的“前驱”和
“后继” 的指针，称作“线索”。
包含 “线索” 的存储结构，称作 “线索链表”。
与其相应的二叉树，称作 “线索二叉树” 。
对线索链表中结点的约定：
在二叉链表的结点中增加两个标志域，
| lchild | ltag | data | rtag | rchild |
|---|
并作如下规定：
若该结点的左子树不空，
则Lchild域的指针指向其左子树，
且左标志域的值为“指针 Link”；
否则，Lchild域的指针指向其“前驱”，
且左标志的值为“线索 Thread” 。
若该结点的右子树不空，
则rchild域的指针指向其右子树，
且右标志域的值为 “指针 Link”；
否则，rchild域的指针指向其“后继”，
且右标志的值为“线索 Thread”。
如此定义的二叉树的存储结构称作“线索链表”。
typedef enum{Link,Thread}PointerThr;typedef struct BiThrNode{ TElemType data; struct BiThrNode *lchild,*child;//左右指针 PointerThr LTag，RTag;//左右标志}BiThrNode,*BiThrTree;- 中序遍历序列CBHFAEGD
7.6.1 变量中序线索二叉树
由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。
for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);中序遍历的第一个结点 ？
左子树上处于“最左下”（没有左子树）的结点。
在中序线索化链表中结点的后继 ？
若无右子树，则为后继线索所指结点；
否则为对其右子树进行中序遍历时访问的第一个结点。
Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e)) { p = T->lchild; // p指向根结点 while (p != T) { // 空树或遍历结束时，p==T while (p->LTag==Link) p = p->lchild; // 第一个结点 if (!Visit (p->data)) return ERROR; while (p->RTag==Thread && p->rchild!=T) { p = p->rchild; Visit(p->data); // 访问后继结点 } p = p->rchild; // p进至其右子树根 } return OK;} // InOrderTraverse_Thr。7.6.3 构造中序线索二叉树
void InThreading(BiThrTree p) { if (p) { // 对以p为根的非空二叉树进行线索化 InThreading(p->lchild); // 左子树线索化 if (!p->lchild) // 建前驱线索 { p->LTag = Thread; p->lchild = pre; } if (!pre->rchild) // 建后继线索 { pre->RTag = Thread; pre->rchild = p; } pre = p; // 保持 pre 指向 p 的前驱 InThreading(p->rchild); // 右子树线索化 } // if} // InThreadingStatus InOrderThreading(BiThrTree &Thrt, BiThrTree T) // 构建中序线索链表 { if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode)))) exit (OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; Thrt->rchild = Thrt; // 添加头结点if (!T) Thrt->lchild = Thrt; else { Thrt->lchild = T; pre = Thrt; InThreading(T); pre->rchild = Thrt; // 处理最后一个结点 pre->RTag = Thread; Thrt->rchild = pre; } return OK;} // InOrderThreading7.6.4 例题
- 已知二叉树，画出中序线索链表
- 引入二叉线索树的目的是(c)
A. 为了能方便地找到双亲
B. 为了能在二叉树中方便地进行插入和删除
C. 加快查找结点的前驱或后继的速度
D. 使二叉树的遍历结果唯一
在遍历中序线索二叉树时，某结点既有左子树又有右子树，那么它的前驱是其(D)
A. 右子树中最左下的结点
B. 右子树中最右下的结点
C. 左子树中最左下的结点
D. 左子树中最右下的结点
7.7 树和森林的存储结构
7.7.1 双亲表示法（树）
| ID | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 0 |
| 4 | E | 2 |
| 5 | F | 2 |
| 6 | G | 5 |
#define MAX_TREE_SIZE 100typedef struct PTNode{//结点结构 Elem data; int parent;//双亲位置域}PTNode;typedef struct{//树结构 PTNode nodes[MAX_TREE_SIZE]; int r,n;//根结点的位置和结点个数}PTree;| data | parent |
|---|
7.7.2 孩子链表表示法（树）
typedef struct CTNode { // 孩子结点结构 int child; struct CTNode *next; } *ChildPtr;typedef struct { // 双亲结点结构 Elem data; int parent; // 双亲位置域 ChildPtr firstchild; // 孩子链的头指针 } CTBox;typedef struct { // 树结构 CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根结点的位置 } CTree;| child | next |
|---|
| data | parent | firstchild |
|---|
7.7.3 孩子兄弟表示法
左链为孩子，右链为兄弟
typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling;} CSNode, *CSTree;| firstchild | data | nextsibling |
|---|
树的各种操作均可由对应的二叉树的操作来完成。
和树对应的二叉树，其左、右子树的概念已改变为：
左是孩子，右是兄弟。
7.7.4 森林和二叉树的对应关系
设森林
$$
F=(T_1,T_2,…T_N); \
T1=(root,t_11,t_12,…,t_1m);
$$
二叉树
$$
B=(LBT,Node(root),RBT);
$$
7.7.5 森林转换成二叉树的转换规则：
若 $F=\phi$，则$B=\phi$;
否则，
由$ROOT(T_1)$对应得到$Node(root)$;
由$ (t_11,t_12,..,t_1m)$对应得到$LBT$;
由$(T_2,T_3,…T_n)$对应得到$RBT$。
7.7.6 由二叉树转换为森林的转换规则
若$B=\phi$，则$F=\phi$;
否则，
由$Node(root)$对应得到$ROOT(T_1)$;
由$LBT$对应得到$(t_11,t_12,…,t_1m)$;
由$RBT$对应得到$(T_2,T_3,…,T_n)$
7.7.7 例题
- 把森林转换成用孩子兄弟法表示的二叉树
转换后：
- 把用孩子兄弟链表表示的二叉树转换成相应的森林
- 把森林转换成用孩子兄弟链表表示的二叉树
7.8 树和森林的遍历
先根（次序）遍历：
若树不空，则先访问根结点，然后依次先根遍历各棵子树
后根（次序）遍历：
若树不空，则依次后根遍历各棵子树，然后访问根结点
按层次遍历
若树不空，则自上而下自左至右访问树中的每个结点
先根遍历时顶点的访问次序：
A B E F C D G H I J K
后根遍历时顶点的访问次序：
E F B C I J K H G D A
层次遍历时顶点的访问次序：
A B C D E F G H I J K
7.8.1 森林的遍历
森林有三部分构成：
- 森林中第一棵树的根结点
- 森林中第一颗树的子树森林
- 森林中其它树构成的森林
7.8.1.1 森林的先序遍历
若森林不为空，则
访问森林中第一棵树的根结点
先序遍历森林中第一棵树的子树森林
先序遍历森林中（除第一棵树之外）其余树构成的森林。
依次从左至右对森林中的每一棵树进行先根遍历。
7.8.1.2 森林的中序遍历
若森林不空，则
中序遍历森林中第一棵树的子树森林
访问森林中第一棵树的根结点
中序遍历森林中（除第一棵树之外）其余树构成的森林。
依次从左至右对森林中的每一棵树进行后根遍历。
7.8.1.3 树的遍历、森林的遍历和二叉树遍历的对应关系
| 森林 | 树 | 二叉树 |
|---|---|---|
| 先序遍历 | 先根遍历 | 先序遍历 |
| 中序遍历 | 后根遍历 | 中序遍历 |
7.8.2 例题
- 求森林的先序和中序遍历
先序：ACEMFNGDHIB
中序：MFNECAHDIBG
- 求树的先根和后根遍历序列
先根：GCEMDHFNIB
后根：MECFHNDIBG
7.9 树和森林的算法
typedef struct CSNode{ Elem data; strcut CSNode *firstchild,*nextsibling;}CSNode,*CSTree;7.9.1 建立树的存储结构
假设以二元组$(F，C) $的形式自上而下、自左而右
依次输入树的各边，建立树的孩子-兄弟链表。
| “#” | “A” |
|---|---|
| “A” | “B” |
| “A” | “C” |
| “A” | “D” |
| “C” | “E” |
| “C” | “F” |
| “F” | “G” |
void CreatTree(CSTree &T){ T=NULL; for(scanf(&fa,&ch);ch!='';scanf(&fa,&ch)){ p=GetTreeNode(ch);//创建结点 EnQueue(Q,p);//指针入队列 if(fa=='#')T=p; else{ GetHead(Q,s);//取队列头元素（指针值） while(s->data!=fa){//查询双亲结点 DeQueue(Q,s); GetHead(Q,s); } if(!(s->firstchils)){ s->firstchild=p; r=p; } else{ r->nextsibling=p; //链接第一个孩子结点 r=p;//链接其他孩子结点 } } }}7.9.2 求树的深度
int TreeDepth(CSTree T){ if(!T)return 0; else{ h1=TreeDepth(T->firstchild); h2=TreeDepth(T->nextsibling); return(max(h1+1,h2)); }}//TreeDepth7.9.3 求树中的叶子结点树
void CountLeaf(CSNode T,int &count){ if(T){ if(!T->fch)count++; CountLeaf(T->fch,count); CountLeaf(T->nsib,count); }//if}//CountLeaf7.9.4 输出树中所有从根到叶子的路径
void OutPath(Bitree T,Stack &S){//输出森林中所有从根到叶的路径 while(T){ Push(S,T->data); else OutPath(T->firstchild,s); Pop(S); T=T->nextsibling; }//while}OutPath7.10 赫夫曼树
路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上分支的数目称作路径长度。
结点的路径长度：从根结点到该结点的路径上分支的数目。
树的路径长度：树中每个结点的路径长度之和。
树的带权路径长度：树中所有叶子结点的带权路径长度之和
$$
WPL(T)=\Sigma w_kl_k(所有叶子结点)
$$最优二叉树（或赫夫曼树）:假设有n个权值${w_1,w_2,…w_n}$,试构造一棵有n个叶子结点的二叉树，每个叶子结点的权值为$w_i$，其中带权路径长度$WPL$最小的二叉树称作最优二叉树（或赫夫曼树）。
$$
WPL(T)= 7\times2+5\times2+2\times3+4\times3+9\times2=60
$$
$$
WPL(T)=7\times4+9\times4+5\times3+4\times2+2\times1=89
$$
7.10.1 赫夫曼树的特点
- 赫夫曼树没有度为1的结点
- 赫夫曼树中结点总数$n$为$2n_0-1$
证明：
$$
n=n_0+n_1+n_2=2n_0-1
$$
7.10.2 例题
- 试证明具有$n_0$个叶子结点的哈夫曼树的分支总数为$2(n_0-1)$。
证明：
$$
由于哈夫曼树是一个二叉树，\而叶子结点树为n_0,
\由二叉树的性质3可知度为2的结点树为n_0-1。
\哈夫曼树的分支都输度=2的结点发出的，\所以哈夫曼树的分支总数为2(n_0-1)
$$
7.10.3 哈夫曼树的构造
以二叉树为例：
（1）根据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合
F = {T1, T2, … , Tn}，
其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树
为空树；
（2）在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、
右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值
为其左、右子树根结点的权值之和；
（3）从F 中删去这两棵树，同时加入刚生成的新树；
（4）重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。
7.10.4 例题
- 用于通信的电文由字符集{a, b, c, d, e, f, g, h}中的字符构成，这8个字母在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，为这8个字母设计哈夫曼编码。
8.图
8.1 图的逻辑结构
//图的抽象数据类型 ADT Graph{//图是由一个顶点集V和一个弧集R构成的数据结构 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集; 数据关系R：R={VR} VR={<v,w>|v,w∈V且p(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了<v,w>的意义或信息; (在弧<v,w>中，称v为弧尾，w为弧头。) } 
//基本操作CreateGraph(&G,V,VR);//按定义(V,VR)构造图DestroyGraph(&G);//销毁图LocateVex(G,u); //若G中存在顶点u,则返回该顶点在图中的位置，否则返回其他信息Getvex(G,v);//返回v的值PutVex(&G,v,value);//对v赋值valueFirstAdiVex(G,v);//返回v的“第一个邻接点”，若该顶点在G中没有邻接点，则返回“空”NextAdjVex(G,v,w);//返回v的（相对于w的）“下一个邻接 点”InsertVex(&G,v);//在图G中添加新顶点VDeleteVex(&G,v);//删除G中顶点v及其相关的弧InsertArc(&G,v,w);//在G中添加弧<v,w>，若G是无向的，则还增添对称弧<w,v>DeleteArc(&G,v,w);//在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次8.2. 图的基本术语
8.2.1 有向图
由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图
8.2.2 无向图
若$$<v, w>\in VR$$ 必有$$<w, v>\in VR$$, 则称$$ (v,w)$$ 为顶点$$v$$ 和顶点$$ w $$之间存在一条边，由顶点集和边集构成的图称作无向图。
8.2.3 网
弧或边带权的图分别称作有向网或无向网。
8.2.4 子图
设图$$G=(V,{VR})$$ 和图 $$G’=(V’,{VR’})$$，且 $$VV$$, $$VR’ \subseteq VR’$$，
则称 $$G’$$ 为$$ G$$ 的子图。
8.2.5 完全图、稀疏图和稠密图
假设图中有$$ n $$个顶点，$$e$$ 条边，则
含有 $$e=n(n-1)/2 $$条边的无向图称作无向完全图；
含有 $$e=n(n-1)$$ 条弧的有向图称作 有向完全图；
若边或弧的个数 $$e<nlogn$$，则称作稀疏图，否则称作稠密图。
8.2.6 无向图的邻接点、关联和度
假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，
边(v,w) 和顶点v 和w 相关联。
和顶点v 关联的边的数目定义为边的度。
例如：
ID(B)=3
ID(A)=2
8.2.7 有向图的邻接点、关联和度
假若顶点$$v$$ 和顶点$$w $$之间存在一条弧，则称顶点$$v$$ 和$$w$$ 互为邻接点，
弧$$<v,w>$$和顶点$$v$$ 和$$w$$ 相关联。
顶点的出度: 以顶点$$v$$为弧尾的弧的数目。
顶点的入度: 以顶点$$v$$为弧头的弧的数目。
$$顶点的度(TD)=出度(OD)+入度(ID)$$
例如：
OD(B)=1
ID(B)=2
TD(B)=3
8.2.8 路径、路径长度、简单路径、简单回路
设图$$G=(V,{VR})$$中的一个顶点序列$${ u=vi,0,vi,1, …, vi,m=w}$$中，
$$(vi,j-1,vi,j)\in VR ，1≤j≤m$$，则称从顶点$$u$$ 到顶点$$w$$ 之间存在一条路径。
路径上边的数目称作路径长度。
如:长度为3的路径$${A,B,C,F}$$
简单路径:
序列中顶点不重复出现的路径。
简单回路:
序列中第一个顶点和最后一个顶点相同的简单路径。
8.2.9 连通图、连通分量(无向图)
若无向图G中任意两个顶点之间都有路径想通，则称此图为连通图；
若无向图为非连通图，则图中各个极大联通子图称作此图的联通分量。
8.2.10 强联通图、强联通分量（有向图）
对于有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。
8.2.11 生成树和生成森林
- 假设一个连通图有 $$n$$ 个顶点和 $$e$$ 条边，其中 $$n-1$$ 条边和 $$n $$个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。
- 对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。
8.3 图的存储表示
内容：介绍图的邻接矩阵和邻接表的存储表示。
8.3.1 图的数组（邻接矩阵）存储表示
$$
A_{ij}=\begin{cases}
0,(i,j)\notin VR\
1,(i,j)\in VR
\end{cases}
$$
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 0 | 0 | 1 | 0 |
| B | 1 | 0 | 0 | 0 | 1 | 1 |
| C | 0 | 0 | 0 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 0 | 0 | 1 |
| E | 1 | 1 | 0 | 0 | 0 | 0 |
| F | 0 | 1 | 1 | 1 | 0 | 0 |
- 有向图的邻接矩阵不一定为对称矩阵
| A | B | C | E | F | |
|---|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 | 0 |
| B | 0 | 0 | 1 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 1 |
| E | 0 | 0 | 1 | 0 | 0 |
| F | 1 | 1 | 0 | 0 | 0 |
8.3.2 图的邻接表存储表示
8.3.2.1无向图的邻接表存储表示
8.3.2.2有向图的邻接表存储表示
8.3.2.3 有向图的逆邻接表存储表示
在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。
8.3.2.4 图的邻接表存储结构定义
typedef struct ArcNode{ //弧结点（或边结点）的结构 int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针 infoType *info;//该弧相关信息的指针}ArcNode;typedef struct VNode{//顶点结点的结构 VertexType data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{//图整体结构的定义 AdjList vertices; int vexnum,arcnum; //顶点数，边数 int kind;//图的种类标志}ALGraph;
8.3.3 例题
- 如果无向图中有n个顶点和e条边，那么它的邻接表中有 2e 个边结点。
- 在一个有向图的邻接表中，如果某个顶点结点指向第一条弧的指针为空，则该顶点的度一定为零(x) (没有出度但是有可能有入度)
- 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵（x) （强连通图的邻接矩阵是对称矩阵）
- 有向完全图中有n个顶点，那么它的逆邻接表中有n(n-1)个弧结点。
- 具有n个顶点和e条弧的有向图用邻接表存储表示时，需要n个头结点和e个弧结点（√）
- 画出有向图的逆邻接表，并写出入度最大的顶点和出度最大的顶点。
入度最大的顶点是A,出度最大的顶点是C 。
8.4图的遍历
内容：介绍图的深度优先搜索遍历和广度优先搜索遍历。
从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。
8.4.1 图的深度优先搜索遍历
从图中某个顶点$V_0$ 出发，访问此顶点，然后依次从$V_0$的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和$V_0$有路径相通的顶点都被访问到。
- 深度优先搜索遍历连通图的过程类似于树的先根遍历
- 如果判别V的邻接点是否被访问？
解决办法是：为每个顶点设立一个“访问标志 $visited[w]$”
- 非连通图如何进行深度优先搜索遍历？
非连通图的所有顶点全部放在一个结构里，依次对所有未被访问的顶点进行遍历
void DFS(Graph G,int v){//从顶点v出发，深度优先搜索遍历连通图G visited[v]=TRUE; VisitFunc(v);//访问第v个顶点 for(w=FirsrAdjVex(G,v));w!=0;w=NextAdjVex(G,v,w)) if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS}void DFSTraverse(Graph G,Status(*Visit)(int v)){ VisitFunc=Visit; for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//访问标志数组初始化 for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}8.4.2 图的广度优先搜索遍历
从图中的某个顶点$$V_0$$出发，并在访问此顶点之后依次访问$$V_0$$的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和$V_0$有路径相通的顶点都被访问到。
若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
void VFSTravserse(Graph G,Status (*Visit)(int v)){ for(v=0;v<G.vexnum;++v) visited[v]=FALSE;//初始化访问标志 InitQueue(Q); for(v=0;v<G.vexnum;++v) if(!visited[v]){//v尚未访问 visited[v]=TRUE; Visit(v);//访问v EnQueue(Q,v); while(!QueueEmpty(Q)){ DeQueue(Q,u);//队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)) if(!visited[w]){ visited[w]=TRUE; Visit(w); EnQueue(Q,w);//访问顶点w入队列 } } }}8.4.3 例题
- 广度优先搜索遍历(从顶点V出发）广度优先搜索遍历序列
$w_1 w_2 w_8 w_7 w_3 w_5 w_6 w_4$
图的广度优先搜索类似于二叉树的（D）遍历
A. 先根 B. 中根 C. 后根 D. 层次
从顶点A出发，写出它的深度优先搜索遍历序列(搜索邻接点时ASCII码值小的顶点优先)
$ACDFEBG$
深度优先遍历图和广度优先遍历图分别采用栈和队列来暂存结点。
已知有向图$G=(V，E)$，其中$V={v_1，v_2，v_3，v_4，v_5，v_6，v_7}，E={<v_1，v_2>，<v_1，v_3>，<v_1，v_4>，<v_2，v_5>，<v_3，v_5>，<v_3，v_6>，<v_3，v_7>，<v_4，v_6>，<v_5，v_7>，<v_6，v_7>}$，对$G$从$v_1$进行$DFS$，若下标小的邻接点优先遍历，则得到的序列是
1 2 5 7 3 6 4
8.4.4. 图的遍历算法的应用
8.4.4.1 求两个顶点之间的简单路径
求从顶点 b 到顶点 k 的一条简单路径，从顶点 b 出发进行深度优先搜索遍历。
假设找到的第一个邻接点是c，则得到的结点访问序列为: $b c h d a e k f g$
假设找到的第一个邻接点是a，则得到的结点访问序列为：
$b a d h c e k f g $
结论
从顶点 i 到顶点 s ,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s 。
遍历过程中搜索到的顶点不一定是路径上的顶点。
void DFSearch(int v,int s,char *PATH){ //从第v个顶点出发递归地深度优先遍历图G //求得一条从v到s的简单路径，并记录在PATH中 visited[v]=TRUE;//访问第v个顶点 Append(PATH,getVertex(v));//第v个顶点加入路径 for(w=FirstAdjVex(v);w!=0&&!found;w=NextAdjVex(v)) if(w=s){ found=TRUE; Append(PATH,w); } else if(!visited[w])DFSearch(w,s,PATH); if(!found)Delete(PATH);//从路径上删除顶点v}8.4.4.2 求两个顶点之间的路径长度最短的路径
若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。路径长度最短：指的是分支的数目最少，而非距离的绝对数值最小。
可以理解为乘坐公交车去某地，换乘次数最少。
深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。
求路径长度最短的路径可以基于广度优先搜索遍历进行，但需要修改链队列的结点结构及其入队列和出队列的算法。
- 将链队列的结点改为“双链”结点。即结点中包含next 和prior两个指针；
- 修改入队列的操作。插入新的队尾结点时，令其prior域的指针指向刚刚出队列的结点，即当前的队头指针所指结点；
- 修改出队列的操作。出队列时，仅移动队头指针，而不将队头结点从链表中删除。
typedef DuLinKListQueuePtr;void InitQueue(LinkQueue& Q){ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); Q.front->next=Q.rear->next=NULL;}void EnQueue(LinkQueue& Q,QelemType e){ p=(QueuePtr)malloc(sizeof(QNode)); p->data=e; p->next=NULL; p->prior=Q.front; Q->rear->next=p; Q.rear=p;}voif DeQueue(LinkQueue &Q,QelemType &e){ Q.front=Q.front->next; e=Q.front->data;}8.4.4.3 例题
坐公交车从A站到B站，中间可能有换乘，如果希望换乘次数最少，可以根据什么算法来设计解决方案。( C )
A．关键路径 B．深度优先搜索
C. 广度优先搜索 D．迪杰斯特拉对有n个顶点、e条边且采用邻接矩阵作为存储结构的无向图进行深度优先搜索遍历的时间复杂度为( B )。
A.O(n) B.O($n^2$) C.O(n+e) D.O(e)
8.5 最小生成树
问题的提出：
假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？
该问题等价于构造(连通网的)最小生成树：
构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。
8.5.1 普利姆算法
基本思想:
取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 条边为止。
struct{ VertexType adgvex;//U集中的顶点序号 VRType lowcost;//边的权值}closeedge[MAX_VERTEX_NUM];
| 0a | 1b | 2c | 3d | 4e | 5f | 6g | |
|---|---|---|---|---|---|---|---|
| Adjvex | c | d | e | a | d | e | |
| Lowcost | 5 | 3 | 8 | 14 | 21 | 16 |
void MiniSpanTree_P(MGraph G, VertexType u) { //用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化 if (j!=k) closedge[j] = { u, G.arcs[k][j].adj }; closedge[k].lowcost = 0; // 初始，U＝{u} for (i=0; i<G.vexnum; ++i) { k = minimum(closedge); // 求出加入生成树的下一个顶点(k) printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树上一条边 closedge[k].lowcost = 0; // 第k顶点并入U集 for (j=0; j<G.vexnum; ++j) //修改其它顶点的最小边 if (G.arcs[k][j].adj < closedge[j].lowcost) closedge[j] = { G.vexs[k], G.arcs[k][j].adj }; }}8.5.3 克鲁斯卡尔算法
基本思想:
考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。
具体做法: 先构造一个只含 $n$ 个顶点的子图$ SG$，然后从权值最小的边开始，若它的添加不使$SG$ 中产生回路，则在 $SG $上加上这条边，如此重复，直至加上 $n-1$ 条边为止。
算法描述： 构造非连通图ST=（V,{});k=i=0;//k计选中的边数while(k<n-1){ ++i; 检查边集E中第i条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路，则输出边(u,v);且k++;}8.5.4 两种算法的比较
n为顶点数，e为边数。
| 算法名 | 普利姆算法 | 克鲁斯卡尔算法 |
|---|---|---|
| 时间复杂度 | O($n^2$) | O(eloge) |
| 适应范围 | 稠密图 | 稀疏图 |
8.5.5 例题
- 无向图一定有唯一形态的最小代价生成树（x）
- 根据普利姆（prim）算法，求它的最小生成树及最小代价（起始点为A）
最小代价：42。
- 设n为网中顶点数，e为网中边数，构造最小生成树的prim算法和kruskal算法的区别在于（ A）。
A．prim算法的时间复杂度为O($n^2$) , 适用于求边稠密的网的最小生成树;
B．prim算法的时间复杂度为O(eloge)，适用于求边稀疏的网的最小生成树;kruskal算法的时间复杂度为O(eloge)，适用于求边稀疏的网的最小生成树。
C．prim算法的时间复杂度为O($n^2$) , 适用于求边稀疏的网的最小生成树;kruskal算法的时间复杂度为O($n^2$) , 适用于求边稠密的网的最小生成树。
D．以上都不对kruskal算法的时间复杂度为O(eloge)，适用于求边稠密的网的最小生成树。
8.6 拓扑排序
1、问题的提出
假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。
检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。
2、什么是拓扑排序
按照有向图给出的次序关系，将图中顶点排成一个线性序列，对应有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系，由此所得顶点的线性序列称之为拓扑有序序列。
可求得拓扑有序序列：
A B C D 或 A C B D
反之，对于下列有向图不能求得它的拓扑有序序列。
因为图中存在一个回路 {B, C, D}
3、如何进行拓扑排序？
（1）从有向图中选取一个没有前驱的顶点，并输出之；
（2）从有向图中删去此顶点以及所有以它为尾的弧；
（3）重复上述两步，直至图空；或者图不空但找不到无前驱的顶点为止。
4、 算法描述
//取入度为零的顶点v;while (v<>0){ printf(v); ++m; w:=FirstAdj(v); while (w<>0) { inDegree[w]--; w:=nextAdj(v,w); } 取下一个入度为零的顶点v;}if m<n printf(“图中有回路”);//在算法中需要用定量的描述替代定性的概念，没有前驱的顶点 == 入度为零的顶点，删除顶点及以它为尾的弧 ==弧头顶点的入度减1。为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。
CountInDegree(G,indegree); //对各顶点求入度InitStack(S);for ( i=0; i<G.vexnum; ++i) if (!indegree[i]) Push(S, i); //入度为零的顶点入栈count=0; //对输出顶点计数while (!EmptyStack(S)) { Pop(S, v); ++count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w)){ --indegree(w); // 弧头顶点的入度减一 if (!indegree[w]) Push(S, w); //新产生的入度为零的顶点入栈 }}if (count<G.vexnum) printf(“图中有回路”)8.6.1 例题
- 已知有向图G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7}，E={<v1，v2>，<v1，v3>，<v1，v4>，<v2，v5>，<v3，v5>，<v3，v6>，<v4，v6>，<v5，v7>，<v6，v7>}，G的一个拓扑有序序列是( A )。
A.v1，v3，v4，v6，v2，v5，v7 B.v1，v3，v2，v6，v4，v5，v7
C.v1，v3，v4，v5，v2，v6，v7 D.v1，v2，v5，v3，v4，v6，v7 - 具有拓扑有序序列的图一定是（A ）。
A. 有向无环图 B. 有向完全图 C. 强连通图 D. 有环 - 对AOV网进行拓扑排序得到的拓扑有序序列不一定是唯一的。（ √ ）
- 对AOV网进行拓扑排序，若当前图中虽有顶点，但不存在无前驱的顶点，则说明此有向图中存在环。（ √ ）
8.7 关键路径
假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间（AOE网）。问：哪些子工程项是“关键工程”？
（即：哪些子工程项将影响整个工程的完成期限?）
1、“整个工程完成的时间”为：从有向图的源点到汇点的最长路径。
（起始时间从0开始)
2、“关键活动”指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。
3、“事件(顶点)” 的 最早发生时间 $ve(j)$
$ve(j) = 从源点到顶点j的最长路径长度；$
4、“事件(顶点)” 的 最迟发生时间$ vl(k)$
$vl(k) = 从顶点k到汇点的最短路径长度= 汇点发生时间-顶点k到汇点的最长路径路径长度。$
8.7.1 例题
- 求关键路径
behk
- 关键路径是AOE网络中（B）。
A. 从源点到汇点的最短路径 B. 从源点到汇点的最长路径 C. 最长的回路 D. 最短的回路 - 关于AOE网，下面不正确的说法是 ( A )。
A. 缩短某个关键活动的完成时间，整个工程必然提前完成 B. 关键路径是从源点到汇点的最长路径 C. 可能有多条关键路径 D. 如果缩短关键活动的完成时间，则可能需要重新规划关键路径
8.6 最短路径
8.6.1从某个源点到其余各的最短路径
求从源点到其余各点的最短路径的算法的基本思想:
依最短路径的长度递增的次序求得各条路径。
其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。路径长度最短的最短路径的特点：
在这条路径上，必定只含一条弧，弧尾是$v_1$，并且这条弧的权值最小。
下一条路径长度次短的最短路径的特点：
它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点$v_1$，再到达该顶点(由两条弧组成)。
再下一条路径长度次短的最短路径的特点:
它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点$v_1$，再到达该顶点(由两条弧组成)；或者是从源点经过顶点$v_2$，再到达该顶点。其余最短路径的特点：
它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。
8.6.2 迪杰斯特拉算法
设置辅助数组Dist，其中每个分量Dist[k] 表示当前所求得的从源点到其余各顶点 k 的最短路径。
一般情况下，
Dist[k] = <源点到顶点 k 的弧上的权值>
或者 = <源点到其它顶点的路径长度>
- <其它顶点到顶点 k 的弧上的权值>。
1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。$$A_{ij}=\begin{cases}G.arcs[v_0][k],v_0和k之间存在弧\INFINITY,v_0和k之间不存在弧\end{cases}$$其中的最小值即为最短路径的长度。2）修改其它各顶点k的Dist[k]值。假设求得最短路径的顶点为u，若 $Dist[u]+G.arcs[u][k]<Dist[k]$则将 $Dist[k] 改为 Dist[u]+G.arcs[u][k]$。
8.6.3 例题
- 求从顶点$v_0到其余各个顶点的最短路径，给出过程。
9.查找
9.1.查找表
查找表是由同一类型的数据元素(或记录)构成的集合。
由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。
- 查找表的操作
- 查询某个“特定的”数据元素是否在查找表中
- 检索某个“特定的”数据元素的各种属性
- 在查找表中插入一个数据元素
- 从查找表中删去某个数据元素
- 查找表的分类
静态查找表
仅作查询和检索操作的查找表
动态查找表
有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表”中的数据元素。
- 关键字
是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。
若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。
若此关键字能识别若干记录，则称之谓“次关键字”。
- 查找
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）
若查找表中存在这样一个记录，则称“查找成功”，查找结果给出整个记录的信息，或指示该记录在查找表中的位置；
否则称“查找不成功”，查找结果给出“空记录”或“空指针”。
- 查找的方法
查找的方法取决于查找表的结构。
如果查找表中的数据元素之间不存在明显的组织规律，就不便于查找。
为了提高查找的效率， 需要在查找表中的元素之间人为地附加某种确定的关系，换句话说， 用某种特定的结构来表示查找表。
9.1.1 例题
- 静态查找表的操作包括 查询、检索。
- 动态查找表的操作包括 查询、检索、插入、删除。
- 主关键字有可能识别若干记录（X）。
- 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录，若查找表中存在这样一个记录，则称“查找成功”（√）。
9.2 静态查找表
ADT StaticSearchTable{ 数据对象D ：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。 数据关系R：数据元素同属一个集合; 基本操作P：Create(&ST,n); Destroy(&ST); Search(ST,key); Traverse(ST,Visit())}ADT StaticSearchTable;//静态查找表的基本操作/*Create(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST;Destroy(&ST);初始条件：静态查找表ST存在;操作结果：销毁表ST。Search(ST,key);初始条件：静态表ST存在，key为和查找表中元素的关键字类型相同的给定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”Traverse(ST,visit())初始条件：静态查找表ST存在，Visit是对元素操作的应用函数操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。 */9.2.1 例题
- 在静态查找表已经存在的情况下，对其的操作一般不改变查找表的结构（√）
- 静态查找表查找成功是指查找表中存在其关键字等于key的数据，key为和查找表中元素的关键字类型相同的给定值。（√）
9.3 顺序表的查找
typedef struct{ ElemType *elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length;//表的长度}SSTable; //顺序表int Search_Seq(SSTable ST,KeyType key){ //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0. ST.elem[0].key=key;//“哨兵” for(i=ST.length;ST.elem[i].key!=key;--i);//从后往前找 return i; //找不到时，i为0}//Search_Seq9.3.1 顺序查找表的时间性能
定义：查找算法的平均查找长度（Average Search Length)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值
$$
ASL=\Sigma P_iC_i
$$
对于顺序表而言，$C_i=n-i+1$
$$
ASL=nP_1+(n-1)P_2+···+2P_{n-1}+P_n
$$
在等概率查找的情况下，$p_i=\frac{1}{n}$
顺序表查找的平均查找长度为：
$$
ASL_{ss}=\frac{1}{n}\Sigma (n-i+1)=\frac{n+1}{2}
$$
在不等概率查找的情况下，$ASL_{ss}$在$P_n \geq P_n-1 \geq ···\geq P_2 \geq P_1 $ 时取极小值
若查找概率无法事先测定，则查找过程中采取的改进办法是，在每个查找之后，将刚刚查找到的记录直接移至表尾的位置上。
9.3.2 例题
- 在顺序表（23，41，75，18，92，49，7，55）中顺序查找其关键字等于给定值49的数据元素，若找到，则给定值49与关键字比较的次数为 3 次。
- 在顺序表（23，41，75，18，92，49，7，55）中顺序查找其关键字等于给定值25的数据元素，若确定找不到，则给定值25与关键字比较的次数为 9 次。
- 对顺序表（23，41，75，18，92，49，7，55）进行等概率顺序查找的平均查找长度ASL为4.5。
9.4 有序表的查找
顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。
若以有序表表示静态查找表，则查找过程可以基于“折半”进行。
int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while(low<=high) { mid = (low+high)/2; if (EQ(key,ST.elem[mid].key)) return mid; // 找到待查元素 else if(LT(key,ST.elem[mid].key)) high= mid-1; // 继续在前半区间进行查找 else low= mid+1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素} // Search_Bin9.4.1 折半查找平均查找情况
一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。
假设 $ n=2^h-1$(满二叉树)，并且查找概率相等，则
$$
A S L_{b s}=\frac{1}{n} \sum_{i=1}^{n} C_{i}=\frac{1}{n}\left[\sum_{j=1}^{h} j \times 2^{j-1}\right]=\frac{n+1}{n} \log {2}(n+1)-1
$$
$n>50$时，可得近似结果
$$
ASL{bs}\approx log_2(n+1)-1
$$
9.4.2 索引顺序表的查找
索引顺序表的查找过程：
- 由索引确定记录所在区间；
- 在顺序表的某个区间内进行查找
索引顺序查找的过程也是一个“缩小区间”的查找过程。
$$
索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度
$$
9.4.3 例题
- 画出在有序表A[1..15]中进行折半查找的判定树，并求出等概率情况下查找成功的平均查找长度。
$\frac{49}{15} $
在等概率的情况下对31个关键字的有序列表进行折半查找，查找成功时的平均查找长度为：
$$
\frac{31+1}{31}log_232-1=\frac{32*5}{31}-1=\frac{160-31}{31}=\frac{129}{31}
$$对线性表进行折半查找时，要求线性表必须（ B ）。
A. 以顺序方式存储 B. 以顺序方式存储，且数据元素有序C. 以链接方式存储 D. 以链接方式存储，且数据元素有序
9.5 动态查找表
ADT DynamicSearchTable{数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合。基本操作P：InitDSTable(&DT);DestroyDSTable(&DT);SearchDST(DT,key);DeleteDSTable(&T,key);DestroyDSTable(&DT);InsertDSTable(&DT,e);DeleteDSTable(&T,key);TraverseDSTable(DT,Visit());}ADT DynamicSearchTable;InitDSTable(&DT);
操作结果：构造一个空的动态查找表DT。
DestroyDSTable(&DT);
初始条件：动态查找表DT存在；
操作结果：销毁动态查找表DT。
SearchDSTable(DT, key);
初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；
操作结果：若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。
InsertDSTable(&DT, e);
初始条件：动态查找表DT存在，e 为待插入的数据元素；
操作结果：若DT中不存在其关键字等于 e.key 的 数据元素，则插入e 到DT。DeleteDSTable(&T, key);
初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；
操作结果：若DT中存在其关键字等于key的数据元素，则删除之。
TraverseDSTable(DT, Visit());
初始条件：动态查找表DT存在，Visit是对结点操作的应用函数；
操作结果：按某种次序对DT的每个结点调用函数 Visit() 一次且至多一次。一旦 Visit() 失败，则操作失败。
9.5.1 例题
- 在动态查找表的插入操作中，和给定值比较的对象是数据元素的关键字，插入的对象是数据元素（或记录）
- 在动态查找表的删除操作中，删除的对象是数据元素
9.6 二叉排序树
内容：介绍二叉排序树的特点及其查找、插入和删除算法。
二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
（3）它的左、右子树也都分别是二叉排序树。
typedef struct BiTNode{//结点结构 TElemType data; struct BiTnode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;3、二叉排序树的查找算法
若二叉排序树为空，则查找不成功；
否则，
1）若给定值等于根结点的关键字，则查找成功；
2）若给定值小于根结点的关键字，则继续在左子树上进行查找；
3）若给定值大于根结点的关键字，则继续在右子树上进行查找。
Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) {// 在根指针 T 所指二叉排序树中递归地查找其关键字等于 key 的数据元素，若查找//成功，则返回指针 p 指向该数据元素的结点，并返回函数值为 TRUE;否则表明//查找不成功，返回指针 p 指向查找路径上访问的最后一个结点，并返回函数值为// FALSE, 指针 f 指向当前访问的结点的双亲，其初始调用值为NULL。if (!T) { p = f; return FALSE; } // 查找不成功else if ( EQ(key, T->data.key) ) { p = T; return TRUE; } // 查找成功 else if ( LT(key, T->data.key) ) SearchBST (T->lchild, key, T, p ); // 在左子树中继续查找 else SearchBST (T->rchild, key, T, p ); // 在右子树中继续查找} // SearchBST4、二叉排序树的插入算法
根据动态查找表的定义，“插入”操作在查找不成功时才进行；
若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。
Status Insert BST(BiTree &T, ElemType e ) { // 当二叉排序树中不存在关键字等于 e.key 的数据元素时，插入元素值为 e 的结点，并返回 TRUE; 否则，不进行插入并返回FALSE。 if (!SearchBST ( T, e.key, NULL, p )) { s = (BiTree) malloc (sizeof (BiTNode)); // 为新结点分配空间 s->data = e; s->lchild = s->rchild = NULL; if ( !p ) T = s; // 插入 s 为新的根结点 else if ( LT(e.key, p->data.key) ) p->lchild = s; // 插入 *s 为 *p 的左孩子 else p->rchild = s; // 插入 *s 为 *p 的右孩子 return TRUE; // 插入成功 } else return FALSE;} // Insert BST5、二叉排序树的删除算法和插入相反，删除是在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。
可分三种情况讨论：
（1）被删除的结点是叶子结点；
（2）被删除的结点只有左子树或者只有右子树；
（3）被删除的结点既有左子树，也有右子树。
Status DeleteBST (BiTree &T, KeyType key ) {// 若二叉排序树 T 中存在其关键字等于 key 的数据元素，则删除该数据元素// 结点，并返回函数值 TRUE，否则返回函数值 FALSE。 if (!T) return FALSE; // 不存在关键字等于key的数据元素 else { if ( EQ (key, T->data.key) ) Delete (T); // 找到关键字等于key的元素 else if ( LT (key, T->data.key) ) DeleteBST ( T->lchild, key ); // 继续在左子树中进行查找 else DeleteBST ( T->rchild, key ); // 继续在右子树中进行查找 return TRUE; } } // DeleteBST6、二叉排序树的查找性能分析
对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。
例如：由关键字序列 1，2，3，4，5构造而得的
二叉排序树，ASL =（1+2+3+4+5）/ 5 = 3
由关键字序列 3，1，2，5，4构造而得的二叉排序树，
ASL =（1+2+3+2+3）/ 5
= 2.2
在等概率的情况下，二叉排序树的平均查找长度为
$$
P(n)=2 \frac{n+1}{n} \log n+C
$$
9.6.1 例题
- 已知关键字序列（20，13，1，5，3， 8，30），
试构造二叉排序树并且进行中序遍历。
中序遍历结果1，3，5，8，13，20，30 - 二叉排序树上结点的关键字的值有可能相同。（ X ）
- 对二叉排序树进行先右后左的中序遍历可以得到
关键字的降序排列。（√）
9.7 平衡二叉树
内容：介绍平衡二叉树的定义和构造。
9.7.1 平衡因子
二叉树上结点的平衡因子定义为：该结点的左子树的深度减去右子树的深度。
平衡二叉树首先是二叉排序树，它是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1 。或者说平衡二叉树上每个结点的平衡因子的绝对值都小于等于1。
9.7.2 构造平衡二叉树的步骤：
1、按照构造二叉排序树的方式逐个添加结点。
2、每当添加一个结点，就要判断当前二叉树是否平衡。
3、如果当前二叉树平衡，则继续添加结点。
4、如果当前二叉树不平衡，先要找出最小不平衡子树，再判断最小不平衡子树中结点的数目；如果结点的数目为3，直接重构；如果结点的数目大于3，则按照LL、RR、LR、RL型重构，重构时最小不平衡子树以加粗部分为根。
9.7.3 平衡二叉树的查找性能分析
由此推得，深度为 $h $的平衡二叉树中所含结点的最小值$N_{h}=\varphi^{h+2} / \sqrt{5}-1$。
反之，含有$ n$ 个结点的平衡二叉树能达到的最大深度$h_{n}=\log _{\varphi}(\sqrt{5}(\mathrm{n}+1))-2$。
因此，在平衡二叉树上进行查找时，
查找过程中和给定值进行比较的关键字的个数和$ log(n) $相当。
9.7.4 例题
- 深度为5的平衡二叉树的结点数至少有 12 个。
- 平衡二叉树中，若某个结点的左右孩子的平衡因子为零，则该结点的平衡因子一定是零。（x)
- 一棵深度为K的平衡二叉树，所有结点的平衡因子都为0，则该树共有______ 个结点。 ( 2k-1 )
- 平衡二叉树一定是二叉排序树（√）
- 按顺序输入一组关键字序列(50，60，70，30，20，10)，画出其构成的平衡二叉树，给出过程。
9.8 B_树
B_树是一种平衡的多路查找树
（1）多叉树的特性：
在 m 阶的B-树上，每个非终端结点可能含有：
n 个关键字 Ki（1≤ i≤n） n<m
n+1 个指向子树的指针 Ai（0≤i≤n）
（2）查找树的特性：
非叶结点中的多个关键字均自小至大有序排列，即：K1< K2 < … < Kn ；
Ai-1 所指子树上所有关键字均小于Ki ；
Ai 所指子树上所有关键字均大于Ki 。
（3）平衡树的特性：
树中所有叶子结点均不带信息，且在树中的同一层次上；
根结点或为叶子结点，或至少含有两棵子树；
其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树。
9.8.1 B_树中关键字的查找过程
从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程交叉进行。
若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找不成功，则返回插入位置。
在查找不成功之后，需进行插入。
显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况：
1）插入后，该结点的关键字个数n<m，不修改指针;
2）插入后，该结点的关键字个数 n=m，则需进行“结点分裂”，
3）若双亲为空，则建新的根结点。
4、B_树中删除关键字的过程
和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于$\lceil m/2 \rceil-1$，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。
9.8.2 B_树查找性能分析
在含 N 个关键字的 B-树上进行一次查找，需访问的结点个数不超过：$\log _{m / 2}((N+1) / 2)+1$
9.8.3 例题
- 一棵m阶B_树的非终端结点至少有______个关键字。( $\lceil m/2 \rceil-1$ )
- 已知3阶B_树结构如下图所示，当插入元素“80” 时，调整后新的根元素是_______。 60
- 一棵3阶B_树中含有2047个关键字，包含叶子结点层，该树的最大深度为（ B ）。
第 H+1 层为叶子结点，而当前树中含有 N 个关键字，则叶子结点必为 N+1 个，$H \leq \log _{\lceil m / 2 \rceil}((N+1) / 2)+1$A. 11 B. 12 C. 13 D. 14 - 一棵8阶的B-树，除根之外的所有非终端结点中最多有7个关键字，最少有4个关键字。（ X ）
9.9 哈希表
表示查找表的静态和动态结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系。
查找的过程为给定值依次和关键字集合中各个关键字进行比较，
查找的效率取决于和给定值进行比较的关键字个数。
用这类方法表示的查找表，其平均查找长度ASL都不为零。
不同表示方法的差别仅在于：关键字和给定值进行比较的顺序不同。
对于频繁使用的查找表，希望 ASL = 0。
只有一个办法：预先知道所查关键字在表中的位置，即要求记录在表中位置和其关键字之间存在一种确定的关系。
但是，对于动态查找表而言，
- 表长不确定；
- 在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。
因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。
9.9.1 例题
- 哈希表的平均查找长度一定大于零。（ X ）
- 哈希表建立了关键字和存储地址之间的映射。（ √ ）
- 哈希表一定是一个压缩映像。（ X ）
- 哈希表的冲突指的是关键字不同而相应的哈希地址却相同。（ √ ）
- 构造哈希表，除了需要选择一个尽可能少产生冲突的哈希函数之外，还需要找到一种处理冲突的方法。（ √ ）
9.9.2 哈希表处理冲突的方法
内容：介绍哈希表处理冲突的方法，包括开放定址法和链地址法。
9.9.2.1 开放定址法
- 线性探测再散列
- 平方探测再散列
- 随机探测再散列
9.9.2.2 链地址法
10. 排序（未完）
10.1直接插入排序
10.1.1原理
把无序序列的第一个插入有序序列中，使无序序列的个数减1，有序序列的个数增1。
10.1.2 插入排序的步骤
- 在R[1…i-1]中查找R[i]的插入位置（利用“顺序查找”实现，从后往前找），R[1…j].key<=R[i].key<R[j+1…i-1].key
- 将R[j+1…i-1]中的所有记录均后移一个位置
- 将R[i]插入到R[j+1]的位置上
void InsertSort(SqList &L){//对顺序表L作直接插入排序 for(int i=2;i<=L.length;i++) if(L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; //复制为监视哨 for(j=i-2;L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j]; //记录后移 L.r[j+1]=L.r[0]; //插入到正确位置 }}10.1.3时间性能
内部排序的时间分析
实现内部排序的基本操作有两个：
1.”比较“两个关键字的大小
2.“移动”记录
算法复杂度：O（n²）
10.2快速排序
10.2.1原理
目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。
10.2.2 代码
int Partition(RedType R[],int low,int high){ R[0]=R[low]; pivotkey=R[low].key; while(low<high){ while(low<high&&R[high].key>=pivotkey) --high; R[low]=R[high]; while(low<high&&R[low].key<=pivotkey) ++low; R[high]=R[low]; } R[low]=R[0]; return low;}//当低子序列或高子序列的长度为1时，就不再进行递归排列了void QSort(RedType &R[],int s,int t){ //对记录序列R[s..t]进行快速排序 if(s<t){//长度大于1 pivotloc=Partition(R,s,t);//对R[s..t]进行一次划分 QSort(R,s,pivotloc-1);//对低子序列递归排序，pivotloc是枢轴位置 Qsort(R,pivotloc+1,t);//对高子序列递归排序 }}void QuickSort(SqList &L){ QSort(L.r,1,L.length);}10.2.3时间性能
- 时间复杂度: Tavg(n)<(b/a+2c)(n+1)ln(n+1)
- 结论：快速排序的时间复杂度为O（nln(n)）
- 若待排记录的初始状态按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O（n²），为避免出现这种情况，需要在一次划分之前进行预处理，需要在首尾中三个位置的值进行相互比较，然后取关键字为“三者之中”的记录为枢轴记录。
10.3 希尔排序
10.3.1原理
对待排序列先作“宏观”调整，再作“微观”调整。所谓”宏观“调整指的是跳跃式的进行插入排序。
R[1],R[1+d],R[1+2d],R[1+3d],R[1+4d],R[1+5d]…..R[1+kd]
R[2],R[2+d],R[2+2d],R[2+3d],R[2+4d],R[2+5d]…..R[2+kd]
…
R[d],R[2d],R[3d],R[4d],R[5d],R[6d]…..R[(k+1)d]
其中，d称为增量，一般是一个素数序列，它的值在排序过程中从大到小逐渐减小，直至最后一趟排序减为1。
如（…5,3,1)
10.3.2 代码
void ShellInsert(Sqlist &L,int dk){ for(int i=dk+1;i<=n;i++) if(L.r[i].key<L.r[i-dk].key){ L.r[0]=L.r[i]; //第i个记录暂存在R[0] for(int j=i-dk;j<0&&(L.r[0].key<L.r[j].key);j-=dk) L.r[j+dk]=L.r[j]; //记录后移，查找插入位置 L.r[j+dk]=L.r[0];//插入 }//if}void ShellSort(SqList &L,int dlta[],int t){ //增量为dlta[]的希尔排序 for(int k=0;k<t;++t) ShellInsert(L,dlta[k]); //一趟增量为dlta[k]的插入排序}10.5归并排序
10.5.1原理
归并排序的过程：
将两个或两个以上的有序子序列归并为1个有序序列。
10.5.2代码
void Merge(RcdType SR[],RcdType &TR[],int int m,int n){//将有序的记录序列SR[i...m]和SR[m+1...n]归并为有序的记录序列TR[i..n]for(int j=m+1,k=i;i<=m&&j<=n;++k){//将SR中记录由小到大地并入TR if(SR[i].key<=SR[j].key)TR[k]=SR[i++]; else TR[k]=SR[j++];} if(i<=m)TR[k..n]=SR[i..m];//将剩余的SR[i..m]复制到TR if(j<=n)TR[k..n]=SR[j..n];//将剩余的SR[j..n]复制到TR}//mergevoid Msort(RcdType SR[],RcdType &TR1[],int s,int t){ //将SR[s..t]归并排序为TR1[s..t] if(s==t)TR1[s]=SR[s]; else{ m=(s+t)/2;//将ST[s..t]平分成SR[s..m]和SR[m+1..t] Msort(SR,TR2,s,m);//递归地将SR[s..m]归并为有序的TR2[s..m] Msort(SR,TR2,m+1,t);//递归地将SR[m+1..t]归并为有序的TR2[m+1..t] Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1]归并到TR1[s..t] }}void MergeSort(SqList&L){ Msort(L.r,L.r,1,L.length);}1.5.3步骤
1.平分直到有序
2.相邻的两个序列排序
1.5.4时间性能
O（nlogn）
每一趟归并时间的复杂度为O（n），要进行log2n趟
9.6链式基数排序
9.6.1原理
基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。
9.6.2数字型基数排序
209,386,768,185,247,606,230,834,539
首先按“个位数”取值分别为0,1,….,9，“分配”成10组，之后按从0至9的顺序将他们“收集”在一起。
然后按其“十位数”取值分别为0,1,….,9，“分配”成10组，之后按从0至9的顺序将他们“收集”在一起。
最后按其“百位数”重复一遍上述操作
