數(shù)據(jù)結(jié)構(gòu)堆棧與隊(duì)列實(shí)驗(yàn)報(bào)告

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

2、數(shù)據(jù)元素StackTop(S,d);（2）設(shè)計(jì)一個(gè)主函數(shù)對(duì)鏈?zhǔn)蕉褩＿M(jìn)行測(cè)試。測(cè)試方法為：依次把數(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è)計(jì)一個(gè)包含5個(gè)數(shù)據(jù)元素的測(cè)試數(shù)據(jù)，然后設(shè)計(jì)一個(gè)主函數(shù)對(duì)鏈?zhǔn)蕉褩＿M(jìn)行測(cè)試，測(cè)試方法為：依次吧5個(gè)數(shù)據(jù)元素入棧，然后出棧并在屏幕上顯示出棧的數(shù)據(jù)元素。第二題 對(duì)順序循環(huán)隊(duì)列，常規(guī)的設(shè)計(jì)方法是使用対尾指針和對(duì)頭指針，對(duì)尾指針用于指示當(dāng)前的対尾位置下標(biāo)，對(duì)頭指針用于指示當(dāng)前的対頭位置下

3、標(biāo)?，F(xiàn)要求：（1）設(shè)計(jì)一個(gè)使用對(duì)頭指針和計(jì)數(shù)器的順序循環(huán)隊(duì)列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊(duì)列，出隊(duì)列，取對(duì)頭元素和判斷隊(duì)列是否為空；（2）編寫(xiě)主函數(shù)進(jìn)行測(cè)試。程序代碼：第一題：（1）源程序"LinStack.h"如下：#define NULL 0typedef struct snode DataType data; struct snode *next; LSNode;/*（1）初始化 StackInitiate(LSNode * head) */void StackInitiate(LSNode * head)/*初始化帶頭結(jié)點(diǎn)鏈?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é)點(diǎn)入棧*/ head->next=p; /*新結(jié)點(diǎn)成為新的棧頂*/ 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）撤銷動(dòng)態(tài)申請(qǐng)空間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）測(cè)試函數(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è)計(jì)結(jié)構(gòu)體和測(cè)試函數(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("不能打開(kāi)文件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為：第一個(gè) 1第二個(gè) 2第三個(gè) 3第四個(gè) 4第五個(gè) 5第二題：原函數(shù)設(shè)計(jì)如下： typedef struct DataType queueMaxQueueSize; int front; /*隊(duì)頭指針*/ int count; /*計(jì)數(shù)器*/ SeqCQueue;/*=*/*(1)初始化QueueInitiate(SeqCQueue *Q) */void QueueInitiate(SeqCQueue *Q)/*初始化順序循環(huán)隊(duì)列Q */ Q->front=0; /*定義初始隊(duì)頭指針下標(biāo)*/ Q->count=0; /*定義初始計(jì)數(shù)器

13、值*/*=*/*(2)非空否QueueNotEmpty(SeqCQueue Q)*/int QueueNotEmpty(SeqCQueue Q)/*判斷順序循環(huán)隊(duì)列Q非空否，非空時(shí)返回1，否則返回0 */ if(Q.count!=0)return 1; else return 0;/*=*/*(3)入隊(duì)列QueueAppend(SeqCQueue *Q, DataType x)*/int QueueAppend(SeqCQueue *Q, DataType x)/*把數(shù)據(jù)元素x插入順序循環(huán)隊(duì)列Q的隊(duì)尾，成功時(shí)返回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)出隊(duì)列QueueDelete(SeqCQueue *Q, DataType *d)*/int QueueDelete(SeqCQueue *Q, DataType *d)/*刪除順序循環(huán)隊(duì)列隊(duì)頭數(shù)據(jù)元素并賦值d，成功時(shí)返回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)取對(duì)頭數(shù)據(jù)元素QueueGet(SeqCQueue Q, DataType *d)*/int QueueGet(SeqCQueue Q, DataType *d)/* 取順序循環(huán)隊(duì)列隊(duì)頭數(shù)據(jù)元素并賦值d，成功時(shí)返回1，否則返回0 */ if(Q.count=0) printf("The queue is empty

16、!n"); return 0; else *d=Q.queueQ.front; return 1; （2）測(cè)試函數(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); /*輸出元素個(gè)數(shù)*/ for(j=0;j<=9;j+) if(QueueDelete(&myQueue,&d)=0) break; printf("%d ",d); /*出隊(duì)列并顯示元素*/ printf("n"); printf("%dn",Qu