数据结构之线性结构（应用实例）

本文为数据结构之线性结构（应用实例），根据网课而整合的笔记。

栗子：

设计函数分别求两个一元多项式的乘积与和

该题的输入与输出样例：

求解思路

1. 多项式表示
2. 程序框架
3. 读多项式
4. 加法实现
5. 乘法实现
6. 多项式输出

一、多项式的表示

（仅表示非零项）

数组：

• 编程简单、调试容易
• 需要事先确定数组大小（若不确定会造成空间浪费）

链表：

• 动态性强
• 编程略为复杂、调试比较困难

PS:一种比较好的实现方法是：动态数组

下面介绍链表表示

数据结构设计

typedef struct PolyNode *Polynomial;
struct PolyNode{
	int coef;/*系数*/
	int expon;/*指数*/
	Polynomial link;
};

二、程序框架搭建

int main()
{
	读入多项式1
	读入多项式2
	乘法运算并输出
	加法运算并输出
	
	return 0；
}

需要设计的函数：

• 读入一个多项式
• 两多项式相乘
• 两多项式相加
• 多项式输出

int main()
{
	Polynomial P1,P2,PP,PS;
	
	P1 = ReadPoly();
	P2 = ReadPoly();
	PP = Mult(P1,P2);
	PrintPoly(PP);
	PS = Add(P1,P2);
	PrintPoly(PS);
	
	return 0;
}

三、如何读入多项式

输入数据格式：4 3 4 -5 2 6 1 -2 0（4为4组数，然后再循环一对一对读入）

Polynomial ReadPoly()
{
	...
	scanf("%d",&N);
	...
	while(N--){
		scanf("%d %d",&c,&e);/*每对数据按指数递减顺序读入*/
		Attach(c,e,&Rear);/*构造并插入新结点*/
	}
	...
	return P;
}

思考：Rear初值是多少？

两种处理方法：

1.Rear初值为NULL

​ 在Attach函数中根据Rear是否为NULL做不同处理（Attach一开始会判别Rear是否为NULL，如果是NULL则申请结点把Rear指向NULL改成把Rear指向这个结点；如果不为NULL则直接把新的结点插入后面）

2.Rear指向一个空结点

​ 结束后要把最后的空结点删掉

四、如何读入多项式

void Attach(int c,int e,Polynomail *pRear)/*pRear是指针的指针*/
{
	Polynomial P;
	P = (Polynomial)malloc(sizeof(struct PolyNode));/*申请结点*/
	P->coef = c; /*对新结点赋值*/
	P->expon = e;
	P->link = NULL;
	(*pRear)->link = P;
	*pRear = P;  /*修改pRear值*/
}

Polynomial ReadPoly()
{
	Polynomial P,Rear,t;
	int c,e,N;
	scanf("%d",&N);
	P = (Polynomial)malloc(sizeof(struct PolyNode));/*链表头空结点*/
	P->link = NULL;
	Rear = P;/*第二种处理方法，一开始就是空结点*/
	while(N--){
		scanf("%d %d",&c,&e);
		Attach(c,e,&Rear);/*将当前项插入多项式尾部*/
	}
	t = P;P = P->link;/*删除临时生成的头结点*/
	free(t);
	return P;
}

五、如何将两个多项式相加

架构

Polynomial Add(Polynomial P1,Polynomial P2)
{	...
	t1 = P1,t2 = P2;
	P = (Polynomial)malloc(sizeof(struct PolyNode));/*构造空结点*/
	P->link = NULL;
	Rear = P;
	while(t1 && t2){
		if(t1->expon == t2->expon){
			...
		}
		else if(t1->expon > t2->expon){
			...
		}
		else{
			...
		}
	}
	while(t1){
		...
	}
	while(t2){
		...
	}
	...
	return P;
}

第一个while 判断指数，计算系数

第二个while和第三个while 分别判断t1和t2为空的情况

方法：

1.将乘法运算转换为加法运算

将P1当前项(ci,ei)乘P2多项式，再加到结果多项式里

t1 = P1;t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;
while(t2){
	Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
	t2 = t2->link;
}

2.逐项插入

将P1当前项(ci,ei)乘P2当前项(c2i,e2i),并插入到结果多项式中。关键是要找到插入位置

初次结果多项式可由P1第一项乘P2获得（如上）

Polynomail Mult(Polynomial P1,Polynomial P2)
{	
    Polynomial P,Rear,t1,t2,t;
    int c,e;
    if(!P1||!P2) return NULL;
	t1 = P1;t2 = P2;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P;
	while(t2){/*先用P1的第1项乘以P2，得到P*/
		Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
        t2 = t2->link;
	}
	t1 = t1->link;
	while(t1){
		t2 = P2;Rear = P;
		while(t2){
			e = t1->expon + t2->expon;/*计算指数*/
			c = t1->coef*t2->coef;/*计算系数*/
			while(Rear->link&&Rear->link->expon>e)
                Rear = Rear->link;
            if(Rear->link&&Rear->link->expon == e){
                if(Rear->link->coef+c)
                    Rear->link->coef+=c;
                else{
                    t = Rear->link;
                    Rear->link=t->link;
                    free(t);
                }
            }
            else{
            	t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = c;t->expon = e;
                t->link = Rear->link;
                Rear->link = t;Rear = Rear->link;
            }
			t2 = t2->link;
		}
		t1 = t1->link;
	}
	t2 = P;P = P->link;
    free(t2);
    return P;
}

六、如何将多项式输出

void PrintPoly(Polynomial P)
{	/*输出多项式*/
	int flag = 0;/*辅助调整输出格式用*/
    if(!P){
    	printf("0 0\n");
    	return;
    }
    while(P){
    	if(!flag)
    		flag = 1;
    	else
    		printf(" ");
    	printf("%d %d",P->coef,P->expon);
    	P = P->link;
    }
	printf("\n");	
}

声明：部分资料源自网络，如有侵权，请联系我删除！
文中如存在谬误、混淆等不足，欢迎批评指正！