用順序結(jié)構(gòu)表示棧并實(shí)現(xiàn)棧的各種基本操縱

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

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

3、f(SqStack)/* 申請(qǐng)空間 */)/*入棧函數(shù)*/void Push(SqStack *p,ElemType x) if(p-toptop=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) x=p_stackp_top;/*遍歷順序棧函數(shù)*/void OutStack(SqStack *p) for(i=p-

4、top;i=0;i-)printf(第 %d 個(gè)數(shù)據(jù)元素是：%6dn,i,p-stacki);/*置空順序棧函數(shù)*/void setEmpty(SqStack *p) p-top= -1;【參考程序】#include#include#define MAXNUM 20#define ElemType int/*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedef struct ElemType stackMAXNUM;int top;SqStack;/*初始化順序棧*/void InitStack(SqStack *p) if(!p)printf(Eorror);p_top=_1;/*入棧*/void Pus

5、h(SqStack *p,ElemType x) if(p-toptop=p-top+1;p-stackp-top=x;elseprintf(Overflow!n);/*出棧*/ElemType Pop(SqStack *p) ElemType x;if(p-top!=0) x=p-stackp-top;n “,p_stackp_top);printf(以前的棧頂數(shù)據(jù)元素%d已經(jīng)被刪除!p-top=p-top-1;return(x);else printf(Underflow!n);return(O);/*獲取棧頂元素*/ElemType GetTop(SqStack *p) ElemType

6、 x;if(p-top!=0) x=p-stackp-top;return(x);else printf(Underflow!n);return(0);/*遍歷順序棧*/void OutStack(SqStack *p) int i;printf(n);if(p-toptop;i=0;i_)printf(” 第 %d 個(gè)數(shù)據(jù)元素是：%6dn,i,p-stacki);/*置空順序棧*/void setEmpty(SqStack *p)p-top= -1;/*主函數(shù)*/main() SqStack *q;int y,cord;ElemType a;doprintf(n);printf(第一次使用必

7、須初始化！n);printf(n);printf(n主菜單nprintf(n1初始化順序棧n);printf(n2插入一個(gè)元素n);printf(n3刪除棧頂元素n);printf(n4取棧頂元素n);printf(n5置空順序棧n);printf(n6結(jié)束程序運(yùn)行n);printf(nn);printf(請(qǐng)輸入您的選擇(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:

8、printf(請(qǐng)輸入要插入的數(shù)據(jù)元素：a=);scanf(%d, &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: setEmpty（q）;printf（n順序棧被置空！n）;OutStack（q）;break;case 6:exit（0）;while （cordtop=NULL;/*鏈棧置空函數(shù)*/void setEmpty(LinkStack * s) s-top=NULL;/*入

9、棧函數(shù)*/void pushLstack(LinkStack * s, Elemtype x) p=(StackNode *)malloc(sizeof(StackNode); /建立一個(gè)節(jié)點(diǎn)。p_data=x;p-next=s-top;/ 指向棧頂。s-top=p;/ 插入/*岀棧函數(shù)*/Elemtype popLstack(LinkStack * s)x=p_data;s-top=p-next;/當(dāng)前的棧頂指向原棧的nextfree(p);/ 釋放/*取棧頂元素函數(shù)*/Elemtype StackTop(LinkStack *s) return s-top-data;/*遍歷鏈棧函數(shù)*/v

10、oid Disp(LinkStack * s)while (p!=NULL) printf(%dn,p-data);p=p-next;【參考程序】#include stdio.h#include malloc.h#include stdlib.htypedef int Elemtype;typedef struct stacknode Elemtype data;stacknode * next;StackNode;typedef struct stacknode * top; /棧頂指針LinkStack;/*初始化鏈棧*/void lnitStack(LinkStack * s) s-to

11、p=NULL;printf(n已經(jīng)初始化鏈棧！n);/*鏈棧置空*/void setEmpty(LinkStack * s) s-top=NULL;printf(n 鏈棧被置空！ n);/*入棧*/void pushLstack(LinkStack * s, Elemtype x) StackNode * p;p=(StackNode *)malloc(sizeof(StackNode); /建立一個(gè)節(jié)點(diǎn)。p_data=x;p-next=s-top;/由于是在棧頂 pushLstack，所以要指向棧頂。s-top=p;/ 插入/*出棧*/Elemtype popLstack(LinkStack

12、 * s) Elemtype x;StackNode * p;p=s-top;/指向棧頂if (s-top =0) printf(n棧空，不能出棧！n);exit(-1);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);return s-top-data;/*遍歷鏈棧*/void Disp(LinkStack * s) printf(n鏈棧中的數(shù)據(jù)為：n);printf

13、(=n); StackNode * p;p=s-top;while (p!=NULL) printf(%dn,p-data);p=p-next; printf(=n);void main()nn);printf(=鏈棧操作=int i,m,n,a;LinkStack * s;s=(LinkStack *)malloc(sizeof(LinkStack);int cord;do printf(n);printf(第一次使用必須初始化！n);printf(n);printf(n主菜單nprintf(n1初始化鏈棧n);printf(n2入棧n);printf(n3出棧n);printf(n4取棧頂

14、元素n);printf(n5置空鏈棧n);printf(n6結(jié)束程序運(yùn)行n);printf(nn);printf(請(qǐng)輸入您的選擇(1,2, 3, 4, 5,6); scanf(%d, &cord);printf(n);switch(cord) case 1: InitStack(s);Disp(s);break;case 2:printf(”輸入將要壓入鏈棧的數(shù)據(jù)的個(gè)數(shù)：n=);scanf(%d,&n);printf(依次將%d個(gè)數(shù)據(jù)壓入鏈棧：n,n);for(i=1;i=n;i+)scanf(%d,& a);pushLstack(s,a);Disp(s);break;case 3: prin

15、tf(n 出棧操作開始!n);printf(輸入將要出棧的數(shù)據(jù)個(gè)數(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 (cordfront=-1;q-rear=-1;/*入隊(duì)函數(shù)*/int append(sqqueue *q, Elemtype x) q_r

16、ear+;q_queueq_rear=x;/*出隊(duì)函數(shù)*/Elemtype Delete(sqqueue *q) x=q_queue+q_front;/*判斷隊(duì)列是否為空函數(shù)*/int Empty(sqqueue *q) if (q-front=q-rear) return TRUE;/*取隊(duì)頭元素函數(shù)*/int gethead(sqqueue *q)return(q-queueq-front+1);/*遍歷隊(duì)列函數(shù)*/void display(sqqueue *q) while(srear)s=s+1;printf(%dqueues); /*建立順序隊(duì)列函數(shù)*/void Setsqqueue

17、(sqqueue *q) for (i=0;in;i+) /*利用循環(huán)快速輸入數(shù)據(jù)*/ scanf(%d,&m);append(q,m); /*利用入隊(duì)函數(shù)快速輸入數(shù)據(jù)*/【參考程序】#include #include #define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE 0typedef struct Elemtype queueMAXNUM;int front;int rear;sqqueue;/*隊(duì)列初始化*/int initQueue(sqqueue *q) if(!q) return FALSE;q-fro

18、nt=-1;q-rear=-1;return TRUE;/*入隊(duì)*/int append(sqqueue *q, Elemtype x) if(q-rear=MAXNUM-1) return FALSE;q-rea 葉+;q_queueq_rear=x;return TRUE;/*出隊(duì)*/Elemtype Delete(sqqueue *q) Elemtype x;if (q-front=q-rear) return 0;x=q-queue+q-front;return x;/*判斷隊(duì)列是否為空*/int Empty(sqqueue *q) if (q-front=q-rear) return

19、 TRUE;return FALSE;/*取隊(duì)頭元素*/int gethead(sqqueue *q) if (q-front=q-rear) return 0;return(q-queueq-front+1);/*遍歷隊(duì)列*/void display(sqqueue *q) int s;s=q-front;if (q-front=q-rear)printf(隊(duì)列空!n);elseprintf(n順序隊(duì)列依次為：”)；while(srear)s=s+1;printf(%dqueues);printf(n);printf(順序隊(duì)列的隊(duì)尾元素所在位置 ：rear=%dn,q-rear); printf(順序隊(duì)列的隊(duì)頭元素所在位置 :front=%dn,q-front);/*建立順序隊(duì)列*/void Setsqqueue(sqqueue *q) int n,i,m;printf(n 請(qǐng)輸入將要入順序隊(duì)列的長度:);scanf(%d,&n);printf(n 請(qǐng)依次輸入入順序隊(duì)列的元素值:n);for (i=0;in;i+)scanf(%d,&m);append(q,m);main() sqqueue *head;int x,y,z,select; head=(sqqu