鏈式隊列的實現(xiàn)細節(jié)與運行機制

1、鏈式隊列的實現(xiàn)細節(jié)與運行機制【實現(xiàn)方法】數(shù)據(jù)結(jié)構(gòu)：隊列要求只能從對尾進從對頭出，對頭不動typedef struct tQueueNode 隊列結(jié)構(gòu)pBITREE ptree;/存儲樹節(jié)點指針tQueueNode* next;QueueNode,*pQueueNode;typedef struct tQueuepQueueNode rear; /隊尾pQueueNode head;對頭LinkListQue;幾個基本的重要函數(shù)Status InitQue(LinkListQue &que) 隊頭和隊尾地址相同que.rear = que.head = (pQueueNode)malloc(si

2、zeof(QueueNode);if(que.rear=NULL II que.head=NULL) return ERROR;que.head-next = NULL;que.head-ptree = NULL;que.rear-next = NULL;que.rear-ptree = NULL;return OK;節(jié)點入隊Status ENQue(LinkListQue &que,pBITREE pNode) pQueueNode p = (pQueueNode)malloc(sizeof(QueueNode);if(p = NULL)return ERROR;對p進行初始化p-next

3、= NULL;p-ptree = NULL;/入隊que.rear-ptree = pNode;que.rear-next = p;que.rear = p;return OK;/將節(jié)點從頭部出隊pQueueNode DeQue(LinkListQue &que)if(que.head = que.rear)return NULL; 空隊列，無法出隊pQueueNode q;q = que.head;que.head = q-next;return q;從這段代碼中，我們很難看出鏈表隊列各個節(jié)點是如何聯(lián)系起來的，現(xiàn)在我用debug工具追蹤它運彳丁的每一步：(初始化省去)int main()Li

4、nkListQue listQue;pBITREE tree;InitBiTree(tree,a);pBITREE treel;InitBiTree(tree1,b);InitQue(listQue);ENQue(listQue,tree);ENQue(listQue,tree1);DDueueNode 口 = DMuef listDue):這是測試調(diào)用，我設(shè)斷點單步追蹤Status ENQue(LinkListQue &que,pBITREE pNode)pQueueNode p = (pQueueNodeJmalloctsizeofCQueueNode); iF(p = NULL) ret

5、urn ERROR;剛進入入隊函數(shù)時，鏈表隊列的首尾指針的地址值為均為：0 x020a38d0也就是說，他們指向的是同一個地址當(dāng)尾節(jié)點插入下一個節(jié)點時，首尾指針?biāo)赶虻牡刂肪鶠椋? x020a3908用一也就是說，不僅首尾指針?biāo)赶蛲坏刂?，連他們的下一個節(jié)點同樣指向同一個地址， 副圖來說就是：Rear和head完全相同再運行一步：此時p被賦給que.rear，會發(fā)生什么變化呢?并運從紅色地址可以看到，rear的地址變?yōu)榕chead-next的地址，同樣，在調(diào)用這個函數(shù)， 行到這里的時候，我們再看看追蹤結(jié)果：此時我們可以看到，鏈表隊列的尾指針rear指向的是head-next-next，也就是說

6、它始終是 一個空節(jié)點，始終指向鏈表head的尾節(jié)點，如此說來就是，這個隊列只是一個空殼，一個 控制器，負責(zé)控制head這個單鏈表而已。讓我們繼續(xù)，看看如何出隊。return NULL; 773IpQueueNode q;q = que.head;0 que.head = q-next;return q;此時追蹤結(jié)果為:再運行一步的結(jié)果為：即將q的next指針賦給que.head，因為我們要將頭指針指向的地址 取出來，讓它本來指針的下一個節(jié)點指針變成新的head從此時可以看到，存儲a的節(jié)點出隊，尾節(jié)點不變，首節(jié)點指向bInitQue(listQue);ENQue(listQue.tree);EN

7、Que(listQue,tree1);pQueueNode q = DeQue(listQue);iF(q *= NULL)printF(cn,q-ptree-data)free(q)；return O;看看測試結(jié)果:a即為出隊的數(shù)據(jù)【總結(jié)】1，隊列其實就是一個鏈表，之所以是隊列，是因為隊列對鏈表實施入隊時只能操作隊尾， 出隊時只能操作隊首的規(guī)則。2，在為空隊列的時候，加入一個節(jié)點，先將首節(jié)點指向它（通過que.rear-next = p;），尾 節(jié)點指向p，這就實現(xiàn)了首節(jié)點的下一個節(jié)點指向rear節(jié)點的操作。如果再加入一個節(jié) 點，那么首節(jié)點的最后一個節(jié)點指向rear。故：rear節(jié)點起到一個裝載工得作用3，出隊就是將首節(jié)點賦給