安徽工业大学《数据结构》课程设计.docx
《安徽工业大学《数据结构》课程设计.docx》由会员分享，可在线阅读，更多相关《安徽工业大学《数据结构》课程设计.docx（19页珍藏版）》请在冰点文库上搜索。
安徽工业大学《数据结构》课程设计
《数据结构》
课程设计报告
学号
XXX
姓名
XXX
班级
计11X
指导教师
储岳中
安徽工业大学计算机学院
2013年6月
一：
一元多项式计算
1.问题：
建立并输出多项式，并完成一元多项式的加法计算。
2.代码清单及调试结果如下：
#include
#include
#include
typedefstructpolynode
{
intcoef，exp;
structpolynode*next;
}node;
node*create（）
{
node*h,*r,*s;
intc,e;
h=（node*）malloc（sizeof（node））;
r=h;
printf（"coef:
"）;
scanf（"%d",&c）;
printf（"exp:
"）;
scanf（"%d",&e）;
while（c!
=0）
{
s=（node*）malloc（sizeof（node））;
s->coef=c;s->exp=e;r->next=s;
r=s;
printf（"coef:
"）;
scanf（"%d",&c）;
printf（"exp:
"）;
scanf（"%d",&e）;
}
r->next=NULL;
return（h）;
}
voidoutput（node*p）
{
while（p->next!
=NULL）
{
p=p->next;
printf（"%d*x^%d+",p->coef,p->exp）;
}
printf（"0"）;
}
node*polyadd（node*ha,node*hb）
{
node*p,*q,*pre,*temp;
intsum;
p=ha->next;
q=hb->next;
pre=ha;
while（p!
=NULL&&q!
=NULL）
{
if（p->expexp）
{
pre->next=p;
pre=pre->next;
p=p->next;
}
elseif（p->exp==q->exp）
{
sum=p->coef+q->coef;
if（sum!
=0）
{
p->coef=sum;pre->next=p;pre=pre->next;p=p->next;temp=q;q=q->next;
free（temp）;
}
else
{
temp=p->next;free（p）;
p=temp;temp=q->next;free（q）;q=temp;
}
}
else
{
pre->next=q;pre=pre->next;q=q->next;
}
}
if（p!
=NULL）
pre->next=p;
elsepre->next=q;
}
main（）
{
node*ha,*hb,*f;
printf（"请输入多项式ha的系数与指数:
\n"）;
ha=create（）;
output（ha）;
printf（"\n"）;
printf（"请输入多项式hb的系数与指数:
\n"）;
hb=create（）;output（hb）;
printf（"\n"）;
printf（"多项式的和是:
\n"）;
polyadd（ha,hb）;output（ha）;
printf（"\n"）;
}
二：
矩阵的运算
1.问题：
采用十字链表表示稀疏矩阵，并实现矩阵的加法运算,要求：
要检查有关运算的条件，并对错误的条件产生报警。
2.设计思路：
本程序需要实现两稀疏矩阵的相加，如果用一般的数组存储矩阵，然后进行相加会很简单，但是当用十字链表表示稀疏矩阵并进行相加时，这时无疑就增加了难度。
本程序通过手动输入两个任意大小的矩阵（两矩阵的大小需要一样）并输入相应位置的数值，当输入的两个矩阵的行数和列数不一样时，给出提醒输入错误。
当两矩阵一样时，分别通过调用十字链表函数，建立十字链表分别存储两矩阵中数值的相关信息。
在进行矩阵相加时，先比较两矩阵在相应的同一行或列是否同时有数值。
要是都有数值时，再进行比较此行或列中的同一位置是否有数，有数则进行计算并将结果插入矩阵C的十字链表中，无数时则分别插入矩阵C的十字链表的相应位置。
要是两矩阵在同一行或列不是同时有值，则将相应有数值的行或列直接插入C矩阵。
3.代码清单及调试结果如下：
#include
#include
#defineMAX100
typedefintdatatype;
typedefstructnode
{
inti,j;
structnode*down,*right;
union{
structnode*next;
datatypev;
}jz;
}crosslist;
intflag=0;
crosslist*creatlinkmat（）
{
crosslist*p,*q,*head,*cp[MAX];
inti,j,k,m,n,t,s;
datatypev;
printf（"输入行,列,非零元素个数:
\n"）;
scanf（"%d%d%d",&m,&n,&t）;
s=m>n?
m:
n;
p=（crosslist*）malloc（sizeof（crosslist））;
p->i=m;p->j=n;
head=p;
cp[0]=p;
for（i=1;i<=s;i++）
{
p=（crosslist*）malloc（sizeof（crosslist））;
p->i=0;p->j=0;cp[i]=p;
p->right=p;p->down=p;
cp[i-1]->jz.next=p;
}
cp[s]->jz.next=head;
for（k=1;k<=t;k++）
{
printf（"请输入一个非零元素的三元组:
\n"）;
scanf（"%d%d%d",&i,&j,&v）;
p=（crosslist*）malloc（sizeof（crosslist））;
p->i=i;p->j=j;
p->jz.v=v;q=cp[i];
while（（q->right!
=cp[i]）&&（q->right->jq=q->right;p->right=q->right;q->right=p;
q=cp[j];
while（（q->down!
=cp[j]）&&（q->down->iq=q->down;p->down=q->down;q->down=p;
}
return（head）;
}
voidinsert（inti,intj,intv,crosslist*cp[]）
{
crosslist*p,*q;
p=（crosslist*）malloc（sizeof（crosslist））;
p->i=i;p->j=j;p->jz.v=v;
q=cp[i];
while（（q->right!
=cp[i]）&&（q->right->jq=q->right;p->right=q->right;q->right=p;
q=cp[j];
while（（q->down!
=cp[j]）&&（q->down->iq=q->down;p->down=q->down;q->down=p;
}
voidprint（crosslist*a）
{
crosslist*p,*q,*r;
intk,col,t,row;
col=a->j;
printf（"矩阵为：
\n"）;
p=a->jz.next;
while（p!
=a）
{
q=p->right;
if（q==a->down）break;
r=p;
while（q!
=p）
{
for（k=1;kj-（r->j）;k++）
printf（"0"）;
printf（"%3d",q->jz.v）;
q=q->right;r=r->right;
}
k=r->j;
for（t=k;tprintf（"0"）;
printf（"\n"）;
p=p->jz.next;
}
}
crosslist*add（crosslist*a,crosslist*b）
{
crosslist*p,*q,*u,*v,*r,*cp[MAX],*c;
ints,i;
if（a->i!
=b->i||a->j!
=b->j）
{
flag=1;returnNULL;
}
c=（crosslist*）malloc（sizeof（crosslist））;
c->i=a->i;c->j=a->j;
if（c->i>c->j）s=c->i;
elses=c->j;
cp[0]=c;
for（i=1;i<=s;i++）
{
r=（crosslist*）malloc（sizeof（crosslist））;
r->i=0;r->right=r;r->down=r;
cp[i]=r;
cp[i-1]->jz.next=r;
}
cp[s]->jz.next=c;
p=a->jz.next;u=b->jz.next;
while（p!
=a&&u!
=b）
{
q=p->right;v=u->right;
if（q==p&&v!
=u）
while（v!
=u）
{
insert（v->i,v->j,v->jz.v,cp）;v=v->right;
}
elseif（v==u&&q!
=p）
while（q!
=p）
{insert（q->i,q->j,q->jz.v,cp）;q=q->right;}
elseif（q!
=p&&v!
=u）
{
while（q!
=p&&v!
=u）
{
if（q->jj）
{
insert（q->i,q->j,q->jz.v,cp）;q=q->right;
}
elseif（q->j>v->j）
{
insert（v->i,v->j,v->jz.v,cp）;v=v->right;
}
Else
{
if（q->jz.v+v->jz.v!
=0）insert（q->i,q->j,（q->jz.v+v->jz.v）,cp）;
q=q->right;v=v->right;
}
}
if（q==p&&v!
=u）
while（v!
=u）
{insert（v->i,v->j,v->jz.v,cp）;v=v->right;}
elseif（v==u&&q!
=p）
while（q!
=p）
{insert（q->i,q->j,q->jz.v,cp）;q=q->right;}
else;
}
else;
p=p->jz.next;u=u->jz.next;
}
returnc;}
main（）
{
crosslist*a,*b,*c;
printf（"矩阵a的内容如下:
\n"）;
a=creatlinkmat（）;print（a）;
printf（"矩阵b的内容如下:
\n"）;
b=creatlinkmat（）;print（b）;
printf（"矩阵a+b的和矩阵c内容如下:
\n"）;
c=add（a,b）;
if（flag==1）printf（"矩阵a、b不是同一类型矩阵不能相加!
!
!
\n"）;
elseprint（c）;
}
三．学生成绩查询系统
1.问题：
试编写程序完成学生成绩记录的查询。
①若按学号进行顺序查找，例如：
输入99070103，则输出56。
②按学号排序后对学号进行折半查找。
③随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。
2.设计思路：
该系统主要有三个选择；第一个就是用顺序表来存储，对学号进行顺序查找，找到你所找的学号就输出该学生的信息；第二个就是对学号进行排序后进行折半查找；第三个就是随机输入以学号为关键字的信息，同时建立二叉排序树，最后对该树进行二叉排序树查找。
3.代码清单及调试结果如下：
#include
#include
#include
typedefstruct
{
charsn[10]，name[20];
intscore;
}student;
typedefstructBinSTreeNode
{
charxuehao[10]，xinming[20];
intchengji;
structBinSTreeNode*lchild,*rchild;
}*BTree;
intshunxu_search（studentstu[],intn,charx[]）
{
inti,j;
for（i=0;iif（strcmp（stu[i].sn,x）==0）
{
printf（"所查找的学生信息如下：
\n学号\t姓名\t成绩\n"）;
printf（"%s%s%d",stu[i].sn,stu[i].name,stu[i].score）;
printf（"\n"）;
return0;
}
}
intzheban_search（studentstu[],intn,charx[]）
{
intlow,mid,high;
low=0;high=n-1;
while（low<=high）
{
mid=（low+high）/2;
if（strcmp（stu[mid].sn,x）==0）
{
printf（"所查找的学生信息如下：
\n学号\t姓名\t成绩\n"）;
printf（"%s%s%d",stu[mid].sn,stu[mid].name,stu[mid].score）;
printf（"\n"）;
return0;
}
elseif（strcmp（stu[mid].sn,x）>0）high=mid-1;
elselow=mid+1;
}
return0;
}
voidBSTree（BTree*t,studentk）
{
BTreer;
if（*t==NULL）
{
r=（BTree）malloc（sizeof（structBinSTreeNode））;
strcpy（r->xuehao,k.sn）;
strcpy（r->xinming,k.name）;
r->chengji=k.score;r->lchild=r->rchild=NULL;*t=r;
return;
}
else
if（strcmp（k.sn,（（*t）->xuehao））<=0）
BSTree（&（（*t）->lchild）,k）;
else
BSTree（&（（*t）->rchild）,k）;
}
BTreeBSTreeSearch（BTreet,charx[]）
{
if（t==NULL）returnNULL;
if（strcmp（t->xuehao,x）==0）returnt;
if（strcmp（t->xuehao,x）>=0）
returnBSTreeSearch（t->lchild,x）;
else
returnBSTreeSearch（t->rchild,x）;
}
main（）
{
studentstu[40];
inti,j,k,n,b;
charx[30];
printf（"学生成绩查询系统:
\n"）;
printf（"请输入总的学生数：
"）;
scanf（"%d",&n）;
printf（"\n请输入这些学生的信息：
\n"）;
printf（"学号姓名成绩\n"）;
for（i=0;i{
printf（"学生%d",i+1）;
scanf（"%s%s%d",&stu[i].sn,&stu[i].name,&stu[i].score）;
}
printf（"学生信息已经全部输入!
\n"）;
printf（"请输入你想查找的学生学号：
"）;
scanf（"%s",&x）;
printf（"\n顺序查找结果:
\n"）;
shunxu_search（stu,n,x）;
printf（"\n折半查找结果:
\n"）;
zheban_search（stu,n,x）;
printf（"\n\n二叉树时排序的查找"）;
printf（"\n输入构成二叉树的学号的个数：
"）;
scanf（"%d",&b）;
BTreeT;
T=（BTree）malloc（sizeof（structBinSTreeNode））;
T=NULL;
for（i=0;i{
printf（"输入你的第%i学号：
",i+1）;
scanf（"%s",&x）;
for（j=0;jif（strcmp（stu[j].sn,x）==0）
k=j;
BSTree（&T,stu[k]）;
}
printf（"学生信息输入完成!
\n"）;
printf（"二叉排序树已经构建！
\n"）;
printf（"\n输入此时你想查询的学生的学号：
"）;
scanf（"%s",&x）;
BTrees;
s=（BTree）malloc（sizeof（structBinSTreeNode））;
s=BSTreeSearch（T,x）;
printf（"所查找的学生信息如下：
\n学号\t姓名\t成绩\n"）;
printf（"%s%s%d\n",s->xuehao,s->xinming,s->chengji）;
}
四：
实验总结
通过对程序的设计，让我对于数据结构有了全新的认识，同时也让我对于数据结构有了更浓厚的兴趣，跟让我认识到自己在C语言方面的严重不足，基本语法容易用错，对于一些常见的结构认识模糊，容易混淆，有很大一部分的程序都是通过借鉴和参照书上的代码及释义来理解和编写的，所以经过这次的实验让我认识的了自身，同时也为自己以后更好的学习C语言只是提供了良好的借鉴和经验。
升级会员 