數(shù)據(jù)結(jié)構(gòu)第3章 棧和隊(duì)列ppt（章節(jié)課程）

1、第3章 棧和隊(duì)列 3.1 棧 3.2 隊(duì)列 3.3 應(yīng)用1陽山書屋本章學(xué)習(xí)目標(biāo)理解棧的定義及其基本運(yùn)算掌握順序棧和鏈棧的各種操作實(shí)現(xiàn)理解隊(duì)列的定義及其基本運(yùn)算掌握循環(huán)隊(duì)列和鏈隊(duì)列的各種操作實(shí)現(xiàn)學(xué)會(huì)利用棧和隊(duì)列解決一些問題2陽山書屋棧和隊(duì)列是兩種重要的線性結(jié)構(gòu)棧和隊(duì)列是操作受限的線性表出進(jìn)排隊(duì)買票漢諾塔進(jìn)出3陽山書屋3.1 棧3.1.1 棧的基本概念棧：限制僅在表的一端進(jìn)行插入和刪除操作的線性表?xiàng)５牟僮魈匦裕喊聪冗M(jìn)后出(F I L O )或后進(jìn)先出(I)的原則 棧頂(top)：允許插入和刪除的一端。 約定top始終指向棧頂位置。 棧底(bottom): 不允許插入和刪除的一端。 入棧順序：e0

2、e1 e2 en-2 en-1 出棧順序：en-1 en-2 e2 e1 e0 ?？梢詫?duì)序列實(shí)現(xiàn)求逆en-1e0e1en-2 進(jìn)棧（Push） 出棧（Pop）棧頂 top棧底bottom 4陽山書屋棧的基本運(yùn)算 ：InitStack(s) 初始化操作，初始化為空棧s 。 IsEmpty(s) 判斷棧空函數(shù)。如果s是空棧，返回“true”，否則返回“false”。IsFull(s) 判斷棧滿函數(shù)。主要應(yīng)用在順序存儲(chǔ)結(jié)構(gòu)中，如果s棧滿，返回“true”，否則返回“false”。Push(s，x) 壓棧操作。將元素x插入到棧s中，并使x成為新的棧頂元素。Pop(s) 出棧函數(shù)。如果棧s非空，那么返回

3、棧頂元素，并刪除該棧頂元素，否則返回空值NULL。GetTop(s) 獲取棧頂元素。如果棧s非空，那么返回值為棧頂元素，否則返回空值NULL。EmptyStack(s) 清空棧操作。將棧s中的所有元素清除掉，使之成為一個(gè)空棧。DestroyStack ()銷毀棧。釋放棧占用的存儲(chǔ)空間。5陽山書屋棧有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu) 順序棧：順序存儲(chǔ)結(jié)構(gòu)的棧。順序棧：用一組連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示棧頂指針：指示棧頂位置 ABACBA (a)空棧 （b）元素A進(jìn)棧 （c）元素B、C進(jìn)棧 （ d）出棧一次 （ e）出棧二次t

4、op-1toptoptoptop-143210432104321043210432106陽山書屋順序棧類型定義： #define StackSize 100 /*順序棧的初始分配空間*/ typedef struct DataType dataStackSize; /*保存棧中元素*/ int top; /*棧指針*/ SeqStack;top為int型，取值范圍為0-StackSize-1。top=-l表示?？眨籺op=StackSize-1表示棧滿。棧的長度：棧頂指針top+17陽山書屋順序棧的基本運(yùn)算：(1) 初始化棧運(yùn)算功能：創(chuàng)建一個(gè)空棧，并將初始化棧頂下標(biāo)top=-1。int Ini

