北京邮电大学-数据结构讲义课件

数据结构

数据结构

1题型(1)基本概念40选择和判断，20个左右简答或给定实例执行算法30（5-6个题目）概念或者某些数据结构的性质例如：霍夫曼编码直接插入/冒泡/快速/选择/堆排序等算法的执行链地址法哈希表装填根据二叉树遍历结果画出树关于图的算法执行，等等题型(1)基本概念402题型(2)算法设计题30常见题型的范围（2-3题目)简单题目（数组，单层或双层循环，条件判断）单向链表或双向链表操作（插入/删除/转置/合并）二分查找，简单排序算法的实现二叉树（复制，相等，相似等，使用简单递归算法）题型(2)算法设计题303第一章绪论第一章绪论4基本概念基本概念5学习数据结构的意义是为研究和解决如何有效地组织和处理非数值数据而产生的理论、技术和方法。是计算机科学中的一门综合性的专业基础课。涉及计算机软件、硬件以及数学等学习数据结构的意义是为研究和解决如何有效地组织和处理非数值数6基本术语数据被计算机加工处理的对象。数据元素（记录、表目）数据的基本单位，是数据集合中的一个有意义的个体。数据项一个数据元素可由若干个数据项组成。

组合项年月日学号姓名班号性别出生日期入学成绩原子项基本术语数据被计算机加工处理的对象。组合项年月日学7基本术语2数据对象是性质相同的数据元素的集合，是数据的一个子集。

学号姓名班号性别出生日期入学成绩

001刘影01女19840417623002李恒01男19831211679003陈诚02男19840910638………………数据结构具有结构的数据元素的集合。它包括数据元素的逻辑结构、存储结构和相适应的运算。数据元素基本术语2数据对象是性质相同的数据元素的集合，是数据的一8数据元素之间的逻辑关系，与计算机无关。可用一个二元组表示：Data_Structure=(D,R)D：数据元素的有穷集合，R：集合D上关系的有穷集合。

[例]

设有数据结构B=(D,R)，其中D={d1,d2,d3,d4,d5,d6}，

R={r}，

r={<d1,d2>,<d1,d3>,<d1,d4>,<d3,d5>,<d3,d6>}，试画出其逻辑结构图。d1d2d3d4d5d6逻辑结构数据元素之间的逻辑关系，与计算机无关。d1d2d39（以班级学生关系为例）(1)集合结构数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构数据元素之间存在一对一的关系。(3)树型结构数据元素之间存在一对多的关系。(4)图状结构或网状结构

数据元素之间存在多对多的关系。成员关系长幼关系管理关系朋友关系四种基本的逻辑结构（以班级学生关系为例）成员关系长幼关系管理关系朋友关系四种基10数据的逻辑结构数据的逻辑结构11存储结构：数据的逻辑结构在计算机中如何表示。数据元素的映象用二进制位(bit)的位串表示数据元素。每个数据元素的映象称为结点每个数据项的映象称为数据域关系的映象两种基本方法及其组合使用。顺序映象：以相对的存储位置表示关系链式映象：以附加信息(指针)表示关系注意：数据的逻辑结构和存储结构的关系可以用数组等线形存储的方式存储逻辑上的树形结构也可以用树状的复杂的存储结构来存储逻辑上的集合关系以达到提高检索速度的目的数据的存储结构存储结构：数据的逻辑结构在计算机中如何表示。数据的存储结构12

数据的逻辑结构+运算的定义-------面向用户，需求分析（抽象数据类型）概念层数据的存储结构+运算的实现-------面向计算机

实现层数据的逻辑结构与存储结构数据的逻辑结构与存储结构13抽象数据类型抽象数据类型(ADT)一个数学模型以及定义在该模型上的一组操作“抽象”是指数据类型的数学抽象特性，其定义仅仅取决于它的一组逻辑特性，而与在计算机内部的表示和实现无关抽象数据类型抽象数据类型(ADT)14算法和算法分析算法和算法分析15算法的概念建立在数据结构基础上的、求解问题的一系列确切的步骤。一个算法必须满足以下五个重要特性有穷性：对任何合法输入执行有穷步后能结束。确定性：每条指令必须有确切的含义。可行性：算法的每一条指令均能执行。输入：有零个或多个输入。输出：有一个或多个输出。算法的概念和特性算法的概念算法的概念和特性16正确性（最重要的标准）算法应满足具体问题的需求对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果健壮性算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果可读性算法应该好读。以有利于阅读者对程序的理解和维护高效性：时间复杂度算法执行占用的CPU时间，随问题规模n的变化函数高效性：空间复杂度算法执行占用的内存总量，随问题规模n的变化函数评价算法优劣的基本标准正确性（最重要的标准）评价算法优劣的基本标准17算法效率的度量时间复杂度空间复杂度算法效率的度量时间复杂度18算法执行的时间事后统计的方法先运行依据算法的程序所得时间的统计量依赖于计算机的硬件、软件等环境因素收集此算法的执行时间和实际占用空间的统计资料。事前分析估算的方法求出该算法的一个时间界限函数；算法执行的时间事后统计的方法19时间复杂度n问题规模，一般为数据的输入量f(n)算法中基本操作重复执行的次数—频度是问题规模n的某个函数算法的时间量度、时间复杂度算法中各语句的频度之和T(n)T(n)=O(f(n))随问题规模的增大，执行时间的增长率和f(n)的增长率相同时间复杂度n20时间复杂度曲线常见的时间复杂度：

