數(shù)據(jù)結(jié)構(gòu)堆棧與隊列實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實驗二 堆棧和隊列實驗?zāi)康模?.熟悉棧這種特殊線性結(jié)構(gòu)的特性；2.熟練并掌握棧在順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)下的基本運算；3.熟悉隊列這種特殊線性結(jié)構(gòu)的特性；3.熟練掌握隊列在鏈表存儲結(jié)構(gòu)下的基本運算。實驗原理：堆棧順序存儲結(jié)構(gòu)下的基本算法；堆棧鏈?zhǔn)酱鎯Y(jié)構(gòu)下的基本算法；隊列順序存儲結(jié)構(gòu)下的基本算法；隊列鏈?zhǔn)酱鎯Y(jié)構(gòu)下的基本算法；實驗內(nèi)容：第一題 鏈?zhǔn)蕉褩ＴO(shè)計。要求（1）用鏈?zhǔn)蕉褩ＴO(shè)計實現(xiàn)堆棧，堆棧的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入棧StackiPush(S,x),出棧StackPop（S,d）,取棧頂

2、數(shù)據(jù)元素StackTop(S,d);（2）設(shè)計一個主函數(shù)對鏈?zhǔn)蕉褩＿M行測試。測試方法為：依次把數(shù)據(jù)元素1，2，3，4，5入棧，然后出棧并在屏幕上顯示出棧的數(shù)據(jù)元素；（3）定義數(shù)據(jù)元素的數(shù)據(jù)類型為如下形式的結(jié)構(gòu)體，Typedef struct char taskName10; int taskNo;DataType;首先設(shè)計一個包含5個數(shù)據(jù)元素的測試數(shù)據(jù)，然后設(shè)計一個主函數(shù)對鏈?zhǔn)蕉褩＿M行測試，測試方法為：依次吧5個數(shù)據(jù)元素入棧，然后出棧并在屏幕上顯示出棧的數(shù)據(jù)元素。第二題 對順序循環(huán)隊列，常規(guī)的設(shè)計方法是使用対尾指針和對頭指針，對尾指針用于指示當(dāng)前的対尾位置下標(biāo)，對頭指針用于指示當(dāng)前的対頭位置下

3、標(biāo)?，F(xiàn)要求：（1）設(shè)計一個使用對頭指針和計數(shù)器的順序循環(huán)隊列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊列，出隊列，取對頭元素和判斷隊列是否為空；（2）編寫主函數(shù)進行測試。程序代碼：第一題：（1）源程序"LinStack.h"如下：#define NULL 0typedef struct snode DataType data; struct snode *next; LSNode;/*（1）初始化 StackInitiate(LSNode * head) */void StackInitiate(LSNode * head)/*初始化帶頭結(jié)點鏈?zhǔn)蕉褩?/ if(*head=(