5、tStack(SeqStack *&sq) sq=(SeqStack *)malloc(sizeof(SeqStack); if (!sq) printf(“memory is not enough!”); return 0; sq-top=-1 ; return 1； 8陽山書屋(2)進(jìn)棧運(yùn)算功能：棧頂指針加1，將進(jìn)棧元素放進(jìn)棧頂指針?biāo)傅奈恢蒙稀?int Push(SeqStack *sq, DataType x) if(sq-top= StackSize-1)/*棧滿*/ return 0; else sq-top+; sq-datasq-top=x ; return 1; 9陽山書屋(

6、3)出棧運(yùn)算功能：先將棧頂元素取出，然后將棧頂指針減1。int Pop(SeqStack *sq, DataType &x) if(sq-top=-1) /*?？?/ return 0; else x=sq-datasq-top; sq-top-; return 1; 10陽山書屋(4)取棧頂元素運(yùn)算功能：將棧中top處的元素取出賦給變量x。int GetTop(SeqStack *sq, DataType &x) if(sq-top=-1) /*?？?/ return 0; else x=sq-datasq-top; return 1; 11陽山書屋(5)判斷棧空運(yùn)算算法功能：若棧為空(to

7、p=-1)則返回值l，否則返回值 0。int StackEmpty(SeqStack *sq) if(sq-top=-1) return 1; else return 0; 12陽山書屋3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第一個(gè)結(jié)點(diǎn)為棧頂結(jié)點(diǎn)優(yōu)點(diǎn)：鏈?zhǔn)綏o棧滿問題，空間可擴(kuò)充特點(diǎn)：插入與刪除僅在棧頂處執(zhí)行l(wèi)s棧頂棧底data next（棧頂指針）鏈棧的類型定義：typedef struct stnod DataType data; /*存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)*/ struct stnode *next ; /*指針域*/LinkStack;13陽山書屋棧的基本運(yùn)算算法： (1)初始化棧運(yùn)

8、算功能：創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的鏈棧，頭結(jié)點(diǎn)指針ls； 用ls-next=NULL標(biāo)識(shí)棧為空棧。 void InitStack(LinkStack *&ls) ls=(LinkStack *)malloc(sizeof(LinkStack); ls-next=NULL; 14陽山書屋(2) 判斷?？者\(yùn)算功能：若棧為空則返回值1，否則返 回值0。int StackEmpty(LinkStack *ls) if(ls-next=NULL) return 1; else return 0;15陽山書屋 (3) 進(jìn)棧運(yùn)算 void Push(LinkStack *ls, DataType x) LinkSt

9、ack *p; p=(LinkStack*)malloc(Sizeof(LinkStack); p-data=x; p-next=ls-next; ls-next=p; 16陽山書屋(4)出棧運(yùn)算功能: 將棧頂結(jié)點(diǎn)的data域值賦給x, 然后刪除該棧頂結(jié)點(diǎn)。 int Pop(LinkStack *ls，DataType &x) LinkStack *p; if(ls-next=NULL) /*?？?，下溢出*/ return 0; else p=ls-next; x=p-data; ls-next=p-next; free(p); return 1; 17陽山書屋(5)取棧頂元素運(yùn)算算法 功能：

10、將棧頂結(jié)點(diǎn)的data域值賦給x。int GetTop(LinkStack *ls, DataType &x) if(ls-next=NULL) /*棧空，下溢出*/ return 0; else x=ls-next-data; return 1; 18陽山書屋3.2 隊(duì)列3.2.1 隊(duì)列的基本概念隊(duì)列：限制插入操作只能在一端進(jìn)行，而刪除操作只能在另一端進(jìn)行的線性表操作特性：按先進(jìn)先出(FIFO)或后進(jìn)后出(LILO)的原則。隊(duì)首（front）：能進(jìn)行刪除的一端隊(duì)尾（rear） ：能進(jìn)行插入操作的一端。出隊(duì)入隊(duì)隊(duì)首（front）隊(duì)尾（rear）19陽山書屋隊(duì)列的基本操作主要：1) InitQue

11、ue(Q)：構(gòu)造一個(gè)空隊(duì)列Q。2) QueueEmpty(Q)：判斷隊(duì)列是否為空。3) QueueLength(Q)：求隊(duì)列的長度。4) GetHead(Q)：返回Q的隊(duì)頭元素，不改變隊(duì)列狀態(tài)。5) EnQueue(Q，x)：插入元素x為Q的新的隊(duì)尾元素。6) DeQueue(Q)：刪除Q的隊(duì)頭元素。7) C1earQueue(Q)：清除隊(duì)列Q中的所有元素。20陽山書屋隊(duì)列有兩種存儲(chǔ)表示：順序隊(duì)列和鏈隊(duì)列 。3.2.2 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)front隊(duì)首指針 隊(duì)首 隊(duì)尾 rear隊(duì)尾指針鏈隊(duì)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列；為一個(gè)同時(shí)帶有首指針和尾指針的單鏈表隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無隊(duì)滿問

