数据结构 实验二 查找与排序.docx
- 文档编号:1148968
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:14
- 大小:74.26KB
数据结构 实验二 查找与排序.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);} 运行结果 三、结论(写本次实验的收获) 了解栈和队列的顺序存储结构和链式存储,例如: 先进后出与先进先出的原则,掌握栈和队列的基本操作方法,以及数值转换,删除队列元素的方法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验二 查找与排序 实验 查找 排序