实习一线性表及其应用
题目：一元稀疏多项式加法实习时间：2011.3.25
一．需求分析：
设计一个实现一元稀疏多项式相加运算的演示程序。
基本要求：（1）输入并建立两个多项式；（2）多项式a与b相加，建立和多项式c；（3）输出多项式a,b,c。输出格式：比如多项式a为：A(x)=c1xe1+ c2xe2+…+ c m xe m，其中，c i和e i分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤e1＜e2＜…＜e m。多项式b,c类似输出。
二．设计：
⏹ 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)=c1xe1+ c2xe2+…+ c m 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->n { 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; }
