数据结构3.2栈与队列(双栈和循环队列).ppt
栈与队列,第10次课 栈与队列,主要内容链式结构复习(单链表,循环链表,链栈)双栈结构的实现(程序示例)循环队列复习运动会比赛安排(链队实现),1、双栈结构,为同时出现的两个栈共同开辟一存储空间，两个栈的栈底设于存储空间的两端,优点:两栈互补余缺充分利用存储空间。,双栈的存储结构定义,typedef struct ElemType*elem；/待分配存储空间 int top1；/队头指针 int top2;/队尾指针 DStack；,双栈操作,栈初始化 InitDStack(DStack&ds)入栈 PushDStack(DStack&ds,ElemType elem,int iFlag)出栈 OutDStack(DStack&ds,ElemType&elem,int iFlag)判栈空 IsEmpty(Dstack ds,int iflag)判栈满 IsFull(DStack ds)销毁栈 DestroyDStack(Dstack&ds),2、循环队列复习,队列的顺序存储结构 typedef struct ElemType*elem；/待分配存储空间 int front；/队头指针 int rear;/队尾指针 SeqQueue；,a1,sq.front,sq.rear,a2,a3,a4,a5,sq.elem,存储空间,循环队列操作,sq.front,InitQueue(SeqQueue,InQueue(SeqQueue&sq,ElemType e),InitQueue(SeqQueue&sq),OutQueue(SeqQueue&sq,ElemType&e),Destroy(SeqQueue&sq),循环队列操作,InQueue(SeqQueue&sq,ElemType e),InitQueue(SeqQueue&sq),OutQueue(SeqQueue&sq,ElemType&e),Destroy(SeqQueue&sq),循环队列操作,sq.front,InQueue(SeqQueue&sq,ElemType e),InitQueue(SeqQueue&sq),OutQueue(SeqQueue&sq,ElemType&e),Destroy(SeqQueue&sq),InQueue(SeqQueue,循环队列操作,InQueue(SeqQueue&sq,ElemType e),InitQueue(SeqQueue&sq),OutQueue(SeqQueue&sq,ElemType&e),Destroy(SeqQueue&sq),OutQueue(SeqQueue sq.front=(sq.front+1)%MAXSIZE；,0,1,2,3,4,5,6,7,a1,a2,a3,a4,a5,sq.rear,a6,a7,sq.front,3、链队实现,空队列,存储结构定义,typedef struct QNode/结点类型 QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct/链队列类型 QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;,初始化操作,Status InitQueue(LinkQueue,空队列,入队操作,Status EnQueue(LinkQueue,出队操作,Status DeQueue(LinkQueue,if(Q.rear=p)Q.rear=Q.front;,应用：运动会比赛安排,某运动会设立 N 个比赛项目，每个运动员可以参加一至三个项目。试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程最短。分析：若将此问题抽象成数学模型，则归属于“划分子集”问题。N 个比赛项目构成一个大小为 n 的集合，有同一运动员参加的项目则抽象为“冲突”关系。,例如：某运动会设有 9 个项目:A=0，1，2，3，4，5，6，7，8，七名运动员报名参加的项目分别为：（1，4，8）、（1，7）、（8，3）、（1，0，5）、（3，4）、（5，6，2）、（6，4）它们之间的冲突关系为:R=（1，4）,（4，8）,（1，8）,（1，7）,（8，3）,（1，0）,（0，5）,（1，5）,（3，4）,（5，6）,（5，2）,（6，2）,（6，4）,“划分子集”问题,将集合A划分成k个互不相交的子集 A1，A2，Ak（kn），使同一子集中的元素均无冲突关系，并要求划分的子集数目尽可能地少。对前述例子而言，问题即为:同一子集的项目为可以同时进行的项目，显然希望运动会的日程尽可能短。,求解方法：,可利用“过筛”的方法来解决划分子集问题。从第一个元素考虑起，凡不和第一个元素发生冲突的元素都可以和它分在同一子集中，然后再“过筛”出一批互不冲突的元素为第二个子集，依次类推，直至所有元素都进入某个子集为止。问题：冲突关系的正确表示？,组号=0;全体元素入队列;while(队列不空)队头元素i出队列入组;while(jQueueLen)队头元素j出队列 if(j和组中元素都不冲突)j入组 else j重新入队列;/while 组号+；,划分子集算法的基本思想:,
