C++中怎么實(shí)現(xiàn)鏈表的排序算法-創(chuàng)新互聯(lián)

本篇內(nèi)容主要講解“C++中怎么實(shí)現(xiàn)鏈表的排序算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“C++中怎么實(shí)現(xiàn)鏈表的排序算法”吧!

成都創(chuàng)新互聯(lián)自成立以來，一直致力于為企業(yè)提供從網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、做網(wǎng)站、網(wǎng)站設(shè)計(jì)、電子商務(wù)、網(wǎng)站推廣、網(wǎng)站優(yōu)化到為企業(yè)提供個(gè)性化軟件開發(fā)等基于互聯(lián)網(wǎng)的全面整合營(yíng)銷服務(wù)。公司擁有豐富的網(wǎng)站建設(shè)和互聯(lián)網(wǎng)應(yīng)用系統(tǒng)開發(fā)管理經(jīng)驗(yàn)、成熟的應(yīng)用系統(tǒng)解決方案、優(yōu)秀的網(wǎng)站開發(fā)工程師團(tuán)隊(duì)及專業(yè)的網(wǎng)站設(shè)計(jì)師團(tuán)隊(duì)。

一、鏈表排序

最簡(jiǎn)單、直接的方式（直接采用冒泡或者選擇排序，而且不是交換結(jié)點(diǎn)，只交換數(shù)據(jù)域）

//線性表的排序,采用冒泡排序,直接遍歷鏈表
void Listsort(Node* & head) {
    int i = 0;
    int j = 0;
    //用于變量鏈表
    Node * L = head;
    //作為一個(gè)臨時(shí)量
    Node * p;
    Node * p1;
    //如果鏈表為空直接返回
    if (head->value == 0)return;

    for (i = 0; i < head->value - 1; i++) {
        L = head->next;
        for (j = 0; j < head->value - i - 1; j++) {
            //得到兩個(gè)值
            p = L;
            p1 = L->next;
            //如果前面的那個(gè)比后面的那個(gè)大，就交換它們之間的是數(shù)據(jù)域
            if (p->value > p1->value) {
                Elemtype temp = p->value;
                p->value = p1->value;
                p1->value = temp;
            }
            L = L->next;
        }
    }
}

因?yàn)榕判蛑兴俣缺容^快的如快速排序是要求它們的數(shù)據(jù)域的地址是相連接的，它比較適合于順序結(jié)構(gòu)，而鏈?zhǔn)浇Y(jié)構(gòu)的時(shí)候，我們就只有使用只會(huì)進(jìn)行前后兩個(gè)比較多排序算法，比如冒泡排序等。我們這里是沒有交換結(jié)點(diǎn)的一種排序方式，這種方式簡(jiǎn)單，明了，這樣就是數(shù)組排序的時(shí)候是一樣的。后面我會(huì)寫通過交換結(jié)點(diǎn)的方式的排序。

下面我們就討論討論這個(gè)排序算法的時(shí)間復(fù)雜度了，因?yàn)樗鞘褂妹芭菖判虻?，它的時(shí)間只要消耗在那兩重循環(huán)，所以時(shí)間復(fù)雜度為：O(n*n),這個(gè)效率實(shí)在是太低，下面我們對(duì)這個(gè)想(ˇ?ˇ) 想～通過另外一種方式來實(shí)現(xiàn)鏈表的排序

二、另外一種鏈表排序方式

我們?cè)谟懻撆判蛩惴ǖ臅r(shí)候，都是把數(shù)據(jù)存放在數(shù)組中進(jìn)行討論的，在順序結(jié)構(gòu)下，我們可以采取很多高效的排序算法，那么這個(gè)就是我們另外一種對(duì)鏈表排序的方式，先把鏈表的內(nèi)容存放到數(shù)組中（時(shí)間為O(n)），然后，我們?cè)趯?duì)那個(gè)數(shù)組進(jìn)行排序（最快為nlog(n)），最后，存放鏈表中（時(shí)間為O(n)）。通過計(jì)算，我們可以得到它的時(shí)間復(fù)雜為（O(nlogn)）,這個(gè)速度已經(jīng)和順序結(jié)構(gòu)下差不多了，可以接受