O(1),O(log2n),O(n),O(nlog2n),O(n2),O(n3),O(2n)O(1)<O(log2n)＜O(n)＜O(nlog2n)＜(n2)＜O(n3)＜＜O(2n)时间复杂度曲线常见的时间复杂度：21空间复杂度算法所需存储空间的度量记作：S(n)=O(f(n))其中n为问题的规模(或大小)存储密度d=数据本身存储量/实际所占存储量空间复杂度22第二章线性表第二章线性表23线性结构的特点在数据元素的非空有限集中存在唯一的一个被称为“第一个”的数据元素存在唯一的一个被称为“最后一个”的数据元素除第一个之外，集合中每个数据元素均只有一个前驱除最后一个之外，集合中每个数据元素均只有一个后继线性结构的特点在数据元素的非空有限集中24

顺序表

顺序表25线性表的顺序存储结构bb+lb+2l…b+(i-1)l…b+(n-1)l顺序存储空间的获得：静态数组在源程序中指定大小，编译时确定运行时存储空间尺寸不可增减有效数据限制在0-n顺序存储空间的获得：动态申请运行时通过malloc函数动态申请指定大小的存储空间可以通过realloc函数扩充或者缩小存储空间大小，但是，可能需要内存拷贝操作（开销大）可以通过free函数释放申请的空间线性表的顺序存储结构bb+lb+2l26线性表的顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充线性表的顺序存储结构的优缺点优点27线性表的单向链式存储线性表的单向链式存储28线性表的链式存储结构与实现线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素数据元素可零散地分布在内存的任何位置上链式存储结构的特点链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。结点之间的相对位置由链表中的指针域指示，而结点在存储器中的存储位置是随意的。线性表的链式存储结构与实现线性表的链式存储结构29线性表的链式存储结构结点的组成数据域存放数据元素的值。指针域（链域）单向链表的每个结点都只有一个指针域。存放下一个结点（直接后继）的地址。通过链域，可将n个结点按逻辑顺序链接在一起（不论其物理次序如何）。数据域指针域线性表的链式存储结构结点的组成数据域30单链表的类型定义typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;不带头节点的单链表

structLNode*L;或者

LinkListL;

