链表的生成
利用链表实现一元多项式的+、-、*运算，注意具体的思路是判断同类项，对其进行合并同类项，在乘法运算达到了O(n^3)，可以优化的地方是先对结果链表C进行预处理，先复制这个链表给C，然后表C的操作过程就将了一维，变成O(n^2)，并且每次可以利用链表的有序性这一点进行二分，但这是链表啊！怎么二分？还没想到，干脆把链表先导入数组中，然后在操作？这样就O(nlogn)了？....扯远了，就先O(n^3)吧。
要求：
实验五、线性表应用—一元多项式加减运算
1 实验目的
掌握用线性结构表示一元多项式的方法及实现一元多项式的加、减运算。
2 实验内容
两个一元多项式从键盘输入，每一项主要包括系数和指数两个数据，分别将两个一元多项式存到两个单链表中，然后对两个一元多项式进行加、减运算，最后输出结果。
3 实验过程
（1）：
（截图）
（2） ：
（截图）
（3） ：
（截图）
4 源代码
（附件）
具体代码如下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//******宏定义参数******
#define OK 1
#define NO 0
#define DATA_MAX_SIZE 20
//******定义数据类型别名******
typedef int Status;
typedef char Excelelem;
typedef int Numelem;
typedef double db;
//******声明数据结构******
typedef struct Node
{
db xishu;
db mi;
struct Node *next;
}LNode,*LinkList;
typedef struct
{
Excelelem name[100];
Numelem length;
LinkList next;
}HeadList,*HeadLinkList;
//******声明函数******
LinkList Init(Numelem *n); //初始化链表体
HeadLinkList HeadInit(char a[]); //初始化链表头
LinkList DATA_UPPER_FIND(LinkList Head,db ans); //查找链表中第一个系数大于ans的结点的前驱
void DATA_ADD(HeadLinkList A,HeadLinkList B,HeadLinkList C); //多项式加法 O(n)
void DATA_SUB(HeadLinkList A,HeadLinkList B,HeadLinkList C); //多项式减法 O(n)
void DATA_Free(HeadLinkList Head); //释放链表体内存
void DATA_cout(HeadLinkList Head); //将链表数据域以多项式形势输出
void DATA_MUL(HeadLinkList A,HeadLinkList B,HeadLinkList C); //多项式乘法 O(n^3)
int main()
{
HeadLinkList A,B,C;
Numelem n;
printf("**********start!**********\n");
A=HeadInit("A多项式");
printf("请输入%s:\n",A->name);
A->next=Init(&A->length);
B=HeadInit("B多项式");
printf("请输入%s:\n",B->name);
B->next=Init(&B->length);
C=HeadInit("C多项式");
C->next=NULL;
printf("请输出%s的内容:\n",A->name);
DATA_cout(A);
printf("请输出%s的内容\n",B->name);
DATA_cout(B);
printf("%s+%s:\n",A->name,B->name);
DATA_ADD(A,B,C);
DATA_cout(C);
printf("%s-%s:\n",A->name,B->name);
DATA_SUB(A,B,C);
DATA_cout(C);
printf("%s*%s:\n",A->name,B->name);
DATA_MUL(A,B,C);
DATA_cout(C);
printf("操作结束，释放内存!\n");
DATA_Free(A);DATA_Free(B);DATA_Free(C);
free(A),free(B),free(C);
printf("***********End!***********\n");
return 0;
}
//******查找插入的位置******
LinkList DATA_UPPER_FIND(LinkList Head,db ans)
{
if(Head->next == NULL || Head->next->mi > ans)
return Head;
return DATA_UPPER_FIND(Head->next,ans);
}
LinkList Init(Numelem *n)
{
//以系数=0为输入结束标志,以下为输入的多项式默认为已合并同类项，否则在查找的时候多一项特判
LinkList Head,p,q;
Numelem i=0;
db a,b;
Head=NULL;
while(~scanf("%lf",&a) && a!=0.0)
{
scanf("%lf",&b);
q=(LinkList)malloc(sizeof(LNode));
q->xishu=a;
q->mi=b;
if(*n==0 || Head->mi>b) q->next=Head,Head=q;
else
{
p=DATA_UPPER_FIND(Head,b);
//if p->mi==b ... 未合并同类项的情况
q->next=p->next;
p->next=q;
}
*n++;
}
return Head;
}
HeadLinkList HeadInit(char *a)
{
HeadLinkList Head;
Head=(HeadLinkList)malloc(sizeof(HeadList));
strcpy(Head->name,a);
Head->length=0;
return Head;
}
void DATA_ADD(HeadLinkList A,HeadLinkList B,HeadLinkList C)
{
LinkList qa=A->next,qb=B->next,p,q=NULL;
DATA_Free(C);
while(qa || qb)
{
p=(LinkList)malloc(sizeof(LNode));
if(qb==NULL || qa && qa->mi<qb->mi)
{
*p=*qa;
qa=qa->next;
}
else if(qa==NULL || qb && qa->mi>qb->mi)
{
*p=*qb;
qb=qb->next;
}
else
{
p->xishu=qb->xishu+qa->xishu;
p->mi=qb->mi;
qa=qa->next;
qb=qb->next;
}
if(q==NULL) p->next=q,C->next=q=p;
else
p->next=q->next,q->next=p,q=p;
C->length++;
}
}
void DATA_SUB(HeadLinkList A,HeadLinkList B,HeadLinkList C)
{
LinkList qa=A->next,qb=B->next,p,q=NULL;
DATA_Free(C);
while(qa!=NULL || qb!=NULL)
{
p=(LinkList)malloc(sizeof(LNode));
if(qb==NULL || qa && qa->mi<qb->mi)
{
*p=*qa;
qa=qa->next;
}
else if(qa==NULL || qb && qa->mi>qb->mi)
{
*p=*qb;
p->xishu*=-1;
qb=qb->next;
}
else
{
*p=*qa;
p->xishu-=qb->xishu;
qa=qa->next;
qb=qb->next;
if(p->xishu==0)
{
free(p);
continue;
}
}
if(q==NULL) p->next=q,C->next=q=p;
else
q->next=p->next,q->next=p,q=p;
C->length++;
}
}
void DATA_MUL(HeadLinkList A,HeadLinkList B,HeadLinkList C)
{
LinkList qa,qb,p,q;
db a,b;
DATA_Free(C);
for(qa=A->next;qa;qa=qa->next)
{
for(qb=B->next;qb;qb=qb->next)
{
a=qa->xishu*qb->xishu;
b=qa->mi+qb->mi;
if(C->length)
{
p=DATA_UPPER_FIND(C->next,b);
if(p->mi == b)
p->xishu+=a;
else
{
q=(LinkList)malloc(sizeof(LNode));
q->xishu=a;
q->mi=b;
q->next=p->next;
p->next=q;
C->length++;
}
}
else
{
p=(LinkList)malloc(sizeof(LNode));
p->xishu=a;
p->mi=b;
p->next=C->next;
C->next=p;
C->length++;
}
}
}
}
void DATA_Free(HeadLinkList Head)
{
LinkList q=Head->next,p;
while (q)
{
p=q;
q=q->next;
free(p);
}
Head->length=0;
Head->next=NULL;
return ;
}
void DATA_cout(HeadLinkList Head)
{
LinkList q=Head->next;
while(q)
{
if(q->xishu>0 && q!=Head->next)
printf("+");
printf("%.1lfx^(%.1lf)",q->xishu,q->mi);
q=q->next;
}
printf("\n");
return ;
}
总结：
链表和顺序表的直接操作各有优点，在处理离散程度较大的数据时，链表可以节省空间，顺序表就会比较耗内存；在处理相对连续的数据时，用到顺序表就可以利用其逻辑结构和物理结构一直这一特点，降低算法的复杂度。
京公网安备 11010502036488号