【正文】 datatype*) malloc(sizeof(datatype))。 sqfront=(sqfront+1) ％ maxsize。 *x= sqdata[sqfront]。 return (x)。 } } 循環(huán)意義下的頭指針加1操作 或者 sqfront= =sqrear 2021/11/10 45 ⑦ 求隊(duì)列長度 int LengthQS(sequeue*sq) { return (sqrear sqfront+maxsize)%maxsize） 。 } 2021/11/10 46 循環(huán)隊(duì)列還可以有其它的定義形式。 假如循環(huán)隊(duì)列定義了頭指針 front和隊(duì)列長度 len， 結(jié)構(gòu)類型則定義如下： typedef struct { datatype data[maxsize]。 int front, len。 }sequeue。 sequeue *sq。 說明： 對(duì)于定義了頭指針 front和隊(duì)列長度len的循環(huán)隊(duì)列 ,由于可以區(qū)分空隊(duì)和滿隊(duì)，所以不需犧牲一個(gè)存儲(chǔ)單元。 空隊(duì)： sqlen==0成立 滿隊(duì)： sqlen==maxsize成立 隊(duì)尾指針為 （ sqfront+ sq len） %maxsize 2021/11/10 47 ① 隊(duì)列初始化 sequeue* InitSQ( ) { sequeue*sq； sq=(sequeue*)malloc (sizeof (sequeue))。 sqfront=maxsize1。 sqlen=0。 } 2021/11/10 48 ② 置空 隊(duì) void setnull(sequeue*sq) { sqfront=maxsize1。 sqlen=0。 } ③ 判隊(duì)空 int EmptyQS(sequeue*sq) { if (sqlen==0) return(1)。 else return(0)。 } 2021/11/10 49 ④ 取隊(duì)頭元素 datatype get(sequeue*sq) { datatype x if (EmptyQS(sq)) { printf(“queue is empty”)。 return (0)。 } else { x=sqdata[(sqfront+1)%maxsize]。 return(x)。 } } 2021/11/10 50 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列簡稱為鏈隊(duì)列，它是僅限在表頭刪除和表尾插入的單鏈表。 也是解決假溢出問題的第三種方法。 結(jié)構(gòu)類型定義： typedef char datatype。 typedef struct node { datatype data。 struct node *next } linklist。鏈隊(duì)列的結(jié)點(diǎn)類型 typedef struct { linklist *front, *rear。 } linkqueue。 //頭尾指針的結(jié)構(gòu)體類型 linkqueue *q。 // * q是鏈隊(duì)列指針 教材上定義為QueueNode 2021/11/10 51 鏈隊(duì)列的圖示說明 : f r o n tr e a rq空的鏈隊(duì)列 非空的鏈隊(duì)列示意圖 f r o n tr e a ra nqq r e a rq f r o n ta 1? 隊(duì)頭結(jié)點(diǎn)前 附加一個(gè)頭結(jié)點(diǎn) ，且頭指針 (qfront)指 向頭結(jié)點(diǎn) ,尾指針指向最后一個(gè)結(jié)點(diǎn)。 ? 鏈隊(duì)列 *q 為空條件： q?front==q?rear 2021/11/10 52 ? 鏈隊(duì)列的基本運(yùn)算實(shí)現(xiàn) ① 鏈隊(duì)列初始化（建立空隊(duì)列） linkqueue * InitQL( ) { linkqueue* q 。 q=(linkqueue*)malloc (sizeof (linkqueue))。 //產(chǎn)生頭、尾指針結(jié)構(gòu)體 qfront=qrear=(linklist*) malloc(sizeof (linklist))。 //產(chǎn)生頭結(jié)點(diǎn) qfrontnext=NULL。 //頭結(jié)點(diǎn)指針域置空 return q。 } ② 置空隊(duì) void SetNullQL(linkqueue*q) { qrear=qfront。 //尾指針也指向頭結(jié)點(diǎn) qfrontnext=NULL。 //頭結(jié)點(diǎn)指針域置空 } 2021/11/10 53 ③ 判隊(duì)空 int EmptyQL(linkqueue*q) { if(qfront==qrear) return(1)。 else return(0)。 } ④ 取隊(duì)頭元素 linklist * FrontQL(linkqueue*q) //取出鏈隊(duì)列 q 的隊(duì)頭元素 { if (EmptyQL(q)) { printf(“queue is empty”)。 return (NULL)。 } else { return (qfrontnext) } return (qfrontnextdata) } 或者 q?front==q?rear 數(shù)據(jù)類型保持一致 函數(shù)類型如果定義為 datatype 2021/11/10 54 ⑤ 入隊(duì) (帶頭結(jié)點(diǎn) ) void EnqueueQL(linkqueue *q, datatype x) //將結(jié)點(diǎn) x加入鏈隊(duì)列 q { linklist *p。 p=(linklist*)malloc(sizeof(linklist))。//新生成一個(gè)結(jié)點(diǎn) pdata=x。 //給新結(jié)點(diǎn)賦值 qrearnext=p。 // 新結(jié)點(diǎn)插入尾端 qrear=qrearnext。 //尾指針指向新結(jié)點(diǎn) qrearnext=NULL。 } 或 qrear=p pnext=NULL。 2021/11/10 55 ⑥ 出隊(duì) (帶頭結(jié)點(diǎn) ) datatype * DequeueQL(linkqueue *q) // 將隊(duì)頭元素刪除 { linklist *s。 datatype *tmp。 if (EmptyQL(q)) { printf(“queue is empty”)。 return (NULL)。 } else { s = qfrontnext。 //s指向被刪除的開始結(jié)點(diǎn) if (snext= =NULL) //當(dāng)前鏈隊(duì)列的長度等于 1 { qfrontnext=NULL。 qrear=qfront 。} //置為空隊(duì) else { qfrontnext=snext。 } //當(dāng)前鏈隊(duì)列的長度大于 1，修改頭結(jié)點(diǎn)的指針域 tmp=(datatype *)malloc(sizeof(datatype))。 //為 tmp開辟空間建立新結(jié)點(diǎn) * tmp = sdata。 free(s)。 //釋放被刪除的結(jié)點(diǎn)空間 return(tmp)。 } 或者 q?front==q?rear 2021/11/10 56 隊(duì)列小結(jié)： 鏈?zhǔn)疥?duì)列 隊(duì)列 的 定義 鏈?zhǔn)疥?duì)列 犧牲一個(gè)單元 循環(huán) 隊(duì)列 解決溢出 數(shù)據(jù)移動(dòng) 順序 隊(duì)列 循環(huán)隊(duì)列判斷 滿和空 標(biāo)志位 運(yùn)算