實驗課程名稱資料結構與課程設計
專業班級 10級計科（2）班
學生姓名趙騰松
學號10410902044
指導教師馮韻
2012 至 2013學年第 1 學期第 3 至 4 周
目錄1 概述 3
2 系統分析 3
3 概要分析 3
4 詳細設計 3
4.1 中綴表示式轉換為字尾表示式演算法設計 3
4.2 字尾表示式演算法設計 9
5 程式** 10
6 執行與測試 14
7總結與心得 14
8 參考文獻 14
本次實驗需要對棧和佇列進行充分的了解雖然棧和佇列實質上是不同的但在編寫程式時大致相似。通常棧可以用順序的方式儲存分配一塊連續的儲存區域存放棧中元素並用乙個變數指向當前的棧頂。而佇列的順序儲存結構需要使用乙個陣列和兩個整數型變數來實現。
棧的順序儲存結構簡稱為順序棧,它是運算受限的順序表。對於順序棧入棧時首先判斷棧是否為滿棧滿的條件為p->top= =maxnum-1棧滿時不能入棧; 否則出現空間溢位引起錯誤這種現象稱為上溢。 出棧和讀棧頂元素操作先判棧是否為空為空時不能操作否則產生錯誤。
通常棧空作為一種控制轉移的條件。
佇列的順序儲存結構稱為順序佇列順序佇列實際上是運算受限的順序表。 入隊時將新元素插入rear所指的位置然後將rear加1。出隊時刪去front所指的元素然後將front加1並返回被刪元素。
編寫乙個程式實現順序棧的各種基本運算並在此基礎上設計乙個主程式完成如下功能：1初始化順序棧；2插入元素；3刪除棧頂元素；4取棧頂元素；5遍歷順序棧；6置空順序棧。
編寫乙個程式實現順序佇列的各種基本運算並在此基礎上設計乙個主程式完成如下功能：1初始化佇列；2建立順序佇列；3入隊；4出隊；5判斷佇列是否為空；6取隊頭元素；7遍歷佇列。
順序掃瞄中綴表示式，當讀到數字時直接將其送至輸出佇列中；當讀到運算子時，將棧中所有優先順序高於或等於該運算子的運算子彈出，送至輸出佇列中，再將當前運算子入棧；當讀到左括號時，即入棧；當讀到右括號時，將靠近棧頂的第乙個左括號上面的運算子全部依次彈出，送至輸出佇列，再刪除棧中的左括號。
具體演算法如下：
void ctpostexp(se**ueue *q)
while(t!='(' && s->top!=-1); break;
case '+':
case '-':
case '*':
case '/':
while(priority(c)<=priority(gettop(s)))
push(s,c); break;
}//endswitch
}while(c!='#');//以'#'號結束表示式掃瞄
} 要執行上述演算法，還必須給出相關的棧和佇列的定義、操作以及呼叫該演算法的主函式。
具體演算法如下：
#include
#define stacksize 100
#define queuesize 100
/*佇列的相關操作*/
typedef char datatype;
typedef struct se**ueue; //定義佇列型別
void initqueue(se**ueue * q)//初始化佇列
int queueempty(se**ueue * q) //判空佇列
void enqueue(se**ueue * q, datatype x) //入佇列
}int dequeue(se**ueue *q)
/*棧的相關操作*/
typedef struct seqstack; //棧型別的定義
void initstack(seqstack * s) //初始化棧
void push(seqstack * s,datatype x) //入棧(進棧）
}datatype pop(seqstack * s) //退棧出棧）
datatype gettop(seqstack * s) //取棧頂元素
//求運算子優先順序函式
int priority(datatype op)
} void main()
q->front=0;
printf("\n");
printf("求值結果為：%d\n",cpostexp(q));
}表4-1 中綴表示式到字尾表示式的轉換過程示例
在計算字尾表示式時，最後儲存的值是最先取出參與運算，所以要用到棧。利用前面生成的字尾表示式佇列，很容易寫出計算字尾表示式的演算法。在演算法中使用了vs棧來儲存讀入的操作和運算結果，因為在生成的字尾表示式佇列中存放的是字串行，因此，在演算法中要有乙個數字字元到值的轉換。
如下圖所示：
表4-2 字尾表示式的計算過程示例
#include
#define stacksize 100
#define queuesize 100
/*佇列的相關操作*/
typedef char datatype;
typedef struct se**ueue; //定義佇列型別
void initqueue(se**ueue * q)//初始化佇列
int queueempty(se**ueue * q) //判空佇列
void enqueue(se**ueue * q, datatype x) //入佇列}
資料結構實驗棧和佇列
實驗二第三章棧和佇列 一 棧 實驗原始碼 include include include define stack init size 100 define stackincrement 10 typedef int selemtype typedef int status typedef stru...
資料結構 棧與佇列
3311 請判斷下列表示式是否正確。輸入乙個表示式，表示式中包括 字母，數字，括號以及符號 判斷表達中各括號的位置是否遵循以下規則 1 各種括號左右數量相同。2 各種括號只能並列和巢狀，不能交差。輸入 只有一行，為乙個長度小於255的表示式。輸出 一行。如果表示式中各括號互相匹配，則輸出 yes 否...
資料結構棧和佇列基本操作
實驗二棧和佇列 棧的順尋儲存操作 include stdio.h include stdlib.h define stack init size 100 define stackincrement 10 typedef struct sqstack void initstack sqstack s ...