数据结构教程第十七课实验三栈的表示与实现及栈的应用



《数据结构教程第十七课实验三栈的表示与实现及栈的应用》由会员分享,可在线阅读,更多相关《数据结构教程第十七课实验三栈的表示与实现及栈的应用(11页珍藏版)》请在装配图网上搜索。
1、► 数据结构教程 第十七课 实验三:栈的表示与实现及栈的应用
数据结构教程 第十七课 实验三:栈的表示与实现及栈的应用
教学目的: 掌握栈的存储表示方式和栈基本操作的实现方法
教学重点: 栈的基本操作实现方法,栈的应用
教学难点: 栈的存储表示
实验内容:
一、栈的实现
实现栈的顺序存储。
栈实现示例
#include
2、1 #define OVERFLOW -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status ; struct STU{ char name[20]; char stuno[10]; int age; int score; }; typedef struct STU SElemType; struct STACK { SElemType *base; SElemType *top; int stacksize; }; t
3、ypedef struct STACK SqStack; typedef struct STACK *pSqstack; Status InitStack(SqStack **S); Status DestroyStack(SqStack *S); Status ClearStack(SqStack *S); Status StackEmpty(SqStack S); int StackLength(SqStack S); Status GetTop(SqStack S,SElemType *e); Status Push(SqStack *S,SElemType e);
4、 Status Pop(SqStack *S,SElemType *e); Status StackTraverse(SqStack S,Status (*visit)()); Status InitStack(SqStack **S) { (*S)=(SqStack *) malloc(sizeof(SqStack)); (*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if(!(*S)->base)exit(OVERFLOW); (*S)->top=(*S)->base
5、; (*S)->stacksize=STACK_INIT_SIZE; return OK; } Status DestroyStack(SqStack *S) { free(S->base); free(S); } Status ClearStack(SqStack *S) { S->top=S->base; } Status StackEmpty(SqStack S) { if(S.top==S.base) return TRUE; else return FALSE; } int StackLength(
6、SqStack S) { int i; SElemType *p; i=0; p=S.top; while(p!=S.base) {p++; i++; } } Status GetTop(SqStack S,SElemType *e) { if(S.top==S.base) return ERROR; *e=*(S.top-1); return OK; } Status Push(SqStack *S,SElemType e) { /* if(S->top - S->base>=S-
7、>stacksize) { S->base=(SElemType *) realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType)); if(!S->base)exit(OVERFLOW); S->top=S->base+S->stacksize; S->stacksize += STACKINCREMENT; } */ *(S->top++)=e; return OK; } Status Pop(SqSta
8、ck *S,SElemType *e) { if(S->top==S->base) return ERROR; *e=*--S->top; return OK; } Status StackPrintElem(SElemType * e) { printf("%s %s %d %d\n",e->name,e->stuno,e->age,e->score); } Status StackTraverse(SqStack S,Status (*visit)()) { while(S.top!=S.base) visit(--S.to
9、p); } main() { SElemType e; SqStack *Sa; clrscr(); printf("\n\n-------------------SqStack Demo is running...----------------\n\n"); printf("First is Push function.\n"); InitStack(&Sa); strcpy(e.name,"stu1"); strcpy(e.stuno,"100001"); e.age=80; e.score=1000;
10、 printf(" Now Stack is Empty.\n"); StackTraverse(*Sa,StackPrintElem); Push(Sa,e); printf(" Now Stack has one element.\n"); StackTraverse(*Sa,StackPrintElem); strcpy(e.name,"stu3"); strcpy(e.stuno,"100002"); e.age=80; e.score=1000; Push(Sa,e); printf(" N
11、ow Stack has another element.\n"); StackTraverse(*Sa,StackPrintElem); printf(" Now Pop Stack,the top elem put into variable e.\n"); Pop(Sa,&e); printf("%s\n%s\n%d\n%d\n",e.name,e.stuno,e.age,e.score); printf(" Let's see the left of Stack's elem:\n"); StackTraverse(*Sa,Stack
12、PrintElem);
getch();
printf("\n\n\nWelcom to visit \n\n");
}
二、栈的应用
1、利用栈实现数制转换 2、利用栈实现单行编辑
以上任选一题。
数制转换示例
#include
13、rsion() { pSqStack S; SElemType e; int n; InitStack(&S); printf("Input a number to convert to OCT:\n"); scanf("%d",&n); if(n<0) { printf("\nThe number must be over 0."); return; } if(!n) Push(S,0); while(n){ Push(S,n%8); n=n/8; } printf("the
14、 result is: ");
while(!StackEmpty(*S)){
Pop(S,&e);
printf("%d",e);
}
}
main()
{
printf("\n\n\n\n");
conversion();
getch();
printf("\n\nWelcome to visit !");
}
单行编辑示例
#include
15、 '`' typedef char SElemType; #include "stack.h" Status visit(SElemType * e) { printf("%c", *e); } char OP[10]={'+','-','*','/','(',')','#'}; int precede[7][7]={ 1,1,2,2,2,1,1, 1,1,2,2,2,1,1, 1,1,1,1,2,1,1, 1,1,1,1,2,1,1, 2,2,2,2,2,3,0, 1,1,
16、1,1,0,1,1, 2,2,2,2,2,0,3}; int In(char c,char *op) { int i=0; while(i<7) if(c==op[i++]) return 1; return 0; } char Precede(char op,char c) { int pos_op; int pos_c; int i; for(i=0;i<7;i++) { if(op==OP[i]) pos_op=i; if(c==OP[i]) pos
17、_c=i; } switch(precede[pos_op][pos_c]) { case 1: return '>'; case 2: return '<'; case 3: return '='; } } char Operate(int a,char theta,int b) { switch(theta) { case '+':return a+b-'0'; case '-':return a-b+'0'; case '*':retur
18、n (a-'0')*(b-'0')+'0'; case '/':return (a-'0')/(b-'0')+'0'; } } char EvaluateExpression() { SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitStack(&OPTR); Push(OPTR,'#'); InitStack(&OPND); c=getchar(); while(c!='#'||GetTop(*OPTR)!='#') { if(!In(c,
19、OP)) {Push(OPND,c);c=getchar();} else switch(Precede(GetTop(*OPTR),c)) { case '<': Push(OPTR,c); c=getchar(); break; case '=': Pop(OPTR,&x); c=getchar(); break; case '>': Pop(OPTR,&theta); Pop(OPND,&b);
20、 Pop(OPND,&a); Push(OPND,Operate(a,theta,b)); break; } } c=GetTop(*OPND); DestroyStack(OPTR); DestroyStack(OPND); return c; } main() { char i; printf("\n\n\n\nOnly within 0..9 evaluation,input a expression end with symbol #:\n"); i=EvaluateExpress
21、ion(); printf("\nThis expression's result is: "); printf("%d\n\n\n\n",i-'0'); printf("\n\nWelcome to visit !"); } 这里是实现栈的头文件 #include "simuc.h" #define OVERFLOW -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status; struct STACK { SElemType *b
22、ase; SElemType *top; int stacksize; }; typedef struct STACK SqStack; typedef struct STACK *pSqStack; Status InitStack(SqStack **S); Status DestroyStack(SqStack *S); Status ClearStack(SqStack *S); Status StackEmpty(SqStack S); int StackLength(SqStack S); SElemType GetTop(SqStack S
23、); Status Push(SqStack *S,SElemType e); Status Pop(SqStack *S,SElemType *e); Status StackTraverse(SqStack S,Status (*visit)()); Status InitStack(SqStack **S) { (*S)=(SqStack *)malloc(sizeof(SqStack)); (*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if(!(*S)->base)
24、exit(OVERFLOW); (*S)->top=(*S)->base; (*S)->stacksize=STACK_INIT_SIZE; return OK; } Status DestroyStack(SqStack *S) { free(S->base); free(S); } Status ClearStack(SqStack *S) { S->top=S->base; } Status StackEmpty(SqStack S) { if(S.top==S.base) return TRUE; else
25、 return FALSE; } int StackLength(SqStack S) { int i; SElemType *p; i=0; p=S.top; while(p!=S.base) {p++; i++; } } SElemType GetTop(SqStack S) { if(S.top==S.base) return ERROR; return *(S.top-1); } Status Push(SqStack *S,SElemType e) { /* if(S
26、->top - S->base>=S->stacksize) { S->base=(SElemType *) realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType)); if(!S->base)exit(OVERFLOW); S->top=S->base+S->stacksize; S->stacksize += STACKINCREMENT; } */ *(S->top++)=e; return OK; } Status Pop(SqStack *S,SElemType *e) { if(S->top==S->base) return ERROR; *e=*(--(S->top)); return OK; } Status StackTraverse(SqStack S,Status (*visit)()) { while(S.top>S.base) visit(--S.top); }
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年水电工程运行维护管理合同示范文本.docx
- 2025年工程勘测设计合同模板.docx
- 2025年区域产品销售代理合同.docx
- 2025年经销商授权合同样本.docx
- 2025年员工住房资金借贷合同.docx
- 2025年轻钢建筑施工合同示例.docx
- 2025年网络推广托管合同.docx
- 2025年简明个人借款正式合同范例.docx
- 2025年房产按揭贷款合同范例.docx
- 2025年技术合同争议调解.docx
- 2025年电子版城市住宅租赁合同范本.docx
- 2025年简易转让合同协议书样本.docx
- 2025年投资顾问服务合同实例.docx
- 2025年经销合同模板.docx
- 2025年工业项目设计合同样本.docx