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

1、棧的順序表示和實(shí)現(xiàn)2.2基礎(chǔ)實(shí)驗(yàn)2.2.1實(shí)驗(yàn)?zāi)康模?）掌握棧的順序表示和實(shí)現(xiàn)（2）掌握棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（3）掌握隊(duì)列的順序表示和實(shí)現(xiàn)（4）掌握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.2.2實(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)簡(jiǎn)稱為順序棧,它是運(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è)置在向量?jī)啥说娜我庖粋€(gè)端點(diǎn)（3）棧頂位置是隨著進(jìn)棧和退棧操作而變化的，用一個(gè)整型量top（通常稱top為棧頂指針）來(lái)指示當(dāng)前棧頂位置【實(shí)現(xiàn)提示】/*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/typedef struct ElemType stackMAXNUM; int top;SqStack;/*初始化順序棧函數(shù)*/void InitStack(SqStack *p)q=(SqStack*)malloc(sizeof(SqS

3、tack) /*申請(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-top;i=0;i-

4、)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 Push(SqStack

5、 *p,ElemType x) if(p-toptop=p-top+1; p-stackp-top=x; else printf(Overflow!n);/*出棧*/ElemType Pop(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

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; do printf(n); printf

7、(第一次使用必須初始化！n); printf(n); printf(n 主菜單 n); printf(n 1 初始化順序棧 n); printf(n 2 插入一個(gè)元素 n); printf(n 3 刪除棧頂元素 n); printf(n 4 取棧頂元素 n); printf(n 5 置空順序棧 n); printf(n 6 結(jié)束程序運(yùn)行 n); printf(n-n); printf(請(qǐng)輸入您的選擇( 1, 2, 3, 4, 5,6); scanf(%d,&cord); printf(n); switch(cord) case 1: q=(SqStack*)malloc(sizeof(SqSt

8、ack); InitStack(q); OutStack(q); break; case 2: 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 (

9、cordtop=NULL;/*鏈棧置空函數(shù)*/void setEmpty(LinkStack * s) s-top=NULL;/*入棧函數(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)前的棧頂指向原棧的next free(p); /釋放

10、/*取棧頂元素函數(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.htypedef int Elemtype;typedef struct stacknode Elemtype data; stacknode * next;StackNode;typedef struct

11、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 * s, Elemtype x) StackNode * p; p=(StackNode *)malloc(sizeof(StackNode); /建立一個(gè)節(jié)點(diǎn)。 p-data=x; p-next=s

12、-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; /當(dāng)前的棧頂指向原棧的next free(p); /釋放 return x;/*取棧頂元素*/Elemtype StackTop(LinkStack *s) if (s-top =0) printf(n鏈?？課

13、); exit(-1); return s-top-data;/*遍歷鏈棧*/void Disp(LinkStack * s) printf(n鏈棧中的數(shù)據(jù)為：n); printf(=n); StackNode * 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);

14、printf(第一次使用必須初始化！n); printf(n); printf(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(n-n); printf(請(qǐng)輸入您的選擇( 1, 2, 3, 4, 5,6); scanf(%d,&cord); printf(n); switch(cord) case 1: InitStack(s); Disp(s); break; case

15、 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: printf(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,S

16、tackTop(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-rear+;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 T

17、RUE;/*取隊(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(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

18、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-front=-1; q-rear=-1; return TRUE; /*入隊(duì)*/int append(sqqueue *q, Elemtype x) if(q-rear=MAXNUM-1) return FALSE; q-rear+; q-queueq-rear=x;

19、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 TRUE; return FALSE;/*取隊(duì)頭元素*/int gethead(sqqueue *q) if (q-front=q-rear) return 0; return(q-queueq-front+1);/*遍歷隊(duì)列*/void dis

20、play(sqqueue *q) int s; s=q-front; if (q-front=q-rear) printf(隊(duì)列空!n); else printf(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ì)列的長(zhǎng)度:); 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=(sqqueue