入门数据结构的心得1(单链表篇）

目前正在学习数据结构，刚刚学到单链表，写了一份简单的代码，自己来缕缕思路。
先上题：

就是一个很简单的用单链表实现多项式加减。????

首先当然是先用结构体定义节点

1.首先当然是先用结构体定义节点，一个多项式它既然是由额两个元素组成嘛，就是前面的系数和后面的指数，那么我们的节点自然需要开三个域对吧，所以就这样写：

点击查看代码（三角形剪头可以点）

typedef struct Node{
    float val;
    int index;
    struct Node *next;
}Node;

2.然后想啊，肯定要创建三个链表吧（好吧，其实一开始我没想到(`・ω・´)），题目中呢有两个，再加上一个我们自己要来存储答案的嘛，当然，这第三个先不急，我们要先解决前两个的输入问题，又因为呢题目说A和B一开始无序，个人认为不仅是之后的第三个要排序，可以先顺带把A和B排序了，方便做题，所以排序函数也是要写的。那么就先从主函数入手：

点击查看代码

int n;
scanf("%d",&n);
Node *head1=NULL;
Node *head2=NULL;

这两句不用解释吧，就是定义一下，然后是输入。

点击查看代码

for(int i=0;i<n;i++){
    float val;
    int index;
    scanf("%f %d",&val,&index);
    createList(&head1,val,index);
}

就是定义两个值嘛，然后通过循环依次输入，这createlist函数呢，我等下再写，至少你要先假设有这么个函数等下用来创建单链表嘛。

接下来就是排序A，输入B，排序B.

点击查看代码

    sortlist(&head1);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        float val;
        int index;
        scanf("%f %d",&val,&index);
        createList(&head2,val,index);
    }
    sortlist(&head2);

3.然后就可以来写createlist函数了，其实就是一个创建单链表嘛；

首先是函数的形参：
void createList(Node **head,float val,int index)
为什么用二级指针的head呢？

这边是简单讲一下为什么用二级指针，理解的可以直接跳过

其实很好理解（~~我认为(´;ω;`)~~），你想啊，我们的单链表等下需不需要排序？那么是不是有可能这个头节点会发生变化呢？都知道啊，这个二级指针它是一个指向指针的指针，记录的是一级指针的地址对吧，这意味着什么呢，就是你可以通过它去访问和修改一级指针，否则的话我们是不是一般情况下就动不了这个一级指针，对吧。诶，那么这样一来，是不是就可以改变这个头节点的值了？
然后呢就是函数的主体，我们可以~~肌肉记忆一样的~~去先申请一个newnode节点：

点击查看代码

Node* newnode=(Node*)malloc(sizeof(Node));
    newnode->val=val;
    newnode->index=index;
    newnode->next=NULL;

然后是逻辑部分，先上代码：
if(*head==NULL){ *head =newnode; }

就是说，如果头节点是空的，那么就直接把这个newnode装上去。

不然呢？

点击查看代码

    else{
        Node* current=*head;
        while(current->next !=NULL){
            current=current->next;
        }
        current->next =newnode;
    }

不然啊，就可以先让一个叫做current 的节点指针先指向头节点吧，然后呢就做循环让它往后走，直到走到最后吧，然后把它的后面接上这个newnode。

这样就写完了单链表的创建函数。

4.接下来个人认为排序比较好写就先写排序了

一样的，Node*current= *head; Node*p=NULL;

点击查看代码

while(current){
        p=current->next;
        while(p){
            if(current->index < p->index){
                float tempval =current->val;
                int tempindex =current->index;
                current->index=p->index;
                current->val=p->val;
                p->index=tempindex;
                p->val=tempval;
            }
            p=p->next;
        }
        current=current->next;
    }

就是你先做循环，直到这个current后面没了对吧，在循环中呢，我们让p啊一直是current后面那个（就是一个简单的冒泡排序）不断比较和交换，直到换完为止对吧。

5.最后就是（(#`皿´)个人认为最烦的部分了，本蒟蒻改了好几次这个）相加函数了

同款形参Node *Add(Node* head1,Node* head2)
同款开头
Node* result=NULL; Node* pa=head1; Node* pb=head2;
首先是一个循环，就是我们的pa和pb此时还没有到底while(pa&&pb)

加餐循环代码QAQ

点击查看代码

    while(pa&&pb){
        if(pa->index == pb->index){
            float sum=pa->val+pb->val;
            if(sum!=0){
                createList(&result,sum,pa->index);
            }
            pa=pa->next;
            pb=pb->next;
        }
        else if(pa->index > pb->index){
        createList(&result,pa->val,pa->index);
        pa=pa->next;
    }
        else{
        createList(&result,pb->val,pb->index);
        pb=pb->next;
    }
}

浅浅解释一下，就是说啊，当这个pa和pb指向的那个东西的值（就是指数）相等时呢，诶，把他们前面的系数相加吧。

如果不是0，那么就把它加到我们的result链表中，同时让pa和pb往后移吧。

（如果是0了，那也没意义对吧），然后呢，如果指数不同，那么就把大的那个加进去（因为我们刚刚排完序了，所以肯定按大小来嘛，就是跳过它嘛）

这样做完，我们的result是不是就弄完了？

当然也还没好

首先肯定是排序吧，那就来一句 sortlist(&result);

诶，这个时候有没有感觉缺什么？（•_ゝ•我也以为没缺，结果测试点爆了。???? ）

我问你，循环结束的条件是什么？
是不是a或者b其中一个跑到底了？那剩下的怎么办啊？（~~总不能放XX上卖了吧？qwq~~）

所以啊，就把剩下来的呢，一起放到result里面去吧。

点击查看代码

while (pa != NULL) {
        if (pa->val != 0) {
            createList(&result, pa->val, pa->index);
                }
        pa = pa->next;
    }
while (pb != NULL) {
        if (pb->val != 0) {
            createList(&result, pb->val, pb->index);
                }
        pb = pb->next;
    }

这样一来就完整了吧，那么主函数里再加加改改

点击查看代码

Node* result=Add(head1,head2);
    Node* current=result;
    for(int i=1;i<x&&current!=NULL;i++) 
        current=current->next;
    if (current != NULL) {
        printf("%.1f %d\n", current->val, current->index);
    }

这样一道题就AC了。

下面是完整代码

点击查看完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
    float val;
    int index;
    struct Node *next;
}Node;
void createList(Node **head,float val,int index){
    Node* newnode=(Node*)malloc(sizeof(Node));
    newnode->val=val;
    newnode->index=index;
    newnode->next=NULL;
    if(*head==NULL){
        *head =newnode;
    }
    else{
        Node* current=*head;
        while(current->next !=NULL){
            current=current->next;
        }
        current->next =newnode;
    }
}
void sortlist(Node**head){
    Node*current= *head;
    Node*p=NULL;
    while(current){
        p=current->next;
        while(p){
            if(current->index < p->index){
                float tempval =current->val;
                int tempindex =current->index;
                current->index=p->index;
                current->val=p->val;
                p->index=tempindex;
                p->val=tempval;
            }
            p=p->next;
        }
        current=current->next;
    }

}
Node *Add(Node* head1,Node* head2){
    Node* result=NULL;
    Node* pa=head1;
    Node* pb=head2;
    while(pa&&pb){
        if(pa->index == pb->index){
            float sum=pa->val+pb->val;
            if(sum!=0){
                createList(&result,sum,pa->index);
            }
            pa=pa->next;
            pb=pb->next;
        }
        else if(pa->index > pb->index){
        createList(&result,pa->val,pa->index);
        pa=pa->next;
    }
    else{
        createList(&result,pb->val,pb->index);
        pb=pb->next;
    }
}
    sortlist(&result);
while (pa != NULL) {
        if (pa->val != 0) {
            createList(&result, pa->val, pa->index);
                }
        pa = pa->next;
    }
while (pb != NULL) {
        if (pb->val != 0) {
            createList(&result, pb->val, pb->index);
                }
        pb = pb->next;
    }
return result;
}

int main(){
int n;
scanf("%d",&n);
Node *head1=NULL;
Node *head2=NULL;
for(int i=0;i<n;i++){
    float val;
    int index;
    scanf("%f %d",&val,&index);
    createList(&head1,val,index);
}
    sortlist(&head1);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        float val;
        int index;
        scanf("%f %d",&val,&index);
        createList(&head2,val,index);
    }
    sortlist(&head2);
    int x;
    scanf("%d",&x);
    Node* result=Add(head1,head2);
    Node* current=result;
    for(int i=1;i<x&&current!=NULL;i++) 
        current=current->next;
    if (current != NULL) {
        printf("%.1f %d\n", current->val, current->index);
    }
    return 0;
    }

