数据结构课程设计参考答案a组课案.docx
《数据结构课程设计参考答案a组课案.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计参考答案a组课案.docx（62页珍藏版）》请在冰点文库上搜索。
数据结构课程设计参考答案a组课案
/*
二叉树的层次遍历
*/
#include
#include
#include
#include
#defineTREEMAX50
typedefstructnode
{
chardata;
structnode*lchild;
structnode*rchild;
}Node;
//递归创建二叉树
Node*CreateBT（）
{
Node*t;
charx;
scanf（"%c",&x）;
fflush（stdin）;
if（x=='#'）
t=NULL;
else
{
t=newNode;
t->data=x;
printf（"\t\t请输入%c结点的左子结点:
",t->data）;
t->lchild=CreateBT（）;
printf（"\t\t请输入%c结点的右子结点:
",t->data）;
t->rchild=CreateBT（）;
}
returnt;
}
//递归先序遍历二叉树
voidPreorder（Node*T）
{
if（T）
{
printf（"%3c",T->data）;
Preorder（T->lchild）;
Preorder（T->rchild）;
}
}
//递归中序遍历二叉树
voidInorder（Node*T）
{
if（T）
{
Inorder（T->lchild）;
printf（"%3c",T->data）;
Inorder（T->rchild）;
}
}
//递归后序遍历二叉树
voidPostorder（Node*T）
{
if（T）
{
Postorder（T->lchild）;
Postorder（T->rchild）;
printf（"%3c",T->data）;
}
}
//非递归先序遍历二叉树
voidnoRecursivePreorder（Node*T）
{
Node*St[TREEMAX],*p;
inttop=-1;
if（T!
=NULL）
{
top++;
St[top]=T;
while（top>-1）
{
p=St[top];
top--;
printf（"%c",p->data）;
if（p->rchild!
=NULL）
{
top++;
St[top]=p->rchild;
}
if（p->lchild!
=NULL）
{
top++;
St[top]=p->lchild;
}
}
printf（"\n"）;
}
}
//非递归中序遍历二叉树
voidnoRecursiveInorder（Node*T）
{
Node*St[TREEMAX],*p;
inttop=-1;
if（T!
=NULL）
{
p=T;
while（top>-1||p!
=NULL）
{
while（p!
=NULL）
{
top++;
St[top]=p;
p=p->lchild;
}
if（top>-1）
{
p=St[top];
top--;
printf（"%c",p->data）;
p=p->rchild;
}
}
printf（"\n"）;
}
}
//非递归后序遍历二叉树
voidnoRecursivePostorder（Node*T）
{
Node*St[TREEMAX],*p;
intflag,top=-1;
if（T!
=NULL）
{
do
{
while（T!
=NULL）
{
top++;
St[top]=T;
T=T->lchild;
}
p=NULL;
flag=1;
while（top!
=-1&&flag）
{
T=St[top];
if（T->rchild==p）
{
printf（"%c",T->data）;
top--;
p=T;
}
else
{
T=T->rchild;
flag=0;
}
}
}while（top!
=-1）;
printf（"\n"）;
}
}
//层次遍历二叉树，用queue数组充当顺序队列
voidLevelOrder（Node*T）
{
Node*queue[TREEMAX],*p;
intpre=-1,rear=-1;
//树根结点先进队
queue[++pre]=T;
//当队列不为空时，出队一个结点的同时将其左右孩子进队
while（（pre-rear+TREEMAX）%TREEMAX!
=0）
{
p=queue[++rear];//出队一个结点并输出
printf（"%3c",p->data）;
if（p->lchild!
=NULL）//左孩子存在则进队
queue[++pre]=p->lchild;
if（p->rchild!
=NULL）//右孩子存在则进队
queue[++pre]=p->rchild;
}
}
voidlist（）
{
printf（"\n"）;
printf（"\n\t\t二叉链表"）;
printf（"\n\t\t****************************************"）;
printf（"\n\t\t*1.建立二叉树*"）;
printf（"\n\t\t*2.递归前序遍历*"）;
printf（"\n\t\t*3.递归中序遍历*"）;
printf（"\n\t\t*4.递归后序遍历*"）;
printf（"\n\t\t*5.非递归前序遍历*"）;
printf（"\n\t\t*6.非递归中序遍历*"）;
printf（"\n\t\t*7.非递归后序遍历*"）;
printf（"\n\t\t*8.层次遍历*"）;
printf（"\n\t\t*9.清屏*"）;
printf（"\n\t\t*0.退出程序*"）;
printf（"\n\t\t****************************************"）;
printf（"\n\t\t请输入菜单项：
"）;
}
voidmain（）
{
Node*T=NULL;
chara,b;
b='m';
while（b=='m'||b=='M'）
{
list（）;
scanf（"%c",&a）;
fflush（stdin）;
switch（a）
{
case'1':
printf（"\n\t\t请按先序序列输入二叉树的结点（输入#表示结点为空）：
\n"）;
printf（"\n\t\t请输入根结点：
"）;
T=CreateBT（）;
printf（"\n\t\t二叉树成功建立^-^\n"）;
break;
case'2':
printf（"\n\t\t该二叉树递归前序遍历为：
"）;
Preorder（T）;
break;
case'3':
printf（"\n\t\t该二叉树递归中序遍历为：
"）;
Inorder（T）;
break;
case'4':
printf（"\n\t\t该二叉树递归后序遍历为：
"）;
Postorder（T）;
break;
case'5':
printf（"\n\t\t该二叉树非递归前序遍历为：
"）;
noRecursivePreorder（T）;
break;
case'6':
printf（"\n\t\t该二叉树非递归中序遍历为：
"）;
noRecursiveInorder（T）;
break;
case'7':
printf（"\n\t\t该二叉树非递归后序遍历为：
"）;
noRecursivePostorder（T）;
break;
case'8':
printf（"\n\t\t该二叉树的层次遍历序列为：
"）;
LevelOrder（T）;
break;
case'9':
system（"cls"）;
break;
case'0':
b='n';
break;
default:
printf（"\n\t\t***对不起，输入有误！
***"）;
}
}
}
/*
多项式运算【链式结构】
*/
#include"stdio.h"
#include"stdlib.h"
typedefstruct_node
{
floatcoe;
intindex;
struct_node*next;
}Node,*NodePtr;
//整理多项式链表，将链表中的结点根据各项指数进行升序排列
voidsortPoly（NodePtrlist）
{
NodePtrp=list->next,q=list,r,ptr;
//让p指向链表的第二个数据结点，
//p为空则说明链表为空，不用整理了。
if（p）
p=p->next;
else
return;
//先从链表的第一个数据结点后断开链表
ptr=q->next;
ptr->next=NULL;
//再将链表的第二个直至最后一个数据结点依次插入链表
while（p）
{
q=list;
ptr=q->next;
while（ptr->indexindex）
{
q=ptr;
ptr=ptr->next;
if（ptr==NULL）
break;
}
if（ptr==NULL）
{
q->next=p;
ptr=p;
p=p->next;
ptr->next=NULL;
}
elseif（ptr->index==p->index）
{
ptr->coe+=p->coe;
r=p->next;
free（p）;
p=r;
}
elseif（ptr->index>p->index）
{
r=p->next;
p->next=ptr;
q->next=p;
p=r;
}
}
}
/*创建一个多项式链表，返回创建链表的头指针*/
NodePtrcreatePoly（）
{
inti=1,index;
floatcoe;
NodePtrresultPtr,q;
//开辟头结点空间
resultPtr=（NodePtr）malloc（sizeof（Node））;
resultPtr->next=NULL;
printf（"请输入多项式第%d项的系数和指数（输入00时结束）：
",i++）;
scanf（"%f%d",&coe,&index）;
while
（1）
{
if（index&&coe==0）
printf（"系数不能为0！
\n"）;
elseif（index==0&&coe==0）
break;
else
{//开辟新结点空间
q=（NodePtr）malloc（sizeof（Node））;
q->coe=coe;
q->index=index;
q->next=NULL;
//将新结点插入多项式链表
q->next=resultPtr->next;
resultPtr->next=q;
//输入下一项
printf（"请输入多项式第%d项的系数和指数（输入00时结束）：
",i++）;
scanf（"%f%d",&coe,&index）;
}
}
//将输入的多项式链表整理后返回
sortPoly（resultPtr）;
returnresultPtr;
}
//判断多项式链表是否已输入或是否为空
intisEmpty（NodePtrlist1,NodePtrlist2）
{
if（list1==NULL）
return1;
elseif（list2==NULL）
return2;
elseif（list1->next==NULL）
return-1;
elseif（list2->next==NULL）
return-2;
else
return0;
}
//两个多项式相加
NodePtraddPoly（NodePtrlist1,NodePtrlist2）
{
NodePtrresultPtr,p=list1->next,q=list2->next,r;
if（isEmpty（list1,list2）==1）
{
printf（"多项式链表L1不存在，请先选择菜单1输入多项式L1！
\n"）;
returnNULL;
}
elseif（isEmpty（list1,list2）==2）
{
printf（"多项式链表L2不存在，请先选择菜单2输入多项式L2！
\n"）;
returnNULL;
}
//创建结果多项式的头结点
resultPtr=（NodePtr）malloc（sizeof（Node））;
resultPtr->next=NULL;
while（p!
=NULL&&q!
=NULL）
{
if（p->index>q->index）
{
//创建新结点
r=（NodePtr）malloc（sizeof（Node））;
r->coe=q->coe;
r->index=q->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
q=q->next;
}
elseif（p->indexindex）
{
r=（NodePtr）malloc（sizeof（Node））;
r->coe=p->coe;
r->index=p->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
p=p->next;
}
else
{
//对应项相加系数不为0
if（p->coe+q->coe!
=0）
{
//创建新结点
r=（NodePtr）malloc（sizeof（Node））;
r->coe=p->coe+q->coe;
r->index=p->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
}
p=p->next;
q=q->next;
}
}
//如果某个链表中尚有多余结点尚未插入结果链表，
//则将剩余结点依次插入结果链表
while（p!
=NULL）
{
r=（NodePtr）malloc（sizeof（Node））;
r->coe=p->coe;
r->index=p->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
p=p->next;
}
while（q!
=NULL）
{
r=（NodePtr）malloc（sizeof（Node））;
r->coe=q->coe;
r->index=q->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
q=q->next;
}
returnresultPtr;
}
//两个多项式相减
NodePtrsubPoly（NodePtrlist1,NodePtrlist2）
{
NodePtrresultPtr,p=list1->next,q=list2->next,r;
if（isEmpty（list1,list2）==1）
{
printf（"多项式链表L1不存在，请先选择菜单1输入多项式L1！
\n"）;
returnNULL;
}
elseif（isEmpty（list1,list2）==2）
{
printf（"多项式链表L2不存在，请先选择菜单2输入多项式L2！
\n"）;
returnNULL;
}
//创建结果多项式的头结点
resultPtr=（NodePtr）malloc（sizeof（Node））;
resultPtr->next=NULL;
while（p!
=NULL&&q!
=NULL）
{
if（p->index>q->index）
{
//创建新结点
r=（NodePtr）malloc（sizeof（Node））;
r->coe=-1*q->coe;
r->index=q->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
q=q->next;
}
elseif（p->indexindex）
{
r=（NodePtr）malloc（sizeof（Node））;
r->coe=p->coe;
r->index=p->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
p=p->next;
}
else
{
//对应项相减系数不为0
if（p->coe-q->coe!
=0）
{
//创建新结点
r=（NodePtr）malloc（sizeof（Node））;
r->coe=p->coe-q->coe;
r->index=p->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
}
p=p->next;
q=q->next;
}
}
//如果某个链表中尚有多余结点尚未插入结果链表，
//则将剩余结点依次插入结果链表
while（p!
=NULL）
{
r=（NodePtr）malloc（sizeof（Node））;
r->coe=p->coe;
r->index=p->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
p=p->next;
}
while（q!
=NULL）
{
r=（NodePtr）malloc（sizeof（Node））;
r->coe=-1*q->coe;
r->index=q->index;
r->next=NULL;
//将新结点插入结果链表
r->next=resultPtr->next;
resultPtr->next=r;
q=q->next;
}
returnresultPtr;
}
//两个多项式相乘
NodePtrmultiPoly（NodePtrlist1,NodePtrlist2）
{
NodePtrp,q,r,resultPtr;
if（isEmpty（list1,list2）==1）
{
printf（"多项式链表L1不存在，请先选择菜单1输入多项式L1！
\n"）;
returnNULL;
}
elseif（isEmpty（list1,list2）==2）
{
printf（"多项式链表L2不存在，请先选择菜单2输入多项式L2！
\n"）;
returnNULL;
}
elseif（isEmpty（list1,list2）==-1||isEmpty（list1,list2）==-2）
{
//给相乘的结果多项式链表开辟头结点
resultPtr=（NodePtr）malloc（sizeof（Node））;
resultPtr->next=NULL;
returnresultPtr;
}
//给相乘的结果多项式链表开辟头结点
resultPtr=（NodePtr）malloc（sizeof（Node））;
resultPtr->next=NULL;
p=list1->next;
q=list2->next;
while（p）
{
//只要p不为空，则将p指向的结点和另一链表的所有结点相乘，
//并将相乘的每个结点插入到结果链表resultP
升级会员 