1、實用文案棧的順序表示和實現2.2基礎實驗2.2.1實驗目的（1）掌握棧的順序表示和實現（2）掌握棧的鏈式表示和實現（3）掌握隊列的順序表示和實現（4）掌握隊列的鏈式表示和實現2.2.2實驗內容實驗一：棧的順序表示和實現【實驗內容與要求】編寫一個程序實現順序棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能:（1）初始化順序棧（2 ）插入元素（3）刪除棧頂元素（4）取棧頂元素（5）遍歷順序棧（6）置空順序棧【知識要點】棧的順序存儲結構簡稱為順序棧，它是運算受限的順序表。對于順序棧，入棧時，首先判斷棧是否為滿，棧滿的條件為：p->top= =MAXNUM-1，棧滿時，不能入棧;否則岀

2、現空間溢岀，引起錯誤，這種現象稱為上溢。岀棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產生錯誤。通常棧空作為一種控制轉 移的條件。注意：（1）順序棧中元素用向量存放（2）棧底位置是固定不變的，可設置在向量兩端的任意一個端點（3） 棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top （通常稱top為棧頂指針）來指示 當前棧頂位置【實現提示】/*定義順序棧的存儲結構*/typedef struct ElemType stackMAXNUM;int top;SqStack;/*初始化順序棧函數*/void lnitStack(SqStack *p)q=(SqStack*)mallo

3、c(sizeof(SqStack)/* 申請空間 */)/*入棧函數*/void Push(SqStack *p,ElemType x) if(p->top<MAXNUM-1)p->top=p->top+1;/* 棧頂 +1*/p->stackp->top=x; /* 數據入棧 */*岀棧函數*/ElemType Pop(SqStack *p)x=p->stackp->top; /*將棧頂元素賦給 x*/p->top=p->top-1; /* 棧頂-1*/*獲取棧頂元素函數*/ElemType GetTop(SqStack *p) x

4、=p_>stackp_>top;/*遍歷順序棧函數*/void OutStack(SqStack *p) for(i=p->top;i>=0;i-)printf("第 %d 個數據元素是：%6dn",i,p->stacki);/*置空順序棧函數*/void setEmpty(SqStack *p) p->top= -1;【參考程序】#include<stdio.h>#include<stdlib.h>#define MAXNUM 20#define ElemType int/*定義順序棧的存儲結構*/typedef

