测试链表

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//定义链表
typedef struct LNode {
    int x;
    int z;
    struct LNode* next;
}LNode, * PtrNode;//同时为结构体，结构体指针重定义
//长度
int length(PtrNode L) {
    PtrNode p = L->next;
    int cnt = 0;
    while (p) {
        cnt++;
        p = p->next;
    }
    return cnt;
}
//初始化
PtrNode Init() {
    PtrNode L = (PtrNode)malloc(sizeof(LNode));
    L->next = NULL;
    return L;
}
//头插法
void InsertHead(PtrNode L, int x, int z) {
    PtrNode p = L->next;
    PtrNode q = (PtrNode)malloc(sizeof(LNode));
    q->x = x;
    q->z = z;
    q->next = p;
    L->next = q;
}
//尾插法
void InsertTail(PtrNode L, int x, int z) {
    PtrNode p = L;
    while (p->next) {
        p = p->next;
    }
    PtrNode q = (PtrNode)malloc(sizeof(LNode));
    q->x = x;
    q->z = z;
    q->next = NULL;
    p->next = q;
}
//测试
int main() {
    PtrNode L1 = Init();
    PtrNode L2 = Init();
    int n1,n2;
    scanf("%d", &n1);
    for (int i = 0; i < n1; i++) {
        int x, z;
        scanf("%d %d", &x, &z);
        InsertTail(L1, x, z);
    }
    scanf("%d", &n2);
    for (int i = 0; i < n2; i++) {
        int x, z;
        scanf("%d %d", &x, &z);
        InsertHead(L2, x, z);
    }
    PtrNode p1 = L1->next;
    while (p1) {
        printf("%d %d\n", p1->x, p1->z);
        p1 = p1->next;
    }
    printf("%d\n", length(L1));
    
    PtrNode p2 = L2->next;
    while (p2) {
        printf("%d %d\n", p2->x, p2->z);
        p2 = p2->next;
    }
    printf("%d\n", length(L2));
}

输入：
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1
输出：

3 4
-5 2
6 1
-2 0
4
3 1
-7 4
5 20
3
 

习题3.6 一元多项式的乘法与加法运算

习题3.6 一元多项式的乘法与加法运算 - 浙大版《数据结构（第2版）》题目集

一、链表思路

1.由于最后降序排列，并且要合并指数相同的项，要移动较多元素。首先想到使用带头结点的单向链表（若限制指数大小，使用线性表＋哈希表会更方便）。

2.使用链表L1，L2分别存储两个多项式。

3.对于乘法，使用L3保存结果。对于加法，直接使用L1存储结果即可。

4.乘法和除法在加入新项（q）时的思路是一致的，设保存结果的链表为L。

（1）L为空，则直接尾插即可。

（2）L不为空，则使用指针k（前驱），p（后继）从头遍历链表，直到指针p的指数小于等于q的指数。

a.L内所有项的指数均大于q的指数，此时p=NULL：k->next=q。

b.p的指数小于q的指数：q->next=p;k->next=q;

c.p的指数等于q的指数：p->x+=x;（x为系数）

注:健壮性考虑

1.同类项合并时有抵消

针对情况4.(2).b：若合并完成后q->x==0，则应该舍弃这个系数为0的项。

2.系数和指数取上限，结果有零多项式

输出时判断结果中，每项系数x是否全为0即可。遇到0多项式则输出0 0。

3.输入有零多项式和常数多项式

针对4.(2)：面对新项时，判断其系数是否为0，为0则舍弃该项。

二、链表完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
    int x;
    int z;
    struct LNode* next;
}LNode,*PtrLNode;
int Length(PtrLNode L){
    PtrLNode p=L->next;
    int cnt=0;
    while(p){
        cnt++;
        p=p->next;
    }
    return cnt;
}
//初始化
PtrLNode Init(){
    PtrLNode L=(PtrLNode)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}
