单向链表的学习

算法

字数统计: 967阅读时长: 4 min

 2018/03/23   Share

最近慢慢地在学习算法，数据结构也越来越难理解，正好碰见一道题目来复习单向链表，使用一元多项式表示多项式并求和。
对于链表，结构体中得包含指向下一个节点的指针。
这道题的重点在于如何去表示多项式，并且如何去比较指数并相加。
先定义结构体并将结构体指针化：

struct node {
    float coef; //系数
    int expn;   //指数
    struct node *next; //指向下一个节点的指针
};
typedef struct node *linklist;  //将结构指针化

之后我的想法是头节点不存放多项式，从第二个节点来进行存储。两个多项式p,q都输入完毕后开始进行比较：如果p的第一项指数比q的第一项指数小，就把p的下一项和q的这一项比较；如果指数相等，就把两项的系数相加；如果p的指数大，那就把q的这一项插入到p的前一项。之后就把其他的代码写出就完成了。这就是大体的思路。

源码部分

#include<stdio.h>
#include<stdlib.h>
struct node {
    float coef; //系数
    int expn;   //指数
    struct node *next; //指向下一个节点的指针
};
typedef struct node *linklist;  //将结构指针化

void CreatPolyn(linklist p, int m) //生成一个新的多项式
{
    int i;
    linklist head = p;
    head->coef = 0.0; head->expn = -1; head->next = NULL; //设置头节点指数为-1，不存储多项式
    p = head;
    for (i = 0; i<m; i++)
    {
        p = p->next = (linklist)malloc(sizeof(struct node));
        scanf("%f%d", &p->coef, &p->expn);
    }
    p->next = NULL;
}
int cmp(int p, int q) //比较两个指数是否相等
{
    if (p < q)
        return -1;
    else if(q == p)
        return 0;
    else
        return 1;
}
void Append(linklist p, linklist qa) 
{
    while (p->next != NULL)
    {
        p = p->next;
        if (p->next == NULL)
        {
            p->next = qa;
            break;
        }
    }
}
void AddPolyn(linklist p, linklist q) //将p+q的值写入p中
{
    float sum = 0;
    linklist ha = p,hb = q,temp = NULL; //用来表示头节点或者pa或qa的上一个节点
    linklist pa = p->next; linklist qa = q->next; //用pa和qa来遍历链表
    while (pa && qa) //如果pa和qa都不为NULL
    {
        switch (cmp(pa->expn, qa->expn))
        {
            case -1:  //如果p的指数较小
                pa = pa->next;
                ha = ha->next;
                break;
            case 0:  //指数相等
                sum = pa->coef + qa->coef;
                if (sum != 0)
                {
                    pa->coef = sum; //将系数的和写入p中
                }
                else //如果系数等于0，就释放当前这个节点
                {
                    temp = pa->next; //用临时变量暂时存储下个节点
                    free(ha->next); 
                    ha->next = temp;
                    pa = ha->next;
                }
                temp = qa->next; //释放q的当前节点，并取下一个节点
                free(qa);
                qa = temp;
                if(pa->next != NULL)
                    pa = pa->next; //如果pa不是最后一个节点则pa移到下一个节点
                break;
            case 1:  //q的指数较小
                temp = qa->next; //用临时变量存储qa的下一个值    
                ha->next = qa;   //常见的插入元素操作    
                qa->next = pa;     
                ha = ha->next;
                qa = temp;  //让qa继续下一次比较
                break;
        }
    }
    if (qa != NULL)
    {
        Append(p, qa);//将qa剩下的值接到p后面
    }
    free(temp);
    free(hb);
}


int main(void)
{
    int n, m;
    linklist p = (linklist)malloc(sizeof(struct node));
    linklist q = (linklist)malloc(sizeof(struct node));
    printf("格式：<系数，指数>\n");
    printf("请输入第一个多项式的项数：");
    scanf("%d", &n);
    CreatPolyn(p, n);
    printf("请输入第二个多项式的项数：");
    scanf("%d", &m);
    CreatPolyn(q, m);
    AddPolyn(p, q);
    //输出结果
    printf("两个多项式的和为：\n");
    p = p->next;
    while (p != NULL)
    {
        printf("<%f,%d>  ", p->coef, p->expn);
        p = p->next;
    }
    return 0;
}

我想学数据结构就是去思考，然后多写代码，理解每一句伪代码，并用自己的代码来实现。

原文作者：Zer0e

原文链接：https://re0.top/2018/03/23/polynomial/

发表日期：三月 23日 2018, 9:09:53 晚上

更新日期：March 25th 2018, 9:35:39 pm

Next Post

记一次有趣的二次注入
Previous Post

misc入门总结

CATALOG

1. 源码部分

