【文档说明】数据结构(c语言版)课件.ppt，共(283)页，2.242 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-44685.html

以下为本文档部分文字说明：

数据结构(C语言版)绪论1.绪论线性表2.线性表栈和队列3.栈和队列串4.串数组和广义表5.数组和广义表树和二叉树6.树和二叉树动态存储管理8.动态存储管理查找9.查找内部排序10.内部排序图7.图第1章绪论◼1-1什么是数据结构1-2基本概念和术语◼1

-2基本概念和术语◼1-3抽象数据类型的表示与实现◼1-4算法和算法分析主菜单主菜单1-1什么是数据结构◼用计算机解决具体问题需要经过的步骤（1）从具体问题抽象出适当的数学模（2）设计解数学模型的算法；（3）

编制、运行并调试程序，直到解决实际问题。例1-1．学生入学情况登记问题例1-1．学生入学情况登记问题学号姓名性别入学总分01丁一男44002马二男43503张三女43804李四男43005王五女44506赵六男42807钱七女43208孙八男43709

冯九女42610郑十女435图1.1学生入学情况登记示例例1-2．井字棋对奕问题例1-2．井字棋对奕问题图1.2井字棋对奕问题示例例1-3．教学计划编排问题例1-3．教学计划编排问题图1.3教学计划编排问题示例由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如

表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据的逻辑结构（a）集合结构（b）线性结构（c）树型结构（d）图形结构图1.4四类基本结构的示意图数据元素之间的逻辑关系，

称为数据的逻辑结构。一个数据的逻辑结构可以用二元组来表示：G=(D,R)其中：D是数据元素的集合；R是D上所有数据元素之间关系的有限集合。逻辑结构的描述例1-4．数据结构Line=（D，R)例1-4．数据结

构Line=（D，R)数据结构Line=（D，R）其中:D={01,02,03,04,05,06,07,08,09,10}R={r}r={<05,01>,<01,03>,<03,08>,<08,02>,<02,07>,<07,04>,<04,06>,<06,09>,<0

9,10>}1-2基本概念和术语◼1．数据（Data）◼2．数据元素（DataElement）◼3．数据项(DataItem)◼4．数据对象（DataObject）◼5．数据逻辑结构（DataStructure）例1-5．数据结构Tree=（D，R)例1

-5．数据结构Tree=（D，R)Tree=（D，R）其中:D={01,02,03,04,05,06,07,08,09,10}R={r}r={<01,02>,<01,03>,<01,04>,<02,05>,<02,

06>,<02,07>,<03,08>,<03,09>,<04,10>}01020803070605040910图1.5树形结构例1-6．数据结构graph=（D，R)例1-6．数据结构graph=（D，R)gra

ph=（D，R）其中:D={a,b,c,d,e}R={r}r={（a,b）,(a,d),（b,d）,（b,c）,（b,e）,（c,d）,（d,e）}badce图1.6图形结构数据的存储结构◼1．顺序存储◼2．链式存

储◼3．索引存储◼4．散列存储1-3抽象数据类型的表示与实现◼1.数据类型（DataType）是一个值的集合和定义在这个值集上的一组操作的总称。◼2.数据类型可分为两类：一类是原子类型，另一类则是结构类型。◼3.抽象数据类型（AbstructDataType，

简称ADT）是指一个数学模型以及定义在该模型上的一组操作。1-4算法和算法分析◼1.算法特性◼2.算法要求◼3.算法描述◼4.算法性能分析与度量算法特性◼1．有究性◼2．确定性◼3．可行性◼4．输入◼5.输出算法要求◼1．正确性◼2．可读性

◼3．健壮性◼4．高效率◼5.低存储算法描述◼1．自然语言◼2．流程图◼3．N-S结构图◼4．伪代码◼5.计算机语言算法性能分析与度量◼1．时间复杂度◼2．空间复杂度时间复杂度（Timecomplexity）时间复杂度:是指程序运行从开始到结束所需要的时间。分析方法:从算法中选取一种对于所研

究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。常见的渐进时间复杂度有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)空

间复杂度（Spacecomplexity）空间复杂度:是指程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括以下两部分：⑴固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结

构变量所占的空间。⑵可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。小结数据结构就是研究数据的逻辑结构、存储结构和运算方法的学科。数据的逻辑结构包括：集合、线性结构、

树形结构、图形结构四种类型。数据的存储结构包括：顺序存储、链式存储、索引存储、散列存储四种。算法的特性及评价算法的好坏标准时间复杂度与空间复杂度第2章线性表◼2-1线性表的类型定义2-2线性表的顺序表示与实现◼2-2线性表的顺序表

示与实现◼2-3线性表的链式表示与实现主菜单主菜单2-1线性表的类型定义◆线性表（LinearList）：是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。基本概念◼1．表长◼2．空表◼3．直接后继

◼4．直接前驱◼5.位序基本运算1.InitList(&L)初始化表2.ListLength(L)求表长3.GetElem(L,cur_e,&next_e)取表中元素4.LocateElem(L,e,compare())定位。5.ListInsert(&L,i,e)插入元素6.ListDel

ete(&L,i,&e)删除元素2-2线性表的顺序表示与实现◆1.线性表的顺序存储结构◆2.基本运算在顺序表上的实现◆3.插入和删除性能分析◼线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素(顺序

表)。◼地址关系:Loc(ai)=Loc(a１)+(i-1)*d1≤I≤n◼顺序表类型：Typedefstruct{ElemType*elem;//存储空间基址intlength；//当前长度intlists

ize；//当前分配的存储容量}SqList；线性表的顺序存储结构◼1.构造一个空线性表算法◼2.线性表的的插入算法◼3.线性表的的删除算法基本运算在线性表上的实现构造一个空线性表算法StatusInitList_Sq(SqList&L){//构造一个空线性表L.elem=(ElemType*)

malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;returnOK;}//InitList

_Sq线性表的插入算法序号元素序号元素112112213213321321424424528525630628742730877842977(a)(b)图2.1线性表插入前后的情况(a)插入前n=8;(b)插入后n=9。线性表的删除算法序号元素序号元素11211221321

3321321424425528528630630742742877(a)(b)图2.2线性表删除前后的情况(a)删除前n=8;(b)删除后n=7。顺序表上的插入运算，时间主要消耗在了数据的移动上，平均移动数据元素的次数：插入

