河北联合大学数据结构报告正文文档格式.docx
《河北联合大学数据结构报告正文文档格式.docx》由会员分享，可在线阅读，更多相关《河北联合大学数据结构报告正文文档格式.docx（22页珍藏版）》请在冰点文库上搜索。
Od->
top=-1;
}/*设置栈顶为空*/
intOdpush（OdNode*Od,doublen）{/*定义数值栈入栈函数*/
if（Od->
top<
StackSize）{/*判断栈顶是否已满*/
top=Od->
top+1;
/*若栈不满，则将n进栈*/
array[Od->
top]=n;
/*栈顶元素变为n*/
return1;
}
else{/*若栈判断为满，则返回0*/
return0;
}}
doubleOdpop（OdNode*Od）{/*定义数值栈出栈函数*/
doublen;
if（-1==Od->
top）{/*判断栈顶是否为空，若栈顶为空，则返回1*/
else{
n=Od->
top];
/*若栈顶不为空，则将栈顶元素n出栈*/
（Od->
top）--;
/*有元素出栈，top自减*/
returnn;
voidOpInit（OpNode*Op）{/*初始化操作符栈*/
Op->
intOppush（OpNode*Op,ElemTypee）{/*定义操作符栈入栈函数*/
if（Op->
top=Op->
/*若栈不满，则将e进栈*/
array[Op->
top]=e;
/*栈顶元素变为e*/
return0;
ElemTypeOppop（OpNode*Op）{/*定义操作符栈出栈函数*/
ElemTypen;
if（-1==Op->
n=Op->
（Op->
intGetTop（OpNodeOp,ElemType*e）{/*定义取出栈顶元素的函数*/
if（0==Op.top）{/*若栈顶元素为空，则返回0*/
*e=Op.array[Op.top];
/*指针e指向栈顶元素*/
else{/*若栈顶元素不为空，则返回1*/
intSLevel（intmode,charoper）{/*定义比较操作符优先级的函数*/
/*返回操作符oper代表优先级的整数值，mode为1，表示oper是栈顶操作符，否则是当前操作符*/
inttmp;
/*定义临时变量*/
switch（oper）{
case'
#'
:
tmp=0;
break;
/*定义#优先级为0*/
（'
tmp=（mode?
1:
6）;
/*若（是栈顶操作符，则优先级为1，否则优先级为6*/
+'
-'
3:
2）;
/*若+或-是栈顶操作符，则优先级为3，否则优先级为2*/
*'
/'
%'
5:
4）;
/*若*、/或%是栈顶操作符，则优先级为5，否则优先级为4*/
）'
7:
1）;
/*若）是栈顶操作符，则优先级为7，否则优先级为1*/
}
returntmp;
}/*返回所得tmp的值*/
charCLevel（charw,charch）{/*判定操作符栈的栈顶操作符w与当前操作符ch之间的优先级关系*/
intgrade;
/*取得栈顶操作符与当前操作符的优先级*/
grade=SLevel（1,w）-SLevel（0,ch）;
/*计算取得操作符与当前操作符的差值*/
if（grade>
0）/*差值大于0，返回>
*/
return'
>
'
;
if（grade==0）/*说明取得操作符和当前操作符优先级相等*/
='
else/*否则，取得操作符优先级小于当前操作符*
<
voidchange（charE[],charA[]）{/*中缀变后缀的实现函数*/
/*E为原前缀式，A为要得到的后缀式*/
OpNodeOp;
/*声明一个操作符栈Op*/
inti=0;
/*i作为扫描数组E的指针*/
intj=0;
/*j用来指示数组A中待写入字符的位置*/
charch=E[i];
/*E中第一个字符送给ch*/
charw='
\0'
OpInit（&
Op）;
/*初始化操作符栈Op*/
Oppush（&
Op,'
）;
/*先把#压入栈内*/
while（ch!
）{/*当ch取得的元素不是#时执行以下命令*/
if（ch>
0'
&
ch<
9'
||ch=='
.'
）{/*若取得的元素为0到9或者是小数点*/
while（ch>
）{
A[j]=ch;
/*将获得的元素赋予A数组*/
j++;
/*A写入位置后移*/
i++;
/*E向后扫描*/
ch=E[i];
}/*将数组E的下一个元素赋值给ch*/
A[j]='
'
}/*给A中的每个数后加一个空格*/
if（ch=='
||ch=='
）{/*若取得的元素为操作符*/
GetTop（Op,&
w）;
/*取Op的栈顶元素*/
while（CLevel（w,ch）=='
）{/*栈顶操作符w比取得的操作符ch的优先级大*/
A[j]=w;
/*将w赋予数组A*/
j=j+1;
Oppop（&
/*将栈顶操作符w出栈*/
}/*取得的操作符入栈*/
if（CLevel（w,ch）=='
）/*若栈顶操作符w比取得的操作符ch的优先级小*/
Op,ch）;
/*取得的操作符直接入栈*/
if（CLevel（w,ch）=='
w!
）{/*若栈顶操作符w与取得的操作符ch的优先级相等*/
/*将栈顶操作符出栈*/
}}}/*观察栈顶操作符*/
if（E[i]!
）/*若取得的字符不是#，i加1*/
i++;
}/*将从E数组取出的元素赋予ch*/
while（w!
）{/*取得的操作符不是#*/
A[j]=w;
/*将操作符赋予A数组*/
Oppop（&
/*Op栈顶元素出栈*/
GetTop（Op,&
A[++j]='
doubleCalc（chararr[]）{/*计算后缀表达式的值*/
OdNodeOd;
/*声明一个数值栈Od*/
inti=0;
/*定义临时变量i*/
charch;
doublex=0,d=1.0;
OdInit（&
Od）;
/*初始化数值栈*/
ch=arr[i];
/*将受到的数组的元素赋值给ch*/
while（ch!
switch（ch）{/*读取字符串中的数值部分*/
case'
1'
2'
3'
4'
5'
6'
7'
8'
）{/*取得的字符不为空*/
if（'
=ch&
while（'
）{/*每读到一个整数部分就*10*/
x=x*10+（ch-'
i=i+1;
ch=arr[i];
else{if（ch=='
ch=arr[++i];
while（'
）{/*每独到一个小数部分就/10*/
d=d*10;
x=x+（ch-'
）/d;
}}}}break;
/*读取数组下一个元素*/
case'
/*若取得的字符为+，从数值栈取两个元素进行+运算*/
x=Odpop（&
Od）+Odpop（&
/*若取得的字符为-，从数值栈取两个元素进行-运算*/
Od）-x;
/*若取得的字符为*，从数值栈取两个元素进行*运算*/
Od）*Odpop（&
/*若取得的字符为/，从数值栈取两个元素进行/运算*/
Od）/x;
/*若取得的字符为%，从数值栈取两个元素进行%运算*/
x=（double）（（int）Odpop（&
Od）%（int）x）;
Odpush（&
Od,x）;
/*将计算结果x入栈*/
x=0;
/*x归零*/
/*继续进行*/
d=1.0;
}/*d归零*/
returnOdpop（&
}/*返回数值栈顶元素，即结果值*/
voidmain（）{/*主函数*/
charE[100];
/*声明一个长度为100的数组E*/
charA[100];
/*声明一个长度为100的数组A*/
printf（"
Pleaseinputtheinfixexpresswitha'
inttheend:
"
/*输出提示信息*/
gets（E）;
/*获取E数组中的表达式*/
change（E,A）;
/*调用中缀式转后缀式函数*/
Thesurffixexpressis:
%s\n"
A）;
/*输出后缀式*/
Theresultis:
%f\n"
Calc（A））;
/*调用计算后缀式的函数，并将结果输出*/
getchar（）;
下面给出的是用中缀表达式直接进行入栈计算算法实现的程序的源代码：
string.h>
stdlib.h>
typedefstruct{/*声明操作符结构体*/
charop;
/*声明操作符类型*/
charlevel;
/*声明操作符优先级*/
}opNode;
typedefunion{
opNodeopNode;
/*声明操作符*/
doublevalue;
/*声明value数值为double型*/
}Node;
typedefstruct{/*声明栈的结构体*/
charleixing;
/*声明一个字符型sort*/
Node*a[100];
/*指定数组大小为100*/
/*声明栈顶*/
}Stack;
Stack*init_sta（）{/*初始化栈*/
inti;
Stack*s=（Stack*）malloc（sizeof（Stack））;
/*分配一个类型为Stack的
结点变量的空间，空间大小为sizeof（Stack）,并将首地址放入指针变量s中*/
s->
top=0;
for（i=0;
i<
100;
i++）/*遍历栈，全为空则栈空*/
a[i]=NULL;
returns;
char*substr（char*s,intn1,intn2）{/*截取子串函数*/
char*ss=（char*）malloc（sizeof（char）*（n2-n1+2））;
/*分配空间，大小为
n2-n1+2，并将首地址放入指针变量ss中*/
inti,j=0;
for（i=n1;
n2;
i++）{/*将从字符串截取的子串赋值给ss*/
ss[j++]=s[i];
ss[j]='
/*字符串后面加上'
returnss;
intempty（Stack*ss）{/*判断栈空函数*/
returnss->
top;
}/*返回栈顶元素*/
Node*Top（Stack*ss）{/*观察栈顶函数*/
if（ss->
=0）{/*若栈顶为空，则返回0*/
else{/*若栈顶不为空，则返回栈顶元素*/
a[ss->
top-1];
Node*Pop（Stack*ss）{/*出栈函数*/
=0）{/*栈顶为空，返回0*/
else{/*否则，栈顶元素出栈*/
ss->
top--;
voidPush（Stack*p,Node*n）{/*进栈函数*/
Node*temp=（Node*）malloc（sizeof（Node））;
/*分配空间，空间大小为
sizeof（Node）,并将首地址放入指针变量temp中*/
if（p->
top>
=100）{/*判断栈是否已满*/
Error!
TheStackisfull!
\n"
free（temp）;
leixing==1）{/*sort为1，指向的为操作符栈，表明temp为操作符*/
temp->
opNode.level=n->
opNode.level;
opNode.op=n->
opNode.op;
else/*sort为2指向的是数值栈，表明temp为数值*/
value=n->
value;
p->
a[p->
top]=temp;
top=p->
doublecalc（charop,doublem,doublen）{/*每出栈一个操作符，就进行一次运算*/
switch（op）{
returnn+m;
returnn-m;
returnn*m;
returnn/m;
return（int）n%（int）m;
}/*计算结束后，返回计算结果*/
voidmath（char*exp）{/*处理函数*/
Node*top;
Node*temp=（Node*）malloc（sizeof（Node））;
/*分配空间，并将首地址放入指针变量temp中*/
Node*tempn=（Node*）malloc（sizeof（Node））;
/*分配空间，并将首地址放入指针变量tempn中*/
Node*tempm;
/*声明一个tempm结点指针*/
charc;
char*temps="
unsignedintindex=0,tempindex;
/*声明一个索引和一个临时索引*/
doublea,b;
Stack*s1=init_sta（）;
/*初始化栈s1*/
Stack*s2=init_sta（）;
/*初始化栈s2*/
s1->
leixing=2;
/*s1的类型为2，栈为数值栈*/
s2->
leixing=1;
/*s2的类型为1，栈为操作符栈*/
while（index<
strlen（exp））{/*循环条件为临时索引小于字符串的长度*/
c=exp[index];
if（c>
c<
||c=='
）{/*读取表达式中的各个数值*/
tempindex=index+1;
while（tempindex<
strlen（exp）&
（exp[tempindex]>
exp[tempindex]<
||exp[tempindex]=='
））{
tempindex++;
}/*当一个数没有读完，索引后移，直至整个数读完*/
if（tempindex==strlen（exp）-1）{/*当临时索引到达表达式尾部时，直接截取*/
temps=substr（exp,index,index+1）;
temps=substr（exp,index,tempindex）;
index=tempindex;
/*索引指向临时索引所在位置*/
value=atof（temps）;
/*将截取的子串转化为double类型*/
Push（s1,temp）;
}/*将转化后的数压入数值栈*/
if（c=='
）{/*字符为+或-时*/
tempn->
opNode.op=c;
opNode.level=1;
/*设置优先级为1*/
top=Top（s2）;
while（empty（s2）>
0&
tempn->
opNode.level<
=top->
opNode.level）{/*操作符栈不为空，
并且栈顶操作符优先级高于或者等于当前操作符*/
tempm=Pop（s2）;
/*操作符栈顶操作符出栈*/
a=Pop（s1）->
/*数值栈顶出来两个数*/
b=Pop（s1）->
value=calc（tempm->
opNode.op,a,b）;
/*两个数进行运算*/
/*运算结果压入数值栈*/
Push（s2,tempn）;
index++;
）{/*字符为*或/或%时*/
/*临时操作符指向c*/
opNode.level=2;
升级会员 