void Listsort_1(Node* & head) {
    int i = 0;
    int j = 0;
    //用于變量鏈表
    Node * L = head;
    //如果鏈表為空直接返回
    if (head->value == 0)return;
    Elemtype * copy = new Elemtype[head->value];
    //變量鏈表，存放數(shù)組
    for (i = 0; i < head->value; i++) {
        L = L->next;
        copy[i] = L->value;
    }
    //調(diào)用STL中的sort函數(shù)
    sort(copy, copy + head->value);
    L = head;
    //存放回鏈表中
    for (i = 0; i < head->value; i++) {
        L = L->next;
          L->value= copy[i];
    }
}

三、比較兩種排序的效率

C++中怎么實(shí)現(xiàn)鏈表的排序算法

如圖所示，在數(shù)據(jù)量為10000的時(shí)候，明顯第二種排序算法消耗的時(shí)間比第一種快了28倍左右。

四、下面通過交換結(jié)點(diǎn)實(shí)現(xiàn)鏈表的排序

首先我們編寫交換結(jié)點(diǎn)的函數(shù)，結(jié)點(diǎn)的交換主要就是考慮結(jié)點(diǎn)的指針域的問題，其中相鄰兩個(gè)結(jié)點(diǎn)是一種特殊的情況，要拿出來特別考慮。我們先畫出結(jié)點(diǎn)交換的思路圖，如下圖

首先我們給出相鄰兩個(gè)結(jié)點(diǎn)交換的思路：

C++中怎么實(shí)現(xiàn)鏈表的排序算法

下面是普通情況下的交換如下圖

C++中怎么實(shí)現(xiàn)鏈表的排序算法

//參數(shù)為頭結(jié)點(diǎn)和需要交換的兩個(gè)結(jié)點(diǎn)的位置（起點(diǎn)為1）
void swap_node(Node * & head,int i,int j) {
    //位置不合法
    if (i<1 || j<1 || i>head->value || j >head->value) {
        cout << "請(qǐng)檢查位置是否合法" << endl;
        return;
    }
    //同一個(gè)位置不用交換
    if (i == j)
    {
        return;
    }
    //相鄰兩個(gè)交換比較簡(jiǎn)單
    if (abs(i - j) == 1) {
        //位置靠前的那個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
        Node * pre;
        if (i < j)
            pre = getitem(head, i);
        else
            pre = getitem(head, j);

        //保存第一個(gè)結(jié)點(diǎn)
        Node * a = pre->next;
        //保存第二結(jié)點(diǎn)
        Node * b = a->next;
        //改變pre下一個(gè)結(jié)點(diǎn)的值
        pre->next = b;
        //必須先把b的下一個(gè)結(jié)點(diǎn)值給a先
        a->next = b->next;
        //讓b的下一個(gè)結(jié)點(diǎn)等于a
        b->next = a;
        return;
    }

    //第一個(gè)結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)
    Node * a = getitem(head, i);
    //第二個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
    Node * b = getitem(head, j);
    //第一個(gè)結(jié)點(diǎn)
    Node * p = a->next;
    //第二個(gè)結(jié)點(diǎn)
    Node * q = b->next;
    //第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    Node * p_next = p->next;
    //第二結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    Node * q_next = q->next;

    //a的下一個(gè)結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)q
    a->next = q;
    //第二結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    q->next = p_next;
    //b的下一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)p
    b->next = p;
    //第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    p->next = q_next;

}

排序時(shí)候的代碼，切記交換結(jié)點(diǎn)都是前后結(jié)點(diǎn)交換，所以交換完成后，L就已經(jīng)被移動(dòng)到下一個(gè)結(jié)點(diǎn)了，故不要再執(zhí)行：L=L->next

//線性表的排序，交換結(jié)點(diǎn)
void Listsort_Node(Node* & head) {
    int i = 0;
    int j = 0;
    //用于變量鏈表
    Node * L = head;
    //作為一個(gè)臨時(shí)量
    Node * p;
    Node * p1;
    //如果鏈表為空直接返回
    if (head->value == 0)return;
    int flag = 0;
    cout << head->value << endl;
    for (i = 0; i < head->value - 1; i++) {
        L = head->next;
        for (j = 0; j < head->value - 1 - i; j++) {
            //如果我們交換了結(jié)點(diǎn)，那么我們就已經(jīng)在交換結(jié)點(diǎn)的時(shí)候，把L移動(dòng)到下一個(gè)結(jié)點(diǎn)了，所以不要
            //再執(zhí)行：L = L->next;，否則會(huì)報(bào)錯(cuò)的
            if (L->value > L->next->value) {
                flag = 1;
                swap_node(head, j + 1, j + 2);

            }
            if (flag == 1) {
                flag = 0;
            }
            else {
                L = L->next;
            }

        }   
    }
}

