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

数据结构辅导李青山西安电子科技大学http:/202.117.118.45/faculty/029-8820-4611课程内容框架数 据 结 构基础数据结构应用数据结构栈队列线性表线性结构 非线性结构串查找内部排序外部排序文件动态存管理储数组广义表 树二叉树 图基本概念1.2基本概念和术语数据、数据元素、数据项、数据对象结构*集合：松散的关系*线性结构：一对一的关系*树形结构：一对多的关系*网状结构：多对多的关系数据结构Data_Structure=（D，S）数据结构的分类1.2基本概念和术语（续）逻辑结构：数据元素之间的逻辑关系（本来的关系）存储结构：数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：*顺序存储结构*链式存储结构描述方式：用高级语言中的“数据类型”来描述算法1.3算法和算法分析内涵:是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。特性:*有穷性：有穷步+有穷时间/每一步*确定性：指令的语义无二义性*可行性：算法能用基本操作完成*输入：零个或多个输入*输出：一个或多个输出算法设计的要求1.3算法和算法分析（续）正确性（Correctness）可读性（Readablity）健壮性（Robustness）高时间效率与低存储量需求算法时间效率的度量1.3算法和算法分析（续）算法时间效率度量的基本做法在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。算法时间复杂度 T(n)=O(f(n)称为算法的渐近时间复杂度，简称时间复杂度。算法存储空间的度量1.3算法和算法分析（续）算法存储空间度量的基本做法用程序执行中需要的辅助空间的消耗作为存储空间度量的依据，是问题规模n的函数。而程序执行中本身需要的工作单元不能算。算法空间复杂度 S(n)=O(f(n)称为算法的空间复杂度。2.线性表3.栈、队列和串第一部分 线性数据结构线性数据结构的特点2.1线性表的逻辑结构在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个之外，集合中的每一个数据元素均只有一个前驱；除最后一个之外，集合中每一个数据元素均只有一个后继。基本概念和术语2.1线性表的逻辑结构（续）线性表：n个数据元素的有限序列（线性表中的数据元素在不同环境下具体含义可以不同，但在同一线性表中的元素性质必须相同）。表长：线性表中元素的个数n(n=0)。空表：n=0时的线性表称为空表。位序：非空表中数据元素 ai 是此表的第 i 个元 素，则称 i 为 ai 在线性表中的位序。线性表的抽象数据类型定义2.1线性表的逻辑结构（续）ADT List 数据对象：D=ai|ai属于ElemSet,i=1,2,n,n=0数据关系：R1=|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个 数据元素的值 ADT ListLocateElem(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查找删除插入顺序表-线性表的顺序存储2.2线性表的顺序存储结构内涵：线性表的顺序存储指用一组地址连续的存储单元依次存储线性表的数据元素。这称为顺序表。特点：*存储单元地址连续（需要一段连续空间）*逻辑上相邻的数据元素其物理位置也相邻 *随机存取 *存储密度为大（100%）顺序表的随机存取2.2线性表的顺序存储结构（续）对线性表L,设每个元素占k个存储单元，则有：递推关系：LOC(ai+1)=LOC(ai)+k任一元素ai+1的存储位置：LOC(ai)=LOC(a1)+(i-1)*k (其中1=i next=p-next;p-next=s单链表上删除运算的实现2.3线性表的链式存储结构（续）删除q（a1，ai,ai+1,an)表长为nListDelete(&L,i,&e)（a1，ai-1,ai+1,an)表长为n-1free(q)ai-1aiLai+1pp-next=p-next-nextai-1aiLai+1p2.线性表3.栈、队列和串教学内容-第三章栈、队列和串是特殊的线性表3.1 栈、队列和串的逻辑结构栈和队列是操作受限的线性表栈和队列的“操作受限”指操作位置受限串的特殊性在于线性表中数据元素只能是字符串一般以子串为操作单位栈、队列和串具有一般线性表共性的特点特殊的线性表反而应用面更宽栈的基本概念和术语3.1 栈、队列和串的逻辑结构（续）栈（Stack）：限定仅在表尾进行插入或删除操作的线性表。栈顶（top）：插入或删除的表尾端。栈底（bottom）：表头端。空栈：空表。栈的操作特点：后进先出（Last In First Out-LIFO）栈的抽象数据类型定义3.1 栈、队列和串的逻辑结构（续）ADT Stack 数据对象：D=ai|ai属于ElemSet,i=1,2,n,n=0数据关系：R1=|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返回值，长度 减1ADT Stack出栈（删除）入栈（插入）队列的基本概念和术语3.1 栈、队列和串的逻辑结构（续）队列（Queue）：限定仅在表的一端进行插入，而另一端进行删除操作的线性表。队尾（rear）：允许插入的一端。队头（front）：允许删除的一端。空队：空表。队列操作特点：先进先出（First In First Out-FIFO）队列的抽象数据类型定义3.1 栈、队列和串的逻辑结构（续）ADT Queue 数据对象：D=ai|ai属于ElemSet,i=1,2,n,n=0数据关系：R1=|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返回值，长度 减1ADT Queue出队（删除）入队（插入）串的基本概念和术语3.1 栈、队列和串的逻辑结构（续）串（String）：由零个或多个字符组成的有限序列。S=a1a2an串名、串值串长空串、空格串子串：串中任意连续的字符组成的子序列主串：字符在串中的位置、子串在串中的位置串相等串的操作特点：一般以子串整体为单位串的抽象数据类型定义3.1 栈、队列和串的逻辑结构（续）ADT Sring 数据对象：D=ai|ai属于CharacterSet,i=1,2,n,n=0数据关系：R1=|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=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;return OK;/Push入栈a1aia2basetopa1eaia2basetop顺序栈上的入栈3.2 栈、队列和串的存储结构（续）Status Pop(SqStack&S,SElemType&e)if(S.top=S.base)return error;e=*-S.top;return OK;/Pop出栈a1ai-1a2basetopa1aiai-1a2basetop顺序栈上的出栈3.2 栈、队列和串的存储结构（续）栈的链式存储-链栈3.2 栈、队列和串的存储结构（续）basetoptypedef struct ElemTypedatastruct Lnode*next Lnode,*StackPtran-1a1antypedef struct StackPtr top StackPtr base LinkStack链栈上的入栈与出栈3.2 栈、队列和串的存储结构（续）链栈上的入栈与出栈与单链表上元素插入删除操作类似插入删除位置都在栈顶处，不花费查找时间栈空的判断队列的顺序存储-循环队列（一）3.2 栈、队列和串的存储结构（续）a1aia2front一般顺序存储的队列特点：队空条件：front=rear队满条件：rear=MAXSIZE队满条件下的队满为假满（假溢出）（真满时：rear=MAXSIZE,front=0）rear/-动态分配-#define MAXSIZE 100 /最大队列长度typedef struct QElemType*baseintfront/指向队头元素当前位置intrear /指向队尾元素下一个位置 SqQueue队列的顺序存储-循环队列（二)3.2 栈、队列和串的存储结构（续）循环队列特点：队空条件：*front=rear（方式一）*标志域+（front=rear）（方式二）队满条件：*(rear+1)%MAXSIZE=front（方式一）*标志域+（front=rear）（方式二）队满条件下的队满为真满队列的顺序存储-循环队列（三)3.2 栈、队列和串的存储结构（续）队列的顺序存储-循环队列（四)3.2 栈、队列和串的存储结构（续）Status EnQueue(SqQueue&Q,QElemType e)if(Q.rear+1)%MAXSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;/EnQueueStatus InitQueue(SqQueue&Q)Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType);if(!Q.base)exit(overflow);Q.front=Q.rear=0;return OK;/InitQueueStatus DeQueue(SqQueue&Q,QElemType&e)if(Q.rear=Q.front)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK;/DeQueue队列的链式存储-链队列（一）3.2 栈、队列和串的存储结构（续）typedef struct QElemTypedatastruct QNode*next QNode,*QueuePtra2ana1typedef struct QueuePtr rear QueuePtr front LinkQueueq.rear.frontStatus EnQueue(LinkQueue&Q,QElemType e)p=(QueuePtr)malloc(sizeof(Qnode);if(!p)exit(overflow);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;/EnQueueStatus InitQueue(LinkQueue&Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(overflow);Q.front-next=NULL;return OK;/InitQueueStatus DeQueue(LinkQueue&Q,QElemType&e)if(Q.rear=Q.front)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;/DeQueue队列的链式存储-链队列（二）3.2 栈、队列和串的存储结构（续）串的顺序存储（一）3.2 栈、队列和串的存储结构（续）/-串的定长顺序存储表示-#define MAXSTRLEN 255 /最大串长度typedef unsigned char SStringMAXSTRLEN+1/0号单元存放串的长度串顺序存储的特点：连续存储单元静态分配串操作中的原操作一般为“字符序列的复制”截尾法处理串值序列的上越界Status SubString(SString&Sub,SString S,int pos,int len)if(pos S0|len S0 pos+1)return ERROR;Sub1.len=Spos.pos+len-1;Sub0=len;return OK;/SubString串的顺序存储（二）3.2 栈、队列和串的存储结构（续）Status Concat(SString&T,SString S1,SString S2)/Concat一般算法3.3 串的模式匹配算法int Index(SString S,SString T,int pos)/返回子串T在主串S中第pos个 i=pos;j=1;/字符之后的位置。若不存在，while(i=s0&j T0)return i T0;else return 0;/Index算法时间复杂度：T(n)=O(n*m)逻辑函数为 Index(S,T,pos)S=a1a2aianT=t1t2tjtm 一般而言，mn算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较之。3.3 串的模式匹配算法（续）第一趟 主串：a b a b c a b c a c b a b/i=3模式串：a b c/j=3第二趟 主串：a b a b c a b c a c b a b/i=2模式串：a/j=1第三趟 主串：a b a b c a b c a c b a b/i=7模式串：a b c a c/j=5第四趟 主串：a b a b c a b c a c b a b/i=4模式串：a/j=1第五趟 主串：a b a b c a b c a c b a b/i=5模式串：a/j=1第六趟 主串：a b a b c a b c a c b a b /i=11模式串：a b c a c/j=6模式串T=abcac改进算法-思路3.3 串的模式匹配算法（续）KMP算法思路：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，继续逐个比较后续字符。当一趟匹配过程中出现字符比较不等时，不回朔i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。优点：在匹配过程中，主串的跟踪指针不回朔 时间效率达到T(n)=O(n+m)如何理解“部分匹配”？主串：a c a b a a c a a b c a c模式串：a c a a b 改进算法-原理3.3 串的模式匹配算法（续）设主串S=s1s2sisn,模式串T=t1t2tjtm 在匹配过程中，当主串中第i个字符与模式串中第j个字符“失配”时（si不等于tj），将模式串“向右滑动”，让模式串中第k（kj）个字符与si对齐继续比较。这时有：t1t2tk-1=si-k+1si-k+2si-1-(1)而由部分匹配成功的结果可知：t1t2tj-1=si-j+1si-j+2si-1-(2)由(2)式可以推知：tj-k+1tj-k+2tj-1=si-k+1si-k+2si-1-(3)由(1)式与(3)式可以推知：t1t2tk-1=tj-k+1tj-k+2tj-1 -(4)令nextj=k，表示当模式串中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。根据其语义，定义如下：0当j=1时 /相当于主串中i指针推进一个位置Nextj=Max k|1kj 且 t1t2tk-1=tj-k+1tj-k+2tj-1 /1其他情况改进算法-Next函数定义3.3 串的模式匹配算法（续）设主串S=s1s2sisn,模式串T=t1t2tjtm Next函数值仅取决于模式串本身的结构而与相匹配的主串无关 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj保证得到第一个“配串”改进算法-匹配过程3.3 串的模式匹配算法（续）第一趟 主串：a c a b a a b a a b c a ca a b c/i=2模式串：a b/j=2,next2=1第二趟 主串：a c a b a a b a a b c a ca a b c/i=2模式串：a/j=1,next1=0第三趟 主串：a c a b a a b a a b c a ca a b c/i=8模式串：a b a a b c/j=6,next6=3第四趟 主串：a c a b a a b a a b c a ca a b c/i=14模式串：(a b)a a b c a c/j=9 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a cnextj 0 1 1 2 2 3 1 2int Index_KMP(SString S,SString T,int pos)/返回子串T在主串S中第pos个字符之后的位置。若不存在,函数值为0 i=pos;j=1;while(i=s0&j T0)return i T0;else return 0;/Index_KMP算法时间复杂度：T(n)=O(n+m)改进算法-KMP算法3.3 串的模式匹配算法（续）4.数组5.广义表6.树和二叉树7.图第二部分 非线性数据结构4.数组5.广义表6.树和二叉树7.图教学内容-第六章6.1树的逻辑结构基本概念和术语树：树T是n个结点的有限集。非空树中：（1）有且只有一个特定的称为根(Root)的结点；（2）当n1时，其余结点可分为m(m0)各互不相交 的有限集T1,T2,Tm,其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。树的结点：一个数据元素和指向其子树的分支。结点的度：结点拥有的子树数。终端结点（或叶子）：度为0的结点。非终端结点（或分支结点、或内部结点）：度不为0的结点。树的度：树内各结点的度的最大值。（结点的）孩子：结点的子树的根。6.1树的逻辑结构（续）树的性质及树的表示树的性质：递归性层次性树的表示形式：树形表示集合嵌套表示广义表形式表示凹入表示datafirstchild nextsibling结点6.2树的存储结构（续）孩子兄弟表示法（二叉链表）/-树的二叉链表（孩子-兄弟）存储表示-typedef struct CSNodeElemTypedata;/树结点数据域struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;6.3二叉树的逻辑结构二叉树的描述性定义及其基本形态二叉树：二叉树BT是n个结点的有限集。非空二叉树中：（1）有且只有一个特定的称为根(Root)的结点；（2）当n1时，其余结点可分为2个互不相交 的有限集BTL,BTR,BTL,BTR分别又是一棵二叉树，BTL称为根的左子树；BTR称为根的右子树。二叉树的基本形态：五种：空二叉树；仅有根结点的二叉树；右子树为空的二叉树；左、右子树均不为空的二叉树；左子树为空的二叉树。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=ji，第j层上至多有2j-1 个结点，则当j=i时，由假设知2i-1 层上至多右2i-2,而二叉树的每个结点的度至多为2，故在第i层上 最大结点数为i-1层上最大结点数的2倍，即2*2i-2=2i-1。证毕性质3：证明 n=n0+n1+n2 n=B+1 B=n1+2n2所以：n0=n2+1 证毕性质4：具有n个结点的完全二叉树的深度为：以2为底的n的对数值取下整+1；性质5：n个结点的完全二叉树结点按照层序编号，则对任一结点i(1=i1，则其双亲是结点(i/2)取下整；(2)如果2in,则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点 2i；(3)如果如果2i+1n,则结点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的对数 lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)return OK;else return ERROR;/当访问失败时，出错 elsereturn OK;/一次递归访问终止 InOrderTraverse /算法时间复杂度：O(n)6.5二叉树的遍历及线索化（续）中序遍历的算法Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e)/中序遍历二叉树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)return ERROR /访问出错 Push(S,p-rchild);/if /while return OK;InOrderTraverse /算法时间复杂度：O(n)Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e)/中序遍历二叉树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)return ERROR /访问出错 p=p-rchild);/else /while return OK;InOrderTraverse /算法时间复杂度：O(n)6.5二叉树的遍历及线索化（续）二叉树遍历的典型应用 已知二叉树的前序遍历序列和中序遍历序列，或者已知二叉树的后序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。EABCDFIJHGKStep1:判定根，由PostOrder知根为A；Step2:判定左子树元素集合，由InOrder知为C B E D G F H InOrder:C B E D G F H A J I KPostOrder:C E G H F D B J K I AStep3:判定右子树元素集合，由InOrder知为J I KStep4:分别对左、右子树元素集合按照中序和后序序列递归进行Step1-Step3，直到元素集合为空。6.5二叉树的遍历及线索化（续）线索二叉树遍历本质是结点之间非线性关系线性化的过程遍历后的元素之间的某种线性关系一般隐藏在遍历规则下需要多次对同一棵树遍历时，如何提高效率？在二叉链表结构中增加线索域，显式描述遍历后的线索关系节省线索域空间，充分利用二叉链表中空的n+1个指针域线索链表：二叉树的存储结构，结点结构定义见前面。线索：指向结点前驱和后继的指针，叫做线索。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。线索二叉树上遍历的过程，就是根据线索和遍历规则不断找当前结点后继结点的过程。6.5二叉树的遍历及线索化（续）线索二叉树上的中序遍历InOrder:C B E D G F H A J I K设当前结点指针为p，其前驱结点为q，后继结点指针为s,则有：求结点p的后继：1.若 p-rtag=1 则 s=p-rchild;2.若p-rtag=0 s为p的右子树的中序遍历序列的第一个结点，即右子树最左下结点EABCDFIJHGK求结点p的前驱：1.若 p-ltag=1 则 q=p-lchild;2.若p-rtag=0 q为p的左子树的中序遍历序列的第一个结点，即左子树最右下结点6.6树、森林与二叉树的转换森林与树相互递归定义森林：m棵互不相交的树的集合。树：树是一个二元组Tree=(root，F),root是根，F是m(m0)棵树的森林，F=T1,T2,Tm其中Ti=(ri，Fi)称为根的第i棵子树；当m!=0时，在树根和其子树森林之间存在下列关系：RF=|i=1,2,m,m0 6.6树、森林与二叉树的转换（续）树与二叉树的转换目的：利用二叉树运算来简化树和森林上的运算；依据：树与二叉树具有相同的二叉链表存储结构；EABCDFIABDECIFEABCDFIJHGKABDECIFKJGH6.6树、森林与二叉树的转换（续）EABCDFIJHGKEABCDFHGKIJ6.6树、森林与二叉树的转换（续）6.7二叉树的应用哈夫曼树(Huffman Tree)结点之间路径长度：树中两个结点之间的分支构成这两个结点的路径，路径上的分支数目为路径长度。树的路径长度：树根到每个结点的路径长度之和。结点的带权路径长度：该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，记为：WPL=w1k1+w2k2+wiki+wnkn。最优二叉树（哈夫曼树）：设n个权值w1,w2,wn,构造一棵有n个叶子结点的二叉树，每个叶子结点带权wi,则其中带权路径长度WPL最小的二叉树称为最优二叉树（哈夫曼树）。6.7二叉树的应用（续）哈夫曼算法(Huffman Algorithmic)输入：n个权值w1,w2,wn ；输出：一棵哈夫曼树算法：步骤一：根据给定的n个权值w1,w2,wn 构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti 中只有一个带权为wi 的根结点，其左右子树均为空。步骤二：在F中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。步骤三：在F中删除这两棵树，同时将新得到的二叉树加入F中。步骤四：重复步骤二与三，直到F只含有一棵树为止。给定权的集合:15,3,14,2,6,9,16,176.7二叉树的应用（续）哈夫曼算法(Huffman Algorithmic)15,3,14,2,6,9,16,1715,5,14,6,9,16,1715,11,14,9,16,1715,14,20,16,1729,20,16,1729,20,3349,33829496161782325141511202933WPL=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=2296.7二叉树的应用（续）哈夫曼编码(Huffman Code)等长编码：每个被编码对象的码长相等。优点：码长等长，易于解码；缺点：被编码信息总码长较大，尤其是当存在 许多不常用的被编码对象时前缀编码：任一个被编码对象的编码都不是另一个 被编码对象的编码的前缀。优点：当存在被编码对象使用概率不同时，被 编码信息总码长可以减小；缺点：码长不等长，不易于解码6.7二叉树的应用（续）哈夫曼编码(Huffman Code)-前缀编码 利用二叉树来设计二进制的前缀编码：被编码对象出现在二叉树的叶子结点。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点对应对象的编码。baedcf0000011111a(00)b(010)c(0110)d(0111)e(10)f(11)这种编码的译码过程从根开始。沿着某条分支走到叶子结点时，走过的二进制字符串即译为该叶子结点对应的对象。然后循环扫描总编码后的字符串。6.7二叉树的应用（续）哈夫曼编码与译码 利用哈夫曼算法可以得到总码长最短的二进制前缀编码，即为哈夫曼编码。设某次编码应用中不同被编码对象有n种，以此n种被编码对象出现的频率作权，构造出的哈夫曼树即为这n种对象的编码树，由此可得到其二进制的前缀编码。假定用于通讯的电文如下，现在要对其编码，采用哈夫曼编码。写出编码后的二进制串。电文：castcatssatatatasac(110)a(0)s(111)t(10)Set=c,a,s,tW=2,7,4,5电文编码：11001111011001011111101001001001110518711642000111csat4.数组5.广义表6.树和二叉树7.图教学内容-第七章ADT Graph 数据对象：V=具有相同性质的数据元素数据关系：R:R=VRVR=|v,w属于V且P(v,w),是从v到w的一条弧，谓词P(v,w)定义了弧 的意义或信息 基本操作：P:CreateGraph(&G,V,VR);DFSTraverseGraph(G,v,Visit();BFSTraverseGraph(G,v,Visit()ADT Graph7.1图的逻辑结构图的抽象数据类型7.1图的逻辑结构（续）基本概念和术语 顶点(Vertex)、弧(Arc)、有向图(Digraph)、边(Edge)、无向图(Undigraph)、完全图(Completed graph)、有向完全图、稀疏图(Sparse graph)、权(Weight)、网(Network)、子图(Subgraph)、邻接点(Adjacent)、（顶点的）度(Degree)、（顶点的）入度(InDegree)、（顶点的）出度(OutDegree)、（顶点之间）路径(Path)、（顶点之间）路径长度、回路或环(Cycle)、简单路径、简单回路（简单环）、（顶点之间）连通、连通图(Connected Graph)、连通分量(Connected Component)、强连通图、强连通分量、（连通图的）生成树：（有向图的）生成森林 0 1 0 1 0 1 0 1 0 1 G1.arcs=0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 7.2树的存储结构（续）数组表示法V3V1V2V5V4G1V1V2V4V3G2 0 1 1 0 0 0 0 0G2.arcs=1 0 0 1 1 1 1 07.2图的存储结构（续）邻接表-图的链式存储基本思路：对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个表结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置；链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息。头结点由两个域组成：链域(firstarc)指向链表中第一个结点；数据域(data)存储顶点vi信息。头结点以顺序结构形式存取，以便随机访问任一顶点的链表。Adjvex nextarc infodatafirstarc表结点头结点7.2图的存储结构（续）V10V21V32V43V54212042031431V3V1V2V5V4G1V1V2V4V3G2V10V32V21V433003230V10V21V32V4330221207.2图的存储结构（续）邻接表-图的链式存储邻接表的优点：边（或弧）稀疏时，节省空间；和边（或弧）相关的信息较多时，节省空间；容易求得当前顶点的第一个邻接点、下一个邻接点。对有向图，也可建立逆向邻接表，即对每个顶点建立一个链接以该顶点为头的弧的表。7.3图的遍历遍历图在图中查找具有某种特征的结点需要对结点进行访问（处理、输出等）操作图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础 图的遍历(Traversing Graph)：从图的某一个顶点出发，按照某条路径访问每个结点,使得每个结点均被访问一次，而且仅被访问一次。遍历本质：结点之间非线性关系线性化的过程遍历思路：*深度优先：类似于树的先根遍历；*广度优先：类似于树的层次遍历。7.3图的遍历（续）深度优先搜索遍历思路：从图的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。这是一个递归算法，遍历过程中，当某个顶点的所有邻接点都被访问到后，需要“回朔”，即沿着调用的逆方向回退到上一层顶点，继续考察该顶点的下一个邻接点。Boolean visitedMAX;/访问标志数组Status(*VisitFunc)(int v);/函数变量Void DFSTraverse(Graph G,Status(*Visit)(int v)VisitFunc=Visit；/使用全局变量VisitFunc，使DFS不必设函数指针参数 for(v=0;vG.vexnum;+v)visitedv=FALSE;/标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);Status DFS(Graph G,int v)/从第v个顶点出发递归地深度优先遍历图G，对每个元素调用函数Visit visitedv=TRUE;VisitFunc(v);/访问第v个顶点 for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/算法时间复杂度与存储结构相关邻接矩