自考数据结构_同步辅导串讲.doc

数据结构自学考试同步辅导

----------------------------------------------------主讲:欧增桂

第一章 概论—考点精析
一,基本概念和术语
1. 用计算机解决问题的实质是对数据的加工,处理.
2. 数据是信息的载体,它能够被计算机识别,存储和加工处理.
3.数据元素是数据的基本单位.有时一个数据元素包括若干个数据项.
第一章 概论—考点精析
4. 编程序使计算机对机内表示的数据进行操作,得到所需的结果,这项工作称为数据处理.
5. 数据结构指的是数据之间的逻辑关系,也称为数据的逻辑结构.包括线性结构和非线性结构两大类.
6. 数据元素及其关系在计算机存储器内的表示,称为数据的存储结构.
第一章 概论—考点精析
(1)存储实现
存储实现的基本目标是建立数据的机内表示
存储结构主要内容:使用一个存储结点来存储一个数据元素;建立各存储结点之间的关联来表示数据元素之间的逻辑关系.
存储结点:一个数据元素在存储结构中的存储
第一章 概论—考点精析
(2)结点之间有如下四种存储方式:
顺序存储方式:每个存储结点只含一个数据元素.所有的存储结点相继存储在一个连续的存储区内,用存储结点间的位置关系表示数据之间的逻辑关系.—随机存取
链接存储方式:每一个存储结点不仅含一个数据元素,还包括指针.每一个指针指向一个与本结点有逻辑关系的结点,即用指针表示逻辑关系.—顺序存取
第一章 概论—考点精析
索引存储方式:每一个存储结点仅含一个数据元素,所有存储结点都连续存放,仅增加一个索引表.通过关键字直接存取
稠密索引表:每个结点在索引表中都有一个索引项.给出结点地址.
稀疏索引表:一组结点在索引表中仅对应一个索引项.给出该组结点的起始位置.
第一章 概论—考点精析
散列存储方式:每一个存储结点仅含一个数据元素,数据元素按散列(Hash)函数确定存储位置.—通过对关键字的计算映射.
第一章 概论—考点精析
7. 数据类型是一个值的集合以及在这些值上定义的一组操作的总称.
数据类型按其值能否分解,通常可分为原子(简单)类型和结构类型两种类型.
抽象数据类型
(Abstract Data Type,ADT):由一组数据结构和在该组数据结构上的一组操作组成.
抽象数据类型在C++中是通过类来描述的
第一章 概论—考点精析
二,学习数据结构的意义
1. 算法+数据结构=程序
2. 解决问题的一个关键步骤是选择合适的数据结构表示该问题,然后才能写出有效的算法.
三,运算的描述
1. 数据的运算是通过算法描述的,所以讨论算法是数据结构课程的重要内容之一.
第一章 概论—考点精析
2. 选用算法要考虑正确性,执行算法所需时间和存储空间,同时算法应易于理解,编码,调试等.在结构中:
(1) 查找运算:找出满足条件的结点的位置
(2) 读取运算:读出结构中指定位置上的内容
(3) 插入运算:在指定位置上增加一个新结点
(4) 删除运算:撤消指定位置上的结点
(5) 更新运算:修改指定结点的内容
第一章 概论—考点精析
四,运算的实现
运算实现是在确定的存储结构下,用计算机语言描述实现某种操作的算法,成为运算实现,这是数据结构的主要内容.
类C语言进行算法描述
第一章 概论—考点精析
五,算法的分析
1. 包括时间和空间两个方面进行分析:时间复杂度和空间复杂度
2. 时间复杂度从好到坏的级别依次是:
常量阶O(1),对数阶O(log2n),线性阶O(n), 优化的平方阶O(n*log2n),平方阶O(N2),立方阶O(n3),指数阶O(2),阶乘阶O(n!)
第二章 线性表—考点精析
一,线性表的逻辑结构—了解以下概念和术语:
线性表:n(n≥0)个结点组成的有限序列
线性结构中的元素是有序的
元素个数可以为0 — 空表
元素的个数是有限的
同一线性表中的元素的类型,长度相同.
第二章 线性表—考点精析
2. 非空的线性结构有以下特点:
只有一个排在第一个的元素,称为线性结构的起始元素.
只有一个排在最后的元素,称为线性结构的终端元素.
除起始元素外,线性结构的其它元素,仅有一个直接前驱.
除终端元素外,线性结构的其它元素,仅有一个直接后继.
第二章 线性表—考点精析
3. 线性结构的逻辑表示如下:
L1=() L1是一个空的线性结构;
L2=(a,b,c,d,e) L2线性结构中有5个元素,a是起始元素,e是终端元素,c的直接前驱元素是b,c的直接后继元素是d,a元素的序号是1,c元素的序号是3.
第二章 线性表—考点精析
4. 线性表的长度:线性表中元素的个数
L1=() L1线性表的长度为零
L2=(a,b,c,d,e) L2线性表的长度为5
第二章 线性表—考点精析
5. 线性表的基本运算包括(函数的结果值):
InitList(L) 初始化,创建一个空表L
ListLength(L) 求线性表L的长度
GetNode(L,i) 读取表L的第i个元素
LocateNode(L,X) 查找定位元素X的位置
InsertList(L,X,i) 将X插入到表L的第i个位置
DeleteList(L,i)
将表中第i个位置上的元素删除
第二章 线性表—考点精析
二,线性表的顺序存储结构
(一) 概念和术语
顺序表:将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元中,采用这种方式存储的线性表称为顺序表.
在算法中,顺序表的存储形式是数组
顺序表—随机存取方式
第二章 线性表—考点精析
(二) 顺序表的运算
InitList(L)
初始化,创建一个长度为 maxsize的空表L (固定长度) L.last=0
第二章 线性表—考点精析
(5)插入运算
void InsertList(SeqList *L,DataType x,int i)
{ int j; ‖ 将新结点x插入到L指向的第i个位置
if(iL length+1)
Error("position error");‖ 位置错return 0
if(L length>=ListSize)
Error("overflow"); ‖ 空间溢出
第二章 线性表—考点精析
for(j=L length-1;j>=i-1;j--)
L data[j+1]= L data[j]; ‖ 结点后移
L data[i-1]=x; ‖ 插入x
L length++; ‖ 表长加1
}
第二章 线性表—考点精析
(6)删除运算
void DeleteList(SeqList *L,int i)
{ int j; ‖ 从L指向的表中删除的第i个结点
if(iL length+1)
Error("position error"); ‖ 位置错return 0
for(j=i; jlength,L.size ,数组下标范围为0≤i≤length-1,例如: for(i=0;ilength;i++)
表元素的值data,item if(L.list[i]==data)
第二章 线性表—考点精析
三,线性表的链式存储结构
(一) 概念和术语
链表:按链式存储方式存储的线性表,分为单链表,循环链表,双链表.
链表中的元素顺序用结点中的指针给出,即用指针表示结点间的逻辑关系, 元素顺序与逻辑顺序一致.采用顺序存取方式.
3. 链表的长度是可变的
第二章 线性表—考点精析
4. 单链表:一个结点存放一个元素,结点包括存放元素值的数据域(data),指向下一个结点的指针域(next)
5. 循环链表:单链表的最后一个结点的指针指向表头结点.
6. 双链表:循环链表中的结点包含两个指针域,分别指向前驱结点和后继结点.
第二章 线性表—考点精析
单链表和循环链表的结点结构:
双链表的结点结构:
next
data
Rlink
data
Llink
第二章 线性表—考点精析
指针操作:p,q为指针
指针移动,遍历:p=p->next
将q指向的结点插入到p指向的结点之后: q->next =p->next; p->next=q;
q指向要删除的结点,p指向其前一个结点: p->next=q->next;
第二章 线性表—考点精析
(二) 链表的运算(单链表)
InitList(L) 初始化,创建一个空表L,L next==Null
第二章 线性表—考点精析
建立单链表的算法(头插入法)
LinkList CreatListF(void)
{ char ch;
LinkList head; ‖ 头指针
ListNode *s; ‖ 工作指针
head=NULL; ‖ 链表开始为空
ch=getchar();
第二章 线性表—考点精析
while(ch!='\n') ‖ 生成新结点
{ s=(ListNode *)malloc(sizeof(ListNode))
s data= ch;
s next=head; ‖ 第一次为NULL,以后使其指向插入前的第一个结点
head=s; ‖ 使head指向新结点
ch=getchar();}
return head; ‖ 返回头指针
}
第二章 线性表—考点精析
在有头结点链表中查找一个结点(按值查找)
ListNode * LocateNode
(LinkList head,DataType key)
{ ListNode *p=head next;
while(p && p data!=key)‖表为空或不等
p=p next; ‖ 扫描下一结点
return p; ‖ 若p=NULL,查找失败,否则
p指向找到的结点
}
第二章 线性表—考点精析
按输入的顺序建立单链表算法的时间复杂度为O(n).
建立有序单链表算法的时间复杂度为O(n2)
访问单链表的结点必须从表头指针开始
对于循环链表和双链表,从表中的任一结点出发,通过指针移动都能访问表结点.
链表的插入和删除只修改指针,不移动表元素.
第三章 栈和队列—考点精析
一,栈
(一) 栈的定义和基本运算—概念和术语
1. 栈:栈是限定仅在一端进行插入,删除的特殊线性表.
栈属于加了限定条件的线性结构
栈是后进先出的线性表
第三章 栈和队列—考点精析
(4) 进栈和出栈端称为栈顶,另一端称为栈底
(5) 栈中元素个数为0时为空栈.
(6) 栈中的元素个数为有限多个
(7) 同一个栈中的元素的类型,长度相同
新进栈的元素称为栈顶元素
第三章 栈和队列—考点精析
栈的基本运算包括:
InitStack(S) 初始化,创建空栈
Push(S,X) 进栈,X成为新的栈顶元素
Pop(S,X) 出栈,将栈顶元素删除,元素的值赋给X
StackTop(S,X) 读栈顶元素,不删除
StackEmpty(S) 判断是否空栈,空栈为1,否则为0
StackFull(S) 判断是否栈满,栈满为1,否则为0
第三章 栈和队列—考点精析
(二) 栈的顺序实现—概念和术语
(1) 顺序栈:栈的顺序存储结构
(2) 栈的顺序实现:使用一个数组data,栈底元素存放在data(0)中,top值为栈内元素个数及位置,空栈时top=-1
(3) 使用一个结构体变量表示一个栈元素:其中一个域为数组data,另一个为top
(4)使用指针变量S指向结构体:
S data S top
第三章 栈和队列—考点精析
2. 顺序存储栈的运算
3. 算法分析
Push(S,X) 的时间复杂度为O(1)
Pop(S,X)的时间复杂度为O(1)
判断栈满的条件:S->top==StackSize-1
判断栈空的条件:S->top==-1
第三章 栈和队列—考点精析
顺序存储进栈操作
void Push(SeqStack *S,DataType x)
{ if(StackFull(S))
Error("Stack overflow");//上溢
S data[++S top]=x;
}
第三章 栈和队列—考点精析
顺序存储退栈操作
DataType Pop(SeqStack *S)
{ if(StackEmpty(S))
Error("Stack underflow");//下溢
return S data[S top--];
}
第三章 栈和队列—考点精析
(三) 栈的链接实现—概念和术语
(1) 栈的链接实现:使用链表实现栈的存储
(2) 链栈:链表的首元素定为栈顶元素,尾元素为栈底.
第三章 栈和队列—考点精析
链栈进栈操作
void Push(linkStack *S,DataType x)
{ StackNode *p=
(StackNode *)malloc(sizeof(StackNode));
p data=x;
p next= S top;
S top=p;
}
第三章 栈和队列—考点精析
链栈退栈操作
DataType Pop(linkStack *S)
{ DataType x;
StackNode *p= S top;
if(StackEmpty(S))
Error("Stack underflow");
x=p data; S top= p next;
free(p); return x;
}
第三章 栈和队列—考点精析
二,队列
(一) 队列的定义及基本运算
1.队列:限定仅能在一端进队,另一端出队的特殊线性表
加限制的线性结构
先进先出表
第三章 栈和队列—考点精析
进队在队尾,出队在队首(头)
可以是空队
队列中的元素个数是有限的,可变的
元素的类型,长度相同
第三章 栈和队列—考点精析
队列的基本运算包括:
InitQueue(Q) 初始化,创建队列
EnQueue(Q,X) 进队,X成为新的队尾元素
Dequeue(Q,X) 出队,将队列头元素删除,元素的值赋给X.
QueueFront(Q,X) 读队列头元素,不删除
QueueEmpty(S) 判断是否空队列,空队为1,否则为0.
QueueFull(S) 判断是否队列满,队满为1,否则为0
第三章 栈和队列—考点精析
(二) 顺序队列
队列的顺序存储,也称循环队列
使用数组data存放队列元素,范围data[0]~data[maxsize-1]
使用结构体变量表示队列,四个域:
数组data,整形变量队头front,队尾rear,队中元素个数count
第三章 栈和队列—考点精析
(4) 用指针变量指向结构体:
sq data,sq front,sq rear,sq count
2.顺序队列运算
初始化
sq front=0,sq rear=0,sq count=0
sq data的maxsize=10
第三章 栈和队列—考点精析
(三) 链队列
使用链表存储队列
单链表有一个头指针,链队列还应该有一个尾指针
第三章 栈和队列—考点精析
进队算法(循环链表)
void EnQueue(CirQueue *Q,DataType x)
{ if(QueueFull(Q))
Error("Queue overflow"); ‖ 队满
Q count++; ‖ 队列元素个数加1
Q data[Q rear]=x; ‖ 新元素插入队尾
Q rear=(Q rear+1)%QueueSize;
} ‖ 队列尾指针加1
第三章 栈和队列—考点精析
出队算法(循环链表)
DataType DeQueue(CirQueue *Q)
{ DataType temp;
if(QueueEmpty(Q))
Error("Queue underflow"); ‖ 队空
temp= Q data[Q front];
Q count--; ‖ 队列元素个数减1
Q front=(Q front+1) %QueueSize;
return temp;
}
第四章 串—考点精析
一,串的基本概念
串(string):零个或多个字符组成的有限序列.如:S="a1a2a3a4……an"
空串(Empty String):长度为零的串
空白串(Blank String):空格组成的串
子串:模式串,主串:目标串
模式匹配:子串定位,串匹配
第四章 串—考点精析
6. 对于某一个i,0 i n-m,将目标串的子串T[i..i+m-1]和模式串P[0..m-1]进行比较,若相等,则称匹配成功
7. 位置i 称为位移
第四章 串—考点精析
8. 有效位移:匹配成功
9. 无效位移:匹配失败
例:设T[0..n-1]="adaabaabcaabaa",P=[0..m-1]="aab",其有效位移是:
T[2..4]=P[0..2]
T[5..7]=P[0..2]
T[9..11]=P[0..2]
第四章 串—考点精析
二,串的运算
Length(S) 求串长
int strlen(char *s);
2. Copy(S1,S2) 将串S2复制到S1中
char *strcpy(char * to,char * from);
3. Concatenation(S1,S2) 连接,将S2复制到S1的末尾
char * strcat(char * to,char *from);
第四章 串—考点精析
4. Compare(S1,S2) 比较串S1和S2的大小
int strcmp(char *s1,char *s2);
5. Index(S,c) 定位c在S中的位置,不在S中时返回NULL
char * stechr(char *s,char c);
6. substr(char *s,int i,int j);
从串S中第i个位置开始取j个字符
第四章 串—考点精析
三,串的存储结构
(一) 串的顺序存储
1.静态存储分配:直接使用定长字符数组
2.动态存储分配:动态分配,释放字符数组
(二) 串的链式存储
用单链表存储串,便于顺序串的插入,删除
第四章 串—考点精析
(三) 串的子串定位运算(模式匹配或串匹配)
1.顺序串
int NaiveStrMatch
(SeqString T,SeqString P)
{ int i,j,k;
int m=P.length;
int n=T.length;
第四章 串—考点精析
for(i=0;i<=n-m;i++)
{ j=0;k=i;
while(j<M&&T.CH[K]==P.CH[J]
{ k++;j++; } ‖ 判定是否有效位移
if(j==m)
return i; ‖ 匹配成功
}
return –1; ‖ 匹配失败
}
第四章 串—考点精析
2.链式串
LinkStrNode * LinkStrMatch
(LinkString T,LinkString P)
{ LinkStrNode * shift,*t,*p;
shift=T; ‖ shift表示位移
t=shift; p=P;
第四章 串—考点精析
while(t&&p)
{ if(t data==p data)
{ t=t next; p=p next; }
else { ‖ 确定shift为无效位移
shift=shift next; ‖ 右移,继续
t=shift; p=P; }
}
第四章 串—考点精析
if(p==NULL)
return shift ‖ 匹配成功
else
return NULL; ‖ 匹配失败
}
第五章 多维数组和广义表—考点精析
多维数组
行优先顺序存储
在数组A[m][n]中,计算元素A[i][j]的地址:A[0][0]的地址加上位移量 (i*n+j)*d
对于三维数组A[m][n][p] ,计算元素A[i][j][k]的地址: A[0][0][0]的地址加上位移量 (i*n*p+j*p+k)*d
第五章 多维数组和广义表—考点精析
当数组下界为1时,在数组A[m][n]中,计算元素A[i][j]的地址: A[1][1]的地址加上位移量 [(i-1)*n+(j-1)]*d
对于三维数组A[m][n][p] ,计算元素A[i][j][k]的地址: A[1][1][1]的地址加上位移量 [(i-1)*n*p+(j-1)*p+(k-1)]*d
第五章 多维数组和广义表—考点精析
2. 列优先顺序存储
在数组A[m][n]中,计算元素A[i][j]的地址:A[0][0]的地址加上位移量 j*m+i
对于三维数组A[m][n][p] ,计算元素A[i][j][k]的地址: A[0][0][0]的地址加上位移量 (k*m*n+j*m+i)*d
第五章 多维数组和广义表—考点精析
当数组下界为1时,在数组A[m][n]中,计算元素A[i][j]的地址: A[1][1]的地址加上位移量 [(j-1)*m+(i-1)]*d
对于三维数组A[m][n][p] ,计算元素A[i][j][k]的地址: A[1][1][1]的地址加上位移量 [(k-1)*m*n+(j-1)*n+(i-1)]*d
第五章 多维数组和广义表—考点精析
一,基本概念
特殊矩阵:非零元素和零元素有一定规律
对称矩阵,三角矩阵,对角矩阵
2. 稀疏矩阵:非零元素远少于矩阵元素总和
3. 广义表:是n个元素a1a2a3……an的有限序列,其中ai或者是一个原子;或者是一个广义表
第五章 多维数组和广义表—考点精析
二,矩阵的压缩存储
特殊矩阵的存储
对称矩阵:只存储上三角或下三角的元素
三角矩阵:常数共享一个存储空间
对角矩阵:零元素存储到一个存储空间
第五章 多维数组和广义表—考点精析
2. 稀疏矩阵
三元组表:对于矩阵Amn中的每一个非零元素,对应的三元组为(i,j,Aij)
带行表的三元组表:加入一个行表,记录每行非零元素在三元组表中的起始位置
第五章 多维数组和广义表—考点精析
仅考虑非零元素
存储非零元素的行号,列号及元素值构成的三元组(i,j,aij).
三元组线性表—把所有的三元组按行号为主序(主关键字),列号为辅序(次关键字)进行排列.例如:
((1,1,3),(1,4,5),(2,3,-2), (3,1,1), (3,3,4), (3,5,6),(5,3,-1))
稀疏矩阵的存储结构
稀疏矩阵的顺序存储类型定义:
struct SMatrix
{ int m,n,t;
‖行,列,元素值
Triple sm [MaxTerms+1]
}
‖s[0]不用,下标范围
1~MaxTerms
6
5
3
1
1
3
5
4
1
-1
3
5
4
3
3
-2
3
2
3
1
1
row col val
下标
1
2
3
4
5
6
7
┇
MaxTerms
第五章 多维数组和广义表—考点精析
用三元组表示的矩阵转置
void TransMatrix
(TriTupleTable *b,TriTupleTable *a)
{ int p,q,col;
b m=a n; b n=a m; b t=a t;
if(b t<=0)
Error("A=0");
q=0;
第五章 多维数组和广义表—考点精析
for(col=0; col for(p=0; p0)结点的完全二叉树的深度为 [log2(n+1)」或「log2n]+1
性质5:对完全二叉树中编号为i的结点 (1≤ i ≤ n,n ≥ 1,n为结点数)有:
(1) 若i ≤ [n/2],即2i ≤ n,则编号为i的结点为分支结点,否则为叶子结点.
第六章 树—考点精析
(2) 若n为奇数,则每个分支结点都既有左孩子,又有右孩子;
(3) 若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子,没有右孩子,其余分支结点左,右孩子都有.
(4)若编号为i的结点有左孩子,则左孩子结点的编号为2i;若编号为i的结点有右孩子,则右孩子结点的编号为2i+1.
第六章 树—考点精析
(5)除树根结点外,若一个结点的编号为i,则它的双亲结点的编号为[i/2],也就是说:
当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子.
当i为奇数时,其双亲结点编号为(i-1)/2,它是双亲结点的右孩子.
第六章 树—考点精析
二,二叉树的存储结构
顺序存储结构:按完全二叉树的形式,从上层开始,每层从左到右存储
链式存储结构:
结点的链结构:
Lchild data Rchild
第六章 树—考点精析
三,二叉树的遍历
先序遍历,先根遍历
访问根结点,遍历左子树,遍历右子树
中序遍历
后序遍历
按层遍历
算法有递归方式和非递归方式两种
第六章 树—考点精析
中序遍历二叉树的递归算法(二叉链表存储)
void Inorder(binTree T)
{ if(T)
{ Inorder(T lchild); ‖ 遍历左子树
printf("%C",T data); ‖访问根结点
Inorder(T rchild); ‖ 遍历右子树
}
}
第六章 树—考点精析
构造二叉树(二叉链表存储)
void CreatBinTree(binTree *T)
{ char ch;
if((ch=getchar())==' ')
*T=NULL;
else
第六章 树—考点精析
{ *T=(BinTNode *)
malloc(sizeof(BinTNode));
(*T) data=ch;
CreatBinTree(binTree *T)
CreatBinTree(binTree *T)
}
}
第六章 树—考点精析
1.前序遍历—A,B,C,D,E,F,G
2.中序遍历—C,B,D,A,E,G,F
3.后序遍历—C,D,B,G,F,E,A
4.按层遍历—A,B,E,C,D,F,G
A
C
D
F
G
E
B
第六章 树—考点精析
四,二叉树的线索化
线索链表结点结构为:
ltag=0:lchild是指向结点左孩子的指针
ltag=1:lchild是指向结点前驱的左线索
rtag=0:rchild是指向结点右孩子的指针
rtag=1:rchild是指向结点后继的右线索
lchild ltag data rtag rchild
第六章 树—考点精析
中序前驱—中序序列中的结点的前驱
中序后继—中序序列中的结点的后继
线索—在结点的空指针域中存放的该结点在某次遍历次序下的前驱结点或后继结点的指针称为线索.
左线索—前驱线索
右线索—后继线索
第六章 树—考点精析
线索化—遍历再加线索的过程
线索二叉树—线索化的二叉树
中序线索二叉树查找结点后继的规律是:
树中所有叶子结点的右链是线索,非叶子结点的右链均为指针.
无法直接得到后继信息,其后继为遍历右子树时访问的第一个结点,即右子树中最左下的结点.
第六章 树—考点精析
中序线索二叉树查找结点前驱的规律是:
若其左标志为1,则左链为指示其前驱的线索;否则其前驱为遍历左子树时最后访问的一个结点.
第六章 树—考点精析
二叉树的中序线索化
void InorderThreading(BinThree p)
{ if(p) ‖p非空时访问结点*p
{ InorderThreading(p lchild);
p ltag=(p lchild) Link:Thread;
p rtag=(p rchild) Link:Thread;
第六章 树—考点精析
if(pre) ‖若p的前驱结点*p存在
{ if(pre rtag==Thread)
pre rchild==p;
if(pre ltag==Thread)
pre lchild==pre; }
pre=p;
InorderThreading(p rchild);
}
*p的前驱为右(左)线索,令*pre的右(左)线索指向中序后继(前驱)
查找中序后继结点算法
BinThrNode * InordSu (BinThrNode * p)
{ BinThrNode *q;
if(p rtag==Thread)
return p rchild;
else
{ q= p rchild;
while(q ltag==Link)
q= q lchild;
return q;
}}
*p的左子树为空,返回右线索所指的中序后继
从*p的右孩子开始,左子树为空,沿左链查找最左下结点.
第六章 树—考点精析
五,树,森林与二叉树的转换
树,森林与二叉树之间存在一一对应关系
1.树 二叉树
(1) 先在所有兄弟结点之间加一连线
(2) 对于每一结点,保留与其长子连线,其余去掉.
第六章 树—考点精析
2.森林 二叉树
(1) 先将森林中的每一棵树变成二叉树
(2) 将二叉树的根结点作为兄弟,从左到右连接
第六章 树—考点精析
六,树的存储结构
1. 双亲链表
2. 孩子链表
3. 孩子兄弟链表
双亲链表表示法
#define MaxTreeSize 100
typedef char DataType;
Typedef struct
{ DataType data; ‖ 结点数据
int parent; ‖双亲指针
}PTreeNode;
Typedef struct
{ PTreeNode nodes[MaxTreeSize];
int n; ‖结点总数
}Ptree;
Ptree T; ‖ T是双亲链表
第六章 树—考点精析
七,树和森林的遍历
仅考虑树和森林的前序遍历和后序遍历
第六章 树—考点精析
八,哈夫曼树—最优二叉树
n个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的树.
权值最大的叶子结点离根越近的二叉树.
满二叉树或完全二叉树不一定是最优二叉树.
第六章 树—考点精析
构造过程
选取权值最小的两个结点,将其权值想加,作为这两个结点的父结点
在包括新形成的结点在内的其余结点中选取权值最小的两个结点,继续上述操作,直到生成根结点.
2. 哈夫曼树的存储结构
3. 哈夫曼编码—最优二叉树中左孩子为0,右孩子为1,叶子结点路径的编码.
第七章 图—考点精析
一,基本概念
图:G=(V,E)
V是顶点的非空有穷集合
E是称为边的顶点序偶对的集合
图G的子图:V'是V的子集,E'是E的子集,且E'中的边关联的顶点均在V'中,则G'=(V',E')是G的子图
第七章 图—考点精析
1. 有向图:图G中的每条边都是有方向的
有向边也称为弧,是有两个顶点组成的有序对
有向图的顶点集表示为:{V1,V2,V3,V4,……}
边集表示为:{, , , , ,……}
有向完全图:有n*(n-1)条边的有向图
第七章 图—考点精析
2. 无向图:图G中的每条边都是无方向的
无向完全图:有n*(n-1)/2条边的无向图
无向图的顶点集表示为:{V1,V2,V3,V4,……}
边集表示为:{(V1,V2),(V1,V3),(V1,V4), (V2,V3),(V3,V4),……}
称边(Vi,Vj)的顶点Vi和Vj互为邻接点(相邻接,相关联),边(Vi,Vj)依附或关联于顶点Vi和Vj
第七章 图—考点精析
3. 度
无向图中,顶点v的度(Degreee)是关联于该顶点的边的数目,记为D(v).
有向图中,以顶点v为终点的边的数目,称为v的入度;以顶点v为始点的边的数目,称为v的出度;顶点v的度为入度与出度之和.
第七章 图—考点精析
4. 路径:在无向图G中,若存在一个顶点序列, Vp,Vi1,Vi2,……Vim,Vq使得无向边 (Vp,Vi1),(Vi1,Vi2),……(Vim,Vq)均属于E(G),则称顶点Vp到Vq存在一条路径.
路径中边的数目称为路径长度
除Vp和Vq外,其余顶点均不相同,称其为简单路径.
第七章 图—考点精析
5. 有根图:图G中若存在一个顶点v,从v出发有路径可以到达图中其它所有顶点,则称此有向图为有根图,v称为图的根.
第七章 图—考点精析
6. 连通图:任意两个顶点之间都有路径
连通分量:无向图G的极大连通子图称为G的连通分量.
一个连通图的连通分量等于这个连通图
非连通图有多个连通分量
无向图—连通图
有向图—强连通图—双向连通
第七章 图—考点精析
具有n个顶点的无向连通图至少有n-1条边,最多有n*(n-1)/2条边.
具有n个顶点的有向连通图至少有n条边
第七章 图—考点精析
二,图的存储结构
邻接矩阵(Adjacencency Matrix):表示顶点之间关系的矩阵.
设 G=(V,E) 是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:
1 若(vi,vj)或是E(G)中的边
A[i,j]=
0 若(vi,vj)或不是E(G)中的边
第七章 图—考点精析
2. 邻接表:从某一顶点出发到达其它顶点的路径构成一个链表,包括顶点表和边表.类似于树的孩子链表表示法.
第七章 图—考点精析
三,图的遍历
深度优先遍历DFS:首先访问出发点v,标记为已访问,然后依次访问v的邻接点w,若w未被访问过,以w为新的出发点,继续前面的操作…….
第七章 图—考点精析
void DFSTraverse(ALGraph *G)
{ int i;
for(i=0;i
visited[i]=FALSE;
for(i=0;i
if(! visited[i])
DFS(G,i);
}
深度优先遍历以邻接表表示的图G
Vi未被访问过,以Vi为源点开始DFS搜索
void DFS(ALFraph *G,int i)
{ EdgeNode *p;
printf("%c", G adjlist[i].vertex);
visited[i]=TRUE;
p= G adjlist[i].firstedge;
while(p)
{ if(! visited[p adjvex])
DFS(G, p adjvex);
p= p next;
}
}
以Vi为出发点的对邻接表表示的图G进行深度优先搜索
第七章 图—考点精析
2. 广度优先遍历BFS:首先访问出发点v,接着依次访问v的所有邻接点wi,然后依次访问与wi邻接的所有未被访问的邻接点,继续……
第七章 图—考点精析
四,生成树和最小生成树
1.生成树
(1) 深度优先搜索得到深度优先生成树
(2) 广度优先搜索得到广度优先生成树
第七章 图—考点精析
2. 最小生成树
带权连通图(网络)的生成树中,各边的权值的和称为生成树的权,权值最小的树称为最小生成树MST.
轻边:具有最小权值的边
第七章 图—考点精析
MST性质:设G=(V,E)是一个网络,U是顶点V的一个真子集,对于边(u,v),若u U;v V-U,且为轻边,则边(u,v)在一棵最小生成树中.
第七章 图—考点精析
普里姆(Prim)算法
当前形成的MST始终是一棵树,按长度递