xx大学 xxx学院
算法与数据结构试验报告
设计名称： 算法与数据结构 设计题目： 链表的应用 学生学号： xx 专业班级： xx 学生姓名： xx 学生成绩： 指导教师（职称）：
课题工作时间： 2012年4月10日
说明：
实验课程类别：课程内实验 实验课程性质：必修
适用专业、年级：2010级计算机工程、计算机网络 开课院、系：计算机科学与工程学院计算机工程教研室 学时：18
编写依据：《算法与数据结构》实验教学大纲 修订时间：2012年2月
《算法与数据结构》课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。
上机的工作环境要求：Windows 2000或以上操作系统、VC++ 6.0或者其它高级程序设计语言。
学生应按指导教师的要求完成实验，并按要求撰写实验报告。
每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。报告内容至少包含如下内容：
1、 学生基本情况：专业班级、学号、姓名 2、 实验题目、实验内容 3、 设计分析 4、 源程序代码
5、 测试用例（尽量覆盖所有分支） 6、 实验总结
一．实验内容与学时分配 序次 一 二 三 实验 题目 线性结构综合应用 非线性结构综合应用 查找技术综合应用 实验 类型 综合性 综合性 综合性 基本技能训练 （1）掌握线性结构的常用操作； （2）能够应用线性结构解决比较简单的问题。 学时 10 （1）掌握树形、图形结构的插入、删除、查找等算法； 4 （2）能够应用二叉树解决比较简单的问题。 （1）熟练掌握查找的常用算法； （2）熟练设计和应用查找算法解决简单的实际问题。 （1）熟练掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； （2）深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用； （3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 2 四 排序技术综合应用 综合性 2 一、试验课题
链表的应用
二、试验内容
一元多项式求和。把任意给定的两个一元多项式P(x) ,Q(x) 输入计算机，计算它们的和并输出计算结果。
三、试验分析
系数 指数
x z next 一元多项式链表的结点结构
四、源程序代码
#include #include /*链表数据类型定义*/ typedef struct LNode {int x,z;
struct LNode *next; }LinkList;
void OutLinkList(LinkList *L); /*输出函数*/
void PutLinkList(LinkList *&L,int n); /*输入函数*/
LinkList *AddLinkList(LinkList *a,LinkList *b); /*求和函数*/ void OutXLinkList(LinkList *L); void OutZLinkList(LinkList *L); void main() {
int n,m;
LinkList *a,*b,*c;
printf(\"\\\本程序可以完成两个一元多项式的加法运算。\\n\"); printf(\"请输入一元多项式a的项数m：\"); scanf(\"%d\
printf(\"请按照从低次到高次的顺序依此输入一元多项式a的系数和指数：\\n\");
PutLinkList(a,m); printf(\"a=\"); OutLinkList(a);
printf(\"请输入一元多项式b的项数n：\"); scanf(\"%d\
printf(\"请按照从低次到高次的顺序依此输入一元多项式b的系数和指数：\\n\");
PutLinkList(b,n); printf(\"b=\"); OutLinkList(b); c=AddLinkList(a,b);
printf(\"两个多项式的和为：\\na+b=\"); OutLinkList(c); }
void PutLinkList(LinkList *&L,int n) {
LinkList *s,*r;
L=(LinkList *)malloc(sizeof(LinkList)); r=L;
for(int i=0;is=(LinkList *)malloc(sizeof(LinkList)); printf(\"请输入第%d项的系数：\ scanf(\"%d\printf(\"请输入第%d项的指数：\ scanf(\"%d\ r->next=s; r=s; }
r->next=NULL; }
/*多项式输出函数*/
void OutLinkList(LinkList *L)
{
char FuHao;
LinkList *p=L->next; FuHao=p->x>0? '+':'-'; if(FuHao=='-') {
printf(\"%c\ if(p->x==-1) printf(\"1\"); }
OutXLinkList(p); OutZLinkList(p); p=p->next; while(p!=NULL) {
FuHao=p->x>0? '+':'-'; printf(\"%c\ OutXLinkList(p); OutZLinkList(p); p=p->next; }
printf(\"\\n\"); }
/*输出系数函数*/
void OutXLinkList(LinkList *L) {
int xi=L->x>0? L->x:-L->x; if(L->x==1||L->x==-1) ; else
printf(\"%d\}
/*输出指数函数*/
void OutZLinkList(LinkList *L) {
if(L->z==0) ;
else if(L->z==1||L->z==-1) {
if(L->z<0) {
if(L->x==1||L->x==-1)
printf(\"1\"); printf(\"/\"); }
printf(\"X\"); } else {
if(L->z<0)
printf(\"/\");
int zhi=L->z>0? L->z:-L->z; printf(\"X^%d\ } }
LinkList *AddLinkList(LinkList *a,LinkList *b) {
a=a->next; b=b->next;
LinkList *c,*d,*s;
c=(LinkList *)malloc(sizeof(LinkList)); d=c;
while(a!=NULL&&b!=NULL) {
if(a->zz) {s=(LinkList *)malloc(sizeof(LinkList)); s->x=b->x; s->z=b->z; d->next=s; d=s;
b=b->next; }
else if(a->z>b->z) {
s=(LinkList *)malloc(sizeof(LinkList)); s->x=a->x; s->z=a->z; d->next=s; d=s;
a=a->next; }
else {
s=(LinkList *)malloc(sizeof(LinkList)); s->x=a->x+b->x; s->z=a->z; if(s->x==0) ; else {
d->next=s; d=s; }
a=a->next; b=b->next; } }
if(a!=NULL) d->next=a; else if(b!=NULL) d->next=b; else
d->next=NULL; return c; }
五、测试用例
1.当a=3x^8-x^5+2x^3+7x^2+5x,b=5x^5+3x^4-7x^2-3x^(-3)时，运行结果如下：
2.当a=3x^8-2x^5+7x^2+5x,b=2x^5+3x^4-12x^2时，运行结果如下：
3. 当a=3x^4-2x^5+7x^2+5x,b=2x^5+3x^4-12x^2时，运行结果如下：
几次测试都表明试验设计的正确性。
六、试验总结
通过本次试验，学会了链表的应用，加深了对链表的理解，知道了链表是把线性表中的元素按照链式储存方式到计算机中的一片连续的储存空间中。储存时用到了动态内存申请的知识。本次试验让我更好的把书本上的知识运用到具体的例子中来，学会了通过vc6.0来建立链表，链表的基本运算输出顺序表等等。同时也了解到了多项式求和问题可以通过链表的知识来解决，也体会其中算法的奥妙。