数据结构 实验二 查找与排序.docx
《数据结构 实验二 查找与排序.docx》由会员分享，可在线阅读，更多相关《数据结构 实验二 查找与排序.docx（14页珍藏版）》请在冰点文库上搜索。
数据结构实验二查找与排序
实验二栈、队列的实现及应用
实验课程名：
高级语言程序设计
专业班级：
11计科一班学号：
姓名：
实验时间：
12.11实验地点：
教师：
一、实验目的和要求
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2、掌握栈和队列的特点，即先进后出与先进先出的原则。
3、掌握栈和队列的基本操作实现方法。
二、实验的内容和步骤
（一）1、实现栈的顺序存储和链式存储
代码：
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineMAXQSIZE100
#defineOK1
#defineERROR0
#include"stdio.h"
#include"iostream.h"
#include"malloc.h"
#include"stdlib.h"
typedefintSElemType;
typedefstruct//definestructureSqStack（）
{SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
intInitStack（SqStack&S）//InitStack（）sub-function
{S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）
{cout<";
return（ERROR）;
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return（OK）;
}//InitStack（）end
intPush（SqStack&S,SElemTypee）//Push（）sub-function
{if（S.top-S.base>S.stacksize）
{S.base=（SElemType*）realloc（S.base,（S.stacksize+
STACKINCREMENT*sizeof（SElemType）））;
if（!
S.base）
{cout<";
return（ERROR）;
}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return（OK）;
}//Push（）end
intPop（SqStack&S,SElemType&e）//Pop（）sub-function
{if（S.top==S.base）
{cout<";
return（ERROR）;
}
e=*--S.top;
return（OK）;
}//Pop（）end
voidmain（）
{
SqStackS;
SElemTypee;
InitStack（S）;
intj,n;
cin>>j;
for（n=0;n{
scanf（"%d",&e）;
Push（S,e）;
}
for（n=j;n>0;n--）
{
Pop（S,e）;
printf（"%d",e）;
}
printf（"\n"）;
}
运行结果
（二）1、利用栈实现数制转换
代码：
#include
#include
#include
#include
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineMAXQSIZE100
#defineOK1
#defineERROR0
typedefintSElemType;
typedefstruct
{SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
intInitStack（SqStack&S）
{S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）
{cout<";
return0;}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return1;
}intGetTop（SqStackS,SElemType&e）
{if（S.top==S.base）
{cout<";
return0;
}e=*（S.top-1）;return1;
}intStackEmpty（SqStackS）
{if（S.top==S.base）return1;
elsereturn0;
}intPush（SqStack&S,SElemTypee）
{if（S.top-S.base>S.stacksize）
{S.base=（SElemType*）realloc（S.base,（S.stacksize+
STACKINCREMENT*sizeof（SElemType）））;if（!
S.base）
{cout<";
return0;}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}*S.top++=e;
return1;}
intPop（SqStack&S,SElemType&e）
{if（S.top==S.base）
{cout<";
return0;
}e=*--S.top;
return1;
}voidConversion（）
{SqStackS;
SElemTypeN,e;
InitStack（S）;
printf（"请输入想转数据：
"）;
scanf（"%d",&N）;
while（N）
{Push（S,N%8）;
N=N/8;}
printf（"所给数据进制转换后为：
"）;
while（!
StackEmpty（S））
{Pop（S,e）;
printf（"%d",e）;
}cout<}
voidmain（）
{
Conversion（）;
}
3、运行结果
（三）1、利用栈实现表达式求值
2、源代码
#include
#include
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT100
usingnamespacestd;
typedefdoubleSElemType;
typedefstructSqStack
{SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
voidInitStack（SqStack&S）
{S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）exit（-1）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}intGetTop（SqStackS,SElemType&e）
{if（S.top==S.base）
returnfalse;
e=*（S.top-1）;
returntrue;
}intPush（SqStack&S,SElemTypee）
{if（S.top-S.base>=S.stacksize）
{S.base=（SElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
S.base）exit（-1）;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}*S.top++=e;
returntrue;
}intPop（SqStack&S,SElemType&e）
{if（S.top==S.base）
returnfalse;
e=*--S.top;
returntrue;
}charPrecede（chara1,chara2）
{charr;
switch（a2）
{
case'+':
case'-':
if（a1=='（'||a1=='#'）
r='<';
else
r='>';
break;
case'*':
case'/':
if（a1=='*'||a1=='/'||a1=='）'）
r='>';
else
r='<';
break;
case'（':
if（a1=='）'）
{cout<<"括号匹配错误!
"<exit（-1）;}
else
r='<';
break;
case'）':
if（a1=='（'）
r='=';
elseif（a1=='#'）
{cout<<"error!
没有左括号"<exit（-1）;}
else
r='>';
break;
case'#':
switch（a1）
{case'#':
r='=';
break;
case'（':
cout<<"error!
没有右括号"<exit（-1）;
default:
r='>';
}break;
}returnr;
}charIn（chard）
{switch（d）
{case'+':
case'-':
case'*':
case'/':
case'（':
case'）':
case'#':
returntrue;
default:
returnfalse;
}}SElemTypeOperate（SElemTypea,SElemTypetheta,SElemTypeb）
{charn=char（theta）;switch（n）
{case'+':
returna+b;
case'-':
returna-b;
case'*':
returna*b;
default:
if（b!
=0）
returna/b;
else
{cout<<"error!
除数不能为零"<exit（-1）;}}}
SElemTypeEvaluateExpression（）
{SqStackOPTR,OPND;
charc;
charData[11];
SElemTypea,b,d,e;
InitStack（OPTR）;
InitStack（OPND）;
Push（OPTR,'#'）;
c=getchar（）;
GetTop（OPTR,e）;
while（c!
='#'||e!
='#'）
{if（In（c））{
switch（Precede（e,c））
{case'<':
Push（OPTR,c）;
c=getchar（）;
break;
case'=':
Pop（OPTR,e）;
c=getchar（）;
break;
case'>':
Pop（OPTR,e）;
Pop（OPND,b）;
Pop（OPND,a）;
Push（OPND,Operate（a,e,b））;
break;}
}elseif（c>='0'&&c<='9'||c=='.'）
{inti=0;while（c>='0'&&c<='9'||c=='.'）
{Data[i]=c;i++;
c=getchar（）;}
Data[i]='\0';
d=atof（Data）;
Push（OPND,d）;
}else{
cout<<"error!
输入错误!
"<exit（-1）;}
GetTop（OPTR,e）;}
GetTop（OPND,e）;
returne;}
intmain（）{
SElemTyperesult;
cout<<"请输入要计算的表达式，并以#号结束"<result=EvaluateExpression（）;
cout<<"结果为:
"<return0;
}3、运行结果
（四）实现循环队列的存储和链队列的基本操作
#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
#include"iostream.h"
#defineMAXQSIZE5
#defineOverflow
#defineOK1
#defineERROR0
typedefintQElemType;
typedefstructQNode
{QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstructLinkQueue
{QueuePtrfront;
QueuePtrrear;
}LinkQueue;
intInitQueue（LinkQueue&Q）
{Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
Q.front）
{printf（"Overflow!
"）;
return（ERROR）;
}Q.front->next=NULL;return（OK）;
}intDestroyQueue（LinkQueue&Q）
{while（Q.front）
{Q.rear=Q.front->next;
free（Q.front）;Q.front=Q.rear;
}return（OK）;
}intEnQueue（LinkQueue&Q,QElemTypee）
{QNode*p;p=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）{printf（"Overflow!
"）;return（ERROR）;
}p->data=e;p->next=NULL;
if（Q.front==NULL）
{Q.front=Q.rear=p;
return（OK）;
}Q.rear->next=p;
Q.rear=p;
return（OK）;
}intDeQueue（LinkQueue&Q,QElemType&e）
{if（Q.front==Q.rear）
{printf（"Ifitwasdeleted,it'sempty!
"）;
return（ERROR）;
}QNode*p;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
free（p）;
return（OK）;
}intQueueTraverse（LinkQueueQ,void（*vi）（QElemType））
{QueuePtrp;
p=Q.front->next;
while（p）
{vi（p->data）;p=p->next;
}printf（"\n"）;returnOK;
}voidvisit（QElemTypei）
{printf（"%d",i）;
}voidmain（）
{inti,j;inte;
QElemTyped;
LinkQueueq;
i=InitQueue（q）;
if（i）for（j=1;j<=8;j++）
{cin>>e;
EnQueue（q,e）;
}QueueTraverse（q,visit）;
DeQueue（q,d）;
printf（"删除了队头元素%d\n",d）;
DestroyQueue（q）;
printf（"销毁队列后，q.front=%uq.rear=%u\n",q.front,q.rear）;}
运行结果
三、结论（写本次实验的收获）
了解栈和队列的顺序存储结构和链式存储，例如：
先进后出与先进先出的原则，掌握栈和队列的基本操作方法，以及数值转换，删除队列元素的方法。
升级会员 