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

第二章线性表、堆栈和队列线性表、堆栈和队列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的后继结点；当时，表中没有结点（包含零个结点），这样的线性表被称为空表。线性表记为(a0,a1,…,an-1)n≠0()n=0线性表的操作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个结点的线性表A[4]在内存中的表示，其中每个结点占2个连续的字节，第一个结点A[0]的首地址为302图4.1线性表的顺序存储线性表A[2]308306304302A[0]A[1]A[3]Loc(a[k])=Loc(a[0])+k*ca0a1an-1akb+cb+k*cbb+(n-1)*c……01n-1k空闲区起始存储位置：b每个元素大小：c求第k个元素的开始位置？线性表上实现的基本运算1、插入[例]在线性表(12,13,21,24,28,30,42,77)中下标为3的结点后，插入元素25。序号元素230416751213212428304277插入25序号元素230416751213252124283042778在下标为k的结点后插入一个新结点//ADL描述算法Insert(A,k,x)IF(k1ORkn)THENPRINT(“overflow”).ELSE(FORi=nTOk＋1STEP-1DOA[i+1]A[i].A[k＋1]x.nn+1.)▌2、删除[例]在线性表(12,13,21,24,28,30,42,77)中删除下标为3的元素。序号元素230416751213212428304277删除24序号元素230416512132128304277删除下标为k的结点//ADL描述算法Delete(A,k)IF(k1ORkn)THENPRINT(“error”)ELSE(FORi=k+1TOnDOA[i-1]A[i].nn-1.)▌●结论：优点：线性表的顺序存储结构简单、易于实现，可以随机访问表中任一元素。缺点：线性表的容量不容易扩充；插入、删除麻烦，需移动元素。线性表、堆栈和队列2.1线性表的定义和基本操作2.2线性表的顺序存储结构2.3线性表的链接存储结构1、单链表的定义●链式存储：用一组任意存储单元存储线性表的数据元素。单链表的结点结构：链表的第一个结点被称为头结点，指向头结点的指针被称为头指针。链表的最后一个结点被称为尾结点。●单链表的定义：每个结点只含有一个指针域的链表叫单链表。datanexta5a3a4∧●特点：逻辑顺序与物理顺序可以相同也可以不同。●优点：①插入、删除方便。②合理利用空间。[例]将线性表(a3，a4，a5)以链表的形式存储在内存中。(a3，a4，a5)a5500a3100002a4002500∧●删除当前节点的后继节点：算法Delete(this.tempptr)/*删除当前结点的后继结点，并令指针tempptr指向被删除结点*/IFnext（this）=NULLTHENtempptrNULLELSE（tempptrnext（this）.next（this）next（tempptr））.▐×…FATHAT…thisGATtempptr在当前结点之后插入结点p//ADL描述算法InsertAfter(this，p)IA1[将当前结点的next域值赋给P的next域]next(p)next(this).IA2[将P赋给当前结点的next域]next(this)p▌…FATHAT…thisGATp×在头指针为head的链表中，插入一个data域为item的新结点作为该链表的表头结点。算法InsertFront(head，item)IF1[调用函数GetNode]GetNode(item,head.newNode).IF2[head指向新结点]headnewNode.▌HATGAT∧itemnewNodeheadhead所谓遍历一个结构，是指按一定的次序访问结构中的所有结点，且每个结点恰被访问一次。遍历链表，就是按一定次序访问链表的所有结点。要想遍历整个链表，必须从头指针开始。遍历链表遍历链表演示算法PrintList(head)//输出头指针为head的链表,每输出5个元素换行PL1[取表头，计数器初始化]currptrhead.count0.acbhead∧currptrPL2[遍历并输出链表结点的data值]WHILE(currptr≠NULL)DO(PRINT(data(currptr)).countcount+1.if(countmod5)=0PRINT(ENTER).currptrnext(currptr).)▌acbheadcurrptr∧abc操作:遍历插入InsertFrontInsertRearInsertAtInsertAfeter删除……从一个结点出发，只能访问到链接在它后面的结点，而无法访问位于它前面的结点。链接结构“循环化”，即令表尾结点的next域存放指向表头结点的指针，而不是存放空指针NULL，这样的链表被称为循环链表。acbhead∧循环链表1循环链表的定义和结构定义：在单链表中，使其最后一个结点的指针又指回到第一个结点，则这样的链表叫循环链表循环链表表头：哨位节点（数据为空，指向第一个数据项）xnx1…L●注意：判断表尾的条件：第一个节点判断空表的条件：xnx1…pHeaderHeaderp-next==NULLp-next==headerHead==NULLHeader-next＝＝Header双向循环链表1问题的提出：找一个结点的前趋结点2双向循环链表的结构★链表的结构leftdataright。。。L★结点结构：Header→left==Header→right==Headerp-right-left=p-left-right=p循环双链表判空的条件：★双链表的对称性：★Header在当前结点(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)Pp4321this在当前结点(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▌左插入演示p2134left(P)left(this)thisright(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ＦＯ)的原则进行操作。a5a3a2a1a4进栈出栈栈顶栈底[例]有一线性表(a1,a2,…,a5)空栈栈顶栈底a5a3a2a1a4入栈顺序e0e1e2…en-2en-1出栈顺序en-1en-2…e2e1e0栈可以对序列实现求逆en-1e0e1en-2…进栈(Push)出栈(Pop)栈顶top栈底●栈的特性：后进先出性。举例栈的封闭性：在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好，使用起来非常安全。堆栈的基本操作：push(item):压入一个元素（插入）；pop(item):弹出一个元素（删除）；peek(item):存取栈顶元素值；clear():清空栈；IsEmpty():判断栈是否为空；堆栈的顺序存储使用数组存放栈元素，栈的规模必须小于或等于数组的规模，当栈的规模等于数组的规模时，就不能再向栈中插入元素。堆栈的类定义与实现类Stack中所涉及到的数据成员：//存放堆栈元素的数组：Tstacklist[MaxStackSize];//栈顶所在数组元素的下标：inttop;●使