入门数据结构的心得1(单链表篇）

就是一个很简单的用单链表实现多项式加减。????

首先当然是先用结构体定义节点

1.首先当然是先用结构体定义节点，一个多项式它既然是由额两个元素组成嘛，就是前面的系数和后面的指数，那么我们的节点自然需要开三个域对吧，所以就这样写：

这两句不用解释吧，就是定义一下，然后是输入。

就是定义两个值嘛，然后通过循环依次输入，这createlist函数呢，我等下再写，至少你要先假设有这么个函数等下用来创建单链表嘛。

接下来就是排序A，输入B，排序B.

3.然后就可以来写createlist函数了，其实就是一个创建单链表嘛；

这边是简单讲一下为什么用二级指针，理解的可以直接跳过

就是说，如果头节点是空的，那么就直接把这个newnode装上去。

不然呢？

不然啊，就可以先让一个叫做current 的节点指针先指向头节点吧，然后呢就做循环让它往后走，直到走到最后吧，然后把它的后面接上这个newnode。

这样就写完了单链表的创建函数。

4.接下来个人认为排序比较好写就先写排序了

就是你先做循环，直到这个current后面没了对吧，在循环中呢，我们让p啊一直是current后面那个（就是一个简单的冒泡排序）不断比较和交换，直到换完为止对吧。

5.最后就是（(#`皿´)个人认为最烦的部分了，本蒟蒻改了好几次这个）相加函数了

加餐循环代码QAQ

浅浅解释一下，就是说啊，当这个pa和pb指向的那个东西的值（就是指数）相等时呢，诶，把他们前面的系数相加吧。

如果不是0，那么就把它加到我们的result链表中，同时让pa和pb往后移吧。

（如果是0了，那也没意义对吧），然后呢，如果指数不同，那么就把大的那个加进去（因为我们刚刚排完序了，所以肯定按大小来嘛，就是跳过它嘛）

这样做完，我们的result是不是就弄完了？

当然也还没好

诶，这个时候有没有感觉缺什么？（•_ゝ•我也以为没缺，结果测试点爆了。???? ）

所以啊，就把剩下来的呢，一起放到result里面去吧。

这样一来就完整了吧，那么主函数里再加加改改

下面是完整代码

写在最后：(=´ω`=)这是我的第一份博客，如有错误，欢迎及时指出，仅供学习参考，仅代表本人思路和方法，如有另解，欢迎讨论

相关阅读

本类排行

相关标签

本类推荐

栏目热点

猜你喜欢

入门数据结构的心得1(单链表篇）

就是一个很简单的用单链表实现多项式加减。????

首先当然是先用结构体定义节点

1.首先当然是先用结构体定义节点，一个多项式它既然是由额两个元素组成嘛，就是前面的系数和后面的指数，那么我们的节点 自然需要开三个域对吧，所以就这样写：

这两句不用解释吧，就是定义一下，然后是输入。

就是定义两个值嘛，然后通过循环依次输入，这createlist函数呢，我等下再写，至少你要先假设有这么个函数等下用来创建单链表嘛。

接下来就是排序A，输入B，排序B.

3.然后就可以来写createlist函数了，其实就是一个创建单链表嘛；

这边是简单讲一下为什么用二级指针，理解的可以直接跳过

就是说，如果头节点是空的，那么就直接把这个newnode装上去。

不然呢？

不然啊，就可以先让一个叫做current 的节点指针先指向头节点吧，然后呢就做循环让它往后走，直到走到最后吧，然后把它的后面接上这个newnode。

这样就写完了单链表的创建函数。

4.接下来个人认为排序比较好写就先写排序了

就是你先做循环，直到这个current后面没了对吧，在循环中呢，我们让p啊一直是current后面那个（就是一个简单的冒泡排序）不断比较和交换，直到换完为止对吧。

5.最后就是（(#`皿´)个人认为最烦的部分了，本蒟蒻改了好几次这个）相加函数了

加餐循环代码QAQ

浅浅解释一下，就是说啊，当这个pa和pb指向的那个东西的值（就是指数）相等时呢，诶，把他们前面的 系数相加吧。

如果不是0，那么就把它加到我们的result链表中，同时让pa和pb往后移吧。

（如果是0了，那也没意义对吧），然后呢，如果指数不同，那么就把大的那个加进去（因为我们刚刚排完序了，所以肯定按大小来嘛，就是跳过它嘛）

这样做完，我们的result是不是就弄完了？

当然也还没好

诶，这个时候有没有感觉缺什么？（•_ゝ•我也以为没缺，结果测试点爆了。???? ）

所以啊，就把剩下来的呢，一起放到result里面去吧。

这样一来就完整了吧，那么主函数里再加加改改

下面是完整代码

写在最后：(=´ω`=)这是我的第一份博客，如有错误，欢迎及时指出，仅供学习参考，仅代表本人思路和方法，如有另解，欢迎讨论

相关阅读

本类排行

相关标签

本类推荐

栏目热点

猜你喜欢

1.首先当然是先用结构体定义节点，一个多项式它既然是由额两个元素组成嘛，就是前面的系数和后面的指数，那么我们的节点自然需要开三个域对吧，所以就这样写：

浅浅解释一下，就是说啊，当这个pa和pb指向的那个东西的值（就是指数）相等时呢，诶，把他们前面的系数相加吧。