数据结构(C语言描述)-课件

数据结构辅导课程内容框架数据结构基础数据结构应用数据结构栈队列线性表线性结构非线性结构串查找内部排序外部排序文件动态存管理储数组广义表树二叉树图2PPT课件基本概念1.2基本概念和术语数据、数据元素、数据项、数据对象结构 *集合：松散的关系 *线性结构：一对一的关系 *树形结构：一对多的关系 *网状结构：多对多的关系数据结构

Data_Structure=（D，S）3PPT课件数据结构的分类1.2基本概念和术语（续）逻辑结构： 数据元素之间的逻辑关系（本来的关系）存储结构： 数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。

分类： *顺序存储结构 *链式存储结构

描述方式： 用高级语言中的“数据类型”来描述4PPT课件算法1.3算法和算法分析内涵:

是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性: *有穷性：有穷步+有穷时间/每一步 *确定性：指令的语义无二义性 *可行性：算法能用基本操作完成 *输入：零个或多个输入 *输出：一个或多个输出5PPT课件算法设计的要求1.3算法和算法分析（续）正确性（Correctness）可读性（Readablity）健壮性（Robustness）高时间效率与低存储量需求6PPT课件算法时间效率的度量1.3算法和算法分析（续）算法时间效率度量的基本做法

在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。 一般而言，这个基本操作是最深层循环内的语句中的原操作。算法时间复杂度

T(n)=O(f(n))称为算法的渐近时间复杂度，简称时间复杂度。7PPT课件算法存储空间的度量1.3算法和算法分析（续）算法存储空间度量的基本做法

用程序执行中需要的辅助空间的消耗作为存储空间度量的依据，是问题规模n的函数。而程序执行中本身需要的工作单元不能算。算法空间复杂度

S(n)=O(f(n))称为算法的空间复杂度。8PPT课件2.线性表3.栈、队列和串第一部分线性数据结构9PPT课件线性数据结构的特点2.1线性表的逻辑结构在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个之外，集合中的每一个数据元素均只有一个前驱；除最后一个之外，集合中每一个数据元素均只有一个后继。10PPT课件基本概念和术语2.1线性表的逻辑结构（续）线性表：n个数据元素的有限序列（线性表中的数据元素在不同环境下具体含义可以不同，但在同一线性表中的元素性质必须相同）。表长：线性表中元素的个数n(n>=0)。空表：n=0时的线性表称为空表。位序：非空表中数据元素ai

是此表的第i个元 素，则称i为ai

在线性表中的位序。11PPT课件线性表的抽象数据类型定义2.1线性表的逻辑结构（续）ADTList{

数据对象：D={ai|ai属于ElemSet,i=1,2,…,n,n>=0}

数据关系：R1={<ai-1,ai>|ai-1,ai属于D,i=2,3,…,n}

基本操作：

InitList(&L)

DestroyList(&L)

ClearList(&L)

ListLength(L)

GetElem(L,i,&e)

初始条件：L存在； 1<=i<=ListLength(L)

操作结果：用e返回L中第i个数据元素的值

} ADTListLocateElem(L,e,compare())

初始条件：L存在；compare()是判定条件

操作结果：返回第1个与e满足关系compare()的数据元素位序，若不存在，则返回0ListInsert(&L,i,e)

初始条件：L存在；1<=i<=ListLength(L)+1

操作结果：第i个位置之前插入元素e，长度加1ListDelete(&L,i,&e)

初始条件：L存在；非空；1<=i<=ListLength(L)

操作结果：删除第i个元素，e返回值，长度减1查找删除插入12PPT课件顺序表---线性表的顺序存储2.2线性表的顺序存储结构内涵： 线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。特点： *存储单元地址连续（需要一段连续空间） *逻辑上相邻的数据元素其物理位置也相邻 *随机存取 *存储密度为大（100%）13PPT课件顺序表的随机存取2.2线性表的顺序存储结构（续）对线性表L,设每个元素占k个存储单元，则有：递推关系：LOC(ai+1)=LOC(ai)+k任一元素ai+1的存储位置：

LOC(ai)=LOC(a1)+(i-1)*k(其中1<=i<=ListLength(L))a1a2…aiai+1…an…LOC(a1)LOC(ai+1)LOC(ai)LOC(an)LOC(a1)+(maxlen-1)*k空闲14PPT课件顺序表上插入运算的实现2.2线性表的顺序存储结构（续）（a1，…，ai,ai+1,…,an)表长为nStatusListInsert_Sq(SqList&L,inti,ElemTypee){

第一步：判断参数是否合法合理，否则出错；第二步：在物理空间中找到插入位置；第三步：插入前的准备工作;第四步：插入；}//ListInsert_SqListInsert(&L,i,e)（a1，…，ai-1,e，ai,…,an)表长为n+1a1a2…ai-1ai…an…a1a2…ai-1ai…an…e插入15PPT课件顺序表上删除运算的实现2.2线性表的顺序存储结构（续）（a1，…，ai,ai+1,…,an)表长为nStatusListDelete_Sq(SqList&L,inti,ElemType

