數(shù)據(jù)結(jié)構(gòu)教程--第3章++棧與隊列...ppt

1、第3章 棧與隊列,數(shù)據(jù)結(jié)構(gòu),3.1 棧（stack）,3.3.1 棧的定義 定義：限定僅在表尾進行插入或刪除操作的線性表，表尾棧頂，表頭棧底，不含元素的空表稱空棧。 特點：先進后出（FILO）或后進先出（LIFO）,棧的基本操作 1）初始化Init一個空棧S； 2）判斷棧S是否空Empty； 3）取棧頂元素Gettop； 4）進棧操作Push； 5）出棧操作Pop；,3.1.2 棧的基本運算,入棧操作為S，出棧操作為X 輸入序列為 1 2 3 4 5 6 7 輸出序列為4 5 1 3 2 7 6 4 3 5 2 1 6 7 3 2 5 4 7 6 1 2 3 1 4 7 6 5 6 7 1 2

2、 5 4 3 5 3 6 7 1 2 4 4 2 1 6 3 7 5 5 4 6 7 3 2 1 7 6 5 4 3 2 1,Stack s; char x,y; main() x=c; y=k; s=Init(); Push(s,x); Push(s,a); Push(s,y); x=Pop(s); Push(s,t); Push(s,x); x=Pop(s); Push(s,s); while (!Empty(s) printf(“%c”, Pop(s); printf(“%cn”,x); ,3.1.2 順序棧 實現(xiàn)：一維數(shù)組sM,棧頂指針top,指向?qū)嶋H棧頂 后的空位置，初值為-1,進棧

3、,A,出棧,棧滿,B,C,D,E,F,設(shè)數(shù)組維數(shù)為M top=-1,棧空，此時出棧，則下溢（underflow) top=M-1,棧滿，此時入棧，則上溢（overflow),?？?棧的順序存儲結(jié)構(gòu)的C語言描述如下： /*/ /* 棧的順序存儲 */ /*/ #define MAXSIZE 100 typedef int datatype; typedef struct datatype dataMAXSIZE; int top ; SeqStack;,棧頂位置,下面是順序存儲棧的幾個基本操作的具體實現(xiàn),/*/ /* 棧（順序存儲）初始化 */ /* 函數(shù)名Init() */ /*/,void

4、Init(SeqStack *s) s-top=-1; ,SeqStack Init() SeqStack s; s.top=-1; return s; ,/*/ /* 判斷棧（順序存儲）是否為空 */ /* 函數(shù)名Empty () */ /* 參數(shù)為SeqStack型變量s */ /* 返回值為整型，如果棧為空，返回1，否則返回0 */ /*/,int Empty(SeqStack s) if (s.top=-1) return(1); else return (0); ,/*/ /* 取得棧頂（順序存儲）結(jié)點值 */ /* 函數(shù)名Gettop() */ /*/,datatype Getto

5、p(SeqStack s) if (Empty(s) printf(n棧是空的!);exit(1); else return s.datas.top; ,/ / 函數(shù)功能:棧（順序存儲）的插入（進棧）操作 / / 函數(shù)參數(shù):指向SeqStack型變量的指針變量s / / datatype型變量x / / 函數(shù)返回值:空 / / 函數(shù)名:Push() / /,void Push(SeqStack s, datatype x) if(s-top=MAXSIZE-1) printf(nThe sequence stack is full!);exit(1); s-top+; s-datas-top=

6、x; ,/ / 函數(shù)功能:棧（順序存儲）的刪除（出棧）操作 / / 函數(shù)參數(shù):指向SeqStack型變量的指針變量s / / 函數(shù)返回值:datatype類型 / / 函數(shù)名Pop() / /,datatype Pop(SeqStack s) if(s-top=-1) printf(nThe sequence stack is empty!);exit(1); else s-top-; return s-datas.top+1; ,鏈棧,棧的鏈式存儲稱為鏈棧。鏈棧就是一個特殊的單鏈表，對于這特殊的單鏈表，它的插入和刪除規(guī)定在單鏈表的同一端進行。鏈棧的棧頂指針一般用top表示。,typedef

7、struct node int data; struct node *next; StackNode，*LinkStack; LinkStack top;,鏈棧結(jié)點的C語言定義,/ / 函數(shù)功能:建立一個空的鏈式棧 / / 函數(shù)參數(shù):無 / / 函數(shù)返回值:LinkStack類型的變量 / / 函數(shù)名:init() / / LinkStack init( ) return NULL; ,1 建立一個空的鏈式棧,/ / 函數(shù)功能:判斷鏈棧是否為空 / / 函數(shù)參數(shù):LinkStack類型變量top / / 函數(shù)返回值:int類型的變量 / / 函數(shù)名:Empty() / / int Empty(

8、LinkStack top) return (top? 0:1); ,2 判斷鏈棧是否為空,/ / 函數(shù)功能:讀鏈棧的棧頂結(jié)點值 / / 函數(shù)參數(shù): LinkStack類型變量top / / 函數(shù)返回值:datatype類型的變量 / / 函數(shù)名:Gettop() / / datatype Gettop(LinkStack top) ,3 取得鏈棧的棧頂結(jié)點值,return(top-data);,if(!top) printf(n鏈式棧是空的!);exit(1);,/ / 函數(shù)功能:輸出鏈棧中各個結(jié)點的值 / / 函數(shù)參數(shù):LinkStack類型變量top / / 函數(shù)返回值:空 / / 函數(shù)

9、名:print() / / void print(LinkStack top) StackNode p; p=top; ,4 輸出鏈棧中各結(jié)點的值,while(p) printf(%5d,p-data); p=p-next;,if(!p) printf(n鏈式棧是空的!);,top,p,(1) p-next=top;,鏈棧插入操作,鏈棧進棧操作,(1),x,top,p,(2),(1) p-next=top;,鏈棧插入操作,鏈棧進棧操作,(2) top=p;,LinkStack Push(StackNode top,datatype x) StackNode p; /分配空間/ /設(shè)置新結(jié)點的值

10、/ /插入（1）/ /插入（2）/ return top; ,5 向鏈棧插入值為x的結(jié)點(進棧),p=(StackNode)malloc(sizeof(StackNode);,p-data=x;,p-next=top;,top=p;,/ / 函數(shù)功能:向鏈棧插入值為x的結(jié)點(進棧) / / 函數(shù)參數(shù):LinkStac類型變量top / / 函數(shù)返回值:LinkStack類型變量 / / 函數(shù)名:Push() / /,top,(1) q=top;,鏈棧刪除操作,(1),鏈棧出棧操作,top,(1) q=top;,鏈棧刪除操作,q,(1),鏈棧出棧操作,(2) top=top-next;,(3)

11、free(q),top,(1) q=top;,鏈棧刪除操作,鏈棧出棧操作,(2) top=top-next;,(3) free(q),LinkStack Pop(LinkStack top,datatype *x) StackNode q; /指向被刪除的結(jié)點（1）/ /刪除棧頂結(jié)點（2）/ return top; ,if(!top) printf(n鏈式棧是空的!);return NULL;,q=top;,top=top-next;,free(q);,6 刪除鏈棧中的棧頂結(jié)點(出棧),/ / 函數(shù)功能:刪除鏈棧中的棧頂結(jié)點(出棧) / / 函數(shù)參數(shù):LinkStack類型變量top,data

12、type型的x / / 函數(shù)返回值:LinkStack類型變量 / / 函數(shù)名:Pop() / /,*x=top-data;,3.1.3 堆棧的應(yīng)用,堆棧在函數(shù)調(diào)用中的應(yīng)用,地圖四染色問題,1,2,2,3,4,1,4,3,3,4,2,3,1# 紫色 2# 黃色 3# 紅色 4# 綠色,1 括號匹配,設(shè)一個表達式中可以包含三種括號：小括號、中括號和大括號，各種括號之間允許任意嵌套，如小括號內(nèi)可以嵌套中括號、大括號，但是不能交叉。舉例如下： ()正確的 () 正確的 ()正確的 ()不正確的 () 不正確的,如何去檢驗一個表達式的括號是否匹配呢？大家知道當自左向右掃描一個表達式時，凡是遇到的開括號

13、（或稱左括號）都期待有一個和它對應(yīng)的閉括號（或稱右括號）與之匹配。 按照括號正確匹配的規(guī)則，在自左向右掃描一個表達式時，后遇到的開括號比先遇到的開括號更加期待有一個閉括號與之匹配。,/ / 函數(shù)功能:判斷表達式括號是否匹配 / / 函數(shù)參數(shù):char類型數(shù)組c / / 函數(shù)返回值:int類型。返回1為匹配,返回0為不匹配 / / 函數(shù)名:match_kouhao() / / int match_kuohao(char c) int i=0; SeqStack s; init( while(ci!=#) switch(ci), case : case : case (:Push( /棧為空則匹配

14、,否則不匹配/ ,回文游戲：順讀與逆讀字符串一樣（不含空格）,1.讀入字符串 2.去掉空格（原串） 3.壓入棧 4.原串字符與出棧字符依次比較 若不等，非回文 若直到棧空都相等，回文,多進制輸出：,字符串：“madam im adam”,算法思想,當n0時，重復(fù)(1)、(2) 直到n=0 （1）將n%r的結(jié)果入棧 （2）n=n/r 當n=0時，將棧的元素依次出棧輸出。 這里我們可以直接調(diào)用棧的基本運算(Init， Push，Pop和Empty)來實現(xiàn)，這樣可以對算法的思路和層次理解更清楚。,typedef int datatype; void conversion(int n, int r)

15、SeqStack s; datatype x; s=Init(); while (n0) Push( ,小 結(jié) 1 棧是限定僅能在表尾一端進行插入、 刪除操作的線性表； 2 棧的元素具有后進先出的特點； 3 棧頂元素的位置由一個稱為棧頂指針的 變量指示， 進棧、出棧操作要修改棧頂指針；,課堂練習(xí),一、選擇題 1鏈棧與順序棧相比，比較明顯的優(yōu)點是()。 A. 插入操作更加方便 B. 通常不會出現(xiàn)棧滿的情況 C. 不會出現(xiàn)?？盏那闆rD. 刪除操作更加方便 2棧的插入和刪除操作在( )進行。 A棧頂 B棧底 C任意位置 D. 指定位置 3設(shè)棧的輸入序列是1，2，3，4，則( )不可能是其出棧序列。

16、A. 1，2，4，3 B. 2，1，3，4 C. 1，4，3，2 D. 4，3，1，2,課堂練習(xí),4輸入序列為ABC，可以變?yōu)镃BA時，經(jīng)過的棧操作為( )。 A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop,課堂練習(xí),二、算法設(shè)計題 1. 設(shè)用一維數(shù)組stackn表示一個堆棧，若堆棧中一個元素需占用length個數(shù)組單元(length 1)，試寫出其入棧、出棧操作的算法。 2. 設(shè)計算法能判斷一個算術(shù)表達

17、式中的圓括號配對是否正確。(提示：對表達式進行掃描，凡遇到“(”就進棧，遇到“)”就退出棧頂?shù)摹?”，表達式掃描完畢時棧若為空則圓括號配對正確。),3.2 隊列 3.2.1 隊列的定義及特點 定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表 隊尾(rear)允許插入的一端 隊頭(ront)允許刪除的一端 隊列特點：先進先出(FIFO),3.2.2 順序隊列及其實現(xiàn),隊列的順序存儲在C語言中可以用一維數(shù)組表示，為了標識隊首和隊尾，需要附設(shè)兩個指針front和rear，front指示的是隊列中最前面，即隊首結(jié)點在數(shù)組中元素的下標的前一個位置，rear指示的是隊尾結(jié)點在數(shù)組中元素

18、的下標位置，也就是說rear指示的是即將插入的結(jié)點在數(shù)組中的下標。,隊列的幾種狀態(tài) ：,隊列的基本操作 1）初始化Init一個空隊Q； 2）判斷棧Q是否空Empty； 3）取隊頭元素Gethead； 4）入隊操作InQueue； 5）出隊操作OutQueue；,隊列的基本操作,main() Queue q; char x, y; x=e; y=c; InQueue(q,h); InQueue(q,r); InQueue(q, y); x=OutQueue(q); InQueue(q,x); x=OutQueue(q); InQueue(q, a); while (!Empty(q) print

19、f(“%c”,OutQueue(q); printf(“%cn”,x); ,/ / 隊列（順序存儲）的定義 / / #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int front ; int rear ; SeqQueue;,1 順序隊列,隊頭位置,隊尾的下一位置,順序存儲隊列的幾個基本操作的具體實現(xiàn):,/ / 函數(shù)功能:隊列（順序存儲）初始化 / / 函數(shù)參數(shù):指向SeqQueue類型變量的指針變量sq / / 函數(shù)返回值:空 / / 函數(shù)名:init() / / void init(

20、SeqQueue sq) sq-front=-1; sq-rear=-1; ,/ / 函數(shù)功能:判斷隊列（順序存儲）是否為空 / / 函數(shù)參數(shù):SeqQueue類型變量sq / / 函數(shù)返回值:int類型。返回1表示空,0表示非空 / / 函數(shù)名:Empty() / / int Empty(SeqQueue sq) return (sq.front=sq.rear? 1:0); ,/ / 函數(shù)功能:打印隊列（順序存儲）的結(jié)點值 / / 函數(shù)參數(shù):SeqQueue類型變量sq / / 函數(shù)返回值:空 / / 函數(shù)名:print() / / void print(SeqQueue sq) int

21、i; if(Empty(sq) printf(n順序隊列是空的!); else for(i=sq.front+1;i=sq.rear;i+) printf(%5d,sq.ai); ,/ / 函數(shù)功能:取得隊列（順序存儲）的隊首結(jié)點值 / / 函數(shù)參數(shù):SeqQueue類型變量sq / / 函數(shù)返回值:datatype類型。返回隊首結(jié)點值 / / 函數(shù)名:Gethead() / / datatype Gethead(SeqQueue sq) if(Empty(sq) printf(n順序隊列是空的！無法獲得隊首結(jié)點值！); exit(1); return sq.datasq.front+1; ,

22、/ / 函數(shù)功能:隊列（順序存儲）的插入（進隊）操作 / / 函數(shù)參數(shù):指向SeqQueue類型變量的指針變量sq / / datatype類型的變量x / / 函數(shù)返回值:空 函數(shù)名:InQueue() / / void InQueue(SeqQueue sq, datatype x) int i; if(sq-rear=MAXSIZE-1) printf(n順序隊列是滿的!);exit(1); sq-rear+; sq-datasq-rear=x; ,/ / 函數(shù)功能:隊列（順序存儲）的刪除（出隊）操作 / / 函數(shù)參數(shù):指向SeqQueue類型變量的指針變量sq / / 函數(shù)返回值:da

23、tatype類型 / / 函數(shù)名:OutQueue() / / datatype OutQueue(SeqQueue sq) datatype x; if(sq-front=sq-rear) printf(n順序隊列是空的！不能做刪除操作!”);exit(1); sq-front+; x=sq-datasq-front; if (sq-front=sq-rear) sq-front=sq-rear=-1; return x; ,在隊列的幾種狀態(tài)圖的（e）狀態(tài)中，隊列是一種隊滿狀態(tài)，將不能再插入新的結(jié)點，而實際上數(shù)組的前部還有許多空的位置。為了充分地利用空間，可以將隊列看作一個循環(huán)隊列，在數(shù)組的

24、前部繼續(xù)作插入運算，這就是循環(huán)隊列。,2 循環(huán)隊列,/ / 循環(huán)隊列 / / #define MAXSIZE 100 typedef int datatype; typedef struct datatype aMAXSIZE; int front ; int rear ; c_SeQueue;,隊頭位置,隊尾的下一位置,在循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當頭尾指針指向向量上界（MAXSIZE-1）時，其加1操作的結(jié)果是指向向量的下界0。 這種循環(huán)意義下的加1操作可以描述為： if(rear+1=MAXSIZE) rear=0; else rear+; 利用模

25、運算可簡化為:rear=(rear+1)%MAXSIZE,給定一個大小為MAXSIZE的數(shù)組存儲一個隊列時，經(jīng)過若干次插入和刪除操作后，當隊尾指指rear=MAXSIZE時，呈現(xiàn)隊列滿的狀態(tài)，而事實上數(shù)組的前部可能還有空閑的位置。為了有效利用空間，將順序存儲的隊列想象為一個環(huán)狀，把數(shù)組中的最前和最后兩個元素看作是相鄰的，這就是循環(huán)隊列。,(b)A進隊,0,隊空,隊滿,如圖所示：由于入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過front=rear來判斷隊列“空”還是“滿”。,采用犧牲一個數(shù)組元素的空間，即若數(shù)組的大小是MAXSIZE，則

26、該數(shù)組所表示的循環(huán)隊列最多允許存儲MAXSIZE-1個結(jié)點。這樣，循環(huán)隊列滿的條件是 (rear+1)%MAXSIZE=front 循環(huán)隊列空的條件是 rear=front,解決此問題的方法至少有三種： 其一是另設(shè)一個布爾變量以匹別隊列的空和滿； 其二是少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認為隊滿（注意：rear所指的單元始終為空）； 其三是使用一個計數(shù)器記錄隊列中元素的總數(shù)（實際上是隊列長度）。,循環(huán)隊列的入隊與出隊操作的實現(xiàn) ：,/ / 函數(shù)功能:循環(huán)隊列（順序存儲）的入隊操作 / / 函數(shù)參數(shù):指向c_SeQueue類型變量的指針變量cq

27、/ / datatype類型的變量x / / 函數(shù)名: InQueue() / / void InQueue(c_SeQuence cq, datatype x) if(cq-rear+1)%MAXSIZE=cq-front) printf(n循環(huán)隊列是滿的！無法進行插入操作！); exit(1); cq-rear=(cq-rear+1)%MAXSIZE; cq-datacq-rear=x; ,循環(huán)隊列（順序存儲）的出隊操作 / / 函數(shù)功能:循環(huán)隊列（順序存儲）的出隊操作 / / 函數(shù)參數(shù):指向c_SeQuence類型變量的指針變量cq / / 函數(shù)返回值:datatype類型 / / 函數(shù)

28、名OutQueue() / / void QutQueue(c_SeQueue cq) if(cq-front=cq-rear) printf(n循環(huán)隊列是空的！無法進行刪除操作！); exit(1); cq-front=(cq-front+1)%MAXSIZE; return cq-datacq-front; ,2.1 選擇題 （1）表長為n的順序存儲的線性表，當在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均個數(shù)為（），刪除一個元素所需移動元素的平均個數(shù)為（）。 A（n1）/2BnCn+1Dn1 En/2F(n+1)/2G(n2)/2 （2）設(shè)棧S和隊列Q的初始狀

29、態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列為e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該為（）。 A6B4C3D2,（3）設(shè)棧的輸入序列為1、2、3n，若輸出序列的第一個元素為n，則第i個輸出的元素為（）。 A不確定Bni+1CiDni （4）在一個長度為n的順序表中刪除第i個元素（1=i=n）時，需向前移動（）個元素。 AniBni+1Cni1Di （5）若長度為n的線性表采用順序存儲結(jié)構(gòu)存儲，在第i個位置上插入一個新元素的時間復(fù)雜度為（）。 AO(n)BO(1)CO(n2)DO(n3),（7）隊列是一種特殊的線性

30、表，其特殊性在于（）。 A插入和刪除在表的不同位置執(zhí)行 B插入和刪除在表的兩端位置執(zhí)行 C插入和刪除分別在表的兩端執(zhí)行 D插入和刪除都在表的某一端執(zhí)行 （8）棧是一種特殊的線性表，具有（）性質(zhì)。 A先進先出B先進后出 C后進后出D順序進出,（9）順序循環(huán)隊列中（數(shù)組的大小為n），隊頭指示front指向隊列的第1個元素，隊尾指示rear指向隊列最后元素的后1個位置，則循環(huán)隊列中存放了n1個元素，即循環(huán)隊列滿的條件為（）。 A(rear+1)%n=front1B(rear+1)%n=front C(rear)%n=frontDrear+1=front （10）順序循環(huán)隊列中（數(shù)組的大小為6），隊頭

31、指示front和隊尾指示rear的值分別為3和0，當從隊列中刪除1個元素，再插入2個元素后，front和rear的值分別為（）。 A5和1B2和4C1和5D4和2,隊列的鏈式存儲稱為鏈式隊列。鏈式隊列就是一個特殊的單鏈表，對于這種特殊的單鏈表，它的插入和刪除規(guī)定在單鏈表的不同端進行。鏈式隊列的隊首和隊尾指針分別用front和rear表示。,3 鏈隊列(linked queue),鏈式隊列的結(jié)點定義和單鏈表一樣。隊列必須有隊首和隊尾指針，因此增加定義一個結(jié)構(gòu)類型，其中的兩個域分別為隊首和隊尾指針。結(jié)點定義：,typedef struct node datatype data; struct no

32、de *next; QNode;,設(shè)隊首、隊尾指針front和rear, front指向頭結(jié)點，rear指向隊尾,typedef struct QNode *front, *rear; LQueue;,LQueue init() /建立一個空的鏈式隊列/ LQueue lq; /分配空間/ /隊尾指針指向?qū)κ字羔? return lq; ,/ / 函數(shù)功能:建立一個空的鏈式隊列 / / 函數(shù)參數(shù):無 / / 函數(shù)返回值: LQueue類型 / / 函數(shù)名:init() / /,1 建立一個空的鏈式隊列,lq.front=(QNode )malloc(sizeof(QNode); lq.fron

33、t-next=NULL;,lq.rear=lq.front;,/ / 函數(shù)功能:判斷鏈式隊列是否為空 / / 函數(shù)參數(shù):LQueue類型變量lq / / 函數(shù)返回值:int類型的變量 / / 函數(shù)名:Empty() / / int Empty(LQueue lq) return (lq.front-next? 1:0); ,2 判斷鏈式隊列是否為空,/ / 函數(shù)功能:輸出鏈隊列中各個結(jié)點的值 / / 函數(shù)參數(shù):LQueue類型變量lq / / 函數(shù)返回值:空 / / 函數(shù)名:print() / / void print(LQueue lq) QNode p; p=lq.front-next;

34、,3 輸出鏈隊列中各結(jié)點的值,while(p) printf(%5d,p-data); p=p-next;,if(!p) printf(“n鏈式隊列是空的!);,/ / 函數(shù)功能:取得鏈隊列的隊首結(jié)點值 / / 函數(shù)參數(shù):LQueue類型的變量lq / / 函數(shù)返回值:datatype類型 / / 函數(shù)名:Gethead() / / datatype Gethead(LQueue lq) if(!lq.front-next) printf(n鏈式隊列是空的!);exit(1); return(lq.front-next-data); ,4 取得鏈隊列的隊首結(jié)點的值,鏈式隊列的插入過程圖示見下圖

35、：,lq.rear-next=p; (2) lq.rear=p;,(1),(2),/ / 函數(shù)功能: 鏈隊列的入隊操作 / / 函數(shù)參數(shù): 指向LQueue類型指針變量lq / / datatype類型的變量x / / 函數(shù)名: InQueue() / / void insert(LQueue *lq,datatype x) QNode p; p=(QNode)malloc(sizeof(QNode); /分配空間/ p-data=x; /設(shè)置新結(jié)點的值/ p-next=NULL; lq-rear-next=p; /隊尾插入/ lq-rear=p; ,5 向鏈隊列中插入一個值為x的結(jié)點,鏈隊列

36、的刪除過程圖示見下圖：,鏈隊列的刪除過程圖示見下圖：,(1) p=lq.front (2) lq.front-next=p-next; (3) free(p);,(2),/ / 函數(shù)功能: 鏈隊列的出隊操作 / / 函數(shù)參數(shù): LQueue類型變量lq，變量x / / 函數(shù)名: InQueue() / / 刪除鏈式隊列中隊首結(jié)點 queue dele(queue lq)/刪除隊首結(jié)點/ node q; if(!lq.front-next) printf(隊列為空,無法刪除！);return qu; q=lq.front-next;/q指向隊首結(jié)點（1）/ lq.front-next=q-next; /修改指針（2）/ free(q);/釋放原隊首結(jié)點空間（3）/ if (lq.front-next=q) lq.rear=lq.front; return lq; ,6 刪除鏈隊列中一個結(jié)點,3.1 選擇題 （1）兩個有序線性表分別具有n個元素與m個元素且nm，現(xiàn)將其歸并成一個有序表，其最少的比較次數(shù)是（）。 AnBmCn1Dm+n （2）非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足（）。 Ap-next=NULL Bp=NULL Cp-next=headDp=head