【文章內(nèi)容簡(jiǎn)介】 ? {link p1,p2,p3。 ? p2=fn。 ? while(p2m*jp2n*i) ? {p1=p2。p2=p2next。} ? p3=(link)malloc(sizeof(*p3))。 ? p3n=j。 ? p3m=i。 ? p3next=p2。 ? p1next=p3。 ? } ? main(){ ? int i,j,n。 ? link p1,p2。 ? scanf(“%d”,amp。n)。 ? fn=(link)malloc(sizeof(struct node))。 ? fnn=0。 ? fnm=1。 ? p1=(link)malloc(sizeof(struct node))。 ? p1n=1。 ? p1m=1。 ? p1next=NULL。 ? fnnext=p1。 ? for(i=n。i1。i) ? for(j=1。ji。j++) ? if(gcd(i,j)==1)insert(i,j)。 ? p1=fn。 ? do{ ? I=0。 ? while((p2!=NULL)amp。amp。(I++10)) ? {printf(“%4d”,p2n)。 ? p2=p2next。 ? } ? printf(“\n”)。 ? for(j=0。ji。j++)printf(“”)。 ? p2=p1。 ? i=0。 ? while ((p2!=NULL)amp。amp。(i++10)) ? { ? printf(“%4d”,p2m)。 ? p2=p2next。 ? } ? printf(“\n\n”)。 ? p1=p2。 ? }while(p2!=NULL)。 ? } ? 棧和隊(duì)列 ? ⒈ 隊(duì)列 ? （ 1）隊(duì)列的特征和基本操作 ? 隊(duì)列是從日常排隊(duì)現(xiàn)象中抽象出來的一種數(shù)學(xué)模型。隊(duì)列結(jié)構(gòu)中的數(shù)據(jù)項(xiàng)可以隨機(jī)地增減，但數(shù)據(jù)進(jìn)出隊(duì)列的方式是受限的，數(shù)據(jù)只能從隊(duì)尾入隊(duì)，也只能從隊(duì)首出隊(duì)。已進(jìn)入隊(duì)列的數(shù)據(jù)的次序是不能改變的。每當(dāng)有數(shù)據(jù)取出時(shí)，剩下的依次向首部移動(dòng)。因此，隊(duì)列稱為一種先進(jìn)先出的結(jié)構(gòu)（ FIFO）。在任何時(shí)刻隊(duì)列中能被讀出的數(shù)據(jù)是隊(duì)列首端的數(shù)據(jù)。 ? 根據(jù)上述特征，隊(duì)列有如下操作： ? 創(chuàng)建隊(duì)列（ CreateQ）； ? 初始化隊(duì)列（ InitQ）； ? 數(shù)據(jù)插入到隊(duì)列（ EnQ）； ? 從隊(duì)列中取出數(shù)據(jù)（ DeQ）； ? 判斷隊(duì)列為空 (EmptyQ)； ? 判斷隊(duì)列為滿（ FULLQ）。 ?（ 2）隊(duì)列的實(shí)現(xiàn) ?隊(duì)列和后面即將講的棧都是程序設(shè)計(jì)中最常用的數(shù)據(jù)結(jié)構(gòu)。但與數(shù)組、記錄等不同，絕大多數(shù)語言并未提供直接實(shí)現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)的設(shè)施。要實(shí)現(xiàn)隊(duì)列長(zhǎng)度任意變化的特征使用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)比較適合。本節(jié)中討論用線性表（靜態(tài)數(shù)據(jù)結(jié)構(gòu)）實(shí)現(xiàn)隊(duì)列的一種方法。 ?假定隊(duì)列中元素的類型為 T，估計(jì)隊(duì)列的最大的長(zhǎng)度為 maxsize，在任何一時(shí)刻，都用 head， tail分別指向隊(duì)列的隊(duì)首元素和隊(duì)尾元素。則隊(duì)列可以用如圖 。 圖 ? maxsize 指針 head tail ?隊(duì)列的初始狀態(tài)是 head=0,tail= 1。 ?根據(jù)隊(duì)列定義， head就恒為 0。那么每當(dāng)隊(duì)列中送出一個(gè)數(shù)據(jù)項(xiàng)，必須執(zhí)行多次移動(dòng)操作。 ?若采用“循環(huán)隊(duì)列”技術(shù)，可以完全避免隊(duì)列內(nèi)元素的移動(dòng)。即當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)時(shí)，先移動(dòng)尾指針tail（即 tail=(tail+1)mod maxsize），插入的數(shù)據(jù)項(xiàng)放入到 qdata[tail]中。而在隊(duì)列中取出數(shù)據(jù)項(xiàng)時(shí)，先移動(dòng) head指針，（即 head=(head+1) mod maxsize）， qdata[head]就是取出的數(shù)據(jù)項(xiàng)。在 C語言中，有 maxsize個(gè)元素的數(shù)組的下標(biāo)是從 0到maxsize 1。因此，無論移動(dòng)隊(duì)首指針還是移動(dòng)隊(duì)尾指針始終都是加 1后模 maxsize。這樣當(dāng)指針走到maxsize1的位置時(shí)，自動(dòng)地又回到了 0，這樣就構(gòu)成了循環(huán)隊(duì)列，其結(jié)構(gòu)如圖 。 ? 用“循環(huán)數(shù)組”實(shí)現(xiàn)隊(duì)列，必須注意怎樣判斷隊(duì)列的空或滿狀態(tài)。在以下的實(shí)現(xiàn)中，隊(duì)起始狀態(tài)除外，任何時(shí)刻 tail都指向最近一個(gè)進(jìn)入隊(duì)列的元素，而 head指向最近一個(gè)已經(jīng)離開的元素原先所占用的位置。因此，（ head+1） mod maxsize 才是真正的當(dāng)前隊(duì)列中首元素的位置。采用條件： ? （ tail+1） mod maxsize=head ? 來作為“隊(duì)列滿”條件，實(shí)際上隊(duì)列中還有一個(gè)空位。這樣隊(duì)列存儲(chǔ)區(qū)有效空間比定義的最大空間少一個(gè)單元。假如把這個(gè)單元也用上，則當(dāng)head和 tail指向同一單元時(shí)，隊(duì)列既可能是滿的，也可能是空的。必須根據(jù) head追上了 tail還是 tail追上了 head來區(qū)分，這樣給處理帶來不便。 ? 下面以 C程序?yàn)槔?，給出隊(duì)列操作中的常用算法。 ? /* 抽象數(shù)據(jù)類型隊(duì)列的定義 */ ? /* */ ? define maxsize 100 ? typedef int T。 ? typedef T Qdata[maxsize]。 ? typedef struct{ ? Qdata data。 ? Int head,tail。 ? }Qzone。 ? typedef Qzone *Q。 ? typedef enum {true=1,false=0}bool。 ? typedef enum{success,fail}status。 ? extern Q initQ()。 ? extern status enQ()。 ? extern T *deQ()。 ? extern T*examQ()。 ? extern bool fullQ()。 ? extern bool emptyQ()。 ? 由于是靜態(tài)實(shí)現(xiàn)，所以沒有 createQ()函數(shù)。將以上內(nèi)容作為一個(gè)模塊存放在 。對(duì)于模塊中各函數(shù)的具體實(shí)現(xiàn)，用另外一個(gè)文件來保存，即在文件 。 ? /* 隊(duì)列操作實(shí)現(xiàn)模塊 */ ? /* */ ? include ? /* 函數(shù) initQ()用來初始化一個(gè)隊(duì)列 */ ? Q initQ( a) ? Qzone *a。 ? { ? Q p。 ? P=a。 ? Phead=maxsize1。 ? ptail=maxsize1。 ? returen(p)。 ? } ? /* enQ() 將元素 term插入到隊(duì)列 */ ? status enQ(term, pq) ? T *term。 ? Q pq。 ? { ? if ((pqtail+1)%maxsize==pqhead) ? return fail。 ? else ? { ? pqtail=(pqtail+1) %maxsize。 ? pqdata[pqtail]=*term。 ? return success。 ? } ? } ? /* 函數(shù) deQ()用來從隊(duì)列中取出一個(gè)數(shù)據(jù) */ ? T * deQ(pq) ? Q pqj。 ? { ? T *term。 ? If(pqtail!=pqhead) ? { ? pqhead=(pqhead+1)%maxsize。 ? term=amp。(paqdata[pqhead])。 ? return(term)。 ? } ? } ? T * examQ( pq) /* 訪問隊(duì)首元素，但不刪除該元素 * / ? Q pq。 ? { ? T *term。 ? if(pqtail!=pqhead){ ? term=amp。(pqqdata[(pqhead+1)%maxsize])。 ? return(term)。 ? } ? } ? bool fullQ(pq) ? Q pq ? {return(((pqtail+1)%maxsize)==pqhead)。 ? } ? bool emptyQ(Q pq) ? {return (pqtail==pqhead)。 } ? 2．棧 ?（ 1）棧的基本特征和操作 ?棧是只限定在表尾進(jìn)行插入和刪除的線性表。因此，對(duì)棧來說，表尾端具有特殊的含義，稱為棧頂。相應(yīng)地，表頭端稱為棧底。不含元素的棧稱為空棧。 ?假設(shè)棧 S=(a1,a2,…,an) ，則 a1稱為棧底元素， an稱為棧頂元素。棧中的元素按 a1,a2,a3…,an 的順序進(jìn)棧的。換句話說，棧的元素修改是后進(jìn)先出的（ LIFO），其示意圖如圖 。 圖 ?進(jìn)棧 出棧 ?棧頂 ?棧底 an a2 a1 棧s=(a1,a2,……,an) ? 棧的基本操作除了在棧頂進(jìn)行插入和刪除以外，還有棧的初始化、判斷棧是否為空，判斷棧是否為滿以及訪問棧頂元素等。 ? （ 2）棧的表示和實(shí)現(xiàn) ? 和線性表相似，棧的存儲(chǔ)也有兩種方式，即順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。本小節(jié)只討論順序存儲(chǔ)方式的棧。 ? 順序存儲(chǔ)結(jié)構(gòu)的棧是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)脑?。同時(shí)附設(shè)指針 top，指示棧頂元素在順序表中的棧頂位置。習(xí)慣上以數(shù)組來描述棧的實(shí)現(xiàn)，棧頂指針用一個(gè)整型變量來表示，它用來指示處于棧頂位置的數(shù)組的下標(biāo)，通常用下標(biāo) 0表示棧為空。在 C語言中數(shù)組的下標(biāo)是從 0開始的。所以下標(biāo) 0表示棧為空對(duì) C語言來說，有些不方便。因此，指針 top指向棧中即將放數(shù)據(jù)的位置。而真正的棧頂元素?cái)?shù)據(jù)的位置，是 top1的位置。 Top等于數(shù)組元素的最大個(gè)數(shù)時(shí)表示棧已滿。其 C語言的實(shí)現(xiàn)過程如 ? define maxsize 100 ? typedef int T。 ? typedef struct ? { ? T stkdata[maxsize]。 ? Int top。 ? }STKzone。 ? typedef STKzone *STK。 ? typedef enum{true=1,false=0}bool。 ? typedef enum{success=1,false=0}status。 ? extern STK initSTK()。 ? extern status push()。 ? extern status pop()。 ? extern status exam()。 ? extern bool fullSTK()。 ? extern bool emptySTK()。 ? 將以上內(nèi)容存于 。 ? 與靜態(tài)實(shí)現(xiàn)隊(duì)列一樣，應(yīng)用模塊必須顯示定義 STKzone類型變量，以建立棧的實(shí)際存儲(chǔ)區(qū)域?；静僮饔上铝心K實(shí)現(xiàn)。 ? /* 棧的操作實(shí)現(xiàn)模塊 */ ? /* */ ? include ? STK initSTK(stk_zone) ? STK stk_zone。 ? { ? STK p。 ? P=stk_zone。 ? ptop=0。 ? return (p)。 ? } ? status push(term,pstk) ? T * term。 ? STK pstk。 ? { ? if (pstktop==maxsize) ? return fail。 ? else ? { ? pstkstkdata[pstktop]=*term。 ? pstktop++。 ? return success。 ? } ? } ? status pop(pdata,pstk) ? T *pdata。 ? STK pstk。 ? { ? bool emptySTK()。 ? if (emptySTK(pstk)) ? return fail。 ? else ? { ? pstktop。 ? *pdata=pstkstkdata[pstktop]。 ? return success。 ? } ? } ? status exam(pdata,pstk) ? T *pdata。 ? STK pstk。 ? { ? bool emptySTK()。 ? if (emptySTK(pstk)) ? return fail。 ? else ?