數據結構實驗報告共享棧

1、 數據結構實 驗 報 告 成績_學號1217417007姓名嚴夢授課教師黃欣專業(yè)12信計實驗報告遞交日期10/8實驗題目兩個棧共享向量（棧類型定義如下），它們的棧底分別設在向量的兩端，編制程序完成共用棧操作。一 需求分析1程序實現的功能：完成共用棧操作。編制函數：1). 元素x進棧i函數； void push(seqstack *s,int i,datatype x);2). 棧i退棧，并返回原棧頂元素函數； datatype pop(seqstack *s,int i);3). 取棧i頂元素函數；datatype top(seqstack *s,int i);4).顯示共用棧內容；void

2、show(seqstack *s);5). 主函數完成功能：a). 開辟?？臻g; b). 兩個棧分別進棧若干個元素; c). 兩個棧分別退?；蛉ｍ斎舾蓚€元素;d). 顯示最后棧內容; 2數據輸入的內容輸入形式與范圍 輸入所創(chuàng)建的棧規(guī)模n1，n2；輸入進棧數據，其類型是整型數；輸入數據以回車符相隔。3數據輸出的內容與形式 輸出取?；虺鰲祿?，輸出共用棧元素, 數據以回車符相隔。二. 主要算法的算法思想.1開辟棧空間：定義數組開辟靜態(tài)空間存儲共用棧2. 元素x進棧i函數：判斷進棧i，判斷棧i是否已滿，不滿則執(zhí)行進棧操作，否則不執(zhí)行。3. 棧i退棧，并返回原棧頂元素函數：判斷退棧i，判斷棧i是否已

3、空，非空則執(zhí)行退棧操作，否則不執(zhí)行。4. 取棧i頂元素函數:判斷取棧i，判斷棧i是否為空，非空則執(zhí)行取棧頂操作，否則不執(zhí)行。5. 主函數:開辟?？臻g；依次調用進棧函數、退棧函數；調用去棧頂函數、顯示共用棧函數。三. 設計：1共用棧存儲結構：順序表。共用棧類型定義：typedef struct datatype vm; Int top0,top1; seqstack; /*單鏈表結點類型*/2參數表（列出所有的符號常量與全局變量）參數名數據傳遞方式數據內容傳遞所屬函數m符號常量宏定義100所有函數3函數間的調用關系圖4列出每個函數的函數聲明、函數作用、函數值、形參內容與形式、主要算法步驟等1)元

4、素x進棧i元素函數首部：void push(seqstack *s,int i,datatype x); 形參：seqstack *s,int i,datatype x 函數作用：將元素x壓入棧i頂端 函數值：無 局部變量 無 進棧算法主要步驟：(a) 判別棧是否已滿 if(s->top0<s->top1);(b) 判別進棧i if(s->top0=i); (c) 棧頂位置移動 s->top0+;else s->top1-; (d) 元素x進棧 s->vs->top=x; 2）棧i退棧，并返回原棧頂元素函數 函數首部：datatype pop(s

5、eqstack *s,int i); 形參：seqstack *s,int i 函數作用：棧i退棧，并返回原棧頂元素 函數值：datatype data局部變量 datatype data 算法主要步驟： 判斷是否為空棧： (a)若空，則輸出“upflow error” if(s->top0<0) printf("upflow errorn");if(s->top1>99) printf("upflow errorn"); (b)若不為空，則退棧，取棧頂元素并棧頂標志移動 data=s->vs->top0;s->

6、top0-; data=s->vs->top1;s->top1+; 3). 取棧i頂元素函數 函數首部：datatype top(seqstack *s,int i); 形參：seqstack *s,int i 函數作用：讀取棧i的棧頂元素。 函數值：datatype data局部變量：datatype data data算法主要步驟：(a) 判斷棧i是否為空；if(s->top0=i)if(s->top0<0)printf("empty errorn"); (b) 讀取棧i棧頂元素；data=s->vs->top0； (c)

7、 將讀取的元素返回；return (data); 四. 調試分析：1調試中出現的問題，解決的辦法 1）Top0未定義，直接用s->top0,還減少變量。 2每個函數的時、空復雜性分析 1）void push(seqstack *s,int i,datatype x);x進入棧i；T(n)=O(1)， S(n)=O(n); 2）datatype pop(seqstack *s,int i); 退棧i； T(n)=O(1), S(n)=O(n); 3). datatype top(seqstack *s,int i); 取棧i棧頂函數 T(n)=O(1) , S(n)=O(1); 4). v

8、oid show(seqstack *s);顯示共用棧內容 T(n)=O(1) , S(n)=O(1); 5). main() 主函數 T(n)=O(1) ， S(n)=O(n).3改進設想，經驗體會 多個棧共用一個數組，棧頂棧底位置都需要考慮。五. 使用說明：如何使用你編制的程序、操作步驟.編譯程序成功后，按界面提示輸入棧規(guī)模以及數據。六. 測試結果：輸入輸出數據內容：窗口顯示如下：(下劃線部分為輸入部分，其余為輸出部分)測試數據一：input the node n1:3input the data s1:15input the data s1:16input the data s1:17i

9、nput the node n2:4input the data :21input the data :22input the data :23input the data :24pop s0 top:17pop s1 top:24top s0:16top s1:23no.0 node:15no.1node:16no.99 node:21no.98 node 22no.97 node:23測試數據二：input the node n1:1input the data s1:15input the node n2:4input the data :21input the data :22inpu

10、t the data :23input the data :24pop s0 top:15pop s1 top:24empty errortop s1:23no.99 node:21no.98 node 22no.97 node:23七源代碼清單#include<stdio.h>#include<stdlib.h>#define m 100typedef int datatype;typedef struct datatype vm;int top0,top1;seqstack;void main()void push(seqstack *s,int i,datatyp

11、e x);datatype pop(seqstack *s,int i);datatype top(seqstack *s,int i);void show(seqstack *s);seqstack stack100;int j,n;datatype data;stack->top0=-1;stack->top1=100;printf("input the node n1:n");scanf("%d",&n);for(j=0;j<n;j+)printf("input the data s1:n");scan

12、f("%d",&data);push(stack,stack->top0,data);printf("input the node n2:n");scanf("%d",&n);for(j=0;j<n;j+)printf("input the data:n");scanf("%d",&data);push(stack,stack->top1,data);data=pop(stack,stack->top0);printf("pop s0 t

13、op:%dn",data);data=pop(stack,stack->top1);printf("pop s1 top:%dn",data);data=top(stack,stack->top0); if(data>0)printf("top s0 :%dn",data);data=top(stack,stack->top1);printf("top s1 :%dn",data);show(stack);void push(seqstack *s,int i,datatype x)if(s->

14、top0<s->top1)if(s->top0=i)s->top0+;s->vs->top0=x;elses->top1-;s->vs->top1=x;elseprintf("overflow errorn");datatype pop(seqstack *s,int i)datatype data;if(s->top0=i)if(s->top0<0)printf("upflow errorn");elsedata=s->vs->top0;s->top0-;else

15、if(s->top1>99)printf("upflow errorn");elsedata=s->vs->top1;s->top1+;return (data);datatype top(seqstack *s,int i)datatype data;if(s->top0=i)if(s->top0<0)printf("empty errorn");elsedata=s->vs->top0;elseif(s->top1>99)printf("empty errorn");elsedata=s->vs->top1;return (data);void show