大连理工大学数据结构(一)上机作业答案张老师文档格式.doc
《大连理工大学数据结构(一)上机作业答案张老师文档格式.doc》由会员分享，可在线阅读，更多相关《大连理工大学数据结构(一)上机作业答案张老师文档格式.doc（12页珍藏版）》请在冰点文库上搜索。
L.elem[i]）;
}
//输出顺序表中的元素
voidListOutput_Sq（SqListL）{
inti,n;
n=L.length;
%2d"
L.elem[i]）;
//顺序表逆置
voidReverseList_Sq（SqList&
ElemTypep;
n/2;
{
p=L.elem[i];
L.elem[i]=L.elem[n-i-1];
L.elem[n-i-1]=p;
voidmain（）{
SqListL;
InitList_Sq（L）;
ListInput_Sq（L）;
ListOutput_Sq（L）;
ReverseList_Sq（L）;
printf（"
\n"
输出结果为：
2．从键盘读入n个整数（升序），请编写算法实现：
（1）CreateList（）：
建立带表头结点的单链表；
（2）PrintList（）：
显示单链表，（形如：
H->
10->
20->
30->
40）;
（3）InsertList（）：
在有序单链表中插入元素x；
（4）ReverseList（）：
单链表就地逆置；
（5）DelList（）：
在有序单链表中删除所有值大于mink且小于maxk的元素。
选作：
使用文本菜单完成功能选择及执行。
参考答案：
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
voidCreateList（LinkList&
L,intn）{
inti;
LNode*p,*q;
L=（LinkList）malloc（sizeof（LNode））;
L->
next=NULL;
q=L;
请输入所要建立的单链表所包含的元素：
i++）{
p=（LinkList）malloc（sizeof（LNode））;
scanf（"
p->
data）;
p->
q->
next=p;
q=p;
voidPrintList（LinkListL）{
LNode*p;
p=L->
next;
while（p）{
p->
p=p->
voidInsertList（LinkListL,ElemTypem）{
LNode*p,*q,*s;
p=L;
q=L->
while（q&
&
q->
data<
m）{
p=q;
q=q->
if（q）{
s=（LinkList）malloc（sizeof（LNode））;
s->
data=m;
next=q;
next=s;
else{
voidReverseList（LinkList&
if（L->
next&
L->
next->
next）{
p=L->
q=p->
while（q）{
p=q;
q=q->
p->
next=L->
L->
}
voidDeleteList（LinkList&
L,ElemTypemink,ElemTypemaxk）{
LNode*p=L,*q;
while（p->
=mink）
q=p;
maxk）
p->
LinkListL;
intn,number;
ElemTypee,mink,maxk;
do{
*********************************\n"
建立单链表请按1.\n"
显示单链表请按2.\n"
有序插入新元素请按3.\n"
单链表就地逆置请按4.\n"
删除大于mink且小于maxk的所有元素请按5.\n"
退出请按0.\n"
\n请选择操作：
number）;
switch（number）{
case1:
printf（"
请输入单链表中的节点个数：
scanf（"
CreateList（L,n）;
break;
case2:
要执行本操作请先建立单链表，请输入单链表中的节点个数：
printf（"
单链表为：
PrintList（L）;
case3:
请输入有序表中插入的值：
scanf（"
e）;
InsertList（L,e）;
PrintList（L）;
case4:
printf（"
单链表逆置：
ReverseList（L）;
case5:
请输入mink和maxk：
%d%d"
mink,&
maxk）;
DeleteList（L,mink,maxk）;
}while（number!
=0）;
第二次作业
栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。
例如，输入表达式：
a+b/c-（d*e+f）*g
输出其后缀表达式：
abc/+de*f+g*-
string.h>
math.h>
#defineOVER-2
#defineture1
#definefalse0
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefcharSElemType;
typedefcharElemType;
typedefstruct{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
//定义结构
intInitStack（SqStack&
S）{
S.base=（ElemType*）malloc（STACK_INIT_SIZE*sizeof（ElemType））;
if（!
S.base）exit（OVER）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}//建栈
intPush（SqStack&
S,SElemTypee）{
if（S.top-S.base>
=S.stacksize）
{S.base=（ElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（ElemType））;
if（!
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
*S.top++=e;
}//插入
intGetTop（SqStack&
S,SElemType&
e）{
if（S.top==S.base）returnERROR;
e=*（S.top-1）;
}//获取栈顶元素
intPop（SqStack&
if（S.top==S.base）returnERROR;
e=*--S.top;
returnOK;
}//删除栈顶并用e返回值
intStackEmpty（SqStackS）{
if（S.top==S.base）
returnture;
else
returnfalse;
intPass（charsuffix[],SElemTypech）
{
char*p;
p=suffix;
while（*p!
='
\0'
）
p++;
*p=ch;
*（p+1）='
;
return0;
}//把操作数ch传进数组suffix
voidadd（charexp[]）
{
char*p;
p=exp;
while（*p!
='
）
++p;
*p='
#'
*（p+1）='
}//在表达式结尾加结束符
voiddel（charsuffix[]）
{
p=suffix;
p++;
}//将字符串结尾附成\0
intPrecede（charc）
{
if（c=='
*'
||c=='
/'
return2;
if（c=='
+'
-'
return1;
（'
）'
return-1;
else
return-2;
}//优先级比较
voidtransform（charsuffix[],charexp[]）
char*p,ch,c;
p=exp;
ch=*p;
SqStackS;
InitStack（S）;
Push（S,'
while（!
StackEmpty（S））
if（ch>
a'
ch<
z'
{
Pass（suffix,ch）;
else
switch（ch）
{
case'
:
Push（S,ch）;
break;
Pop（S,c）;
while（c!
{
Pass（suffix,c）;
Pop（S,c）;
}
default:
if（ch=='
while（!
{
Pop（S,c）;
Pass（suffix,c）;
}
else
GetTop（S,c）;
while（Precede（c）>
=Precede（ch））
GetTop（S,c）;
Push（S,ch）;
}
if（ch!
ch=*++p;
}//后缀表达式转化
intmain（）
charsuffix[100];
suffix[0]='
charexp[100];
printf（"
请输入一个表达式：
gets（exp）;
add（exp）;
transform（suffix,exp）;
del（suffix）;
后缀表达式为：
%s\n"
suffix）;
第三次作业
二叉树采用二叉链表存储，试设计算法实现：
1．CreateBT（BiTree&
T）：
从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；
如输入：
AB#D##CE#F###则建立如下图所示二叉树的二叉链表
2．ExchangeBT（BiTreeT）:
设计递归算法实现二叉树中所有结点的左右孩子交换；
3．CountLeaf（BiTreeT,TElemTypex,int&
count）:
统计以值为x的结点为根的子树中叶子结点的数目；
4．DispBiTree（BiTreeT,intlevel）:
按树状打印二叉树。
B
C
F
A
E
D
打印得到：
#C
###F
##E
##D
#B
提示：
对于根为T，层次为level的子树：
①打印其下一层（level+1层）右子树；
②打印根结点；
③打印其下一层（level+1层）左子树；
*结点左边的’#’个数为其层次数*
typedefstructBiTNode{
chardata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
//输入先序序列，创建二叉树的二叉链表
voidCreateBT（BiTree&
T）{
charch;
%c"
ch）;
if（ch=='
T=NULL;
T=（BiTNode*）malloc（sizeof（BiTNode））;
T->
data=ch;
CreateBT（T->
lchild）;
rchild）;
//交换二叉树中结点的左右孩子
voidExchangeBT（BiTree&
BiTreetemp;
if（T）{
temp=T->
lchild;
lchild=T->
rchild;
lchild=temp;
ExchangeBT（T->
//查找值为x的结点
BiTreeSearchTree（BiTreeT,charx）{
BiTreeNTree;
if（T->
data==x）
returnT;
NTree=SearchTree（T->
lchild,x）;
if（NTree==NULL）
NTree=SearchTree（T->
rchild,x）;
returnNTree;
returnNULL;
//统计一x为根的子树中叶子结点的个数
voidLeafCount（BiTreeT,int&
count）{
if（（T->
lchild==NULL）&
（T->
rchild==NULL））
count++;
LeafCount（T->
lchild,count）;
rchild,count）;
//按树状打印输出二叉树的元素，level表示结点的层次
voidPrintBiTree（BiTreeT,intlevel）{
PrintBiTree（T->
lchild,level+1）;
for（i=0;
level;
#"
%c\n"
T->
rchild,level+1）;
BiTreeT,SecT;
charSecch;
intcount=0;
输入先序序列建立二叉树：
CreateBT（T）;
二叉树为：
PrintBiTree（T,0）;
交换结点的左右孩子\n"
ExchangeBT（T）;
\n此时二叉树为：
输入要统计叶子结点个数的子树的根：
fflush（stdin）;
//清理缓存
Secch）;
SecT=SearchTree（T,Secch）;
LeafCount（SecT,count）;
叶子结点数为：
%d\n"
count）;
升级会员 