数据结构堆栈与队列实验报告.doc
文本预览下载声明
PAGE
PAGE 8
实验二 堆栈和队列
实验目的：
1.熟悉栈这种特殊线性结构的特性；
2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算；
3.熟悉队列这种特殊线性结构的特性；
3.熟练掌握队列在链表存储结构下的基本运算。
实验原理：
堆栈顺序存储结构下的基本算法；
堆栈链式存储结构下的基本算法；
队列顺序存储结构下的基本算法；
队列链式存储结构下的基本算法；
实验内容：
第一题 链式堆栈设计。要求
（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个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。
第二题 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求：
（1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空；
（2）编写主函数进行测试。
程序代码：
第一题：
（1）源程序LinStack.h如下：
#define NULL 0
typedef struct snode
{ DataType data;
struct snode *next;
} LSNode;
/*（1）初始化 StackInitiate(LSNode ** head) */
void StackInitiate(LSNode ** head)
/*初始化带头结点链式堆栈*/
{ if((*head=(LSNode *)malloc(sizeof(LSNode)))==NULL)exit(1);
(*head)-next=NULL;
}
/*（2）非空否 StackNotEmpty(LSNode * head) */
int StackNotEmpty(LSNode * head)
/*判断堆栈是否为空，非空返回1，否则返回0*/
{ if(head-next==NULL) return 0;
else return 1;
}
/*（3）入栈StackPush(LSNode * head, DataType x) */
int StackPush(LSNode *head, DataType x)
/*把数据元素x插压入链式堆栈head的栈顶作为新的栈顶，*/
/*入栈成功返回1，否则返回0 */
{ LSNode *p;
if((p=(LSNode *)malloc(sizeof(LSNode)))==NULL)
{ printf(The memory space is not enough!\n);
return 0;
}
p-data=x;
p-next=head-next; /*新结点入栈*/
head-next=p; /*新结点成为新的栈顶*/
return 1;
}
/*（4）出栈StackPop(SLNode *head, DataType *d) */
int StackPop(LSNode *head, DataType *d)
/*出栈并把栈顶数据元素值带到参数d，*/
/*出栈成功返回1，否则返回0 */
{ LSNode *p;
p=head-next;
if(p==NULL)
{ printf(The Stack has been empty!\n);
return 0;
}
head-next=p-next;
*d=p-data;
free(p);
return 1;
}
/*（5）取栈顶数据元素StackTop(LSNode *head, DataType *d) */
int StackTop(LSNode *he
显示全部