數(shù)據(jù)結(jié)構(gòu)棧的基本操作,進棧,出棧

第五次實驗報告——順序棧、鏈棧的插入和刪除一 需求分析1、在演示程序中，出現(xiàn)的元素以數(shù)字出現(xiàn)定義為 int 型，2、演示程序在計算機終端上，用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應(yīng)的輸入數(shù)據(jù)和運算結(jié)果顯示在終端上3、順序棧的程序執(zhí)行的命令包括如下：1）定義結(jié)構(gòu)體2）順序棧的初始化及創(chuàng)建3）元素的插入4）元素的刪除5）順序棧的打印結(jié)果3、鏈棧的程序執(zhí)行的命令包括如下：1）定義結(jié)構(gòu)體2）鏈棧的初始化及創(chuàng)建3）元素的插入4）元素的刪除5）鏈棧的打印結(jié)果概要設(shè)計1、順序?？赡苄枰玫接行虮淼某橄髷?shù)據(jù)類型定義：ADTList{數(shù)據(jù)對象 :D={ai|ai ∈ElemL,i=1,2,...,n,n ≥0}數(shù)據(jù)關(guān)系 :R1={<ai-1,ai>|ai-1,ai ∈D,i=2,...,n}基本操作：InitStack(SqStack&S)操作結(jié)果：構(gòu)造一個空棧Push(L,e)操作結(jié)果：插入元素 e為新的棧頂元素StatusPop(SqStack&S)操作結(jié)果：刪除棧頂元素}ADTList ；2、鏈?？赡苄枰玫接行虮淼某橄髷?shù)據(jù)類型定義：ADTList{數(shù)據(jù)對象 :D={ai|ai ∈ElemL,i=1,2,...,n,n ≥0}數(shù)據(jù)關(guān)系 :R1={<ai-1,ai>|ai-1,ai ∈D,i=2,...,n}基本操作：LinkStack(SqStack&S)操作結(jié)果：構(gòu)造一個空棧StatusPush(L,e)操作結(jié)果：插入元素 e為新的棧頂元素StatusPop(SqStack&S)操作結(jié)果：刪除棧頂元素}ADTList ；3、順序棧程序包含的主要模塊：(1) 已給定的函數(shù)庫：2）順序棧結(jié)構(gòu)體：3）順序棧初始化及創(chuàng)建:(4) 元素插入(5) 元素刪除（6）主程序：、鏈棧程序包含的主要模塊：(1) 已給定的函數(shù)庫：2）鏈棧結(jié)構(gòu)體：3）鏈棧初始化及創(chuàng)建:(4) 元素插入(5) 元素刪除(6) 主程序：三 詳細設(shè)計線性棧：結(jié)構(gòu)體（邱建美）#defineSTACK_INIT_SIZE100// 存儲空間初始分配量#defineSTACKINCREMENT10// 存儲空間分配增量typedefstruct{int*base;// 在構(gòu)造棧之前和銷毀之后， base的值為 NULLint*top;// 棧頂指針intstacksize;// 當前已分配的存儲空間，以元素為單位}SqStack#include"Base.h"主函數(shù)（張濤）#include"construction.h"#include"stack_operation.c"intmain(){SqStackS;intchoice,e;S=InitStack();S=Input_Sq(S);printf(" 請選擇執(zhí)行的操作，輸入 1執(zhí)行入棧操作，輸入 2執(zhí)行出棧操作 choice=");scanf("%d",&choice);switch(choice){case1:{printf(" 請輸入插入元素的值 e=");scanf("%d",&e);S=Push(S,e);printf(" 執(zhí)行入棧操作后的線性棧為 ");Print_Stack(S);};break;case2:{S=Pop(S);printf(" 執(zhí)行出棧操作后的線性棧為 ");Print_Stack(S);};break;default:printf(" 您輸入的值不合法 ");}}線性棧的創(chuàng)建（鄭峰）SqStackInitStack()// 線性棧的創(chuàng)建{SqStackS;S.base=(int*)malloc(STACK_INIT_SIZE *sizeof(int));// 分配存儲空間if(!S.base)exit(OVERFLOW);// 存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnS;}輸入函數(shù)（胡高飛）SqStackInput_Sq(SqStackS)// 輸入函數(shù){intn,i;printf(" 請輸入元素個數(shù) n=");scanf("%d",&n);printf(" 請輸入%d個元素",n);for(i=0;i<n;i++){scanf("%d",S.top);S.top++;}returnS;}進棧函數(shù)（鄭峰）SqStackPush(SqStackS,inte)//{

進棧函數(shù)if(S.top-S.base>=S.stacksize)//

