《数据结构》课程实验实训报告

1、数据结构课程实验实训报告实验名称栈与队列实验序号3学号14302043姓名陈前方班级信管本二实验日期2015.11.15指导教师金照林成绩、实验目的和要求目的： 掌握堆栈和队列数据结构描述，学会针对堆栈和队列的基本操作。要求： 掌握 C 语言结构化程序设计思想，结构数据类型，指针数据类型。、实验具体内容及步骤1. 实现课本中链式堆栈（ p64-p66）的基本操作，并编制主函数实际运行验证其正确性。2. 链式堆栈设计。要求：（1） 用链式堆栈设计实现堆栈， 堆栈的操作集合包括： 初始化、 非空否、入栈、出栈、 取栈顶数据元素。（ 2） 设计一个主函数对链式堆栈进行测试。测试方法为依次把数据元素1

2、、2、3、4、5 入栈，然后出栈并在屏幕上显示出栈的数据元素。（ 3） 定义数据元素的数据类型为如下形式的结构体：typedef structchar taskName10;/ 任务名int taskNo;/ 任务号DataType;首先设计一个包含 5 个数据的测试数据， 然后设计一个主函数对链式堆栈进行测 试。测试的方法为：依次把 5 个元素入栈，然后出栈并在屏幕上显示出栈的数据3. 实现课本中顺序循环队列 （ p75-p77 ）的基本操作， 并编制主函数实际运行验证其正确性。4. 对顺序循环队列，常规的方法是使用队尾指针和队头指针，队尾指针用于指示当前的队 尾位置下标，队头指针用于指示当

3、前的队头位置下标。现要求：（ 1） 设计一个使用队头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化、入队列、出队列、取队头元素和判断队列是否为空。（ 2） 设计一个测试主函数进行测试。三、实验结果与分析(程序代码按序粘贴在下面，并将运行结果截图)1#include#includetypedef int DataType;typedef struct snodeDataType data;struct snode *next; LSNode; /* 初始化操作： */void StackInitiate(LSNode *head)/* 初始化带头结点链式堆栈 */if(*head

4、= (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

5、*)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 =

6、 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

7、 = head;while(p != NULL)p1 = p;p = p-next;free(p1);void 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;elseprintf(The element of local top is :%dn,x); printf(The sequence o

8、f outing elements is:n); while(StackNotEmpty(myStack) StackPop(myStack, &x);printf(%d , x);printf(n);Destroy(myStack);2#include #include #define MaxStackSize 100 typedef int DataType;typedef structDataType stackMaxStackSize; int top; SeqStack; /* 初始化操作： */ void StackInitiate(SeqStack *S) /* 初始化带头结点链

9、式堆栈 */S-top=0;int StackNotEmpty(SeqStack S)if(S.toptop=MaxStackSize)printf( 堆栈已满无法插入 !n);return 0;elseS-stackS-top=x;S-top+;return 1;int StackPop(SeqStack *S, DataType *d)if(S-toptop-;*d=S-stackS-top;return 1;int StackTop(SeqStack S, DataType *d)if(S.top=0)printf( 堆栈已空 !n);return 0;else*d=S.stackS.t

10、op-1;return 1;void main(void)SeqStack myStack;int i,x;StackInitiate(&myStack); for(i=0;irear=0;Q-front=0;Q-count=0;int QueueNotEmpty(SeqCQueue Q)if(Q.count!=0)return 1;elsereturn 0;int QueueAppend(SeqCQueue *Q,DataType x)if(Q-count0&Q-rear=Q-front)printf( 队列已满无法插入！ n); return 0;elseQ-queueQ-rear=x;Q

11、-rear=(Q-rear+1)%MaxQueueSize;Q-count+;return 1;int QueueDelete(SeqCQueue *Q,DataType *d)if(Q-count=0)printf( 队列已空无数据元素出队列 !n); return 0;else*d=Q-queueQ-front; Q-front=(Q-front+1)%MaxQueueSize; Q-count-;return 1;int QueueGet(SeqCQueue Q,DataType *d)if(Q.count=0)printf( 队列已空无数据可取 n);return 0;else*d=Q

12、.queueQ.front;return 1;void main(void)SeqCQueue myQueue;int i,x;QueueuInitiate(&myQueue); for(i=0;irear=0;Q-front=0;Q-count=0;int QueueNotEmpty(SeqCQueue Q)if(Q.front!=Q.rear) return 1;elsereturn 0;int QueueAppend(SeqCQueue *Q,DataType x) if(Q-front=(Q-rear+1)%MaxQueueSize) printf( 队列已满无法插入！ n); ret

13、urn 0;elseQ-queueQ-rear=x; Q-rear=(Q-rear+1)%MaxQueueSize; Q-count+;return 1;int QueueDelete(SeqCQueue *Q,DataType *d) if(Q-front=Q-rear) printf( 队列已空无数据元素出队列 !n); return 0;else*d=Q-queueQ-front; Q-front=(Q-front+1)%MaxQueueSize; Q-count-;return 1;int QueueGet(SeqCQueue Q,DataType *d)if(Q.front=Q.rear)printf( 队列已空无数据可取 n); return 0;else*d=Q.queueQ.front;return 1;void main(void)SeqCQueue myQueue;int i,x;QueueuInitiate(&myQueue); for(i=0;i5;i+)if(QueueAppend(&myQueue,i+1)