如果L为NULL标志空链表，否则，L为指向链表首个元素的指针单链表的类型定义typedefstructLNode{31带头节点的单链表头结点在单链表的第一个结点之前附设的结点；为了确定链表中第一个结点的位置而设立；数据域可以不存储任何信息，也可以存放关于线性表的附加信息，如长度等；尾结点指针域为空（无后继），用NULL表示。带头节点的单链表32带头结点的单链表插入运算具体操作X②

S

①③

④

P带头结点的单链表插入运算具体操作X②S33带头结点的单链表插入算法将元素e插入到p节点之后s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;

带头结点的单链表插入算法将元素e插入到p节点之后34带头结点单链表的删除算法具体操作存储池pq带头结点单链表的删除算法具体操作存储池p35带头结点单链表的删除算法删除p节点之后的节点q=p->next;if(q!=NULL){p->next=q->next;free(q);}带头结点单链表的删除算法删除p节点之后的节点36不带头单链表的转置

pre=NULL;p=head;while(p!=NULL){t=p->next;p->next=pre;pre=p;p=t;}head=pre;

不带头单链表的转置pre=NULL;37单链表的缺点获取节点P的前驱的算法删除节点p的算法替换节点p的算法在节点p之前插入新节点的算法单链表的缺点获取节点P的前驱的算法38线性表的双向链式存储线性表的双向链式存储39双向链表双链表的定义：每个节点有两个指针typedefstructDuLNode{ElemTypedata; structDuLNode*prior; structDuLNode*next;}DuLNode,*DuLinkList;结点的物理表示双向链表双链表的定义：每个节点有两个指针结点的物理表示40带头结点双向循环链表的插入将新元素e插入到双向链表中p节点前s=(DuLNode*)malloc(sizeof(DuLNode));s->data=e;s->prior=p->prior; p->prior->next=s;s->next=p;p->prior=s;带头结点双向循环链表的插入将新元素e插入到双向链表中p节点前41带头结点双向循环链表的删除删除节点pp->prior->next=p->next;p->next->prior=p->prior;free(p);带头结点双向循环链表的删除删除节点p42第三章栈和队列第三章栈和队列43插入和删除操作受限的线性表栈和队列都是线性表，只是在操作上做了限制栈（stack）后进先出(LIFO:LastInFirstOut)的线性表表头端称为栈底（bottom）表尾端称为栈顶（top）插入和删除都在栈顶进行队列（queue）先进先出(FIFO:FirstInFirstOut)的线性表表头端称为队头（front）表尾端称为队尾（rear）插入在队尾进行，而删除则在队头进行插入和删除操作受限的线性表栈和队列都是线性表，只是在操作上做44栈的定义和基本操作栈的定义和基本操作45栈的基本操作InitStack(&s)初始化堆栈StackEmpty(s)判断堆栈是否空push(s,e)将元素e压入堆栈pop(s,&e)弹出栈顶元素栈的基本操作InitStack(&s)46栈的存储结构两种方式顺序表方式（常用）链表方式顺序表方式的堆栈类型定义#defineSTACK_SIZE128ElemTypestack[STACK_SIZE];inttop;堆栈容量的设计：根据算法需要，分析算法的空间复杂度编号系统0~(n-1)，top记载下个空位位置，或者说，元素个数栈满和栈空（“上溢”与“下溢”）栈的存储结构两种方式47顺序表方式的堆栈操作#defineInitStack()top=0#defineStackEmpty()(top==0)Statuspush(elemTypee){if(top==STACK_SIZE)returnERROR;stack[top++]=e;returnOK;}

顺序表方式的堆栈操作#defineInitStack()48顺序表方式的堆栈操作Statuspop(elemType&e){if(top==0)returnERROR;e=stack[--top];returnOK;}顺序表方式的堆栈操作Statuspop(elemType49栈的链式存储结构以及操作存储结构设计不带头的单链表类型定义structNODE{ElemTypedata;structNODE*next;};structNODE*stack;操作算法InitStackClearStack:释放所有节点其他操作：Push,Pop，StackEmpty栈的链式存储结构以及操作存储结构设计50队列队列51队列的定义队列是一种特殊的线性表限定插入和删除操作分别在表的两端进行具有先进先出(FIFO—FirstInFirstOut)的特点。队列的定义队列是一种特殊的线性表52队列的操作主要操作增加（入队）EnQueue(Q,e);删除（出队）DeQueue(Q,&e);判断队列是否为空QueueEmpty(Q)其他操作初始化队列InitQueue(Q)获取队列长度QueueLength(Q)清除队列中的所有元素ClearQueue(Q)队列的操作主要操作53队列的存储结构和实现链表方式顺序表方式队列的存储结构和实现链表方式54链式队列链式队列55链式队列的其它算法存储结构单链表，双向循环链表，带头节点插入算法，删除算法求队列长度遍历队列中现有所有元素链式队列的其它算法存储结构56使用顺序表方式实现队列使用顺序表方式实现队列57循环队列(1)存储结构使用静态的数组或者动态申请的连续存储空间(顺序表)队列描述队头队尾基本算法增加元素:“假溢”现象，解决方法：循环队列删除元素循环队列(1)存储结构58循环队列(2)“上溢”与“下溢”的条件：队列满和队列空的表示方法方法一：浪费一个存储空间，以(rear+1)%N==front判断队列满方法二：设置队列中的数据元素计数或者队满标志循环队列(2)59第五章数组和广义表第五章数组和广义表60数组数组61数组的顺序表示和实现二维数组的顺序存储方式行优先顺序列优先顺序根据数组下表(i,j)检索顺序表中元素K的方式数组的顺序表示和实现二维数组的顺序存储方式62数组的顺序存储方式（续）多维数组行优先顺序规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序规定为先排最左下标，从左向右，最后排最右下标。数组的顺序存储特点只要已知开始结点的存放地址（即基地址）、数组维数、每维的上、下界，和每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数；数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。例：数组：ElemTypeA[m][n];addr(A[i][j])=Base(A)+((i*n)+j)*sizeof(ElemType);addr(A[i][j])=Base(A)+((j*m)+i)*sizeof(ElemType);数组的顺序存储方式（续）多维数组63稀疏矩阵稀疏矩阵非零元素很少，分布没有规律；设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），则称A为稀疏矩阵；令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵；在压缩存储时需要同时存储非零元素的下标和值；可用三元组存储（行号，列号，值）。

0120000

100030

000500

000000

020006ijv1212211253345522566A稀疏矩阵稀疏矩阵012000064广义表广义表65广义表的定义广义表又称列表，其每一个元素的结构都可能是不同的；是n(n≥0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表；通常记作LS=(a1,a2,a3,…,an)LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。第一个元素a1称为表LS的表头（head），由余下元素组成的表(a2,a3,...,an)称为LS的表尾（tail）。广义表中括号的重数称为广义表的深度。广义表的定义广义表66

广义表的长度和深度((),(e),(a,(b,c,d)),(f,g))长度4，深度3广义表的长度和深度((),(e),(a,(b,c,d))67

广义表操作广义表的长度和深度(P108,p113)((),(e),(a,(b,c,d)),(f,g))长度4，深度3head与tail操作(p108)A=(a,(b,c))Head(A)aB=Tail(A)((b,c))C=Head(B)(b,c)Tail(B)()Head(C)bD=Tail(C)(c)Head(D)cTail(D)()L=((a,b,c),(e,f,g))取出元素fHead(Tail(Head(Tail(L))))L=((a,b,c),x,(u,t,w))取出元素tHead(Tail(Head(Tail(Tail(L)))))广义表操作广义表的长度和深度(P108,p113)68第六章树和二叉树第六章树和二叉树69树的定义和基本术语树的定义和基本术语70树的定义树是一类重要的非线性数据结构，是以分支关系定义的层次结构；树是n(n≥0)个结点的有限集，非空树满足：有且仅有一个特定的称之为根(root)的结点；除根以外的其余结点可分为m(0m<n)个互不相交的子集T1,T2,T3…Tm，其中每个子集本身又是一棵树，且称为根的子树。树的定义树是一类重要的非线性数据结构，是以分支关系定义的层次71树的一些基本术语结点的度（degree）结点所拥有的子树的数目。叶子结点（leaf--又称终端结点terminalnode）度为零的结点。分支结点（branchnode）度不为零的结点孩子（child）结点的子树的根称为结点的孩子。树的一些基本术语结点的度（degree）72树的一些基本术语(续)双亲（parent）结点是其孩子的双亲。祖先（forefather）从树根到双亲的所有结点称为该结点的祖先。子孙（progeny）以结点为根的子树的所有结点称为该结点的子孙。兄弟（sibling）同一父母的所有孩子互称兄弟。层次（level）树根为第一层，其孩子为第二层，孙子为第三层，以此类推。树的一些基本术语(续)双亲（parent）73树的一些基本术语(续)堂兄弟（cousin）双亲在同一层的结点互称堂兄弟。深度（depth）树中结点的最大层次称为树的深度。有序树（orderedtree）结点各子树从左至右是有秩序的树称为有序树。无序树（unorderedtree）结点各子树没有秩序的树称为无序树。森林（forest）森林是m(m≥0)棵互不相交的树的集合。树的一些基本术语(续)堂兄弟（cousin）74二叉树二叉树75二叉树的定义(1)定义二叉树是n(n0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和两棵互不相交的左子树和右子树的二叉树组成。二叉树的特点：定义是递归的；0结点的度2；是有序树。二叉树的定义(1)定义76二叉树的定义(2)二叉树的五种基本形态两种特殊的二叉树满二叉树：每一层上的结点数都是最大结点数完全二叉树：只有最下面两层结点的度可小于2，而最下一层的叶结点集中在左边若干位置上123456712345678910二叉树的定义(2)二叉树的五种基本形态1277二叉树的性质(1)性质1二叉树的第i层上至多有2i-1(i1)个结点。性质2深度为k的二叉树至多有2k-1个结点(k1)。二叉树的性质(1)性质178二叉树的性质(2)性质3对任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2

，则n0=n2+1证明设度为1的节点数为n1，结点总数为nn=n0+n1+n2(1)除根节点外，每个节点都有一个分支射入，设分支数为B，有：B=n+1 (2)所有分支由非叶子节点射出，有B=n1+2n2(3)由(1)(2)(3)得：n0=n2+1二叉树的性质(2)性质379二叉树的性质(3)性质4具有n个结点的完全二叉树的深度为log2n+1。二叉树的性质(3)性质480二叉树的性质(4)性质5对一棵具有n个结点的完全二叉树，对其结点按层从上至下(每层从左至右)进行1至n的编号，则对任一结点i(1in)有：若i=1，则i是根，无双亲；若i>1，则i的双亲是i/2。若2i>n，则i无左孩子;否则，i的左孩子是2i。若2i+1>n，则i无右孩子;否则，i的右孩子是2i+1。123456712345678910二叉树的性质(4)性质5123481二叉树的存储结构(1)顺序存储结构按完全二叉树存储（可以用数组这样线性的存储结构存储一个非线性的数据结构）#defineMaxTreeSize128typedefTElemTypeSqBiTree[MaxTreeSize];SqBiTreebt;ABCDEF1234567ABDEFC二叉树的存储结构(1)顺序存储结构#defineMaxT82二叉树的存储结构(2)顺序存储结构用父母指针存储存储结点数据和其父结点的序号ABCDEF011233123456ABDEFC#defineMaxTreeSize100typedefstructNode{ Telemtypedata; intparent;}Node;typedefNodebTree[MaxTreeSize];

二叉树的存储结构(2)顺序存储结构ABCDEF011233183二叉树的存储结构(3)链式存储结构用二叉链表存储链式存储结构用三叉链表存储

A^^B^

C^^D^E^bt

A^B^

C^^D^E^bt二叉树的存储结构(3)链式存储结构链式存储结构A84二叉树的存储结构(4)二叉链表的类型定义typedefstructBiTNode{ TElemTypedata；structBiTNode*lchild；

structBiTNode*rchild；}BiTNode,*BiTree；性质：有N个节点的二叉树共有N+1个空指针，N-1个非空指针。三叉链表的类型定义typedefstructTriTNode{ TElemTypedata；structBiTNode*lchild；

structBiTNode*rchild；

structBiTNode*parent；}TriTNode,*TriTree；二叉树的存储结构(4)二叉链表的类型定义三叉链表的类型定义85遍历二叉树遍历二叉树86遍历二叉树遍历二叉树指按某条搜索路线走遍二叉树的每个结点，使得树中每个结点都被访问一次，且仅被访问一次。根据搜索路径的不同，二叉树的遍历分为八种：1、前序遍历（preordertraversal）DLR2、中序遍历（inordertraversal）

LDR3、后序遍历（postordertraversal）LRD4、逆前序遍历（inverse

preordertraversal）DRL5、逆中序遍历（inverse

inordertraversal）RDL6、逆后序遍历（inverse

postordertraversal）RLD7、按层次遍历（level-by-leveltraversal）8、按层次逆遍历（inverselevel-by-leveltraversal）√√√√遍历二叉树遍历二叉树根据搜索路径的不同，二叉树的遍历分为八种87遍历方法先序遍历：ABDEC中序遍历：DBEAC后序遍历：DEBCAABCDE遍历二叉树示例ABDEFC1.ABDCEF2.DBAECF3.DBEFCA4.ACFEBD5.FCEABD6.FECDBA7.ABCDEF8.ACBFED1-前序2-中序3-后序4-逆前序5-逆中序6-逆后序7-层次8-层次逆遍历方法ABCDE遍历二叉88利用遍历结果确定二叉树问题先序序列+中序序列中序序列+后序序列先序序列+后序序列(x，为什么？)

先序序列:ABCDEFGH

中序序列:BDCEAFHGABFCGDEH思考：层序+先序/中序/后序，能否确定？如何做？利用遍历结果确定二叉树问题(1)例如：层序ABCDEFGHIJ,中序DBGEHJACIF

例如：中序ABCDEFGHIJ,后序ACDBHJIGFE利用遍历结果确定二叉树问题ABFCGDEH思考：层序+先序/89利用遍历结果确定二叉树问题(2)一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，求出空格处的内容，并画出该二叉树先序：_H_A_DIKC_B中序：J_FADG_KEI_后序：_F_AHCE_B_G先序：_

H_A_D

IKC_B中序：J_FAD

G

_KEI_

后序：_F_AH

CE_B_

G利用遍历结果确定二叉树问题(2)一棵二叉树的先序、中序和后序90voidPreorder(BiTreet){if(t){visit(t);Preorder(t->lchild);Preorder(t->rchild);}}voidInorder(BiTreet){if(t){Inorder(t->lchild);visit(t);Inorder(t->rchild);}}voidPostorder(BiTreet){if(t){Postorder(t->lchild);Postorder(t->rchild);visit(t);}}遍历二叉树的递归算法voidPreorder(BiTreet)voidIn91判断两个二叉树是否相等(相似）类似的其他递归式二叉树算法(1)intcheck(BiTreea,BiTreeb){if(a==NULL)returnb==NULL;if(b==NULL)return0;

if(a->data!=b->data)return0;returncheck(a->lchild,b->lchild)&&check(a->rchild,b->rchild);}交换二叉树的左右子树）voidswap(BiTreet){if(t==NULL)return;

tmp=t->lchild;t->lchild=t->rchild;t->rchild=tmp;swap(t->lchild);swap(t->rchild);}判断两个二叉树是否相等(相似）类似的其他递归式二叉树算法(192类似的其他递归式二叉树算法(2)拷贝二叉树BiTreebtcopy(BiTreet){if(t==NULL)returnNULL;

p=malloc(sizeof(*BiTree));p->data=t->data;p->lchild=btcopy(t->lchild);p->rchild=btcopy(t->rchild);returnp;}类似的其他递归式二叉树算法(2)拷贝二叉树BiTreebt93树和森林树和森林94树的存储结构：双亲表示法ABCDEFG^001033０123

456ABCEFGD

存储方法：使用顺序结构#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;}PTNode;/*节点的存储结构*/typedefstruct{/*顺序存储结构*/PTNodenodes[MAX_TREE_SIZE];intr,n;/*根位置和节点数*/}PTree;优点：简单，紧凑，易于寻找双亲节点缺点：查询某节点的孩子效率低树的存储结构：双亲表示法ABCDEFG^001033０195树的存储结构:孩子兄弟表示法孩子兄弟表示法A∧B∧CD∧∧E∧∧F∧G∧ABCEFGD树的存储结构:孩子兄弟表示法孩子兄弟表示法A∧B∧CD∧∧E96森林与二叉树的转换转换原则按孩子兄弟表示法进行转换。树与二叉树的转换DE森林与二叉树的转换转换原则DE97森林与二叉树的转换森林与二叉树的转换98赫夫曼树及其应用赫夫曼树及其应用99赫夫曼树及其应用赫夫曼树最优树；是一类带权路径长度最短的树；路径长度指树中两个结点间路径上所含有的分支数目。树的路径长度指从树根到每一结点的路径长度之和。带权路径长度指结点的路径长度与该结点的权之积。赫夫曼树及其应用赫夫曼树100赫夫曼树树的带权路径长度树中所有叶子结点的带权路径长度；最优二叉树或赫夫曼树。WPL最小的二叉树。赫夫曼树树的带权路径长度101赫夫曼树的构造根据给定的n个权值{w1,w2,...wn}构成n棵二叉树的集合F={T1,T2,...,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空；在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中；重复2和3，直到F中只含一棵树为止；这棵树就是赫夫曼树；性质：所有节点的度要么为0，要么为2；不一定是完全二叉树；子树也是赫夫曼树赫夫曼树的构造根据给定的n个权值{w1,w2,...wn}构102[例]

w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100赫夫曼树构造举例1[例]w={5,29,7,8,14,23,3103例：已知字符A、B、C、D、E、F、G，使用频度分别为：0.25、0.1、0.15、0.06、0.3、0.05、0.09，试以此构造霍夫曼树。GB0.19A0.44FD0.11C0.26E0.5611、0.250.10.150.060.30.050.092、0.250.10.150.30.09

0.11

3、0.250.150.30.11

0.19

4、

0.250.30.19

0.265、0.3

0.26

0.446、0.440.567、1.00赫夫曼树构造举例2例：已知字符A、B、C、D、E、F、G，使用频度分别为：0104GBAFDCE000000111111A:01B:001C:101D:1001E:11F:1000G:000E:100A:000B:001C:010D:011F:101G:110000000111111GBAFDCE0赫夫曼编码等长编码WPL霍夫曼编码

=2.56WPL等长编码

=3

利用赫夫曼编码可提高效率：(3-2.56)/3≈15%赫夫曼编码GBAFDCE000000111111A:01B:105赫夫曼编码的特点不等长编码

赫夫曼编码是不等长编码前缀编码赫夫曼编码是前缀编码，即任一编码都不是另一字符编码的前缀发送过程（编码）根据由赫夫曼树得到的编码表送出字符数据接收过程（解码）按左0、右1的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束赫夫曼编码的特点不等长编码106第七章图第七章图107本章内容定义和术语存储结构：邻接矩阵、邻接表，十字链表，邻接多重表两种遍历策略：深度优先搜索和广度优先搜索连通性和最小生成树拓扑排序和关键路径(AOV,AOE)求最短路径问题的解法本章内容定义和术语108图的基本概念图的基本概念109图的定义和术语(1)图G由两个集合V(G)和E(G)组成，记作G=(V,E)其中V(G)是顶点的非空有穷集合，E(G)是边的有穷集合，而边是顶点的无序对或有序对。112323423图的定义和术语(1)图G112323423110图的基本术语(2)顶点(vertex)数据元素所构成的结点通常称为顶点。弧(arc)若两个顶点间有关系<x,y>∈E，则称<x,y>为一条弧。弧头(又称终端点)若<x,y>为一条弧，则顶点y称为弧头。弧尾(又称初始点)若<x,y>为一条弧，则顶点x称为弧尾。边(Edge)无向图中两条弧<x,y>和<y,x>可用一条边(x,y)来表示。图的基本术语(2)顶点(vertex)111图的基本术语(3)顶点的度（degree）无向图：与顶点相关联的边数称为该顶点的度有向图：分为入度和出度顶点的入度（indegree）以顶点为头的弧数称为该顶点的入度。顶点的出度（outdegree）以顶点为尾的弧数称为该顶点的出度。路径（path）由顶点vi经过一系列边和顶点到达顶点vj所得到的顶点序列。回路（loop--又称环cycle）起点和终点为同一顶点的路径称为回路。ABCEFD图的基本术语(3)顶点的度（degree）ABCEFD112图的基本术语(4)简单路径(路径的顶点)序列中顶点不重复出现的路径。简单回路(简单环)除路径起点和终点相同外，其余顶点均不相同的回路。稀疏图边数很少的图(如e<nlogn)。稠密图边数很多的图。权(weight)有些图的边或弧具有一定的大小，称之为权。网带权值的图又称为网或网络。ABCEFD图的基本术语(4)简单路径ABCEFD113图的基本术语(5)子图由图的部分顶点和边组成的新图称为原图的子图。生成子图由图的全部顶点和部分边组成的子图称为原图的生成子图。邻接点若边(vi,vj)∈E，则vi与vj互为邻接点。图的基本术语(5)子图114图的基本术语(6)有向图若<x,y>∈E，并不总有<y,x>∈E，则称此图为有向图无向图若<x,y>∈E，总有<y,x>∈E，则称此图为无向图完全图具有n*(n-1)/2条边的无向图称为完全图。有向完全图具有n*(n-1)条弧的有向图称为有向完全图。图的基本术语(6)有向图115图的基本术语(7)生成树连通图的极小连通生成子图称为原图的生成树。生成森林由多棵有向树构成的有向图的生成子图称为生成森林。最小代价生成树连通网中由最小权值的边构成的生成树。图的基本术语(7)生成树116图的存储图的存储117图的存储结构：邻接矩阵数组表示法邻接矩阵ABCEFDAij={0(vi,vj)∈E1(vi,vj)∈EABCDEF000001101000000100000010010000000010ABCDEF#defineInfinityINT_MAXtypedefenum{DG,DN,AG,AN}GraphKind;typedefstructArcCell{VRTypeadj;InfoType*info;}ArcCell,AdjMatrix[20][20];typedefstructGragh{VertexTypevexs[20];intvtxnum,arcnum;AdjMatrixarcs;GraghKindkind;}Gragh;图的存储结构：邻接矩阵数组表示法ABCEFDAij={0118带权图的存储结构:邻接矩阵

邻接矩阵

32

45232542Aij={(vi,vj)∈E权值(vi,vj)∈EAB

CD带权图的存储结构:邻接矩阵邻接矩阵325119图的遍历图的遍历120图的遍历图的遍历按某种搜索顺序对图中每个结点访问且仅访问一次。遍历图的两种方式深度优先搜索DFS广度优先搜索BFS图的遍历图的遍历121深度优先搜索类似树的先根边历从某顶点v0

出发，访问该顶点依次从v0的未被访问过的邻接点中选取一个顶点作为新出发点;用同样的方法访问其它所有未被访问过邻接顶点若此时仍有顶点未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点；反复此过程，直至图中所有顶点均被访问过一遍为止。ABCEFGDHABFEHCDG深度优先搜索类似树的先根边历ABCEFGDHABFEHCDG122广度优先搜索类似树的按层次遍历从某顶点v0出发，访问该顶点依次访问v0的所有未被访问过的邻接点然后将所有这些邻接点作为新的出发点，用同样的方法访问其它所有顶点，直到所有与v0

连通的顶点均被访问到为止；若此时仍有顶点尚未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点；反复此过程，直至图中所有顶点均被访问过一遍为止。ABCEFGDHABCFHDGE广度优先搜索类似树的按层次遍历ABCEFGDHABCFHDG123最小生成树最小生成树124无向图的连通分量和生成树无向图的连通分量从图中任一顶点出发，一次调用深度或广度优先搜索所得到的顶点集即为连通分量中的顶点集。生成树连通分量中的节点，连同遍历时走过的边，构成图的生成树非连通图，多个生成树，形成生成森林无向图的连通分量和生成树无向图的连通分量125最小生成树定义由一个网络生成的各边的权数总和最小的生成树；构造算法Prim算法Kruskal算法最小生成树定义126Prim算法将图中顶点分为两个集合，其中集合X包含图的一个顶点v0，集合Y包含除v0

外的其它所有顶点；将跨接这两个集合的权值最小的边加入图中，并将其依附在该边的集合Y中的顶点v1

从Y中移入集合X中；反复过程2，直到集合Y为空，所得生成子图即为最小生成树。算法复杂性O(n2)ABCEFD2313221ABCEFD21321Prim算法将图中顶点分为两个集合，其中集合X包含图的一127拓扑排序与关键路径拓扑排序与关键路径128拓扑排序拓扑排序由某集合上的一个偏序得到该集合上的一个全序AOV网(ActivityOnVertex)有向边表示两个活动间的次序关系顶点表示活动这类图又称为顶点活动图，简称AOV图如用顶点表示课程，用弧表示某些课程是其它课程的先修课，则拓扑排序就是求在同时只能学习一门课程时的学习次序拓扑排序拓扑排序129拓扑排序的算法步骤扫描图中每个顶点，将入度为零的顶点入队列；从队列中取出一个顶点输出，并将其所有邻接点的入度减1，若入度减为零，则将该邻接点入队列

反复执行步骤2，直至所有顶点的入度均为零若该有向图是有环图，则不存在拓扑排序，就不可能输出全部顶点；否则就可以输出全部顶点。此特点可用来判断一个有向图是否存在回路。C1C2C3C6C4C5C7C8C9C10C1C2C3C4C5C6C7C8C9C10C2C1C3C4C5C6C7C8C9C10C1C2C4C3C5C6C7C8C9C10C2C1C4C3C5C6C7C8C9C10C1C2C5C4C3C6C7C8C10C9拓扑排序结果：拓扑排序的算法步骤扫描图中每个顶点，将入度为零的顶点入队列；130关键路径AOE图(ActivityOnEdge)顶点一般用来表示事件(状态)弧用来表示活动弧的权值表示活动所需时间AOE网的性质进入Vi的活动都结束，Vi所代表的事件才发生顶点Vi所代表的事件发生，从Vi出发的活动才能开始源点:入度为0的顶点，即工程的开始点汇点:出度为0的顶点，即工程的完成点关键路径影响整个工程进度的活动所组成的路径:从源点到汇点的最长路径，是完成该工程的最短时间减少这些活动所需时间，整个工程就可能提前完成关键活动关键路径上的活动会延长工期，关键活动的加快可能缩短工期关键路径AOE图(ActivityOnEdge)131关键路径举例V1V2V3V6V4V5V7V8V9V10a1=4a2=3a3=2a4=3a5=3a6=5a9=5a12=5a7=4a8=6a10=2a11=1a13=8a14=5如左图所示工程，其最后完工时间为21天。能否加快某些活动进度，使整个工期缩短呢？关键路径举例V1V2V3V6V4V5V7V8V9V10a1=132第九章查找第九章查找133基本概念基本概念134基本概念查找表由同一类型的数据元素构成的集合；静态查找表对查找表的查找仅是以查询为目的，不改动查找表中的数据。动态查找表可以在查找表中插入不存在的记录，或删除某个已存在的记录。关键字数据元素（或记录）的某个数据项，能用来标识一个数据元素。查找指定某个值，在查找表中确定是否存在一个记录，该记录的关键字等于给定值。基本概念查找表135基本概念（续）查找成功查找表中存在满足查找条件的记录。查找不成功查找表中不存在满足查找条件的记录。平均查找长度ASL——查找方法时效的度量为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。查找成功时的ASL计算方法：n：记录的个数pi：查找第i个记录的概率，(不特别声明时认为等概率pi=1/n)ci：找到第i个记录所需的比较次数基本概念（续）查找成功136顺序表的查找顺序表的查找137静态查找表顺序表的查找通常查找表中的各元素（或记录）的关键字的值是无序的。实际查找时，通常将给定值放在第0个记录处，然后从后向前查找，直到找到所查记录为止，找不到则返回结果0。因为记录0像哨兵一样看守着查找表下界，所以不会越界。typedefstruct{ KeyTypekey; DataTypedata;}ElemType;typedefstruct{ ElemType*elem; intlength;}SSTable;静态查找表顺序表的查找typedefstruct{138顺序表查找算法intseq_search(SSTablel,KeyTypekey){ for(i=0；i<l.length;i++)if(l.elem[i]==key)returni; return-1;}intseq_search(SSTablel,KeyTypekey){ l.elem[0].key=key; for(i=l.length;l.elem[i].key!=key;i--); returni;}顺序表查找算法intseq_search(SSTable139顺序表算法:采用链表结构structELEM*seq_search(KeyTypekey){for(p=head;p!=NULL;p=p->next)if(p->key==key)returnp; returnNULL;}structELEM*seq_search(KeyTypekey){tail->key=key;for(p=head;p->key!=key;p=p->next);returnp==tail?NULL:p;}顺序表算法:采用链表结构structELEM*seq_s140顺序表算法性能分析性能分析查找成功时ASLs(n)==(1+2+...+n)/n=(n+1)/2查找失败时ASLf=n+1顺序表算法性能分析性能分析141静态查找表有序表的查找有序表查找表中的各元素（或记录）的关键字的值是有序的。仍可用顺序查找，但在找不到时不需比较到表尾在等概率情况下，平均查找长度为：ASL成功

=(n+1)/2ASL不成功

=(n+2)/2有序表的查找更好的方法是折半查找静态查找表有序表的查找142折半查找折半查找143折半查找只有有序表才能用折半查找的方法将给定值与中间的记录进行比较；若找到则查找成功；否则若给定值比中间记录小，则对前一半子表进行折半查找，反之则对后一半子表进行折半查找。若在查找过程中，遇到查找子表的上界小于下界，则表示查找失败折半查找只有有序表才能用折半查找的方法144折半查找算法及性能分析intbinsearch(SSTableST,keytypekey){low=1;high=ST.length;while(low<=high) { mid=(low+high)/2; if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elem[mid].key)high=mid-1; elsehigh=mid+1;}return0;}查找性能分析折半查找每次只查表的一半，其所有记录的查找路径构成一棵二叉树，称为折半查找树（或判定树），每次查找只走了该树的一条分支，故平均查找长度不超过log2n+1折半查找算法及性能分析intbinsearch(SST145哈希表哈希表146哈希表哈希表一个有限的连续地址空间，用以容纳按哈希地址存储的记录。哈希函数记录的存储位置与它的关键字之间存在的一种对应关系。

Loc(ri)=H(keyi)冲突不同的两个关键字经过哈希函数运算后所得到的散列地址相同理想情况下没有冲突，查找复杂度O(1)一般考虑哈希表，冲突是不可避免发生的；同义词在同一地址出现冲突的各关键字。哈希(散列)地址根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。装填因子α=记录数/哈希表长度α>1必然冲突，α<<1也有可能冲突哈希表哈希表147哈希函数的构造方法直接定址法：H(key)=a*key+b，a、b为常数；数字分析法分析关键字，找出其中几位数字作散列地址（例如：指针值）除留余数法H(key)=keyMODp，p≤m，m为比散列表长度小的数p可以选用素数，更有利于“散列”，少冲突伪随机数法选取一个用关键字作为种子的伪随机数发生器生成散列地址哈希函数的构造方法直接定址法：148解决冲突的方法开放定址法再散列法链地址法散列表设立指针，将所有散列地址为此位置的关键字记录用单链表形式存储起来；公共溢出区法建立公共溢出区，将所有发生冲突的关键字记录存储到公共溢出区中去解决冲突的方法开放定址法149哈希表建立、查找举例有一组关键字序列(38、59、125、168、216、719、455、20)，用函数H(key)=keyMOD10将其按顺序散列到散列表HT(0:9)中，用链地址法，画出散列表，并分别求在等概率情况下查找成功和不成功的平均查找长度。哈希表建立、查找举例有一组关键字序列(38、59、125、1150链地址法ASL成功=—————————=——=1.37581181+1+2+1+1+2+1+2ASL不成功=——————————=——=1.81018102+1+1+1+1+3+2+1+3+30∧1∧2∧3∧4∧5∧6∧7∧8∧9∧38∧59∧125∧216∧20∧168∧719∧455∧链地址法ASL成功=—————————=——=1151第十章内部排序第十章内部排序152基本概念基本概念153基本概念排序排序又称分类，是计算机中很重要的操作，它是将一个数据元素（或记录）的任意序列排列成一个按关键字有序的序列。定义设有记录序列{R1、R2………..Rn}，其相应的关键字序列为{K1、K2………..Kn}；若存在一种确定的关系：Kx≤Ky≤…≤Kz，则将记录序列{R1、R2………..Rn}排成按该关键字有序的序列{Rx、Ry………..Rz}的操作，称之为排序。关系是任意的，如通常经常使用的小于、大于等关系。排序过程中的两种基本操作比较操作：比较两个关键字值的大小的操作。移动操作：将记录从一个位置移动到另一个位置的操作。基本概念排序154基本概念（续）排序方法稳定的排序方法若待排序列中存在两个或以上关键字相等的记录，设Ki=Kj(1≤i<j≤n)，即排序前Ri在Rj前，若在排序后Ri仍在Rj前，则称排序是稳定的简单的直接插入排序和冒泡排序都是稳定排序不稳定的排序方法待排序列中存在两个或以上关键字相等的记录，设Ki=Kj(1≤i<j≤n)，即排序前Ri在Rj前，若在排序后Rj却在Ri前，则称排序是不稳定稳定的希尔排序，快速排序和堆排序都是不稳定排序基本概念（续）排序方法155基本概念（续）排序的分类内部排序待排序列记录全部存放在计算机随机存储器中进行排序的过程称为内部排序。外部排序待排序列记录数量太大，不能全部存放在计算机随机存储器中，排序过程中需对计算机外存进行访问，这种排序过程称为外部排序。基本概念（续）排序的分类156基本概念（续）待排序列的三种存储结构顺序存储：存储在地址连续的一组存储单元中（以此为例）；链式存储：存储在地址不连续的一组存储单元（链表）中；地址存储：记录顺序存储，另设关键字和记录地址排序。基本概念（续）待排序列的三种存储结构157插入排序插入排序158直接插入排序一种简单的排序方法将记录一个个插入到已排序好的有序表中，从而得到长度增加的新的有序表。直接插入排序一种简单的排序方法159r[0]用作哨兵。共执行5遍操作。每遍操作：先将元素复制内容放入r[0]，再将本元素与已排序的序列从尾开始进行比较。在已排序的序列中寻找自己的位置进行插入，或者寻找不到，一直进行到哨兵为止，意味着本元素最小，应该放在r[1]。每进行一遍，排序的序列将增加一个元素。如果序列中有n个元素，那么最多进行n遍即可。e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将 其排序。结果仍保存在下标为1至5的元素之中。012362410612345插入排序直接插入排序160r[0]用作哨兵。共执行5遍操作。e.g:36、2直接插入排序算法Insert_sort()/*数据存于r[1]~r[N]*/{inti,j;for(i=2;i<=N;i++){if(r[i]<r[i-1]){r[0]=r[i];r[i]=r[i-1];