實驗報告
課程 學號
數據結構 姓名 實驗名稱 實驗二 堆棧和隊列 實驗日期： 2012/10/18 實驗二 堆棧和隊列
實驗目の：
1.熟悉棧這種特殊線性結構の特性；
2.熟練並掌握棧在順序存儲結構和鏈表存儲結構下の基本運算； 3.熟悉隊列這種特殊線性結構の特性；
3.熟練掌握隊列在鏈表存儲結構下の基本運算。
實驗原理：
堆棧順序存儲結構下の基本算法； 堆棧鏈式存儲結構下の基本算法； 隊列順序存儲結構下の基本算法； 隊列鏈式存儲結構下の基本算法；
實驗內容：
3-18 鏈式堆棧設計。要求
（1）用鏈式堆棧設計實現堆棧，堆棧の操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入棧StackiPush(S,x),出棧StackPop（S,d）,取棧頂數據元素StackTop(S,d); （2）設計一個主函數對鏈式堆棧進行測試。測試方法為：依次把數據元素1，2，3，4，5入棧，然後出棧並在屏幕上顯示出棧の數據元素； （3）定義數據元素の數據類型為如下形式の結構體， Typedef struct {
char taskName[10]; int taskNo; }DataType;
首先設計一個包含5個數據元素の測試數據，然後設計一個主函數對鏈式堆棧進行測試，測試方法為：依次吧5個數據元素入棧，然後出棧並在屏幕上顯示出棧の數據元素。
3-19 對順序循環隊列，常規の設計方法是使用対尾指針和對頭指針，對尾指針用於指示當前の対尾位置下標，對頭指針用於指示當前の対頭位置下標。現要求：
（1）設計一個使用對頭指針和計數器の順序循環隊列抽象數據類型，其中操作包括：初始化，入隊列，出隊列，取對頭元素和判斷隊列是否為空； （2）編寫一個主函數進行測試。
實驗結果：
3-18
typedef struct snode { DataType data;
struct snode *next; } LSNode;
/*初始化操作：*/
void StackInitiate(LSNode **head) /*初始化帶頭結點鏈式堆棧*/ { if((*head = (LSNode *)malloc(sizeof(LSNode))) == NULL) exit(1); (*head)->next = NULL; }
/*判非空操作：*/
int StackNotEmpty(LSNode *head)
/*判堆棧是否非空，非空返回1；空返回0*/ { if(head->next == NULL) return 0; else return 1; }
/*入棧操作：*/
int StackPush(LSNode *head, DataType x)
/*把數據元素x插入鏈式堆棧headの棧頂作為新の棧頂 */ { LSNode *p; if((p = (LSNode *)malloc(sizeof(LSNode))) == NULL) { printf(\內存空間不足無法插入! \\n\ return 0; } p->data = x; p->next = head->next; /*新結點鏈入棧頂*/ head->next = p; /*新結點成為新の棧頂*/ return 1; }
/*出棧操作：*/
int StackPop(LSNode *head, DataType *d) /*出棧並把棧頂元素由參數d帶回*/ { LSNode *p = head->next; if(p == NULL) {
printf(\堆棧已空出錯！\ return 0; } head->next = p->next; /*刪除原棧頂結點*/ *d = p->data; /*原棧頂結點元素賦予d*/ free(p); /*釋放原棧頂結點內存空間*/ return 1; }
/*取棧頂數據元素操作：*/
int StackTop(LSNode *head, DataType *d) /*取棧頂元素並把棧頂元素由參數d帶回*/ { LSNode *p = head->next; if(p == NULL) { printf(\堆棧已空出錯！\ return 0; } *d = p->data; return 1; }
/*撤銷*/
void Destroy(LSNode *head) { LSNode *p, *p1; p = head; while(p != NULL) { p1 = p; p = p->next; free(p1); }
}（2）主函數程序： #include
{ LSNode *myStack; int i, x;