數(shù)據結構棧的基本操作,進棧,出棧

1、第五次實驗報告順序棧、鏈棧的插入和刪除1、在演示程序中，出現(xiàn)的元素以數(shù)字出現(xiàn)定義為 int型，2、演示程序在計算機終端上，用戶在鍵盤上輸入演示程序中規(guī)定的運算命令, 相應的輸入數(shù)據和運算結果顯示在終端上3、順序棧的程序執(zhí)行的命令包括如下：(1)(2)(3)(4)(5)定義結構體順序棧的初始化及創(chuàng)建元素的插入元素的刪除順序棧的打印結果3、鏈棧的程序執(zhí)行的命令包括如下：(1)(2)(3)(4)(5)定義結構體鏈棧的初始化及創(chuàng)建元素的插入元素的刪除鏈棧的打印結果二概要設計1、順序棧可能需要用到有序表的抽象數(shù)據類型定義:ADT List數(shù)據對象：D=ai|ai ElemL, i=1,2，,n, n數(shù)據

2、關系：R仁<ai-1,ai>|ai-1,ai D, i=2,.,n 基本操作:In itStack(SqStack &S)操作結果：構造一個空棧Push(L,e)操作結果：插入元素e為新的棧頂元素Status Pop (SqStack &S)操作結果：刪除棧頂元素ADT List ;2、鏈棧可能需要用到有序表的抽象數(shù)據類型定義:ADT List數(shù)據對象：D=ai|ai ElemL, i=1,2，,n, n D, i=2,.,n 數(shù)據關系：R仁<ai-1,ai>|ai-1,ai基本操作:Lin kStack(SqStack &S)操作結果：構造一個

3、空棧Status P ush(L,e)操作結果：插入元素e為新的棧頂元素Status Pop (SqStack &S)操作結果：刪除棧頂元素ADT List ;3、順序棧程序包含的主要模塊:(1) 已給定的函數(shù)庫:(2)順序棧結構體:(3)順序棧初始化及創(chuàng)建：(4)元素插入(5)元素刪除(6)主程序:4、鏈棧程序包含的主要模塊:(1)已給定的函數(shù)庫:(2) 鏈棧結構體:(3) 鏈棧初始化及創(chuàng)建：兀素插入(5)元素刪除(6)主程序：三詳細設計線性棧:結構體(邱建美)#defineSTACK INIT SIZE 100/存儲空間初始分配量 #defi ne STACKINCREMENT 1

4、0/存儲空間分配增量 typ edef structint *base;/ 在構造棧之前和銷毀之后，base的值為NULLint *top;/棧頂指針int stacksize;/當前已分配的存儲空間，以元素為單位SqStack#i nclude"Base.h"主函數(shù)(張濤)#in clude"c on structi on .h" #in clude"stack_ op eratio n.c" int mai n()SqStack S;int choiceeS=I nitStackO;S=I np ut_Sq(S);printf（&

5、quot;請選擇執(zhí)行的操作，輸入1執(zhí)行入棧操作，輸入2執(zhí)行出棧操作choice="）;sca nf("%d", &choice);switch(choice) case 1:printf（”請輸入插入元素的值e="）;sca nf("%d", &e);S=P ush(S,e);printf（”執(zhí)行入棧操作后的線性棧為"）;Prin t_Stack(S);break;case 2:S=Pop(S);printf（”執(zhí)行出棧操作后的線性棧為"）;Prin t_Stack(S);break;default

