數(shù)據(jù)結構高職學習資料

1、書名：數(shù)據(jù)結構ISBN： 978-7-111-49031-9出版社：機械工業(yè)出版社本書配有電子課件1第三章棧和隊列本章要點棧和隊列的定義、特點棧和隊列基本操作算法的實現(xiàn)棧和隊列的應用33.1 棧3.1.1 棧的定義及基本運算 棧是限制在表的一端進行插入和刪除操作的線性表。允許插入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。當表中沒有元素時稱為空棧。常做的基本運算有：（1）棧初始化：Init_SeqStack(s)初始條件：棧s不存在操作結果：構造了一個空棧。（2）判?？眨篍mpty_SeqStack(s)初始條件：棧s已存在操作結果：若s為空棧返回為1，否則返回為0。（3）入棧： Push_

2、SeqStack(s，x)初始條件：棧s已存在 操作結果：在棧s的頂部插入一個新元素x， x成為新的棧頂元素。棧發(fā)生變化。（4）出棧：Pop_SeqStack(s)初始條件：棧s存在且非空操作結果：棧s的頂部元素從棧中刪除，棧中少了一個元素。（5）取棧頂元素：Get_SeqStack (s)初始條件：棧s存在且非空操作結果：棧頂元素作為結果返回，棧不變化。3.1.2 棧的存儲實現(xiàn)和運算實現(xiàn)1順序棧利用順序存儲方式實現(xiàn)的棧稱為順序棧。順序棧的類型描述如下：#define MaxSize 50 typedef struct Datatype dataMaxSize; int top; SeqSta

3、ck定義一個指向順序棧的指針：SeqStack *s;通常0下標端設為棧底，這樣空棧時棧頂指針top=-1; 入棧時，棧頂指針加，即s-top+; 出棧時，棧頂指針減，即s-top-。棧操作的示意圖如圖3-2所示。圖(a)是空棧，圖(c)是A、B、C、D、E 5個元素依次入棧之后，圖(d)是在圖(c)之后E、D相繼出棧，此時棧中還有3個元素，通過這個示意圖要深刻理解棧頂指針的作用。（1）初始化空棧初始條件：棧不存在。操作結果：構造一個空棧。 操作步驟：創(chuàng)建一個SeqStack類型的結構體指針s，并返回指針s。算法3.1如下：void Init_SeqStack(SeqStack *s) /算法

4、3.1s-top = 0;（2）判斷空棧初始條件：棧存在。操作結果：判斷棧是否為空。 操作步驟：判斷棧s是否為空，如果為空返回1，否則返回0。算法3.2如下：int Empty_SeqStack(SeqStack *s) if (s-top= = 0) return 1; else return 0;（3）入棧初始條件：棧s存在。操作結果：在棧s的頂部插入一個新元素x， x成為新的棧頂元素。int Push_SeqStack (SeqStack *s, Datatype x) if(s-top = MaxSize - 1) printf(溢出n); return 0; else s-datas

