《软件开发技术基础 第2章 数据结构及其应用.ppt》由会员分享，可在线阅读，更多相关《软件开发技术基础 第2章 数据结构及其应用.ppt（170页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构概念及顺序表西安交通大学计教中心西安交通大学计教中心2.1 2.1 数据结构基本概念数据结构基本概念1数据（数据（data）数据是指能够输入到计算机中，并被计算机识数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合别和处理的符号的集合。2数据元素（数据元素（dataelement）数数据据元元素素是是组组成成数数据据的的基基本本单单位位。数数据据元元素素是是一一个个数数据据整整体体中中相相对对独独立立的的单单位位。但但它它还还可可以以分分割割成成若若干干个个具具有有不不同同属属性性的的项项（字字段段），故故不不是是组成数据的最小单位组成数据的最小单位数据结构（数据结构（dat
2、astructure）是是指指相相互互之之间间存存在在一一种种或或多多种种特特定定关关系系的的数数据据元元素素所所组组成成的的集集合合。数数据据结结构构包包含含三三个个方方面面的的内内容容，即即数数据据的的逻逻辑辑结结构构，数数据据的的存存贮贮结结构和对数据所施加的运算构和对数据所施加的运算。这三个方面的关系为这三个方面的关系为：数数据据的的逻逻辑辑结结构构独独立立于于计计算算机机，是是数数据据本本身身所所固固有的有的存存贮贮结结构构是是逻逻辑辑结结构构在在计计算算机机存存贮贮器器中中的的映映像像，必须依赖于计算机。必须依赖于计算机。运运算算是是指指所所施施加加的的一一组组操操作作总总称称。运
3、运算算的的定定义义直直接接依依赖赖于于逻逻辑辑结结构构，但但运运算算的的实实现现必必依依赖赖于于存存贮贮结构。结构。数据结构基本类型数据结构基本类型线性结构线性结构 通迅录、成绩单、花名册通迅录、成绩单、花名册树形结构树形结构 电子字典、家谱、目录电子字典、家谱、目录图状结构图状结构 交通线路交通线路、通信网络通信网络数据结构中常用的存贮结构数据结构中常用的存贮结构(1)顺序存贮顺序存贮所所有有元元素素存存放放在在一一片片连连续续的的存存贮贮单单元元中中，逻逻辑辑上上相邻的元素存放到计算机内存仍然相邻。相邻的元素存放到计算机内存仍然相邻。(2)链式存贮链式存贮所所有有元元素素存存放放在在可可以
4、以不不连连续续的的存存贮贮单单元元中中，元元素素之之间间的的关关系系通通过过地地址址确确定定，逻逻辑辑上上相相邻邻的的元元素素存存放到计算机内存后不一定是相邻的。放到计算机内存后不一定是相邻的。(3)索引存贮（略）索引存贮（略）(4)散列存贮（略）散列存贮（略）算法（算法（algorithm）通通俗俗地地讲讲，算算法法就就是是一一种种解解题题的的方方法法。更更严严格格地地说说，算算法法是是由由若若干干条条指指令令组组成成的的有有穷穷序序列列，它它必必须须满满足足下下述述条件（也称为算法的五大特性）：条件（也称为算法的五大特性）：（1）输输入入：具具有有0个个或或多多个个输输入入的的外外界界量量
5、（算算法法开开始始前前的的初始量）初始量）（2）输输出出：至至少少产产生生一一个个输输出出，它它们们是是算算法法执执行行完完后后的的结果。结果。（3）有穷性：）有穷性：每条指令的执行次数必须是有限的。每条指令的执行次数必须是有限的。（4）确定性：）确定性：每条指令的含义都必须明确，无二义性。每条指令的含义都必须明确，无二义性。（5）可行性：）可行性：每条指令的执行时间都是有限的。每条指令的执行时间都是有限的。1时间复杂度时间复杂度一个算法花费的时间与算法中语句的执行次一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费数成正比，哪个算法中语句执行次数多，它花费时间就
6、多。时间就多。数据结构中数据元素个数数据结构中数据元素个数n称为问题的规模，称为问题的规模，当当n不断变化时，语句的执行次数也会变化。一不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数个算法中的时间复杂度一般用语句执行次数的数量级来衡量。量级来衡量。例如：例如：for(i=1;i=n;i+)for(j=1;j0)L-maxsize=size;L-length=0;L-data=newElemTypesize;/申请空间申请空间elsecout线性表初始化长度错误线性表初始化长度错误;（2 2）在表中第）在表中第 i i 个位置插入新元素个位置插入新元素x x 算
7、法实现的主要步骤是：算法实现的主要步骤是：判断插入位置的合理性以及表是否已判断插入位置的合理性以及表是否已满。满。从最后一个元素开始依次向前，将每从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第个元素向后移动一个位置，直到第i i个元个元素为止。素为止。向空出的向空出的第第i i个位置存入新元素个位置存入新元素x x。最后还要将线性表长度加一。最后还要将线性表长度加一。voidInsert(SeqList*L,inti,ElemTypex)if(iL-length+1|L-length=L-maxsize)coutlength-1;j=i-1;j-)L-dataj+1=L-dat
8、aj;/元素依次后移元素依次后移 L-datai-1=x;/向第向第i个位置存入新元素个位置存入新元素xL-length+;/表长度加一表长度加一（3）在表中删除第i个元素算法实现的主要步骤是：算法实现的主要步骤是：判断删除位置的合理性。判断删除位置的合理性。从第从第i+1i+1个元素开始，依次向后个元素开始，依次向后直到最后一个元素为止，将每个元直到最后一个元素为止，将每个元素向前移动一个位置。这时第素向前移动一个位置。这时第i i个元个元素已经被覆盖删除。素已经被覆盖删除。最后还要将线性表长度减一。最后还要将线性表长度减一。voidDelete(SeqList*L,inti)if(iL-l
9、ength)cout表中没有第表中没有第i个元素个元素;elsefor(intj=i;jlength-1;j+)L-dataj-1=L-dataj;L-length-;（4）在表中查找某个元素下下面面是是根根据据数数据据元元素素本本身身的的值值进进行行查查询询的的算算法法，x为为需需要要查查找找的的元元素素，算算法法返返回回元元素素的的实际位置。实际位置。intFind(SeqList*L,ElemTypex)for(inti=0;ilength;i+)/查找成功，返回元素位置查找成功，返回元素位置if(L-datai=x)returni+1;return0;/查找失败，返回查找失败，返回0顺
10、序表应用举例顺序表应用举例【例例2-1】利用顺序表表示多项式，实现两个一利用顺序表表示多项式，实现两个一元多项式元多项式L1(x)和和L2(x)相加，将结果存于多项相加，将结果存于多项式式L3(x)中。并计算当中。并计算当L1(x)=3.5+4x2+2.5x4，L2(x)=1.5x+2.6x2+1.6x3时，时，L3(x)的结果是什的结果是什么。么。一一元元多多项项式式P(x)可可以以表表示示为为(a0,0),(a1,1),(an,n)。例例如如线线性性表表(6,1),(-5,4),(8,10)表表示多项式示多项式:P(x)=6x-5x4+8x10。用用顺顺序序表表L1和和L2存存放放需需要要
11、相相加加的的两两个个多多项项式式L1(x)和和L2(x)，用用顺顺序序表表L3来来存存放放结结果果。多多项项式式相相加加算算法可按照下列步骤实现：法可按照下列步骤实现：设设定定两两个个位位置置变变量量i和和j指指向向顺顺序序表表L1和和L2的的第第一一个个元元素素，设设定定位位置置变变量量k表表示示L3的的插插入入位位置置，插插入入位置从位置从1开始。本例中开始。本例中i、j和和k初值均为初值均为1。比比较较i和和j两两个个位位置置数数据据元元素素的的指指数数项项，如如果果L1中中第第i项项指指数数较较小小，则则将将此此项项数数据据元元素素复复制制到到L3的的位位置置k中中，并并将将位位置置变
12、变量量i和和k后后移移；如如果果L2中中第第j项项指指数数较较小小，则则同同样样是是将将此此项项复复制制到到L3中中，并并将将位位置置变变量量j和和k后后移移；如如果果两两项项指指数数项项相相等等，则则合合并并同同类类项项后后再再将将结结果果复复制制到到L3中中，并并将将位位置置变变量量i、j和和k同时后移同时后移。当当L1或或L2中中的的一一个个顺顺序序表表已已经经处处理理完完毕毕，则则将将另另一个顺序表的一个顺序表的剩余部分剩余部分复制到复制到L3中。中。参照程序参照程序例例2-1线性链表西安交通大学计教中心西安交通大学计教中心采用链式存储结构的线性表有单链表、双采用链式存储结构的线性表有
13、单链表、双向链表、单循环链表以及双向循环链表等多种向链表、单循环链表以及双向循环链表等多种形式。形式。单链表用一组地址任意的存储单元存放线单链表用一组地址任意的存储单元存放线单链表用一组地址任意的存储单元存放线单链表用一组地址任意的存储单元存放线性表中的数据元素。由于逻辑上相邻的元素其性表中的数据元素。由于逻辑上相邻的元素其性表中的数据元素。由于逻辑上相邻的元素其性表中的数据元素。由于逻辑上相邻的元素其物理位置不一定相邻，为了建立元素间的逻辑物理位置不一定相邻，为了建立元素间的逻辑物理位置不一定相邻，为了建立元素间的逻辑物理位置不一定相邻，为了建立元素间的逻辑关系，需要在线性表的每个元素中附加
14、其后继关系，需要在线性表的每个元素中附加其后继关系，需要在线性表的每个元素中附加其后继关系，需要在线性表的每个元素中附加其后继元素的地址信息。元素的地址信息。元素的地址信息。元素的地址信息。这种地址信息称为指针。附加了其他元素这种地址信息称为指针。附加了其他元素这种地址信息称为指针。附加了其他元素这种地址信息称为指针。附加了其他元素指针的数据元素称为结点。指针的数据元素称为结点。指针的数据元素称为结点。指针的数据元素称为结点。单链表的概念单链表的概念结点定义结点定义结结点点包包含含数数据据域域和和指指针针域域,结结点点结结构构可可描描述为述为:其其中中data域域用用来来存存放放结结点点本本身
15、身信信息息，类类型型由由具具体体问问题题而而定定，本本节节也也将将其其设设定定为为ElemType类类型型，表表示示某某一一种种具具体体的的已已知类型，知类型，next域存放下一个元素地址。域存放下一个元素地址。带头结点单链表的逻辑结构带头结点单链表的逻辑结构 为了能顺次访问每个结点，需要保存单链为了能顺次访问每个结点，需要保存单链表第一个结点的存储地址。这个地址称为线性表第一个结点的存储地址。这个地址称为线性表的头指针，本节用表的头指针，本节用head表示。表示。为了操作上的方便，可以在单链表的头部为了操作上的方便，可以在单链表的头部增加一个特殊的头结点。头结点的类型与其他增加一个特殊的头结
16、点。头结点的类型与其他结点一样，只是头结点的数据域为空。结点一样，只是头结点的数据域为空。增加头结点避免了在删除或添加第一个位增加头结点避免了在删除或添加第一个位置的元素时进行的特殊程序处理。置的元素时进行的特殊程序处理。heada1a2an带头结点的单链表带头结点的单链表带头结点单链表的存储结构带头结点单链表的存储结构head38数据域数据域数据域数据域38229486a286 94 a3NULLa122存储地址存储地址单链表存储结构示意图单链表存储结构示意图结点的结点的c+描述描述typedefstructLNodeElemTypedata;/数据域，数据域，ElemType代代/表某种数
17、据类型表某种数据类型structLNode*next;/指针域指针域*LinkList;这个定义是自引用类型的。换言之，每个这个定义是自引用类型的。换言之，每个结点都包含另一个同类型结点的地址。结点都包含另一个同类型结点的地址。指针操作指针操作假如假如p p为指向某一结点的指针，则该结点的为指向某一结点的指针，则该结点的数据域用数据域用p-datap-data表示，该结点的指针域用表示，该结点的指针域用 p-nextp-next表示。它们都是变量，可以被赋值，表示。它们都是变量，可以被赋值，也可向其他变量赋值。也可向其他变量赋值。例如例如:假定假定datadata为为整型变量整型变量,则则p-
18、data=5;p-next=NULL;将将结点变为结点变为:aiai-1ai-1aiai-1ai+1qqpp如果如果p为指向结点为指向结点ai的指针，那么的指针，那么p-next就是就是指向指向ai后继后继ai+1的指针；若的指针；若q为另一指针变量为另一指针变量q=p指针指针p指向指针指向指针q所指的结点所指的结点q=p-next指针指针p指向指针指向指针q所指结点的后继所指结点的后继p=p-next指针指针p向后移动一个结点向后移动一个结点pai-1aiai+1p常用算法常用算法（1 1）求单链表的长度）求单链表的长度单单链链表表长长度度不不定定，要要确确定定链链表表长长度度需需要要走走遍
19、遍表表中中所所有有结点才能算出。结点才能算出。intLength()LNode*p=head-next;/p指向第一个元素所在结点指向第一个元素所在结点intlen=0;while(p!=NULL)/逐个检测逐个检测p结点存在与否结点存在与否 len+;p=p-next;/指针后移指针后移returnlen;为了保持头指针不变，使用了指针为了保持头指针不变，使用了指针p在链表中移动。在链表中移动。（2）从单链表中删除第）从单链表中删除第i个结点个结点为了从单链表中删除第为了从单链表中删除第i个结点，需进行如下操作：个结点，需进行如下操作：若第若第i个结点存在则找到第个结点存在则找到第i和第和第
20、i-1个个结结点的指针点的指针p和和q通通过过语语句句q-next=p-next将将第第i-1个个结结点点的的指指针针域域赋赋值值为第为第i+1个个结结点的指针，将第点的指针，将第i个结点从链表中断开。个结点从链表中断开。释放第释放第i个结点所占空间以便于重用。个结点所占空间以便于重用。qpai-1aiai+1q-next=p-next;q-next=p-next;deletep;deletep;voidDelete(LinkList&head，inti)if(i1)cout”不存在第不存在第”i”个元素个元素”;elseLNode*p=head;/p指向头结点指向头结点(第第0个结点个结点)
21、LNode*q;/q和和p最终分别指向第最终分别指向第i-1和第和第i个结点个结点intk=0;while(p!=NULL&knext;k+;if(p=NULL)coutinext=p-next;/从链表中删除该结点从链表中删除该结点deletep;/释放结点释放结点p（3）在第）在第i个位置插入新结点个位置插入新结点x在链表的第在链表的第i个位置插入一个新结点，需进行如下操作：个位置插入一个新结点，需进行如下操作：首先找到第首先找到第i-1个结点的指针个结点的指针p建立新结点建立新结点s并通过语句并通过语句s-next=p-next将其指针指将其指针指向第向第i个结点个结点通过语句通过语句p
22、-next=s将第将第i-1个结点的指针指向新结点个结点的指针指向新结点s-data=x;s-data=x;s-next=p-next;s-next=p-next;p-next=s;p-next=s;ai-1aipxs12voidInsert(LinkList&head,inti,ElemTypex)if(i1)cout不存在第不存在第i个位置个位置;elseLNode*p=head;/p最终将指向第最终将指向第i-1个结点个结点intk=0;/p目前指向第目前指向第0个结点个结点(头结点头结点)while(p!=NULL&knext;k+;if(p=NULL)coutidata=x;s-ne
23、xt=p-next;/定义结点定义结点s的指针域的指针域p-next=s;/修改结点修改结点p的指针域的指针域（4）在单链表中查找数据值为）在单链表中查找数据值为x的结点的结点可可以以按按照照数数据据元元素素本本身身的的值值进进行行查查找找，也也可可以以按按照照数数据据元元素素的的某某个个属属性性进进行行查查找找。这这里里仅仅给给出出按按照照数数据据元素本身的值进行查找的算法。元素本身的值进行查找的算法。LNode*Find(LinkList&head,ElemTypex)LNode*p=head-next;/p指向第一个元素所在结点指向第一个元素所在结点while(p!=NULL&p-dat
24、a!=x)p=p-next;returnp;其他形式的链表其他形式的链表（1 1）单循环链表）单循环链表通通过过把把单单链链表表最最后后一一个个结结点点的的指指针针改改为为指指向向第第一一个个结结点点，就就可可以以把把一一个个单单链链表表改改造造成成单单循循环环链链表表。因因为为单单链链表表最最后后一一个个结结点点的的指指针针总总是是空空值值，所所以以这这样样的修改总是可行的。的修改总是可行的。head.a1a2anhead2 2）双向链表）双向链表如果每个链表结点既有指向下一个元素的指针，又如果每个链表结点既有指向下一个元素的指针，又有指向前一个元素的指针，那么这种有指向前一个元素的指针，那
25、么这种链表就是链表就是双双向链表，双向链表结点的定义只需在单链表结点向链表，双向链表结点的定义只需在单链表结点定义的基础上增加一个前向指针即可定义的基础上增加一个前向指针即可。head.ana2a1链表应用举例链表应用举例 约瑟夫环问题可以解释为：将整数约瑟夫环问题可以解释为：将整数1 1至至n n围围成一个圆圈，假定从某个整数开始顺时针成一个圆圈，假定从某个整数开始顺时针从从1 1数到数到m m时，令该位置整数出列；然后再时，令该位置整数出列；然后再从下一数开始，顺时针从从下一数开始，顺时针从1 1数到第数到第m m时再令时再令其出列，如此下去，直到圆圈中无整数为其出列，如此下去，直到圆圈中
26、无整数为止。请写出所有数字出列的顺序。止。请写出所有数字出列的顺序。【例2-2】栈与队列西安交通大学计教中心西安交通大学计教中心栈的定义栈的定义栈栈是是限限制制在在表表的的一一端端进进行行插插入入和和删删除除操操作作的的线线性性表表。允允许许进进行行插插入入和和删删除除操操作作的的一一端端称为栈顶，另一端称为栈底。称为栈顶，另一端称为栈底。如如果果多多个个元元素素依依次次进进栈栈，则则后后进进栈栈的的元元素素必必然然先先出出栈栈，所所以以堆堆栈栈又又称称为为后后进进先先出出（LIFOLIFO）表表。堆堆栈栈设设有有一一个个栈栈顶指针标志栈顶位置。顶指针标志栈顶位置。栈示意图a a1 1a a3
27、 3a a2 2进栈进栈出栈出栈top堆栈的主要操作有：堆栈的主要操作有：创建空栈。创建空栈。进栈进栈(push)push)操作操作:在栈顶插入元素。在栈顶插入元素。出栈出栈(pop)pop)操作操作:在栈顶删除元素。在栈顶删除元素。读栈顶元素读栈顶元素:只是读出栈顶元素，并不只是读出栈顶元素，并不改变栈内元素。改变栈内元素。顺序栈顺序栈同顺序表一样，可利用一维数组来实现。定义如下：同顺序表一样，可利用一维数组来实现。定义如下：structSqStackElemType*data;/存储元素的数组存储元素的数组inttop;/栈顶指针，存储栈顶元素下标栈顶指针，存储栈顶元素下标intstack
28、size;/最大可用空间数量最大可用空间数量;SeqStacks;/定义一个堆栈定义一个堆栈s一般将数组的一般将数组的0下标单元作为栈底，将栈顶元素下标单元作为栈底，将栈顶元素的下标存储在栈顶指针的下标存储在栈顶指针top中，它随着元素进栈出栈中，它随着元素进栈出栈而变化。而变化。top为为-1表示空栈，表示空栈，top等于等于stacksize-1则表则表示栈满。示栈满。（1 1）顺序栈初始化）顺序栈初始化堆堆栈栈的的初初始始化化主主要要是是为为存存储储元元素素的的数数组组申申请请空空间间，下面的初始化函数申请了长度为下面的初始化函数申请了长度为sizesize的空间。的空间。voidIni
29、tStack(SqStack*s,intsize)if(size0)s-stacksize=size;s-top=-1;s-data=newElemTypesize;/申请空间申请空间elsecouttopstacksize-1)s-top+;s-datatop=x;elsecouttop-1)e=s-datas-top;s-top-;elsecouttop-1)e=s-datas-top;elsecoutdata=x;p-next=top;top=p;（2 2）出栈操作出栈操作若栈不空，则删除栈顶元素，用若栈不空，则删除栈顶元素，用e返回其值。返回其值。voidPop(LinkStack&t
30、op,ElemType&e);SNode*p;if(top!=NULL)e=top-data;p=top;top=top-next;deletep;举例举例:后缀表达式求值后缀表达式求值假定表达式是由加减乘除和数字构成。最简假定表达式是由加减乘除和数字构成。最简单的表达式为下列形式：单的表达式为下列形式：(操作数操作数S S1 1)()(运算符运算符OPOP)()(操作数操作数S S2 2)三种不同的表示方法：三种不同的表示方法：前缀表示法前缀表示法 OPOPS S1 1S S2 2 例如例如6+36+3写成写成+63+63中缀表示法中缀表示法 OPSOPS1 1S S2 2 例如例如6+36
31、+3写成写成63+63+后缀表示法后缀表示法 S S1 1S S2 2OPOP 例如例如6+36+3写成写成63+63+同时，任何表达式都可分解为下列形式：同时，任何表达式都可分解为下列形式：(子表达式子表达式E E1 1)()(运算符运算符OPOP)()(子表达式子表达式E E2 2)它的后缀表示法应写成：它的后缀表示法应写成：(E E1 1的后缀表示的后缀表示)()(E E2 2的后缀表示的后缀表示)OPOP只要不断对子表达式进一步分解，总能将子表达只要不断对子表达式进一步分解，总能将子表达式分解为最简单形式，因此任何四则运算表达式式分解为最简单形式，因此任何四则运算表达式都可写成前缀式或
32、后缀式。都可写成前缀式或后缀式。例如：例如：2*2*(6+3)(6+3)2 2(6+3)(6+3)*2 263+63+*。(注意：转化为后缀式后括号去掉注意：转化为后缀式后括号去掉)中缀式虽然容易理解，但在求值的时候利中缀式虽然容易理解，但在求值的时候利用前缀式或后缀式更为简单。用后缀式求用前缀式或后缀式更为简单。用后缀式求值的算法为：值的算法为：首先设立一个堆栈，依此读取后缀式首先设立一个堆栈，依此读取后缀式中的字符，若字符是数字，则进栈并继续中的字符，若字符是数字，则进栈并继续读取，若字符是运算符（记为读取，若字符是运算符（记为OPOP），），则连则连续出栈两次得到数字续出栈两次得到数字S
33、 S1 1和和S S2 2，计算表达式计算表达式S 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入栈。这时入栈。
34、这时1818就是最终结果。就是最终结果。【例例2-32-3】假定表达式是由不超假定表达式是由不超过过四个实四个实数进行四则数进行四则运算构成的算式，运算构成的算式，要编写一个要编写一个程序来求解程序来求解该该算式的算式的结结果果。中缀表达式变成等价的后缀表达式中缀表达式变成等价的后缀表达式将将中中缀缀表表达达式式变变成成等等价价的的后后缀缀表表达达式式，表表达达式式中中操操作作数数次次序序不不变变，运运算算符符次次序序发发生生变变化化，同同时时去去掉掉了了圆圆括括号号。转转换换规规则则是是：设设设设立立立立一一一一个个个个栈栈栈栈，存存存存放放放放运运运运算算算算符符符符，首首首首先先先先栈栈
35、栈栈为为为为空空空空，编编编编译译译译程程程程序序序序从从从从左左左左到到到到右右右右扫扫扫扫描描描描中中中中缀缀缀缀表表表表达达达达式式式式，若若若若遇遇遇遇到到到到操操操操作作作作数数数数，直直直直接接接接输输输输出出出出，并并并并输输输输出出出出一一一一个个个个空空空空格格格格作作作作为为为为两两两两个个个个操操操操作作作作数数数数的的的的分分分分隔隔隔隔符符符符；若若若若遇遇遇遇到到到到运运运运算算算算符符符符，则则则则必必必必须须须须与与与与栈栈栈栈顶顶顶顶比比比比较较较较，运运运运算算算算符符符符级级级级别别别别比比比比栈栈栈栈顶顶顶顶级级级级别别别别高高高高则则则则进进进进栈栈栈
36、栈，否否否否则则则则退退退退出出出出栈栈栈栈顶顶顶顶元元元元素素素素并并并并输输输输出出出出，然然然然后后后后输输输输出出出出一一一一个个个个空空空空格格格格作作作作分分分分隔隔隔隔符符符符；若若若若遇遇遇遇到到到到左左左左括括括括号号号号，进进进进栈栈栈栈；若若若若遇遇遇遇到到到到右右右右括括括括号号号号，则则则则一一一一直直直直退退退退栈栈栈栈输输输输出出出出，直直直直到到到到退退退退到到到到左左左左括括括括号号号号止止止止。当当当当栈变成空时，输出的结果即为后缀表达式。栈变成空时，输出的结果即为后缀表达式。栈变成空时，输出的结果即为后缀表达式。栈变成空时，输出的结果即为后缀表达式。步骤步
37、骤栈中元素栈中元素输出结果输出结果说明说明1(（进栈（进栈2(1输出输出13(+1+进栈进栈4(+12输出输出2512+退栈输出，退栈退栈输出，退栈到（止到（止6*12+*进栈进栈7*(12+（进栈（进栈8*(12+（进栈（进栈9*(12+8输出输出810*(-12+8-进栈进栈将中缀表达式将中缀表达式(1+2)*(8-2)/(7-4)(1+2)*(8-2)/(7-4)变成等价的后缀表达变成等价的后缀表达式。式。现在用栈来实现该运算，栈的变化及输出结果如现在用栈来实现该运算，栈的变化及输出结果如下：下：11*(-12+82输出输出212*(12+82-退栈输出，退退栈输出，退栈到（止栈到（止1
38、3*(/12+82-/进栈进栈14*(/(12+82-（进栈进栈15*(/(12+82-7输出输出716*(/(-12+82-7-进栈进栈17*(/(-12+82-74输出输出418*(/12+82-74-退栈输出，退退栈输出，退栈到（止栈到（止19*12+82-74-/退栈输出，退退栈输出，退栈到（止栈到（止2012+82-74-/*退栈并输出退栈并输出队列定义队列定义队列是只能在表的一端进行插入、在另一队列是只能在表的一端进行插入、在另一端进行删除操作的线性表。允许删除元素的一端进行删除操作的线性表。允许删除元素的一端称为队头，允许插入元素的一端称为队尾。端称为队头，允许插入元素的一端称为
39、队尾。显然不论元素按何种顺序进入队列，也必显然不论元素按何种顺序进入队列，也必然按这种顺序出队列，所以队列又称为先进先然按这种顺序出队列，所以队列又称为先进先出（出（FIFOFIFO）表。队列有两个活动端，所以设置表。队列有两个活动端，所以设置了对头和队尾两个位置指针。一般队头指针记了对头和队尾两个位置指针。一般队头指针记作作frontfront，队尾指针记作队尾指针记作rearrear。abcfrontrear入队入队出队出队队列示意图队列示意图循环队列循环队列队列顺序存储队列顺序存储顺序存储的队列中，每次出队列的元顺序存储的队列中，每次出队列的元素必定是队头元素，因此如果采取与普素必定是队
40、头元素，因此如果采取与普通顺序表同样的操作方式，则每次出队通顺序表同样的操作方式，则每次出队操作必然将整个队列向前移动，这使得操作必然将整个队列向前移动，这使得效率大大降低。效率大大降低。因此因此在顺序存储的队列中，出队和入在顺序存储的队列中，出队和入队操作都不移动元素而是移动指针。队操作都不移动元素而是移动指针。为方便起见，这里规定队头指针为方便起见，这里规定队头指针front指向队头元素的前一个位置，队尾指针指向队头元素的前一个位置，队尾指针rear指向队尾元素所在位置。这样，指向队尾元素所在位置。这样，入队入队和出队操作的和出队操作的执行步骤都是首先执行执行步骤都是首先执行指指针移动，再
41、进行元素读写。针移动，再进行元素读写。对空队列而言，可假定对空队列而言，可假定front和和rear的的值为值为-1假溢出假溢出ABCfrontrearfrontrear(a)A B C入入队队 (b)A B出队出队,D E入入队队 (c)队列假溢出队列假溢出队列假溢出示意图CDEfrontrear随着元素不断入队列、出队列，随着元素不断入队列、出队列，rear和和front指针会指针会不断向后移动（如图不断向后移动（如图(b)所示），最终会指向数组的最所示），最终会指向数组的最大下标位置（如图大下标位置（如图(c)所示）。由于所示）。由于rear和和front指针只指针只能单方向移动，这时元
42、素无法入队列，但是队列中仍有能单方向移动，这时元素无法入队列，但是队列中仍有大量空闲位置。这种情况称为假溢出。大量空闲位置。这种情况称为假溢出。循环队列循环队列解决队列假溢出的办法是将存放队列元素的数组解决队列假溢出的办法是将存放队列元素的数组首尾相接，形成循环队列。首尾相接，形成循环队列。循环队列的基本操作循环队列的基本操作方式为：方式为：入队列时先执行入队列时先执行rear=(rear+1)%Mrear=(rear+1)%M，再将新元素再将新元素在在rearrear指示位置加入；指示位置加入；出队列时先执行出队列时先执行front=(front+1)%Mfront=(front+1)%M，
43、再将下标再将下标为为frontfront的元素取出。的元素取出。为了将队空和对满的条件加以区分，一般不使用为了将队空和对满的条件加以区分，一般不使用front指针所指的位置。指针所指的位置。队空条件为队空条件为front=rear队满条件为队满条件为(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE (a)a)循环队列空循环队列空 (b)b)非空循环队列非空循环队列 (c)c)循环队列满循环队列满 循环队列示意图循环队列示意图循环队列描述如下：循环队列描述如下：structSqQueueE
44、lemType*data;/存放元素的数组存放元素的数组intlength;/数组空间总长度数组空间总长度intfront;/队头指针队头指针intrear;/队尾指针队尾指针;SqQueueq;/定义队列定义队列qfront和和rear指针取值均为所指数组单元的下标。指针取值均为所指数组单元的下标。由于队头指针所指单元总是空的，由于队头指针所指单元总是空的，length比实际能比实际能存储的元素多一。存储的元素多一。常用算法常用算法（1）循环队列初始化）循环队列初始化初始化过程建立数组空间并将队头、队尾指针设定初始化过程建立数组空间并将队头、队尾指针设定到到0号单元。号单元。voidInit
45、Queue(SqQueue&Q,intsz)Q.length=sz+1;Q.front=Q.rear=0;Q.data=newElemTypeQ.length;这里这里sz为队列最大长度为队列最大长度，数组长度，数组长度lengthlength比比szsz大一。大一。（2）入队操作）入队操作若队列不满，则在队尾插入元素若队列不满，则在队尾插入元素x作为新的队尾。作为新的队尾。voidEnQueue(SqQueue&Q,ElemTypex)if(Q.rear+1)%Q.length=Q.front)cout队列已满队列已满;elseQ.rear=(Q.rear+1)%Q.length;Q.dat
46、aQ.rear=x;（3）出队操作出队操作若队列不空，则删除队头元素并用若队列不空，则删除队头元素并用e取回该元素取回该元素的值。的值。voidDeQueue(SqQueue&Q,ElemType&e)if(Q.rear=Q.front)cout队列已空队列已空;elseQ.front=(Q.front+1)%Q.length;e=Q.dataQ.front;（4）取队头元素取队头元素若队列不空，则用若队列不空，则用e取回队头元素的值。取回队头元素的值。voidGetHead(SqQueue&Q,ElemType&e)if(Q.rear=Q.front)coutnext=NULL;Q.rear
47、=Q.front;/尾指针也指向头结点尾指针也指向头结点（2）求队列的长度）求队列的长度返回队列的元素个数，即队列的长度。返回队列的元素个数，即队列的长度。intQueueLength(LinkQueue&Q)QNode*p=Q.front;intlen=0;while(p!=Q.rear)len+;p=p-next;returnlen;（3）入队列操作入队列操作插入元素插入元素x为队列新的队尾元素。为队列新的队尾元素。voidEnQueue(LinkQueue&Q,ElemTypex)QNode*s=newQNode;/建立新结点建立新结点ss-data=x;s-next=NULL;Q.re
48、ar-next=s;/在队尾插入在队尾插入结点结点sQ.rear=s;/修改队尾指针修改队尾指针（4）出队列操作）出队列操作若队列不空，则删除队头元素，用若队列不空，则删除队头元素，用e返回其值。返回其值。voidDeQueue(LinkQueue&Q,ElemType&e)QNode*p;if(Q.front=Q.rear)coutnext;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;deletep;删除最后一个元素时，需要修改尾指针，使其指向头结点。删除最后一个元素时，需要修改尾指针，使其指向头结点。（5）取队头元素）取队
49、头元素若队列不空，则用若队列不空，则用e返回队头元素；返回队头元素；voidGetHead(LinkQueue&Q,ElemType&e)QNode*p;if(Q.front=Q.rear)coutnext;e=p-data;求求k阶斐波那切数列某一项阶斐波那切数列某一项k阶斐波那切数列阶斐波那切数列ai定义如下：定义如下：解决方法解决方法解决方法解决方法:建立一个容量为建立一个容量为k k的循环队列，将前的循环队列，将前k k个个元素依次入队。然后计算第元素依次入队。然后计算第k+1k+1个元素，它等于队列个元素，它等于队列中全部元素之和。而后将对头元素出队，将第中全部元素之和。而后将对头元
50、素出队，将第k+1k+1个个元素入队。重复上述过程，就可求得任意指定项元元素入队。重复上述过程，就可求得任意指定项元素的值素的值。【例2-4】利用循环队列求k阶斐波那切数列某一式的值。树和图西安交通大学计教中心西安交通大学计教中心树的递归定义树的递归定义:树是由树是由n n个具有相同特性的数据元素组成的集合。若个具有相同特性的数据元素组成的集合。若n=0n=0，则称其为空树。一棵非空树则称其为空树。一棵非空树T T必须满足：必须满足：1 1）其中有一个特定的元素称为）其中有一个特定的元素称为T T的根的根rootroot。2 2）除根以外的集合可被划分为除根以外的集合可被划分为m m个不相交的