好了，今天的就寫到這里了，今天通過寫交換結(jié)點(diǎn)，發(fā)現(xiàn)鏈表真的很容易忽悠人，我就被忽悠了一個(gè)小時(shí)，才知道那個(gè)結(jié)點(diǎn)已經(jīng)被移動(dòng)到下一個(gè)結(jié)點(diǎn)了。

最后，補(bǔ)充一個(gè)實(shí)現(xiàn)鏈表反轉(zhuǎn)的好方法（感覺你在頭文件里面計(jì)算一下鏈表的長(zhǎng)度可以帶來很多遍歷的）

void rollback(Node * & head) {
    //先知道了最后一個(gè)元素和第一個(gè)元素的位置
    int end = head->value;
    int start = 1;
    //兩邊同時(shí)開工
    //進(jìn)行調(diào)換
    while (1) {
        if (end == start)
            return;
        swap_node(head, end, start);
        --end;
        ++start;
    }
}

希望大家，對(duì)我寫的代碼做出一些評(píng)價(jià)。我想想還是直接貼個(gè)完成的代碼出來好了，調(diào)轉(zhuǎn)代碼也在里面了

include<iostream>
#include<ctime>
#include<cstdlib>
#include<windows.h>
#include<algorithm>
using namespace std;
typedef int Elemtype;

//鏈?zhǔn)浇Y(jié)構(gòu)，我們打算在鏈表中添加一個(gè)
//保存長(zhǎng)度的頭結(jié)點(diǎn)，加入這個(gè)結(jié)點(diǎn)可以方便我們對(duì)結(jié)點(diǎn)做一些
//基本的操作，結(jié)點(diǎn)保存的是線性表的長(zhǎng)度
struct Node
{
    //結(jié)點(diǎn)的值,如果是頭結(jié)點(diǎn)，保存是鏈表的長(zhǎng)度
    Elemtype value;
    //下一個(gè)結(jié)點(diǎn)的地址
    Node * next;

};

//創(chuàng)建一個(gè)空鏈表，每個(gè)頭結(jié)點(diǎn)就代表一個(gè)鏈表
void InitList(Node * & head) {
    head = new Node();
    head->value = 0;
    head->next = NULL;
}
//銷毀一個(gè)鏈表
void DestroyList(Node * & head) {
    delete head;
    head = NULL;
}

//清空整個(gè)列表
void ClearList(Node * & head) {
    head->value = 0;
    head->next = NULL;
}