//尾插法
void InsertTail(PtrLNode L,int x,int z){
    PtrLNode p=L;
    while(p->next){
        p=p->next;
    }
    PtrLNode q=(PtrLNode)malloc(sizeof(LNode));
    q->x=x;
    q->z=z;
    q->next=NULL;
    p->next=q;
}
//创造新结点
PtrLNode create(int x,int z){
    PtrLNode q=(PtrLNode)malloc(sizeof(LNode));
    q->x=x;
    q->z=z;
    //必须指向空
    q->next=NULL;
    return q;
}
//插入新项
void InsertL3(PtrLNode L3,int x,int z){
    if(x==0){
        return;
    }
    PtrLNode p3=L3->next;
    PtrLNode k=L3;
    while(p3!=NULL&&p3->z>z){
        k=p3;
        p3=p3->next;
    }
    if(p3!=NULL&&p3->z==z){
        //相同则合并
        p3->x+=x;
        //合并后系数为零则舍弃
        if(p3->x==0){
            k->next=p3->next;
            free(p3);
        }
    }
    else{
        //插入新节点（表头，表中，表尾）
        PtrLNode q=create(x,z);
        q->next=p3;
        k->next=q;
    }
}
//乘
void muilty(PtrLNode L1,PtrLNode L2,PtrLNode L3){
    PtrLNode p1;
    PtrLNode p2;
    int xx,zz;
    for(p1=L1->next;p1!=NULL;p1=p1->next){
        for(p2=L2->next;p2!=NULL;p2=p2->next){
            xx=p1->x*p2->x;
            zz=p1->z+p2->z;
            InsertL3(L3,xx,zz);
        }
    }
}
//加
void sum(PtrLNode L1,PtrLNode L2){
    PtrLNode p2=L2->next;
    while(p2){
        InsertL3(L1,p2->x,p2->z);
        p2=p2->next;
    }
}
//输出（保持健壮性）
void PrintPoly(PtrLNode L){
    PtrLNode p;
    int isfirst=1;
    int value=0;
    for(p=L->next;p!=NULL;p=p->next){
        if(p->x!=0){
            value=1;
            if(isfirst){
                printf("%d %d",p->x,p->z);
                isfirst=0;
            }else{
                printf(" %d %d",p->x,p->z);
            }
        }
    }
    if(value==0){
        printf("0 0");
    }
}

int main(){
    PtrLNode L1=Init();
    PtrLNode L2=Init();
    PtrLNode L3=Init();
    int n1,n2,x,z;
    scanf("%d",&n1);
    for(int i=0;i<n1;i++){
        scanf("%d %d",&x,&z);
        InsertTail(L1,x,z);
    }
    scanf("%d",&n2);
    for(int i=0;i<n2;i++){
        scanf("%d %d",&x,&z);
        InsertTail(L2,x,z);
    }
    //多项式乘法L1*L2=L3
    muilty(L1,L2,L3);
    //多项式加法L1+L2=L1
    sum(L1,L2);
    //输出
    PrintPoly(L3);
    printf("\n");
    PrintPoly(L1);
}

最终好结局

三、顺序表思路

注意到题目中，指数范围大于等于0，且小于1000，只要搞一个较大的数组p[2005]，用哈希表即可简单解决

四、顺序表代码

#include<stdio.h>
#include<stdlib.h>
typedef struct poly{
    int x;
    int z;
}poly,*Ppoly;
void muiltiple(Ppoly p1,Ppoly p2, Ppoly p3,int n1,int n2){
    int xx,zz;
    for(int i=0;i<n1;i++){
        for(int j=0;j<n2;j++){
            xx=p1[i].x*p2[j].x;
            zz=p1[i].z+p2[j].z;
            p3[zz].x+=xx;
            p3[zz].z=zz;
        }
    }
}
void sum(Ppoly p1,Ppoly p2,Ppoly p4,int n1, int n2){
    int xx,zz;
    for(int i=0;i<n1;i++){
        xx=p1[i].x;
        zz=p1[i].z;
        p4[zz].x+=xx;
        p4[zz].z=zz;
    }
    for(int i=0;i<n2;i++){
        xx=p2[i].x;
        zz=p2[i].z;
        p4[zz].x+=xx;
        p4[zz].z=zz;
    }
}
void printPoly(Ppoly p){
    int value=0;
    int isfirst=1;
    for(int i=2004;i>=0;i--){
        if(p[i].x!=0){
            value=1;
            if(isfirst){
                printf("%d %d",p[i].x,p[i].z);
                isfirst=0;
            }else{
                printf(" %d %d",p[i].x,p[i].z);
            }
        }
    }
    if(value==0){
        printf("0 0");
    }
}
int main(){
    int n1,n2;
    scanf("%d",&n1);
    poly p1[2005]={0},p2[2005]={0},p3[2005]={0},p4[2005]={0};
    for(int i=0;i<n1;i++){
        scanf("%d %d",&p1[i].x,&p1[i].z);
    }
    scanf("%d",&n2);
    for(int i=0;i<n2;i++){
        scanf("%d %d",&p2[i].x,&p2[i].z);
    }
    muiltiple(p1,p2,p3,n1,n2);
    sum(p1,p2,p4,n1,n2);
    printPoly(p3);
    printf("\n");
    printPoly(p4);
}