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 InitStack(SqStack *p)q=(SqStack*)ma

3、lloc(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)

4、 x=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(

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

7、else printf("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-&g

8、t;top= -1;/*主函數*/main() 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&quo

9、t;);printf("n6結束程序運行n"printf("n-n");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&q

10、uot;,&a);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:順序棧被置空！ n"); setEmpty(q);printf("nOutStack(q);break;case 6:exit(0);while (cord<=6);【思考與提高】(1)讀棧頂元素的算法與退棧頂元素的算法有何區別？(2)如果一個程序中要用

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

12、鏈棧中的結點是動態分配的，所以可以不考慮上溢。【實現提示】typedef int Elemtype;typedef struct stacknode Elemtype data;標準文檔實用文案stacknode * next;StackNode;/*定義鏈棧*/typedef struct stacknode * top; /棧頂指針LinkStack;/*初始化鏈棧函數*/void InitStack(LinkStack * s) s=(LinkStack *)malloc(sizeof(LinkStack);/* s->top=NULL;/*鏈棧置空函數*/void setEmpt

13、y(LinkStack * s) s->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; /當前的棧頂指向原棧的free(p); /釋放初始化申請空間*/建立一個節點。n

14、ext/*取棧頂元素函數*/Elemtype StackTop(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 stacknod

15、e 標準文檔實用文案Elemtype data;stacknode * next;StackNode;typedef struct stacknode * top; /棧頂指針LinkStack;/*初始化鏈棧*/void InitStack(LinkStack * s) s->top=NULL;printf("n已經初始化鏈棧！n");/*鏈棧置空*/void setEmpty(LinkStack * s) s->top=NULL;printf("n 鏈棧被置空！ n");/*入棧*/void pushLstack(LinkStack *

16、s, Elemtype x) StackNode * p;p=(StackNode *)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);

17、x=p->data;s->top=p->next; /當前的棧頂指向原棧的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 *

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

19、rintf("n主菜單n");printf("n 1初始化鏈棧 n");printf("n 2入棧n");printf("n 3出棧n");printf("n 4取棧頂元素 n");printf("n 5置空鏈棧n");printf("n 6結束程序運行 n");printf("nn");printf("請輸入您的選擇(1,2, 3, 4, 5,6)");scanf("%d",&cord)

20、;printf("n");switch(cord) case 1: InitStack(s);Disp(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&qu

21、ot;);printf("輸入將要出棧的數據個數：m=");scanf("%d",&m);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);

22、【思考與提高】(1)棧的兩種存儲結構在判別棧空與棧滿時，所依據的條件有何不同？(2)在程序中同時使用兩個以上的棧時，使用順序棧共享鄰接空間則很難實現，能否通過鏈棧來方便 地實現？如何實現？實驗三：隊列的順序表示和實現【實驗內容與要求】編寫一個程序實現順序隊列的各種基本運算，并在此基礎上設計一個主程序，完成如下功能:(1)初始化隊列(2)建立順序隊列(3)入隊(4)出隊(5)判斷隊列是否為空標準文檔實用文案(6)取隊頭元素(7)遍歷隊列【知識要點】隊列的順序存儲結構稱為順序隊列，順序隊列實際上是運算受限的順序表。入隊時，將新元素插入rear所指的位置，然后將 rear加1。出隊時，刪去front

23、所指的元素，然后將front力口 1并返回被刪元素。順序隊列中的溢出現象：(1)"下溢"現象。當隊列為空時，做出隊運算產生的溢出現象。“下溢”是正常現象，常用作程序控制轉移的條件。(2)"真上溢"現象。當隊列滿時，做進棧運算產生空間溢出的現象。“真上溢”是一種出錯狀態，應設法避免。(3)"假上溢"現象。由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法 重新利用。當隊列中實際的元素個數遠遠小于向量空間的規模時，也可能由于尾指針已超越向量空間的上界 而不能做入隊操作。該現象稱為"假上溢"現象。注意

24、：(1)當頭尾指針相等時，隊列為空。(2)在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。【實現提示】/*定義隊列*/typedef 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->rea

25、r+;q->queueq->rear=x;/*出隊函數*/Elemtype Delete(sqqueue *q) x=q->queue+q->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

26、+1;printf("%d<-", q->queues); /*建立順序隊列函數*/void Setsqqueue(sqqueue *q) 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

27、0typedef struct Elemtype queueMAXNUM;int front;int rear;sqqueue;/*隊列初始化*/int initQueue(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->rear+;q->queueq->rear=x;return TRUE;/*出隊*/Elem

28、type Delete(sqqueue *q)標準文檔實用文案 Elemtype x;if (q->front=q->rear) return 0;x=q->queue+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->fron

29、t+1);/*遍歷隊列*/void display(sqqueue *q) int s;s=q->front;if (q->front=q->rear)printf("隊列空！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