链表实现多项式相加的实验报告

实 验 报 告

课程名称：数据结构题 目 ：链表实现多项式相加班 级 ：学 号 ：姓 名 ：完成时间：

2012年 月 日 1、 实验目的和要求

1）掌握链表的运用方法；

2）学习链表的初始化并建立一个新的链表； 3）知道如何实现链表的插入结点与删除结点操作； 4）了解链表的基本操作并灵活运用 2、实验内容

1）建立两个链表存储一元多项式； 2）实现两个一元多项式的相加；

3）输出两个多项式相加后得到的一元多项式。 3、算法基本思想

数降序存入两个链表中，将大小较大的链表作为相加后的链表寄存处。定义两个临时链表节点指针p,q,分别指向两个链表头结点。然后将另一个链表中从头结点开始依次与第一个链表比较，如果其指数比第一个小，则p向后移动一个单位，如相等，则将两节点的系数相加作为第一个链表当前节点的系数，如果为0，则将此节点栓掉。若果较大，则在p前插入q,q向后移动一个，直到两个链表做完为止。 4、算法描述

用链表实现多项式相加的程序如下：

#include #include #include struct node{ int exp; float coef; struct node*next; };

void add_node(struct node*h1,struct node*h2); void print_node(struct node*h); struct node*init_node()

{

struct node*h=(struct node*)malloc(sizeof(struct node)),*p,*q; int exp;

float coef=1.0; h->next=NULL;

printf(\"请依次输入多项式的系数和指数(如:\\\"2 3\\\"；输入\\\"0 0\\\"时结束):\\n\"); p=(struct node*)malloc(sizeof(struct node)); q=(struct node*)malloc(sizeof(struct node)); for(;fabs(coef-0.0)>1.0e-6;) { scanf(\"%f %d\ if(fabs(coef-0.0)>1.0e-6) { q->next=p; p->coef=coef; p->exp=exp; p->next=NULL; add_node(h,q); } } free(p); free(q); return(h); }

void add_node(struct node*h1,struct node*h2) { struct node*y1=h1,*y2=h2; struct node*p,*q; y1=y1->next; y2=y2->next; for(;y1||y2;) if(y1) { if(y2) { if(y1->expexp) y1=y1->next; else if(y1->exp==y2->exp) { y1->coef+=y2->coef; if(y1->coef==0) { for(p=h1;p->next!=y1;p=p->next); p->next=y1->next;

free(y1); y1=p->next; } else y1=y1->next; y2=y2->next; } else if(y1->exp>y2->exp) { for(p=h1;p->next!=y1;p=p->next); q=(struct node*)malloc(sizeof(struct node)); q->exp=y2->exp; q->coef=y2->coef; q->next=y1; p->next=q; y2=y2->next; } } else return; } else if(y2) do{ q=(struct node*)malloc(sizeof(struct node)); q->exp=y2->exp; q->coef=y2->coef; q->next=NULL; for(p=h1;p->next!=y1;p=p->next); p->next=q; y1=q; y2=y2->next; }while(y2); else return; }

void print_node(struct node*h) { if(h->next==NULL) printf(\"y=0\\n\"); else { printf(\"y=\"); for(;h->next;) {

h=h->next; if(h->exp==0) { printf(\"%f\ if(h->next&&h->next->coef>0.0) printf(\"+\"); }

else { printf(\"%fx%d\ if(h->next&&h->next->coef>0.0) printf(\"+\"); } } printf(\"\\n\"); } }

main() { struct node*y1=(struct node*)malloc(sizeof(struct node)); struct node*y2=(struct node*)malloc(sizeof(struct node)); y1=init_node(); }

printf(\"第一个多项式为:\\n\"); print_node(y1); y2=init_node();

printf(\"第二个多项式为:\\n\"); print_node(y2);

printf(\"两个多项式的和为:\\n\"); add_node(y1,y2); print_node(y1);

5、测试数据与运行结果

输入多项式系数和指数后计算得到结果的截图为：

6、实验总结

此次上机实验应用了链表实现了一次实际操作，完成了一个一元多项式的简单相加，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了链表的重要性以及其应用的方便，并且对指针加深了印象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。