1、實用文案棧的順序表示和實現(xiàn)2.2基礎(chǔ)實驗2.2.1實驗?zāi)康?1)掌握棧的順序表示和實現(xiàn)(2)掌握棧的鏈?zhǔn)奖硎竞蛯崿F(xiàn)(3)掌握隊列的順序表示和實現(xiàn)(4)掌握隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.2.2實驗內(nèi)容實驗一：棧的順序表示和實現(xiàn)【實驗內(nèi)容與要求】編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能：(1)初始化順序棧(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧【知識要點】棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的順序表。對于順序棧，入棧時，首先判斷棧是否為滿，棧滿的條件為：p->top= =MAXNUM-1棧滿時，不能入棧否則出現(xiàn)空間

2、溢出，引起錯誤，這種現(xiàn)象稱為上溢。出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。通常棧空作為一種控制轉(zhuǎn) 移的條件。注意：(1)順序棧中元素用向量存放(2)棧底位置是固定不變的，可設(shè)置在向量兩端的任意一個端點(3)棧頂位置是隨著進(jìn)棧和退棧操彳而變化的，用一個整型量top (通常稱top為棧頂指針)來指示當(dāng)前棧頂位置【實現(xiàn)提示】/*定義順序棧的存儲結(jié)構(gòu)*/typedef struct ElemType stackMAXNUM;標(biāo)準(zhǔn)文檔實用文案int top;SqStack;/*初始化順序棧函數(shù)*/void InitStack(SqStack *p)q=(SqStack*)ma

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

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

5、 struct ElemType stackMAXNUM;int top;SqStack;/*初始化順序棧*/void InitStack(SqStack *p) if(!p)printf("Eorror");p->top=-1;/*入棧*/標(biāo)準(zhǔn)文檔實用文案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("以前的棧頂數(shù)據(jù)元素d已經(jīng)被刪除！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 個數(shù)據(jù)元素是：6dn",i,p->stacki);標(biāo)準(zhǔn)文檔實用文案/*置空順序棧*/void setEmpty(SqStack *p)p-&g

8、t;top= -1;/*主函數(shù)*/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結(jié)束程序運(yùn)行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("請輸入要插入的數(shù)據(jù)元素：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);標(biāo)準(zhǔn)文檔實用文案break;case 5:順序棧被置空！ n"); setEmpty(q);printf("nOutStack(q);break;case 6:exit(0);while (cord<=6);【思考與提高】(1)讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？(2)如果一個程序中要用

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

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

13、y(LinkStack * s) s->top=NULL;/*入棧函數(shù)*/void pushLstack(LinkStack * s, Elemtype x) p=(StackNode *)malloc(sizeof(StackNode); / p->data=x;p->next=s->top; / 指向棧頂。s->top=p; /插入/*出棧函數(shù)*/Elemtype popLstack(LinkStack * s)x=p->data;s->top=p->next; /當(dāng)前的棧頂指向原棧的free(p); /釋放初始化申請空間*/建立一個節(jié)點。n

14、ext/*取棧頂元素函數(shù)*/Elemtype StackTop(LinkStack *s) return s->top->data;/*遍歷鏈棧函數(shù)*/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 標(biāo)準(zhǔn)文檔實用文案Elemtype data;stacknode * next;StackNode;typedef struct stacknode * top; /棧頂指針LinkStack;/*初始化鏈棧*/void InitStack(LinkStack * s) s->top=NULL;printf("n已經(jīng)初始化鏈棧！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); /建立一個節(jié)點。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; /當(dāng)前的棧頂指向原棧的nextfree(p); /釋放return x;/*取棧頂元素*/Elemtype StackTop(LinkStack *s) if (s->top =0) printf("n鏈棧空 n");exit(-1);標(biāo)準(zhǔn)文檔實用文案return s->top->data;)/*遍歷鏈棧*/void Disp(LinkStack * s) printf("n鏈棧中的數(shù)據(jù)為：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結(jié)束程序運(yùn)行 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("輸入將要壓入鏈棧的數(shù)據(jù)的個數(shù)：n=");scanf("%d",&n);printf("依次將d個數(shù)據(jù)壓入鏈棧：n",n);for(i=1;i<=n;i+)標(biāo)準(zhǔn)文檔實用文案scanf("%d",&a);pushLstack(s,a);Disp(s)；break;case 3: printf("n出棧操作開始！n&qu

21、ot;);printf("輸入將要出棧的數(shù)據(jù)個數(shù)：m=");scanf("%d",&m);for(i=1;i<=m;i+)printf("n第d 次出棧的數(shù)據(jù)是：%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)棧的兩種存儲結(jié)構(gòu)在判別棧空與棧滿時，所依據(jù)的條件有何不同？(2)在程序中同時使用兩個以上的棧時，使用順序棧共享鄰接空間則很難實現(xiàn)，能否通過鏈棧來方便 地實現(xiàn)？如何實現(xiàn)？實驗三：隊列的順序表示和實現(xiàn)【實驗內(nèi)容與要求】編寫一個程序?qū)崿F(xiàn)順序隊列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能:(1)初始化隊列(2)建立順序隊列(3)入隊(4)出隊(5)判斷隊列是否為空標(biāo)準(zhǔn)文檔實用文案(6)取隊頭元素(7)遍歷隊列【知識要點】隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運(yùn)算受限的順序表。入隊時，將新元素插入rear所指的位置，然后將 rear加1。出隊時，刪去front

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

24、：(1)當(dāng)頭尾指針相等時，隊列為空。(2)在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。【實現(xiàn)提示】/*定義隊列*/typedef struct Elemtype queueMAXNUM;int front;int rear;sqqueue;/*隊列初始化函數(shù)*/int initQueue(sqqueue *q)q=(sqqueue*)malloc(sizeof(sqqueue);/* 初始化申請空間 */q->front=-1;q->rear=-1;/*入隊函數(shù)*/int append(sqqueue *q, Elemtype x) q->rea

25、r+;q->queueq->rear=x;/*出隊函數(shù)*/Elemtype Delete(sqqueue *q) x=q->queue+q->front;/*判斷隊列是否為空函數(shù)*/int Empty(sqqueue *q) if (q->front=q->rear) return TRUE;標(biāo)準(zhǔn)文檔實用文案/*取隊頭元素函數(shù)*/int gethead(sqqueue *q)return(q->queueq->front+1);/*遍歷隊列函數(shù)*/void display(sqqueue *q) while(s<q->rear)s=s

26、+1;printf("%d<-", q->queues); /*建立順序隊列函數(shù)*/void Setsqqueue(sqqueue *q) for (i=0;i<n;i+)/*利用循環(huán)快速輸入數(shù)據(jù)*/ scanf("%d",&m);append(q,m); /*利用入隊函數(shù)快速輸入數(shù)據(jù) */【參考程序】#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)標(biāo)準(zhǔn)文檔實用文案 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