大连理工大学810数据结构

下面是好好范文网小编收集整理的大连理工大学810数据结构，仅供参考，欢迎大家阅读！

1.进制转换

#define N 8//定义待转换的进制N（二进制-九进制）typedefint SElemType;//定义栈元素类型为整数voidconversion1//对于输入的任意一个非负十进制整数，打印输出与其等值的N进制数	SqStack s;unsigned n;//非负整数	SElemType e;InitStack(s);//初始化栈printf("将十进制整数n转换为%d进制数，请输入：n(>=0)=", Nn);//输入非负十进制整数nwhile(n)//当n不等于0s, n%N);//入栈n除以N的余数（N进制的低位）		n = n / NStackEmpty(s))//当栈不空s, e);//弹出栈顶元素且赋值给eprintf eprintf

2.十进制转十六进制

voidconversion2()//十进制->十六进制{	SqStack s;unsigned n;//非负整数	SElemType e;InitStack(s);//初始化栈printf("将十进制整数n转换为十六进制数，请输入:n(>=0)="n);//输入非负十进制整数nwhile(n)//当n不等于0s, n //入栈n除以16的余数（十六进制的低位）		n = n StackEmpty(s))//当栈不空s, e);//弹出栈顶元素且赋值给eif(e printf eprintf e //大于9的余数，输出相应的字符}printf

3.括号匹配的检验

typedefchar SElemType//对于输入的任一字符串，检验括号是否匹配	SqStack s;	SElemType chp, e;InitStack(s);//初始化栈成功printf("请输入带括号（()、和）的表达式n"ch);	p = ch;//p指向字符串的首字符p)//没到串尾{switch(*ps,*p//左括号入栈，且p++StackEmpty(ss, e);//弹出栈顶元素 e =='('&&*p  e =='['&&*p  e =='{'&&*p //出现3中匹配情况之外的情况printf("左右括号不配对n"ERRORprintf("缺乏左括号n"ERRORdefault:			p++;//其他字符不处理，指针向后移StackEmpty(s))//字符串结束时栈空printf("括号匹配n"printf("缺乏左括号n"

4.行编辑程序