&e){

第一步：判断参数是否合法合理，否则出错；第二步：在物理空间中找到删除位置；第三步：删除；第四步：删除后的善后工作}//ListDelete_SqListDelete(&L,i,&e)（a1，…，ai-1,ai+1,…,an)表长为n-1删除a1a2…ai-1ai+1…an…a1a2…ai-1ai…an…ai+116PPT课件顺序表优缺点分析2.3线性表的链式存储结构优点： *不需要额外空间来存储元素之间的关系 *可以随机存取任一元素可以通过使用动态数组数据类型来描述顺序表而改进这两个缺点缺点：*插入和删除运算需要移动大量元素*需要一段连续空间*预先分配足够大的空间*表的容量难以扩充17PPT课件链表---线性表的链式存储2.3线性表的链式存储结构（续）内涵： 线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其前驱和（或）后继之间的关系用指针来存储。这称为链表。术语： *结点 *数据域 *指针域 *头指针 *头结点分类： *单链表 *循环链表 *双向链表 *双向循环链表 *静态链表18PPT课件单链表2.3线性表的链式存储结构（续） 单链表中，如果每个结点中只包含一个指域，称这种链表为线性链表或单链表。 单链表可由头指针唯一确定。a2an^a1…LL^19PPT课件单链表的数据类型描述用高级语言中的指针类型描述线性表的链式存储//----------用结构指针描述------------typedef

struct

