棧的共享 數(shù)據(jù)結(jié)構(gòu)

1、實(shí)驗(yàn)二 共享棧一、 設(shè)計的目的要求1、 了解棧的特性，以及它在實(shí)際問題中的應(yīng)用。2、 掌握棧的實(shí)現(xiàn)方法以及它的基本操作，學(xué)習(xí)運(yùn)用棧來解決問題。二、 設(shè)計的主要內(nèi)容設(shè)計兩個順序棧共享空間，試寫出兩個棧公用的棧操作算法push（x，k）和pop（k）,其中k為0或1，用以指示棧號。編寫一個完整的程序?qū)崿F(xiàn)。三、 設(shè)計的解題思路線性表（a1，a2，an）試一種邏輯結(jié)構(gòu)，若在計算機(jī)中對它采用順序棧存儲結(jié)構(gòu)來存儲，則就是棧表。兩個棧表公用一個內(nèi)存空間圖示如下：2 4 3 1 0 maxsizeTop0 top1在數(shù)據(jù)結(jié)構(gòu)中用C語言來描述，可以利用數(shù)組表示順序表。將兩個原表A和B存放在一個數(shù)組的存儲空間（a

2、1，a2，amaxsize-1）中，實(shí)現(xiàn)方法是：設(shè)置兩個棧頂指針變量top1和top0，開始時top0 = -1和top1 = maxsize表示兩個棧均為空，然后根據(jù)變量k是0還是1，分別進(jìn)行入棧和出棧的操作。具體實(shí)現(xiàn)還要編寫一個完整的程序，用主函數(shù)調(diào)用這里的函數(shù)來完成出入棧的操作。四、 算法思路#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#define maxsize 10typedef int datatype;typedef struc

3、t datatype datamaxsize; int top2;sqstack; /定義一個結(jié)構(gòu)體類型的sqstacksqstack a,*s; /定義一個結(jié)構(gòu)體類型變量a和指針變量sssqstack *init(sqstack *s) /初始化兩個棧均為空，s是指向棧類型的指針 s=(sqstack *)malloc(sizeof(sqstack); /申請空間 s->top0=-1; /top1、top0分別是第0和第1 個棧的棧頂指針 s->top1=maxsize; return s;int push(sqstack *s,datatype x,int k) /入棧操作，

4、s是棧頂指針，x是要插入的數(shù)，k是棧號 if(s->top0+1=s->top1) printf("n"); printf("兩個棧均滿，不能進(jìn)棧！n"); /判斷是否棧滿 return 0; if(k=0) s->topk+; /改棧頂指針加1或減1，來選擇不滿的棧 else s->topk-; s->datas->topk=x; /將X插入當(dāng)前棧頂 return 1;int pop(sqstack *s,int k) /出棧操作，棧頂元素由參數(shù)x返回 int x; if(k=0&&s->top

5、0=-1)|(k=1&&s->top1=maxsize) printf("棧空,不能退棧！nn"); return 0; x=s->datas->topk; /區(qū)棧頂元素給X if(k=0) s->topk-; /改棧頂指針加1或減1，來選擇不滿的棧 else s->topk+; return x;void get(sqstack *s,int l) /元素輸入函數(shù)，l來判斷是否已經(jīng)建棧 int k=0,x; while(k=1|k=0) if(l=0) printf("棧還未建立！n"); break; e

6、lse printf("請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2):"); /選擇要輸入的棧號，并輸入元素 scanf("%d",&k); printf("n"); if(k=0|k=1) x=0; printf("請輸入數(shù)據(jù)："); while(x!=-1) scanf("%d",&x); if(x=-1) break; push(s,x,k); printf("n"); else break; void check(sqstack *s) /檢測棧

7、內(nèi)的元素但并不輸出int i,l=0; while(l=0|l=1) printf("請選擇輸出方向，正向(0)，方向(1)，結(jié)束(2):"); scanf("%d",&l); printf("n"); if(l=2) break; else if(l=0&&s->top0=-1)|(l=1&&s->top1=maxsize) printf("棧空,不能退棧！nn"); continue; else if(l=0) printf("正向數(shù)據(jù)為："

8、;); for(i=0;i<=s->topl;i+) printf("%4d",s->datai); printf("nn"); else printf("反向數(shù)據(jù)為："); for(i=maxsize-1;i>=s->topl;i-) printf("%4d",s->datai); printf("nn"); void print(sqstack *s) /元素輸出函數(shù) int x,z=1,f=1,l=0; while(l=0|l=1) printf(&qu

9、ot;請選擇輸出方向，正向(0)，方向(1):"); scanf("%d",&l); printf("n"); x=pop(s,l); if(x=0) printf("選擇'1'繼續(xù),'0'結(jié)束輸出："); scanf("%d",&l); printf("n"); if(l=1) continue; else break; printf("n"); else if(l=0) printf("正向第%d個：%d

10、n",z,x); z+; printf("n"); else printf("反向第%d個：%dn",f,x); f+; printf("n"); void menu() /菜單函數(shù) printf(" 棧的共享實(shí)驗(yàn)n" ); printf("=n"); printf(" 1.棧的建立n" ); printf(" 2.棧的共享輸入n" ); printf(" 3.棧單個的輸出n" ); printf(" 4.棧的檢測n

11、" ); printf(" 0.退出實(shí)驗(yàn)n" ); printf("=n" );void main() /主函數(shù) int h,k,l=0; /定義l為標(biāo)志，判斷是否已建棧，如未建立l=0，否則l=1 char i; sqstack *s; for(;) menu(); printf(" 請選擇 0-4：" ); scanf("%d",&h); if(h<0|h>4) printf("n輸人錯誤! n" ); printf("Enter 'y'

12、; to contunie :"); scanf("%s",&i); system("cls"); continue; else switch(h) case 1: system("cls"); printf("*n"); printf("* 棧的建立*n"); printf("*n"); printf("n"); s=init(s); /棧的建立 printf("Enter 'y' to contunie :&

13、quot;); scanf("%s",&i); printf("n"); l=1; system("cls"); break; case 2: system("cls"); printf("*n"); printf("* 棧的共享輸入*n"); printf("*n" ); get(s,l); / 棧的輸入 printf("n"); printf("Enter 'y' to contunie :&quo

14、t;); scanf("%s",&i); printf("n"); system("cls"); break; case 3: system("cls"); printf("*n" ); printf("* 棧單個的輸出* n"); printf("*n" ); print(s); /棧的單個輸出 printf("n"); system("cls"); break; case 4: system("

15、cls"); printf("*n" ); printf("* 棧的檢測* n"); printf("*n" ); check(s); /對棧內(nèi)元素的檢測 printf("n"); system("cls"); break; case 0: system("cls"); printf("* 再 見！*n"); printf("n"); return 0; 五、 運(yùn)算結(jié)果結(jié)果一：0號棧輸入元素（1，2，3，4，7，8，10），1

16、號棧輸入元素（0，5，6）棧的共享實(shí)驗(yàn)1. 棧的建立2. 棧的共享輸入3. 棧單個的輸出4. 棧的檢測0. 退 出 實(shí) 驗(yàn)請 選 擇 0-4：1 （回車）* 棧 的 建 立 *Enter y to continue ：y （回車）*棧 的 共 享 輸 入*請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2): 0 （回車）請輸入數(shù)據(jù)：1 2 3 4 7 8 10 1 （回車）請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2): 1 （回車）請輸入數(shù)據(jù)：0 5 6 1 （回車）請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2): 2 （回車）Enter y to continue ：y （回車）*