算法性能分析+=+−=11)1(Eniiininp设：Pi=1/(n+1)，即为等概率情况，则：时间复杂度为Ｏ(n)顺序表上的删除运算，时间主要消耗在了数据的移动上，平均移动数据元素的次数：删除算法性能分析设：Pi=1/n，即为等概率情况，则

：时间复杂度为Ｏ(n)=−=niideinp1)(E+==−=−=−==11121)(1)(Eniniideninninp2-3线性表的链式表示与实现◆1.线性链表(单链表)◆2.循环链表◆3.双向链表线性链表

基本概念◼1．链式存储结构的特点◼2．结点（Node）◼3．线性链表◼4．头结点单链表基本运算◼1．建立单链表◼2．查找◼3．插入◼4．删除单链表的插入算法➢算法思想插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。➢具体步骤

：（1）找到ai-1存储位置p（2）生成一个数据域为x的新结点*s（3）新结点的指针域指向结点ai。（s->next=p->next）（4）令结点*p的指针域指向新结点(p->next=s)单链表的插入算法单链表的插入算法voidList

Insert(LinkListhead,inti,ElemTypee,){p=head;j=0;while(p&&j<i-1)(p=p->next;++j;)if(!p||j>i-1)returnERROR；s=(ListNode*)malloc(sizeof(List

Node));s->data=e;s->next=p->next;p->next=s;returnOK；}//ListInsert时间复杂度亦为O(n)单链表的删除算法➢算法思想删除运算是将表的第i个结点删去。➢具体步骤：（1）找到ai-1的存储位置p（因为在单链表中

结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）（2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）（p->next=p->next->next）（3）释放结点ai的空间，将其归还给"存储池"

。(free(q))单链表的删除算法单链表的删除算法voidListDelete(LinkListhead,inti){p=head;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(p==NULL||p->next==NULL)returnERR

OR;//退出程序运行q=p->next;//使q指向被删除的结点aip->next=q->next;//将ai从链上摘下free(q);//释放结点ai的空间给存储池}算法的时间复杂度也是O（n）循环链表对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针

置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。双向链表双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior特点：1）双链表由头指针head惟一确定的。2）带头结

点的双链表的某些运算变得方便。3）将头结点和尾结点链接起来，为双（向）循环链表。双向链表的结点结构typedefstructDuLNode{ElemTypedata;structDuLNode*prior,*next;}DuLNode,*DuLinkList;双向

链表的前插入操作s->prior=p->prior;//③s->next=p;//④p->prior->next=s;//⑤p->prior=s;//⑥双向链表的删除操作p->prior->next=p->next;//①p

->next->prior=p->prior;//②free(p);//③小结线性表是一种最简单的数据结构，数据元素之间存在着一对一的关系。其存储方法通常采用顺序存储和链式存储。顺序存储的最大优点是可以随机存取，且存储空间比较节约，而缺点是表的扩充困难，

插入、删除要做大量的元素移动。线性表的链式存储是通过结点之间的链接而得到的。根据链接方式又可以分为：单链表、双链表和循环链表等。第3章栈和队列◼3-1栈3-2栈的应用举例◼3-2栈的应用举例◼3-3队列主菜单主菜单3-1栈◆1.栈的定义及相关概念◆2.栈的基本运

算◆3.栈的表示与实现栈的定义及相关概念◼栈（Stack）：是限制仅在表的一端进行插入和删除运算的线性表。◼1．栈顶（Top）◼2．栈底（Bottom）◼3．空栈◼4．LIFO表◼5.退栈◼6.进栈栈的基本运算1.InitS

tack(&L)初始化栈2.StackEmpty（S）判栈空3.StackFull（S）判栈满4.Push（S，x）进栈5.Pop（S）退栈6.StackTop（S）取栈顶元素栈的表示与实现1、顺序栈的类型定义#define

StackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据类型为字符typedefstruct{DataTypedata[StackSize];inttop;}S

eqStack;栈的表示与实现2、顺序栈的进栈操作进栈时，需要将S-＞top加1注意：①S-＞top==StackSize-1表示栈满②"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。3、顺序栈的退栈操作退栈时，需将S-＞top减1注意：①S-＞top<0

表示空栈②"下溢"现象——当栈空时，做退栈运算产生的溢出现象。栈的操作示意图栈的操作示意图AFEDCBAFEDCBAJIHGFEDCBAtop=-1top=0top=5top=3top=9(a)(b)(c)(d)(e)3-2栈的应用举例◆

例3-1：数制转换◆例3-2:表达式求值◆例3-3:迷宫求解例3-1将十进制138转换为二进制例3-1将十进制138转换为二进制NN/2（整除）N%2（求余）138690693413417进0出178栈1栈84次0次42序0序210101∴（138）10=（1

0001010）2例3-23+4/（25–（6+15））*8输入符号运算符栈输出结果操作说明33输出3++3+进栈4+3,4输出4/+,/3,4/继续进栈(+,/,(3,4（进栈25+,/,(3,4,25输出25-+,/,(,-3,4,25-进栈(+,/,(,-,(3,4,2

5（再进栈6+,/,(,-,(3,4,25,6输出6++,/,(,-,(,+3,4,25,6+进栈15+,/,(,-,(,+3,4,25,6,15输出15)+,/,(,-3,4,25,6,15,+遇），依次弹出第2个（后的符号)+,/3,4,25,6,15,+,-遇），依次弹出第1个（后的

符号*+,*3,4,25,6,15,+,-,/弹出/，但*高于+，继续进栈8+.*3,4,25,6,15,+,-,/,8输出8#3,4,25,6,15,+,-,/,8,*,+遇到结束符#，依次弹出*，+例3-3迷宫求解例3-3迷宫求解例3-3迷宫求解例3

-3迷宫求解3-3队列◆1.队列的定义及相关概念◆2.队列的基本运算◆3.链队列◆4.顺序队列◆5.循环队列队列的定义及相关概念◼队列（Queue）：是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表◼1．队头（Front）◼2.队尾（Re

ar）◼3.空队列◼4.FIFO表：队列的实例队列的实例1.如车站排队买票或自动取款机排队取款。2.在计算机处理文件打印时，为了解决高速的CPU与低速的打印机之间的矛盾，对于多个请求打印文件，操作系统把

它们当作可以被延迟的任务，提出打印任务的先后顺序，就是它们实际打印的先后顺序。即按照“先进先出”的原则形成打印队列。队列的基本运算1.InitQueue（Q）置空队。2.QueueEmpty（Q）判队空。3.QueueFull（Q

）判队满。4.EnQueue（Q，x）入队。5.DeQueue（Q）出队。6.QueueFront（Q）返回队头元素，链队列—队列的链式表示与实现队列的链式存储结构称为链队列（或链队），实际上它是一个带有头指针（front）和尾指针（rear）的单链表。为了处理方便，也可以给

链队列附加一个头结点。链队列为空的条件是front=rear，即队列的头指针和尾指针均指向表头结点，如下图所示。队列运算指针变化状况队列运算指针变化状况(a)^a1^a1a2^a1a2^frontfrontfrontfrontrearrearrearrear(b)(c)(d)链队的描述链队的描

述typedefstructQnode{QElemTypedata;structQnode*next;}QNode,*QueuePtr;/*链队结点的类型*/typedefstruct{QNnode*front,*rear;}L

Queue;链队列的入队运算voidEnQueue(LinkQueue*Q,QElemTypex){//将元素x插入链队列尾部QueueNode*p=(QueueNode*)malloc(sizeof(QueueNod

e));p->data=x;p->next=NULL;if(QueueEmpty(Q))Q->front=Q->rear=p;/将x插入空队列else{//x插入非空队列的尾Q->rear->next=p;//*p链到原队尾结点后Q->rear=p;//队尾指针指向新的尾

}}链队列的出队运算QElemTypeDeQueue(LinkQueue*Q){QElemTypex;QueueNode*p;if(QueueEmpty(Q))Error("Queueunderflow");//下溢p=Q->front;//指向对头结点x=p->data;//保

存对头结点的数据Q->front=p->next;//头结点从链上摘下if(Q->rear==p)Q->rear=NULL;free(p);//释放被删队头结点returnx;//返回原队头数据}链队列的队队头元素QElemTypeQueueFront(Link

Queue*Q){if(QueueEmpty(Q))Error("Queueifempty.");returnQ->front->data;}顺序队列—队列的顺序表示与实现顺序队列是用内存中一组连续的存储单元顺序存放队列中各元素。所以可以用一维数组Q[MA

XLEN]作为队列的顺序存储空间，其中MAXLEN为队列的容量，队列元素从Q[0]单元开始存放，直到Q[MAXLEN–1]单元。因为队头和队尾都是活动的，因此，除了队列的数据以外，一般还设有队首（front）和队尾

（rear）两个指针。顺序队列的假溢出顺序队列的假溢出ABCDEFGHFGHIJRear=0front=0rear=5rear=8rear=10front=0front=5front=5(a)(b)(c)(d)循环队列为了克服顺序队列中假

溢出，通常将一维数组queue[0]到q[maxsize-1]看成是一个首尾相接的圆环，即queue[0]与queue[maxsize-1]相接在一起。将这种形式的顺序队列称为循环队列。若rear+1=maxsize,则令rear=0.这样运算很不方便，可利用数学

中的求模运算来实现。入队：rear=(rear+1)modmaxsize;squeue[rear]=x.出队：front=(front+1)modmaxsize.循环队列的变化循环队列的变化循环队列的基本运算◼1.进队列算法（1）检查队列是否已满，若队满，则进行溢出错误处理；（

2）将队尾指针后移一个位置（即加1），指向下一单元；（3）将新元素赋给队尾指针所指单元。◼2.出队列算法（1）检查队列是否为空，若队空，则进行下溢错误处理；（2）将队首指针后移一个位置（即加1）；（3）取队首元素的值。◼3.队列初始

化front=rear=0;小结栈只允许在栈顶进行插入和删除等操作;队列只允许在队尾进行插入操作，在队头进行删除操作。栈主要特点是“后进先出”。队列的主要特点是“先进先出”。栈的主要操作：进栈、出栈、读栈顶元素、判栈空和判栈满。队列的主要操作:进队、出队、判队空、判队满、求队列长度和读队头元素

等。能灵活应用栈和队列的基本原理解决一些综合性的应用问题。第4章串◼4-1串类型的定义4-2串的表示与实现◼4-2串的表示与实现◼4-3串的模式匹配主菜单主菜单4-1串类型的定义◆1.串的定义及相关概念◆2.串的基本运算串的定义及相关概念◼串(string)是由零个或多个

字符组成的有限序列。◼1.空串◼2.空白串◼3.子串◼4.主串串的基本运算1.strcpy(S,T)串复制2.strcat(S,T)串联接3.strlen(T)求串长度4.strsub(S,i,j,T)子串5．strcmp(S,T)串比较大小6.ind

ex(S,T)求子串位置7.replace(S,i,j,T)串替换4-2串的表示与实现◆1.顺序串◆2.静态存储分配的顺序串◆3.动态存储分配的顺序串◆4.串的链式存储◆5.串运算的实现顺序串顺序串:串的顺序存储结构。与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列

。因此可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为如下两类：（1）静态存储分配的顺序串（2）动态存储分配的顺序串静态存储的顺序串直接使用定长的字符数组来定义该种方法顺序串的具体描述：#defineMaxStrSize256/

/该值依赖于应用，由用户定义typedefcharSeqString[MaxStrSize];//SeqString是顺序串类型SeqStringS;//S是一个可容纳255个字符的顺序串静态存储的顺序串注意：①串值空间的大小在编译时刻就已确定，是静态的。难以适

应插入、链接等操作②直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。所以串空间最大值为MaxStrSize时，最多只能放MaxStrSize-1个字符。动态存储的顺序串顺序串

的字符数组空间可使用C语言的malloc和free等动态存储管理函数，来根据实际需要动态地分配和释放。（1）较简单的定义typedefchar*string;//C中的串库<string.h>相当于使用此类型

定义串（2）复杂定义typedefstruct{char*ch;//若串非空，按实际的串长分配存储区，否则ch为NULLintlength;}HString;串的链式存储1、链串：用单链表方式存储串值，串的这种链式存储结构简称为链串。2、链串的结构类型定义typedefstruct

node{chardata;structnode*next;}LinkStrNode;//结点类型typedefLinkStrNode*LinkString;//LinkString为链串类型LinkSt

ringS;//S是链串的头指针链串的结点大小链串的结点大小4-3串的模式匹配◆模式匹配即子串定位运算。设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配。其中被匹配的主串s称为目标串，匹配的子串

t称为模式。模式匹配的基本思想首先将s1与t1进行比较，若不同，就将s2与t1进行比较，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，

即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比较完，则说明本趟匹配成功，本趟的起始位置是i–j+1，否则，匹配失败。模式匹配的例子模式匹配的例子主串s=“ABABCA

BCACBAB”模式t=“ABCAC”小结串是一种特殊的线性表，规定每个数据元素仅由一个字符组成。串的顺序存储有非紧凑格式和紧凑格式两种，非紧凑格式存储操作简单，但内存浪费；紧凑格式可以节省内存，但操作却不方便。串的链式存储结构具有插入、删除方便的优点，但其存储密度很低；若采用紧凑的链式存储（一个

结点放多个字符），虽然提高了空间利用率，但其插入、删除方便的优点也随之消失。串的堆分配存储是一种动态存储结构。串的基本运算包括串的连接、插入、删除、比较、替换、和模式匹配等第5章数组和广义表◼5-1数组的定义5-

2数组的顺序表示与实现◼5-2数组的顺序表示与实现◼5-3矩阵的压缩存储主菜单主菜单◼5-4广义表的定义◼5-5广义表的存储结构5-1数组的定义◆1、一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。◆2、二维数组二维数

组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。◆3、多维数组三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量……5-2数组的顺序存储与实现◼1、行优先顺序将数组元素按行向量排列，第i+

1个行向量紧接在第i个行向量后面。例、二维数组Amn的按行优先存储的线性序列为：a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn◼2、列优先顺序将数组元素按列向量排列，第i+1个列向

量紧接在第i个列向量后面。例、二维数组Amn的按列优先存储的线性序列为：a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn例5-1一个2×3二维数组例5-1一个2×3二维数组5-2数组的

顺序存储与实现3、地址的计算1）按行优先顺序存储的二维数组Amn地址计算公式LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d2）按列优先顺序存储的二维数组Amn地址计算公式LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d3）按行

优先顺序存储的三维数组Amnp地址计算公式LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d4）下界不为1的二维数组的地址计算公式①二维数组A[c1..d1,c2..d2]的地址计算公式：LOC(

aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d②下界为0的二维数组的地址计算公式（C语言中使用）LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d5-3矩阵的压缩

存储◆1.矩阵的二维数组描述◆2.矩阵的压缩存储◆3.特殊矩阵◆4.稀疏矩阵矩阵的二维数组描述◼矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。矩阵的压缩存储◼矩阵中非零元素呈某种规律分布或者矩阵中出现大量

的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。特殊矩阵◼1.对称矩阵◼2.三角矩阵◼3.对角矩阵对称矩阵的特点对称矩阵的特点对称矩阵的压缩存储◼1.对

称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。◼2.按“行优先顺序”存储主对角线(包括对角线)以下的元素◼3.aij和sa[k]之间的对应关系：若i≥j

，k=i×(i+1)／2+j0≤k<n(n+1)／2若i＜j，k=j×(j+1)／2+i0≤k<n(n+1)／2令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为：k=i×(i+1)／2+j0≤k<n(n+1)／2三角矩阵的特点三

角矩阵的特点三角矩阵的压缩存储三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中。①上三角矩阵中

aij和sa[k]之间的对应关系┌i×(2n-i+1)／2+j-i当i≤jk=│└n×(n+1)/2当i＞j②下三角矩阵中aij和sa[k]之间的对应关系┌i×(i+1)／2+j当i≥jk=│└n×(n+

1)/2当i＜j对角矩阵的特点对角矩阵的特点对角矩阵的压缩存储◼一种压缩方法是将A压缩到一个n行w列的二维数组B中，如下图所示，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。稀疏矩阵◼1.稀疏矩阵◼2.三元组顺序表◼3.十字链表稀疏矩阵◼设矩阵Amn中有s个非零元素，若s远远小于矩阵元素

的总数(即s<<m×n)，则称A为稀疏矩阵。◼为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。◼其中每一个非零

元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。三元组顺序表三元组顺序表例5-2转置矩阵的实现例5-2转置矩阵的实现十字链表的基本思想◼用十字链表表示稀疏矩阵的基本思想是：对每个非零元素存储为一个结点，结点由5个域组成，其结构如图表示，其中：row域存储非零元

素的行号，col域存储非零元素的列号，v域存储本元素的值，right，down是两个指针域。十字链表十字链表5-4广义表的定义◆广义表：是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。广义表通常记作：GL=(a1，a2，…，ai，…，an)。

◆1.基本概念◆2.广义表表示◆3.广义表运算基本概念◼1.原子◼2.子表◼3.长度◼4.深度◼5.表头◼6.表尾广义表表示◼1.广义表常用表示◼2.带名字的广义表表示◼3.广义表的图形表示广义表常用表示①E=()E是一个空表

，其长度为0。②L=(a，b)L是长度为2的广义表，它的两个元素都是原子，深度为1。③A=(x，L)=(x，(a，b))A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L，深度为2。④B=(A，y)=((

x，(a，b))，y)B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y，深度为3。⑤C=(A，B)=((x，(a，b))，((x，(a，b))，y))C的长度为2，两个元素都是子表，深度为4。⑥D=(a，D)=(a，(a，(a，(…)

)))带名字的广义表表示①E()②L(a，b)③A(x，L(a，b))④B(A(x，L(a，b))，y)⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))⑥D(a，D(a，D(…)))广义表的图形表示①图中的分支结点对应广义表②非分支结点一般是原子③但空表对应的也是非分

支结点。5-4广义表的存储结构由于广义表中的数据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可用一个

结点表示。◆1.头尾表示法◆2.孩子兄弟表示法头尾表示法表结点、原子结点typedefemnu{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{

structGLNode*hp,*tp;}ptr;}：}*Glist；头尾表示法示例头尾表示法示例孩子兄弟表示法◆在孩子兄弟表示法中，也有两种结点形式：一种是有孩子结点，用以表示列表；另一种是无孩子结点，用以表示单元素。在有孩

子结点中包括一个指向第一个孩子（长子）的指针和一个指向兄弟的指针；而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点，在结点中还要设置一个标志域。如果标志为1，则表示该结点为有孩子结点；如果标志为0，则表示该结点为

无孩子结点。孩子兄弟表示法结点孩子兄弟表示法结点孩子兄弟表示法示例孩子兄弟表示法示例小结⑴多维数组的逻辑结构；⑵多维组的两种顺序存储方式，计算给定元素在存储区中的地址；⑶对称矩阵、三角矩阵的压缩存储方式；⑷稀疏矩阵的三元组表表示方法。(5)广义表的定义和基本运算。第6章树和二叉树◼6-

1树的定义和基本术语6-2二叉树◼6-2二叉树◼6-3遍历二叉树和线索二叉树主菜单主菜单◼6-4树和森林◼6-5赫夫曼树及其应用6-1树的定义和基本术语◆1.树的定义◆2.基本术语◆3.树的表示树的定义树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则

它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)AACGBDEFKLHMIJ基本术语◼结点：包含一个数据元素及若干指向其子树的分支◼结点的

度：结点拥有的子树数◼叶结点：度为0的结点[没有子树的结点]◼分支结点：度不为0的结点[包括根结点]，也称为非终端结点。除根外称为内部结点◼孩子：结点的子树的根[直接后继，可能有多个]◼双亲：孩子的直接前驱[最多只能有一个]◼兄弟：同一双亲的孩子◼子孙：以某结点为根的树中的所有结点基本

术语◼祖先：从根到该结点所经分支上的所有结点◼层次：根结点为第一层，其孩子为第二层，依此类推◼深度：树中结点的最大层次◼森林：互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林◼有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树

(OrderedTree)；否则称为无序树(UnoderedTree)。树的表示ABCEIJDFGH(A(B(D,E(I,J),F),C(G,H)))ABCEDJFGH6-2二叉树◆二叉树的定义二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=

0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的五种基本形态二叉树的性质性质１:在二叉树的第i层上至多有2i-1个结点证明：1.i=1,只有一个根节点，因此2i-1=20=12.设第i-1层上，

以上性质成立，即第i-1层至多有2(i-1)-1结点。由二叉树的定义可知，任何结点的度小于2，因此，第i层上的结点数最多为第i-1层上的两倍，即2*2i-2=2i-1二叉树的性质性质2:深度为k的二叉树至多有2k-1个结点证明

：1.由性质１，已知第i层上结点数最多为2i-1k2.∑2i-1=2k-1i=1二叉树的性质性质3:如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：1.设n1为度为1的结点，则总结点数=n0+n1+n22.设B为二叉树的分支数，除根结点外，每个结点有

且只有一个分支，因此n=B+13.每个分支皆由度为1或2的结点发出，B=n1+2n24.n=B+1=(n1+2n2)+1=n0+n1+n2，因此n0=n2+1满二叉树➢一个深度为k且有2k-1个结点的二叉树➢每层上的结点数都是最大数➢可以自上而下、自左至右连续编号621

754389101113141512完全二叉树➢当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树➢叶子结点只在最大两层上出现➢左子树深度与右子树深度相等或大１621754389101112二叉树

的性质性质4:具有n个结点的完全二叉树,其深度为log2n+1设k为深度，由二叉树性质２，已知2k-1-1<n≤2k-1即2k-1≤n<2k即k=log2n+1621754389101112二叉树的性质性质5:在完全二叉树中，结点i的双亲为i/2结点i的左孩子LCHILD(i)=2i结点i的

右孩子RCHILD(i)=2i+16217543891011122i+2i2i+32i+12ii+1i/2二叉树的顺序存储结构◼用一组连续的存储单元依次自上而下,自左至右存储结点完全二叉树的顺序表示一般二叉树的顺序表示1

23456789101248910567391236478910512340567800910二叉树的链式存储结构◼二叉链表采用数据域加上左、右孩子指针datalChildrChildlChilddatarChild

二叉链表举例二叉链表举例146ABCDFErootABCDFEroot二叉树的链式存储结构◼三叉链表采用数据域加上左、右孩子指针及双亲指针lChilddataparentrChildparentdatalChildrChild三叉链表举例三叉链表举例ABCDFEroot

ABCDFEroot6-3遍历二叉树和线索二叉树◆1.遍历二叉树◆2.线索二叉树遍历二叉树◆1.DLR[先序遍历]◆2.LDR[中序遍历]◆3.LRD[后序遍历]ＤLR先序遍历算法：1.若二叉树为空，则返回；否则：2.访问根节点(D)3.先序遍历左子树(

L)4.先序遍历右子树(R)ADBFCGE结果:ABDEGCF中序遍历算法：1.若二叉树为空，则返回；否则：2.中序遍历左子树(L)3.访问根节点(D)4.中序遍历右子树(R)ADBFCGE结果:DBGEAFC后序遍历算法：1.若二叉树为空，则返回；否则：2.后序遍历左子树

(L)3.后序遍历右子树(R)4.访问根节点(D)ADBFCGE结果:DGEBFCA中序遍历算法voidInOrder(BinTreeT){if(T){//如果二叉树非空InOrder(T->lchild)；print

f(“％c”，T->data)；//访问结点InOrder(T->rchild);}}//InOrder线索二叉树◼1.增加新指针最简单的方法是在每个结点中，增加前驱(fwd)和后继(bkwd)指针◼2.利用空指针➢在有n个结点的二叉树

中，必定存在n+1个空链域.➢因为每个结点有两个链域（左、右孩子指针），因此共有2n个链域➢除根结点外，每个结点都有且仅有一个分支相连，即n-1个链域被使用➢在结点中增加两个标记位（LTag,RTag)6-4树和森林◆1.树

的存储结构◆2.树与二叉树的关系◆3.森林与二叉树的关系◆4.树的遍历◆5.森林的遍历树的存储结构◆1.双亲表示法◆2.孩子表示法◆3.孩子兄弟表示法双亲表示法◆采用一组连续的存储空间，由于每个结点只有一个双亲，只需

要一个指针◆注意：根无双亲，其parent域为-1。◆适用场合:双亲链表表示法中指针parent向上链接，适合求指定结点好的双亲或祖先(包括根)；求指定结点的孩子或其它后代时，可能要遍历整个数组。ABCDEFG-10001130123456

AEBGDFC孩子表示法◆可以采用多重链表，即每个结点有多个指针◆最大缺点是空链域太多[(d-1)n+1个]AEBGDFCdatachild1child2child3childdABCDEFG0123456123^45^6^孩子兄弟表

示法◆采用二叉链表：左边指针指向第一个孩子，右边指针指向兄弟AEBGDFCdatafirstChildnextSiblingBCDGFEA树与二叉树的对应关系◆树与二叉树都可以采用二叉链表作存储结构◆任意给定一棵树，可以找到一个唯一的二叉树(没有右子

树)AEBGDFCBCDGFEAABGDFCE树对应的二叉树森林与二叉树的对应关系◼如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应三棵树的

森林对应的二叉树T1T2T3AFHBCDGIJEKABCEDHIKFGJ树的遍历1.先根（次序）遍历当树非空时➢访问根结点➢依次先根遍历根的各棵子树2.后根（次序）遍历当树非空时➢依次后根遍历根的各棵子树➢访问根结点AEBGDFC先根遍历结果:ABEFCDG后根遍历结果:EF

BCGDA森林的遍历◆1.先序遍历◆2.中序遍历6-5赫夫曼树及其应用◆1.最优二叉树◆2.Huffman树构造◆3.Huffman树算法◆4.Huffman树编码最优二叉树◆最优二叉树：假设二叉树有n个叶子，其每个叶子结点带权wi，则带权路径长度WPL最小的二

叉树称为最优二叉树.◆赫夫曼(Huffman)树就是一棵最优二叉树◆WPL=1*5+2*3+2*4=19ADBCE5３４Huffman树构造◆在Huffman树中，权值最大的结点离根最近◆权值最小的结点离根最远ADBCE5３４Huffman树算法◆1.根据给定的n个权值(w1,w2,…

,wn)构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点◆2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和◆3.在F中删除这两棵树，同时将新得到的二叉树加入F中◆4.重复2

,3，直到F只含一棵树为止Huffman树算法◆1.根据给定的n个权值(w1,w2,…,wn)构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点◆2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值

之和◆3.在F中删除这两棵树，同时将新得到的二叉树加入F中◆4.重复2,3，直到F只含一棵树为止Huffman树举例Huffman树举例F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}7524初始合并{2

}{4}75246F:{18}1175246合并{5}{6}5合并{7}{11}27461118◆设给出一段报文：GOOD_GOOD_GOODGODG◆字符集合是{O,G,_,D}，各个字符出现的频度(次数)是W＝{7,5,2,4}。◆若给每个字

符以等长编码◆O:00G:10_:01D:11◆则总编码长度为(2+7+4+5)*2=36.◆若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。◆各字符出现概率为{2/18,7/18,4/18,5/18},化整为{2,7,4,5}◆可构成右图所示Huffman树Huffman树编码5

274◆令左孩子分支为编码‘0’，右孩子分支为编码‘1’◆得到不等长编码：◆O:0G:10_:110D:111◆则总编码长度为◆7*1+5*2+4*3+2*3=35◆Huffman是一种前缀编码，解码时不会混淆Huffman

树编码5274000111小结⑴树和二叉树的定义、逻辑特点及性质，在二叉树上定义的基本运算；⑵二叉树的链式存储结构及其类型说明，二叉树的顺序存储结构及其类型说明；⑶二叉树链式存储结构的组织方式；⑷二叉树的三种遍历方法及其算法；⑸

以遍历为基础在二叉树上实现的几种运算；⑹哈夫曼树和哈夫曼算法；第7章图◼7-1图的定义和术语7-2图的存储结构◼7-2图的存储结构◼7-3图的遍历主菜单主菜单◼7-4图的连通性问题◼7-5有向无环图及其应用◼7-6最短路

径7-1图的定义和术语图（Graph）是由非空的顶点（Vertices）集合和一个描述顶点之间关系——边（Edges）的有限集合组成的一种数据结构。可以用二元组定义为：G＝（V，E）其中，G表示一个图，V是图G中顶点的集合，E

是图G中边的集合。无向图G1=（V，E）V＝{v1,v2,v3,v4,v5}；E＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。(vi,vj)表示顶点vi和顶点vj之间有一条无向直接连线，也称为边。图7.1无向图G1V1V3V2V4V

5有向图G2=(V,E)V={v1,v2,v3,v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}<vi,vj>表示顶点vi和顶点vj之间有一条有向直接连线，也称为弧。其中vi称为弧尾，vj称为弧头。图7.2有向图G2V1V3V2V4图的相关术语◆1.无向图（Undi

graph）◆2.有向图（Digraph）◆3.无向完全图◆4.有向完全图◆5.稠密图、稀疏图◆6.顶点的度◆7.权图的相关术语◆8.网——边（或弧）上带权的图称为网（Network）◆9.路径、路径长度◆1

0.回路、简单路径、简单回路◆11.子图◆12.连通图、连通分量◆13.强连通图、强连通分量◆14.生成树7-2图的存储结构◆数组表示法---邻接矩阵◆链式存储结构---邻接表图的邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵。假设图G＝（V，E）有n个顶点，即V＝{v0

,v1,…,vn-1}，则G的邻接矩阵是具有如下性质的n阶方阵：1若(vi,vj)或<vi,vj>是E(G)中的边A[i][j]=0若(vi,vj)或<vi,vj>不是E(G)中的边图7.3一个无向图的邻接矩阵表示图的邻接矩阵的性质（1）无向图的邻接矩阵一定是一个对称矩

阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。（2）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度TD(vi)。（3）对于有向图，邻接矩阵的第i行（或第i列）非零元素

（或非∞元素）的个数正好是第i个顶点的出度OD(vi)（或入度ID(vi)）。（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间

代价很大。这是用邻接矩阵存储图的局限性。图的邻接矩阵表示#defineINFINITYINT_MAX//最大值无穷大#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,A

G,AN}GraphKind;//有向图，有向网，无向图，无向网typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0表示相邻否，带权图，则为权值类型InfoType*info;//该弧相关停息的指针}ArcCell,AdjMatr

ix[max_vertex_num][max_vertex_num];图的邻接矩阵表示tpyedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的

当前顶点数和弧数GraphKindkind;//图的种类标志}MGraph;网的邻接矩阵若G是网，则邻接矩阵可定义为：wij若(vi,vj)或<vi,vj>是E(G)中的边A[i][j]=0或∞若(vi,vj)或<vi,vj>不是E(G)

中的边图7.4一个网的邻接矩阵表示邻接表在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点由三个域组成，其中邻接点域(adjvex)指示与顶点v

i邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点；数据域(info)存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点，包含链域(firstarc)指向链表中第一个结点，还设有存储顶点vi的名或其它有关信息的数据域(data)。图的邻接表表

示#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;type

defstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];图的邻接表表示ty

pedefstruct{AdjListvertices;//图的当前顶点数和弧数intvexnum,arcnum;//图的种类标志intkind;}ALGraph;图7.3的邻接表图7.3的邻接表图7.2的邻接表和逆邻接表图7.2的邻接表和逆邻

接表7-3图的遍历图的遍历（traversinggraph）是指从图中的某一顶点出发，对图中的所有顶点访问一次，而且仅访问一次。图的遍历是图的一种基本操作。图的遍历方法:◆深度优先搜索◆广度优先搜索图的遍历操作特点（1）在图结构中

，每一个结点的地位都是相同的，没有一个“自然”的首结点，图中任意一个顶点都可作为访问的起始结点。（2）在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何访问图中其余的连通分量。（3）在图结构中，如果有回路存在，那么

一个顶点被访问之后，有可能沿回路又回到该顶点。（4）在图中，一个顶点可以和其它多个顶点相连，当这个顶点访问过后，就要考虑如何选取下一个要访问的顶点。深度优先搜索深度优先搜索（Depth-FisrstSearch）遍历类似于树的先

根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发v出发，首先访问此顶点，然后任选一个v的未被访问的邻接点w出发，继续进行深度优先搜索，直到图中所有和v路径相通的顶点都被访问到；若此时图中还有顶点未被访问到，则另选一个未被

访问的顶点作为起始点，重复上面的做法，直至图中所有的顶点都被访问。深度优先遍历图的过程深度优先遍历图的过程V1V5V2V4V8V3V6V7图7-5无向图G5以图7-5的无向图G5为例，其深度优先搜索得到的顶点访问序列为：v1→v2→v4→v8→

v5→v3→v6、→v7广度优先搜索广度优先搜索（Depth-FisrstSearch）类似于树的按层次遍历。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的

邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程中以v为起始点，

由近至远，依次访问和v有路径相通且路径长度为1,2,…的顶点。广度优先搜索算法1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接

点，并作相应的标记。3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。广度优先遍历图的过程广度优先遍历图的过程V1V5V2V4V8V3V6V7图7-5无向图G5以图7-5的无向图

G5为例，其广度优先搜索得到的顶点访问序列为：v1→v2→v3→v4→v5→v6→v7→v87-4图的连通性问题判定一个图的连通性是图的一个应用问题，我们可以利用图的遍历算法来求解这一问题。本节将讨论无向图的连通性问题，并讨论最小代价生成树等问题

。无向图的连通分量和最小生成树在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中

得到的顶点访问序列恰为其各个连通分量中的顶点集。无向图的连通分量和生成树◼无向连通图遍历：仅需从图中任一顶点出发，进行DFS或BFS便可访问到所有顶点。◼无向非连通图遍历：需要多次遍历才可访问到所有木顶点。◼生成

树：遍历所经过的边的集合与所有顶点的集合构成一棵生成树。生成树不唯一。◼在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，若边集E(G’)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G’是原图G的生成树（Span

ningtree）。无向图的连通分量和生成树◼生成树有如下特点：➢任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现环路；如果去掉一条边此子图就会变成非连通图。➢一个有n个顶点的完全图，一共存在n(n-2)种不同的生成树。最小生成树◼概念对于带权的连

通图（连通网）G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（MinimumSpanningTree）。具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路）。普里姆算法构造最小生成树基本思

想：从所有u∈U，v∈V－U的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到U＝V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。图7.6Prim算法构造最小生成树的过程示意图AEBF

CDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)6812141617515666668888812121214145克鲁斯卡算法构造最小生成树基本思想：Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。其

基本思想是：首先选取全部的n个顶点，将其看成n个连通分量；然后按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n个结点的生成树，有n-1条边，故反复上述过程，直到选取了n-1条边为止，就构成了一棵最小生成树。图7-7Kruska

l算法构造最小生成树的过程示意图AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)681214161751556666888851212551457-5拓朴排序及其应用◆在工程实践中，一个工程项目往往由若干

个子项目组成，这些子项目间往往有多种关系：➢①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；➢②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。◆在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。◆学

校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。AOV网◼以上类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个

个顶点称之为活动(Activity)。◼如果从顶点Vi到Vj之间存在有向边<Vi，Vj>,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(ActivityOnVertexnetwork,简称AOV网络)。例某专业课程设置例某专业

课程设置C2C3C4C5C6C7C8C1课程代号普通物理计算机原理程序设计离散数学数据结构编译技术操作系统高等数学课程代号C1C2C1,C4C4,C5C4,C6C3,C6先行课程AOV图AOV图C1C2C3C4C5C6C7C8AOV网◼在AOV网络中，如果顶点Vi的活动必须在顶点V

j的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。◼AOV网络中一定不能有有向环路。例如在图6.17那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之

间的先后关系进入了死循环。◼因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。拓扑排序◼所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要

求的前趋、后继关系都能得到满足。◼由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。◼通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑

排序序列中，则AOV网络必定不包含有有向环路。拓扑排序方法➢(1)在网络中选择一个没有前趋的顶点，并把它输出；➢(2)从网络中删去该顶点和从该顶点发出的所有有向边；➢(3)重复执行上述两步，直到网中所有的顶点都被输出(此时，原AOV网络中的所有顶点和边就都被删除掉了)。➢如果进

行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。关键路径法➢关键路径法是采用边表示活动(ActivityOnEdge)的网络，简称为AOE网络。➢AOE网络是一个带权

的有向无环路图，其中，每个顶点代表一个事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。➢离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。➢权值表示活动持续的时间。关键路径➢完成工程所需

的时间就是从开始点起进行到结束点止所需的时间。➢路径长度是指沿路径各边的权值之和，也就是这些边所代表的活动所需时间之和。➢完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大的路径叫做关键路径。➢分析关键路

径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。7-6最短路径最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个交通网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，问题是如何在城市A和城市B

之间找一条最近的通路。如果将城市用顶点表示，城市间的公路用边表示，公路的长度则作为边的权值，那么，这个问题就可归结为在网中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径，并称路径上的第一个

顶点为源点（Sourse），最后一个顶点为终点（Destination）。在不带权的图中，最短路径是指两点之间经历的边数最少的路径。图7.8用迪杰斯特拉算法求有向图的最短路径过程V1V5V2V4V3201035101530V1V5V2V4V32015V1V

5V2V4V320101530V1V5V2V4V320101530V1V5V2V4V32010153010小结图的定义、术语及其含义；各种图的邻接矩阵表示法及其类型说明；图的按深度优先搜索遍历方法和按广度优先搜索遍历方法；生成树和最小生成树的概念；由Pri

m算法思想构造最小生成树按Prim算法思想；拓扑序列和拓扑排序的概念、算法思想；解并掌握关键路径的算法思想；理解并掌握最短路径的算法思想。第9章查找◼9-1静态查找表9-2动态查找表◼9-2动态查找表◼9-3哈希表主菜单主菜单9-1静态

查找表◼查找的基本概念◼顺序查找(SequentialSearch)◼二分查找(BinarySearch)◼分块查找(BlockingSearch)查找的基本概念◆查找表◆查找◆动态查找表◆静态查找表◆关键字（Key）◆主关

键字◆内查找和外查找◆平均查找长度ASL顺序查找(SequentialSearch)◆基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败

。顺序查找(SequentialSearch)◆基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。顺序查找的类型说明ty

pedefstruct{KeyTypekey；InfoTypeotherinfo；//此类型依赖于应用}NodeType；typedefNodeTypeSeqList[n+1]；//0号单元用作哨兵顺序查找的算法intSeqSearch(SeqlistR，KeyTypeK){//在

顺序表R[1..n]中顺序查找关键字为K的结点，//成功时返回找到的结点位置，失败时返回0inti；R[0].key=K；//设置哨兵for(i=n；R[i].key!=K;i--)；//从表后往前找returni；//若i为0，表示查找失败，

否则R[i]是要找的结点}//SeqSearch顺序查找算法分析➢①算法中监视哨R[0]的作用为了在for循环中省去判定防止下标越界的条件i≥1，从而节省比较的时间。➢②成功时的顺序查找的平均查找长度：即查找成功时的平均比较次数约为表长的一半。➢③表中各结点的查找概率

并不相等的ASL➢④顺序查找的优点算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。➢⑤顺序查找的缺点查找效率低，因此，当n较大时不宜采用顺序查找。二分查找◼二分查找又称折半查

找，它是一种效率较高的查找方法。◼二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。二分查找的基本思想设R[low..high]是当前的查找区间（1）首先确定该区间的中点位置：(2）然后将待查的K值与R[mid].key比较：若相

等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。二分查找判定树二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分

查找的判定树(DecisionTree)或比较树(ComparisonTree)。注意：判定树的形态只与表结点个数n相关，而与输入实例中R[1..n].keys的取值无关。二分查的优缺点➢虽然二分查找的效率高，但是要将表按关键字排序。而

排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。➢二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。➢对那些查找少而又经常

需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。分块查找◼分块查找(BlockingSearch)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。◼分块查找的优点是：◼①在表中插入或删除一个记录时，只要找到该记录所属的块

，就在该块内进行插入和删除运算。◼②因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。9-2动态查找表◼1.二叉排序树◼2.平衡二叉树二叉排序树◼二叉排序树（BinarySortTree）或者是一棵

空树；或者是具有下列性质的二叉树：◼（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；◼（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；◼（3）左右子树也都是二叉排序树。二叉排序树◼二叉排序树的插入◼（1）插入原则◼（a）若二叉树为空，则插入结点为新的根结点。否则，

◼（b）插入结点小于根结点，在左子树上查找；插入结点大于根结点，在右子树上查找，直至某个结点的的左、右子树空为止。◼（c）插入结点小于该结点，作为该结点的左孩子，否则作为该结点的右孩子。例9-1记录的关键字序列为：33，50，42，18，39，9，77，44，2，11，24，则构造一棵二叉

排序树例9-1记录的关键字序列为：33，50，42，18，39，9，77，44，2，11，24，则构造一棵二叉排序树二分排序树的查找过程（1）若查找树为空，查找失败。（2）查找树非空，将给定值kx与查找树的根结点关键字比较。（3）若相等，查找成功，结束查找过程，否则

，（a）当给kx小于根结点关键字，查找将在以左子女为根的子树上继续进行，转（1）（b）当给kx大于根结点关键字，查找将在以右子女为根的子树上继续进行，转（1）二分链表结点描述以二叉链表作为二叉排序树的存储结构，则查找过程算法程序描述如下：typedefstr

uctnode//二叉排序树结点结构{KeyTypekey;//数据元素字段structnode*lchild,*rchild;//左、右指针字段}BSTNode;//二叉树结点类型二叉排序树查找算法voidSearchBST(B

STreeT,KeyTypeKey){BSTNode*p=T;while(p){if(p->key==Key){printf("已经找到\n");return;}p=(Key<p->key)?p->lchild:p->r

child;}printf("没有找到\n");}二叉排序树查找分析在二叉排序树上查找其关键字等于给定值结点的过程，恰是走了一条从根结点到该结点的路程的过程。含有n个结点的二叉树是不唯一的，如何来进行查找分析呢？图9.1(a)二叉排序树图9.2(b)查找分析

后的二叉排序树302528153520153530402520平衡二叉树◼平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树：◼（1）它的左子树和右子树高度之差的绝对值不超过1；◼（2）它的左子树和右子树都是平衡二叉树。平衡二叉

树举例平衡二叉树举例图9.3(a)非平衡二叉树图9.4(b)平衡二叉树07060903585406550754247300-320-201070603585407542101-11009-2哈希表◼1.哈希表◼2.哈希表的冲突现象◼3.哈希函数的

构造方法◼4.处理冲突的方法哈希表◆前面所讨论的查找方法，由于数据元素的存储位置与关键字之间不存在确定的关系，因此，查找时，需要进行一系列对关键字的查找比较，即“查找算法”是建立在比较的基础上的，查找效率由比较一次缩

小的查找范围决定。理想的情况是依据关键字直接得到其对应的数据元素位置，即要求关键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字得到对应的数据元素位置。哈希表举例哈希表举例例9-211个元素的关键字分别为18，27，1，20，22，6，10，13，41，15，25。例9-211个元素

的关键字分别为18，27，1，20，22，6，10，13，41，15，25。1.通过这个函数对11个元素建立查找表如下：012345678910图9.5关键字与函数的对应关系102041186271525131222.查找时，对给定值kx依然通过

这个函数计算出地址，再将kx与该地址单元中元素的关键字比较，若相等，查找成功。哈希表与哈希方法：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键字进行比较，确定查找是否成功，这就是哈希方法。哈希方法中使用的转换函数称

为哈希函数。按这个思想构造的表称为哈希表。哈希表的冲突现象◼对于n个数据元素的集合，总能找到关键字与存放地址一一对应的函数。若最大关键字为m，可以分配m个数据元素存放单元，选取函数f(key)=key即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常

关键字的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突(Collision)，映射到同一哈希地址上的关键字称为同义词。可以说，冲突不可能避免，只能尽可能减少。哈希函数的构造方法◼1

.直接定址法◼2.平方取中法◼3.除留余数法直接定址法Hash(key)=a·key+b(a、b为常数)即取关键字的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址集合与关键字集合

大小相同，因此，对于较大的关键字集合不适用。【例8-5】关键字集合为{20，30，50，60，80，90}，选取哈希函数为：Hash(key)=key/10，则存放如下：0123456789图9.6关键字存放地址806050302090除

留余数法Hash(key)=keymodp(p是一个整数)即取关键字除以p的余数作为哈希地址。使用除留余数法，选取合适的p很重要，若哈希表表长为m，则要求p≤m，且接近m或等于m。p一般选取质数，也可以是不包含小于20质因子的合数。处理冲突的方法◆1.开放定址法◆2.拉链法◆3.建立一个

公共溢出区开放定址法所谓开放定址法，即是由关键字得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。线性探测法Hi=(Hash(key)+di)modm(1≤i<m)其中：Hash(key)为哈

希函数m为哈希表长度di=i；i=1，2，3，…，m-1例9-3关键字集为{47，7，29，11，16，92，22，8，3}，哈希表表长为11，Hash(key)=keymod11。用线性探测法处理冲突，建表如下：01234567891

0829731692472211△△△▲图9.7用线性探测法处理冲突的哈希表47、7、11、16、92均是由哈希函数得到的没有冲突的哈希地址而直接存入的；Hash(29)=7，哈希地址上冲突，需寻找下一个空的

哈希地址。由H1=(Hash(29)+1)mod11=8，哈希地址8为空，将29存入。另外，22、8同样在哈希地址上有冲突，也是由H1找到空的哈希地址的；而Hash(3)=3，哈希地址上冲突，由H1=(Hash(3)+1)mod11=

4仍然冲突；H2=(Hash(3)+2)mod11=5仍然冲突；H3=(Hash(3)+3)mod11=6找到空的哈希地址，存入。线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈

希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。为此，可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题。二次探测法（平方探测法）Hi=(Hash(key)±di)modm其中：Hash(key)为哈希函数m为哈希表长度，m要求是某个4k

+3的质数(k是整数)di为增量序列12，-12，22，-22，……，q2，-q2且q≤(m-1)仍以上例用二次探测法处理冲突，建表如下：012345678910△▲△△图9.8二次探测法处理冲突的哈希表对关键字寻找空的哈希地址只有3这个关键字与上例不同，Hash(3)=3

，哈希地址上冲突，由H1=(Hash(3)+12)mod11=4仍然冲突；H2=(Hash(3)-12)mod11=2找到空的哈希地址，存入。8291716924732211小结查找表的基本概念及查找原理；查找表的顺序存储结构、顺序表及其类型

说明；查找运算在查找表和有序表上的实现；二叉排序树的定义、性质及各结点间的键值关系；二叉排序树的查找算法和基本思想；平衡二叉排序树的概念；散列表及散列存储和散列查找的基本思想；各种散列表的组织、解决冲突的方法

；第10章内部排序◼10-1概述10-2插入排序◼10-2插入排序◼10-3快速排序主菜单主菜单◼10-4选择排序10-5归并排序◼10-5归并排序◼10-6各种排序方法比较10-1概述◆1．排序（Sorting）将数据元素（或记录）的任意序列，重新排列成一个按关键字

有序（递增或递减）的序列的过程称为排序。◆2．排序过程中的两种基本操作（1）比较两个关键字值的大小。（2）根据比较结果，移动记录的位置。◆3．对关键字排序的三个原则（1）关键字值为数值型的，则按键值大小为依据。（2）关键字值为ASCII码，则按键值的内码编排顺序为依据。（3）关键

字值为汉字字符串类型，则大多以汉字拼音的字典次序为依据。10-1概述◆4．排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是

稳定的；反之，则称为不稳定的。例如：对数据键值为：5，3，8，3，6，6，排序。若排序后的序列为：3，3，5，6，6，8，其相同键值的元素位置依旧是3在3前，6在6前，与排序前保持一致，则表示这种排序法是稳定的；若排序后的序列为：3，

3，5，6，6，8，则表示这种排序法是不稳定的。10-1概述◆5．内排序整个排序过程都在内存进行的排序称为内排序。◆6．外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。10-2插入排序◆直

接插入排序◆二分插入排序◆希尔排序直接插入排序的基本思想直接插入排序（StraightInsertionSort）是一种最简单的排序方法，它的基本操作是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。

插入前：（1358）[27496]有序无序插入后：（12358）[7496]有序无序10.1直接插入排序过程示例直接插入排序算法分析直接插入排序的时间复杂度为O(n2)，辅助空间为O（1）。直接插入排序是稳定的排序方法。直接插入排序最适合待排序关键字基本有序的序列。二分插

入排序基本思想直接插入算法虽然简单，但当记录数量n很大时，则比较次数将大大增加，对于有序表（限于顺序存储结构），为了减少关键字的比较次数，可采用二分插入排序。二分插入排序的基本思想是：用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入。希尔排序基本思想先将整个待排序记

录序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序时”，再对全体记录进行一次直接插入排序。特点：子序列不是简单的逐段分割，而是将相隔某个“增量”的记录组成一个子序列，所以关键字较小的记录不是

一步一步地前移，而是跳跃式前移，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要做少量比较和移动即可完成排序，时间复杂度较低。10.2希尔排序过程示例希尔排序算法分析希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难

题。到目前为止尚未求得一种最好的增量序列，有人在大量实验的的基础推出：当n在某个特定范围内希尔排序所需的比较和移动次数约为n1.3，所以其平均时间复杂度约为O（n1.3）。其辅助空间为O（1）。希尔排序是不稳定的排序方法。10-3快速排序◆基本思想

就排序时间而言，快速排序被认为是一种最好的内部排序方法通过一趟快速排序将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位

置并被存放好，这个过程称为一趟快速排序。第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。显然，这是一个递归的过程，不断进行下去，直到每个待排序的子

序列中只有一个记录时为止，整个排序过程结束。快速排序是对冒泡排序的一种改进。10-3快速排序◆基本思想就排序时间而言，快速排序被认为是一种最好的内部排序方法通过一趟快速排序将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比

枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好，这个过程称为一趟快速排序。第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且

它们又分别分割出独立的两个子序列……。显然，这是一个递归的过程，不断进行下去，直到每个待排序的子序列中只有一个记录时为止，整个排序过程结束。快速排序是对冒泡排序的一种改进。快速排序算法设待排序列的下界

和上界分别为low和high，R[low]是枢轴记录，一趟快速排序的具体过程如下：（1）首先将R[low]中的记录保存到pivot变量中，用两个整型变量i,j分别指向low和high所在位置上的记录；（2）先从j所指的记录起自右向左逐一将关键字和pivot.key进行比较

，当找到第1个关键字小于pivot.key的记录时，将此记录复制到i所指的位置上去；（3）然后从i+1所指的记录起自左向右逐一将关键字和pivot.key进行比较，当找到第1个关键字大于pivot.key的记录时，将该记录复制到j所指的位置上去；（4）接着再从j

-1所指的记录重复以上的（2）、（3）两步，直到i=j为止，此时将pivot中的记录放回到i（或j）的位置上，一趟快速排序完成。快速排序算法分析➢空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调

用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。➢时间效率：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(

n)为对n个记录的待排序列进行快速排序所需时间。➢理想情况下：每次划分，正好将分成两个等长的子序列，则时间复杂度为O(nlog2n)；➢最坏情况下：快速排序每次划分，只得到一个子序列，这时快速排序蜕化为冒泡排序的过程，其时间复杂度最差，为O(n2)。➢快速排序是通常被

认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。快速排序是一个不稳定的排序方法。10-4选择排序◆选择排序主要是从待排序列中选取一个关键字值最小的记录，把它与第一个记录交换存储位置，使之成为有序。然后在余下的

无序的记录中，再选出关键字最小的记录与无序区中的第一个记录交换位置，又使之成为有序。依次类推，直至完成整个排序。简单选择排序1．基本思想（1）初始状态：整个数组r划分成两个部分，即有序区（初始为空）和无序区。（2）基本操作：从无序中选择关键字值最小的记录，将其与无序区的第

一个记录交换（实质是添加到有序区尾部）。从初态（有序区为空）开始，重复步骤（2），直到终态（无序区为空）。简单选择排序算法分析➢简单选择排序比较次数与关键字初始排序无关。➢找第一个最小记录需进行n-1次比较，找第二个最小记录需要

比较n-2次，找第i个最小记录需要进行n-i次比较，总的比较次数为：➢（n-1）+（n-2）+……+（n-i）+……2+1=n(n-1)/2=n2/2➢时间复杂度：O(n2)➢辅助空间：O（1）➢简单选择排序是不稳定的排序方法。堆排序1．基本思想（1）把用数组来存储待排序的数

据，转换成一棵完全二叉树。（2）将完全二叉树转换成堆树。（3）有了堆树后，我们便开始排序。88427527613806988426277513806913426277588806969426277588801369426277580

8813图10.3建堆树的过程6942627751380134262775698013426277569806942627758013图10.4堆排序的过程继续相同步骤，最后只剩下树根，完成整个堆排序过程。(a)输出堆顶后，将堆底13送入堆顶(b)堆被破坏，根结点与左子女交换(c

)左子树不满足堆，其根与左孩子交换(d)堆已建成10-5归并排序◆基本思想（1）将n个记录的待排序序列看成是有n个长度都为1的有序子表组成。（2）将两两相邻的子表归并为一个有序子表。（3）重复上述步骤，直至归并为一个长度为n的有序表。归并排序算法分析➢对n个元素的序列，执行二路归并算法，则必须

做log2n趟归并，每一趟归并的时间复杂度是O（n），所以二路归并的时间复杂度为O(nlog2n)。➢两路归并排序需要和待排序序列一样多的辅助空间。其空间复杂度为O（n）。➢两路归并排序也是一种稳定性的排序。10-6各种排序

方法比较◆评估一个排序法的好坏，除了用排序的时间及空间外，尚需考虑稳定度、最坏状况和程序的编写难易程度，例如冒泡排序法，虽然效率不高，但却常常被使用，因为好写易懂。而归并排序法需要大量的额外空间，快速排序法虽然很快，但在某些时

候效率却与插入排序法差不多。以下就常用的排序法按最坏情况下所需时间、平均所需时间、是否属于稳定排序、所需的额外空间等以表10-1来表示。表10-1各种排序方法比较小结排序基本概念及内排序和外排序、稳定排序和非稳定排

序的区别；插入排序的基本思想、基本步骤和算法；冒泡排序的基本思想、基本步骤、算法和算法分析；快速排序的基本思想、基本步骤和算法；直接选择排序的基本思想、基本步骤、算法和算法分析；堆排序的基本思想、基本步骤和算法；归并排序的思想；