链表的二路归并 求大神发完整的代码!!不会写啊!

题目:设有n个待排序元素存放在一个不带表头结点的单链表中, 每个链表结点只存放一个元素, 头指针为r。试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。

c

3个回答

代码稍微有点长:

 // teste0100.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"


template<typename T>
class List
{
private:
    struct Node
    {
        T data;
        Node* next;
        Node(const T& t=T()):data(t)
        {next=NULL;}
    };
    Node* head;
    Node* getPointer(int pos)
    {
        Node* p=head;
        for(int i=0;i<pos;i++)
            p=p->next;
        return p;
    }
public:
    List():head(NULL){};
    void clear()
    {
        while(head!=NULL)
        {
            Node* p = head->next;
            delete head;
            head = p;
        }
    }
    ~List()
    {
        clear();
    }
    void insert_front(const T& t)
    {
        Node* p = new Node(t);
        p->next = head;
        head = p;
    }
    void travel()
    {
        Node* p = head;
        while(p!=NULL)
        {
            cout<<p->data<<' ';
            p = p->next;
        }
        cout << endl;
    }

    void insert_back(const T& t)
    {
        Node* p = new Node(t);
        if(head == 0)
            head = p;
        else
        {
            getPointer(size()-1) -> next = p;
        }
    }
    int size()
    {
        int cnt = 0;
        Node* p = head;
        while(p != NULL)
        {
            cnt++;
            p = p->next;
        }
        return cnt;
    }
    T getHead()
    {
        if(head == NULL)
            throw "No Head";
        return head->data;
    }
    T getTail()
    {
        if(head == NULL)
            throw "No Tail";
        Node* p = head;
        while(p->next != NULL)
        {
            p = p->next;
        }
        return p->data;
    }
    bool empty()
    {
        return head==NULL;
    }
    int find(const T& t)
    {
        int pos = 0;
        Node* p = head;
        while(p!=NULL)
        {
            if(p->data == t)
                return pos;
            pos++;
            p = p->next;
        }
        return -1;
    }
    bool updata(const T& o, const T& n)
    {
        int pos = find(o);
        if(pos == -1)
            return false;
        Node* p = getPointer(pos);
        p->data = n;
        return true;
    }

    bool erase(const T& t)
    {
        int pos = find(t);
        if(pos == -1)
            return false;
        if(pos == 0)
        {
            Node* p = head->next;
            delete head;
            head = p;
        }
        else
        {
            Node* pre = getPointer(pos-1);
            Node* cur = pre->next;
            pre->next = cur->next;
            delete cur;
        }
        return true;
    }
};

最近刚写过一篇博客,不过是基于C++的,供你参考:http://blog.csdn.net/cxsmarkchan/article/details/50850499
代码在这里:https://github.com/cxsmarkchan/mySTL/blob/master/lib/list_impl.h
里面的stable_sort函数就是二路归并。
都是个人的理解,希望对你有帮助。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