17、棧 的 檢 測 *請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2): 0 （回車）正向數(shù)據(jù)為：1 2 3 4 7 8 10請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2): 1 （回車）反向數(shù)據(jù)為：0 5 6請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2): 2 （回車）* 棧 的 單 個 輸 出 *請選擇輸出方向，正向(0)，方向(1): 0 （回車）正向第1個：10請選擇輸出方向，正向(0)，方向(1): 0 （回車）正向第2個：8請選擇輸出方向，正向(0)，方向(1): 0 （回車）正向第3個：17請選擇輸出方向，正向(0)，方向(1): 0 （回車）正向第4個：4請選擇輸出方向，

18、正向(0)，方向(1): 0 （回車）正向第5個：3請選擇輸出方向，正向(0)，方向(1): 0 （回車）正向第6個：2請選擇輸出方向，正向(0)，方向(1): 0 （回車）正向第7個：1請選擇輸出方向，正向(0)，方向(1): 0 （回車）?？眨荒芡藯?！選擇'1'繼續(xù),'0'結(jié)束輸出：1 （回車）請選擇輸出方向，正向(0)，方向(1): 1 （回車）反向第1個：6 請選擇輸出方向，正向(0)，方向(1): 1 （回車）反向第2個：5 請選擇輸出方向，正向(0)，方向(1): 1 （回車）反向第3個：0 請選擇輸出方向，正向(0)，方向(1): 1 （回車）棧

19、空，不能退棧！選擇'1'繼續(xù),'0'結(jié)束輸出：0 （回車）棧的共享實(shí)驗(yàn)5. 棧的建立6. 棧的共享輸入7. 棧單個的輸出8. 棧的檢測1. 退 出 實(shí) 驗(yàn)請 選 擇 0-4：0 （回車）* 再 見 *按任意鍵繼續(xù)結(jié)果二：還未建立棧就輸入數(shù)據(jù)棧的共享實(shí)驗(yàn)1. 棧的建立2. 棧的共享輸入3. 棧單個的輸出4. 棧的檢測0. 退 出 實(shí) 驗(yàn)請 選 擇 0-4：2 （回車）*棧 的 共 享 輸 入*棧還未建立！Enter y to continue ：y （回車）結(jié)果三：輸入的數(shù)據(jù)過多時棧的共享實(shí)驗(yàn)1. 棧的建立2. 棧的共享輸入3. 棧單個的輸出4. 棧的檢測0. 退 出 實(shí) 驗(yàn)請 選 擇 0-4：1 （回車）* 棧 的 建 立 *Enter y to continue ：y （回車）*棧 的 共 享 輸 入*請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2): 0 （回車）請輸入數(shù)據(jù)：1 2 3 4 5 6 7 8 9 10 11 1 （回車）兩棧均滿，不能進(jìn)棧！請選擇輸入方向，正向(0)，方向(1)，結(jié)束(2): 2 （回車）Enter y to continue ：y （回車）六、 調(diào)試小結(jié)函數(shù)init (sqstack *s) 中少了一條s=(sqstack *