12、題，但有隊(duì)空問題。21陽山書屋鏈隊(duì)的類型定義： typedef struct QNode DataType data; struct QNode *next; QType; /*鏈隊(duì)中結(jié)點(diǎn)的類型*/ typedef struct qptr QType *front,*rear; LinkQueue; /*鏈隊(duì)類型*/隊(duì)空的條件:lq-front=lq-next=NULL。22陽山書屋鏈隊(duì)基本運(yùn)算算法：(1) 初始化隊(duì)列運(yùn)算 功能：置隊(duì)列l(wèi)q的rear和front均為NULL。void InitQueue(LinkQueue *&lq) lq=(LinkQuene *)malloc(sizeof

13、(LinkQuene); lq-rear=lq-front=NULL; /*初始情況*/23陽山書屋(2) 入隊(duì)運(yùn)算功能：創(chuàng)建一個(gè)新結(jié)點(diǎn)，將其鏈接到鏈隊(duì)列的末尾， 并由rear指向它。Void EnQueue(LinkQueue *lq, DataType x) QType *s; /*創(chuàng)建新結(jié)點(diǎn)，插入到鏈隊(duì)的末尾*/ s=(QType *)malloc(sizeof(QType); /*創(chuàng)建新結(jié)點(diǎn)，插入到鏈隊(duì)的末尾*/ s-data=x; s-next=NULL; if(lq-front=NULL&lq-rear=NULL) /*空隊(duì)*/ lq-rear=lq-front=s; else l

14、q-rear-next=s; lq-rear=s; 24陽山書屋(3)出隊(duì)運(yùn)算功能：將front結(jié)點(diǎn)的data域值賦給x，并刪除該結(jié)點(diǎn)。DataType DeQueue(LinkQueue *lq) QType *p; DataType x; if(lq-front=NULL&lq-rear=NULL) /*空隊(duì)*/ exit(-1); p=lq-front; x=p-data; if(lq-rear=lq-front) /* 若原隊(duì)列中只有一個(gè)結(jié)點(diǎn)，刪除后隊(duì)列變空*/ lq-rear=lq-front=NULL; else lq-front=p-next; free(p); return x

15、; 25陽山書屋(4) 取隊(duì)頭元素運(yùn)算功能：將front指向結(jié)點(diǎn)的data域值賦給xDataType GetHead(LinkQueue *lq) DataType x; if(lq-front=NULL&lq-rear=NULL) /*空隊(duì)*/ exit(-1); x=lq-front-data; return x; 26陽山書屋(5)判斷隊(duì)空運(yùn)算算法功能：若鏈隊(duì)為空，則返回1；否則返回0 int QueueEmpty(LinkQueue *lq) if(lq-front=NULL&lq-rear=NULL) return 1; else return 0; 27陽山書屋3.2.3 循環(huán)隊(duì)列

16、順序隊(duì)列：順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列，即用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)頭到隊(duì)尾的元素；順序隊(duì)列：實(shí)質(zhì)是運(yùn)算受限的順序表；543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空隊(duì) （b）a、b入隊(duì) （c）a、b出隊(duì)，c、d入隊(duì)（d）假溢出28陽山書屋3.2.3 循環(huán)隊(duì)列由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，設(shè)立兩個(gè)指針 front 和 rear ，指針 front隊(duì)頭， rear指示隊(duì)尾下一個(gè)元素；每插入一新元素，rear 增 1，每刪除一元素，front 增 1。front = rear = 0 表示空隊(duì)列，rea

17、r=MAXSIZE 表示隊(duì)滿。543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空隊(duì) （b）a、b入隊(duì) （c）a、b出隊(duì)，c、d入隊(duì)（d）假溢出29陽山書屋543210543210543210543210rearfrontbadcfefrontrearrearfrontfrontrear(a)空隊(duì) （b）a、b入隊(duì) （c）a、b出隊(duì)，c、d入隊(duì)（d）假溢出避免假溢出有兩種辦法： 1) 每次一個(gè)元素出隊(duì)，將整個(gè)隊(duì)列向前移動(dòng)一個(gè)位置。 2) 采用循環(huán)隊(duì)列：將順序隊(duì)列的數(shù)據(jù)區(qū)data0MAXSIZE-1 看成一個(gè)

