第8章第8章　结构体、共用体及枚举类型.ppt

Invalid choice Enter your choice: 1. to push a value into stack 2. to pop a value from stack 3. to end program ? 3 ↙  End of run 8.2.4 队列 　　队列也是一种受限的链表，即对它增加新结点时只能在其尾部进行，对它删除结点时只能在头部进行，因而它是一种“先进先出(First In First Out, 即FIFO)”的数据结构。在队列中插入和删除结点的操作分别称为“入队(enqueue)”和“出队(dequeue)”操作。因此对队列的操作需要两个指针，一个指向队列头部(headp)，另一个指向队列尾部(tailp)。图8-20的队列中箭头的指向就是从头部指向尾部。 图 8 - 20 队列的结构 　　1. 队列的类型定义 　　队列的类型定义如下： struct queuenode { int data; struct queuenode *next; }; typedef struct queuenode Qnode; typedef Qnode * Qnodep; 　　2. 入队和出队函数的定义 　　入队和出队操作都涉及对指针值的改变，因此函数中采用传引用调用方法，函数的形参定义为二级指针，实参为指针的地址。　 　　(1) 入队函数enqueue： void enqueue(Qnodep *headp, Qnodep *tailp, int value) { Qnodep newp; newp=(Qnodep) malloc(sizeof(Qnode)); if(newp!=NULL) {newp-data=value; newp-next=NULL; if(*headp==NULL)*headp=newp; else (*tailp)-next=newp; *tailp=newp; } esle printf(″%d not inserted. No memory available.＼n″, value); } 　　函数enqueue从主调函数中接收三个参数：指向队列头部的指针的地址，指向队列尾部的指针的地址以及要插入到队列中的值。入队操作主要有以下六个步骤： 　　① 建立一个新结点，调用malloc函数开辟内存空间，把新结点的地址赋给newp。 　　② 把要插入队列中的数值赋给结点的数值域newp-data。 　　③ 对新结点的指针域赋以NULL值(这对插入的每个结点都要进行，因为新结点插在队尾，而队尾的指针域必须是NULL)。 　　④ 如果原队列为空，则新结点应为队列中的惟一结点，指向队列头的指针也必须指向它，即把newp赋给*headp。 　　⑤ 如果原队列不空，则不涉及队列头指针，只对队尾指针进行操作就可以了，即把newp赋给(*tailp)-next, 则新结点就加入队尾了。 　　⑥ 使队尾指针指向新结点，即把newp赋给*tailp。 　　入队操作的示意图如图8 - 21所示。 图 8 - 21 入队操作的过程 　　(2) 出队函数dequeue： int dequeue(Qnodep *headp, Qnodep *tailp) { int value; Qnodep temp; value=(*headp)-data; temp=*headp; *headp=(*headp)-next; /* 摘除队列头结点 */ if(*headp==NULL) *tailp=NULL; /* 队列中无结点 */ free(temp); return value; } 　　函数dequeue从主调函数中接收两个参数：指向队列头部的指针的地址和指向队列尾部的指针的地址。出队操作过程有以下六个步骤： 　　① 把队头结点的值保存起来，即把(*headp)-data赋给变量value。 　　② 用temp指向要被释放的内存，即把*headp赋给temp。 　　③ 调整队头指针，使它指向下一个结点，即把*headp-next赋给*headp。 　　④ 如果队头指针为NULL，说明队列中无结点，则队尾指针也应该是NULL。 　　⑤ 释放temp所指向的内存空间。 　　⑥ 把value的值返回调用者。 　　出队操作的示意图如图8 - 22所示。 图 8 - 22 出队操作的过程 　　在主调函数中，可以定义指向队列头和指向队列尾的指针并赋初值：