栈和队列的应用实验报告.doc

栈和队列的应用(**********j)
一 实验目的
使学生掌握栈的特点及其逻辑结构和物理结构的实现；
使学生掌握队列的特点及其逻辑结构和物理结构的实现；
使学生掌握链栈和顺序栈结构的插入、删除等基本运算的实现；
使学生掌握链队列和顺序队列结构的插入、删除等基本运算的实现；
使学生熟练运用栈结构解决常见实际应用问题；
使学生熟练运用队列结构解决常见实际应用问题；
二 实验环境
所需硬件环境为微机；
所需软件环境为 Microsoft Visual C++ ；
三 实验内容
链栈:
#include ""/*详见实验1*/
LinkList InitStack_Sl() {
LinkList S;
S=InitList_Sl();
return S; }
Status DestroyStack_Sl(LinkList S) {
if(!S) return ERROR;/*链栈不存在*/
DestroyList_Sl(S);
return OK; }
Status StackEmpty_Sl(LinkList S) {
if(!S) return ERROR;/*链栈不存在*/
if(S->next==NULL)
return TRUE;
else
return FALSE; }
/*若链栈S存在，则当S非空时返回栈顶元素e */
Status StackGetTop_Sl(LinkList S) {
if(!S) return ERROR;/*链栈不存在*/
if(S->next==NULL) return FALSE;/*栈空*/
else
return (S->next->elem); }
/*若链栈S存在，则当S非空时，删除栈顶元素并用e保存删除的栈顶元素*/
Status StackPop_Sl(LinkList S,ElemType *e) {
if(!S) return ERROR;/*链栈不存在*/
ListDelete_Sl(S,e);
return OK; }
/*若链栈S存在时，插入元素e为新的栈顶元素*/
Status StackPush_Sl(LinkList S,ElemType e) {
if(!S) return ERROR;/*链栈不存在*/
ListInsert_Sl(S,e);
return OK; }
/*若链栈S存在，返回链栈中元素个数*/
int StackLength_Sl(LinkList S) {
if(!S) return ERROR;/*链栈不存在*/
return ListLength_Sl(S); }
/*若链栈S存在，遍历链栈S，对每个元素执行操作void(*operate)(ElemType*)*/
Status StackTraverse_Sl(LinkList S,void(*operate)(ElemType*)) {
if(!S) return ERROR;/*链栈不存在*/
return(ListTraverse_Sl(S,operate)); }
链队列
#include ""/*详见实验1*/
typedef struct Qode{
ElemType elem;
struct Qode *next;
} Qode,*Queue;
typedef struct {
Queue front;
Queue rear;
}Linkqueue, *LinkQueue;
/*InitQueue_Sq()构造一个空的队列*/
LinkQueue InitQueue_Sl() {
LinkQueue Q;
Q->front=Q->rear=(Queue)malloc(sizeof(Qode));
if(!Q->front) return NULL;/*存储分配失败*/
Q->front->next=NULL;
return Q; }
/*若队列Q存在，销毁链队列Q*/
Status DestroyQueue_Sl(LinkQueue Q) {
Queue p;
if(!Q) return ERROR;/*链队列不存在*/
do{ /*释放单向线性链表空间*/
p=Q->front;
Q->front=Q->front->next;
free(p);