18、首尾相接的圓環(huán)，頭尾指針的關(guān)系不變30陽山書屋循環(huán)隊(duì)列的類型定義： #define MAXSIZE 100 /*最大隊(duì)列長度 */ typedef struct datatype dataMAXSIZE; /*存儲(chǔ)隊(duì)列的數(shù)據(jù)空間*/ int front; /*隊(duì)頭指針，若隊(duì)列不空，則指向隊(duì)頭元素*/ int rear; /*隊(duì)尾指針，若隊(duì)列不空，則指向隊(duì)尾元素的下一個(gè)位置*/ SeqQueue; rear front 0 1 2 3e4e331陽山書屋循環(huán)隊(duì)列特點(diǎn) rear front 0 1 2 3(3) 隊(duì)空將頭尾連接成一個(gè)環(huán)，形成循環(huán)隊(duì)列。 rear(1)一般情況 front 0 1 2

19、 3e4e3 (2) 隊(duì)滿 e3 e4 0 1 2 3 reare5rear=fronte6rear=front front32陽山書屋在入隊(duì)時(shí)， rear=（rear+1）%MAXSIZE。存儲(chǔ)隊(duì)列的數(shù)組就變?yōu)槭孜蚕嘟拥囊粋€(gè)環(huán)，即為循環(huán)隊(duì)列。在出隊(duì)時(shí)，front=(front+1)%MAXSIZE，實(shí)現(xiàn)存儲(chǔ)空間的首尾相接。判斷隊(duì)列“空”還是“滿”的處理方法：一是另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列的“空”和“滿”；二是少用一個(gè)元素的空間，約定以“隊(duì)頭指針在隊(duì)尾指針的下一位置(指環(huán)狀的下一位置)上”作為隊(duì)列“滿”的標(biāo)志。33陽山書屋543210543210543210dcfedcgfrontrearrea

20、rfrontrearfront(a)正常情況 （b） 隊(duì)滿 （c） 隊(duì)空 在循環(huán)隊(duì)列中：若front=rear，則稱為隊(duì)空；若(rear+1)%maxsize=front, 則稱為隊(duì)滿。循環(huán)隊(duì)列中能裝入的元素個(gè)數(shù)為maxsize-1，即浪費(fèi)一個(gè)存儲(chǔ)單元，但是這樣可以給操作帶來較大方便。34陽山書屋3循環(huán)隊(duì)列的基本操作(1)構(gòu)造空隊(duì)列int InitQueue(SeqQueue *&q) q=(SeqQueue*)malloc(sizeof(SeqQueue); /*開辟一個(gè)足夠大的存儲(chǔ)隊(duì)列空間*/ if (!q) return 0; q-front=q-rear=0; /*將隊(duì)列頭尾指針置為零

21、*/ return 1;35陽山書屋(2) 判斷隊(duì)空int QueueEmpty(SeqQueue *q) return(q-front=q-rear); /*如果隊(duì)列為空，則返回1，否則返回0*/36陽山書屋 (3) 入隊(duì) int EnQueue(SeqQueue*q，DataType x) if(q-rear+1)%MAXSIZE=q-front) /*判斷隊(duì)列是否滿*/ printf(n循環(huán)隊(duì)列滿!”); return FALSE; /* 若隊(duì)列滿，則終止*/ q-dataq-rear=x; /*將元素x入隊(duì)*/ q-rear=(q-rear+1)MAXSIZE; /*修改隊(duì)尾指針*/

