数据结构及其应用PPT课件

《数据结构及其应用PPT课件》由会员分享，可在线阅读，更多相关《数据结构及其应用PPT课件（186页珍藏版）》请在金锄头文库上搜索。

1、软件开发技术基础软件开发技术基础 数据结构及其应用数据结构及其应用 什么是数据什么是数据整数数据整数数据Struct student Struct student long num; long num; char name9; char name9; char sex; char sex; float score; float score; 学生花名册数据学生花名册数据学号学号 姓名姓名 性别性别 成成绩绩 98031001 98031001 张三张三 男男 88 8898031002 98031002 李四李四 女女 89.589.5 .棋盘数据：围棋棋盘棋盘数据：围棋棋盘如如何何描描述述？

2、棋盘数据：井字棋盘棋盘数据：井字棋盘OO* *OOOOOO* *OOOO* * * * *OOOOOCharchess9;或intchess9;城市交通图数据城市交通图数据OOOOOOOOO咸阳咸阳西安西安长安县长安县临潼临潼兴平兴平礼泉礼泉渭南渭南大荔大荔图像数据图像数据 像素存储像素存储 （行号，列号，颜色）（行号，列号，颜色）声音数据声音数据时刻值，幅度值时刻值，幅度值数据元素数据元素-是数据这个集合中的一个个体，是数据的基本单位。是数据这个集合中的一个个体，是数据的基本单位。数据项数据项-是具有独立含义，且不可再细分的最小标识单位。是具有独立含义，且不可再细分的最小标识单位。数据结构数

3、据结构-指相互之间存在一种或多种特定关系的数据元素集合指相互之间存在一种或多种特定关系的数据元素集合数据的逻辑结构数据的逻辑结构-反映数据元素之间客观存在的逻辑关系。反映数据元素之间客观存在的逻辑关系。数据的存储结构数据的存储结构-将数据的逻辑结构在计算机内存中存储的结构。将数据的逻辑结构在计算机内存中存储的结构。 数据的物理结构数据的物理结构数据的运算数据的运算-是定义在数据结构上的操作。是定义在数据结构上的操作。 例如求某个数据结构中的最大元素等。例如求某个数据结构中的最大元素等。线性表、堆栈、队列、树、图线性表、堆栈、队列、树、图名词术语名词术语什么是算法？什么是算法？算法算法-是解决问

4、题方案的准确而完整的描述是解决问题方案的准确而完整的描述算法的特性：有穷性、确定性、可行性、有输入、有输出算法的特性：有穷性、确定性、可行性、有输入、有输出时间复杂度：依据算法编制成程序后，在计算机上运行所消耗时间时间复杂度：依据算法编制成程序后，在计算机上运行所消耗时间空间复杂度：依据算法编制成程序后，在计算机上运行所消耗空间空间复杂度：依据算法编制成程序后，在计算机上运行所消耗空间用数量级来度量和分析时间复杂度和空间复杂度。用数量级来度量和分析时间复杂度和空间复杂度。 # #define n 1000000define n 1000000 sum=sum+1; sum=sum+1; O(1

5、)O(1) for(I=0;In;I+) sum+; for(I=0;In;I+) sum+; O(n)O(n) for(I=0;In;I+) for(j=0;jn;j+) sum+; for(I=0;In;I+) for(j=0;jn;j+) sum+; O(nO(n2 2) ) float a; float a; O(1)O(1) float an; float an; O(n)O(n) float ann float ann O(nO(n2 2) )算法算法什么是线性表什么是线性表日常生活中常见到表格形式的一类数据日常生活中常见到表格形式的一类数据 列车时刻表列车时刻表 学生成绩表学生成

6、绩表 周名缩写表周名缩写表 车次车次火车种类火车种类始发站始发站终点站终点站始发时间始发时间到达时间到达时间140140特快特快西安西安上海上海2020：30301919：45454242特快特快西安西安北京北京1717：30307 7：4545361361普快普快西安西安铜川铜川9 9：45451313：1010列车时刻表列车时刻表学号学号姓名姓名性别性别分数分数9901100199011001周敏周敏女女86869901100299011002苏伊诗苏伊诗女女92929901100399011003王苏朋王苏朋男男7676学生成绩表学生成绩表Sun.Mon.Tue.Wen.Thu.Fri.

7、Sat.周名缩写表周名缩写表1 1）表表中中每每一一行行信信息息虽虽然然组组成成的的内内容容不不同同，但但都都代代表表某某个个明明确确独独立立的的含含义义，将将表表中中每每一一行行信信息息称称之之为为一一个个数数据据元素；元素；2 2）每每个个数数据据元元素素在在表表中中的的位位置置固固定定，除除了了第第一一个个元元素素和和最最后后一一个个元元素素外外，其其余余元元素素都都有有唯唯一一一一个个前前驱驱元元素素和和唯一一个后继元素；唯一一个后继元素；3 3）表中数据元素的个数不相同，有长有短；）表中数据元素的个数不相同，有长有短；4 4）大大多多数数表表中中数数据据元元素素会会增增加加或或减减少

8、少，是是动动态态变变化化的的。但也有一些表是固定不变，但也有一些表是固定不变，将这些表格形式的数据加以抽象，统称为线性表。将这些表格形式的数据加以抽象，统称为线性表。 上述表格数据具有如下共同特点：上述表格数据具有如下共同特点：什么是线性表什么是线性表试举出日常生活中线性表的例子？试举出日常生活中线性表的例子？对线性表有哪些处理（或操作）呢？对线性表有哪些处理（或操作）呢？1 1）统统计计线线性性表表里里总总共共有有多多少少个个元元素素。简简称称求求表表长长，记记作作 LengthLength（L L），），2 2）获获取取线线性性表表中中某某个个数数据据元元素素的的信信息息。简简称称取取元元

9、素素，记作记作 GetGet（L L，i i） 3 3）置置换换或或修修改改线线性性表表中中某某个个数数据据元元素素的的信信息息。简简称称置置换元素换元素， 记作记作ReplaceReplace（L L，i i，x x）4 4）在在线线性性表表中中某某个个位位置置上上增增加加一一个个数数据据元元素素。简简称称插插入元素入元素， 记作记作InsertInsert（L L，i i，x x）5 5）删删除除线线性性表表中中某某个个位位置置上上的的一一个个数数据据元元素素。简简称称删删除元素除元素， 记作记作DeleteDelete（L L，i i）6 6）查查找找某某个个数数据据元元素素是是否否在在

10、线线性性表表中中存存在在。简简称称查查找找元素元素， 记作记作LocateLocate（L L，x x）7 7）对对线线性性表表中中的的数数据据元元素素按按某某个个数数据据项项的的值值递递增增（或或递减）递减） 的顺序排列。简称的顺序排列。简称排序排序，记作，记作Sort(L)Sort(L)。线性表的顺序存储结构线性表的顺序存储结构-顺序表类顺序表类线性表的非顺序存储结构线性表的非顺序存储结构-链表类链表类线性表的两种存储结构线性表的两种存储结构顺序表类const int MAXSIZE=100; const int MAXSIZE=100; /顺序表最大允许长度顺序表最大允许长度class

11、SeqListclass SeqListpublic:public: ElemType dataMAXSIZE; / ElemType dataMAXSIZE; / 存储数据的数组存储数据的数组 int length; int length; / / 顺序表当前长度顺序表当前长度 SeqList() length=0; SeqList() length=0; / /构造函数构造函数 void ClearList() length=0; /void ClearList() length=0; /将顺序表置将顺序表置为空表为空表 bool IsListEmpty() return length=0

12、; bool IsListEmpty() return length=0; /判断是判断是否为空表否为空表 / /判断顺序表是否为满判断顺序表是否为满 bool IsListFull() return length=MAXSIZE;bool IsListFull() return length=MAXSIZE; void ListDelete( int i ); / void ListDelete( int i ); /在表中删除第在表中删除第i i个元素个元素 / /在表中第在表中第 i i 个位置插入新元素个位置插入新元素x x void ListInsert( int i, ElemTy

13、pe x ); void ListInsert( int i, ElemType x ); int Find( ElemType x ); int Find( ElemType x ); / /在表中查找元素在表中查找元素;数据元素类型说明插入前：（插入前：（a a 1 1，a a 2 2，a a i-1 i-1，a a i i，a a n n）插入后：（插入后：（a a 1 1，a a 2 2，a a i-1 i-1，x x ，a a i i，a a n n）第第1 1步步: : 判定表不满方可插入；判定表不满方可插入；第第2 2步步: : 判定插入位置判定插入位置i i的合法性；的合法性；

14、第第3 3步步: : 将第将第n n至第至第i i个元素后移一个存储位置；个元素后移一个存储位置；第第4 4步步: : 将将x x存入到存入到a a i-1 i-1之后空间；之后空间；第第5 5步步: : 线性表的长度加线性表的长度加1 1。 插入算法voidSeqList:ListInsert(inti,ElemTypex)if(ilength+1|length=MAXSIZE)cout=i-1;j-)dataj+1=dataj;/元素依次向后移动元素依次向后移动datai-1=x;/向第向第i个位置存入新元素个位置存入新元素length+;/表长度加表长度加1在等概率的条件下在等概率的条件

15、下, ,插入函数的时间复杂度插入函数的时间复杂度: :N/2N/2 a a1 1 a a2 2 a a3 3 a a4 4 a an-1n-1 a an n 有有N+1N+1处可能插入处可能插入, ,等概率值为等概率值为1/(1+1/(1+N)N) 插入算法评价删除前：（删除前：（a a 1 1，a a 2 2，a a i-1 i-1，a a i i，a a i+1 i+1，a a n n） 删除后：（删除后：（a a 1 1，a a 2 2，a a i-1 i-1，a a i+1 i+1，a a n n） 第第1 1步：判定表不空方可删除；步：判定表不空方可删除；第第2 2步：判定删除位置步

16、：判定删除位置i i值的合法性；值的合法性；第第3 3步：将第步：将第i+1i+1至第至第n n个元素依次向前移动一个存储位置；个元素依次向前移动一个存储位置；第第4 4步：将线性表的长度减步：将线性表的长度减1 1。 删除算法voidSeqList:Delete(inti)if(iL-length)cout表中没有第表中没有第i个元素个元素;elsefor(intj=i;j=length-1;j+)dataj-1=dataj;/元素依次向前移动元素依次向前移动length-;删除函数的时间复杂度：（删除函数的时间复杂度：（N-1N-1）/2 /2 在等概率条件下在等概率条件下插入和删除算法详

