一元稀疏多项式加法
实习一 线性表及其应用
题目：一元稀疏多项式加法 一．需求分析：
设计一个实现一元稀疏多项式相加运算的演示程序。
基本要求：（1）输入并建立两个多项式；（2）多项式a 与b 相加，建立和多项式c ；（3）输出多项式a,b,c 。输出格式：比如多项式a 为：A(x)=c1xe 1+ c2xe 2+…+ c m xe m ，其中，c i 和e i 分别为第i 项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e 2＜…＜e m 。多项式b,c 类似输出。
实习时间：2011.3.25
二．设计：
⏹ 1. 设计思想
（1）用带头结点的单链表存储多项式。
（2）三个多项式链表中都只存储非零系数项。若多项式a 与b 中指数相等的两项相加后，系数为零，则在和多项式c 中不存储该指数项。
⏹ 2. 设计表示
（1）函数调用关系图：
main →ListCreate →ListInsertSort →ListAdd →Printf （2）函数接口规则说明：
int ListCreate(SLNode **head,int t)/*建立以head 为头指针的有t 个结点的单向链表
void ListInsertSort(SLNode *head,int n)/*对以head 为头指针有n 个结点的单向链表按其存储的多项式各项的指数用冒泡法排序法由小到大排序*/
int ListAdd(SLNode *f1,SLNode *f2,SLNode **head,int n1,int n2)/*将有n1项的多项式f1和有n2项的多项式f2相加，存储在新建的以head 为头指针的单向链表中*/
void Printf(SLNode *la)/*按题目要求输出多项式la*/
⏹ 3. 实现注释
（1）根据多项式的项数n 、系数以及指数建立单向链表； （2）多项式的项数、系数和指数均可自由输入； （3）多项式按A(x)=c1xe 1+ c2xe 2+…+ cm xe m 的形式输出
⏹ 4. 详细设计
创建函数
int ListCreate(SLNode **head,int t) {
SLNode *p,*q; int i;
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
(*head)->next=NULL;q=*head; for(i=0;i
if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
printf("请输入x 的系数data 和指数n:"); scanf("%d%d",&p->data,&p->n); p->next=NULL;q->next=p;q=p; }
return 1; }
插入函数
void ListInsertSort(SLNode *head,int n) {
SLNode *p,*q,*s; int i,j,k; j=n;k=1; while(k
i=1; p=head; q=p->next; s=q->next; while(i
if(q->n>s->n) {
p->next=s; q->next=s->next; s->next=q; p=s; s=q->next; } else {
p=p->next; q=q->next; s=s->next; }i++; }j--;k++; } }
求和函数
int ListAdd(SLNode *f1,SLNode *f2,SLNode **head,int n1,int n2) {
SLNode *p,*q,*M,*N; int i=0,j=0;
M=f1->next,N=f2->next;
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)
printf("内存空间不足！\n"); return 0; }
(*head)->next=NULL;q=*head; while(i
if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
if(M->nn) {
p->data=M->data; p->n=M->n; M=M->next; i++; }
else if(M->n>N->n) {
p->data=N->data; p->n=N->n; N=N->next; j++; } else {
p->data=M->data+N->data; p->n=M->n; M=M->next; N=N->next; i++; j++; }
if(p->data==0) free(p); else {
q->next=p; p->next=NULL; q=p; }
if(i>=n1) {
while(j
if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
p->data=N->data; p->n=N->n; N=N->next; q->next=p; p->next=NULL; q=p; j++; } }
if(j>=n2) {
while(i
if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
p->data=M->data; p->n=M->n; M=M->next; q->next=p; p->next=NULL; q=p; i++; } }
return 1; }
输出函数
void Printf(SLNode *la) {
SLNode *p; p=la->next; if(la->next==NULL) {
free(p); printf("0"); return; }
if(p->n==0) printf("%d",p->data); else if(p->data==1) printf("X%d",p->n); else if(p->data==-1) printf("-X%d",p->n); else printf("%dX%d",p->data,p->n); p=p->next;
while(p->next!=NULL) {
if(p->data==1) printf("+X%d",p->n); else if(p->data==-1) printf("-X%d",p->n);
else if((p->datadata!=-1)) printf("%dX%d",p->data,p->n); else printf("+%dX%d",p->data,p->n); p=p->next; }
if(p->next==NULL) {
if(p->data==1) printf("+X%d",p->n); else if(p->data==-1) printf("-X%d",p->n);
else if((p->datadata!=-1)) printf("%dX%d",p->data,p->n); else printf("+%dX%d",p->data,p->n); } }
三. 调试分析
四、用户手册
五、运行结果
六、源程序清单
#include #include
typedef struct Node {
int data; int n;
struct Node *next; }SLNode;
int ListCreate(SLNode **head,int t) {
SLNode *p,*q; int i;
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
(*head)->next=NULL;q=*head;
for(i=0;i
if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
printf("请输入x 的系数data 和指数n:"); scanf("%d%d",&p->data,&p->n); p->next=NULL;q->next=p;q=p; }
return 1; }
void ListInsertSort(SLNode *head,int n) {
SLNode *p,*q,*s; int i,j,k; j=n;k=1; while(k
i=1; p=head; q=p->next; s=q->next; while(i
if(q->n>s->n) {
p->next=s; q->next=s->next; s->next=q; p=s; s=q->next; } else {
p=p->next; q=q->next; s=s->next; }i++; }j--;k++;
} }
int ListAdd(SLNode *f1,SLNode *f2,SLNode **head,int n1,int n2) {
SLNode *p,*q,*M,*N; int i=0,j=0;
M=f1->next,N=f2->next;
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
(*head)->next=NULL;q=*head; while(i
if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL) {
printf("内存空间不足！\n"); return 0; }
if(M->nn) {
p->data=M->data; p->n=M->n; M=M->next; i++; }
else if(M->n>N->n) {
p->data=N->data; p->n=N->n; N=N->next; j++; } else {
p->data=M->data+N->data; p->n=M->n; M=M->next; N=N->next; i++; j++;
}
if(p->data==0) free(p);
else
{
q->next=p;
p->next=NULL;
q=p;
}
}
if(i>=n1)
{
while(j
{
if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL)
{
printf("内存空间不足！\n");
return 0;
}
p->data=N->data;
p->n=N->n;
N=N->next;
q->next=p;
p->next=NULL;
q=p;
j++;
}
}
if(j>=n2)
{
while(i
{
if((p=(SLNode *)malloc(sizeof(SLNode)))==NULL)
{
printf("内存空间不足！\n");
return 0;
}
p->data=M->data;
p->n=M->n;
M=M->next;
q->next=p;
p->next=NULL;
q=p;
i++;
}
}
return 1;
}
void Printf(SLNode *la)
{
SLNode *p;
p=la->next;
if(la->next==NULL)
{
free(p);
printf("0");
return;
}
if(p->n==0) printf("%d",p->data);
else if(p->data==1) printf("X%d",p->n);
else if(p->data==-1) printf("-X%d",p->n);
else printf("%dX%d",p->data,p->n);
p=p->next;
while(p->next!=NULL)
{
if(p->data==1) printf("+X%d",p->n);
else if(p->data==-1) printf("-X%d",p->n);
else if((p->datadata!=-1)) printf("%dX%d",p->data,p->n); else printf("+%dX%d",p->data,p->n);
p=p->next;
}
if(p->next==NULL)
{
if(p->data==1) printf("+X%d",p->n);
else if(p->data==-1) printf("-X%d",p->n);
else if((p->datadata!=-1)) printf("%dX%d",p->data,p->n); else printf("+%dX%d",p->data,p->n);
}
}
void main()
{
SLNode *f1,*f2,*f3;
int t1,t2;
printf("请输入两个多项式非零项个数t1,t2\n"); scanf("%d%d",&t1,&t2);
if(t1
{
printf("输入参数错误！\n");
return;
}
printf("创建多项式f1\n");
ListCreate(&f1,t1);
printf("创建多项式f2\n");
ListCreate(&f2,t2);
ListInsertSort(f1,t1);
ListInsertSort(f2,t2);
ListAdd(f1,f2,&f3,t1,t2);
printf("f1(X)=");
Printf(f1);
printf("\nf2(X)=");
Printf(f2);
printf("\nf3(X)=");
Printf(f3);
printf("\n");
}