2022年数据结构-堆栈和队列实验报告.pdf

课程数据结构实验名称实验二堆栈和队列学号姓名实验日期：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;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 7 页 - - - - - - - - - - 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(堆栈已空出错！);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 7 页 - - - - - - - - - - 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 void main(void) LSNode *myStack; int i, x; StackInitiate(&myStack);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 7 页 - - - - - - - - - - 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 byn);运行结果为：（3）设计结构体和测试函数如下：#include#include#includetypedef struct char taskName10; int taskNo;DataType;#includevoid main() LSNode *myStack; FILE *fp; DataType task,x; if(fp=fopen(,r)=NULL) printf(不能打开文件!n); exit(0); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 7 页 - - - - - - - - - - StackInitiate(&myStack); while(!feof(fp) fscanf(fp,%s %d,&,& StackPush(myStack,task); fclose(fp); while(StackNotEmpty(myStack) StackPop(myStack,&x); printf(%s %dn,; Destroy(myStack);printf(This program is made by n);运行结果为：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!=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) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 7 页 - - - - - - - - - - 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=0) printf(The queue is empty!n); return 0; else *d=; return 1; （2）主函数程序：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 7 页 - - - - - - - - - - #include#define MaxQueueSize 100typedef int DataType;#includevoid 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,; /*输出元素个数 */ for(j=0;j=9;j+) if(QueueDelete(&myQueue,&d)=0) break; printf(%d ,d); /*出队列并显示元素*/ printf(n); if(QueueNotEmpty(myQueue)=1) printf(队列不为空 n); /*再次判空 */printf(This program is made by n);运行结果为：总结与思考对于堆栈和队列实验的操作，我明白了栈和队列这两种特殊线性结构的特性，初步掌握了栈在顺序存储结构和链表存储结构下的基本运算。顺序循环队列中初始化，入队列， 出队列，取对头元素和判断队列是否为空是关键。此次实验之后我的逻辑又得到了进一步加强。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 7 页 - - - - - - - - - -