5、 struct ElemType stackMAXNUM;int top;SqStack;/*初始化順序棧*/void InitStack(SqStack *p) if(!p)printf("Eorror");p_>top=_1;/*入棧*/void Push(SqStack *p,ElemType x) if(p->top<MAXNUM-1) p->top=p->top+1;p->stackp->top=x;elseprintf("Overflow!n");/*出棧*/ElemType Pop(SqStack

6、*p) ElemType x;if(p->top!=0) x=p->stackp->top;n “,p_>stackp_>top);printf("以前的棧頂數據元素%d已經被刪除!p->top=p->top-1;return(x);else printf("Underflow!n");return(O);/*獲取棧頂元素*/ElemType GetTop(SqStack *p) ElemType x;if(p->top!=0) x=p->stackp->top;return(x);else printf

7、("Underflow!n");return(0);/*遍歷順序棧*/void OutStack(SqStack *p) int i;printf("n");if(p->top<0)printf("這是一個空棧！");printf("n");for(i=p_>top;i>=0;i_)printf(” 第 %d 個數據元素是：%6dn",i,p->stacki);/*置空順序棧*/void setEmpty(SqStack *p)p->top= -1;/*主函數*/mai

8、n() SqStack *q;int y,cord;ElemType a;doprintf("n");printf("第一次使用必須初始化！n");printf("n");printf("n主菜單n"printf("n1初始化順序棧n");printf("n2插入一個元素n");printf("n3刪除棧頂元素n");printf("n4取棧頂元素n");printf("n5置空順序棧n");printf("

9、;n6結束程序運行n");printf("nn");printf("請輸入您的選擇(1,2, 3, 4, 5,6)");scanf("%d", &cord);printf("n");switch(cord) case 1: q=(SqStack*)malloc(sizeof(SqStack);InitStack(q);OutStack(q);break;case 2: printf("請輸入要插入的數據元素：a=");scanf("%d", &a);

10、Push(q,a);OutStack(q);break;case 3: Pop(q);OutStack(q);break;case 4: y=GetTop（q）;printf（"n棧頂元素為：dn",y）;OutStack（q）;break;case 5: setEmpty（q）;printf（"n順序棧被置空！n"）;OutStack（q）;break;case 6:exit（0）;while （cord<=6）;【思考與提高】（1 ）讀棧頂元素的算法與退棧頂元素的算法有何區別？（2）如果一個程序中要用到兩個棧，為了不發生上溢錯誤，就必須給每個棧

11、預先分配一個足夠大的存 儲空間。若每個棧都預分配過大的存儲空間，勢必會造成系統空間緊張。如何解決這個問題？實驗二：棧的鏈式表示和實現【實驗內容與要求】編寫一個程序實現鏈棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：（1）初始化鏈棧（2 ）鏈棧置空（3）入棧（4）出棧（5）取棧頂元素（6 ）遍歷鏈棧【知識要點】鏈棧是沒有附加頭結點的運算受限的單鏈表。棧頂指針就是鏈表的頭指針。注意：（1） LinkStack結構類型的定義可以方便地在函數體中修改top指針本身（2） 若要記錄棧中元素個數，可將元素個數屬性放在LinkStack類型中定義。（3）鏈棧中的結點是動態分配的，所以可以不考慮

12、上溢。【實現提示】typedef int Elemtype;typedef struct stacknode Elemtype data;stacknode * next;StackNode;/*定義鏈棧*/typedef struct stacknode * top; /棧頂指針LinkStack;/*初始化鏈棧函數*/void lnitStack(LinkStack * s) s=(LinkStack *)malloc(sizeof(LinkStack);/*初始化申請空間 */s->top=NULL;/*鏈棧置空函數*/void setEmpty(LinkStack * s) s-

13、>top=NULL;/*入棧函數*/void pushLstack(LinkStack * s, Elemtype x) p=(StackNode *)malloc(sizeof(StackNode); /建立一個節點。p_>data=x;p->next=s->top;/ 指向棧頂。s->top=p;/ 插入/*岀棧函數*/Elemtype popLstack(LinkStack * s)x=p_>data;s->top=p->next;/當前的棧頂指向原棧的nextfree(p);/ 釋放/*取棧頂元素函數*/Elemtype StackTop

14、(LinkStack *s) return s->top->data;/*遍歷鏈棧函數*/void Disp(LinkStack * s)while (p!=NULL)printf("%dn",p->data);p=p->next;【參考程序】#include "stdio.h"#include "malloc.h"#include "stdlib.h"typedef int Elemtype;typedef struct stacknode Elemtype data;stacknode

15、* next;StackNode;typedef struct stacknode * top; /棧頂指針LinkStack;/*初始化鏈棧*/void lnitStack(LinkStack * s) s->top=NULL;printf("n已經初始化鏈棧！n");/*鏈棧置空*/void setEmpty(LinkStack * s) s->top=NULL;printf("n 鏈棧被置空！ n");/*入棧*/void pushLstack(LinkStack * s, Elemtype x) StackNode * p;p=(St

16、ackNode *)malloc(sizeof(StackNode); /建立一個節點。p_>data=x;p->next=s->top;/由于是在棧頂 pushLstack，所以要指向棧頂。s->top=p;/ 插入/*出棧*/Elemtype popLstack(LinkStack * s) Elemtype x;StackNode * p;p=s->top;/指向棧頂if (s->top =0) printf("n棧空，不能出棧！n");exit(-1);x=p->data;s->top=p->next;/當前的棧

17、頂指向原棧的nextfree(p);/ 釋放return x;/*取棧頂元素*/Elemtype StackTop(LinkStack *s) if (s->top =0) printf("n 鏈棧空 n");exit(-1);return s->top->data;/*遍歷鏈棧*/void Disp(LinkStack * s) printf("n鏈棧中的數據為：n");printf("=n"); StackNode * p;p=s->top;while (p!=NULL) printf("%dn&

18、quot;,p->data);p=p->next; printf("=n");nn");void main()printf("=鏈棧操作=int i,m,n,a;LinkStack * s;s=(LinkStack *)malloc(sizeof(LinkStack);int cord;do printf("n");printf("第一次使用必須初始化！n");printf("n");printf("n主菜單n"printf("n1初始化鏈棧n"

19、;);printf("n2入棧n");printf("n3出棧n");printf("n4取棧頂元素n");printf("n5置空鏈棧n");printf("n6結束程序運行n");printf("nn");printf("請輸入您的選擇(1,2, 3, 4, 5,6)"); scanf("%d", &cord);printf("n");switch(cord) case 1: InitStack(s);D

20、isp(s);break;case 2:printf(”輸入將要壓入鏈棧的數據的個數：n=");scanf("%d",&n);printf("依次將%d個數據壓入鏈棧：n",n);for(i=1;i<=n;i+)scanf("%d",& a);pushLstack(s,a);Disp(s);break;case 3: printf("n 出棧操作開始!n");printf("輸入將要出棧的數據個數：m=");scanf("%d",&m)

21、;for(i=1;i<=m;i+)printf("n第%d 次出棧的數據是：%d",i,popLstack(s);Disp(s);break;case 4: printf("nn鏈棧的棧頂元素為：dn",StackTop(s);printf("n");break;case 5: setEmpty(s);Disp(s);break;case 6:exit(0);while (cord<=6);【思考與提高】(1) 棧的兩種存儲結構在判別棧空與棧滿時，所依據的條件有何不同？(2) 在程序中同時使用兩個以上的棧時，使用順序棧共享

22、鄰接空間則很難實現，能否通過鏈棧來方便 地實現？如何實現？實驗三：隊列的順序表示和實現【實驗內容與要求】編寫一個程序實現順序隊列的各種基本運算，并在此基礎上設計一個主程序，完成如下功能:(1) 初始化隊列(2) 建立順序隊列(3) 入隊(4) 出隊(5) 判斷隊列是否為空(6) 取隊頭元素(7 )遍歷隊列【知識要點】隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表。入隊時，將新元素插入rear所指的位置，然后將rear加1。出隊時，刪去front所指的元素，然后將front 加1并返回被刪元素。順序隊列中的溢岀現象：(1) "下溢”現象。當隊列為空時，做岀隊運算產生的

23、溢岀現象。“下溢”是正常現象，常用作程序控 制轉移的條件。(2) "真上溢”現象。當隊列滿時，做進棧運算產生空間溢岀的現象。“真上溢”是一種岀錯狀態，應 設法避免。(3) "假上溢"現象。由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小于向量空間的規模時，也可能由于尾指針已超越向量空間的上界 而不能做入隊操作。該現象稱為”假上溢"現象。注意：(1) 當頭尾指針相等時，隊列為空。(2) 在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。【實現提示】/*定義隊列*/typed

24、ef struct Elemtype queueMAXNUM;int front;int rear;sqqueue;/*隊列初始化函數*/int initQueue(sqqueue *q)q=(sqqueue*)malloc(sizeof(sqqueue);/*初始化申請空間 */q_>front=_1;q->rear=-1;/*入隊函數*/int append(sqqueue *q, Elemtype x) q_>rear+;q_>queueq_>rear=x;/*出隊函數*/Elemtype Delete(sqqueue *q) x=q_>queue+q

25、_>front;/*判斷隊列是否為空函數*/int Empty(sqqueue *q) if (q->front=q->rear) return TRUE;/*取隊頭元素函數*/int gethead(sqqueue *q)return(q->queueq->front+1);/*遍歷隊列函數*/void display(sqqueue *q) while(s<q->rear)s=s+1;printf("%d<-", q->queues); /*建立順序隊列函數*/void Setsqqueue(sqqueue *q)

26、for (i=0;i<n;i+) /*利用循環快速輸入數據*/ scanf("%d",&m);append(q,m); /*利用入隊函數快速輸入數據*/【參考程序】#include <stdio.h>#include <malloc.h>#define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE 0typedef struct Elemtype queueMAXNUM;int front;int rear;sqqueue;/*隊列初始化*/int initQueue

27、(sqqueue *q) if(!q) return FALSE; q->front=-1;q->rear=-1;return TRUE;/*入隊*/int append(sqqueue *q, Elemtype x) if(q->rear>=MAXNUM-1) return FALSE;q->rea 葉+;q_>queueq_>rear=x;return TRUE;/*出隊*/Elemtype Delete(sqqueue *q) Elemtype x;if (q->front=q->rear) return 0;x=q->queu

28、e+q->front;return x;/*判斷隊列是否為空*/int Empty(sqqueue *q) if (q->front=q->rear) return TRUE;return FALSE;/*取隊頭元素*/int gethead(sqqueue *q) if (q->front=q->rear) return 0;return(q->queueq->front+1);/*遍歷隊列*/void display(sqqueue *q) int s;s=q->front;if (q->front=q->rear)printf(

29、"隊列空!n");elseprintf("n順序隊列依次為：”)；while(s<q->rear)s=s+1;printf("%d<-", q->queues);printf("n");printf("順序隊列的隊尾元素所在位置 ：rear=%dn",q->rear); printf("順序隊列的隊頭元素所在位置 :front=%dn",q->front);/*建立順序隊列*/void Setsqqueue(sqqueue *q) int n,i,m;printf("n 請輸入將要入順序隊列的長度:");scanf("%d",&n);printf("n 請依次輸入入順序隊列的元素值:n");for (i=0;i<n;i+)scanf("%d",