LNode{

ElemType data //数据域

struct

LNode *next //指针域}Lnode,*LinkList2.3线性表的链式存储结构（续）20PPT课件单链表上插入运算的实现2.3线性表的链式存储结构（续）（a1，…，ai,ai+1,…,an)表长为nListInsert(&L,i,e)（a1，…，ai-1,e，ai,…,an)表长为n+1插入ai-1ai…L…ai-1ai…L…e^sesS=(LinkList)malloc(sizeof(LNode))ps->next=p->next;p->next=s21PPT课件单链表上删除运算的实现2.3线性表的链式存储结构（续）删除q（a1，…，ai,ai+1,…,an)表长为nListDelete(&L,i,&e)（a1，…，ai-1,ai+1,…,an)表长为n-1free(q)ai-1ai…L…ai+1pp->next=p->next->nextai-1ai…L…ai+1p22PPT课件2.线性表3.栈、队列和串教学内容---第三章23PPT课件栈、队列和串是特殊的线性表3.1栈、队列和串的逻辑结构栈和队列是操作受限的线性表栈和队列的“操作受限”指操作位置受限串的特殊性在于线性表中数据元素只能是字符串一般以子串为操作单位栈、队列和串具有一般线性表共性的特点特殊的线性表反而应用面更宽24PPT课件栈的基本概念和术语3.1栈、队列和串的逻辑结构（续）栈（Stack）：限定仅在表尾进行插入或删除操作的线性表。栈顶（top）

：插入或删除的表尾端。栈底（bottom）

：表头端。空栈：空表。栈的操作特点：后进先出（LastInFirstOut---LIFO）25PPT课件栈的抽象数据类型定义3.1栈、队列和串的逻辑结构（续）ADTStack{

数据对象：D={ai|ai属于ElemSet,i=1,2,…,n,n>=0}

数据关系：R1={<ai-1,ai>|ai-1,ai属于D,i=2,3,…,n}//a1

为栈底，an

栈顶基本操作：

InitStack(&S)

DestroyStack(&S)

StackEmpty(S)

ClearStack(&S)

StackLength(S)

GetTop(S,&e)

初始条件：S存在,非空；

操作结果：用e返回S的栈顶元 素 Push(&S,e)

初始条件：S存在操作结果：插入元素e为新的栈顶元素，长度加 1Pop(&S,&e)

初始条件：S存在；非空操作结果：删除S的栈顶元素，e返回值，长度 减1}ADTStack出栈（删除）入栈（插入）26PPT课件队列的基本概念和术语3.1栈、队列和串的逻辑结构（续）队列（Queue）：限定仅在表的一端进行插入，而另一端进行删除操作的线性表。队尾（rear）

：允许插入的一端。队头（front）：允许删除的一端。空队：空表。队列操作特点：先进先出（FirstInFirstOut---FIFO）27PPT课件队列的抽象数据类型定义3.1栈、队列和串的逻辑结构（续）ADTQueue{

数据对象：D={ai|ai属于ElemSet,i=1,2,…,n,n>=0}

数据关系：R1={<ai-1,ai>|ai-1,ai属于D,i=2,3,…,n}//a1

为队头，an

队尾基本操作：

InitQueue(&Q)

DestroyQueue(&Q)

ClearQueue(&Q)

QueueEmpty(Q)

QueueLength(Q)

GetHead(Q,&e)

初始条件：Q存在,非空；

操作结果：用e返回Q的栈顶元 素 EnQueue(&Q,e)

初始条件：Q存在操作结果：插入元素e为新的队尾元素，长度加 1DelQueue(&S,&e)

初始条件：Q存在；非空操作结果：删除Q的对头元素，e返回值，长度 减1}ADTQueue出队（删除）入队（插入）28PPT课件串的基本概念和术语3.1栈、队列和串的逻辑结构（续）串（String）：由零个或多个字符组成的有限序列。S=‘a1a2…an’串名、串值串长空串、空格串子串：串中任意连续的字符组成的子序列主串：字符在串中的位置、子串在串中的位置串相等串的操作特点：一般以子串整体为单位29PPT课件串的抽象数据类型定义3.1栈、队列和串的逻辑结构（续）ADTSring{

数据对象：D={ai|ai属于CharacterSet,i=1,2,…,n,n>=0}

数据关系：R1={<ai-1,ai>|ai-1,ai属于D,i=2,3,…,n}基本操作：

StrAssign(&T,chars)

StrCopy(&T,S)

StrEmpty(S)

StrLength(S)

SubString(&Sub,S,pos,len)

初始条件：S存在,1<=pos<=StrLength(S), 0<=len<=StrLength(S)-pos+1；

操作结果： Index(S,T,pos)StrInsert(&S,pos,T)

初始条件：S存在,1<=pos<=StrLength(S)+1

操作结果：在串S的第pos个字符之前插入串TStrDelete(&S,pos,len)

初始条件：S存在,1<=pos<=StrLength(S)-len+1

操作结果：从串S中删除第pos个字符起长度为

len

的子串}ADTString插入查找删除30PPT课件栈的顺序存储3.2栈、队列和串的存储结构a1…ai…a2base//----------动态分配------------#defineSTACK_INIT_SIZE100//空间初始分配量#defineSTACKINCREMENT10 //空间分配增量typedef

struct{

sElemType *base

sElemType *top

int

stacksize//当前分配的存储容量}SqStacktop31PPT课件StatusPush(SqStack&S,SElemTypee)

if(S.top–S.base>=S.stacksize){ S.base=(SElemTupe*)realloc(S.base,(S.stacksize

+STACKINCERMENT)*sizeof(Selemtype)); if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base+S.stacksize;

S.stacksize=+STACKINCERMENT;}*S.top++=e;returnOK;}//Push入栈a1…ai…a2basetopa1eai……a2basetop顺序栈上的入栈3.2栈、队列和串的存储结构（续）32PPT课件StatusPop(SqStack&S,SElemType&e)

if(S.top=S.base)returnerror;e=*--S.top;returnOK;}//Pop出栈a1…ai-1…a2basetopa1aiai-1……a2basetop顺序栈上的出栈3.2栈、队列和串的存储结构（续）33PPT课件栈的链式存储---链栈3.2栈、队列和串的存储结构（续）basetoptypedef

struct{

ElemType data

struct

Lnode *next }Lnode,*StackPtran-1a1^an…typedef

struct{

StackPtr top

StackPtr base}LinkStack34PPT课件链栈上的入栈与出栈3.2栈、队列和串的存储结构（续）链栈上的入栈与出栈与单链表上元素插入删除操作类似插入删除位置都在栈顶处，不花费查找时间栈空的判断35PPT课件队列的顺序存储---循环队列（一）3.2栈、队列和串的存储结构（续）a1…ai…a2front一般顺序存储的队列特点：队空条件：front=rear队满条件：rear=MAXSIZE队满条件下的队满为假满（假溢出）（真满时：rear=MAXSIZE,front=0）rear36PPT课件//----------动态分配------------#defineMAXSIZE100//最大队列长度typedef

struct{

QElemType *base

int front //指向队头元素当前位置

int rear//指向队尾元素下一个位置}SqQueue队列的顺序存储---循环队列（二)3.2栈、队列和串的存储结构（续）37PPT课件循环队列特点：队空条件： *front=rear（方式一） *标志域+（front=rear）（方式二）队满条件： *(rear+1)%MAXSIZE=front（方式一） *标志域+（front=rear）（方式二）队满条件下的队满为真满队列的顺序存储---循环队列（三)3.2栈、队列和串的存储结构（续）38PPT课件队列的顺序存储---循环队列（四)3.2栈、队列和串的存储结构（续）StatusEnQueue(SqQueue&Q,QElemTypee)

if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}//EnQueueStatusInitQueue(SqQueue&Q){

Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType));if(!Q.base)exit(overflow);Q.front=Q.rear=0;returnOK;}//InitQueueStatusDeQueue(SqQueue&Q,QElemType&e){

