吉林大学数据结构课件 第二章 线性表、堆栈和队列

第二章线性表、堆栈和队列,线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构,例1英文字母表(A,B,C,Z)例2某班学生健康情况登记表。学号姓名性别年龄健康情况01张军男18一般02陈红女17良好03陈军男19健康,线性表定义：一个线性表是由零个或多个具有相同类型的结点组成的有序集合。通常用（a0，a1，an-1）来表示一个线性表，n为自然数。当时，a0称为线性表的表头（head），an-1称为线性表的表尾（tail），ai称为ai+1的前驱结点，ai+1称为ai的后继结点；当时，表中没有结点（包含零个结点），这样的线性表被称为空表。,线性表的操作1.创建一个线性表；2.确定线性表的长度；3.确定线性表是否为空；4.存取表中第k个结点的字段值；5.查找指定字段值在表中的位置；6.删除表中第k个结点；7.在表中第k个结点后插入一个新结点；,线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构,线性表的存储结构,在线性表（a0，a1，an-1）中，对于表中的相邻结点ai与ai-1（这里的“相邻”是指二者逻辑相邻）它们在计算机存储器中的物理存储地址Loc(ai)与Loc(ai-1)的关系？,顺序存储结构顺序存储：用一组连续的存储空间依次存储线性表的元素。特点：其逻辑顺序与物理顺序相同。实现顺序存储的最有效方法是使用一维数组。例：线性表(a0，a1，a2,a3)。,顺序存储结构实现顺序存储的最有效方法是使用一维数组。,图4.1是包含4个结点的线性表A4在内存中的表示，其中每个结点占2个连续的字节，第一个结点A0的首地址为302,Loc(ak)=Loc(a0)+k*c,起始存储位置：b每个元素大小：c求第k个元素的开始位置？,线性表上实现的基本运算1、插入例在线性表(12,13,21,24,28,30,42,77)中下标为3的结点后，插入元素25。,在下标为k的结点后插入一个新结点/ADL描述算法Insert(A,k,x)IF(kn)THENPRINT(“overflow”).ELSE(FORi=nTOk1STEP-1DOAi+1Ai.Ak1x.nn+1.),2、删除例在线性表(12,13,21,24,28,30,42,77)中删除下标为3的元素。,删除下标为k的结点/ADL描述算法Delete(A,k)IF(kn)THENPRINT(“error”)ELSE(FORi=k+1TOnDOAi-1Ai.nn-1.),结论：优点：线性表的顺序存储结构简单、易于实现，可以随机访问表中任一元素。缺点：线性表的容量不容易扩充；插入、删除麻烦，需移动元素。,线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构,1、单链表的定义链式存储：用一组任意存储单元存储线性表的数据元素。,单链表的结点结构：链表的第一个结点被称为头结点，指向头结点的指针被称为头指针。链表的最后一个结点被称为尾结点。单链表的定义：每个结点只含有一个指针域的链表叫单链表。,特点：逻辑顺序与物理顺序可以相同也可以不同。优点：插入、删除方便。合理利用空间。例将线性表(a3，a4，a5)以链表的形式存储在内存中。,(a3，a4，a5),002,500,删除当前节点的后继节点：算法Delete(this.tempptr)/*删除当前结点的后继结点，并令指针tempptr指向被删除结点*/IFnext（this）=NULLTHENtempptrNULLELSE（tempptrnext（this）.next（this）next（tempptr）.,在当前结点之后插入结点p/ADL描述算法InsertAfter(this，p)IA1将当前结点的next域值赋给P的next域next(p)next(this).IA2将P赋给当前结点的next域next(this)p,在头指针为head的链表中，插入一个data域为item的新结点作为该链表的表头结点。算法InsertFront(head，item)IF1调用函数GetNodeGetNode(item,head.newNode).IF2head指向新结点headnewNode.,HAT,GAT,head,遍历链表,所谓遍历一个结构，是指按一定的次序访问结构中的所有结点，且每个结点恰被访问一次。遍历链表，就是按一定次序访问链表的所有结点。要想遍历整个链表，必须从头指针开始。,遍历链表遍历链表演示算法PrintList(head)/输出头指针为head的链表,每输出5个元素换行PL1取表头，计数器初始化currptrhead.count0.,PL2遍历并输出链表结点的data值WHILE(currptrNULL)DO(PRINT(data(currptr).countcount+1.if(countmod5)=0PRINT(ENTER).currptrnext(currptr).),a,b,c,操作:遍历插入InsertFrontInsertRearInsertAtInsertAfeter删除,单链表的缺点,从一个结点出发，只能访问到链接在它后面的结点，而无法访问位于它前面的结点。链接结构“循环化”，即令表尾结点的next域存放指向表头结点的指针，而不是存放空指针NULL，这样的链表被称为循环链表。,循环链表1循环链表的定义和结构定义：在单链表中，使其最后一个结点的指针又指回到第一个结点，则这样的链表叫循环链表循环链表表头：哨位节点（数据为空，指向第一个数据项）,注意：判断表尾的条件：第一个节点判断空表的条件：,Header,Header,p-next=NULLp-next=header,Head=NULLHeader-nextHeader,双向循环链表1问题的提出：找一个结点的前趋结点2双向循环链表的结构链表的结构,结点结构：,Headerleft=Headerright=Headerp-right-left=p-left-right=p,循环双链表判空的条件：,在当前结点(this)之后插入结点p算法InsertRight(this，P)/在当前结点Node(this)的右边插入结点Node(P)IR1令当前结点的右结点的左指针指向Node(P)left(right(this)P.IR2令Node(P)的右指针指向当前结点的右结点right(P)right(this).IR3令Node(P)的左指针指向当前结点left(P)this.IR4令当前结点的右指针指向Node(P)right(this)P,left(right(this)P.right(P)right(this).left(P)this.right(this)P,this,在当前结点(this)之后插入结点p算法InsertRight(this，P)/在当前结点Node(this)的右边插入结点Node(P)IR1令当前结点的右结点的左指针指向Node(P)left(right(this)P.IR2令Node(P)的右指针指向当前结点的右结点right(P)right(this).IR3令Node(P)的左指针指向当前结点left(P)this.IR4令当前结点的右指针指向Node(P)right(this)P,在当前结点(this)之前插入结点p算法InsertLeft(this，P)/InsertLeft用IL简记IL1令Node(P)的左指针指向当前结点的左结点left(P)left(this).IL2令当前结点之左结点的右指针指向Node(P)right(left(this)P.IL3令Node(P)的右指针指向当前结点right(P)this.IL4令当前结点的左指针指向Node(P)left(this)P,左插入演示,left(P)left(this),this,right(left(this)P.,right(P)this.,left(this)P,算法DeleteNode（this）/*删除当前结点*/DN1.令当前结点的左结点的右指针指向当前结点的右结点right（left（this）right（this）.DN2.令当前结点的右结点的左指针指向当前结点的左结点left（right（this）left（this）,right（left（this）right（this）.left（right（this）left（this）,this,对比分析空间效率,顺序表当表中的元素较少时，顺序表中的很多空间处于闲置状态，造成了空间的浪费；链表所占用的空间是根据需要动态申请的，不存在空间浪费的问题，但是链表需要在每个结点上附加一个指针线性表长度较大时，顺序表的空间效率较高，线性表长度N较小时，链表的空间效率较高。,对比分析时间复杂性,顺序表随机存取是非常容易的，但是每插入或者删除一个元素，都需要移动若干元素；链表无法实现随机存取，必须要从表头开始遍历链表，直到找到要存取的元素，但是链表的插入和删除操作却非常简便当线性表经常需要进行插入、删除操作时，链表的时间复杂性较小，效率较高；当线性表经常需要存取，且存取操作比插入删除操作频繁的情况下，则是顺序表的时间复杂性较小，效率较高。,栈和队列,栈和队列都是操作受限的线性表,堆栈堆栈的定义和主要操作堆栈的顺序存储,内容提要：堆栈是一种操作受限制的线性表堆栈的特性：后进先出堆栈的顺序存储,堆栈和队列堆栈的定义和操作栈的定义：栈是插入和删除只能在其一端进行的线性表。并按先进后出(FILO)或后进先出(I)的原则进行操作。,例有一线性表(a1,a2,a5),空栈栈顶栈底,a5,a3,a2,a1,a4,入栈顺序e0e1e2en-2en-1出栈顺序en-1en-2e2e1e0栈可以对序列实现求逆,en-1,e0,e1,en-2,进栈(Push)出栈(Pop),栈顶top,栈底,栈的特性：后进先出性。,举例,栈的封闭性：在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好，使用起来非常安全。,堆栈的基本操作：,push(item):压入一个元素（插入）；pop(item):弹出一个元素（删除）；peek(item):存取栈顶元素值；clear():清空栈；IsEmpty():判断栈是否为空；,堆栈的顺序存储使用数组存放栈元素，栈的规模必须小于或等于数组的规模，当栈的规模等于数组的规模时，就不能再向栈中插入元素。堆栈的类定义与实现类Stack中所涉及到的数据成员：/存放堆栈元素的数组：TstacklistMaxStackSize;/栈顶所在数组元素的下标：inttop;,使用数组存放堆栈元素初始top=-1堆栈的状态堆栈空：top=-1堆栈满：top=MaxStackSize-1,栈内变化情况,向栈顶压入一个元素算法Push(item)Push1堆栈已满？IFtop=MaxStackSize1THEN(PRINT“STACKOVERFLOW!”.RETURN.).Push2栈顶指针加1toptop+1.stacklisttopitem,-1,堆栈变化情况,1,2,3,0,A,C,B,初始状态A压入栈B、C压入栈,从栈顶弹出一个元素算法Pop(.temp)Pop1堆栈已空？IFtop=1THEN(PRINT“Attempttopopanemptystack!”.RETURN.).Pop2保存栈顶元素，改变栈顶位置tempstacklisttop.toptop1,-1,堆栈变化情况,1,2,3,0,A,C,B,初始状态C弹出栈B、A弹出栈,测试栈是否为空栈空的条件：top=-1算法StackEmpty(.i)SE1堆栈已空？IFtop=1THENi1ELSEi0.测试栈是否为满栈满的条件：top=MaxStackSize-1算法StackFull(.i)SF1堆栈已满？IFtop=MaxStackSize1THENi1ELSEi0.,清空栈算法ClearStackCS1重置栈顶top1.RETUEN.,链式栈,用数组实现的栈效率很高，但若同时使用多个栈，顺序栈将浪费大量的空间栈顶对应链表的表头还是表尾?栈主要操作的对象是栈顶元素若栈顶对应表尾，则每次栈顶操作都要对单链表进行遍历,顺序栈与链式栈的比较,在空间复杂性上顺序栈必须初始就申请固定的空间，当栈不满时，必然造成空间的浪费；链式栈所需空间是根据需要随时申请的，其代价是为每个元素提供空间以存储其next指针域。在时间复杂性顺序栈和链式栈的时间复杂性均为O(1).在堆栈的实际应用中，有时还需对非栈顶元素进行存取，对于这类存取操作，用数组实现的顺序栈可以快速定位，其时间复杂性为O(1),小结：堆栈是一种操作受限制的线性表push和pop操作只和栈顶有关堆栈的特性：后进先出堆栈的状态堆栈空：top=-1堆栈满：top=MaxStackSize-1,堆栈的应用语法检查（括号出现次数）扫描待检查程序中的每一个字符，当扫描到每个花、中、圆左括号时，令其进栈，当扫描到每个花、中、圆右括号时，则检查栈顶是否为相应的左括号，若是则作退栈处理，若不是则表明出现了语法错误，应返回0。当扫描到程序文件结尾后，若栈为空则表明没有发现括号配对错误，应返回1，否则表明栈中还有未配对的括号，应返回0。另外，对于一对单引号或双引号内的字符不进行括号配对检查。,堆栈的应用十进制数转换为r进制数首先用十进制整数x除以基数r，得到的整余数是r进制数y的最低位y0，放入堆栈，接着以x除以r的整数商作为被除数，用它除以r得到的整余数是y的次最低位y1，放入堆栈；依次类推，直到商为0时得到的整余数是y的最高位ym，放入堆栈，假定y共有m+1位，则栈顶是最高位，且栈中有m+1个r进制数。,队列队列的定义和主要操作队列的顺序存储,内容提要：队列是一种操作受限制的线性表队列的特性：先进先出队列的顺序存储,队列队列的定义：队列是插入在一端进行而删除在其另一端进行的线性表。并按先进向出(FIFO)的原则进行操作。能进行删除的一端称为队首(front)，能进行插入操作的一端称为队尾(rear)。,a1,队尾,队头,入队,出队,an,出队入队队首(front)队尾(rear)与栈类似，队列的封闭性也非常好栈能对输入序列部分或全局起求逆作用队列对输入序列起缓冲作用，队列的应用非常广泛,e0,e1,en-2,en-1,队列的特性：先进先出性。,队列的基本操作：,QInsert(item):向队尾添加元素（入队）；QDelete():删除队首元素（出队）；QFront():获取队首的元素值；IsFull():判断队列是否为满；IsEmpty():判断队列是否为空；,队列的顺序存储使用数组存储队列中元素constintMaxQSize=50;TemplateClassQueueprivateTqlistMaxQSize;/存放队列元素的数组：intfront;/队首所在数组元素的下标intrear;/队尾所在数组元素的下标加1得到的值intcount;/队列中元素的个数,public:Queue(void);/初始化数据成员voidQinsert(constT,队列的指针的规定front永远指向队首元素。rear永远指向队尾元素的下一地址。,例等待处理某作业进队、出队情况。,rear=1,a0进队,front=0,rear=0,初始状态,a0,a1,a2,a1a2进队,rear=2,rear=3,插入:rear=rear+1删除元素的方法1：令front=front+1,front=0,a0,a1,a2,rear=3,front=1,演示,rear=n,无法利用的空间,x,a2,删除的方法2:令元素向前移动,front总等于0插入:rear=rear+1,a1,0,1,2,Maxsize-1,a0出队,front=0,rear=2,a0,删除:raer=raer-1,rear=1,所有元素的地址都必须改变，效率低下,front=n-3,an-3,an-2,0,1,2,Maxsize-1,rear=n-1,循环队列:很好的解决了(1)(2)中存在的问题。,n-3,rear=n-1,an-1,rear=0,删除队首元素的方法3：循环队列,front顺时针移动一位,rear=n-1,front=n-2,an-2,0,1,2,Maxsize-1,rear=n-1,删除队首元素的方法3：循环队列,front=n-1,an-3,an-2,0,1,2,Maxsize-1,rear=2,x,删除元素x：,n-3,an-3,rear=2,an-2,0,.,1,n-1,.,.,.,front=n-1,n-2,x,front顺时针移动一位,front=0,front=0,采用环状模型来实现队列,各数据成员的意义如下：front指定队首位置，删除一个元素就将front顺时针移动一位；rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；队空、队满？count存放队列中元素的个数。队空：count=0队满：count=MaxQSize,删除队首元素：front顺时针移动一位情况1：,A,B,B,删除A,front=(front+1)MODMaxQSize;,MaxQSize=10,9,8,7,删除队首元素：front顺时针移动一位情况2,rear,0,front=9,D,rear,front=0,删除C,front=(front+1)MODMaxQSize;,MaxQSize=10,9,D,(9+1)MOD10=0,rear,0,B,B,rear,插入C,rear=(rear+1)MODMaxQSize;,插入一个元素：rear顺时针移动一位情况2,8,9,8,9,将元素item插入队尾算法QInsert(item)QI1队列已满？IFcount=MaxQSizeTHEN(PRINT“Queueoverflow!”.RETURN.).QI2插入countcount+1.qlistrearitem.rearMOD(rear+1,MaxQSize),删除队首元素算法QDelete(.temp)/用temp来保存被删除元素QD1队列为空?IFcount=0THEN(PRINT“DELETINGFROMANEMPTYQUEUE!”.RETURN.).QD2删除tempqlistfront.countcount1.frontMOD(front+1,MaxQSize),队列空的条件：count=0队列满的条件：count=MaxQSize,队列的链接存储链式队列的结构：(a1,a2,an),1、Queue类的说明(利用LinkedList)由于链表类LinkedList与队列对应的操作几乎是相同的，所以利用链表类可以直接实现链接存储的队列。,#includelink.htemplateclassQueueprivate:/存放队列元素的链表LinkedListqueueList;public:voidQInsert(constT,(1)向队尾插入元素elttemplatevoidQueue:QInsert(constT,删除并返回队首元素值templateTQueue:QDelete(void)if(queueList.ListEmpty()exit(1);queueList.Next();returnqueueList.DeleteFront();,存取队首元素值templateTQueue:QFront(void)constif(queueList.ListEmpty()exit(1);/指针指回队首并返回队首元素值queueList.Reset();ReturnqueueList.Data();,小结：队列是一种操作受限制的线性表操作只和队头、队尾有关队列的特性：先进先出队列的状态队列空：count=0队列满：count=MaxQSize,栈的应用算术表达式求值,表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。,表达式都是由操作数（operand）运算符（operator）界限符（delimiter）组成的。其中操作数可以是常数，也可以是变量或常量的标识符；运算符是算术运算符（+,-,*,/）；界限符为左右括号和标识表达式结束的结束,算术表达式的表示方法1.中缀表达式运算符在操作数之间如：A*B/C运算规则：(1)先计算括号内，后计算括号外；(2)在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级；(3)同一优先级运算，从左向右依次进行。,用计算机来处理中缀表达式比较复杂。一个中缀表达式中有多少个运算符，原则上就得对表达式扫描多少遍，才能完成计算。在编译系统中，把中缀表达式转换成另外一种表示方法，即后缀表达式，然后对后缀式表达式进行处理，后缀表达式也称为逆波兰式。,2.后缀表达式：1929年，由波兰逻辑学家（Lukasiewicz）提出。例A*B/C;AB*C/;定义：运算符紧跟在两个操作数之后的表达式叫后缀表达式。优点：后缀表达式没有括号不存在优先级的差别计算过程完全按照运算符出现的先后次序进行,中缀表达式后缀表达式a+bab+a+b*cabc*+a*b*c+c*d(a+b)*(c-d)*e+f),ab*c*cd*+,ab+cde*f+*,D,方法:（1）把表达式充分加括号，最后归结为每一个括号里仅有一种运算；（2）移动运算符使之取代与之对应的右括号；（3）去掉所有括号。,中缀表达式转后缀表达式(堆栈的应用)首先设定一个运算符栈，用来保存扫描中缀表达式得到的暂不能放入后缀表达式中的运算符。基本思想：从左到右依次读出中缀表达式中的各个符号（操作数或运算符），每读出一个符号后，根据如下运算规则进行处理：1.假如是操作数，将其放入后缀表达式中；2.如果是运算符，则：（1）栈空：运算符放入栈中，（2）栈不空：比较当前读到的运算符与栈顶运算符的优先级,1）假如读出的运算符的优先级大于栈顶运算符的优先级，则将其压入运算符栈，读中缀表达式的下一个符号。2）若栈顶运算符的