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

1、棧的順序表示和實(shí)現(xiàn) 2.2基礎(chǔ)實(shí)驗(yàn) 2.2.1實(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) 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) 置空順序棧 【知識(shí)要點(diǎn)】 棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，它是運(yùn)算受限的順序表。 對(duì)于順序棧，入棧時(shí)，首先判斷棧是否為滿，棧滿的條件為：p-top= =M

2、AXNUM-1 ，棧滿時(shí)，不能入 棧；否則岀現(xiàn)空間溢岀，引起錯(cuò)誤，這種現(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 ln

3、itStack(SqStack *p) q=(SqStack*)malloc(sizeof(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

4、-stackp-top; /*遍歷順序棧函數(shù)*/ void OutStack(SqStack *p) for(i=p_top;i=O;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; /*初始化順序棧*

5、/ void InitStack(SqStack *p) if(!p) printf(Eorror); p-top=-1; /*入棧*/ void Push(SqStack *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

6、(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(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 setEm

7、pty(SqStack *p) p-top= -1; /*主函數(shù)*/ main() SqStack *q; int y,cord;ElemType a; do printf(n); printf(”第一次使用必須初始化！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(nn); printf(請(qǐng)輸入您的選擇(1,2

8、, 3, 4, 5,6); scanf(%d, printf(n); switch(cord) case 1: q=(SqStack*)malloc(sizeof(SqStack); InitStack(q); OutStack(q); break; case 2: printf(請(qǐng)輸入要插入的數(shù)據(jù)元素：a=); scanf(%d, 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; c

9、ase 5: setEmpty(q); printf(n順序棧被置空！n); OutStack(q); break; case 6: exit(0); while (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ù)

10、*/ Elemtype popLstack(LinkStack * s) x=p_data; s-top=p-next;/當(dāng)前的棧頂指向原棧的next free(p);/ 釋放 /*取棧頂元素函數(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 typede

11、f int Elemtype; typedef struct stacknode Elemtype data; stacknode * next; StackNode; typedef struct stacknode * top; / 棧頂指針 LinkStack; /*初始化鏈棧*/ void lnitStack(LinkStack * s) s-top=NULL; printf(n已經(jīng)初始化鏈棧！n); /*鏈棧置空*/ void setEmpty(LinkStack * s) s-top=NULL; printf(n 鏈棧被置空！ n); /*入棧*/ void pushLstack(

12、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 * s) Elemtype x; StackNode * p; p=s-top;/指向棧頂 if (s-top =0) printf(n棧空，不能出棧！ n); exit(-1); x=p-data; s-top=p-

13、next;/當(dāng)前的棧頂指向原棧的next free(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(=n); StackNode * p; p=s-top; while (p!=NULL) printf(%dn,p-data); p=p_next; printf(=n); void m

14、ain() printf(=鏈棧操作=nn); 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(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); pri

15、ntf(請(qǐng)輸入您的選擇(1,2, 3, 4, 5,6); scanf(%d, printf(n); switch(cord) case 1: InitStack(s); Disp(s); break; case 2: n=); printf(”輸入將要壓入鏈棧的數(shù)據(jù)的個(gè)數(shù): scanf(%d, printf(依次將%d個(gè)數(shù)據(jù)壓入鏈棧：n,n); for(i=1;i=n;i+) scanf(%d, pushLstack(s,a); Disp(s); break; case 3: printf(n出棧操作開(kāi)始!n); printf(輸入將要出棧的數(shù)據(jù)個(gè)數(shù)：m=); scanf(%d, for(i=

16、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-rea r+; q_queueq_rear=x; /*出隊(duì)函數(shù)*/ Elemty

17、pe 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(sqqueue *q) for (i=0;in;

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

19、; 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 T

20、RUE; 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); 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, printf(n請(qǐng)依次輸入入順序隊(duì)列的元素值:n); for (i=0;in;i+) scanf(%d, append(q,m); main() sqqueue *head; int x,y,z,select; head=(sqqueu