鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)細(xì)節(jié)與運(yùn)行機(jī)制

1、鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)細(xì)節(jié)與運(yùn)行機(jī)制【實(shí)現(xiàn)方法】數(shù)據(jù)結(jié)構(gòu)：隊(duì)列要求只能從對(duì)尾進(jìn)從對(duì)頭出，對(duì)頭不動(dòng)typedef struct tQueueNode 隊(duì)列結(jié)構(gòu)pBITREE ptree;/存儲(chǔ)樹節(jié)點(diǎn)指針tQueueNode* next;QueueNode,*pQueueNode;typedef struct tQueuepQueueNode rear; /隊(duì)尾pQueueNode head;對(duì)頭LinkListQue;幾個(gè)基本的重要函數(shù)Status InitQue(LinkListQue &que) 隊(duì)頭和隊(duì)尾地址相同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é)點(diǎn)入隊(duì)Status ENQue(LinkListQue &que,pBITREE pNode) pQueueNode p = (pQueueNode)malloc(sizeof(QueueNode);if(p = NULL)return ERROR;對(duì)p進(jìn)行初始化p-next

3、= NULL;p-ptree = NULL;/入隊(duì)que.rear-ptree = pNode;que.rear-next = p;que.rear = p;return OK;/將節(jié)點(diǎn)從頭部出隊(duì)pQueueNode DeQue(LinkListQue &que)if(que.head = que.rear)return NULL; 空隊(duì)列，無法出隊(duì)pQueueNode q;q = que.head;que.head = q-next;return q;從這段代碼中，我們很難看出鏈表隊(duì)列各個(gè)節(jié)點(diǎn)是如何聯(lián)系起來的，現(xiàn)在我用debug工具追蹤它運(yùn)彳丁的每一步：(初始化省去)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):這是測(cè)試調(diào)用，我設(shè)斷點(diǎn)單步追蹤Status ENQue(LinkListQue &que,pBITREE pNode)pQueueNode p = (pQueueNodeJmalloctsizeofCQueueNode); iF(p = NULL) ret

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

6、它始終是 一個(gè)空節(jié)點(diǎn)，始終指向鏈表head的尾節(jié)點(diǎn)，如此說來就是，這個(gè)隊(duì)列只是一個(gè)空殼，一個(gè) 控制器，負(fù)責(zé)控制head這個(gè)單鏈表而已。讓我們繼續(xù)，看看如何出隊(duì)。return NULL; 773IpQueueNode q;q = que.head;0 que.head = q-next;return q;此時(shí)追蹤結(jié)果為:再運(yùn)行一步的結(jié)果為：即將q的next指針賦給que.head，因?yàn)槲覀円獙㈩^指針指向的地址 取出來，讓它本來指針的下一個(gè)節(jié)點(diǎn)指針變成新的head從此時(shí)可以看到，存儲(chǔ)a的節(jié)點(diǎn)出隊(duì)，尾節(jié)點(diǎn)不變，首節(jié)點(diǎn)指向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;看看測(cè)試結(jié)果:a即為出隊(duì)的數(shù)據(jù)【總結(jié)】1，隊(duì)列其實(shí)就是一個(gè)鏈表，之所以是隊(duì)列，是因?yàn)殛?duì)列對(duì)鏈表實(shí)施入隊(duì)時(shí)只能操作隊(duì)尾， 出隊(duì)時(shí)只能操作隊(duì)首的規(guī)則。2，在為空隊(duì)列的時(shí)候，加入一個(gè)節(jié)點(diǎn)，先將首節(jié)點(diǎn)指向它（通過que.rear-next = p;），尾 節(jié)點(diǎn)指向p，這就實(shí)現(xiàn)了首節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向rear節(jié)點(diǎn)的操作。如果再加入一個(gè)節(jié) 點(diǎn)，那么首節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)指向rear。故：rear節(jié)點(diǎn)起到一個(gè)裝載工得作用3，出隊(duì)就是將首節(jié)點(diǎn)賦給