2019数据结构C++第3章第7讲.pptxVIP

上节课重点内容：双向链表的插入删除使用静态链表实现循环链表栈的操作练习：用循环链表求解约瑟夫问题约瑟夫问题的提法（完整程序）n 个人围成一个圆圈，首先第 1 个人从 1 开始，一个人一个人顺时针报数, 报到第 m 个人，令其出列。然后再从下一 个人开始，从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。用不带表头结点的循环链表来组织。lLink data rLink前驱方向 ? ? 后继方向双向链表 (Doubly Linked List)双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。双向链表每个结点结构： 双向链表通常采用带表头结点的循环链表形式。firstfirstrLinklLinkp-lLinkpp-rLink非空表 空表结点指向p == p-lLink-rLink == p-rLink-lLinkfirst314815current后插入25firsewNodecurrent双向循环链表的插入算法 (非空表)newNode-rLink = current-rLink; current-rLink = newNode;newNode-rLink-lLink = newNode;newNode-lLink = current;双向循环链表的插入算法 (空表)firstfirst25后插入25newNodecurrentcurrentnewNode-rLink = current-rLink (newNode-rLink = first); current-rLink = newNode;newNode-rLink -lLink = newNode; ( first-lLink = newNode ) newNode-lLink = current;双向循环链表的删除算法非空表first314815删除48currentfirst3115currentcurrent-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink;a1a2a3a4a5firstΛ静态链表的结构012345dataa3a4a1a5a2link3245-1(0)10号是表头结点，link给出首元结点地址。循环链表收尾时link = 0，回到表头结点。如果不是循环链表，收尾结点指针link = -1。link指针是数组下标，因此是整数。数据结构电子教案第三章 栈与队列栈 ( Stack )只允许在一端插入和删除的线性表允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom)特点 后进先出 (LIFO)退栈进栈topan-1an-2?a0bottom顺序栈的操作template class Evoid SeqStackE::overflowProcess() {//私有函数：当栈满则执行扩充栈存储空间处理 E *newArray = new E[2*maxSize];//创建更大的存储数组 for (int i = 0; i = top; i++) newArray[i] = elements[i]; maxSize += maxSize; delete [ ]elements; elements = newArray;//改变elements指针}; template class Evoid SeqStackE::Push(E x) {//若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理 if (IsFull() == true) overflowProcess;//栈满 elements[++top] = x; //栈顶指针先加1, 再进栈}; template class Ebool SeqStackE::Pop(E x) {//函数退出栈顶元素并返回栈顶元素的值 if (IsEmpty() == true) return false; x = elements[top--];//栈顶指针退1 return true;//退栈成功}; template class Ebool SeqstackE::getTop(E x) {//若栈不空则函数返回该栈栈顶元素的地址 if (IsEmpty() == true) return false; x = elements[top]; return true;};栈的链接存储表示 — 链式栈top链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作Data nextSan栈顶an-1a1栈底栈的链式存储和实现栈的链式存