17、见插入和删除算法详见rjjcjg_1.cpprjjcjg_1.cpp删除算法评价int SeqList:Find(ElemType x ) for( int i = 0; inext=NULL;/头结点的指针为空头结点的指针为空intListSize();/求单链表长度求单链表长度LNode*GetElemPointer(intpos);/返回表中指定序号结点的指针返回表中指定序号结点的指针voidInsertList(inti,ElemTypex);/向单链表第向单链表第i个位置插入元素个位置插入元素xLNode*LinkList:DeleteList(inti);/从单链表中删除第从单链表

18、中删除第i个结点个结点LNode*Find(ElemTypex)；/在单链表中查找数据值为在单链表中查找数据值为x的结点的结点;单链表类的完整定义如下：指针操作指针操作假如假如p p为指向某一结点的指针为指向某一结点的指针则该结点的数据域用则该结点的数据域用p-datap-data表示表示 该结点的指针域用该结点的指针域用p-nextp-next表示表示它们都是变量，可以被赋值，也可向其他变量赋值。它们都是变量，可以被赋值，也可向其他变量赋值。例如例如: : 假定假定datadata为整型变量为整型变量, ,则则p-data=5; p-next=NULL; 将将结点变为结点变为: : aiai

19、-1ai-1aiai-1ai+1qqpp如果如果p为指向结点为指向结点ai的指针，那么的指针，那么p-next就是指向就是指向ai后继结点后继结点ai+1的指针；若的指针；若q为另一指针变量为另一指针变量p=q指针指针p指向指针指向指针q所指的结点所指的结点p=q-next指针指针p指向指针指向指针q所指结点的后继所指结点的后继指针操作指针操作要确定链表长度需要走遍表中所有结点才能算出。要确定链表长度需要走遍表中所有结点才能算出。为了保持头指针不变，使用了指针为了保持头指针不变，使用了指针p p在链表中移在链表中移动。动。求单链表的长度求单链表的长度int LinkList:ListSize(

20、) int LinkList:ListSize() LNode *p=head-next; /p LNode *p=head-next; /p指向第一个元素所在结点指向第一个元素所在结点 int len=0; int len=0; while( p!=NULL ) while( p!=NULL ) / /逐个检测逐个检测p p结点存在与否结点存在与否 len+;len+; p=p-next; p=p-next; / /指针后移指针后移 return len;return len; LNode* LinkList:GetElemPointer(int pos) if(posnext;/p为为首首

21、元元结结点指针点指针 int k=1; while( p!=NULL & knext; k+; if(k=pos&p!=NULL) return p; /返返回回第第pos个个结结点指针点指针 else return NULL; /该位置不存在该位置不存在 返回单链表中指定序号的结点的指针返回单链表中指定序号的结点的指针Lnode* newnode=new LNode;newnode-data=x;newnode-next=previous-next;previous-next=newnode;单链表类的插入算法从表头开始从表头开始寻找插入位置寻找插入位置判定插入位置有错否判定插入位置有错否申

22、请新结点申请新结点修改链表指针，将新结点插入链表中修改链表指针，将新结点插入链表中void LinkList:InsertList( int i, ElemType x) LNode *p=head; p=GetElemPointer(i-1); /p最最终终将将指指向向第第i-1个结点个结点 if(!p) cout idata = x; s-next=p-next; /定义结点定义结点s的指针域的指针域 p-next=s;/修改结点修改结点p的指针域的指针域 Ai-1AiXpsp-next=s;新结点链入表中示意图s-next=p-next;previous-next=current-nex

23、t;delete current;单链表类的删除算法判定空表判定空表寻找插入位置寻找插入位置确认插入有错否确认插入有错否修改链表指针修改链表指针收回结点空间收回结点空间LNode*LinkList:DeleteList(inti)if(i1)cout”不存在第不存在第”i”个元素个元素”;elseLNode*p=head;/p指向头结点指向头结点(第第0个结点个结点)LNode*q; /q和和p最终分别指向第最终分别指向第i-1和第和第i个个结点结点intk=0;while(p!=NULL&knext;k+;if(p=NULL)coutinext=p-next; /从链表中删除该结点从链表中删

24、除该结点deletep;/释放结点释放结点pAi-1Aiq-next=p-next;deletep;Ai+1qp删除Ai结点示意图XX可可以以按按照照数数据据元元素素本本身身的的值值进进行行查查找找，也也可可以以按按照照数数据据元元素素的的某某个个属属性性进进行行查查找找。这这里里仅仅给给出出按按照照数据元素本身的值进行查找的算法。数据元素本身的值进行查找的算法。在单链表中查找数据值为在单链表中查找数据值为x x的结点的结点LNode* LinkList:Find( ElemType x ) LNode *p=head-next; /p指向第一个元素所指向第一个元素所在结点在结点 while

25、( p!=NULL & p-data!=x ) p = p-next; return p; 循环链表headA1AnA2head空循环链表空循环链表非空循环链表非空循环链表前驱指针域前驱指针域prior后继指针域后继指针域next数据域数据域data双向链表结点示意图双向链表结点示意图每个数据元素存储结构如下：每个数据元素存储结构如下：head.ana2a1 约瑟夫环问题可以解释为：将整数约瑟夫环问题可以解释为：将整数1 1至至n n围围成一个圆圈，假定从某个整数开始顺时针成一个圆圈，假定从某个整数开始顺时针从从1 1数到数到m m时，令该位置整数出列；然后再时，令该位置整数出列；然后再从下一

26、数开始，顺时针从从下一数开始，顺时针从1 1数到第数到第m m时再令时再令其出列，如此下去，直到圆圈中无整数为其出列，如此下去，直到圆圈中无整数为止。请写出所有数字出列的顺序。止。请写出所有数字出列的顺序。 链表应用举例链表应用举例 演示【演示【例例2-2】2-2.2-2.cppcpp堆栈堆栈stack探讨货仓工作原理探讨货仓工作原理假设只有一个门的货仓，先进去的货物后出来。假设只有一个门的货仓，先进去的货物后出来。若线性表比照货仓，货物比照数据元素。若线性表比照货仓，货物比照数据元素。元素只能在线性表的一端插入删除。元素只能在线性表的一端插入删除。堆栈的定义堆栈的定义堆栈堆栈指插入和删除元素

27、操作只能在表指插入和删除元素操作只能在表的一端进行，这种线性表称为堆栈。的一端进行，这种线性表称为堆栈。堆栈又称堆栈又称LIFOLIFO表或表或FILOFILO表表DCBA插入插入进栈进栈删除删除出栈出栈栈顶栈顶栈底栈底创建一个堆栈：创建一个堆栈：setnull(stack)setnull(stack)判空栈：判空栈： emptystack(stack)emptystack(stack)元素进栈：元素进栈： push(stack,data)push(stack,data)元素出栈：元素出栈： pop(stack)pop(stack)取栈顶元素：取栈顶元素： gettop(stack)getto

28、p(stack)堆栈的基本操作由于栈是一个特殊线性表，顺序栈类与顺序表基本相由于栈是一个特殊线性表，顺序栈类与顺序表基本相同。同。类似于线性表的顺序存储结构，顺序栈类的类似于线性表的顺序存储结构，顺序栈类的C+C+描述如描述如下：下：#defineSTACKSIZE100classSeqStackpublic:ElemTypedataSTACKSIZE;/存储元存储元素的数组素的数组inttop;SeqStack()top=-1;/构造函构造函数数BOOLstack_empty();/判栈空判栈空函数函数BOOLpush(ElemTypex);/元素进元素进栈函数栈函数BOOLpop(Elem

29、Type&result);/元素出元素出栈函数栈函数BOOLgettop(ElemType&result);/取栈顶取栈顶元素元素stack();顺序栈类定义A1A1A2A2A3A3A4A4A5A5A6A6内存储器内存储器toptop5 5 栈顶栈顶0 0 栈底栈底进栈进栈出栈出栈进栈的核心操作：进栈的核心操作：top+;top+;datatop=X;datatop=X;出栈的核心操作：出栈的核心操作：X=datatop;X=datatop;top-;top-;1 12 23 34 4顺序栈类的进栈函数第第1步：判断栈是否已满，若栈满则元素不步：判断栈是否已满，若栈满则元素不 能进栈，退出函数

30、；能进栈，退出函数；第第2步：栈顶下标变量步：栈顶下标变量top增增1，即，即top+；第第3 3步：在步：在toptop所指向的当前位置存入元素所指向的当前位置存入元素x x。 BOOLSeqStack push(ElemTypex)if(top=STACKSIZE-1)cout栈满。又称栈溢出栈满。又称栈溢出(上溢上溢)n;returnFALSE;elsetop+;datatop=x;returnTRUE;顺序栈类的出栈函数第第1步：判定栈是否为空栈，若为空则无元步：判定栈是否为空栈，若为空则无元 素可以出栈，退出函数；素可以出栈，退出函数；第第2步：弹出（删除）栈顶元素；步：弹出（删除）

31、栈顶元素；第第3 3步：栈顶下标变量步：栈顶下标变量toptop减减1 1，即，即top-top-。 BOOLSeqStack pop(ElemType&result)if(top=1)cout栈空栈空.又称栈溢出又称栈溢出(下溢下溢)n;returnfalse;elseresult=datatop;top-;returntrue;顺序栈类的取栈顶函数第第1步：判定栈是否为空栈，若为空则无元步：判定栈是否为空栈，若为空则无元 素可以出栈，退出函数；素可以出栈，退出函数；第第2步：弹出（删除）栈顶元素；步：弹出（删除）栈顶元素；BOOLSeqStack gettop(ElemType&resul

32、t)if(top=1)coutdata=x;p-next=top;top=p;链栈进栈操作若栈不空，则删除栈顶元素，用若栈不空，则删除栈顶元素，用result返回其值。返回其值。void LinkStack:Pop(ElemType &result);SNode *p;if(top!=NULL)result = top-data;p=top;top=top-next;delete p;链栈出栈操作三种不同的表示方法：三种不同的表示方法：前缀表示法前缀表示法 OPOPS S1 1S S2 2 例如例如6+36+3写成写成+63+63中缀表示法中缀表示法 S S1 1OPOPS S2 2 例如例如

33、6+36+3写成写成6+36+3后缀表示法后缀表示法 S S1 1S S2 2OPOP 例如例如6+36+3写成写成63+63+算术表达式表示算术表达式表示同时，任何表达式都可分解为下列形式：同时，任何表达式都可分解为下列形式： ( (子表达式子表达式E E1 1)()(运算符运算符OPOP)()(子表达式子表达式E E2 2) )它的后缀表示法应写成：它的后缀表示法应写成：( (E E1 1的后缀表示的后缀表示)()(E E2 2的后缀表示的后缀表示) )OPOP只要不断对子表达式进一步分解，总能将子表达只要不断对子表达式进一步分解，总能将子表达式分解为最简单形式，因此任何四则运算表达式式分

34、解为最简单形式，因此任何四则运算表达式都可写成前缀式或后缀式。都可写成前缀式或后缀式。例如：例如： 2* 2*(6+3)(6+3) 2 2(6+3)(6+3)* * 2 263+63+* *。 ( (注意：转化为后缀式后括号去掉注意：转化为后缀式后括号去掉) )算术表达式表示算术表达式表示用后缀式求值的算法为：用后缀式求值的算法为：首先设立一个堆栈，依此读取后缀式中的字符首先设立一个堆栈，依此读取后缀式中的字符若字符是数字，则进栈并继续读取若字符是数字，则进栈并继续读取若字符是运算符，则连续出栈两次得到数字若字符是运算符，则连续出栈两次得到数字S S1 1和和S S2 2计算表达式计算表达式S

35、 S1 1OPOPS S2,2,并将结果入栈，并将结果入栈，继续读取后缀式。当读到结束符时停止读操作继续读取后缀式。当读到结束符时停止读操作这时堆栈中只应该有一个数据，即结果数据。这时堆栈中只应该有一个数据，即结果数据。后缀表达式求值后缀表达式求值 例如后缀式例如后缀式263+*263+*的计算过程为的计算过程为2 2、6 6、3 3依次依次入栈，读入栈，读+ +号则令号则令3 3和和6 6依次出栈，计算依次出栈，计算6+36+3后将结后将结果果9 9入栈，读入栈，读* *号则令号则令9 9和和2 2依次出栈，计算依次出栈，计算2*92*9后后将结果将结果1818入栈。这时入栈。这时1818就

36、是最终结果。就是最终结果。【例【例2-32-3】假定表达式是由不超过四个实数进行】假定表达式是由不超过四个实数进行四则运算构成的算式，要编写一个程序来求解该四则运算构成的算式，要编写一个程序来求解该算式的结果。算式的结果。运行运行2_3.2_3.cppcpp举例计算后缀表达式举例计算后缀表达式中缀式变成后缀式中缀式变成后缀式转换规则是：转换规则是：设立一个栈，存放运算符，首先栈为空设立一个栈，存放运算符，首先栈为空设立一个栈，存放运算符，首先栈为空设立一个栈，存放运算符，首先栈为空编译程序从左到右扫描中缀表达式编译程序从左到右扫描中缀表达式编译程序从左到右扫描中缀表达式编译程序从左到右扫描中缀

37、表达式若若若若遇遇遇遇到到到到操操操操作作作作数数数数，直直直直接接接接输输输输出出出出，并并并并输输输输出出出出一一一一个个个个空空空空格格格格作作作作为为为为两两两两个操作数的分隔符个操作数的分隔符个操作数的分隔符个操作数的分隔符若若若若遇遇遇遇到到到到运运运运算算算算符符符符，则则则则必必必必须须须须与与与与栈栈栈栈顶顶顶顶比比比比较较较较，运运运运算算算算符符符符级级级级别别别别比比比比栈栈栈栈顶顶顶顶级级级级别别别别高高高高则则则则进进进进栈栈栈栈，否否否否则则则则退退退退出出出出栈栈栈栈顶顶顶顶元元元元素素素素并并并并输输输输出出出出，然后输出一个空格作分隔符然后输出一个空格作分隔

38、符然后输出一个空格作分隔符然后输出一个空格作分隔符若若若若遇遇遇遇到到到到左左左左括括括括号号号号，进进进进栈栈栈栈；若若若若遇遇遇遇到到到到右右右右括括括括号号号号，则则则则一一一一直直直直退退退退栈栈栈栈输出，直到退到左括号止输出，直到退到左括号止输出，直到退到左括号止输出，直到退到左括号止当栈变成空时，输出的结果即为后缀表达式。当栈变成空时，输出的结果即为后缀表达式。当栈变成空时，输出的结果即为后缀表达式。当栈变成空时，输出的结果即为后缀表达式。步骤步骤栈中元素栈中元素输出结果输出结果说明说明1(（进栈（进栈2(1输出输出13( +1+进栈进栈4( +1 2输出输出251 2 +退栈输出

39、，退栈退栈输出，退栈到（止到（止6*1 2 +*进栈进栈7* (1 2 +（进栈（进栈8* ( (1 2 +（进栈（进栈9* ( (1 2 + 8输出输出810* ( ( -1 2 + 8- 进栈进栈将中缀表达式将中缀表达式(1+2)*(8-2)/(7-4)(1+2)*(8-2)/(7-4)变成等价的变成等价的后缀表达式。后缀表达式。现在用栈来实现该运算，栈的变化现在用栈来实现该运算，栈的变化及输出结果如下：及输出结果如下：11* ( ( -1 2 + 8 2输出输出212* (1 2 + 8 2 -退栈输出，退退栈输出，退栈到（止栈到（止13* ( /1 2 + 8 2 -/ 进栈进栈14*

40、 ( / (1 2 + 8 2 -（ 进栈进栈15* ( / (1 2 + 8 2 - 7输出输出716* ( / ( -1 2 + 8 2 - 7- 进栈进栈17* ( / ( -1 2 + 8 2 - 7 4输出输出418* ( /1 2 + 8 2 - 7 4 -退栈输出，退退栈输出，退栈到（止栈到（止19*1 2 + 8 2 - 7 4 - /退栈输出，退退栈输出，退栈到（止栈到（止201 2 + 8 2 - 7 4 - / *退栈并输出退栈并输出对头对头队尾队尾队列类似日常生活中的排队原理队列类似日常生活中的排队原理LILO表表FIFO表表分析进队顺序：分析进队顺序：A,B,C则出队

41、顺序有哪些？则出队顺序有哪些？进队进队出队出队队列队列也是特殊的线性表。它只允许在线性表的一个端也是特殊的线性表。它只允许在线性表的一个端点进行插入，而在线性表的另一个端点进行删除操作点进行插入，而在线性表的另一个端点进行删除操作ABCD EFG队列的五种基本运算队列的五种基本运算类似于顺序表类的定义，类似于顺序表类的定义，C+描述如下：描述如下：constintQUEUESIZE=200;classSeqQueuepublic:ElemTypedataQUEUESIZE;intfront,rear;SeqQueue()front=rear=1;/创创建空队列建空队列BOOLqueue_emp

42、ty();/判判队列空队列空BOOLaddqueue(ElemTypex);/元元素进队素进队BOOLdelqueue(ElemType&element);/元元素出队素出队BOOLfrontgueue(ElemType&element);/取取队头队头queue();顺序队列类定义入列操作：入列操作： rear+;rear+; datarear=X; datarear=X;出列操作：出列操作： front+;front+; X = datafront; X = datafront;分析：队列空的条件分析：队列空的条件 front = rearfront = rear 队列满的条件队列满的条件

43、 rear = QUEUESIZE-1rear = QUEUESIZE-1 分析队列操作分析队列操作队列假满的状态队列假满的状态front=rear=QUEUESIZE-1或或front-1&rear=QUEUESIZE-1假设假设MAXSIZE为为8rear front E F G H front rear解决假满的两种方法：解决假满的两种方法：1、整个队列中的元素左移、整个队列中的元素左移2、构造循环队列、构造循环队列入列操作：入列操作：rear=(rear+1)%QUEUESIZE;datarear=X;出列操作：出列操作：front=(front+1)%QUEUESIZE;X=data

44、front;循环队列示意图循环队列示意图0 17 26 35 40 1 2 3 4 5 6 7为了将队空和对满的条件加以区分，一般不使用为了将队空和对满的条件加以区分，一般不使用front指针所指的位置。指针所指的位置。队空条件为队空条件为:front=rear队满条件为队满条件为:(rear+1)%QUEUESIZE=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE ( (a)a)循环队列空循环队列空 ( (b)b)非空循环队列非空循环队列 ( (c)c)循环队列满循环队列满 循环队列示意图循环队列示意图/

45、循环队列进队函数循环队列进队函数bool SeqQueue:addqueue(ElemType x) if(rear+1)%MAXSIZE=front) printf(“队列已满，元素不能进队列！队列已满，元素不能进队列！n”); return false; else real=(real+1)%MAXSIZE; datareal=x; return true; /循环队列出队函数循环队列出队函数bool SeqQueue:delqueue( ElemType &x) if(front=rear) printf(“队列已空，无法删除元素队列已空，无法删除元素 n n”); return fal

46、se; else front=(front+1)%QUEUESIZE; x=datafront; return true; 链队列链队列队列链式存储队列链式存储 链队列实质上就是只能在头部删除元素、只链队列实质上就是只能在头部删除元素、只能在尾部插入元素的单链表。能在尾部插入元素的单链表。队头指针队头指针frontfront就是单链表的头指针，队尾就是单链表的头指针，队尾指针指针rearrear则是指向单链表最后一个结点的指针。则是指向单链表最后一个结点的指针。 Qa1anfrontrear非空链队列非空链队列 structQNode/类似于单链表的类似于单链表的C+描述如下：描述如下：Ele

47、mTypedata;structQNode*next;classLinkQueuepublic:QNode*front;/队头指针队头指针QNode*rear;/队尾指针队尾指针LinkQueue()front=newQNode; /建立头结点建立头结点front-next=NULL;rear=front;/尾指针也指向头结点尾指针也指向头结点intLength();/求求队队列列长长度度voidEnQueue(ElemTypex);/入入队队操操作作voidDeQueue(ElemType&e);/出出队队操操作作voidGetHead(ElemType&e);/求求队队头头元素元素;链队列

48、返回队列的元素个数，即队列的长度。返回队列的元素个数，即队列的长度。 int LinkQueue:Length() QNode * p=front;int len=0;while(p!=rear)len+;p= p-next;return len;求队列的长度求队列的长度链队列进队算法：链队列进队算法： 1、申请新结点、申请新结点 2、链入新结点、链入新结点voidLinkQueue:EnQueue(ElemTypex)QNode*s=newQNode;/建立新结点建立新结点ss-data=x;s-next=NULL;rear-next=s; /在队尾插入结点在队尾插入结点srear=s;/修

49、改队尾指针修改队尾指针链队列进队算法链队列出队算法：链队列出队算法： 1、判断队列空否、判断队列空否 2、队头元素出队、队头元素出队 3、出队元素归还操作系统、出队元素归还操作系统voidLinkQueue:DeQueue(ElemType&e)QNode*p;if(front=rear)coutnext;e=p-data;front-next=p-next;if(rear=p)rear=front;deletep;删除最后一个元素时，需要修改尾指针，使其指向头结点删除最后一个元素时，需要修改尾指针，使其指向头结点上机练习一：求两个链表的交集上机练习一：求两个链表的交集解决方法解决方法解决方法

50、解决方法: : : : 建立两个带头结点的单链表；建立两个带头结点的单链表； 通过插入函数插入两个链表中的所有元素通过插入函数插入两个链表中的所有元素 创建第三个带头结点的单带头结点的单链表 从两个表头开始循环比较，只有相等才能插入上机练习二：求上机练习二：求k阶斐波那切数列某一项阶斐波那切数列某一项k阶斐波那切数列阶斐波那切数列ai定义如下：定义如下：解决方法解决方法解决方法解决方法: : : : 建立一个容量为建立一个容量为k k的循环队列，将前的循环队列，将前k k个个元素依次入队。然后计算第元素依次入队。然后计算第k+1k+1个元素，它等于队列个元素，它等于队列中全部元素之和。而后将对

51、头元素出队，将第中全部元素之和。而后将对头元素出队，将第k+1k+1个个元素入队。重复上述过程，就可求得任意指定项元元素入队。重复上述过程，就可求得任意指定项元素的值素的值。【例例2-4】利用循环队列求】利用循环队列求k阶斐波那切数列阶斐波那切数列 某一式的值。某一式的值。 前面所学的数据结构都是线性关系结构，即每个数前面所学的数据结构都是线性关系结构，即每个数据元素都只有唯一的前驱元素和唯一的后继元素。据元素都只有唯一的前驱元素和唯一的后继元素。 但是在客观世界中数据元素之间的关系不一定是线但是在客观世界中数据元素之间的关系不一定是线性关系，即不一定是唯一的前驱和唯一的后继，称为非性关系，即

52、不一定是唯一的前驱和唯一的后继，称为非线性关系结构。线性关系结构。 例如分析任何一个企事业单位的组织机构，会发现例如分析任何一个企事业单位的组织机构，会发现任何一个部门机构，它只隶属于一个部门机构，而下辖任何一个部门机构，它只隶属于一个部门机构，而下辖一个以上部门机构。假如把部门机构看成数据元素，那一个以上部门机构。假如把部门机构看成数据元素，那么可以说任何一个数据元素有唯一的前驱元素，但有多么可以说任何一个数据元素有唯一的前驱元素，但有多个后继元素。个后继元素。 又例如日常生活中对事物的分类又例如日常生活中对事物的分类水果的分类。水果的分类。非线性数据结构：树和图 西安交通大学管理学院电信学

53、院医学院信控系计算机系电子系组织机构示意水果芒果苹果梨香蕉红富士黄元帅秦冠巴拿马芝麻水果分类示意RAEGDCBXFZYKJIHMLNPOQVUTS*+%将上述分层结构抽象成如下所示的结构倒置树 树是包含树是包含n n个数据元素的有限集合个数据元素的有限集合T T（n1n1），并且），并且满足：满足：（1 1）T T中有一个称为根的结点中有一个称为根的结点rootroot；（2 2）T T中除根以外的其余结点被分成中除根以外的其余结点被分成m m（nm0nm0）个）个互不相交的集合互不相交的集合T T1 1、T T2 2、T Tm m，且每一个集合又符合，且每一个集合又符合上述两条，即它上述两条

54、，即它们本身又是一棵树，这些树称为们本身又是一棵树，这些树称为rootroot的子树。的子树。树的递归定义T1T2TNT3T4GACFDEB树的一般形式树的一般形式结点结点表示树中的数据元素；表示树中的数据元素；树枝树枝表示树中的数据元素与数据元素之间的关系；表示树中的数据元素与数据元素之间的关系；叶子结点叶子结点表示没有后继的结点称为叶子（或终端结点）；表示没有后继的结点称为叶子（或终端结点）；分支结点分支结点表示非叶子结点称为分支结点（或非终端结点）；表示非叶子结点称为分支结点（或非终端结点）；结点的度结点的度意指一个结点的子树数目就称为该结点的度；意指一个结点的子树数目就称为该结点的度；

55、树的度树的度意指一棵树上所有结点的度的最大值就是这棵树的度；意指一棵树上所有结点的度的最大值就是这棵树的度；结点的层次结点的层次确定根结点的层数为确定根结点的层数为1 1，其它任何结点的层数等于，其它任何结点的层数等于 它的父结点的层数加它的父结点的层数加1 1；有关树的基本术语树的深度树的深度意指一棵树中，结点的最大层次值就是树的深度；意指一棵树中，结点的最大层次值就是树的深度；孩子结点孩子结点代表某结点的子树的根称为该结点的孩子结点；代表某结点的子树的根称为该结点的孩子结点；双亲结点双亲结点相对于某结点的前驱结点，称该结点为双亲结点；相对于某结点的前驱结点，称该结点为双亲结点；兄妹兄妹意指

56、同属于一个双亲的孩子结点之间互称为兄弟；意指同属于一个双亲的孩子结点之间互称为兄弟；堂兄妹堂兄妹意指其双亲在同一层的结点之间互称为兄弟；意指其双亲在同一层的结点之间互称为兄弟；有序树有序树如果一棵树中结点的各子树看成是从左至右依次有序排如果一棵树中结点的各子树看成是从左至右依次有序排 列且不能交换，则该树就称为有序树；列且不能交换，则该树就称为有序树；无序树无序树如果一棵树中结点的各子树可以互换排列次序，则该树如果一棵树中结点的各子树可以互换排列次序，则该树 称为无序树；称为无序树；森林森林森林是森林是n n棵互不相交的树的集合（棵互不相交的树的集合（n0n0）；）；建空树建空树 记作记作se

57、tnull(T)setnull(T)，置，置T T为空树。为空树。求根结点求根结点 记作记作root(x)root(x)，求，求x x所在树的根结点。所在树的根结点。求双亲结点求双亲结点 记作记作parent(Tparent(T，x)x)，在树，在树T T中取出结点中取出结点x x的双亲。的双亲。求孩子结点求孩子结点 记作记作child(T,x,i)child(T,x,i)，在树，在树T T中取出结点中取出结点x x的第的第i i个孩子。个孩子。插入结点插入结点 记作记作ins_child(T,y,i,x)ins_child(T,y,i,x)，将，将x x作为树作为树T T中中y y结点的第结

58、点的第i i个孩子。个孩子。删除子树删除子树 记作记作del_child(T,x,I)del_child(T,x,I)，即删除树，即删除树T T中中x x结点的第结点的第i i棵子树。棵子树。 遍历树遍历树 记作记作TRAVERSE(T)TRAVERSE(T)，即从根结点出发，按某种次序，依次访问树，即从根结点出发，按某种次序，依次访问树 中每个结点，且每个结点只访问一次的操作。中每个结点，且每个结点只访问一次的操作。树的基本运算二叉树的定义二叉树是二叉树是n n（n0n0）个结点的有限集合，且满足以）个结点的有限集合，且满足以下两条下两条: :(1)(1)或者为空二叉树，即或者为空二叉树，即

59、n=0n=0；(2)(2)或者由一个根结点和两棵互不相交的被称为根或者由一个根结点和两棵互不相交的被称为根的左子树和右子树所组成，左子树和右子树分别的左子树和右子树所组成，左子树和右子树分别又是一棵二叉树。又是一棵二叉树。问题：问题：1 1、二叉树可以定义为度不大于、二叉树可以定义为度不大于2 2的树？的树？ 2 2、三个结点的二叉树有几种形态？、三个结点的二叉树有几种形态？探讨结构较为简单的一类树，二叉树探讨结构较为简单的一类树，二叉树创建空二叉树创建空二叉树 记作记作setnull(BT)setnull(BT)，置，置BTBT为空二叉树。为空二叉树。求二叉树的根求二叉树的根 记作记作roo

60、t(x)root(x)，求结点，求结点x x所在二叉树的根。所在二叉树的根。求双亲结点求双亲结点 记作记作parent(BT,x)parent(BT,x)，在二叉树中求结点，在二叉树中求结点x x的双亲。的双亲。求左孩子结点求左孩子结点 记作记作lchild(BT,x),lchild(BT,x),在二叉树在二叉树BTBT中求结点中求结点x x的左孩子。的左孩子。求右孩子结点求右孩子结点 记作记作rchild(BT,x),rchild(BT,x),在二叉树在二叉树BTBT中求结点中求结点x x的右孩子。的右孩子。插入左孩子结点插入左孩子结点 记作记作ins_lchild(BT,x,y),ins_

61、lchild(BT,x,y),将结点将结点y y置为结点置为结点x x的左孩子。的左孩子。插入右孩子结点插入右孩子结点 记作记作ins_rchild(BT,x,y),ins_rchild(BT,x,y),将结点将结点y y置为结点置为结点x x的右孩子。的右孩子。删除左孩子删除左孩子 记作记作del_lchild(BT,x),del_lchild(BT,x),在二叉树在二叉树BTBT中，删除结点中，删除结点x x的左子树。的左子树。删除左孩子删除左孩子 记作记作del_rchild(BT,x),del_rchild(BT,x),在二叉树在二叉树BTBT中，删除结点中，删除结点x x的右子树。的

62、右子树。遍历二叉树遍历二叉树 记作记作TRAVERSE(BT),TRAVERSE(BT),即从根结点出发，按某种次序，依次访问即从根结点出发，按某种次序，依次访问 二叉树中每个结点，且每个结点只访问一次。二叉树中每个结点，且每个结点只访问一次。二叉树的基本操作左指针域左指针域数据域数据域 右指针域右指针域二叉树的非顺序存储结构 根据二叉树的特性：任何一个结点最多有左、根据二叉树的特性：任何一个结点最多有左、右两个子树，这样可以为树中每个数据元素设计右两个子树，这样可以为树中每个数据元素设计三个存储区域（或称变量）。三个存储区域（或称变量）。 一个域用来存放数据元素值，两个域用来存一个域用来存放

63、数据元素值，两个域用来存放指向左右子树根的指针。也就是说对于二叉树放指向左右子树根的指针。也就是说对于二叉树中任意一个数据元素可以设计成如下存储结构。中任意一个数据元素可以设计成如下存储结构。俗称结点。俗称结点。二叉树的二叉链表存储结构示意图ABCFEGDABCDEGFVVVVVVVVstructBinTreeNode/结点的定义结点的定义ElemTypedata;structBinTreeNode*leftChild,*rightChild;classBinTree/二叉链表类的定义二叉链表类的定义public:BinTreeNode*root;/定义根结点指针定义根结点指针BinTree(

64、)root=NULL;/构造函数，创建空树构造函数，创建空树boolIsEmpty()returnroot=NULL;/判空二叉树判空二叉树voidIns_lchild(BinTreeNode*p,BinTreeNode*q)p-leftChild=q;/在叶子结点在叶子结点p p下插入左子树下插入左子树q qvoidIns_rchild(BinTreeNode*p,BinTreeNode*q)p-rightChild=q;/在叶子结点在叶子结点p p下插入右子树下插入右子树q q/删除结点删除结点p p的左子树的左子树voidDel_lchild(BinTreeNode*p)p-leftCh

65、ild=NULL;/删除结点删除结点p p的右子树的右子树voidDel_rchild(BinTreeNode*p)p-rightChild=NULL;voidPreOrder(BinTreeNode*t); /先序遍历先序遍历voidInOrder(BinTreeNode*t);/中序遍历中序遍历voidPostOrder(BinTreeNode*t);/后序遍历后序遍历;注意：上述性质都可以通过归纳方法进行证明。注意：上述性质都可以通过归纳方法进行证明。二叉树的性质性质一性质一：二叉树的第：二叉树的第i i层上至多有层上至多有2 2i-1i-1（i1i1）个结点。）个结点。性质二性质二：深

66、度为：深度为h h的二叉树上最多含有的二叉树上最多含有2 2h h-1-1个结点。个结点。性质三性质三：包含：包含n n个结点的二叉树必有个结点的二叉树必有n-1n-1条树枝条树枝( (分枝分枝) )。性质四性质四：任何一棵二叉树，若含有：任何一棵二叉树，若含有n n0 0个叶子结点、个叶子结点、n n2 2个个 度为度为2 2的结点，则必存在关系式的结点，则必存在关系式n n0 0=n=n2 2+1 +1 。若一棵二叉树的深度为若一棵二叉树的深度为h h，且含有，且含有2 2h h-1-1个结点，则称该二叉树为个结点，则称该二叉树为满二叉树满二叉树。AABCABCDEGF深度为深度为1 1

67、深度为深度为2 2 深度为深度为5 5满二叉树深度为4的满二叉树编号规则：编号规则： 设满二叉树的深度是设满二叉树的深度是h h，根结点的编号为，根结点的编号为1 1，其余结点，其余结点的编号次的编号次序是从上层到下层，每层从左到右。序是从上层到下层，每层从左到右。推论：推论：1 1）若）若11i2i2h-1h-1-1-1，则结点，则结点i i的左子树根的编号为的左子树根的编号为2*2*i i，结点，结点i i的右子树根的编号为的右子树根的编号为2*2*i+1i+1； 2 2）若）若11i2i2h h-1-1，则结点，则结点i i的父结点的编号为的父结点的编号为( (int)(i/2)int)

68、(i/2)；124589101136712131415设一个深度为设一个深度为h h的二叉树，每层结点数目如果满足：的二叉树，每层结点数目如果满足：1 1）第）第i i层（层（11ih-1ih-1）上的结点个数均为）上的结点个数均为2 2i i-1-1；2 2）第）第h h层从右边起连续缺若干个结点。层从右边起连续缺若干个结点。这样的二叉树称为完全二叉树。这样的二叉树称为完全二叉树。ABCDEGFH完全二叉树ABCDE从满二叉树叶从满二叉树叶子所在的层次子所在的层次中，自右向左中，自右向左连续删除若干连续删除若干叶子所得到的叶子所得到的二叉树被称为二叉树被称为完全二叉树。完全二叉树。 首先将任

69、何一棵二叉树转变为相同深度的完全二叉树，首先将任何一棵二叉树转变为相同深度的完全二叉树，即通过编号顺序，在每一层加上一些空结点，以便保证第即通过编号顺序，在每一层加上一些空结点，以便保证第i i层上有层上有2 2i-1i-1个结点。其次将实结点和空结点依次存入一维个结点。其次将实结点和空结点依次存入一维数组中。数组中。ABCDEFGHABCDEFGH0123456789101112A B C DE FG H任何一棵二叉树都可用一维数组来储存的方法ABCDEFG 二叉树的逻辑形态？ ABCDEFGH 二叉树的逻辑形态？ABCDEGFABCDEGFH问题二叉树的遍历根据一定的规律访问二叉树中的每一

70、个根据一定的规律访问二叉树中的每一个结点，且每个结点只能访问一次的过程。结点，且每个结点只能访问一次的过程。注意：定义中所提到的访问，对于不同应用问题有不同的注意：定义中所提到的访问，对于不同应用问题有不同的操作意义。例如读取二叉树中的每一个结点的值，进行统操作意义。例如读取二叉树中的每一个结点的值，进行统计计算。又比如修改二叉树中的每一个结点的值等等。计计算。又比如修改二叉树中的每一个结点的值等等。 由于二叉树中每个结点最多有两棵子树，也就是由于二叉树中每个结点最多有两棵子树，也就是说一个结点可能有两个后继，所以，二叉树的遍历方说一个结点可能有两个后继，所以，二叉树的遍历方法会有好几种。可以

71、将二叉树看成如下图所示的三个法会有好几种。可以将二叉树看成如下图所示的三个基本组成部分。基本组成部分。这样一来对二叉树的访问顺序就有六种这样一来对二叉树的访问顺序就有六种 DLR DLR 先根遍历先根遍历 LDR LDR 中根遍历中根遍历 LRD LRD 后根遍历后根遍历 DRLDRL RDLRDL RLDRLD 先序遍历先序遍历a.a.访问根结点；访问根结点； b.b.先序遍历左子树；先序遍历左子树； c.c.先序遍历右子树；先序遍历右子树；中序遍历中序遍历a.a.中序遍历左子树；中序遍历左子树； b.b.访问根结点；访问根结点； c.c.中序遍历右子树；中序遍历右子树；后序遍历后序遍历a.

72、a.后序遍历左子树；后序遍历左子树； b.b.后序遍历右子树；后序遍历右子树； c.c.访问根结点；访问根结点；二叉树的三种遍历方式ABCDEGFABCDEGFH讨论下列两棵二叉树的遍历先根遍历结果：先根遍历结果：中根遍历结果：中根遍历结果：后根遍历结果：后根遍历结果：/假设二叉树存储以二叉链表结构假设二叉树存储以二叉链表结构voidBinTree:PreOrder(BinTreeNode*t)if(t)Visit(t);/访问根结点访问根结点PreOrder(t-leftChild);/遍历左子树遍历左子树PreOrder(t-rightChild);/遍历右子树遍历右子树先序遍历二叉树的递

73、归算法先序遍历二叉树的递归算法/中序遍历算法中序遍历算法voidBinTree:InOrder(BinTreeNode*t)if(t)InOrder(t-leftChild);/遍历左子树遍历左子树Visit(t);/访问根节点访问根节点InOrder(t-rightChild);/遍历右子树遍历右子树/后序遍历算法后序遍历算法voidBinTree:PostOrder(BinTreeNode*t)if(t)PostOrder(t-leftChild);/遍历左子树遍历左子树PostOrder(t-rightChild);/遍历右子树遍历右子树Visit(t);/访问根节点访问根节点非线性数据

74、结构：图 图是中一种重要的、比树更复杂的非线性数据结图是中一种重要的、比树更复杂的非线性数据结构。构。 在树中，每个结点只与上层的父结点有联系，并在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系，而同一层的结点可以与其下层的多个子结点有联系，而同一层的结点之间没有任何横向联系。之间没有任何横向联系。 在图中，结点之间的联系是任意的，每个结点都在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。可以与其它的结点相联系。 图的应用范围非常广泛，诸如电网络分析、交通、图的应用范围非常广泛，诸如电网络分析、交通、管道线路、集成电路布图、工程进度安排图等实际问管道线

75、路、集成电路布图、工程进度安排图等实际问题的处理都可以归纳为图的问题题的处理都可以归纳为图的问题图的定义图的定义 图是由数据元素集合及数据元素间图是由数据元素集合及数据元素间的关系集合组成的一种数据结构。一般的关系集合组成的一种数据结构。一般记作记作GraphGraph( V, E )( V, E )。其中。其中V V是数据元是数据元素的非空有限集合；素的非空有限集合；E E是数据元素之间关是数据元素之间关系的有限集合。系的有限集合。边和弧的含义 若若 属于属于R R ，则，则 Vi,Vj表示从顶点表示从顶点V Vi i出发到出发到顶点顶点V Vj j存在存在一条弧一条弧，其中：，其中：V V

76、i i称之为弧尾，称之为弧尾，V Vj j称之为称之为弧头。弧头。ViVj 若（若（V Vi i，V Vj j）属于）属于R R ，则（，则（V Vi i，V Vj j）表示顶点）表示顶点V Vi i和顶点和顶点V Vj j之间存在之间存在一条边一条边。ViVj无向图集合表示：无向图集合表示：G G1 1=(V,E) =(V,E) V=1,2,3,4,5V=1,2,3,4,5E=(1,2),(1,3),(2,3),(3,4),(4,5)E=(1,2),(1,3),(2,3),(3,4),(4,5)12354有向图集合表示：有向图集合表示： G G2 2= =（V V，E E） V=1V=1，2

77、 2，3 3，4 4，5 5，66E=1E=2，21，23，24，3 6，63214356图的符号表示邻接点邻接点：对于无向图，如果边（：对于无向图，如果边（v v，u u）E E，则，则v v和和u u互为互为邻接点，亦即邻接点，亦即u u是是v v的邻接点，的邻接点，v v也是也是u u的邻接点；对于有向的邻接点；对于有向图，如果弧图，如果弧 EuE，则，则u u是是v v的邻接点。的邻接点。顶点的度顶点的度：在无向图中，顶点的度就是以该顶点为一个端：在无向图中，顶点的度就是以该顶点为一个端点的边点的边 的条数。在有向图中，以某顶点为弧头的条数。在有向图中，以某顶点为弧头的弧的数目，称为此

78、顶点的入度；以某顶点为弧尾的弧的的弧的数目，称为此顶点的入度；以某顶点为弧尾的弧的数目，称为此顶点的出度。该顶点的度则是此顶点的入度数目，称为此顶点的出度。该顶点的度则是此顶点的入度与出度之和。与出度之和。路径路径：在图：在图G G中，从顶点中，从顶点v v至顶点至顶点u u的一条路径是指存在这的一条路径是指存在这样的顶点的序列（样的顶点的序列（v v，v v1 1，v v2 2，v vi i，u u），并且有），并且有 ， v,， vu 都属于边（弧）集合。都属于边（弧）集合。长度长度：路径上弧的数目称为该路径的长度。：路径上弧的数目称为该路径的长度。环（回路）环（回路）：第一个顶点和最后一

79、个顶点相同的路径称为：第一个顶点和最后一个顶点相同的路径称为回路或环回路或环有关图的术语连通图连通图：在无向图中，若每一对顶点之间都有路径，此图：在无向图中，若每一对顶点之间都有路径，此图为连通图为连通图强连通图强连通图：在有向图中，若每一对顶点：在有向图中，若每一对顶点u u和和v v之间都在从之间都在从v v到到u u及从及从u u到到v v的路径，则称此图为强连通图。的路径，则称此图为强连通图。网网：如果图：如果图G G（V V，E E）中每条边（弧）都赋有反映这条边）中每条边（弧）都赋有反映这条边的某种特性的数据，则称此图是一个网。的某种特性的数据，则称此图是一个网。权权：与边（弧）相

80、关的数据称为该边的权。：与边（弧）相关的数据称为该边的权。通常我们用通常我们用n n表示图中顶点数目，表示图中顶点数目，e e表示图中边或弧的数目，表示图中边或弧的数目，并且下并且下面的讨论不涉及顶点到自身的边或弧，因此面的讨论不涉及顶点到自身的边或弧，因此, ,对于有对于有n n个顶个顶点的有向点的有向图来说图来说, ,其弧的数目有其弧的数目有00enen（n-1n-1）。）。完全有向图完全有向图：在：在n n个顶点的有向图中，具有个顶点的有向图中，具有n n（n-1n-1）条弧）条弧的有向图的有向图 称为完全有向图。称为完全有向图。完全图完全图：在：在n n个顶点的无向图中，具有个顶点的无

81、向图中，具有n(n-1n(n-1）/2/2条边的无条边的无向图向图子图子图：设有图：设有图G=(V,E)G=(V,E)和图和图G=G=（VV，E)E)，若，若VV包含包含在在V V中，且中，且 EE包含在包含在E E中，则称中，则称GG是是G G的子图。的子图。有关图的术语0132528130123410234( (a)a)无向图无向图 ( (b)b)有向图有向图 ( (c)c)网络网络术语提问？ 由于一个图是由顶点集合由于一个图是由顶点集合V V和顶点之间的关系集合和顶点之间的关系集合E E( (即顶点偶对集合即顶点偶对集合) )。因此，设计一个图的存储结构只要。因此，设计一个图的存储结构只

82、要分别解决集合分别解决集合V V和集合和集合E E的存贮结构表示即可。的存贮结构表示即可。 显然可以用一个一维数组表示集合显然可以用一个一维数组表示集合V V中的所有顶点；中的所有顶点；用一个二维数组来表示集合用一个二维数组来表示集合E E。此二维数组被称为邻接矩。此二维数组被称为邻接矩阵。阵。 对于对于n n个顶点的有向图，则其邻接矩阵中所有元素按个顶点的有向图，则其邻接矩阵中所有元素按如下公式来确定：如下公式来确定： 对于对于n n个顶点的无向图，则其邻接矩阵中所有元素按如下公式个顶点的无向图，则其邻接矩阵中所有元素按如下公式来确定：来确定：图的存储结构图的存储结构: :邻接矩阵邻接矩阵.

83、对于无向图，邻接矩阵第对于无向图，邻接矩阵第i i行（或第行（或第i i列）的元素之和则列）的元素之和则是顶点是顶点V Vi i的度；的度；.对于有向图，邻接矩阵第对于有向图，邻接矩阵第i i行的元素之和为顶点行的元素之和为顶点V Vi i的出的出度；邻接矩阵第度；邻接矩阵第i i列的元素之和为顶点列的元素之和为顶点V Vi i的入度。的入度。12354214356无向图G1 有向图G2# #define MAX_NUM 100 define MAX_NUM 100 / / 最大顶点个数最大顶点个数typedef struct typedef struct VertexType vexsMAX

84、_NUM; / VertexType vexsMAX_NUM; /顶点数组顶点数组 ArcType MatrixMAX_NUMMAX_NUM; /ArcType MatrixMAX_NUMMAX_NUM; /邻接矩阵邻接矩阵 int vexnum; /int vexnum; /图的实际顶点数图的实际顶点数 int arcnum; /int arcnum; /图的实际弧图的实际弧( (边边) )数数 int kind; /int kind; /图的种类标志图的种类标志, 1, 1有向图有向图, , /2 /2有向网有向网,3,3无向图无向图,4,4无向网无向网 MGraph;MGraph; 其其

85、中中ArcTypeArcType是是顶顶点点关关系系的的数数据据类类型型。VertexTypeVertexType是是顶点的数据类型。顶点的数据类型。MAX_NUMMAX_NUM表示最多可存的顶点数。表示最多可存的顶点数。0132528130123410234( (a)a)无向图无向图 ( (b)b)有向图有向图 ( (c)c)网络网络0132401324012340123401230132( (a)a)无向图邻接矩阵无向图邻接矩阵 ( (b)b)有向图邻接矩阵有向图邻接矩阵 ( (c)c)网络邻接矩阵网络邻接矩阵 邻接矩阵反映出图中顶点之间的联系，值得注意的是邻接矩阵反映出图中顶点之间的联系

86、，值得注意的是当一个图为稀疏图时，其邻接矩阵为稀疏矩阵。如果将邻当一个图为稀疏图时，其邻接矩阵为稀疏矩阵。如果将邻接矩阵看成是顺序存储结构，那么，另一种结构就是链式接矩阵看成是顺序存储结构，那么，另一种结构就是链式存贮结构，把一个顶点的所有邻接顶点都链接在同一个单存贮结构，把一个顶点的所有邻接顶点都链接在同一个单链表上。链表上。 邻接表存储形式是一种链表与数组结合的存储形式。邻接表存储形式是一种链表与数组结合的存储形式。在邻接表中，图中每个顶点数据存储为数组，某个顶点的在邻接表中，图中每个顶点数据存储为数组，某个顶点的所有邻接点建立一个单链表，所有邻接点建立一个单链表，n n个顶点就建立个顶点

87、就建立n n个单链表。个单链表。 邻接表中由下列三个结点组成，如下图所示：邻接表中由下列三个结点组成，如下图所示：图的存储结构图的存储结构: :邻接表邻接表firstdatanextadjvex数组元素（头结点）：数组元素（头结点）：无权图中的单链表结无权图中的单链表结点：点：网中的单链表的结点：网中的单链表的结点：infonextadjvex214356#defineMAX_NUM100/顶顶点点最最大大允允许许数数量量structAdjNode/表结点类型定义表结点类型定义intadjvex;/该邻接点在数组中的位置该邻接点在数组中的位置InfoTypeinfo;/该弧相关信息该弧相关信息

88、structAdjNode*next; /指向下一邻接点的指针指向下一邻接点的指针;typedefstructVNode/头结点类型定义头结点类型定义VertexTypedata;/顶点信息顶点信息AdjNode*first;/指向邻接表第一个结点指向邻接表第一个结点AdjList;typedefstructAdjListheadArrayMAX_NUM; /头结点数组头结点数组intvexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数intkind;/图的种类标志图的种类标志ALGraph; 从这个定义不难看出，图的遍历与树的遍历从这个定义不难看出，图的遍历与树的遍历的区别

89、在于，图可以从任意一个顶点出发，而树的区别在于，图可以从任意一个顶点出发，而树的遍历必须沿着树根结点进行。的遍历必须沿着树根结点进行。 遍历图的方法一般有两种：深度优先遍历遍历图的方法一般有两种：深度优先遍历 广度优先遍历。广度优先遍历。图的遍历从图中某一顶点出发访问图中所有的从图中某一顶点出发访问图中所有的顶点，使每个顶点都被访问且仅被访顶点，使每个顶点都被访问且仅被访问一次。这样的过程称为图的遍历。问一次。这样的过程称为图的遍历。深度优先遍历连通图深度优先遍历连通图深度优先遍历的基本思想是：深度优先遍历的基本思想是：1.1.首先访问图首先访问图G G的指定起始顶点的指定起始顶点v v0 0

90、； 2.2.从从v v0 0出发，访问一个与出发，访问一个与v v0 0邻接的顶点邻接的顶点w w1 1后，再后，再从顶从顶 点点w w1 1 出发，访问与出发，访问与w w1 1邻接且未被访问过的顶点邻接且未被访问过的顶点w w2 2 。然后从。然后从w w2 2出发，重复上述过程，直到找不到出发，重复上述过程，直到找不到存存 在未访问过的邻接顶点为止。在未访问过的邻接顶点为止。 3. 3.回退到尚有未被访问过的邻接点的顶点，从该回退到尚有未被访问过的邻接点的顶点，从该顶顶 点出发，重复步骤点出发，重复步骤2 2，步骤，步骤3 3，直到所有被访问，直到所有被访问过过 的顶点的邻接点都已被访问

91、为止。的顶点的邻接点都已被访问为止。 可可见见深深度度优优先先遍遍历历总总是是沿沿着着一一条条路路径径走走到到底底，再再沿沿另一条路另一条路径径走走到到底底。直直到到图图中中所所有有顶顶点点访访问问遍遍。对对于于一一个个连连通通图图（包括强（包括强连连通通图图），从从一一个个顶顶点点出出发发，可可以以访访问问图图中中的的其其它它所所有有顶点。由顶点。由于于连连通通图图中中可可能能存存在在回回路路，因因此此可可能能会会出出现现这这样样的的情情况况：在在访访问问过过某某个个结结点点之之后后，又又顺顺着着某某条条路路径径回回到到该该顶顶点点。为为了了避避免免对对一一个个顶顶点点访访问问两两次次，在在

92、遍遍历历过过程程中中必必须须对对每每个被访问过的顶点作一个访问标志。个被访问过的顶点作一个访问标志。深度优先遍历结果深度优先遍历结果: :V V1 1VV3 3VV5 5VV2 2VV4 4VV6 6A B E F G D C广度优先遍历连通图广度优先遍历连通图广度优先遍历是图的另外一种遍历策略，其基本思广度优先遍历是图的另外一种遍历策略，其基本思想是：想是：1. 1. 访问起始点访问起始点v v0 0； 2. 2. 从从v v0 0出发，依次访问出发，依次访问V V0 0的未被访问过的邻接点的未被访问过的邻接点w w1 1， w w2 2，w wt t。然后依次从。然后依次从w w1 1，w

93、 w2 2，w wt t出发，出发，访访 问各自未被访问过的邻接点。问各自未被访问过的邻接点。 3. 3. 重复步骤重复步骤2 2直到所有顶点都被访问过为止。直到所有顶点都被访问过为止。 上图的广度优先遍历序列为：上图的广度优先遍历序列为：V V1 1VV3 3VV2 2VV4 4VV5 5VV6 6A B E D C F G 设设计计二二进进制制编编码码方方案案时时要要考考虑虑不不同同字字符符的的使使用用频频率率，使使用用频频率率高高的的字字符符编编码码应应当当尽尽量量短短一一些些。但但是是仅仅考虑使用频率也是不够的。仅仅考虑使用频率也是不够的。例例如如：某某个个文文件件由由A、B、C、D四

94、四个个字字符符组组成成，其中其中A用得最多，用得最多，C次之。次之。 方案方案1: A 1 C 0 B 10 D 11 那那么么象象1100这这样样的的二二进进制制数数据据具具有有二二义义性性，既既代代表表AACC，又可代表，又可代表ABC，还可代表，还可代表DCC。为为了了不不使使二二进进制制编编码码具具有有二二义义性性，每每个个字字符符编编码码都不能与其他字符编码的前面若干位重合。都不能与其他字符编码的前面若干位重合。哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编码 BDCA0011AB01DC0011 (a)有二义性的编码系统对应的二叉树 (b)无二义性的编码系统对应的二叉树任任何何一一个个无无

95、二二义义性性的的二二进进制制字字符符编编码码系系统统必必然然与与这这样样一一颗颗二二叉叉树树对对应应，该该二二叉叉树树的的叶叶子子结结点点对对应应着着所所有有需需要要转转换换的的字字符符，并并且且按按照照左左分分支支代代表表0 0、右右分分支支代代表表1 1的的规规则则，从从根根到到该该叶叶子子的的分分支支对对应应的的0 0、1 1序序列列就就构构成成叶叶子子对对应应字字符的二进制编码。符的二进制编码。 可以利用二叉树分析字符编码问题。假设二可以利用二叉树分析字符编码问题。假设二叉树中的左分支代表叉树中的左分支代表0 0，右分支代表，右分支代表1 1，则不，则不论字符是采用何种论字符是采用何种

96、0 0、1 1组合形式构成的编码，组合形式构成的编码，它必然对应某个二叉树中一个结点它必然对应某个二叉树中一个结点。1 1）假设每个字符使用频率是相等的，那么不同字符）假设每个字符使用频率是相等的，那么不同字符的编码长度之和就可衡量编码系统的优劣。而某个的编码长度之和就可衡量编码系统的优劣。而某个字符编码的长度就是对应的二叉树中根到某个叶子字符编码的长度就是对应的二叉树中根到某个叶子的分支的数目（又称为的分支的数目（又称为根到叶子的路径长度根到叶子的路径长度）。）。2 2）如果每个字符使用频率不相等，那么将不同字符）如果每个字符使用频率不相等，那么将不同字符的编码长度乘上其使用权值再加起来，也

97、可衡量编的编码长度乘上其使用权值再加起来，也可衡量编码系统的优劣。也就是用根到每个叶子的路径长度码系统的优劣。也就是用根到每个叶子的路径长度乘以叶子对应字符的使用权值再加起来作为衡量标乘以叶子对应字符的使用权值再加起来作为衡量标准，准，显然这种加权和除以字符总数就是每个字符的显然这种加权和除以字符总数就是每个字符的加权平均编码长度。加权平均编码长度。二叉树带权路径长度二叉树带权路径长度：设二叉树有：设二叉树有n n个带有权值个带有权值的叶子结点，每个叶子到根的路径长度乘以其的叶子结点，每个叶子到根的路径长度乘以其权值之和称为二叉树带权路径长度。权值之和称为二叉树带权路径长度。w wi i为第为

98、第i i个叶子的权重，个叶子的权重，l li i为第为第i i个叶子到根的路径长度。个叶子到根的路径长度。哈夫曼树哈夫曼树：以一些带有固定权值的结点作为叶子，：以一些带有固定权值的结点作为叶子，并具有最小带权路径长度的二叉树称为哈夫曼树。并具有最小带权路径长度的二叉树称为哈夫曼树。哈夫曼树定义哈夫曼树定义HuffmanHuffman最早给出了一个带有规律构造算法，具体如下：最早给出了一个带有规律构造算法，具体如下： 1 1）根据给定的）根据给定的n n个权值个权值 w w1 1，w w2 2，w wn n 构成构成n n棵二叉树的集合棵二叉树的集合 F=F=（T T1 1，T T2 2，T T

99、n n），其中每棵二叉树），其中每棵二叉树T Ti i中只有一个带权中只有一个带权 为为w wi i的根结点，其左右子树均为空。的根结点，其左右子树均为空。 2 2）在）在F F中选取两棵根结点的权值最小的树做为左、右子树构造中选取两棵根结点的权值最小的树做为左、右子树构造 一棵新的二叉树，且置新的二叉树的根结点的权值为其左、一棵新的二叉树，且置新的二叉树的根结点的权值为其左、 右子树上根结点的权值之和。右子树上根结点的权值之和。 3 3）在）在F F中删除这两棵树，同时将新得到的二叉树加入到中删除这两棵树，同时将新得到的二叉树加入到F F中。中。 4 4）重复（）重复（2 2）和（）和（3

100、3）直到）直到F F只含一棵树为止。只含一棵树为止。这棵树便是这棵树便是HuffmanHuffman树。树。 n n个具有权值的结点形成哈夫曼树的构造算法个具有权值的结点形成哈夫曼树的构造算法设有顶点集合设有顶点集合 a a，b b，c c，dd，其权值集合为，其权值集合为3232，4242，7 7，2424构造构造HuffmanHuffman树的过程如下：树的过程如下：假定有一段报文由假定有一段报文由a a、b b、c c、d d四个字符构成，它们的四个字符构成，它们的使用频率比为使用频率比为64216421，则用，则用a a、b b、c c、d d作为叶子作为叶子结点构造哈夫曼树的过程如图

101、所示。结点构造哈夫曼树的过程如图所示。若二叉树中的左分支代表0，右分支代表1,则a、b、c、d的哈夫曼编码分别为0、10、110、111。 【例2-5】假定编码系统中有五个字符假定编码系统中有五个字符X X、S S、D D、E E、A A，它们的使用频率比为，它们的使用频率比为2957829578，以这些频率，以这些频率值作叶子的权构造哈夫曼树，并输出哈夫曼编码。值作叶子的权构造哈夫曼树，并输出哈夫曼编码。 运行运行2_5.2_5.cppcpp 若存在这样的数据元素，则称查找是成功的；若存在这样的数据元素，则称查找是成功的； 若不存在这样的数据元素，若不存在这样的数据元素， 则称查找是不成功的

102、。则称查找是不成功的。查找与排序关键字关键字: :指数据元素中可以标识该数据元素的一组数据项。指数据元素中可以标识该数据元素的一组数据项。例如学生记录中的学号、姓名；公民记录中的身份证号码等。例如学生记录中的学号、姓名；公民记录中的身份证号码等。查找查找：根据给定的关键字值，在一组数据元素中确定：根据给定的关键字值，在一组数据元素中确定一个其关键字值等于给定值的数据元素的过程。一个其关键字值等于给定值的数据元素的过程。一组待查数据元素的集合称为一组待查数据元素的集合称为查找表查找表查找表是具有一定存储结构的数据集合，比如顺查找表是具有一定存储结构的数据集合，比如顺序表结构、链式结构、树形结构等

103、。序表结构、链式结构、树形结构等。静态查找表静态查找表: : 查找表一旦建立，在以后的查找表一旦建立，在以后的查找过程中不会改变表的长度极其内容。查找过程中不会改变表的长度极其内容。动态查找表动态查找表：查找表建立后，在后来的查：查找表建立后，在后来的查找过程中会改变查找表的内容极其长度。找过程中会改变查找表的内容极其长度。 假设要实现词汇统计功能。就是统计一篇文章中使假设要实现词汇统计功能。就是统计一篇文章中使用了多少词汇以及每个词汇的使用次数。这就是动态查用了多少词汇以及每个词汇的使用次数。这就是动态查找的例子。找的例子。 解决方法是先建立一个空的查找表，以后每读到一解决方法是先建立一个空

104、的查找表，以后每读到一个词就在查找表中查询一下，如果该词汇存在则将其使个词就在查找表中查询一下，如果该词汇存在则将其使用次数加一，否则将新词插入到查找表中并设使用次数用次数加一，否则将新词插入到查找表中并设使用次数为一次。显然，这个查找表是不断扩张的。为一次。显然，这个查找表是不断扩张的。 1) 1) 查找的方法查找的方法 显然，查找某个数据元素依赖于查找表中数据元素的组织方显然，查找某个数据元素依赖于查找表中数据元素的组织方式。按照数据元素的组织方式决定采用某种的查找方法；反过来式。按照数据元素的组织方式决定采用某种的查找方法；反过来，为了提高查找方法的效率，又要求数据元素采用某些特殊的组，

105、为了提高查找方法的效率，又要求数据元素采用某些特殊的组织方式。因此，在研究各种查找方法时，必须弄清各种查找方法织方式。因此，在研究各种查找方法时，必须弄清各种查找方法所适用的组织方式。所适用的组织方式。 2) 2) 查找算法的评价查找算法的评价 衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。而在查找算法中，基本运算是给定值与关键字值的比较，即算法的而在查找算法中，基本运算是给定值与关键字值的比较，即算法的主要时间是花费在主要时间是花费在“比较比较”上的，所以，用上的，所以，用平均查找长度平均查找长度作为评价查作为评价查找算法好坏的依

106、据。找算法好坏的依据。 对于含有对于含有n n个数据元素的查找表，查找成功的平均查找长度为个数据元素的查找表，查找成功的平均查找长度为ASL=其中：其中：P Pi i为查找第为查找第i i个数据元素的概率；个数据元素的概率；C Ci i为查找到第为查找到第i i个数个数据元素时，需进行的比较次数。据元素时，需进行的比较次数。 假设静态顺序查找表的存储结构为：假设静态顺序查找表的存储结构为： struct SSTable ElemType *data; /存储空间地址存储空间地址int length; /表的长度表的长度 ; 顺序查找表的元素存放在顺序查找表的元素存放在data0data0至至d

107、atalength-1datalength-1中。中。静态查找技术静态查找技术顺序查找是最普通也是最简单的查找技术。其基本顺序查找是最普通也是最简单的查找技术。其基本思想是：思想是：从第一个元素开始，逐个把元素的关键字值和给定值进行从第一个元素开始，逐个把元素的关键字值和给定值进行比较，若比较，若某个元素的关键字值和给定值相等，则查找成功；否则，某个元素的关键字值和给定值相等，则查找成功；否则，若直至第若直至第n n个记录都不相等，说明不存在满足条件的数据元素，查个记录都不相等，说明不存在满足条件的数据元素，查找失败。找失败。顺序查找算法顺序查找算法C+C+语言描述如下：语言描述如下：int

108、SqSearch(SSTable &L, KeyType key)int SqSearch(SSTable &L, KeyType key) int k = 0;int k = 0;while(kL.length&L.datak.x!=key) while(kL.length&L.datak.x!=key) k+; k+; if (kL.length) if (kL.length) return k+1; return k+1; / /返回数据元素位返回数据元素位置置else else return 0; return 0; 在在上述算法中为了避免上述算法中为了避免“出界出界”，需在循，需在循

109、环中作环中作kL.length 的判断，这使算法的执行的判断，这使算法的执行时间几乎增加一倍。为提高效率，对查找表的时间几乎增加一倍。为提高效率，对查找表的结构改动如下：结构改动如下： 适当设置数组长度，将元素存于适当设置数组长度，将元素存于data1data1至至datalength-1datalength-1中，在中，在0 0号单元预存待查找数号单元预存待查找数据据keykey作为监视哨。改写查找过程为从后往前作为监视哨。改写查找过程为从后往前查找。查找。因为循环查找过程至少会在因为循环查找过程至少会在0号单元停止，号单元停止，这样就不必在每一次循环中都判别是否数组出这样就不必在每一次循环

110、中都判别是否数组出界。界。优化算法优化算法改进的顺序查找算法改进的顺序查找算法C+语言描述如下：语言描述如下：intSqSearch(SSTable&L,KeyTypekey)L.data0.x=key;/监视哨监视哨intk=L.length;while(L.datak.x!=key)k=k-1;/从后往前找从后往前找returnk;/找不到时，找不到时，k为为0下下面面分分析析一一下下改改进进的的顺顺序序查查找找算算法法的的时时间间性性能能。对对于于改改进进的的顺顺序序查查找找而而言言，找找到到第第i个个元元素素的的比比较较次次数数Ci=n-i+1，所所以以在等概率查找的情况下，顺序表查找

111、的平均查找长度为：在等概率查找的情况下，顺序表查找的平均查找长度为： 从顺序查找算法中可以得出这样一个结论，平均每次查找需从顺序查找算法中可以得出这样一个结论，平均每次查找需要比较半个表的元素。当表长很长时，查找效率不高。需要改进要比较半个表的元素。当表长很长时，查找效率不高。需要改进 如果查找表中的所有数据元素按关键字递增（或递减）有序，如果查找表中的所有数据元素按关键字递增（或递减）有序，则可以采用一种高效率的查找方法则可以采用一种高效率的查找方法折半查找。折半查找。 折半查找的思路是：先确定待查元素所在区域，然后逐步缩折半查找的思路是：先确定待查元素所在区域，然后逐步缩小区域，直到查找成

112、功或失败为止。设：待查元素所在区域的下小区域，直到查找成功或失败为止。设：待查元素所在区域的下界为界为low,low,上界为上界为hig,hig,则中间位置则中间位置mid=mid=（low+higlow+hig）/2/2， 若中间位置元素关键字值等于给定值若中间位置元素关键字值等于给定值, ,则查找成功；则查找成功； 若中间位置元素关键字值大于给定关键值，则在若中间位置元素关键字值大于给定关键值，则在lowlowmid-1mid-1区域内进行折半查找；区域内进行折半查找； 若中间位置元素关键字值小于给定值，则在若中间位置元素关键字值小于给定值，则在mid+1mid+1highig区域区域内进

113、行折半查找；内进行折半查找；折半查找 设设置置查查找找区区间间初初值值，设设下下界界low low = = 0 0，设设上上界界high = length-1high = length-1。 若若lowhighlowhigh则则计计算算中中间间位位置置mid mid = = (low (low +high)/2+high)/2。 若若keydatamidkeydatamidkeydatamid，则则设设low low = = mid+1mid+1并并继继续续执执行步骤行步骤；若若key=datamidkey=datamid则则查查找找成成功功，返返回回目目标标元元素素位位置置mid+1mid+

114、1（位置从（位置从1 1计数）。计数）。 若当若当low=highlow=high时，时，keykey!=datamid=datamid则查找失则查找失败，返回败，返回0 0。折半查找算法的步骤描述如下折半查找算法的步骤描述如下：折半查找算法的折半查找算法的C+C+语言描述如下：语言描述如下：intBinSearch(SSTable&L,KeyTypekey)intlow,high,mid;low=0;high=L.length-1;/设置查找区间初值设置查找区间初值while(low=high)mid=(low+high)/2;if(key=L.datamid.x)returnmid+1;/

115、查查找成功找成功elseif(keyL.datamid.x)high=mid-1;/继继续续在在前前半半区区间间进进行行查找查找elselow=mid+1;/继续在后半区间进行查找继续在后半区间进行查找return0; /不存在待查元素不存在待查元素 对对给给定定有有序序数数列列 5，6，11，17，21，23，28，30，32，40进进行行半半查查找找算算法法，查查找找关关键键字字值值为为30的的数数据元素。则查找过程如下：据元素。则查找过程如下： 第第1次次： 5，6，11，17，21，23，28，30，32，40 low=0 mid=(0+9)/2 =4 high=9第第2次：次： 5，

116、6，11，17，21，23，28，30，32，40 low=5 mid=7 high=9 二叉排序树二叉排序树二叉排序树二叉排序树可能为一棵空的二叉树，若非空则可能为一棵空的二叉树，若非空则可能为一棵空的二叉树，若非空则可能为一棵空的二叉树，若非空则必必必必须须须须满足以下特征：满足以下特征：满足以下特征：满足以下特征： （1 1 1 1）根结点左子树中所有结）根结点左子树中所有结）根结点左子树中所有结）根结点左子树中所有结点的关键字小于根结点的关点的关键字小于根结点的关点的关键字小于根结点的关点的关键字小于根结点的关键字；键字；键字；键字； （2 2 2 2）根结点右子树中所有结）根结点右子

117、树中所有结）根结点右子树中所有结）根结点右子树中所有结点的关键字大于或等于根结点的关键字大于或等于根结点的关键字大于或等于根结点的关键字大于或等于根结点的关键字；点的关键字；点的关键字；点的关键字； （3 3 3 3）根结点的左右子树也都）根结点的左右子树也都）根结点的左右子树也都）根结点的左右子树也都是二叉排序树。是二叉排序树。是二叉排序树。是二叉排序树。 一棵二叉排序树二叉排序树的定义 建建立立了了二二叉叉排排序序树树之之后后，若若查查找找过过程程中中不不插插入入或或删删除元素除元素( (静态查找静态查找) )，则在二叉排序树中查找方法为：则在二叉排序树中查找方法为：1)1)将将给给定定数

118、数据据keykey与与根根结结点点关关键键字字x x进进行行比比较较，若若key=xkey=x则查找成功；则查找成功； 2)2)若若keyxkeyxkeyx，则则与与右右子子树树的的根根结结点点的的关关键键字字值值进进行行比较。比较。 重重复复上上述述步步骤骤，直直到到查查找找成成功功；或或者者一一直直比比较较到到叶叶子结点也找不到目标元素，则查找失败。子结点也找不到目标元素，则查找失败。/可定义二叉排序树结点如下：可定义二叉排序树结点如下：typedefstructBinNodeElemTypex;/关键字关键字structBinNode*left,*right;*BinNodePtr;/二

119、叉排序树查找算法（二叉排序树查找算法（静态查找静态查找）C+语言描述：语言描述：BinNode*search_btree(BinNodePtr&p,KeyTypekey)while(p!=NULL&p-x!=key)if(keyx)p=p-left;elsep=p-right;returnp;假设一组数据元素的关键字序列如下：假设一组数据元素的关键字序列如下：45，24，53，12，37，93，30，40，80分析查找元素分析查找元素40 进进行行动动态态查查找找时时，查查找找过过程程还还涉涉及及到到插插入入新新结点。其方法为：结点。其方法为：(1)(1)在在二二叉叉排排序序树树中中查查找找数

120、数据据key(key(按按前前一一页页的的方方法法) )，若若查查找找成成功功则则程程序序中中止止，若若查查找找失失败败则则转转入下面插入过程入下面插入过程(2)(2)(2)(2)以以数数据据keykey作作为为关关键键字字建建立立新新结结点点，假假定定查查找找过过程程最最后后到到达达某某叶叶子子结结点点，比比较较keykey与与此此叶叶子子结结点点的的关关键键字字，若若keykey小小于于后后者者则则将将新新结结点点插插入入为为叶叶子子结结点点的的左左孩孩子子，若若keykey大大于于后后者者则则新新结结点点插插入为叶子结点的右孩子。入为叶子结点的右孩子。 动态查找动态查找过程也是过程也是生

121、成生成二叉排序树的过程。假定二叉排序树的过程。假定由整数序列由整数序列10，6，19，22，8，2生成一棵生成一棵二叉排序树，可以采用逐个元素插入的方法实现。二叉排序树，可以采用逐个元素插入的方法实现。(1) 首先将首先将10作为根结点作为根结点(2) 然后插入然后插入6时，通过比较知时，通过比较知6x!=key ) / while(p!=NULL & p-x!=key ) / 循环查找过程循环查找过程循环查找过程循环查找过程 pre=p;pre=p;/ pre/ pre为结点为结点为结点为结点p p的父结点指针的父结点指针的父结点指针的父结点指针if( keyx )if( keyx )p=p

122、-left;p=p-left;elseelse p=p-right; p=p-right; if(p=NULL)/ 查找失败，插入新结点查找失败，插入新结点 /建立新结点建立新结点建立新结点建立新结点p=newBinNode;p=newBinNode;p-left=NULL;p-left=NULL;p-right=NULL;p-right=NULL;p-x=key;p-x=key;if(pre!=NULL)if(pre!=NULL)/新结点不是根，则作为叶子插入新结点不是根，则作为叶子插入 if(pre-xp-x)pre-left=p;if(pre-xp-x)pre-left=p;/插入为左孩

123、子插入为左孩子插入为左孩子插入为左孩子elsepre-right=p;elsepre-right=p;/插入为右孩子插入为右孩子插入为右孩子插入为右孩子 returnp;/返回找到的结点或插入的新结点的指返回找到的结点或插入的新结点的指 例例2.62.6字符统计程序字符统计程序该该程程序序可可统统计计由由用用户户输输入入的的一一个个字字符符串串中中各各种种字字符符的的使使用用次次数数。程程序序算算法法是是：首首先先建建立立空空的的二二叉叉排排序序树树，每每次次读读入入字字符符后后就就在在树树表表中中查查询询，若若找找到到则则将将该该字字符符使使用用次次数数加加一一；否否则则，将将读读入入的的字

124、字符符插插入入二二叉叉排排序序树树。为为记记录录字字符符使使用用次次数数，在在二二叉叉树树结结点点定定义义中中增增加加了了使使用用次次数数属属性性。读读完完整整个个字字符符串串后后用用中中序遍历法读出每个字符使用次数。序遍历法读出每个字符使用次数。利用二叉排序树统计字符出现次数程序利用二叉排序树统计字符出现次数程序2-6.2-6.CPPCPP排序排序码排序码：指数据元素中一个（或多个）数据项。：指数据元素中一个（或多个）数据项。 注意与查找中关键字的定义比较。注意与查找中关键字的定义比较。排序排序：假设：假设n n个数据元素分别为个数据元素分别为 R R1 1，R R2 2，R Rn n ，其

125、相应，其相应的排序码为的排序码为 K K1 1，K K2 2，, K, Kn n ，所谓排序就是将所有数据，所谓排序就是将所有数据元素按排序码非递减（或非递增）的次序排列起来，形成元素按排序码非递减（或非递增）的次序排列起来，形成新的有序序列的过程。新的有序序列的过程。排序表排序表：指所有待排序数据元素构成的线性表。：指所有待排序数据元素构成的线性表。 注意排序表的存储结构可以是顺序表，也可以是链表。注意排序表的存储结构可以是顺序表，也可以是链表。 关于排序的名词术语 如果待排序元素中，存在多个具有相同排序码的元素，如果待排序元素中，存在多个具有相同排序码的元素，若经过排序这些元素的相对次序保

126、持不变，则称这种若经过排序这些元素的相对次序保持不变，则称这种排序排序算法是稳定的算法是稳定的；若这些元素相对次序发生了改变，则称这；若这些元素相对次序发生了改变，则称这种种排序算法是不稳定的排序算法是不稳定的。 排序又可分为两大类；一类是内部排序，另一类是外排序又可分为两大类；一类是内部排序，另一类是外部排序。部排序。内部排序内部排序：指所有数据元素均放在内存中，整个排序过程：指所有数据元素均放在内存中，整个排序过程都是在内存中进行的排序都是在内存中进行的排序外部排序外部排序：指当待排序的元素非常多，排序时全部元素不：指当待排序的元素非常多，排序时全部元素不能同时存放在内存中，所以排序期间不

127、仅要使用内存，而能同时存放在内存中，所以排序期间不仅要使用内存，而且还要使用外部存贮器的排序。且还要使用外部存贮器的排序。简单插入排序第第1 1步步: :将排序表分成有序子表和无序子表将排序表分成有序子表和无序子表第第2 2步步: :从无序子表中取出元素，在有序表中寻找插入位置从无序子表中取出元素，在有序表中寻找插入位置第第3 3步步: :从插入位置到表尾的所有元素均后移一个位置从插入位置到表尾的所有元素均后移一个位置第第4 4步步: :将该元素插入到有序子表中将该元素插入到有序子表中第第5 5步步: :无序表空否，若不空，执行第无序表空否，若不空，执行第2 2步；若空结束排序步；若空结束排序

128、假设排序码序列是（假设排序码序列是（1818，1212，1010，1212，3030，1616） 初始状态初始状态 1812 10 12 30 16 第第1趟（趟（i=2） 12 1810 12 30 16 第第2趟（趟（i=3） 10 12 1812 30 16 第第3趟（趟（i=4） 10 12 12 1830 16 第第4趟（趟（i=5） 10 12 12 18 3016 第第5趟（趟（i=6） 10 12 12 16 18 30简单插入排序算法实现简单插入排序算法实现直接插入排序算法直接插入排序算法C+C+语言描述：语言描述：voidInsertSort(intv,intn)inti,

129、j,temp;for(i=1;i0&temp1N1，则执行第，则执行第1 1步，否则结束排序步，否则结束排序假设排序码序列是（假设排序码序列是（2 2，7 7，2 2，2 2，3 3，1 1） 初始状态初始状态 2 7 2 2 3 1 2 7 2 2 3 1 第第1 1趟（趟（i=1i=1） 1 1 7 2 2 3 2 7 2 2 3 2 第第2 2趟（趟（i=2i=2） 1 21 2 7 2 3 2 7 2 3 2 第第3 3趟（趟（i=3i=3） 1 2 21 2 2 7 3 2 7 3 2 第第4 4趟（趟（i=4i=4） 1 2 2 21 2 2 2 3 7 3 7 第第5 5趟（趟（

130、i=5i=5） 1 2 2 2 31 2 2 2 3 7 7 简单选择排序算法实现简单选择排序算法实现简单选择排序算法简单选择排序算法C+C+语言描述：语言描述： voidSelectSort(intv,intn)inti,j,k,temp;for(i=0;in-1;i+)intk=i; /k存放最小记录位置存放最小记录位置for(j=i+1;jn;j+)/找最小记录位置找最小记录位置if(vjvk)k=j;if(k!=i)/交换第交换第i和第和第k个位置记录个位置记录temp=vi;vi=vk;vk=temp; 冒泡排序的基本思路是：第一趟排序对第一趟排序对全部记录全部记录R1，R2，Rn自

131、左向右顺次两两自左向右顺次两两比较，若比较，若Rk大于大于Rk+1则交换则交换Rk和和Rk+1( k=1, 2, n-1)，第一趟排序完成后，第一趟排序完成后Rn成为序列成为序列中最大记录。第二趟排序对序列前中最大记录。第二趟排序对序列前n-1个记个记录采用同样的比较和交换方法，第二趟排序录采用同样的比较和交换方法，第二趟排序完成后完成后Rn-1成为序列中仅比成为序列中仅比Rn小的次大的记小的次大的记录。第三趟排序对序列前录。第三趟排序对序列前n-2个记录采用同个记录采用同样处理方法。如此做下去，最多做样处理方法。如此做下去，最多做n-1趟排趟排序，整个序列就排序完成。序，整个序列就排序完成。

132、冒泡排序应用冒泡排序的过程。应用冒泡排序的过程。 初始状态：初始状态：35 22 16 19 22 第第1趟趟 ： 22 16 19 22 35 第第2趟趟 ： 16 19 22 22 35 第第3趟趟 ： 16 19 22 22 35 第第4趟趟 ： 16 19 22 22 35 冒泡排序算法冒泡排序算法C+C+语言描述语言描述：void BubleSort(int v , int n) int temp;for (int i=1; in; i+) for (int i=1; in; i+) for (int j=0; jn-i; j+) /for (int j=0; jvj+1 ) /交换

133、两个相邻元素交换两个相邻元素 temp=v j ; vj=vj+1; vj+1=temp; / /第第第第i i大的元素筛选结束大的元素筛选结束大的元素筛选结束大的元素筛选结束 改进后的冒泡排序 初始状态初始状态65 97 76 13 27 49 5865 97 76 13 27 49 58 第第1 1趟（趟（j=1j=16 6） 65 76 13 27 49 5865 76 13 27 49 589797 第第2 2趟（趟（j=1j=15 5） 65 13 27 49 5865 13 27 49 5876 9776 97 第第3 3趟（趟（j=1j=14 4） 13 27 49 5813 2

134、7 49 5865 76 9765 76 97 第第4 4趟（趟（j=1j=13 3） 13 27 4913 27 4958 65 76 9758 65 76 97 第第5 5趟（趟（j=1j=12 2） 13 2713 2749 58 65 76 9749 58 65 76 97 第第6 6趟（趟（j=1j=1） 131327 49 58 65 76 9727 49 58 65 76 97改进的冒泡排序算法实现改进的冒泡排序算法实现 templatetemplate void seqlistbubblesort_M() void seqlistbubblesort_M() int i,j,f

135、lag int i,j,flag datatype temp; datatype temp; insert_data(1,temp); insert_data(1,temp); i=1; i=1; do flag=0; / do flag=0; /标志位置标志位置0 0 for(j=1;j=last-i;j+)for(j=1;jdataj+1) / if(datajdataj+1) /在当前表中进行交换在当前表中进行交换 temp=dataj;temp=dataj; dataj=dataj+1; dataj=dataj+1; dataj+1=temp; dataj+1=temp; flag=1

136、; / flag=1; /有交换，标志位置有交换，标志位置1 1 ; ; i+;i+; while(ilast&flag); / while(ilast&flag); /是否已经排顺是否已经排顺 delete_data(1); /delete_data(1); /排序完毕，删除表头元素排序完毕，删除表头元素 ; ;快速排序快速排序的基本思想是：在待排序的快速排序的基本思想是：在待排序的n n个元素中任取一个元素个元素中任取一个元素R R，以，以该元素排序码该元素排序码k k为准，将所有剩下的为准，将所有剩下的n-1n-1个元素分为两个子序列：个元素分为两个子序列： 第一个子序列中每个元素的排序

137、码均小于或等于第一个子序列中每个元素的排序码均小于或等于k k；第二个子序；第二个子序列中每个元素的排序码均大于或等于列中每个元素的排序码均大于或等于k k。然后将。然后将k k所对应的元素放在所对应的元素放在两个子序列之间。完成第一趟排序，使得待排序序列成为：两个子序列之间。完成第一趟排序，使得待排序序列成为： 1 R R 2 分别对子序列分别对子序列1 1和子序列和子序列2 2重复上述划分，直到每个子序列中只重复上述划分，直到每个子序列中只有一个元素时为止。有一个元素时为止。快速排序示意图 在在在在22, 35, 27, 16, 45, 19, 22, 35, 27, 16, 45, 19

138、, 2222 上的划分算法（即一趟快上的划分算法（即一趟快上的划分算法（即一趟快上的划分算法（即一趟快速排序）速排序）速排序）速排序）假设元素序列为（假设元素序列为（4949，3838，6060，9090，7070，1515，3030，4949）第一趟快速排序划分过程如下第一趟快速排序划分过程如下初始状态：初始状态：49493838606090907070151530304949（1 1） 30 38 60 90 70 15 30 38 60 90 70 15 j j 49 49（2 2） 30 38 30 38 i i 90 70 15 60 49 90 70 15 60 49（3 3） 3

139、0 38 15 90 70 30 38 15 90 70 j j 60 49 60 49（4 4） 30 38 15 30 38 15 i i 70 90 60 49 70 90 60 49（5 5） 30 38 15 30 38 15 ijij 70 90 60 49 70 90 60 49最后状态：最后状态：30 38 15 30 38 15 4949 70 90 60 49 70 90 60 49 下下列列快快速速排排序序中中划划分分序序列列的的算算法法对对vlow与与vhigh之之间间的的元元素素进进行行划划分分，利利用用了了序序列列第第一一个个记记录录作作为为基基准准，最最终终将将l

140、ow与与high区区间间中中的的序序列列划划分分为为左左右右两两个个子子序序列列，将将基基准准对对象象放放到到适适当当位位置置并并返返回回其其位位置置的的下下标。标。int Partition( int low, int high ) int pivot = vlow; /基准对象pivot位置为low while(lowhigh) while(lowpivot) high-; /右边界下移 vlow=vhigh; /小于pivot的放到左侧 while(lowhigh & vlow=pivot) low+; /左边界上移 vhigh=vlow;/大于pivot的放到右侧 vlow= pivo

141、t;/此时low等于high return low; 前面的序列经过划分后，基准元素前面的序列经过划分后，基准元素2222的位置已经确的位置已经确定不变了。只需将序列定不变了。只需将序列1919，1616和和 27,45,35, 27,45,35,2222 分别排序即可。进一步的工作是将两个子序列分别分别排序即可。进一步的工作是将两个子序列分别划分，可分别取划分，可分别取1919和和2727为基准元素。为基准元素。 22，35，27，16，45，19，22 19，16 22 27，45，35，22 16 19 22 22 27 35，45 16 19 22 22 27 35 45 快速排序快速

142、排序执行过程执行过程快速排序每趟变化如下：初始状态：初始状态： 49 493838606090907070151530304949第一趟：第一趟：38 15 30 38 15 30 4949 60 90 70 49 60 90 70 49第二趟：第二趟： 15 30 15 30 3838 4949 49 49 6060 90 70 90 70第三趟：第三趟： 1515 30 30 3838 4949 4949 6060 70 70 9090快速排序的递归算法实现templatetemplatevoid seqlistquicksort(int low,int hig)void seqlistquicksort(int low,int hig) int i; int i; if(lowhig) if(lowhig) i=qpass(low,hig); / i=qpass(low,hig); /确定中间位置确定中间位置 quicksort(low,i-1); /quicksort(low,i-1); /在当前表的前半部分快速排序在当前表的前半部分快速排序 quicksort(i+1,hig); /quicksort(i+1,hig); /在当前表的后半部分快速排序在当前表的后半部分快速排序 ; ;