22、return TRUE;37陽山書屋(4)出隊(duì) DataType DeQueue(SeqQueue *q) DataType x; if(q-front=q-rear) /*判斷隊(duì)列是否空*/ printf(n循環(huán)隊(duì)列空!不能做刪除操作!); return FALSE; / *若隊(duì)列空，則終止*/ x=q-dataq-front; /*將隊(duì)頭元素出隊(duì)并賦給變量x*/ q-front=(q-front+1)MAXSIZE; /*修改隊(duì)列頭指針*/ return x; /*將被刪除元素返回*/38陽山書屋3.3 應(yīng)用3.3.1 棧的應(yīng)用【例3.1】 設(shè)計(jì)一個(gè)算法，判斷一個(gè)表達(dá)式中符號(hào)“(”與“)”

23、、“”與“”、“”與“”是否匹配。若匹配，則返回1；否則返回0。設(shè)置一個(gè)棧st；用i掃描表達(dá)式exps，當(dāng)遇到“(”、“”、“”時(shí)，將其進(jìn)棧，遇到“”、“”、“)”時(shí)，判斷棧頂是否是相匹配的括號(hào)。若不是，則退出掃描過程，返回0；否則直至exps掃描完畢為止；若top=-1，則返回1，否則返回0。39陽山書屋#define Max 100int match(char *exps) char stMax; int top=-1,i=0; int nomatch=0; while(expsi!=0&nomatch=0) switch(expsi) case (: top+;sttop=expsi ;

24、 break; case : top+;ttop=expsi ; break; case : top+;ttop=expsi ; break; case ): if(expstop=() top-; else nomatch=l ; break;case : if(expstop=) top-; else nomatch=1 ; break; case : if(expstop= ) top-; else nomatch=l; break; i+; if(nomatch=0&top=-1) /*?？涨曳?hào)匹配則返回l*/ return 1; else return 0 ; /*否則返回0*/4

25、0陽山書屋【例3.2】數(shù)制轉(zhuǎn)換問題。把一個(gè)非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換成n（2n35）進(jìn)制數(shù)，其中各位的系數(shù)如果大于9的依次用大寫英文字母AZ表示。 十進(jìn)制整數(shù)x轉(zhuǎn)換成n進(jìn)制數(shù)的法則是：對(duì)x除n取余，直到整商為為止，先得到的余數(shù)需要后輸出。 例如，十進(jìn)制整數(shù)83轉(zhuǎn)換成8進(jìn)制數(shù)的過程如下圖所示，結(jié)果為(123)8。41陽山書屋Typedef * SeqStack；main()int x, n;SeqStack *stack;InitStack (stack); /*初始化棧stack*/doprintf(x=);scanf(%d, &x);printf(n=);scanf(%d, &n);while(n3

26、5 | x0); /*輸入有效數(shù)據(jù),x是十進(jìn)制數(shù),n是進(jìn)制*/ while(x) /*除n取余,余數(shù)保存在堆棧中*/ Push(stack, x%n);x/=n; while(!ISEmpty(stack) /*依次出棧，直到?？?/Pop(stack, &x);if(x10) printf(%c,x+0);/*輸出位的系數(shù)，范圍09*/else printf(%c,x+A-10);/*輸出位的系數(shù)，范圍AZ*/printf(n);DestroyStack(stack);42陽山書屋【例3.3】利用一個(gè)棧逆置一個(gè)帶頭結(jié)點(diǎn)的單鏈表，已知head是帶頭結(jié)點(diǎn)的單鏈表(a1，a2，an) (其中n0)

27、。說明如下： typedef int DataType ； typedef struct node DataType data； struct node *next； LinkList； LinkList *head;請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，利用一個(gè)順序棧將上述單鏈表 實(shí)現(xiàn)逆置利用一個(gè)順序棧將單鏈表(a1，a2，an) (其中 n0)逆置為(an，an-l，a1) 43陽山書屋44陽山書屋 解題思路： 1)建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表head。 2)輸出該單鏈表。 3)建立一個(gè)空棧s(順序棧)。 4)依次將單鏈表的數(shù)據(jù)入棧。 5)依次將單鏈表的數(shù)據(jù)出棧，并逐 個(gè)將出棧的數(shù)據(jù)存入單鏈表的數(shù)據(jù)域(自前向后）。

28、 6)再輸出單鏈表。45陽山書屋/*利用順序棧逆置單鏈表程序*/#include #include #define maxsize 100 /*棧的最大元素?cái)?shù)為100*/typedef int DataType;typedef struct node /*定義單鏈表結(jié)點(diǎn)類型*/ DataType data; struct node *next; LinkList;LinkList *head; /*定義單鏈表的頭指針*/typedef struct /*定義順序棧*/ DataType dmaxsize; int top;SeqStack;SeqStack s;/*定義順序棧s，s是結(jié)構(gòu)體變量