6、 : printf(”您輸入的值不合法"）;線性棧的創(chuàng)建（鄭峰）SqStack In itStack()/線性棧的創(chuàng)建SqStack S;S.base=(i nt*)malloc(STACK_INIT_SIZE* sizeof(i nt);/分配存儲空間if(!S.base)exit(OVERFLOW);/存儲分配失敗S.t op 二S.base;S.stacksize二STACK_INIT_SIZE;retur n S;輸入函數(shù)（胡高飛）SqStack Inpu t_Sq(SqStack S)/ 輸入函數(shù)int n,i;printf（"請輸入元素個數(shù)n二”）;sea nf

7、("%d",&n);prin tf（"請輸入d個元素",n）;for(i=0;i vn ;i+)sea nf("%d",S.to p);S.t op+;retur n S;進棧函數(shù)（鄭峰）SqStack P ush(SqStack S,i nt e)/ 進棧函數(shù)if(S.t op-S.base>=S.stacksize)/判斷棧是否為滿，追加存儲空S.base=(i nt*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(i nt);if(!S.base)exit(O

8、VERFLOW);/存儲分配失敗S.to p=S.base+S.stacksize;S.stacksize+二STACKINCREMENT;*S.to P+二e;/ 插入元素retur n S;出棧函數(shù)（邱建美）SqStack Pop (SqStack S)/ 刪除函數(shù)int e;if(S.t op二二S.base)printf（”線性棧為空"）;e=*-S.t op;retur n S;輸出函數(shù)（方傲俠）void Prin t_Stack(SqStack S)/打印函數(shù)int i;while(S.base!二S.t op)for(i=0;ivS.t op-S.base;i+)S.t

9、op-;p ri ntf("%5d",*S.to p);prin tf("n");庫函數(shù)* Base.h (程序名)*/#in cludevstri ng.h>#in cludevct yp e.h>#in cludevmalloc.h> /* malloc()等*/#includevlimits.h> /* INT MAX等*/#i ncludevstdio.h> /* EOF(=Z或 F6),NULL */#i ncludevstdlib.h> /* atoi() */#i ncludevio.h> /* e

10、of() */#i ncludevmath.h> /* floor(),ceil(),abs() */#in clude vp rocess.h> /* exit() */*函數(shù)結果狀態(tài)代碼*/#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1 #defi ne ERROR 0 #defi ne INFEASIBLE -1 /* #define OVERFLOW -2 因為在 math.h 中已定義 OVERFLOW值為是函數(shù)的類型，其值是函數(shù)結果狀3,故去掉此行*/ typ edef int Status; /* Status態(tài)代碼，如OK等

11、*/typ edef int Boolea n; /* Boolea n是布爾類型，其值是TRUE或FALSEl鏈棧程序:結構體（邱建美）typ edef struct SNode/建立鏈表結構體int data;struct SNode *n ext;SNode,*Li nkStack;主函數(shù)（方傲俠）#i nclude"Base.h" #in clude"c on structio n.h" #i nclude"Li nkStack_ op eratio n.c" int mai n()default : printf(”您輸入的

12、值不合法n"）;Lin kStack S;int choiceeS=Creatlist_Stack();printf（"請選擇執(zhí)行的操作，輸入1執(zhí)行入棧操作，輸入2執(zhí)行出棧操作choice="）;sca nf("%d", &choice);switch(choice)case 1:printf（”請輸入插入元素的值e="）;sca nf("%d", &e);S=Pu sh(S,e);printf（”執(zhí)行操作入棧后的線性棧為"）;Prin t_Stack(S);break;case 2:S=

13、Pop(S);printf（”執(zhí)行出棧操作后的線性棧為"）;Prin t_Stack(S);break;創(chuàng)建一個鏈棧創(chuàng)建鏈棧函數(shù)（張濤）Li nkStack Creatlist_Stack()/Lin kStack S;Lin kStack P;int i,n;S=(Li nkStack)malloc(sizeof(SNode);S->next二NULL;/*先建立一個鏈棧*/printf（"請輸入元素個數(shù)n二”）;sca nf("%d",&n);prin tf（"請輸入d個數(shù)據n", n）;i=0;sca nf(&qu

14、ot;%d", &S->data);生成新結點*/for(i=1;i vn;+i)P=(Li nkStack)malloc(sizeof(SNode); /*P-> next二S;S二P;scanf("%d",&S->data); /*輸入元素值 */retur n S;入棧函數(shù)（方傲俠）Li nkStack Push(Li nkStack S,i nt e)Lin kStack P;if(S=NULL)return ERROR;P=(Li nkStack)malloc(sizeof(SNode);P->data二e;P-&

15、gt; next二S;S二P;retur n S;出棧函數(shù)（胡高飛）Li nkStack Pop(Lin kStack S)Lin kStack P,Q;P=S;S=S->n ext;free( P);retur n S;輸出函數(shù)（鄭峰）void Prin t_Stack(Li nkStack S)while(S)prin tf("%5d",S->data);S=S->n ext;prin tf("n");庫函數(shù)* Base.h (程序名)*/#in cludevstri ng.h>#in cludevct yp e.h>#

16、in cludevmalloc.h> /* malloc()等*/#includevlimits.h> /* INT MAX等*/#i ncludevstdio.h> /* EOF(=Z或 F6),NULL */#i ncludevstdlib.h> /* atoi() */#i ncludevio.h> /* eof() */#i nclude<math.h> /* floor(),ceil(),abs() */ #in elude <p rocess.h> /* exit() */*函數(shù)結果狀態(tài)代碼*/ #defi ne TRUE 1

17、#defi ne FALSE 0#defi ne OK 1 #defi ne ERROR 0 #defi ne INFEASIBLE -1 /* #define OVERFLOW -2 因為在 math.h 中已定義 OVERFLOW值為是函數(shù)的類型，其值是函數(shù)結果狀3,故去掉此行*/ typ edef int Status; /* Status態(tài)代碼，如OK等*/typ edef int Boolea n; /* Boolea n是布爾類型，其值是TRUE或FALSEl四調試分析: 輸出函數(shù)用了語句 S->next!二NULL改正：語句S! =NULL五用戶手冊:看提示內容六測試結果線性棧:1）請輸入元素的個數(shù)：4，請輸入4個數(shù)據1 2 3 4，請輸入執(zhí)行語句，選擇輸入1執(zhí)行入棧操作，選擇輸入2執(zhí)行出棧操作choice=1 , 請輸入插入元素的值e=6,執(zhí)行入棧操作后的線性棧為6 4 3 2 1 2）請輸入