MENU

单链表实现一元多项式的加法

• November 20, 2020 •

昨天有个大二学弟请教数据结构,要我给他讲解这个题目如何用单链表实现,刹那间,我爽快的答应了

问题如图所示:

啥都不说了,都在代码里,上!

#include<stdio.h>
#include<stdlib.h>

/* 定义一个结点,存放单项式 */
typedef struct node
{
    float coef; // 存系数 
    int exp;    // 存指数
    struct node *next; // 指针:存下一个结点的地址 
}PloyNode;

/* 初始化 */
void initiateList(PloyNode** head)
{  
    // 为头结点开辟PloyNode大小的内存空间 
    *head = (PloyNode*)malloc(sizeof(PloyNode));  
    (*head)->next = NULL;   // 刚开始下一个结点默认为空 
}

int n;   // 表示共n个单项式  
PloyNode *list1; // 存放第一个多项式的链表  
PloyNode *list2; // 存放第二个多项式的链表 
float coefs[100]; // 存放多项式的系数
PloyNode*result; // 存放结果多项式的链表 

/* 尾插法建立多项式链表 */
PloyNode* buildListRear(PloyNode* head, float arr[], int n)
{
    // 复制头指针 
    PloyNode* p = head; 
    int exp = 0;    // 指数是从0开始递增的 
    for(int i = 0; i < n; i++)
    {
        // 创建一个新结点,开辟内存空间 
        PloyNode *newNode = (PloyNode*)malloc(sizeof(PloyNode));
        newNode->coef = arr[i];    // 赋值系数 
        newNode->exp = exp++;      // 赋值指数 
        newNode->next = NULL;      // 新结点成为最后一个结点,所以指向空 
        p->next = newNode;         // 之前的最后一个结点的变为倒数第二个结点 
        p = newNode;               // p 又指向最后一个结点 
    }
    return head;
} 

/* 遍历输出多项式链表 */
void output(PloyNode* head)
{
    PloyNode *p = head->next;
    while(p != NULL)
    {
        printf("%.2f", p->coef);   // 打印系数 
        if(p->exp != 0){           // 除了第一项的指数为零,后续都不为0 
            printf(" * X^%d ", p->exp);
        }
        // 控制 + 号 
        if(p->next != NULL)
        {
            printf("+ ");
        }
        p = p->next;
    }
    printf("\n\n");
}

/* 两个多项式相加 */
PloyNode* add(PloyNode* head1, PloyNode* head2)
{
    // 初始化结果链表 
    initiateList(&result);
    PloyNode *p1 = head1, *p2 = head2, *p3 = result;
    int exp = 0;
    while(p1->next != NULL && p2->next != NULL)
    {
        PloyNode* newNode = (PloyNode*)malloc(sizeof(PloyNode));
        newNode->coef = p1->next->coef + p2->next->coef;   // 结果的系数 = 多项式1的系数 + 多项式2的系数 
        newNode->exp = exp++;    // 赋值指数 
        newNode->next = NULL;    // 新结点成为最后一个结点,指针域指向空 
        p3->next = newNode;      //  之前的最后一个结点成为倒数第二个结点 
        p3 = newNode;            // p3 指向最后一个结点 
        p1 = p1->next;           // 多项式一往后遍历 
        p2 = p2->next;           // 多项式二往后遍历 
    }
    // 计算较长的多项式余下的项 
    if(p1->next != NULL){
        // 同上 
        while(p1->next != NULL)
        {
            PloyNode* newNode = (PloyNode*)malloc(sizeof(PloyNode));
            newNode->coef = p1->next->coef;   // 结果的系数 = 多项式1的系数 + 多项式2的系数 
             newNode->exp = exp++;
            newNode->next = NULL;
            p3->next = newNode;
            p3 = newNode;
            p1 = p1->next;
        }
    }else{
        // 同上 
        while(p2->next != NULL)
        {
            PloyNode* newNode = (PloyNode*)malloc(sizeof(PloyNode));
            newNode->coef = p2->next->coef;   // 结果的系数 = 多项式1的系数 + 多项式2的系数 
             newNode->exp = exp++;
            newNode->next = NULL;
            p3->next = newNode;
            p3 = newNode;
            p2 = p2->next;
        }
    }
    return result;
}

int main()
{
    /* 建立第一个多项式 */
    initiateList(&list1); // 初始化第一个多项式 
    printf("请输入第一个多项式的项数:");
    scanf("%d", &n);
    printf("输入 %d 个数作为第一个多项式的系数(用空格隔开):", n);
    for(int i = 0; i < n; i++)
        scanf("%f", &coefs[i]);
    // 尾插建立链表 
    list1 = buildListRear(list1, coefs, n);
    // 输出建立好的第一个多项式
    printf("多项式一:P1 = ");
    output(list1); 
    
    /* 建立第二个多项式 */ 
    initiateList(&list2); // 初始化第一个多项式 
    printf("请输入第二个多项式的项数:");
    scanf("%d", &n);
    printf("输入 %d 个数作为第二个多项式的系数(用空格隔开):", n);
    for(int i = 0; i < n; i++)
        scanf("%f", &coefs[i]);
    // 尾插建立链表 
    list2 = buildListRear(list2, coefs, n);
    // 输出建立好的第二个多项式
    printf("多项式二:P2 = ");
    output(list2); 
    
    /* 计算 */ 
    initiateList(&result); // 初始化结果多项式
    result = add(list1, list2);
    printf("相加结果为:P = "); 
    output(result);
}

运行结果:

Archives QR Code Tip
QR Code for this page
Tipping QR Code