实验报告
课程 学号
数据结构 姓名 实验名称 实验二 堆栈和队列 实验日期： 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 taskName[10]; int taskNo; }DataType;
首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。
3-19 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求：
（1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写一个主函数进行测试。
实验结果：
3-18
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\ 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<> #include<>
typedef int DataType; #include \ void main(void) { LSNode *myStack;