//插入函數(shù)
bool Listinsert(Node * & head, int i, Elemtype value) {

    //插入到前面的方法
    int j = 0;
    Node * L = head;
    //如果插入的位置不合法，直接返回錯(cuò)誤提示
    if (i<1 || i>head->value + 1)return false;

    //得到插入位置的前一個(gè)結(jié)點(diǎn)
    while (j < i - 1) {
        L = L->next;
        ++j;
    }

    //s是一個(gè)臨時(shí)結(jié)點(diǎn)
    Node * s = new Node();
    s->value = value;    //先對(duì)臨時(shí)結(jié)點(diǎn)賦值
    s->next = L->next;   //讓臨時(shí)結(jié)點(diǎn)下一個(gè)位置指向當(dāng)前需要插入前一個(gè)結(jié)點(diǎn)的下一個(gè)位置
    L->next = s;          //讓前一個(gè)結(jié)點(diǎn)下一個(gè)位置指向臨時(shí)結(jié)點(diǎn)，完成
                          //線性表的長(zhǎng)度加一
    ++head->value;
    return true;
}
//得到某個(gè)位置上的值
Node * getitem(Node * & head, int i) {
    //我們要求程序返回特定位置上的值
    //我們一樣是從頭結(jié)點(diǎn)開始尋找該位置
    int j = 0;
    Node * L = head;
    //想要的那個(gè)位置是否合法
    if (i<1 || i >head->value)return NULL;

    //同樣是先得到前一個(gè)結(jié)點(diǎn)
    while (j < i - 1) {
        L = L->next;
        ++j;
    }
    //value = L->next->value;
    return L;
}
//線性表的排序,采用冒泡排序,直接遍歷鏈表
void Listsort(Node* & head) {
    int i = 0;
    int j = 0;
    //用于變量鏈表
    Node * L = head;
    //作為一個(gè)臨時(shí)量
    Node * p;
    Node * p1;
    //如果鏈表為空直接返回
    if (head->value == 0)return;

    for (i = 0; i < head->value - 1; i++) {
        L = head->next;
        for (j = 0; j < head->value - i - 1; j++) {
            //得到兩個(gè)值
            p = L;
            p1 = L->next;
            //如果前面的那個(gè)比后面的那個(gè)大，就交換它們之間的是數(shù)據(jù)域
            if (p->value > p1->value) {
                Elemtype temp = p->value;
                p->value = p1->value;
                p1->value = temp;
            }
            L = L->next;
        }
    }
}
//通過數(shù)組來完成我的排序
void Listsort_by_array(Node* & head) {
    int i = 0;
    int j = 0;
    //用于變量鏈表
    Node * L = head;
    //如果鏈表為空直接返回
    if (head->value == 0)return;
    Elemtype * copy = new Elemtype[head->value];
    //變量鏈表，存放數(shù)組
    for (i = 0; i < head->value; i++) {
        L = L->next;
        copy[i] = L->value;
    }
    //調(diào)用STL中的sort函數(shù)
    sort(copy, copy + head->value);
    L = head;
    //存放回鏈表中
    for (i = 0; i < head->value; i++) {
        L = L->next;
        L->value = copy[i];
    }
}

//參數(shù)為頭結(jié)點(diǎn)和需要交換的兩個(gè)結(jié)點(diǎn)的位置（起點(diǎn)為1）
void swap_node(Node * & head,int i,int j) {
    //位置不合法
    if (i<1 || j<1 || i>head->value || j >head->value) {
        cout << "請(qǐng)檢查位置是否合法" << endl;
        return;
    }
    //同一個(gè)位置不用交換
    if (i == j)
    {
        return;
    }
    //相鄰兩個(gè)交換比較簡(jiǎn)單
    if (abs(i - j) == 1) {
        //位置靠前的那個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
        Node * pre;
        if (i < j)
            pre = getitem(head, i);
        else
            pre = getitem(head, j);

        //保存第一個(gè)結(jié)點(diǎn)
        Node * a = pre->next;
        //保存第二結(jié)點(diǎn)
        Node * b = a->next;
        //改變pre下一個(gè)結(jié)點(diǎn)的值
        pre->next = b;
        //必須先把b的下一個(gè)結(jié)點(diǎn)值給a先
        a->next = b->next;
        //讓b的下一個(gè)結(jié)點(diǎn)等于a
        b->next = a;
        return;
    }

    //第一個(gè)結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)
    Node * a = getitem(head, i);
    //第二個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
    Node * b = getitem(head, j);
    //第一個(gè)結(jié)點(diǎn)
    Node * p = a->next;
    //第二個(gè)結(jié)點(diǎn)
    Node * q = b->next;
    //第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    Node * p_next = p->next;
    //第二結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    Node * q_next = q->next;

    //a的下一個(gè)結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)q
    a->next = q;
    //第二結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    q->next = p_next;
    //b的下一個(gè)結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)p
    b->next = p;
    //第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向第二個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    p->next = q_next;

}
//反轉(zhuǎn)
void rollback(Node * & head) {
    //先知道了最后一個(gè)元素和第一個(gè)元素的位置
    int end = head->value;
    int start = 1;
    //兩邊同時(shí)開工
    //進(jìn)行調(diào)換
    while (1) {
        if (end <= start)
            return;
        swap_node(head, end, start);
        --end;
        ++start;
    }
}
void print(Node * & head);
//線性表的排序,采用冒泡排序,直接遍歷鏈表
//線性表的排序，交換結(jié)點(diǎn)
void Listsort_node(Node* & head) {
    int i = 0;
    int j = 0;
    //用于變量鏈表
    Node * L = head;
    //作為一個(gè)臨時(shí)量
    Node * p;
    Node * p1;
    //如果鏈表為空直接返回
    if (head->value == 0)return;
    int flag = 0;

    for (i = 0; i < head->value - 1; i++) {
        L = head->next;
        for (j = 0; j < head->value - 1 - i; j++) {
            //如果我們交換了結(jié)點(diǎn)，那么我們就已經(jīng)在交換結(jié)點(diǎn)的時(shí)候，把L移動(dòng)到下一個(gè)結(jié)點(diǎn)了，所以不要
            //再執(zhí)行：L = L->next;，否則會(huì)報(bào)錯(cuò)的
            if (L->value > L->next->value) {
                flag = 1;
                swap_node(head, j + 1, j + 2);

            }
            if (flag == 1) {
                flag = 0;
            }
            else {
                L = L->next;
            }

        }   
    }
}