FILE *fpSElemType c){//将字符c送至fp所指的文件中fputc(c, fpLineEdit//利用字符栈s，从终端接受一行并送至调用过程的数据区	SqStack s;char ch;InitStack(s);printf("请输入一个文本文件,^Z结束输入：n");	ch =getcharch //当全文没结束（EOF为^Z键，全文结束）while(ch !=EOF&& ch //当全文没结束且没到行末(不说换行符)switch(chStackEmpty(ss, ch//仅当栈非空时退栈，c可由ch代替ClearStack(s);//重置s为空栈break;defaults, ch);//其他字符进栈}			ch =getchar//从终端接受下一个字符}StackTraverse(s, copy);//将从栈底到栈顶的栈内字符传送至文件 fp);//向文件输入一个换行符ClearStack(s);//重置s为空栈if(ch 			ch =getcharDestroyStack(s

5.迷宫问题

struct PosType//迷宫坐标位置类型{int x y#define MAXLENGTH 25 //设迷宫的最大行列为25typedefint MazeType[MAXLENGTH][MAXLENGTH];//迷宫数组类型[行][列]MazeType m;//迷宫数组int x, y;//迷宫的行数，列数PosType begin1, end1;//迷宫的入口坐标，出口坐标//输出迷宫的解（m数组）int i, ji  i < x; ij  j < y; jprintf m[i][jprintf k){//设定迷宫的布局（墙为值0，通道值为k）int i, j, x1, y1;printf("请输入迷宫的行数，列数（包括外墙）：""%d,%d",&x,&yi  i < x; i++)//定义周边值为0（外墙）{		mi		m[x ii  i < y; i		m[i		m[i][y i  i <= x  ij  j <= y  j			m[i][j]= k;//定义除外墙，其余都是通道，初值为k}}printf("请输入迷宫内墙单元数："j);printf("请依次输入迷宫内墙每个单元的行数、列数：n"i  i <= j; i"%d,%d",&x1, y1);		m[x1][y1//修改墙的值为0}printf("迷宫结构如下：n"printf("输入入口的行数，列数：""%d,%d",&begin1.x,&begin1.y);printf("输入出口的行数，列数：""%d,%d",&end1.x,&end1.y

6.利用栈求解迷宫问题

int curstep //当前足迹，初值（在入口处）为1struct SElemType//栈的元素类型{int ord;//通道块在路径上的“序号”	PosType seat;//通道块在迷宫中的“坐标位置”int di;//从此通道块走向下一通道的“方向”（0-3表示东-北）};Status Pass(PosType b){//当迷宫m的b点的序号为1（可通过路径），返回OK；否则，返回ERRORif(m[b.x][b.yreturn OK;elsereturn ERRORFootPrint(PosType a){//使迷宫m a点的值变为足迹（curstep）	m[a.x][a.y]= curstepNextPos(PosType &c,int di){//根据当前位置及移动方向，求得下一位置	PosType direc//{行增量，列增量}，移动方向，依次是东南西北	c.x += direc[di].x;	c.y += direc[di].yMarkPrint(PosType b){//使迷宫m的b点的序号变为-1（不能通过的路径）	m[b.x][b.yStatus MazePath(PosType start, PosType end){//若迷宫m中存在从入口start到出口end的通道，//则求得一条存放在栈中（从栈底到栈顶），并返回TRUE；否则返回FALSE	SqStack S;//顺序栈	PosType curpos;//当前位置	SElemType e;//栈元素；InitStack(S);//初始化栈	curpos = start;//当前位置在入口curpos//当前位置可以通过，即是未曾走到过的通道块FootPrint(curpos);//留下足迹			e.ord = curstep;			e.seat = curpos;			e.di S, e);//入栈当前位置及状态			curstep++;//足迹加1if(curpos.x == end.x && curpos.y == end.y)//到达终点（出口）return TRUE;NextPos(curpos, e.di);//由当前位置及移动方向，确定下一个当前位置//当前位置不能通过StackEmpty(SS, e);//退栈到前一位置				curstep--;//足迹再减一while(e.di ==3&&!StackEmpty(S))//前一位置处于最后一个方向（北）{MarkPrint(e.seat);//在前一位置留下不能通过的标记（-1）Pop(S, e);//再退回一步					curstep--;//足迹再减1e.di //没到最后一个反向（北）{					e.di++;//换下一个方向探索Push(S, e);//入栈该位置的下一个方向					curstep++;//足迹加1					curpos = e.seat;//确定当前位置NextPos(curpos, e.di);//确定下一个当前位置是该新方向上的相邻块StackEmpty(Sreturn FALSE//初始化迷宫，通道值为1if(MazePath(begin1, end1printf("此迷宫从入口到出口的一条路径如下：n"//输出此通路printf("此迷宫无通路n"

迷宫程序运行结果：

7.表达式求值

charPreCede(SElemType t1, SElemType t2){//判断两符号的优先关系char f;switch(t2t1  t1 			f ='<';//t1<t2else			f ='>';//t1>t2t1  t1  t1 			f ='>';//t1>t2else			f ='<';//t1<t2t1 printf("括号不匹配n"ERROR			f ='<';//t1<t2switch(t1			f //t1=t2printf("缺乏左括号n"ERROR);default:			f ='>';//t1>t2switch(t1			f //t1=t2printf("缺乏左括号n"ERROR);default:			f ='>';//t1>t2}}return f;}
8
Status In(SElemType c){//判断c是否为7中运算符之一switch(creturn TRUE;default:return FALSE
9
SElemType Operate(SElemType a, SElemType theta, SElemType b){//做四则运算a、theta、b，返回运算结果switch(thetareturn a + breturn a - breturn a * b;}return a / b;}
10.表达式求值
typedefchar SElemType;//栈元素为字符型SElemType EvaluateExpression//算数表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈	SqStack OPTR, OPND;	SElemType a, b, c, x;InitStack(OPTR);//初始化运算符栈OPTR和运算数栈OPNDInitStack(OPNDOPTR//将换行符压入运算符栈OPTR栈底（改）	c =getchar//由键盘读入1个字符到cGetTop(OPTR, x);//将运算符栈OPTR的栈顶元素赋给xwhile(c  x //c和x不都是换行符c))//c是7种运算符之一{switch(PreCede(x,c))//判断x和c的优先权{case'<'OPTR, c);//栈顶元素x的优先权低，入栈c				c =getchar//由键盘读入下一个字符到cOPTR, x);//x='(' 且 c=')'情况，弹出'('给x（后又扔掉）				c =getchar//由键盘读入下一个字符到c（扔掉‘）’）'>'OPTR, x);//栈顶元素x的优先权高，弹出运算符栈OPTR的栈顶元素给x（改）Pop(OPND, b);//依次弹出运算数栈OPND的栈顶元素给b，aPop(OPND, aOPND,Operate(a, x, b//做运算a x b，并将运算结果入运算数栈c >='0'&& c //c是操作数OPND, c //将该操作数的值（不是ASCII码）压入运算数栈OPND			c =getchar//由键盘读入下一个字符到c}else//c是非法字符{printf("出现非法字符n"ERRORGetTop(OPTR, x);//将运算符栈OPTR的栈顶元素赋给xOPND, x);//弹出运算数栈OPND的栈顶元素（运算结果）给x（改此处）StackEmpty(OPND//运算数栈OPND不空（运算符栈OPTR仅剩‘n’）{printf("表达式不正确|n"ERRORreturn x;}