鏈棧順序棧實驗報告

1、第五次實驗報告一一順序棧、鏈棧的插入和刪除一需求分析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ù)類型定義：ADT List數(shù)據(jù)對象:D=ai|ai6 ElemL, i=1,2

2、，,n, n >0數(shù)據(jù)關(guān)系:R1=<ai-1,ai>|ai-1,ai6 D, i=2,n 基本操作：InitStack(SqStack &S)操作結(jié)果：構(gòu)造一個空棧Push(L,e)操作結(jié)果：插入元素e為新的棧頂元素Status Pop(SqStack &S)操作結(jié)果：刪除棧頂元素ADT List ;2、鏈棧可能需要用到有序表的抽象數(shù)據(jù)類型定義：ADT List數(shù)據(jù)對象:D=ai|ai 6 ElemL, i=1,2，,n, n >0數(shù)據(jù)關(guān)系:R1=<ai-1,ai>|ai-1,ai6 D, i=2,n 基本操作：LinkStack(SqSta

3、ck &S)操作結(jié)果：構(gòu)造一個空棧Status Push(L,e)操作結(jié)果：插入元素e為新的棧頂元素Status Pop(SqStack &S)操作結(jié)果：刪除棧頂元素ADT List ;3、順序棧程序包含的主要模塊：(1) 已給定的函數(shù)庫：(2)順序棧結(jié)構(gòu)體：(3)順序棧初始化及創(chuàng)建：(4) 元素插入(5) 元素刪除(6)主程序:4、鏈棧程序包含的主要模塊：(1) 已給定的函數(shù)庫：(2)鏈棧結(jié)構(gòu)體：(3)鏈棧初始化及創(chuàng)建：(4) 元素插入(5) 元素刪除(6) 主程序：三詳細設(shè)計線性棧：結(jié)構(gòu)體#define STACK_INIT_SIZE 100存儲空間初始分配量#define

4、 STACKINCREMENT 10/存儲空間分配增量typedef structint *base;在構(gòu)造棧之前和銷毀之后，base的值為NULLint *top;/ 棧頂指針int stacksize;/當前已分配的存儲空間，以元素為單位SqStack#include"Base.h"主函數(shù)#include"construction.h"#include"stack_operation.c"int main()SqStack S;int choice,e;S=InitStack();S=Input_Sq(S);printf(&quo

5、t;請選擇執(zhí)行的操作，輸入1執(zhí)行入棧操作，輸入2執(zhí)行 出棧操作choice=");scanf("%d”,&choice);switch(choice)case 1:printf("請輸入插入元素的值e=");scanf("%d",&e);S=Push(S,e);printf("執(zhí)行入棧操作后的線性棧為");Print_Stack(S);break;case 2:S=Pop(S);printf("執(zhí)行出棧操作后的線性棧為")；Print_Stack(S);break;default

6、 : printf("您輸入的值不合法");線性棧的創(chuàng)建SqStack InitStack()/線性棧的創(chuàng)建SqStack S;S.base=(int*)malloc(STACK_INIT_SIZE * sizeof(int);/ 分配存儲空間if(!S.base)exit(OVERFLOW);/存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return S;輸入函數(shù)SqStack Input_Sq(SqStack S)/輸入函數(shù)int n,i;printf(" 請輸入元素個數(shù)n=");scanf(&quo

7、t;%d",&n);printf(" 請輸入外元素",n);for(i=0;i<n;i+)scanf("%d",S.top);S.top+;return S;進棧函數(shù)SqStack Push(SqStack S,int e)/進棧函數(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

8、.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/ 插入元素return S;出棧函數(shù)SqStack Pop(SqStack S)/ 刪除函數(shù)int e;if(S.top=S.base)printf("線性棧為空");e=*-S.top;return S;輸出函數(shù)void Print_Stack(SqStack S)/ 打印函數(shù)int i;while(S.base!=S.top)for(i=0;i<S.top-S.base;i+)S.top-;printf("%5d”,*S.top)

9、;printf("n");庫函數(shù)* Base.h (程序名)*/#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc() 等 */#include<limits.h> /* INT_MAX 等 */#include<stdio.h> /* EOF(=AZ 或 F6),NULL */#include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<m

10、ath.h> /* floor(),ceil(),abs() */#include<process.h> /* exit() */*函數(shù)結(jié)果狀態(tài)代碼*/# define TRUE 1# define FALSE 0# define OK 1# define ERROR 0# define INFEASIBLE -1/* #define OVERFLOW -2 因為在 math.h 中已定義 OVERFLOW®為3,故去掉此行*/typedef int Status; /* Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等*/typedef int Boo

11、lean; /* Boolean是布爾類型，其值是 TRUE或FALSEl鏈棧程序：結(jié)構(gòu)體typedef struct SNode/建立鏈表結(jié)構(gòu)體int data;struct SNode *next;SNode,*LinkStack;主函數(shù)#include"Base.h"#include"construction.h"#include"LinkStack_operation.c"int main()LinkStack S;int choice,e;S=Creatlist_Stack();printf("請選擇執(zhí)行的操作，輸

12、入1執(zhí)行入棧操作，輸入2執(zhí)行出棧操作choice=");scanf("%d”,&choice);switch(choice)case 1:printf("請輸入插入元素的值e=");scanf("%d",&e);S=Push(S,e);printf("執(zhí)行操作入棧后的線性棧為");Print_Stack(S);break;case 2:S=Pop(S)；printf("執(zhí)行出棧操作后的線性棧為");Print_Stack(S);break;default : printf(&qu

13、ot;您輸入的值不合法n");創(chuàng)建鏈棧函數(shù)LinkStack Creatlist_Stack()創(chuàng)建一個鏈棧LinkStack S;LinkStack P;int i,n;S=(LinkStack)malloc(sizeof(SNode);S->next=NULL;/*先建立一個鏈棧*/printf("請輸入元素個數(shù)n=");scanf("%d",&n);printf("請輸入外數(shù)據(jù)n",n);i=0;scanf("%d”,&S->data);for(i=1;i<n;+i)P=(L

14、inkStack)malloc(sizeof(SNode); /* 生成新結(jié)點 */P->next=S;S=P;scanf("%d”,&S->data); /*輸入元素值 */return S;入棧函數(shù)LinkStack Push(LinkStack S,int e)LinkStack P;if(S=NULL)return ERROR;P=(LinkStack)malloc(sizeof(SNode);P->data=e;P->next=S;S=P;return S;出棧函數(shù)LinkStack Pop(LinkStack S)LinkStack P,Q

15、;P=S;S=S->next;free(P);return S;輸出函數(shù)void Print_Stack(LinkStack S)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<s

16、tdio.h> /* EOF(=AZ 或 F6),NULL */#include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */ #include<process.h> /* exit() */*函數(shù)結(jié)果狀態(tài)代碼*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW

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