數據結構實驗報告(棧,括號匹配).docx

北京建筑工程學院理學院數據結構與算法課程 實驗報告課程名稱數據結構與算法 實驗名稱 棧的創(chuàng)建以及應用實驗地點 機房203 日期_2012/4/3姓名 班級 學號 指導教師 成績_【實驗目的】l 熟悉并寫出棧的邏輯結構表示l 實現棧的存儲表示l 實現棧的操作【實驗內容】 l 括號匹配【實驗要求】l 在實驗報告中寫出棧的ADT表示；l 在實驗報告中給出數據類型定義和核心算法和程序；l 在實驗報告中羅列實驗過程中出現的問題和解決的方法；l 打包上交調試后的完整程序，提交實驗報告；l 實驗之前寫出實驗報告的大概框架，實驗過程中填寫完整。l 實驗時攜帶需要上機調試的程序；l 實驗評分：實驗之前預習占20%，實驗報告書寫情況占50%，運行情況30%?！緦嶒灢襟E】1 棧的ADT表示ADT Stack數據對象：D=ai|ai ElemSet,i=1，2，n,n=0數據關系：R1=|ai-1,ai D,i=2,n約定an為棧頂端，a1為棧底端基本操作：Status InitStack(&s)操作結果：構造一個空棧s。Status Push( &s, e)初始條件：棧s已經存在。操作結果：插入元素e為新的棧頂元素。Status Pop( &s, &e)初始條件：棧s已經存在，并不為空。操作結果：刪除s的棧頂元素，并用e返回其值。Status Check( &s, e)初始條件：棧s已經存在，并不為空。操作結果:判斷括號是否匹配。Status EnterString( &s)ADT Stack2 數據類型定義和核心算法和程序 數據類型定義：typedef int Status;typedef char SElemType;typedef struct /棧的順序存儲表示SElemType* base;SElemType* top;int stacksize;SqStack;int x=0;SElemType a;SElemType e; 核心算法： 程序：#include #include #include #define TURE 1#define FALSE 0#define ERROR 0#define OK 1#define INFEASIBLE -1#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef char SElemType;typedef struct /棧的順序存儲表示SElemType* base;SElemType* top;int stacksize;SqStack;int x=0;Status InitStack(SqStack &s)/構造一個空棧Ss.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType);if (!s.base) exit(OVERFLOW);/內存分配失敗s.top = s.base;s.stacksize = STACK_INIT_SIZE;return OK;Status Push(SqStack &s,SElemType e)/插入元素e為新的棧頂元素if(s.top-s.base=s.stacksize)/棧滿追加存儲空間。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;Status Pop(SqStack &s,SElemType &e)/若棧不空，則刪除s的棧頂元素，用e返回其值，并返回ok；否則返回error。if(s.top = s.base) return ERROR;e = * -s.top;return OK;/Status Check(SqStack &s,SElemType e)SElemType a;Pop(s,a);if( a=( & e=) |a=& e= |a=& e= )return TURE;return ERROR;Status EnterString(SqStack &s)SElemType e;while (1)scanf(%c,&e);if(e=(|e=|e=)Push(s,e);else if(e=)|e=|e=)if(!Check(s,e)return FALSE;break;else if(e!=n)x=1;return FALSE;break;elsebreak;void main()S