2020年数据结构实验报告.doc

数据结构实验报告
想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是人才给大家收集的数据结构实验报告，供大家阅读参考。
一、实验目的及要求
1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。
本实验训练的要点是“栈”和“队列”的观点;
二、实验内容
1)利用栈，实现数制转换。
2)利用栈，实现任一个表达式中的语法检查(选做)。
3)编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
三、实验流程、操作步骤或核心代码、算法片段
顺序栈：
StatusInitStack(SqStack&S)
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)
returnERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusDestoryStack(SqStack&S)
{
free(S.base);
returnOK;
}
StatusClearStack(SqStack&S)
{
S.top=S.base;
returnOK;
}
StatusStackEmpty(SqStackS)
{
if(S.base==S.top)
returnOK;
returnERROR;
}
intStackLength(SqStackS)
{
returnS.top-S.base;
}
StatusGetTop(SqStackS,ElemType&e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)returnERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
StatusPush(SqStack&S,ElemTypee)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)
returnERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
StatusPop(SqStack&S,ElemType&e)
{
if(S.top==S.base)
returnERROR;
e=*--S.top;
returnOK;
}
StatusStackTraverse(SqStackS)
{
ElemType*p;
p=(ElemType*)malloc(sizeof(ElemType));
if(!p)returnERROR;
p=S.top;
while(p!=S.base)//S.top上面一个...
{
p--;
printf("%d",*p);
}
returnOK;
}
StatusCompare(SqStack&S)
{
intflag,TURE=OK,FALSE=ERROR;
ElemTypee,x;
InitStack(S);
flag=OK;
printf("请输入要进栈或出栈的元素：");
while((x=getchar())!='#'&&flag)
{
switch(x)
{
case'(':
case'[':
case'{':
if(Push(S,x)==OK)
printf("括号匹配成功!\n\n");
break;
case')':
if(Pop(S,e)==ERROR||e!='(')
{
printf("没有满足条件\n");
flag=FALSE;
}
break;
case']':
if(Pop(S,e)==ERROR||e!='[')
flag=FALSE;
break;
case'}':
if(Pop(S,e)==ERROR||e!='{')
flag=FALSE;
break;
}
}
if(flag&&x=='#'&&StackEmpty(S))
returnOK;
else
returnERROR;
}
链队列：
StatusInitQueue(LinkQueue&Q)
{
Q.front=Q.rear=
(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)returnERROR;
Q.front->next=NULL;
returnOK;
}
StatusDestoryQueue(LinkQueue&Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
returnOK;
}
StatusQueueEmpty(LinkQueue&Q)
{
if(Q.front->next==NULL)
returnOK;
returnERROR;
}
StatusQueueLength(LinkQueueQ)
{
inti=0;
QueuePtrp,q;
p=Q.front;
while(p->next)
{
i++;
p=Q.front;
q=p->next;
p=q;
}
returni;
}
StatusGetHead(LinkQueueQ,ElemType&e)
{
QueuePtrp;
p=Q.front->next;
if(!p)
returnERROR;
e=p->data;
returne;
}
StatusClearQueue(LinkQueue&Q)
{
QueuePtrp;
while(Q.front->next)
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
Q.front->next=NULL;
Q.rear->next=NULL;
returnOK;
}
StatusEnQueue(LinkQueue&Q,ElemTypee)
{
QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
returnERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;//p->next为空
returnOK;
}
StatusDeQueue(LinkQueue&Q,ElemType&e)