4、LSNode *)malloc(sizeof(LSNode)=NULL)exit(1); (*head)->next=NULL;/*（2）非空否 StackNotEmpty(LSNode * head) */int StackNotEmpty(LSNode * head)/*判斷堆棧是否為空，非空返回1，否則返回0*/ if(head->next=NULL) return 0; else return 1;/*（3）入棧StackPush(LSNode * head, DataType x) */int StackPush(LSNode *head, DataType x)/*把數(shù)

5、據(jù)元素x插壓入鏈?zhǔn)蕉褩ead的棧頂作為新的棧頂，*/*入棧成功返回1，否則返回0 */ LSNode *p; if(p=(LSNode *)malloc(sizeof(LSNode)=NULL) printf("The memory space is not enough!n"); return 0; p->data=x; p->next=head->next; /*新結(jié)點入棧*/ head->next=p; /*新結(jié)點成為新的棧頂*/ return 1;/*（4）出棧StackPop(SLNode *head, DataType *d) */in

6、t StackPop(LSNode *head, DataType *d)/*出棧并把棧頂數(shù)據(jù)元素值帶到參數(shù)d，*/*出棧成功返回1，否則返回0 */ LSNode *p; p=head->next; if(p=NULL) printf("The Stack has been empty!n"); return 0; head->next=p->next; *d=p->data; free(p); return 1;/*（5）取棧頂數(shù)據(jù)元素StackTop(LSNode *head, DataType *d) */ int StackTop(LSNo

7、de *head, DataType *d)/*取棧頂數(shù)據(jù)元素并由參數(shù)d帶回，*/* 成功返回1，否則返回0 */ LSNode *p; p=head->next; if(p=NULL) printf("The Stack has been empty!n"); return 0; *d=p->data; return 1;/*（6）撤銷動態(tài)申請空間Destroy(LSNode *head) */ void Destroy(LSNode *head) LSNode *p, *p1; p=head; while(p!=NULL) p1=p; p=p->nex

8、t; free(p1); （2）測試函數(shù)如下：#include<stdio.h>/*該文件包含printf()函數(shù)*/#include<stdlib.h>/*該文件包含exit()函數(shù)*/#define NULL 0typedef int DataType;#include "LinStack.h"void main(void) LSNode *myStack; int i, x; StackInitiate(&myStack); for(i=0;i<5; i+) if(StackPush(myStack,i+1)=0) printf(

9、"error!n"); return; if(StackTop(myStack, &x)=0) printf("error!n"); return; else printf("The element of local top is :%dn",x); printf( "The sequence of outing elements is:n"); while(StackNotEmpty(myStack) StackPop(myStack, &x); printf("%d ", x

10、); Destroy(myStack);（3）設(shè)計結(jié)構(gòu)體和測試函數(shù)如下：#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct char taskName10; int taskNo;DataType;#include"LinStack.h"void main() LSNode *myStack; FILE *fp; DataType task,x; if(fp=fopen("task.dat","r")=NULL) p

11、rintf("不能打開文件task.dat!n"); exit(0); StackInitiate(&myStack); while(!feof(fp) fscanf(fp,"%s %d",&task.taskName,&task.taskNo); StackPush(myStack,task); fclose(fp); while(StackNotEmpty(myStack) StackPop(myStack,&x); printf("%s %dn",x.taskName,x.taskNo); Des

12、troy(myStack);其中task.dat為：第一個 1第二個 2第三個 3第四個 4第五個 5第二題：原函數(shù)設(shè)計如下： typedef struct DataType queueMaxQueueSize; int front; /*隊頭指針*/ int count; /*計數(shù)器*/ SeqCQueue;/*=*/*(1)初始化QueueInitiate(SeqCQueue *Q) */void QueueInitiate(SeqCQueue *Q)/*初始化順序循環(huán)隊列Q */ Q->front=0; /*定義初始隊頭指針下標(biāo)*/ Q->count=0; /*定義初始計數(shù)器

13、值*/*=*/*(2)非空否QueueNotEmpty(SeqCQueue Q)*/int QueueNotEmpty(SeqCQueue Q)/*判斷順序循環(huán)隊列Q非空否，非空時返回1，否則返回0 */ if(Q.count!=0)return 1; else return 0;/*=*/*(3)入隊列QueueAppend(SeqCQueue *Q, DataType x)*/int QueueAppend(SeqCQueue *Q, DataType x)/*把數(shù)據(jù)元素x插入順序循環(huán)隊列Q的隊尾，成功時返回1，否則返回0 */ if(Q->count=MaxQueueSize) p

14、rintf("The queue is full!n"); return 0; else int r; r=Q->front+Q->count; Q->queuer=x; Q->count+; return 1; /*=*/*(4)出隊列QueueDelete(SeqCQueue *Q, DataType *d)*/int QueueDelete(SeqCQueue *Q, DataType *d)/*刪除順序循環(huán)隊列隊頭數(shù)據(jù)元素并賦值d，成功時返回1，否則返回0 */ if(Q->count=0) printf("The queue

15、 is empty!n"); return 0; else *d=Q->queueQ->front; Q->front=(Q->front+1)%MaxQueueSize; Q->count-; return 1; /*=*/*(6)取對頭數(shù)據(jù)元素QueueGet(SeqCQueue Q, DataType *d)*/int QueueGet(SeqCQueue Q, DataType *d)/* 取順序循環(huán)隊列隊頭數(shù)據(jù)元素并賦值d，成功時返回1，否則返回0 */ if(Q.count=0) printf("The queue is empty

16、!n"); return 0; else *d=Q.queueQ.front; return 1; （2）測試函數(shù)如下：#include<stdio.h>#define MaxQueueSize 100typedef int DataType;#include"SeqQueue.h"void main(void) int i,j,d; SeqCQueue myQueue; QueueInitiate(&myQueue); printf("%dn",QueueNotEmpty(myQueue); /*判空*/ for(i=0;i<=10;i+) if(QueueAppend(&myQueue,i+1)=0) break; printf("%dn",myQueue.count); /*輸出元素個數(shù)*/ for(j=0;j<=9;j+) if(QueueDelete(&myQueue,&d)=0) break; printf("%d ",d); /*出隊列并顯示元素*/ printf("n"); printf("%dn",Qu