投稿
  1. 首页
  2. python

C++链表归并排序

code•2022-4-25•python•阅读48

C++链表归并排序,第1张

说在前面：
  1. 你需要先会写数组的归并排序。
  2. 除此之外，你还要对递归的过程有很清晰的认识。
  3. 你需要会用熟练的使用指针，这是C++玩家必备技能。
  4. 代码里的List，可能命名成Node更加合适，我也不知道我当时这么想的，命了个这鼠名字，看着挺别扭的。

掌握归并排序的核心思想就行了，将大区间分解成两个小区间之后呢，双指针，把小的数值一个一个的压入新的容器（这里自然是指链表了）里面，等待两个子区间其中有一个全部压入了之后，把另外一个区间剩余的全部压入，返回。这就完成归并的基本逻辑阐述了。

归并排序对新手是很具有挑战性的，因为要用到递归还有双指针，比较难的是前者，太抽象了，所以，新手不妨用一个长度为3，为5，为7的数组先多模拟一下，想清楚该怎么做了再去做。

下面附上python代码，C玩家可以当成伪代码读，因为篇幅比较简单，精髓可能更容易get到吧！

def f(num):
    if len(num)<=1:
        return num
    l,r=f(num[:len(num)//2]),f(num[len(num)//2:])
    ans=[]
    a,b=0,0
    while a

仿照上面的逻辑，我们开始准备链表归并。

首先，我们先把链表建立好，这个没啥，

其次，把链表的补丁打好，打补丁主要还是为了仿照数组归并的思路，不然指针太能绕了头都给指晕。

主要的补丁其实就一个，就是上面python代码里面第四行，递归分解的那一部分，我在类里面写了个split方法，该方法能够在给定位置切上一刀，使原来的链表切断，并且返回将后半部分构成新的链表返回。

List *getKthNode(int position) {//返回position位置的指针，方便我分割链表。
        List *p = head.next;
        while (position--) {
            p = p->next;
        }
        return p;
    }

    mylist split(int from) {//这个函数我用来分割原来的链表，list[:from]，list[from:]
        //同时把原来的链表卡断，返回后半部分
        List *ends = NULL;
        int count = 0;
        List *p = &head;
        for (int i = from; i > 0; --i) {
            p = p->next;
        }//定位分割点之前的那个点位
        mylist ret;
        List newHead = List{0, getKthNode(from)};
        ret = mylist(newHead);
        p->next = NULL;
        length = from;
        return ret;
    }

这里还需要借助getKthNode方法的帮助，算是个小补丁吧，帮忙找到第position个结点（本链表有头结点，头结点是哨兵节点，帮助写代码用的，没实际作用，还有一种是没有头结点的链表写法，每一个节点都是真实且有意义的，不做赘述）。

完成了split方法，再然后就可以直接写归并了，（代码太乱了，命名也不规范，见谅）：

mylist mylistMergeSort(mylist x) {
    if (x.length == 1) {
        return x;
    }
    mylist r = x.split(x.length / 2);
    mylist l = x;
    mylist rpart = mylistMergeSort(r);
    mylist lpart = mylistMergeSort(l);
    List *p1 = rpart.head.next;
    List *p2 = lpart.head.next;
    List *p3 = new List;
    List *p4 = p3;
    while (p1 and p2) {
        if (p1->val <= p2->val) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }
    while (p1) {
        p3->next = p1;
        p1 = p1->next;
        p3 = p3->next;
    }
    while (p2) {
        p3->next = p2;
        p2 = p2->next;
        p3 = p3->next;
    }
    List ans = {0, p4->next};
    return mylist(ans);
}

为了方便和python数组归并对照，加深理解，我再发一遍python:

def f(num):
    if len(num)<=1:
        return num
    l,r=f(num[:len(num)//2]),f(num[len(num)//2:])
    ans=[]
    a,b=0,0
    while a

大致就这么多，细细品吧，码友，下一个帖子，祝你好运。

全部代码： 头文件： 
//
// Created by chen on 2022/4/20.
//

#ifndef STANDARDLIST_MYLIST_H
#define STANDARDLIST_MYLIST_H

#endif //STANDARDLIST_MYLIST_H

#include 
#include 

using namespace std;
struct List {
    int val;
    List *next;
};

class mylist {
public:
    List head;
    int length;

    mylist(mylist const &t) {//引用
        head = t.head;
        length = t.length;
    }

    mylist(List givedHead) {//根据头结点构造链表，为了写归并，做个铺垫（其实不写也可以，灵活点总归是好的）
        head = givedHead;
        List *p = &head;
        length = 0;
        while (p->next != NULL) {
            length++;
            p = p->next;
        }
    }

    mylist() {
        List pnode;
        head = pnode;
        head.next = NULL;
        length = 0;
    }

    void insert(int val, int position = -1) {
        if (position == -1) {
            position = length;//不写append方法了，如果不填写position就默认是append。
        }
        List *p = &head;
        while (position--) {
            p = p->next;//找到目标位置的前一个点，head节点作为哨兵}
        }
        List *mem = p->next;//head->0->1->2 要在0号位置插入元素，需要记住0这个位置当前的节点
        /*错的List newData = {val, mem};
        p->next = &newData;*/
        List *t = new List{val, mem};
        p->next = t;
        length++;
    }

    void deleteNode(int position) {
        List *p = &head;
        while (position--) {
            p = p->next;
        }
        List *mem = p->next;
        p->next = p->next->next;
        free(mem);
        length--;
    }

    List *getKthNode(int position) {//返回position位置的指针，方便我分割链表。
        List *p = head.next;
        while (position--) {
            p = p->next;
        }
        return p;
    }

    mylist split(int from) {//这个函数我用来分割原来的链表，list[:from]，list[from:]
        //同时把原来的链表卡断，返回后半部分
        List *ends = NULL;
        int count = 0;
        List *p = &head;
        for (int i = from; i > 0; --i) {
            p = p->next;
        }//定位分割点之前的那个点位
        mylist ret;
        List newHead = List{0, getKthNode(from)};
        ret = mylist(newHead);
        p->next = NULL;
        length = from;
        return ret;
    }

    void print() {
        List *p = head.next;
        while (p) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }

};

mylist mylistMergeSort(mylist x) {
    if (x.length == 1) {
        return x;
    }
    mylist r = x.split(x.length / 2);
    mylist l = x;
    mylist rpart = mylistMergeSort(r);
    mylist lpart = mylistMergeSort(l);
    List *p1 = rpart.head.next;
    List *p2 = lpart.head.next;
    List *p3 = new List;
    List *p4 = p3;
    while (p1 and p2) {
        if (p1->val <= p2->val) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }
    while (p1) {
        p3->next = p1;
        p1 = p1->next;
        p3 = p3->next;
    }
    while (p2) {
        p3->next = p2;
        p2 = p2->next;
        p3 = p3->next;
    }
    List ans = {0, p4->next};
    return mylist(ans);
}
源文件: 
#include 
#include "mylist.h"

using namespace std;

int main() {
    mylist ml = mylist();
    for (int i = 0; i < 10; i++) {
        if (ml.length) {
            int x = rand() % (ml.length + 1);
            ml.insert(i, x);

            cout << i << " 插入位置是" << x << "  ";
        } else {
            ml.insert(i);
            cout << i << " 插入位置是" << 0 << "  ";
        }
        ml.print();
    }
    cout << "排序前：";
    ml.print();
    cout << "排序后：";
    mylistMergeSort(ml).print();
    //注意，本排序之后ml值会发生变化，还要再定义一个链表存储下，有点不足。
    //example:
    //0 插入位置是0  0
    //1 插入位置是1  0 1
    //2 插入位置是1  0 2 1
    //3 插入位置是1  0 3 2 1
    //4 插入位置是3  0 3 2 4 1
    //5 插入位置是4  0 3 2 4 5 1
    //6 插入位置是6  0 3 2 4 5 1 6
    //7 插入位置是0  7 0 3 2 4 5 1 6
    //8 插入位置是8  7 0 3 2 4 5 1 6 8
    //9 插入位置是3  7 0 3 9 2 4 5 1 6 8
    //排序前：7 0 3 9 2 4 5 1 6 8
    //排序后：0 1 2 3 4 5 6 7 8 9
    return 0;
}

本人能力有限，代码中或许会存在部分bug，没有测出来，所以到时候发现了还请多多关照本新手

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/718789.html

赞 (0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
codecode管理员组
00
上一篇 2022-04-25
下一篇2022-04-25

发表评论

登录后才能评论

评论列表（0条）

    Copyright © 2022 内存溢出 版权所有 蜀ICP备2023005044号 Powered by outofmemory.cn

    保存