if(Q.rear==Q.front)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}//DeQueue39PPT课件队列的链式存储---链队列（一）3.2栈、队列和串的存储结构（续）typedef

struct{

QElemType data

struct

QNode *next }QNode,*QueuePtra2an^a1…typedef

struct{

QueuePtr rear

QueuePtr front}LinkQueueq.rear.front40PPT课件StatusEnQueue(LinkQueue&Q,QElemTypee)

p=(QueuePtr)malloc(sizeof(Qnode));if(!p)exit(overflow);p->data=e; p->next=NULL;Q.rear->next=p; Q.rear=p;returnOK;}//EnQueueStatusInitQueue(LinkQueue&Q){

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(overflow);Q.front->next=NULL;returnOK;}//InitQueueStatusDeQueue(LinkQueue&Q,QElemType&e){

if(Q.rear==Q.front)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}//DeQueue队列的链式存储---链队列（二）3.2栈、队列和串的存储结构（续）41PPT课件串的顺序存储（一）3.2栈、队列和串的存储结构（续）//----------串的定长顺序存储表示------------#defineMAXSTRLEN255//最大串长度typedefunsignedcharSString[MAXSTRLEN+1] //0号单元存放串的长度串顺序存储的特点：连续存储单元静态分配串操作中的原操作一般为“字符序列的复制”截尾法处理串值序列的上越界42PPT课件StatusSubString(SString&Sub,SStringS,intpos,int

