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

1、第五次實(shí)驗(yàn)報(bào)告順序棧、鏈棧的插入和刪除一 需求分析1、 在演示程序中，出現(xiàn)的元素以數(shù)字出現(xiàn)定義為int型，2、 演示程序在計(jì)算機(jī)終端上，用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，相應(yīng)的輸入數(shù)據(jù)和運(yùn)算結(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è)計(jì)1、順序?？赡苄枰玫接行虮淼某橄髷?shù)據(jù)類型定義：ADT List數(shù)據(jù)對(duì)象:D

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

3、tack(SqStack &S) 操作結(jié)果：構(gòu)造一個(gè)空棧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)主程序： 三 詳細(xì)設(shè)計(jì)線性棧：結(jié)構(gòu)體（邱建美）#define STACK_INI

4、T_SIZE 100/存儲(chǔ)空間初始分配量#define STACKINCREMENT 10/存儲(chǔ)空間分配增量typedef structint *base;/在構(gòu)造棧之前和銷毀之后，base的值為NULLint *top;/棧頂指針int stacksize;/當(dāng)前已分配的存儲(chǔ)空間，以元素為單位SqStack#include"Base.h"主函數(shù)（張濤）#include"construction.h"#include"stack_operation.c"int main()SqStack S;int choice,e;S=InitSt

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

6、quot;);Print_Stack(S);break;default : printf("您輸入的值不合法");線性棧的創(chuàng)建（鄭峰）SqStack InitStack()/線性棧的創(chuàng)建SqStack S;S.base=(int*)malloc(STACK_INIT_SIZE * sizeof(int);/分配存儲(chǔ)空間if(!S.base)exit(OVERFLOW);/存儲(chǔ)分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return S;輸入函數(shù)（胡高飛）SqStack Input_Sq(SqStack S)/輸入函數(shù)int n,

7、i;printf("請(qǐng)輸入元素個(gè)數(shù)n=");scanf("%d",&n);printf("請(qǐng)輸入%d個(gè)元素",n);for(i=0;i<n;i+)scanf("%d",S.top);S.top+;return S;進(jìn)棧函數(shù)（鄭峰）SqStack Push(SqStack S,int e)/進(jìn)棧函數(shù)if(S.top-S.base>=S.stacksize)/判斷棧是否為滿，追加存儲(chǔ)空間S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

8、sizeof(int);if(!S.base)exit(OVERFLOW);/存儲(chǔ)分配失敗S.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;

9、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&g

10、t; /* 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 -2 因?yàn)樵趍ath.h中已定義OVERFLOW的值為3,故去掉此行 */ typedef

11、 int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */ typedef int Boolean; /* 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 m

12、ain()LinkStack S;int choice,e;S=Creatlist_Stack();printf("請(qǐng)選擇執(zhí)行的操作，輸入1執(zhí)行入棧操作，輸入2執(zhí)行出棧操作choice=");scanf("%d",&choice);switch(choice)case 1:printf("請(qǐng)輸入插入元素的值e=");scanf("%d",&e);S=Push(S,e);printf("執(zhí)行操作入棧后的線性棧為");Print_Stack(S);break;case 2:S=Pop

13、(S);printf("執(zhí)行出棧操作后的線性棧為");Print_Stack(S);break;default : printf("您輸入的值不合法n");創(chuàng)建鏈棧函數(shù)（張濤）LinkStack Creatlist_Stack()/創(chuàng)建一個(gè)鏈棧LinkStack S;LinkStack P;int i,n;S=(LinkStack)malloc(sizeof(SNode);S->next=NULL;/* 先建立一個(gè)鏈棧 */printf("請(qǐng)輸入元素個(gè)數(shù)n=");scanf("%d",&n);prin

14、tf("請(qǐng)輸入%d個(gè)數(shù)據(jù)n",n);i=0;scanf("%d",&S->data);for(i=1;i<n;+i)P=(LinkStack)malloc(sizeof(SNode); /* 生成新結(jié)點(diǎn) */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)

15、malloc(sizeof(SNode);P->data=e;P->next=S;S=P;return S;出棧函數(shù)（胡高飛）LinkStack Pop(LinkStack S)LinkStack P,Q;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&

16、gt; #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>

17、; /* exit() */ /* 函數(shù)結(jié)果狀態(tài)代碼 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 /* #define OVERFLOW -2 因?yàn)樵趍ath.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五 用戶手冊(cè):看提示內(nèi)容六 測試結(jié)果線性棧：1） 請(qǐng)輸入元素的個(gè)數(shù)：4，請(qǐng)輸入4個(gè)數(shù)據(jù) 1 2 3 4，請(qǐng)輸入執(zhí)行語句，選擇輸入1執(zhí)行入棧操作，選擇輸入2執(zhí)行出棧操作choice=1，請(qǐng)輸入插入元素的值e=6，執(zhí)行入棧操作后的線性棧為6 4 3 2 12）