1、數學與計算科學學院實 驗 報 告實驗項目名稱 棧的順序表示和實現 所屬課程名稱 數據結構 實 驗 類 型 驗證型 實 驗 日 期 2013.11.14 班 級 信計1201 學 號 201253100109 姓 名 成 績 一、實驗概述：【實驗目的】掌握棧的特點及順序棧的基本運算【實驗原理】1、棧是限定僅在表尾插入或刪除操作的線性表，棧的修改是按后進先出的原則進行的2、棧的順序存儲表示：#define STACK_INIT_SIZE 6 /存儲空間初始分配量#define STACKINCREMENT 2 /存儲空間分配增量typedef structSElemType *base; /在棧構

2、造之前和銷毀之后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當前分配的存儲空間，以元素為單位SqStack;【實驗環境】VC + 6.0二、實驗內容：【實驗方案】編寫主函數，調用棧的初始化建空棧、取棧頂元素、進棧以及出棧的算法，調制運行，得出結果。【實驗過程】（實驗步驟、記錄、數據、分析）1、輸入初始化建空棧、取棧頂元素、進棧、出棧算法和主函數：/棧的順序存儲表示#define STACK_INIT_SIZE 6； /存儲空間初始分配量#define STACKINCREMENT 2； /存儲空間分配增量typedef structSEle

3、mType *base; /在棧構造之前和銷毀之后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當前分配的存儲空間，以元素為單位SqStack;Status InitStack(SqStack &S)/構造一個空棧S/InitStackStatus GetTop(SqStack S,SElemType &e)/若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR/GetTopStatus Push(SqStack &S,SElemType e)/插入元素e為新的棧頂元素/PushStatus Pop(SqS

4、tack &S,SElemType &e)/若棧頂不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR/Popvoid main()2、調試：發現錯誤：在以下編碼中出現多個錯誤：Status InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);syntax error : missing ')' before ''；syntax error : ')'；illegal indirection

5、；這三個錯誤主要是由于前面棧的順序存儲表示編碼中出現錯誤，應把“#define STACK_INIT_SIZE 6； #define STACKINCREMENT 2；”中的兩個分號去掉；修改之后，繼續調試，又發現一個錯誤： 'Sqstack' : undeclared identifier即Sqstack無定義，查看前面編碼發現，是對SqStack進行定義，故這里也要與之相應，需把Sqstack改為SqStack；3、調試到無任何錯誤，運行：因棧的存儲空間初始化分配量為6，故需輸入六個數字“2 3 56 7 7 5”，按回車鍵，得到“2 3 56 7 7 5；e=5”其中e=

6、5表示棧頂元素為5，由此完成了棧的初始化建空棧、取棧頂元素算法；接著輸入一個數“23”，表示要插入的元素，回車，得到“2 3 56 7 7 23；e=23；23”，此時“23”已進棧，棧頂元素變為e=23，因存儲空間為6，而棧的修改是按后進先出原則進行，所以棧頂元素“23”先出棧，由此完成了棧的進棧、出棧算法；最終棧的順序表示和實現得以完成。【實驗結論】（結果）【實驗小結】（收獲體會）這次上機，順利的完成了棧的順序表示和實現的上機實驗任務，但是沒有能夠獨立編寫主函數，而是需要在老師和同學的幫助下才能夠編寫出來，所以自己還要繼續努力，爭取學會自己編寫主函數。三、指導教師評語及成績：評 語評語等級

7、優良中及格不及格1.實驗報告按時完成,字跡清楚,文字敘述流暢,邏輯性強2.實驗方案設計合理3.實驗過程（實驗步驟詳細,記錄完整,數據合理,分析透徹）4實驗結論正確. 成 績： 指導教師簽名： 批閱日期：附錄1：源 程 序#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;#defin

8、e STACK_INIT_SIZE 6 /存儲空間初始分配量#define STACKINCREMENT 2 /存儲空間分配增量typedef structSElemType *base; /在棧構造之前和銷毀之后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當前分配的存儲空間，以元素為單位SqStack;Status InitStack(SqStack &S)/構造一個空棧SS.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!S.base)exit(O

9、VERFLOW); /存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStackStatus GetTop(SqStack S,SElemType &e)/若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORif(S.top=S.base) return ERROR;e=*(S.top-1);return OK;/GetTopStatus Push(SqStack &S,SElemType e)/插入元素e為新的棧頂元素if(S.top-S.base>=S.stacksize)/棧滿，

10、追加存儲空間S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!S.base) exit(OVERFLOW); /存儲分配失敗S.top=S.base+S.stacksize;S.stacksize +=STACKINCREMENT;* S.top+=e;return OK;/PushStatus Pop(SqStack &S,SElemType &e)/若棧頂不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORif(S.top=S.ba

11、se) return ERROR;e= * -S.top;return OK;/Popvoid main()SqStack S;int i;SElemType e;InitStack(S); for(i=0;i<STACK_INIT_SIZE;i+)scanf("%d",&S.basei);S.top+;for(i=0;i<S.top-S.base;i+)printf("%d ",*(S.base+i); printf("n"); GetTop(S,e);printf("e=%dn",e);scanf("%d",&e); Push(S,e); for(i=0;i<S.top-S.base;i+)prin