void print(Node * & head) {
    //輸出我們只需要傳入頭結(jié)點(diǎn)，然后循環(huán)判斷當(dāng)前結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)是否為空，
    //這樣就可以輸出所有內(nèi)容
    Node * L = head;
    while (L->next) {
        L = L->next;
        cout << L->value << " ";
    }
    cout << endl;
}
int main() {
    //鏈表的頭結(jié)點(diǎn)，不存放任何值，首先初始化頭結(jié)點(diǎn)
    Node * head;

    Node * head_array;
    Node * head_node;
    Node * head_roll;
    srand((int)time(NULL));     //每次執(zhí)行種子不同，生成不同的隨機(jī)數(shù)
    //創(chuàng)建一個(gè)鏈表

    InitList(head); 
    InitList(head_array);
    InitList(head_node);
    InitList(head_roll);

    int i;
    cout << "請(qǐng)輸入需要插入元素個(gè)數(shù)" << endl;
    int n;
    cin >> n;//5
    //cout << "請(qǐng)輸入" << n << "個(gè)值" << endl;
    for (i = 0; i < n; i++) {
        Elemtype temp;
        temp = rand();
        if (!Listinsert(head, i + 1, temp)) {
            cout << "插入元素失敗" << endl;
        }
        if (!Listinsert(head_array, i + 1, temp)) {
            cout << "插入元素失敗" << endl;
        }
        if (!Listinsert(head_node, i + 1, temp)) {
            cout << "插入元素失敗" << endl;
        }
        if (!Listinsert(head_roll, i + 1, temp)) {
            cout << "插入元素失敗" << endl;
        }

    }
    cout << "初始化結(jié)果" << endl;
    print(head);
    cout << "反轉(zhuǎn)結(jié)果" << endl;
    rollback(head_roll);
    print(head_roll);
    cout << "冒泡排序（數(shù)據(jù)域交換）" << endl;
    Listsort(head);
    print(head);
    cout << "借數(shù)組為媒介進(jìn)行排序（數(shù)據(jù)域交換）" << endl;
    Listsort_by_array(head_array);
    print(head_array);
    cout << "冒泡排序（結(jié)點(diǎn)交換）" << endl;
    Listsort_node(head_node);
    print(head_node);
    system("pause");
    return 0;

}

運(yùn)行環(huán)境：vs2015

輸出結(jié)果：

C++中怎么實(shí)現(xiàn)鏈表的排序算法

到此，相信大家對(duì)“C++中怎么實(shí)現(xiàn)鏈表的排序算法”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)建站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

網(wǎng)站欄目：C++中怎么實(shí)現(xiàn)鏈表的排序算法-創(chuàng)新互聯(lián)
本文路徑：http://muchs.cn/article34/djidpe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、用戶體驗(yàn)、做網(wǎng)站、網(wǎng)站內(nèi)鏈、云服務(wù)器、商城網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

C++中怎么實(shí)現(xiàn)鏈表的排序算法-創(chuàng)新互聯(lián)

一、鏈表排序

二、另外一種鏈表排序方式

三、比較兩種排序的效率

四、下面通過交換結(jié)點(diǎn)實(shí)現(xiàn)鏈表的排序

一、鏈表排序

二、另外一種鏈表排序方式

三、比較兩種排序的效率