《数据结构堆栈与队列实验报告(共8页).doc》由会员分享，可在线阅读，更多相关《数据结构堆栈与队列实验报告(共8页).doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上实验二 堆栈和队列实验目的：1.熟悉栈这种特殊线性结构的特性；2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算；3.熟悉队列这种特殊线性结构的特性；3.熟练掌握队列在链表存储结构下的基本运算。实验原理：堆栈顺序存储结构下的基本算法；堆栈链式存储结构下的基本算法；队列顺序存储结构下的基本算法；队列链式存储结构下的基本算法；实验内容：第一题 链式堆栈设计。要求（1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶
2、数据元素StackTop(S,d);（2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素；（3）定义数据元素的数据类型为如下形式的结构体，Typedef struct char taskName10; int taskNo;DataType;首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。第二题 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下
3、标。现要求：（1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空；（2）编写主函数进行测试。程序代码：第一题：（1）源程序LinStack.h如下：#define NULL 0typedef struct snode DataType data; struct snode *next; LSNode;/*（1）初始化 StackInitiate(LSNode * head) */void StackInitiate(LSNode * head)/*初始化带头结点链式堆栈*/ if(*head=(LSNode *)mal
4、loc(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)/*把数据元素x插压入链式堆栈head的栈顶作为
5、新的栈顶，*/*入栈成功返回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; /*新结点入栈*/ head-next=p; /*新结点成为新的栈顶*/ return 1;/*（4）出栈StackPop(SLNode *head, DataType *d) */int StackPop(LSNode *head, DataType *d)/*出栈并把栈顶数据元
6、素值带到参数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）取栈顶数据元素StackTop(LSNode *head, DataType *d) */ int StackTop(LSNode *head, DataType *d)/*取栈顶数据元素并由参数d带回，*/* 成功返回1，否则返回0 */ LSNode *p; p=head-
7、next; if(p=NULL) printf(The Stack has been empty!n); return 0; *d=p-data; return 1;/*（6）撤销动态申请空间Destroy(LSNode *head) */ void Destroy(LSNode *head) LSNode *p, *p1; p=head; while(p!=NULL) p1=p; p=p-next; free(p1); （2）测试函数如下：#include/*该文件包含printf()函数*/#include/*该文件包含exit()函数*/#define NULL 0typedef int
8、 DataType;#include LinStack.hvoid main(void) LSNode *myStack; int i, x; StackInitiate(&myStack); for(i=0;i5; i+) if(StackPush(myStack,i+1)=0) printf(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
9、elements is:n); while(StackNotEmpty(myStack) StackPop(myStack, &x); printf(%d , x); Destroy(myStack);（3）设计结构体和测试函数如下：#include#include#includetypedef struct char taskName10; int taskNo;DataType;#includeLinStack.hvoid main() LSNode *myStack; FILE *fp; DataType task,x; if(fp=fopen(task.dat,r)=NULL) pri
10、ntf(不能打开文件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); Destroy(myStack);其中task.dat为：第一个 1第二个 2第三个 3第四个 4第五个 5第二题
11、：原函数设计如下： typedef struct DataType queueMaxQueueSize; int front; /*队头指针*/ int count; /*计数器*/ SeqCQueue;/*=*/*(1)初始化QueueInitiate(SeqCQueue *Q) */void QueueInitiate(SeqCQueue *Q)/*初始化顺序循环队列Q */ Q-front=0; /*定义初始队头指针下标*/ Q-count=0; /*定义初始计数器值*/*=*/*(2)非空否QueueNotEmpty(SeqCQueue Q)*/int QueueNotEmpty(Se
12、qCQueue Q)/*判断顺序循环队列Q非空否，非空时返回1，否则返回0 */ if(Q.count!=0)return 1; else return 0;/*=*/*(3)入队列QueueAppend(SeqCQueue *Q, DataType x)*/int QueueAppend(SeqCQueue *Q, DataType x)/*把数据元素x插入顺序循环队列Q的队尾，成功时返回1，否则返回0 */ if(Q-count=MaxQueueSize) printf(The queue is full!n); return 0; else int r; r=Q-front+Q-coun
13、t; Q-queuer=x; Q-count+; return 1; /*=*/*(4)出队列QueueDelete(SeqCQueue *Q, DataType *d)*/int QueueDelete(SeqCQueue *Q, DataType *d)/*删除顺序循环队列队头数据元素并赋值d，成功时返回1，否则返回0 */ if(Q-count=0) printf(The queue is empty!n); return 0; else *d=Q-queueQ-front; Q-front=(Q-front+1)%MaxQueueSize; Q-count-; return 1; /*
14、=*/*(6)取对头数据元素QueueGet(SeqCQueue Q, DataType *d)*/int QueueGet(SeqCQueue Q, DataType *d)/* 取顺序循环队列队头数据元素并赋值d，成功时返回1，否则返回0 */ if(Q.count=0) printf(The queue is empty!n); return 0; else *d=Q.queueQ.front; return 1; （2）测试函数如下：#include#define MaxQueueSize 100typedef int DataType;#includeSeqQueue.hvoid m
15、ain(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); /*输出元素个数*/ for(j=0;j=9;j+) if(QueueDelete(&myQueue,&d)=0) break; printf(%d ,d); /*出队列并显示元素*/ printf(n); printf(%dn,QueueNotEmpty(myQueue); /*再次判空*/实验结果：（1）测试函数输出结果如下：（2）测试设计的结构体结果如下：（3）测试仅使用头指针和计数器的队列结果如下：总结与思考只使用对头指针和计数器的循环队列，实现方法和加上尾指针只有在入队列操作时有所不同，其他的都一样；而此时，入队列元素的位置就由对头指针和计数器决定，此算法的清晰度（可读性）比不上有尾指针的循环队列；但是在判空以及循环具体操作时更为方便；在以结构体数据类型的操作中，要注意的是，取数据元素时也要用结构体类型的变量去取出，输出时也一样。专心-专注-专业