5、-top = x; s-top+; return 1; （4）出棧初始條件：棧s存在。操作結果：棧s的頂部元素從棧中刪除。Datatype Pop_SeqStack(SeqStack *s) Datatype x; if(Empty_SeqStack (s) printf(棧空n);x = 0; else s-top-; x = (s-data)s-top; return x; /*棧頂元素存入*x，返回*/ （5）取棧頂元素初始條件：棧s存在。操作結果：從棧s中取出棧頂元素。Datatype Get_SeqStack(SeqStack *s) if ( Empty_SeqStack ( s

6、) ) return 0; /*棧空*/ else return (s-data-s-top ); 2. 鏈棧 用鏈式存儲結構實現(xiàn)的棧稱為鏈棧。typedef struct node Datatype data;struct node *next;StackNode，* LinkStack;（1）置空棧 初始條件：棧不存在。操作結果：構造一個空棧。LinkStack Init_LinkStack（） LinkStack top=(LinkStack)malloc(sizeof(StackNode); top-next=NULL; return top; （2）判斷?？粘跏紬l件：棧存在。操作結果

7、：判斷棧是否為空。int Empty_LinkStack（LinkStack top ） if（top-next=NULL） return 1; else return 0; （3）入棧 初始條件：棧top存在。操作結果：在棧頂結點top后插入一新結點，新結點數(shù)據(jù)元素值為x。Push_LinkStack（LinkStack top, Datatype x） StackNode *s;s= (LinkStack) malloc（sizeof（StackNode）;s-data=x; s-next=top-next;top -next =s;（4）出棧初始條件：棧s存在。操作結果：棧s的頂部元素從

8、棧中刪除。Datatype Pop_LinkStack (LinkStack top, Datatype x) Datatype x; StackNode *p; if (top-next= =NULL) return 0; else p = top-next; x = p-data; top -next = pnext; free (p); return x; 3.2 棧的應用舉例【例3-1】編寫一個程序?qū)崿F(xiàn)以下順序棧上的各種基本操作，用一個主程序串成。（1）棧的初始化； （2）棧不滿的情況下元素進棧；（3）棧不空的情況下元素出棧；（4）輸出棧中元素；（5）計算棧中元素個數(shù)#include

9、#include#define add 43 #define subs 45 #define mult 42 #define div 47 #define MaxSize 100 typedef struct int dataMaxSize;/*用數(shù)組來表示?？臻g，定義長度為MaxSize的棧*/ int top; /*棧頂*/ SeqStack;typedef SeqStack *STK; typedef enumok,error Bool; SeqStack expStackNode; STK expSTK; STK Init_LinkStack(SeqStack *stack_zone)

10、/*執(zhí)行棧初始化，建棧指針*/ STK p; p=stack_zone; p-top=0; return p; Bool Push_LinkStack(int *term,STK pstk)/*將一結構型數(shù)據(jù)送入棧中*/ if(pstk-top=MaxSize) return error; /*棧滿，進棧失敗*/ pstk-datapstk-top =*term; (pstk-top)+;/*棧頂指針移動*/ return ok; Bool Empty_LinkStack(STK pstk)/*判斷棧是否為空棧*/ return(pstk-top=0); Bool Pop_LinkStack(

11、int *pdata, STK pstk)/*從棧中取出一結構型數(shù)據(jù)*/ if(Empty_LinkStack(pstk) return error; (pstk-top)-;/*退棧*/ *pdata =pstk-datapstk-top; return ok; int Eval(char tag,int a1,int a2) switch(tag) case add:return(a1+a2); break; case subs:return(a1-a2); break; case mult:return(a1*a2); break; case div:return(a1/a2); bre

12、ak; return ok; void main() char c; int opd1,opd2,temp,c1; expSTK=Init_LinkStack(&expStackNode); printf(n后置表達式: ); while(c=getchar()!= n ) if(c= ) continue; if(c47)&(c58) /*判斷是否是0-9的字符*/ putchar(c); c1=c-48; /*把輸入的字符型數(shù)字轉(zhuǎn)換成數(shù)字*/ if(Push_LinkStack(&c1,expSTK)=error)/*運算分量進棧*/ printf(n表達式太長n); exit(0); e

13、lse if(c=add)|(c=subs)|(c=mult)|(c=div) putchar(c); if(Pop_LinkStack(&opd1,expSTK)=error) /*將運算量1出棧*/ printf( n表達式語法錯！ );if(Pop_LinkStack(&opd2,expSTK)=error) /*將運算量2出棧*/ printf( n表達式語法錯！ ); temp=Eval(c,opd2,opd1);/*計算得到結果*/ Push_LinkStack(&temp,expSTK);/*將運算結果進棧*/ else printf( n表達式語法錯！ );/*出現(xiàn)非法字符*/

14、 /*while*/ if(Pop_LinkStack(&opd1,expSTK)=error) printf( n表達式語法錯！ ); if(!(Empty_LinkStack(expSTK) printf( n表達式語法錯！ ); printf(=%-3dn,opd1); 【例3-2】數(shù)制轉(zhuǎn)換問題。將十進制數(shù)N轉(zhuǎn)換為r進制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3456，r=8為例轉(zhuǎn)換方法如下：（3456）10 =（6563）8#include#includetypedef int Datatype;typedef struct node Datatype data;struct node

15、*next;StackNode, *LinkStack;LinkStack Init_LinkStack()/*初始化棧，算法3.6*/ LinkStack top=(LinkStack)malloc(sizeof(StackNode); top-next=NULL; return top; int Empty_LinkStack(LinkStack top) /*棧判空，算法3.7*/ if(top-next= NULL) return 1; else return 0; void Push_LinkStack(LinkStack top, Datatype x) /*壓棧，算法3.8*/

16、StackNode *s;s=(LinkStack)malloc(sizeof(StackNode);s-data=x; s-next=top-next;top-next=s; int Pop_LinkStack(LinkStack top)/*出棧，算法3.9*/ Datatype x; StackNode *p; if(top-next=NULL) return 0; else p=top-next; x=p-data; top-next=p-next; free (p); return x; void Conversion(int N,int r) /*進制的轉(zhuǎn)換*/ LinkStack

17、 s=Init_LinkStack();/*調(diào)用算法3.6，初始化棧*/ printf (轉(zhuǎn)換后的結果是:,N,r); while(N) Push_LinkStack(s,N%r); /*調(diào)用算法3.8，壓棧*/ N=N/r; while(!Empty_LinkStack(s) /*調(diào)用算法3.7判斷棧是否空*/ printf (%d ,Pop_LinkStack(s); /*調(diào)用算法3.9，出棧*/ printf (n ); void main()int i,r;printf(請輸入待換的數(shù)據(jù));scanf(%d,&i);printf(請輸入轉(zhuǎn)換后的進制); scanf(%d,&r); Co

18、nversion(i,r);3.3 隊列3.3.1 隊列的定義及基本運算 前面所講的棧是一種“后進先出”的數(shù)據(jù)結構，而在實際中還有一種“先進先出” (FIFO-First In First Out)的數(shù)據(jù)結構：即插入操作在表一端進行，而刪除操作在表的另一端進行，這種數(shù)據(jù)結構稱為 隊列，把允許插入的一端稱為隊尾(rear) ，把允許刪除的一端稱為隊頭(front)。如圖3-4所示是一個有5 個元素的隊列。入隊的順序依次為：a1、 a2 、a3 、a4 、 a5 出隊的順序依然是：a1、 a2 、a3 、a4 、 a5 隊列是一種運算受限制的線性表，在隊列上進行的基本操作有：（1）隊列初始化：In

19、it_Queue(q) 初始條件：隊列不存在。 操作結果：構造一個空隊列。（2）入隊操作： In_Queue(q,x), 初始條件：隊列q存在。 操作結果：對已存在的隊列q，插入一個元素x到隊尾位 置。（3）出隊操作：Out_Queue(q,x) 初始條件：隊q存在且非空 操作結果：刪除隊首元素，其值用x返回。3.3.2 隊列的存儲實現(xiàn)及運算實現(xiàn)（1）順序隊列#define MaxSize 50 /*隊列的最大容量*/typedef struct Datatype dataMaxSize; /*隊員的存儲空間*/ int front , rear; /*隊頭隊尾指針*/ SeQueue;定義一

20、個指向隊列的指針變量： SeQueue *q; 隊列的數(shù)據(jù)區(qū)為：q-data0-q-dataMaxSize -1 隊頭指針：q-front 隊尾指針：q-rear 采用順序存儲結構的隊列稱為順序隊。因為隊列的隊頭和隊尾都是可以進行操作，因此設有隊頭、隊尾兩個指針。順序隊列的類型定義如下： 設隊頭指針指向隊頭元素，隊尾指針指向隊尾元素的下一個位置，置空隊則為：q-front=q-rear=0。 在不考慮溢出的情況下，元素入隊，入隊操作后將隊尾指針加1，指向新位置。操作如下：q-dataq-rear=x; /*插入的元素x賦值給隊尾元素*/q-rear+; 在不考慮隊空的情況下，出隊操作將隊頭指針

21、加1，表明隊頭元素出隊。操作如下：x=q-dataq-front;q-front+;隊中元素的個數(shù)：m=(q-rear)-(q-front);隊滿時：m= MaxSize； 隊空時：m=0。(a) 空隊列rontrear入隊3個元素a3a2a1frontrear(c) 出隊3個元素frontrear(d) 入隊2個元素a5a4frontrear圖3-5 隊列示意圖 從圖中可以看到，隨著入隊出隊的進行，會使整個隊列整體向后移動，這樣就出現(xiàn)了圖3-5(d)中的現(xiàn)象：隊尾指針已經(jīng)移到了最后,再有元素入隊就會出現(xiàn)溢出，而事實上此時隊中并未真的“滿員”，這種現(xiàn)象為“假溢出”，這是由于“隊尾入隊頭出”這種

22、受限制的操作所造成。解決假溢出的方法之一是將隊列的數(shù)據(jù)區(qū)data0.MaxSize-1看成頭尾相接的循環(huán)結構，頭尾指針的關系不變，將其稱為“循環(huán)隊列”，“循環(huán)隊列”的示意圖如圖3-6所示，頭尾相接的循環(huán)結構。圖3-6循環(huán)隊列示意圖入隊時的隊尾指針加1操作修改為：q-rear=(q-rear+1) % MaxSize;出隊時的隊頭指針加1操作修改為：q-front=(q-front+1) % MaxSize; 設有循環(huán)隊列，其初始狀態(tài)是front=rear=0，各種操作后隊列的頭、尾指針的狀態(tài)變化情況如下圖3-7所示。 123450(a) 空隊列frontrear123450(b) d, e,

23、b, g入隊frontdebgrear123450(c) d, e出隊bgfrontrear 入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，無法通過front=rear來判斷隊列“空”還是“滿”。123450(d)i, j, k入隊bgfrontijkrear123450(e) b, g出隊ijkrearfront123450(f) r, p, s, t入隊ijkfrontrprear圖3-7 循環(huán)隊列操作及指針變化情況 就是說“隊滿”和“隊空”的條件是相同的了，front=rear。這是必須要解決的問題。 方法一：附設一個存儲隊中元素個數(shù)的變量如

24、num，當num=0時隊空，當num=MaxSize時為隊滿。 方法二：少用一個元素空間，如3-7圖（f）所示的情況就視為隊滿，也就是說，隊滿時還有一空閑單元，不能再增加元素，此時的狀態(tài)：隊尾指針rear+1就會從后面趕上隊頭指針。這種情況下隊滿的條件是：(rear+1) % MaxSize=front，能和隊空front=rear條件區(qū)分開。（1） 置空隊初始條件：隊列不存在。操作結果：構造一個空隊列。void Init_Queue(SeQueue *q) q-front=q-rear=0; （2）入隊初始條件：隊q存在。操作結果：對已存在的隊列q，插入一個元素x到隊尾。void In_Qu

25、eue(SeQueue *q, Datatype e) if(q-rear+1)%MaxSize=q-front) printf(隊滿); else q-dataq-rear=e; q-rear=(q-rear+1)%MaxSize; （3）出隊 初始條件：隊列q存在。 操作結果：刪除隊首元素，并返回其值。 int Out_Queue(SeQueue *q, Datatype *e) if(q-front=q-rear) printf(隊空); return 0; /*隊空不能出隊*/ else *e=q-data q-front; /*讀出隊頭元素*/ q-front=(q-front+1)

26、%MaxSize; return 1; /*出隊完成*/ 2. 鏈隊 采用鏈式存儲結構的隊稱為鏈隊。和鏈棧類似，用單鏈表來實現(xiàn)鏈隊，根據(jù)隊列的FIFO原則，為了操作上的方便，我們分別需要一個頭指針和尾指針，如圖3-8所示。 圖3-8 鏈隊示意圖 圖3-8中頭指針front和尾指針rear是兩個獨立的指針變量，從結構性上考慮，通常將二者封裝在一個結構中。鏈隊的描述如下： typedef struct node Datatype data; struct node *next; QNode; /*鏈隊結點的類型*/typedef struct QNnode *front,*rear; LQueue

27、; /*將頭尾指針封裝在一起的鏈隊*/ 定義一個指向鏈隊的指針：LQueue *q;按這種思想建立的帶頭結點的鏈隊如圖3-9所示。圖3-9 頭尾指針封裝在一起的鏈隊（1）創(chuàng)建一個帶頭結點的空隊：初始條件：隊列不存在。操作結果：構造一個空隊列。void Init_LQueue(LQueue *q) /*鏈隊列初始化*/q-front = (QNode*)malloc(sizeof(QNode);q-front-next = NULL;q-rear = q-front;（2）入隊初始條件：隊q存在。操作結果：對已存在的隊列q，插入一個元素x到隊尾。int In_LQueue(LQueue *q,

28、Datatype x)/*元素x 入隊列*/ QNode *s;s=(QNode*)malloc(sizeof(QNode);if(s!=NULL) s-data = x;s-next = NULL;q-rear-next=s;q-rear=s;return 1;else return 0;（3）判隊空初始條件：隊列q存在。操作結果：若q為空隊則返回為1，否則返回為0。int Empty_LQueue( LQueue *q) if (q-front=q-rear) return 1; else return 0; （4）出隊初始條件：隊列q存在。操作結果：刪除隊首元素，并返回其值。int De

29、l_LQueue(LQueue *q, Datatype *e) /*刪除隊頭元素并返回*/ QNode *p; if(Empty_LQueue(q) printf(隊列空n);return 0; else p =q-front-next; q-front-next = p-next;if(p-next = NULL) q-rear = q-front; *e = p-data; free(p); return 1;【例3-3】利用隊的順序存儲結構，實現(xiàn)隊列插入，刪除的功能。#include#include #include#define MaxSize 10 /*隊列的最大容量*/typedef struct int aMaxSize; /*隊員的存儲空間*/ int front, rear; /*隊頭隊尾指針*/SeQueue;SeQueue QL;void Init_Queue(SeQueue *q)/*初始化隊列，算法3.10*/ q-front=0;q-rear=0; void Disp_Queue(SeQueue *q)char