ch2_线性表.ppt

计算机软件基础计算机软件基础张新峰张新峰综合楼综合楼802Email:Tel:1587-802课件下载：课件下载：zxf_Key:rjjsjc1Ch2 线性数据结构线性数据结构2.1数据结构产生的背景数据结构产生的背景2.2 基本概念基本概念2.3 线性表线性表2.4 栈和队列栈和队列2.5 串和数组串和数组22.2.1 线性表的定义线性表的定义定定义义2-1 线线性性表表(Linear-list)是是n(n0)个个数数据元素的有限序列。记为：据元素的有限序列。记为：(a1，a2,.,an)其其中中，数数据据元元素素个个数数n称称为为表表的的长长度度，n=0时，称此线性表为空表时，称此线性表为空表。3L=(a1,a2,a3,a4,a5,a6,.,an)ai-1,ai ,ai+1直接前驱直接前驱 直接后继直接后继线性表长度线性表长度线性表的逻辑结构线性表的逻辑结构4线性表的特点线性表的特点同一性：线性表由同类数据元素组成，每同一性：线性表由同类数据元素组成，每一个一个ai必须属于同一数据对象。必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。表长度就是表中数据元素的个数。有序性：线性表中表中相邻数据元素之间有序性：线性表中表中相邻数据元素之间存在着序偶关系存在着序偶关系。5线性表举例线性表举例例例2-1 26个大写的英文字母表：个大写的英文字母表：(A，B，C，.，Z)例例2-2 某某校校从从1996年年到到2002年年各各种种型型号号计计算算机机拥拥有有量量的的变变化化情情况况，可可以以用用线线性性表表给给出：出：(200，220，250，300，400，700，1200)6姓姓 名名学学 号号性性 别别年年 龄龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 贫血贫血.例例2-3 学生健康情况登记表学生健康情况登记表7线性表的基本操作线性表的基本操作(1)INITIATE(L)初始化操作，设定一个空的线性表初始化操作，设定一个空的线性表L。(2)LENGTH(L)求表长，求出线性表求表长，求出线性表L中数据元素个数。中数据元素个数。(3)GET(L,i)取元素函数，若取元素函数，若1iLENGTH(L)，则函数值为给定线性则函数值为给定线性表表L中第中第i个数据元素，否则为空元素个数据元素，否则为空元素NULL。(4)PRIOR(L,elm)。求前趋函数，若求前趋函数，若elm的位序大于的位序大于1，则函数值为，则函数值为elm的前趋，的前趋，否则为空元素。否则为空元素。8线性表的基本操作线性表的基本操作(5)NEXT(L,elm)。求后继函数，若求后继函数，若elm的位序小于的位序小于LENGTH(L)，则函数值为，则函数值为elm的后继，否则为空元素。的后继，否则为空元素。(6)LOCATE(L,x)。定位函数，返回元素定位函数，返回元素x在线性表在线性表L中的位置。若中的位置。若L中有多个中有多个x，则只返回第一个，则只返回第一个x的位置，若在的位置，若在L中不存在中不存在x，则返回，则返回0。(7)INSERT(L,i,x)。插入操作，在线性表插入操作，在线性表L中的第中的第i个位置上插入元素个位置上插入元素x，运算结，运算结果使得线性表的长度增加果使得线性表的长度增加1。9线性表的基本操作线性表的基本操作(8)DELETE(L，i)。删除操作，若删除操作，若1iLENGTH(L)，删除给定线性表，删除给定线性表L中的第中的第i个数据元素，使得线性表的长度减个数据元素，使得线性表的长度减1。(9)EMPTY(L)。判空表函数，若判空表函数，若L为空表，则返回布尔值为空表，则返回布尔值“true”，否则返回布尔值，否则返回布尔值“false”。其他的操作：合并，排序。其他的操作：合并，排序。10线性表的顺序存储结构线性表的顺序存储结构将线性表的元素按其逻辑次序依次存将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里。放在一组地址连续的存储单元里。采用顺序存储结构的线性表通常称为采用顺序存储结构的线性表通常称为顺序表顺序表。11bb+lenb+(i-1)*lenb+(n-1)*lenb+(maxlen-1)*lena1a2aian空闲空闲Loc(ai)=Loc(a1)+(i-1)*len随随机机存存取取结结构构 线线性性表表的的顺顺序序存存储储结结构构12顺序存储结构的顺序存储结构的C语言实现语言实现 typedef int datatype;/*datatype可为任何类型，这里假设为可为任何类型，这里假设为int*/#define maxlen 1024 /*线性表可能的最大长度，这里假设为线性表可能的最大长度，这里假设为1024*/typedef struct datatype datamaxlen;int last;/最后一个元素在数组中位置（逻辑位置），最后一个元素在数组中位置（逻辑位置），即线性表的长度。即线性表的长度。sequenlist;13表的初始化表的初始化算法算法1 void InitList(sequenlist*L)/分配顺序表的动态存储空间，将表的长度置为分配顺序表的动态存储空间，将表的长度置为0 L=(sequenlist*)malloc(sizeof(sequenlist);L-last=0;14表的初始化表的初始化 算法算法2 sequenlist*initList()sequenlist*L=(sequenlist*)malloc(sizeof(sequenlist);L-last=0;return L;15线线性性表表的的插插入入a1:ai1aiai+1:an:a1:ai1aiai+1:an:aix插入插入x注意插入元素后：表长注意插入元素后：表长+116算法设计：算法设计：q命名命名:Insertq入口参数入口参数Lixq出口参数出口参数:L及插入是否成功标志及插入是否成功标志插入算法参数设置插入算法参数设置17需要考虑的问题：需要考虑的问题：q插入位置是否合理插入位置是否合理?q是否有空间是否有空间?q插入动作插入动作移动移动插入插入修改长度修改长度插入算法步骤插入算法步骤18int insert(sequenlist*L,int x,int i)int j;if(L-last=maxsize)print(“表已满表已满”);return 0;else if(i L-last+1)print(“非法插入位置非法插入位置”);return 0;else for(j=L-last-1 ;j=i-1;j-)L-dataj+1=L-dataj;/结点后移结点后移 L-datai1=x;/插入到插入到L-datai中中 L-last+;/表长度加表长度加1 return 1;19插入算法分析插入算法分析思考：数据元素合法的插入位置有多少个？思考：数据元素合法的插入位置有多少个？假假设设在在表表的的任任一一合合法法位位置置插插入入新新元元素素的的概概率率p均均等等，则则 p 1/(n+1)则插入操作中元素的平均移动次数则插入操作中元素的平均移动次数20a1:ai1aiai+1:an:a1:ai1ai+1:an:删除删除注意删除元素后：表长注意删除元素后：表长1线线性性表表的的删删除除21算法设计算法设计q命名命名:deleteq入口参数入口参数Liq出口参数出口参数:L及删除是否成功标志及删除是否成功标志删除算法参数设置删除算法参数设置22需要考虑的问题需要考虑的问题：删除位置是否合理删除位置是否合理?表是否为空表是否为空?删除操作删除操作保存被删除的元素内容保存被删除的元素内容保存被删除的元素内容保存被删除的元素内容移动移动移动移动修改长度修改长度修改长度修改长度删除算法的步骤删除算法的步骤23int delete(sequenlist*L,int i)int j;if(iL-last)print(“非法删除位置非法删除位置”);return 0;else for(j=i;j last-1;j+)L-dataj-1=L-dataj;/结点前移结点前移 L-last-;/表长度减表长度减1 return 1；24删除算法分析删除算法分析思考：合法的删除位置个数？思考：合法的删除位置个数？假假设设在在表表的的任任一一合合法法删删除除位位置置删删除除元元素素的的概概率率p均等，则均等，则 p1/n 则插入操作中元素的平均移动次数则插入操作中元素的平均移动次数25线性表的顺序存储结构特点线性表的顺序存储结构特点优点优点元素的逻辑关系相邻，物理位置上也相邻。元素的逻辑关系相邻，物理位置上也相邻。随机存取随机存取缺点缺点在作插入或删除操作时，需移动大量元素；在作插入或删除操作时，需移动大量元素；长长度度变变化化较较大大的的线线性性表表预预先先分分配配空空间间时时，须须按按最大空间分配，存储空间不能得到充分利用；最大空间分配，存储空间不能得到充分利用；表的容量难以扩充。表的容量难以扩充。26作业作业1.已知一个顺序表已知一个顺序表L的元素按照值非递减有序排的元素按照值非递减有序排列，试用列，试用C语言编写一个算法将元素语言编写一个算法将元素x插入，插插入，插入后该表仍然保持非递减有序排列。入后该表仍然保持非递减有序排列。2.用顺序表用顺序表A、B表示集合，试用表示集合，试用C语言编写算语言编写算法求集合法求集合A和集合和集合B的交集（假设的交集（假设A、B内无重复内无重复元素）。元素）。27线性表的顺序存储结构特点线性表的顺序存储结构特点n顺顺序序存存储储结结构构适适合合于于表表中中元元素素变变动动较较少少的的情况情况n原因：存放的连续性原因：存放的连续性n突破突破n用用地地址址任任意意的的存存储储单单元元存存放放，主主要要指指离离散散存放存放n用指针来表示元素之间的关系用指针来表示元素之间的关系28顺序存储结构顺序存储结构链式存储结构链式存储结构29单链表结点的概念单链表结点的概念数据元素内容数据元素内容该数据元素的该数据元素的直接后继地址直接后继地址datanext数据域数据域指针域指针域30链表结点的链表结点的C语言描述语言描述结点的结点的C语言描述为：语言描述为：struct node int data;struct node*next;typedef struct node NODE；31a1a3a2a4head可用存储空间可用存储空间单链表结构单链表结构不同结点存储位置一般是分散的，但每个结点不同结点存储位置一般是分散的，但每个结点所包含的数据项却是存放在一小块连续的空间中所包含的数据项却是存放在一小块连续的空间中32a1a3a2a4head单链表结构单链表结构l 为了顺次访问每个结点，需要保存单链表第一个为了顺次访问每个结点，需要保存单链表第一个结点的存储地址，这个地址称为线性表的头指针。结点的存储地址，这个地址称为线性表的头指针。l 头指针在单链表中一般不后移。头指针在单链表中一般不后移。33存储地址存储地址数据域数据域指针域指针域 1horse8 8monkey40 15pandaNULL 23cat1 35pig15 40elephant3523头指针头指针headcathorsemonkeyelephantpigpanda线性链表的逻辑状态示意图线性链表的逻辑状态示意图线性链表的物理状态示意图线性链表的物理状态示意图线性链表举例线性链表举例head34a1ana2headhead不带头结点的单链表不带头结点的单链表两种链表两种链表a 非空表非空表b 空表空表a1anheada2head带头结点的单链表带头结点的单链表a 非空表非空表b 空表空表35链表结点的链表结点的C语言描述语言描述 struct node int data;struct node*next;typedef struct node NODE；36链表基本操作链表基本操作-初始化初始化NODE*Init()/建立一个空的单链表建立一个空的单链表 L=(NODE*)malloc(sizeof(NODE)；if(L=NULL)printf(“无内存空间可分配无内存空间可分配”);exit(0);L-next=NULL;return L;37链表基本操作链表基本操作-求表长求表长int Length(NODE*L)/求带头结点的单链表的长度求带头结点的单链表的长度NODE*p;p=L-next;/p指向第一结点指向第一结点 j=0;while(p)j+;p=p-next;/移移动动p指向下一结点指向下一结点 return j;38链表基本操作链表基本操作-取第取第i个元素个元素NODE*Get(NODE*L,int i);NODE*p;if(inext;j=1;while(p!=NULL&jnext;j+;if(j=i)return p;else return NULL;39链表基本操作链表基本操作-按值查找按值查找NODE*Locate(NODE*L,int x)NODE*p;p=L-next;while(p!=NULL&p-data!=x)p=p-next;if(!p)printf(“无所无所查查找的找的结结点点”);return NULL;else return p;40链表基本操作查找链表基本操作查找问题描述：查找链表的第问题描述：查找链表的第i 个结点个结点问题分析：问题分析：输入：链表，输入：链表，i输出：指向第输出：指向第i个结点的指针个结点的指针41链表查找链表查找a1a2aiheadpppp42查找步骤查找步骤step1 初始化初始化,指针指针p指向头指针指向头指针,计数器置计数器置0step2 p非空且计数器小于非空且计数器小于i循环循环step3 每循环一次每循环一次,p后移一个位置后移一个位置,计数器加计数器加1step4 循环结束循环结束,返回指向返回指向ai 的指针的指针p43NODE*get(NODE*head,int i)NODE*p;int counter=0;/指针指针p指向头结点指向头结点 p=head;while(p!=NULL)&(counter next;/计数器加计数器加1 counter+;/找到结点找到结点 if(p!=NULL)&(counter=i)/*找到找到,1=in或或idata=x s-next=p-next p-next=sai-1aipsx插入算法步骤插入算法步骤52void insert(NODE*head,int i,int x)NODE*p,*s;int j=0;p=head;while(p!=NULL)&(j next;j+;if(p=NULL)|(j i-1)printf(i值不合法值不合法 n);/*找不到找不到,in或或i data=x;s-next=p-next;p-next=s;53ai-1pai+1ait删除操作删除操作54step1 找到找到ai-1的的位置位置,使指针使指针p指向指向ai-1step2 使指针使指针t指向指向p所指结点的后继所指结点的后继step3 使使t所指结点所指结点ai 脱脱链链step4 释放释放t。删除步骤删除步骤 55void delete(NODE*head,int i)NODE*p,*s;int j=0;p=head;while(p-next!=NULL)&(j next;j+;if(p-next=NULL)|(j i-1)printf(“i值不合法值不合法 n”);/*找不到找不到,in或或i next;p-next=s-next;free(s);56算法设计算法设计q命名命名:createlink1q入口参数入口参数:无无q出口参数出口参数:head反向建立链表反向建立链表57q创建头结点；创建头结点；q重复下列操作重复下列操作N次：次：输入元素信息；输入元素信息；创建结点；创建结点；将新结点插入到首端。将新结点插入到首端。反向建立链表算法步骤反向建立链表算法步骤58反向建立链表反向建立链表headAN-1sheadAN-1AN-2AN-1Ai+1headAis59反向建立链表反向建立链表C程序实现程序实现#define N m /*m为链表中数据元素的个数为链表中数据元素的个数*/int AN;NODE*creatlink1()NODE*head,*s;int i;/*生成头结点生成头结点*/head=(NODE*)malloc(sizeof(NODE);/*置空表置空表 */head-next=NULL;60for(i=N-1;i=0;i-)/*插入插入N个数据个数据 */*生成新结点生成新结点*/s=(NODE*)malloc(sizeof(NODE);/*将输入数据放入新结点数据域将输入数据放入新结点数据域*/s-data=Ai;/*新结点与原首结点链接新结点与原首结点链接*/s-next=head-next;/*将新结点插入到表头将新结点插入到表头*/head-next=s;/*返回单链表头指针返回单链表头指针*/return head;61算法设计算法设计q命名命名:creatlink2q入口参数入口参数:无无q出口参数出口参数:h正向建立链表正向建立链表62q创建创建(设置设置)头结点头结点(head)；q重复下列操作重复下列操作n次：次：输入元素信息输入元素信息;创建结点；创建结点；将新结点插到链表的尾端。将新结点插到链表的尾端。q设置尾指针设置尾指针p为空；为空；正向建立链表算法步骤正向建立链表算法步骤63正向建立链表正向建立链表headA0sheadA0Ai-1A0headAip spspp64正向建立链表正向建立链表C程序实现程序实现NODE*creatlink2()NODE*head,*p,*s;int num;/*生成头结点生成头结点*/head=(NODE*)malloc(sizeof(NODE);/*读入第一个结点值读入第一个结点值*/scanf(“%d”,&num);/*头指针头指针=尾指针尾指针*/p=head;while(num!=0)/*输入为输入为0为输入结束符为输入结束符*/65 /*生成新结点生成新结点*/s=(NODE*)malloc(sizeof(NODE);/*新结点上填入输入值新结点上填入输入值*/s-data=num;/*新结点新结点*s插入到尾结点插入到尾结点*p之后之后*/p-next=s;/*尾指针尾指针p指向新的表尾指向新的表尾*/p=s;/*读入下一个结点值读入下一个结点值*/scanf(“%d”,&num);/*将尾结点的指针置空将尾结点的指针置空*/p-next=NULL;/*返回单链表头指针返回单链表头指针*/return head;66 例例2-6 设设计计算算法法：将将一一个个带带头头结结点点的的单单链链表表A分分解解为为两两个个带带头头结结点点的的单单链链表表A和和B，使使得得A表表中中含含有有原原表表中中序序号号为为奇奇数数的的元元素素，B表表中中含含有有原原表表中中序序号号为为偶数的元素，且保持其相对顺序。偶数的元素，且保持其相对顺序。67例题例题2-6A2A1AA3pBrqq=p-next;p-next=q-next;r-next=q;pA4qp=p-next;r=q;r68解：解：void disA(NODE*A,NODE*B)NODE*r,*p,*q;B=(NODE*)malloc(sizeof(NODE);/*建立单链表建立单链表B的头结点的头结点*/r=B;p=A-next;while(p!=NULL)&(p-next!=NULL)69 q=p-next;p-next=q-next;r-next=q;r=q;p=p-next;r-next=NULL;p-next=NULL;70定义定义 表中最后一个结点的指针域指向头结表中最后一个结点的指针域指向头结 点，点，链表形成一个环。链表形成一个环。特点特点 从表中任何一个结点出发可扫描整个链表从表中任何一个结点出发可扫描整个链表中的所有结点中的所有结点。循环链表循环链表 71循环链表循环链表a1heada2anhead非空表非空表空表空表循环单链表循环单链表72每个结点有两个指针域每个结点有两个指针域datanextprior特点特点:克服单链表的单向性克服单链表的单向性双向链表结构双向链表结构 73typedef struct DNode DataType data;struct DNode *prior,*next;DLinkList;双向链表定义双向链表定义 74双向链表双向链表headheada1a2an带头结点的空双向链表带头结点的空双向链表带头结点的非空双向链表带头结点的非空双向链表75heada1a2anpp-next-prior=p-prior-next=phead带头结点的空双向循环链表带头结点的空双向循环链表带头结点的非空双向循环链表带头结点的非空双向循环链表76双向链表插入结点双向链表插入结点abxsps-prior=p-prior;(p-prior)-next=s;s-next=p;p-prior=s;77双向链表删除双向链表删除abcp(p-prior)-next=p-next(p-next)-prior=p-prior;free(p);78例题2-8heada1a2anqp79 顺序存储优点顺序存储优点方法简单方法简单,各种高级语言中都有数组各种高级语言中都有数组,易实现。易实现。不用为表示结点间的逻辑关系而增加额外的不用为表示结点间的逻辑关系而增加额外的存储开销。存储开销。顺序表具有按元素序号随机访问的特点。顺序表具有按元素序号随机访问的特点。顺序表与链表的比较顺序表与链表的比较80 顺序存储表的缺点顺序存储表的缺点做插入、删除操作时，平均移动大约表中一做插入、删除操作时，平均移动大约表中一半的元素，对于表长较大的顺序表效率低。半的元素，对于表长较大的顺序表效率低。需预先分配足够大的存储空间，估计过大，需预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。过小，又会造成溢出。链表的优缺点恰好与顺序表相反链表的优缺点恰好与顺序表相反。顺序表与链表的比较顺序表与链表的比较81 v线性表的长度：线性表的长度：当对线性表的长度或存储规模相对固定当对线性表的长度或存储规模相对固定时，采用顺序表；反之，采用链表。时，采用顺序表；反之，采用链表。v 线性表要进行的操作：线性表要进行的操作：顺序表连续顺序存放，随即存顺序表连续顺序存放，随即存取，适合频繁查找的操作。但当线性表要进行大量的删取，适合频繁查找的操作。但当线性表要进行大量的删除、插入运算时，用顺序存储会导致大量的元素移动，除、插入运算时，用顺序存储会导致大量的元素移动，易采用链表。易采用链表。v 采用的程序设计语言：采用的程序设计语言：顺序表容易实现，并且任何高顺序表容易实现，并且任何高级语言中都有数组类型，链表的操作是基于指针的，只级语言中都有数组类型，链表的操作是基于指针的，只适合提供指针操作的程序设计语言。适合提供指针操作的程序设计语言。在实际应用一般可以考虑以下几点在实际应用一般可以考虑以下几点在实际应用一般可以考虑以下几点在实际应用一般可以考虑以下几点顺序表与链表的比较顺序表与链表的比较栈和队列栈和队列83 栈栈定义定义 插入、删除只在线性表一端进行的插入、删除只在线性表一端进行的线性表被称为栈。线性表被称为栈。a1 a2 a3 a4 .an插入插入删除删除84后进先出后进先出-LIFO (Last In First Out)栈顶浮动栈顶浮动栈底固定栈底固定栈的特点栈的特点85设计栈的意义设计栈的意义1.调用函数或子程序非它莫属；调用函数或子程序非它莫属；2.递归递归运算的有力工具；运算的有力工具；3.用于保护现场和恢复现场；用于保护现场和恢复现场；4.简化了程序设计的问题简化了程序设计的问题。86栈的基本操作栈的基本操作置空栈置空栈SetNull(S)，完成对栈的初始化。，完成对栈的初始化。判断栈是否为空判断栈是否为空Empty(S)，若栈，若栈S为空，则返为空，则返回真；否则，返回假。回真；否则，返回假。进栈进栈Push(S，e)，在栈顶插入数据元素，在栈顶插入数据元素e。出栈出栈Pop(S)，删除栈，删除栈S的栈顶数据元素，并把的栈顶数据元素，并把出栈数据元素返回。出栈数据元素返回。取栈顶元素取栈顶元素GetTop(S)，取栈，取栈S的栈顶数据元的栈顶数据元素，并把数据元素返回。素，并把数据元素返回。87与线性表相同，仍为一对一与线性表相同，仍为一对一(1:1)关系关系。用用顺序栈顺序栈顺序栈顺序栈或或链栈链栈链栈链栈存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见只能在只能在栈顶栈顶栈顶栈顶运算，且访问结点时依照运算，且访问结点时依照后进先出后进先出后进先出后进先出（LIFO）的原则。的原则。关键是编写关键是编写入栈入栈入栈入栈和和出栈出栈出栈出栈函数，具体实现依顺函数，具体实现依顺序栈或链栈的存储结构有别而不同。序栈或链栈的存储结构有别而不同。存储结构存储结构存储结构存储结构运算规则运算规则运算规则运算规则实现方式实现方式实现方式实现方式 逻辑结构逻辑结构逻辑结构逻辑结构栈栈88栈栈栈栈 是仅在是仅在表尾表尾进行插入、删除操作的线性表。进行插入、删除操作的线性表。表尾表尾(即即 an 端端)称为称为栈顶栈顶;表头表头(即即 a1 端端)称为称为栈底。栈底。例如：例如：栈栈 S S=(a1 ,a2 ,a3 ,.,an-1 ,an)插入元素到栈顶的插入元素到栈顶的操作，称为操作，称为入栈入栈。从栈顶删除最后一从栈顶删除最后一个元素的操作，称个元素的操作，称为为出栈出栈。a an n称为栈顶元素称为栈顶元素a a1 1称为栈底元素称为栈底元素强调：强调：强调：强调：插入和删除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！89堆栈一般线性表异同堆栈一般线性表异同 堆栈是一种特殊的线性表，它只能在表的堆栈是一种特殊的线性表，它只能在表的一端（即一端（即一端（即一端（即栈顶）栈顶）栈顶）栈顶）进行插入和删除运算。进行插入和删除运算。与一般线性表的区别：仅在于与一般线性表的区别：仅在于运算规则运算规则运算规则运算规则不同。不同。一般线性表一般线性表一般线性表一般线性表 堆栈堆栈堆栈堆栈逻辑结构：逻辑结构：1:1 逻辑结构：逻辑结构：1:1 存储结构：顺序存储结构：顺序表表、链、链表表 存储结构：顺序存储结构：顺序栈栈、链、链栈栈运算规则：运算规则：随机存取随机存取随机存取随机存取 运算规则：运算规则：后进先出后进先出后进先出后进先出“进进”插入插入=压入压入=PUSH（an+1)“出出”删除删除=弹出弹出=POP(an)90例例例例1 1：一个栈的输入序列为一个栈的输入序列为1、2、3，若在，若在入栈的过入栈的过程中允许出栈程中允许出栈，则可能得到的出栈序列是什么？，则可能得到的出栈序列是什么？答：答：答：答：可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解：1入入1出，出，2入入2出，出，3入入3出，出，即即123；1入入1出，出，2、3入，入，3、2出，出，即即132；1、2入，入，2出，出，3入，入，3、1出，出，即即231；1、2入，入，2、1出，出，3入入3出，出，即即213；1、2、3入，入，3、2、1出，出，即即321；合计有合计有5种可能性。种可能性。91#define MAXSIZE 100 /栈容量栈容量typedef struct DataType dataMAXSIZE;/存储空间存储空间 int top;/栈顶指针栈顶指针 Stack;顺序栈顺序栈定义定义92q栈空时，栈空时，top=-1；非空时，非空时，top位于位于栈顶元素的位置栈顶元素的位置q顺序栈的空间固定顺序栈的空间固定顺序栈顺序栈实现要点实现要点93Stack *InitStack()/构造一个空栈构造一个空栈s Stack*S；S=(Stack*)malloc(sizeof(Stack);S-top=-1;return S;顺序栈顺序栈建立算法建立算法94int EmptyStack(Stack*S)/若栈空，则返回若栈空，则返回1，否则返回否则返回0 if(S-top=-1)return 1;else return 0;判定顺序栈是否空算法判定顺序栈是否空算法95intint GetTop(Stack*S,DataTypeDataType*x)/若栈不空，则返回若栈不空，则返回1，否则返回否则返回0 if(S-top=-1)return 0;else x=(DataTypeDataType*)malloc(sizeof(DataTypeDataType);*x=S-data S-top;return 1;取顺序栈顶元素算法取顺序栈顶元素算法96int Push(Stack*S,DataType x)/插入元素插入元素x为新的栈顶元素为新的栈顶元素 if(S-top=MAXSIZE-1)return 0;else S-top+;S-data S-top=x;return 1;顺序栈顺序栈进栈算法进栈算法97int Pop(Stack*S,DataTypeDataType*x)/若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用x返回其值，返回其值，并返回并返回1；否则返回否则返回0 if(S-top=-1)return 0;else x=(DataTypeDataType*)malloc(sizeof(DataTypeDataType);*x=S-data S-top;S-top-;return 1;顺序栈顺序栈出栈算法出栈算法98typedef struct snode DataType data;/存储栈元素存储栈元素 struct lnode*next;/指针指针Stack;Stack *top;链栈链栈定义定义(栈的大小不定栈的大小不定)99datanexttop栈顶栈顶栈底栈底100q栈空时，栈空时，top=NULL；非空时，；非空时，top指向栈顶元素指向栈顶元素q链栈的空间不固定链栈的空间不固定链栈链栈实现要点实现要点101Stack *InitStack()/构造一个空构造一个空链链栈栈 return NULL;链栈链栈建立算法建立算法102int EmptyStack(Stack*top)/若若链链栈空，则返回栈空，则返回1，否则返回否则返回0 if(top=NULL)return 1;else return 0;判链栈是否为空的算法判链栈是否为空的算法103intint GetTop(Stack*top,DataTypeDataType*x)/若若链链栈不空，则返回栈不空，则返回1，否则返回否则返回0 if(top=NULL)return 0;else x=(DataTypeDataType*)malloc(sizeof(DataTypeDataType);*x=top-data;return 1;取链栈栈顶元素的算法取链栈栈顶元素的算法104void Push(Stack*top,DataType x)/插入元素插入元素x为新的为新的链链栈顶元素栈顶元素 Stack*p;p=(Stack*)malloc(sizeof(Stack);p-data=x;p-next=top;top=p;链栈链栈进栈算法进栈算法105int Pop(Stack*top,DataType*x)/若若链链栈不空栈不空,则删除则删除链链栈的栈顶元素，用栈的栈顶元素，用x返回其值，并返回其值，并返回返回1；否则返回否则返回0 if(top=NULL)return 0;else x=(DataType*)malloc(sizeof(DataType);*x=top-data;p=top;top=top-next;free(p);return 1;链栈链栈出栈算法出栈算法106队列队列在现实生活中，队列比比皆是，它反映在现实生活中，队列比比皆是，它反映“先来先服务先来先服务”的处理原则。的处理原则。自动流水装配线上部件的处理过程就是队列的自动流水装配线上部件的处理过程就是队列的典型例子，最早进入队列的最早离开。典型例子，最早进入队列的最早离开。操作系统中的作业调度队列以及共享环境下计操作系统中的作业调度队列以及共享环境下计算机各种外部设备的分配和使用等。算机各种外部设备的分配和使用等。107为什么要研究队列？为什么要研究队列？1.1.离散事件的模拟离散事件的模拟（模拟事件发生的先后（模拟事件发生的先后顺序）顺序）；2.2.操作系统中的作业调度操作系统中的作业调度（一个（一个CPUCPU执行执行多个作业）多个作业）；3.3.简化程序设计。简化程序设计。108 若线性表的插入操作在一端进行，若线性表的插入操作在一端进行，删除操作在另一端进行，则称此删除操作在另一端进行，则称此线性表为队列。线性表为队列。队列队列定义定义109a1,a2,a3,a4,.,an删除端删除端插入端插入端队头队头front队尾队尾rear队列队列结构结构110FIFO (First In First Out)队头、队尾均是浮动的队头、队尾均是浮动的队列队列特点特点111队列的顺序存储结构队列的顺序存储结构struct sequeue datatype datamaxsize;int front，rear;/*顺序队列的类型顺序队列的类型*/sequeue sq /*sq 是顺序队列的指针是顺序队列的指针*/规定：规定：头指针头指针front总是指向当前队头元素的前一个位总是指向当前队头元素的前一个位 置，尾指针置，尾指针rear指向当前队尾元素的位置指向当前队尾元素的位置。112队列的运算队列的运算入队运算入队运算sqrear+;/*尾指针加尾指针加1*/sqdatasqrear=x;/*x入队入队*/出队运算出队运算sqfront+;/*头指针加头指针加1*/113DCBAsq-rear=-1sq-front=-1sq-rear=0sq-rear=1sq-rear=2sq-rear=3sq-rear=-1sq-front=-1空队列空队列A、B、C、D相继入队相继入队114sq-front=0sq-front=1sq-front=2sq-rear=3sq-front=-1CDBAsq-front=3A、B、C、D相继出队相继出队EFsq-front=3sq-rear=5E、F相继出队相继出队115总结队列为空与队列为满的条件总结队列为空与队列为满的条件116EFsq-front=3sq-rear=5E、F相继出队相继出队假溢出现象假溢出现象 请想想如何解决请想想如何解决假溢出问题？假溢出问题？117循环队列示意图循环队列示意图118循环队列循环队列队头指针的后移队头指针的后移 if(sq-front+1=maxsize)sq-front=0 else front=front+1 或 front=(front+1)%maxsize119队尾指针的后移队尾指针的后移 if(sq-rear+1=maxsize)sq-rear=0 else sq-rear=sq-rear+1 或 sq-rear=(sq-rear+1)%maxsize120如何判断循环队列为空队列如何判断循环队列为空队列 sq-frontsq-reara0a1a2a3 sq-frontsq-rear空队列空队列满队列满队列121 sq-frontsq-reara1a2a3 sq-frontsq-rear空队列空队列满队列满队列122判断空队和满队的条件判断空队和满队的条件空队列：空队列：sq-rear=sq-fro