len){

if(pos<1||pos>S[0]||len<0||len>S[0]–pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}//SubString串的顺序存储（二）3.2栈、队列和串的存储结构（续）StatusConcat(SString&T,SStringS1,SStringS2){…}//Concat43PPT课件一般算法3.3串的模式匹配算法int

Index(SString

S,SStringT,intpos){//返回子串T在主串S中第pos个

i=pos; j=1; //字符之后的位置。若不存在，

while(i<=s[0]&&j<=T[0]){//函数值位0 if(S[i]==T[j]){++i; ++j;} else{i=i-j+2; j=1;}}if(j>T[0])returni–T[0];elsereturn0;}//Index算法时间复杂度：T(n)=O(n*m)逻辑函数为Index(S,T,pos)S=‘a1a2…ai…an’ T=‘t1t2…tj…tm’一般而言，m<<n算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较之。44PPT课件3.3串的模式匹配算法（续）第一趟主串： ababcabcacbab //i=3

模式串：abc //j=3第二趟主串： ababcabcacbab //i=2

模式串：a /j=1第三趟主串： ababcabcacbab //i=7

模式串：abcac //j=5第四趟主串： ababcabcacbab //i=4

模式串：a //j=1第五趟主串： ababcabcacbab //i=5

模式串：

a //j=1第六趟主串： ababcabcacbab //i=11

模式串：abcac //j=6模式串T=‘abcac’45PPT课件改进算法---思路3.3串的模式匹配算法（续）KMP算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符。当一趟匹配过程中出现字符比较不等时，不回朔i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。优点：在匹配过程中，主串的跟踪指针不回朔时间效率达到T(n)=O(n+m)如何理解“部分匹配”？主串：acabaacaabcac 模式串：acaab

46PPT课件改进算法---原理3.3串的模式匹配算法（续）设主串S=‘s1s2…si…sn’,模式串T=‘t1t2…tj…tm’在匹配过程中，当主串中第i个字符与模式串中第j个字符“失配”时（si不等于tj），将模式串“向右滑动”，让模式串中第k（k<j）个字符与si对齐继续比较。这时有：

‘t1t2…tk-1’=‘si-k+1si-k+2…si-1’ -----(1)而由部分匹配成功的结果可知：

‘t1t2…tj-1’=‘si-j+1si-j+2…si-1’ -----(2)由(2)式可以推知：

‘tj-k+1tj-k+2…tj-1’=‘si-k+1si-k+2…si-1’ -----(3)由(1)式与(3)式可以推知：

‘t1t2…tk-1’=‘tj-k+1tj-k+2…tj-1’ -----(4)

47PPT课件令next[j]=k，表示当模式串中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。根据其语义，定义如下：0 当j=1时//相当于主串中i指针推进一个位置Next[j]=Max{k|1<k<j且‘t1t2…tk-1’=‘tj-k+1tj-k+2…tj-1’}// 1 其他情况改进算法---Next函数定义3.3串的模式匹配算法（续）设主串S=‘s1s2…si…sn’,模式串T=‘t1t2…tj…tm’Next函数值仅取决于模式串本身的结构而与相匹配的主串无关j 12345678模式串 abaabcacnext[j] 01122312j 12345678模式串 abaabcacnext[j] 保证得到第一个“配串”48PPT课件改进算法---匹配过程3.3串的模式匹配算法（续）第一趟主串： acabaabaabcac aabc //i=2

模式串：a

b

//j=2,next[2]=1第二趟主串： acabaabaabcac aabc //i=2

模式串：a //j=1,next[1]=0第三趟主串： acabaabaabcac aabc //i=8

模式串：abaabc //j=6,next[6]=3第四趟主串：acabaabaabcac aabc //i=14

模式串：

(ab)aabcac //j=9j 12345678模式串 abaabcacnext[j] 0112231249PPT课件int

Index_KMP(SString

S,SStringT,intpos){//返回子串T在主串S中第pos个字符之后的位置。若不存在,函数值为0

i=pos; j=1; while(i<=s[0]&&j<=T[0]){ if(j==0|S[i]==T[j]){++i; ++j;} elsej=next[j];}if(j>T[0])returni–T[0];elsereturn0;}//Index_KMP算法时间复杂度：T(n)=O(n+m)改进算法---KMP算法3.3串的模式匹配算法（续）50PPT课件4.数组5.广义表6.树和二叉树7.图第二部分非线性数据结构51PPT课件4.数组5.广义表6.树和二叉树7.图教学内容---第六章52PPT课件6.1树的逻辑结构基本概念和术语树：树T是n个结点的有限集。非空树中： （1）有且只有一个特定的称为根(Root)的结点； （2）当n>1时，其余结点可分为m(m>0)各互不相交 的有限集T1,T2,…,Tm,其中每一个集合本身又是 一棵树，并且称为根的子树(SubTree)。树的结点：一个数据元素和指向其子树的分支。结点的度：结点拥有的子树数。终端结点（或叶子）：度为0的结点。非终端结点（或分支结点、或内部结点）：度不为0的结点。树的度：树内各结点的度的最大值。（结点的）孩子：结点的子树的根。53PPT课件6.1树的逻辑结构（续）树的性质及树的表示树的性质：递归性层次性树的表示形式：树形表示集合嵌套表示广义表形式表示凹入表示54PPT课件datafirstchildnextsibling结点6.2树的存储结构（续）孩子兄弟表示法（二叉链表）//----------树的二叉链表（孩子-兄弟）存储表示------------typedef

struct

CSNode{

ElemType data; //树结点数据域

struct

CSNode *firstchild,*nextsibling;}CSNode,*CSTree;55PPT课件6.3二叉树的逻辑结构二叉树的描述性定义及其基本形态二叉树：二叉树BT是n个结点的有限集。非空二叉树中：（1）有且只有一个特定的称为根(Root)的结点； （2）当n>1时，其余结点可分为2个互不相交的有限集BTL,BTR,BTL,BTR分别又是一棵二叉树，BTL称为根的左子树；BTR称为根的右子树。二叉树的基本形态：

五种：空二叉树；仅有根结点的二叉树；右子树为空的二叉树；左、右子树均不为空的二叉树；左子树为空的二叉树。56PPT课件6.3二叉树的逻辑结构（续）二叉树的数学性质性质1：在二叉树的第i层上至多右2i-1个结点(i>=1);性质2：深度为k的二叉树至多有2k–1个结点(k>=1);性质3：二叉树T，若叶子结点数为n0,度为2的结点数为n2，则有n0=n2+1;性质1：[证明]

i=1时，显然有2i-1=20=1；假设对于所有的j，1<=j<i，第j层上至多有2j-1个结点，则当j=i时，由假设知2i-1层上至多右2i-2,而二叉树的每个结点的度至多为2，故在第i层上

最大结点数为i-1层上最大结点数的2倍，即2*2i-2=2i-1。

[证毕]性质3：[证明]

n=n0

+n1+n2n

=B+1B=n1+2n2所以：

n0

=n2+1

[证毕]性质4：具有n个结点的完全二叉树的深度为：以2为底的n的对数值取下整+1； 性质5：n个结点的完全二叉树结点按照层序编号，则对任一结点i(1<=i<=n)，有：（1）如果i=1，则结点i是二叉树的根；如果i>1，则其双亲是结点(i/2)取下整；(2)如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i；(3)如果如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。满二叉树：深度为k且有2k–1个结点的二叉树;完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。性质4：[证明]假设深度为k，由性质2以及完全二叉树定义有：2k-1–1<n<=2k–1推出2k-1

<=n<2k

k–1<=以2为底的n的对数<k由于k是整数，所以结论成立。

[证毕]57PPT课件6.4二叉树的存储结构顺序存储具体做法：利用完全二叉树的性质，元素之间的关系隐含在元素的编号中，所以采用顺序存储后，完全二叉树中结点的存储位置为其编号所在的位置。对于一般二叉树，若采用顺序存储，须先增加虚结点以补成虚完全二叉树，对此虚完全二叉树的存储对应该二叉树的顺序存储。//----------二叉树的顺序存储表示------------#defineMAX_TREE_SIZE 100typedef

TElemType

SqBiTree[MAX_TREE_SIZE]; //0号单元存放根结点SqBiTree

bt;58PPT课件ABCDIJEABDIJK6.4二叉树的存储结构（续）顺序存储59PPT课件6.4二叉树的存储结构（续）二叉链表存储datalchildrchild结点//----------二叉树的二叉链表存储表示------------typedef

struct

BiTNode{

TElemType data; //数据域

struct

BiTNode *lchild,*rchild;}BiTNode,*BiTree;60PPT课件6.4二叉树的存储结构（续）三叉链表存储datalchildrchild结点parent//----------二叉树的三叉链表存储表示------------typedef

struct

BiTNode{

TElemType data; //数据域

struct

BiTNode *lchild,*rchild，*parent;}BiTNode,*BiTree;61PPT课件6.4二叉树的存储结构（续）（二叉）线索链表存储datalchild结点ltagrtagrchild//----------二叉树的二叉线索链表存储表示------------typedef

enum{Link,Thread}PointerTag;//Link==0;Thread==1typedef

struct

BiThrNode{

TElemType data; //数据域

struct

BiThrNode *lchild,*rchild;//左、右孩子指针

PointerTag

LTag，Rtag; //左、右标志}BiThrNode,*BiThrTree;62PPT课件EABCDFIJHGK6.4二叉树的存储结构（续）（二叉）线索链表存储63PPT课件6.5二叉树的遍历及线索化遍历二叉树在二叉树中查找具有某种特征的结点需要对结点进行访问（处理、输出等）操作二叉树上许多复杂操作的基础是对其遍历遍历(Traversing)：按照某条路径访问每个结点,使得每个结点均被访问一次，而且仅被访问一次。遍历本质：结点之间非线性关系线性化的过程两种思路： *只要保证每个结点都被访问到一次； *遍历过程中易于实现关于结点的复杂操作层次遍历法递归遍历法：先序、中序、后序64PPT课件6.5二叉树的遍历及线索化（续）遍历二叉树的方法先序遍历(PreOrderTraverse)：DLR;

若二叉树为空，则空操作（递归基础）；否则：访问根结点；先序遍历左子树；先序遍历右子树。中序遍历(InOrderTraverse)：LDR;

若二叉树为空，则空操作（递归基础）；否则：中序遍历左子树；访问根结点；中序遍历右子树。后序遍历(PostOrderTraverse)：LRD;

若二叉树为空，则空操作（递归基础）；否则：后序遍历左子树；中序遍历右子树；访问根结点。层次遍历(LevelOrderTraverse)：从上到下，自左至右按照层次遍历。65PPT课件EABCDFIJHGK层次遍历：A,B,I,C,D,J,K,E,F,G,H先序遍历：A,B,C,D,E,F,G,H,I,J,K中序遍历：C,B,E,D,G,F,H,A,J,I,K后序遍历：C,E,G,HF,D,B,J,K,I,A66PPT课件StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit

if(T){

if(InOrderTraverse(T->lchild,Visit)) if(Visit(T->data)){

if(InOrderTraverse(T->rchild,Visit)) returnOK; }elsereturnERROR;//当访问失败时，出错}else returnOK;//一次递归访问终止}InOrderTraverse

//算法时间复杂度：O(n)6.5二叉树的遍历及线索化（续）中序遍历的算法StatusInOrderTraverse1(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit

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))returnERROR//访问出错

Push(S,p->rchild);}//if}//whilereturnOK;}InOrderTraverse

//算法时间复杂度：O(n)StatusInOrderTraverse2(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit

InitStack(S); p=T; While(p||!StackEmpty(S)){ if(p){Push(S,p);p=p->lchild;}//根指针入栈,遍历左子树 else{

//根指针退栈，访问根结点，遍历右子树

Pop(S,p); if(!Visit(p->data))returnERROR//访问出错

p=p->rchild);}//else}//whilereturnOK;}InOrderTraverse

//算法时间复杂度：O(n)67PPT课件6.5二叉树的遍历及线索化（续）二叉树遍历的典型应用已知二叉树的前序遍历序列和中序遍历序列，或者已知二叉树的后序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。EABCDFIJHGKStep1:判定根，由PostOrder知根为A；Step2:判定左子树元素集合，由InOrder知为{CBEDGFH}InOrder:CBEDGFHAJIKPostOrder:CEGHFDBJKIAStep3:判定右子树元素集合，由InOrder知为{JIK}Step4:分别对左、右子树元素集合按照中序和后序序列递归进行Step1---Step3，直到元素集合为空。68PPT课件6.5二叉树的遍历及线索化（续）线索二叉树遍历本质是结点之间非线性关系线性化的过程遍历后的元素之间的某种线性关系一般隐藏在遍历规则下需要多次对同一棵树遍历时，如何提高效率？在二叉链表结构中增加线索域，显式描述遍历后的线索关系节省线索域空间，充分利用二叉链表中空的n+1个指针域线索链表：二叉树的存储结构，结点结构定义见前面。线索：指向结点前驱和后继的指针，叫做线索。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。线索二叉树上遍历的过程，就是根据线索和遍历规则不断找当前结点后继结点的过程。69PPT课件6.5二叉树的遍历及线索化（续）线索二叉树上的中序遍历InOrder:CBEDGFHAJIK设当前结点指针为p，其前驱结点为q，后继结点指针为s,则有：求结点p的后继：1.若p->rtag=1

则s=p->rchild;2.若p->rtag=0s为p的右子树的中序遍历序列的第一个结点，即右子树最左下结点EABCDFIJHGK求结点p的前驱：1.若p->ltag=1

则q=p->lchild;2.若p->rtag=0q为p的左子树的中序遍历序列的第一个结点，即左子树最右下结点70PPT课件6.6树、森林与二叉树的转换森林与树相互递归定义森林：m棵互不相交的树的集合。树：树是一个二元组Tree=(root，F),root是根，F是m(m>0)棵树的森林，F={T1,T2,…,Tm}其中Ti=(ri，Fi)

称为根的第i棵子树；当m!=0时，在树根和其子树森林之间存在下列关系：RF={<root，ri>|i=1,2,…,m,m>0}

71PPT课件6.6树、森林与二叉树的转换（续）树与二叉树的转换目的：利用二叉树运算来简化树和森林上的运算；依据：树与二叉树具有相同的二叉链表存储结构；EABCDFIABDECIF72PPT课件EABCDFIJHGKABDECIFKJGH6.6树、森林与二叉树的转换（续）73PPT课件EABCDFIJHGKEABCDFHGKIJ6.6树、森林与二叉树的转换（续）74PPT课件6.7二叉树的应用哈夫曼树(HuffmanTree)结点之间路径长度：树中两个结点之间的分支构成这两个结点的路径，路径上的分支数目为路径长度。树的路径长度：树根到每个结点的路径长度之和。结点的带权路径长度：该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为：WPL=w1k1+w2k2+…+wiki

+wnkn。最优二叉树（哈夫曼树）：设n个权值{w1,w2,…,wn

},构造一棵有n个叶子结点的二叉树，每个叶子结点带权wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树（哈夫曼树）。75PPT课件6.7二叉树的应用（续）哈夫曼算法(HuffmanAlgorithmic)输入：n个权值{w1,w2,…,wn

}

；输出：一棵哈夫曼树算法：步骤一：根据给定的n个权值{w1,w2,…,wn

}

构成n棵二叉树的集合F={T1,T2…,Tn}，其中每棵二叉树Ti

中只有一个带权为wi

的根结点，其左右子树均为空。步骤二：在F中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。步骤三：在F中删除这两棵树，同时将新得到的二叉树加入F中。步骤四：重复步骤二与三，直到F只含有一棵树为止。76PPT课件给定权的集合:{15,3,14,2,6,9,16,17}6.7二叉树的应用（续）哈夫曼算法(HuffmanAlgorithmic){15,3,14,2,6,9,16,17}{15,5,14,6,9,16,17}{15,11,14,9,16,17}{15,14,20,16,17}{29,20,16,17}{29,20,33}{49,33}{82}9496161782325141511202933WPL=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=22977PPT课件6.7二叉树的应用（续）哈夫曼编码(HuffmanCode)等长编码：每个被编码对象的码长相等。 优点：码长等长，易于解码； 缺点：被编码信息总码长较大，尤其是当存在 许多不常用的被编码对象时前缀编码：任一个被编码对象的编码都不是另一个 被编码对象的编码的前缀。 优点：当存在被编码对象使用概率不同时，被 编码信息总码长可以减小； 缺点：码长不等长，不易于解码78PPT课件6.7二叉树的应用（续）哈夫曼编码(HuffmanCode)---前缀编码利用二叉树来设计二进制的前缀编码：被编码对象出现在二叉树的叶子结点。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点对应对象的编码。baedcf0000011111a(00)b(010)c(0110)d(0111)e(10)f(11)这种编码的译码过程从根开始。沿着某条分支走到叶子结点时，走过的二进制字符串即译为该叶子结点对应的对象。然后循环扫描总编码后的字符串。79PPT课件6.7二叉树的应用（续）哈夫曼编码与译码利用哈夫曼算法可以得到总码长最短的二进制前缀编码，即为哈夫曼编码。设某次编码应用中不同被编码对象有n种，以此n种被编码对象出现的频率作权，构造出的哈夫曼树即为这n种对象的编码树，由此可得到其二进制的前缀编码。假定用于通讯的电文如下，现在要对其编码，采用哈夫曼编码。写出编码后的二进制串。电文：castcatssatatatasac(110)a(0)s(111)t(10)Set={c,a,s,t}W={2,7,4,5}电文编码：11001111011001011111101001001001110518711642000111csat80PPT课件4.数组5.广义表6.树和二叉树7.图教学内容---第七章81PPT课件ADTGraph{

数据对象：V={具有相同性质的数据元素}

数据关系：R: R={VR}

VR={<v,w>|v,w属于V且P(v,w),<v,w>是从v到w的一 条弧，谓词P(v,w)定义了弧<v,w>的意义或信息}

基本操作：P:

CreateGraph(&G,V,VR);DFSTraverseGraph(G,v,Visit()); …;BFSTraverseGraph(G,v,Visit())

}ADTGraph7.1图的逻辑结构图的抽象数据类型82PPT课件7.1图的逻辑结构（续）基本概念和术语顶点(Vertex)、弧(Arc)、有向图(Digraph)、边(Edge)、无向图(Undigraph)、完全图(Completedgraph)、有向完全图、稀疏图(Sparsegraph)、权(Weight)、网(Network)、子图(Subgraph)、邻接点(Adjacent)、（顶点的）度(Degree)、（顶点的）入度(InDegree)、（顶点的）出度(OutDegree)、（顶点之间）路径(Path)、（顶点之间）路径长度、回路或环(Cycle)、简单路径、简单回路（简单环）、（顶点之间）连通、连通图(ConnectedGraph)、连通分量(ConnectedComponent)、强连通图、强连通分量、（连通图的）生成树：（有向图的）生成森林83PPT课件 01010 10101G1.arcs=01011 10100 011007.2树的存储结构（续）数组表示法V3V1V2V5V4G1V1V2V4V3G2 0110 0000G2.arcs=1001 111084PPT课件7.2图的存储结构（续）邻接表---图的链式存储基本思路：对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个表结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置；链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息。头结点由两个域组成：链域(firstarc)指向链表中第一个结点；数据域(data)存储顶点vi信息。头结点以顺序结构形式存取，以便随机访问任一顶点的链表。Adjvexnextarcinfodatafirstarc表结点头结点85PPT课件7.2图的存储结构（续）V10V21V32V43V5421^20^420^31^431^V3V1V2V5V4G1V1V2V4V3G2V10V32V21V4330^0^32^30^V10V2^1V32V4330^221^20^86PPT课件7.2图的存储结构（续）邻接表---图的链式存储邻接表的优点：边（或弧）稀疏时，节省空间；和边（或弧）相关的信息较多时，节省空间；容易求得当前顶点的第一个邻接点、下一个邻接点。对有向图，也可建立逆向邻接表，即对每个顶点建立一个链接以该顶点为头的弧的表。87PPT课件7.3图的遍历遍历图在图中查找具有某种特征的结点需要对结点进行访问（处理、输出等）操作图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础图的遍历(TraversingGraph)：从图的某一个顶点出发，按照某条路径访问每个结点,使得每个结点均被访问一次，而且仅被访问一次。遍历本质：结点之间非线性关系线性化的过程遍历思路： *深度优先：类似于树的先根遍历； *广度优先：类似于树的层次遍历。88PPT课件7.3图的遍历（续）深度优先搜索遍历思路：从图的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。这是一个递归算法，遍历过程中，当某个顶点的所有邻接点都被访问到后，需要“回朔”，即沿着调用的逆方向回退到上一层顶点，继续考察该顶点的下一个邻接点。Booleanvisited[MAX]; //访问标志数组Status(*VisitFunc)(intv); //函数变量VoidDFSTraverse(GraphG,Status(*Visit)(intv)){

VisitFunc=Visit；//使用全局变量VisitFunc，使DFS不必设函数指针参数

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//标志数组初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}StatusDFS(GraphG,intv){//从第v个顶点出发递归地深度优先遍历图G，对每个元素调用函数Visitvisited[v]=TRUE; VisitFunc(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);}//算法时间复杂度与存储结构相关邻接矩阵存储:T(n)=O(n2);邻接表存储:T(n)=O(n+e)89PPT课件7.3图的遍历（续）深度优先搜索V12V9V10V11V1G3V3V6V2V8V5V4V7一种DFS遍历序列：

V1,V2,V4,V8,V5,V3,V6,V7,V9,V10,V12,V11当存储结构和算法确定后，遍历序列唯一。90PPT课件7.3图的遍历（续）广度优先搜索遍历思路：从图的某个顶点v出发，访问此顶点，然后依次访问v的未被访问的邻接点，然后从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的