判斷棧是否為滿， 追加存儲空間{S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base)exit(OVERFLOW);// 存儲分配失敗S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;// 插入元素returnS;}出棧函數(shù)（邱建美）SqStackPop(SqStackS)// 刪除函數(shù){inte;if(S.top==S.base)printf(" 線性棧為空 ");e=*--S.top;returnS;}輸出函數(shù)(方傲俠)voidPrint_Stack(SqStackS)// 打印函數(shù){inti;while(S.base!=S.top){for(i=0;i<S.top-S.base;i++){S.top--;printf("%5d",*S.top);}printf("\n");}庫函數(shù)*Base.h( 程序名)*/#include<string.h>#include<ctype.h>#include<malloc.h>/*malloc() 等*/#include<limits.h>/*INT_MAX 等*/#include<stdio.h>/*EOF(=^Z 或F6),NULL*/#include<stdlib.h>/*atoi()*/#include<io.h>/*eof()*/#include<math.h>/*floor(),ceil(),abs()*/#include<process.h>/*exit()*//* 函數(shù)結(jié)果狀態(tài)代碼 */#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2 因為在 math.h中已定義 OVERFLOW的值為3,故去掉此行 */typedefintStatus;/*Status 是函數(shù)的類型 ,其值是函數(shù)結(jié)果狀態(tài)代碼，如 OK等*/typedefintBoolean;/*Boolean 是布爾類型 ,其值是 TRUE或FALSEl鏈棧程序：結(jié)構(gòu)體(邱建美）typedefstructSNode// 建立鏈表結(jié)構(gòu)體{intdata;structSNode*next;}SNode,*LinkStack;主函數(shù)（方傲俠）#include"Base.h"#include"construction.h"#include"LinkStack_operation.c"intmain(){LinkStackS;intchoice,e;S=Creatlist_Stack();printf(" 請選擇執(zhí)行的操作，輸入 1執(zhí)行入棧操作，輸入 2執(zhí)行出棧操作 choice=");scanf("%d",&choice);switch(choice){case1:{printf(" 請輸入插入元素的值 e=");scanf("%d",&e);S=Push(S,e);printf(" 執(zhí)行操作入棧后的線性棧為 ");Print_Stack(S);};break;case2:{S=Pop(S);printf(" 執(zhí)行出棧操作后的線性棧為 ");Print_Stack(S);};break;default:printf(" 您輸入的值不合法 \n");}}創(chuàng)建鏈棧函數(shù)（張濤）LinkStackCreatlist_Stack()// 創(chuàng)建一個鏈棧{LinkStackS;LinkStackP;inti,n;S=(LinkStack)malloc(sizeof(SNode));S->next=NULL;/* 先建立一個鏈棧 */printf(" 請輸入元素個數(shù) n=");scanf("%d",&n);printf(" 請輸入%d個數(shù)據(jù)\n",n);i=0;scanf("%d",&S->data);for(i=1;i<n;++i){P=(LinkStack)malloc(sizeof(SNode));/*

生成新結(jié)點

*/P->next=S;S=P;scanf("%d",&S->data);/*

輸入元素值

*/}returnS;}入棧函數(shù)（方傲俠）LinkStackPush(LinkStackS,inte){LinkStackP;if(S==NULL)returnERROR;P=(LinkStack)malloc(sizeof(SNode));P->data=e;P->next=S;S=P;returnS;}出棧函數(shù)（胡高飛）LinkStackPop(LinkStackS){LinkStackP,Q;P=S;S=S->next;free(P);returnS;}輸出函數(shù)（鄭峰）voidPrint_Stack(LinkStackS){while(S){printf("%5d",S->data);S=S->next;}printf("\n");}庫函數(shù)*Base.h(程序名#include<string.h>#include<ctype.h>

)*/#include<malloc.h>/*malloc()

等

*/#include<limits.h>/*INT_MAX

等

*/#include<stdio.h>/*EOF(=^Z

或

F6),NULL*/#include<stdlib.h>/*atoi()*/#include<io.h>/*eof()*/#include<math.h>/*floor(),ceil(),abs()*/#include<process.h>/*exit()*//* 函數(shù)結(jié)果狀態(tài)代碼 */#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2 因為在 math.h中已定義 OVERFLOW的值為3,故去掉此行 */typedefintStatus;/*Status 是函數(shù)的類型 ,其值是函數(shù)結(jié)果狀態(tài)代碼，如 OK等*/typedefintBoolean;/*Boolean 是布爾類型 ,其值是 TRUE或FALSEl四調(diào)試分析:輸出函數(shù)用了語句 S->next!=NULL改正：語句 S！=NULL五用戶手冊:看提示內(nèi)容六 測試結(jié)果線性棧：1）請輸入元素的個數(shù)： 4，請輸入 4個數(shù)據(jù) 1234 ，請輸入執(zhí)行語句，選擇輸入 1執(zhí)行入棧操作，選擇輸入 2執(zhí)行出棧操作 choice=1，請輸入插入元素的值 e=6，執(zhí)行入棧操作后的線性棧為 643212）請輸入元素的個數(shù)： 4，請輸入 4個數(shù)據(jù) 1234 ，請輸入執(zhí)行語句，選擇輸入 1執(zhí)行入棧操