武汉工商学院
《数据结构》课程实验实训报告
实验名称 栈与队列 学 号 实验日期 14302043 2015.11.15 姓 名 指导教师 陈前方 金照林 实验序号 班 级 成 绩 3 信管本二 一、实验目的和要求 目的：掌握堆栈和队列数据结构描述，学会针对堆栈和队列的基本操作。 要求：掌握C语言结构化程序设计思想，结构数据类型，指针数据类型。 二、实验具体内容及步骤 1. 实现课本中链式堆栈（p64-p66）的基本操作，并编制主函数实际运行验证其正确性。 2. 链式堆栈设计。要求： （1） 用链式堆栈设计实现堆栈，堆栈的操作集合包括：初始化、非空否、入栈、出栈、取栈顶数据元素。 （2） 设计一个主函数对链式堆栈进行测试。测试方法为依次把数据元素1、2、3、4、5入栈，然后出栈并在屏幕上显示出栈的数据元素。 （3） 定义数据元素的数据类型为如下形式的结构体： typedef struct{ char taskName[10]; //任务名 int taskNo; //任务号 }DataType; 首先设计一个包含5个数据的测试数据，然后设计一个主函数对链式堆栈进行测试。测试的方法为：依次把5个元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 3. 实现课本中顺序循环队列（p75-p77）的基本操作，并编制主函数实际运行验证其正确性。 4. 对顺序循环队列，常规的方法是使用队尾指针和队头指针，队尾指针用于指示当前的队尾位置下标，队头指针用于指示当前的队头位置下标。现要求： （1） 设计一个使用队头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化、入队列、出队列、取队头元素和判断队列是否为空。 （2） 设计一个测试主函数进行测试。 武汉工商学院
三、实验结果与分析（程序代码按序粘贴在下面，并将运行结果截图） 1．#include #include typedef int DataType; typedef struct snode { DataType 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\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); } } void main(void) { LSNode *myStack; int i, x; StackInitiate(&myStack); for(i=0;i<5;i++) { if(StackPush(myStack,i+1)==0) { printf(\ return; } } if(StackTop(myStack,&x)==0) { printf(\ return; } else printf(\ printf(\ while(StackNotEmpty(myStack)) { StackPop(myStack, &x); printf(\ } printf(\ Destroy(myStack); printf(\武汉工商学院
} 2．#include #include #define MaxStackSize 100 typedef int DataType; typedef struct { DataType stack[MaxStackSize];; int top; } SeqStack; /*初始化操作：*/ void StackInitiate(SeqStack *S) /*初始化带头结点链式堆栈*/ { S->top=0; } int StackNotEmpty(SeqStack S) { if(S.top<=0) return 0; else return 1; } /*入栈操作：*/
loading