29、，s是全局變量*/46陽山書屋LinkList *CreatList() /*建立單鏈表 */ LinkList *p, *q; int n=0; p=q=(LinkList *)malloc(sizeof(LinkList t); head=p; p-next=NULL; /*頭結(jié)點(diǎn)的數(shù)據(jù)域不存放任何東西*/ p=(LinkList *)malloc(sizeof(LinkList ); scanf(%d,&p-data); while(p-data!=-1) /*輸入-l表示鏈表結(jié)束*/ n=n+1; q-next=p; q=p; p=(LinkList *)malloc(sizeof(L

30、inkList ); scanf(%d,&p-data); q-next=NULL; free(p) return(head);47陽山書屋void print(LinkList *head) /*輸出單鏈表*/ LinkList *p; p=head-next; if(p=NULL) printf(This is an empty 1istn ); else do printf(%6d,p-data); p=p-next; while(p!=NULL); printf(n); 48陽山書屋SeqStack InitStack() /*構(gòu)造一個(gè)空棧s*/ s.top=-1; return s;

31、49陽山書屋int push(SeqStack *s, DataType x) /*入棧，此處s是指向順序棧的指針*/ if(*s).top=maxsize-1) /*(*s).top即為s-top，下同*/ printf(棧已滿，不能入棧!n); return 0; else (*s).top+; /*棧頂指針上移*/ (*s).d(*s).top=x; /*將x存入棧中*/ return x; 50陽山書屋DataType pop(SeqStack *s) /*出棧，s是指向順序棧的指針*/ DataType y; if(*s).top=-1) printf(棧為空，無法出棧!n); re

32、turn 0; else y=(*s).d(*s).top; /*棧頂元素出棧，存入y中*/ (*s).top-; /*棧頂指針下移*/ return y; 51陽山書屋int StackEmpty(SeqStack s) /*判?？?，此處s是結(jié)構(gòu)體變量*/ return s.top=-1;int StackFull(SeqStack s) /*判棧滿，此處s是結(jié)構(gòu)體變量*/ return s.top=maxsize-1;52陽山書屋LinkList *backlinklist(LinkList *head)/*利用順序棧s逆置單鏈表head*/ LinkList *p; p=head-nex

33、t; initstack(); while(p) push(&s, p-data); /*單鏈表的數(shù)據(jù)依次入棧s*/ p=p-next; p=head-next; while(!stackempty(s) p-data=pop(&s); /*數(shù)據(jù)出棧依次存入單鏈表的數(shù)據(jù)域*/ p=p-next; return(head); 53陽山書屋 void main() linklist *head; head=creatlist(); print(head); head=backlinklist(head); print(head); 54陽山書屋3.3.2 隊(duì)列的應(yīng)用 【例34】打印楊輝三角形是一個(gè)

34、初等數(shù)學(xué)問題。系數(shù)表中的第i行有i+1個(gè)數(shù)，除了第1個(gè)和最后一個(gè)數(shù)為1外，其余的數(shù)則為上一行中位于其左、右的兩數(shù)之和(如圖310所示）。55陽山書屋分析第 i 行元素與第 i+1行元素的關(guān)系目的是從前一行的數(shù)據(jù)可以計(jì)算下一行的數(shù)據(jù)56陽山書屋從第 i 行數(shù)據(jù)計(jì)算并存放第 i+1 行數(shù)據(jù)57陽山書屋#define MAXSIZE 10 /*定義隊(duì)列的最大長度*/#includetypedef int datatype;typedef struct int dataMAXSIZE; int front; int rear;SeqQueue; 58陽山書屋SeqQueue *InitQueue() SeqQueue *q; q=(SeqQueue*)malloc(sizeof(SeqQueue); q-front=q-rear=0; return q; 59陽山書屋void EnQueue(SeqQueue *q,datatype x) if(q-rear+1