鏈棧順序棧實驗報告.doc

第五次實驗報告順序棧、鏈棧的插入和刪除一 需求分析1、 在演示程序中，出現(xiàn)的元素以數(shù)字出現(xiàn)定義為int型，2、 演示程序在計算機終端上，用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，相應的輸入數(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é)果二 概要設計1、順序?？赡苄枰玫接行虮淼某橄髷?shù)據(jù)類型定義：ADT List數(shù)據(jù)對象:D=ai|aiElemL, i=1,2,.,n, n0數(shù)據(jù)關(guān)系:R1=|ai-1,ai 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|aiElemL, i=1,2,.,n, n0數(shù)據(jù)關(guān)系:R1=|ai-1,ai D, i=2,.,n 基本操作：LinkStack(SqStack &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)主程序： 三 詳細設計線性棧：結(jié)構(gòu)體#define STACK_INIT_SIZE 100/存儲空間初始分配量#define STACKINCREMENT 10/存儲空間分配增量typedef structint *base;/在構(gòu)造棧之前和銷毀之后，base的值為NULLint *top;/棧頂指針int stacksize;/當前已分配的存儲空間，以元素為單位SqStack#includeBase.h主函數(shù)#includeconstruction.h#includestack_operation.cint main()SqStack S;int choice,e;S=InitStack();S=Input_Sq(S);printf(請選擇執(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 : 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(%d,&n);printf(請輸入%d個元素,n);for(i=0;i=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;/插入元素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;iS.top-S.base;i+)S.top-;printf(%5d,*S.top);printf(n);庫函數(shù)* Base.h (程序名) */ #include #include #include /* malloc()等 */ #include /* INT_MAX等 */ #include /* EOF(=Z或F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* 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 Boolean; /* Boolean是布爾類型,其值是TRUE或FALSEl鏈棧程序：結(jié)構(gòu)體typedef struct SNode/建立鏈表結(jié)構(gòu)體int data;struct SNode *next;SNode,*LinkStack;主函數(shù)#includeBase.h#includeconstruction.h#includeLinkStack_operation.cint main()LinkStack S;int choice,e;S=Creatlist_Stack();printf(請選擇執(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 : printf(您輸入的值不合法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(請輸入%d個數(shù)據(jù)n,n);i=0;scanf(%d,&S-data);for(i=1;inext=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;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 #include #include /* malloc()等 */ #include /* INT_MAX等 */ #include /* EOF(=Z或F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* 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 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個數(shù)據(jù) 1 2 3 4，請輸入執(zhí)行語句，選擇輸入1執(zhí)行入棧操作，選擇輸入