数据结构-堆栈和队列实验报告

实验报告课程数据结构实验名称实验二 堆栈和队列学号姓名实验日期：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 taskName10; int taskNo;DataType;首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。3-19 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求：（1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空；（2）编写一个主函数进行测试。实验结果：3-18 typedef struct snodeDataType 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#includetypedef int 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 elements is:n); while(StackNotEmpty(myStack) StackPop(myStack, &x); printf(%d , x); printf(n); Destroy(myStack); printf(This program is made by10273206n);运行结果为：（3）设计结构体和测试函数如下：#include#include#includetypedef struct char taskName10; int taskNo;DataType;#includeLinStack.hvoid main() LSNode *myStack; FILE *fp; DataType task,x; if(fp=fopen(task.txt,r)=NULL) printf(不能打开文件task.txt!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);printf(This program is made by 10273206n);运行结果为：3-19（1） typedef struct DataType queueMaxQueueSize; int front; /*队头指针*/ int count; /*计数器*/ SeqCQueue;/*初始化操作：QueueInitiate(SeqCQueue *Q) */ void QueueInitiate(SeqCQueue *Q)/*初始化顺序循环队列Q */ Q-front=0; /*定义初始队头指针下标*/ Q-count=0; /*定义初始计数器值*/*判非空否操作：QueueNotEmpty(SeqCQueue Q)*/int QueueNotEmpty(SeqCQueue Q)/*判断顺序循环队列Q非空否，非空时返回1，否则返回0 */ if(Q.count!=0)return 1; else return 0;/*入队列操作：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-count; Q-queuer=x; Q-count+; return 1; /*出队列操作：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; /*取对头数据元素操作：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 main(void) int i,j,d; SeqCQueue myQueue; QueueInitiate(&myQueue); if(QueueNotEmpty(myQueue)=0) printf(队列为空！请输入数据元素：n); /*判空*/ 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); if