详解C++实现链表的排序算法

一、链表排序

最简单、直接的方式(直接采用冒泡或者选择排序,而且不是交换结点,只交换数据域)

//线性表的排序,采用冒泡排序,直接遍历链表
void Listsort(Node* & head) {
    int i = 0;
    int j = 0;
    //用于变量链表
    Node * L = head;
    //作为一个临时量
    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++) {
            //得到两个值
            p = L;
            p1 = L->next;
            //如果前面的那个比后面的那个大,就交换它们之间的是数据域
            if (p->value > p1->value) {
                Elemtype temp = p->value;
                p->value = p1->value;
                p1->value = temp;
            }
            L = L->next;
        }
    }
}

因为排序中速度比较快的如快速排序是要求它们的数据域的地址是相连接的,它比较适合于顺序结构,而链式结构的时候,我们就只有使用只会进行前后两个比较多排序算法,比如冒泡排序等。我们这里是没有交换结点的一种排序方式,这种方式简单,明了,这样就是数组排序的时候是一样的。后面我会写通过交换结点的方式的排序。

下面我们就讨论讨论这个排序算法的时间复杂度了,因为它是使用冒泡排序的,它的时间只要消耗在那两重循环,所以时间复杂度为:O(n*n),这个效率实在是太低,下面我们对这个想(ˇˍˇ) 想~通过另外一种方式来实现链表的排序

二、另外一种链表排序方式

我们在讨论排序算法的时候,都是把数据存放在数组中进行讨论的,在顺序结构下,我们可以采取很多高效的排序算法,那么这个就是我们另外一种对链表排序的方式,先把链表的内容存放到数组中(时间为O(n)),然后,我们在对那个数组进行排序(最快为nlog(n)),最后,存放链表中(时间为O(n))。通过计算,我们可以得到它的时间复杂为(O(nlogn)),这个速度已经和顺序结构下差不多了,可以接受

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];
    //变量链表,存放数组
    for (i = 0; i < head->value; i++) {
        L = L->next;
        copy[i] = L->value;
    }
    //调用STL中的sort函数
    sort(copy, copy + head->value);
    L = head;
    //存放回链表中
    for (i = 0; i < head->value; i++) {
        L = L->next;
          L->value= copy[i];
    }
}

三、比较两种排序的效率

如图所示,在数据量为10000的时候,明显第二种排序算法消耗的时间比第一种快了28倍左右。

四、下面通过交换结点实现链表的排序

首先我们编写交换结点的函数,结点的交换主要就是考虑结点的指针域的问题,其中相邻两个结点是一种特殊的情况,要拿出来特别考虑。我们先画出结点交换的思路图,如下图

首先我们给出相邻两个结点交换的思路:

下面是普通情况下的交换如下图

//参数为头结点和需要交换的两个结点的位置(起点为1)
void swap_node(Node * & head,int i,int j) {
    //位置不合法
    if (i<1 || j<1 || i>head->value || j >head->value) {
        cout << "请检查位置是否合法" << endl;
        return;
    }
    //同一个位置不用交换
    if (i == j)
    {
        return;
    }
    //相邻两个交换比较简单
    if (abs(i - j) == 1) {
        //位置靠前的那个结点的前一个结点
        Node * pre;
        if (i < j)
            pre = getitem(head, i);
        else
            pre = getitem(head, j);

        //保存第一个结点
        Node * a = pre->next;
        //保存第二结点
        Node * b = a->next;
        //改变pre下一个结点的值
        pre->next = b;
        //必须先把b的下一个结点值给a先
        a->next = b->next;
        //让b的下一个结点等于a
        b->next = a;
        return;
    }

    //第一个结点前一个结点
    Node * a = getitem(head, i);
    //第二个结点的前一个结点
    Node * b = getitem(head, j);
    //第一个结点
    Node * p = a->next;
    //第二个结点
    Node * q = b->next;
    //第一个结点的下一个结点
    Node * p_next = p->next;
    //第二结点的下一个结点
    Node * q_next = q->next;

    //a的下一个结点指向第二个结点q
    a->next = q;
    //第二结点的下一个结点指向第一个结点的下一个结点
    q->next = p_next;
    //b的下一个结点指向第一个结点p
    b->next = p;
    //第一个结点的下一个结点指向第二个结点的下一个结点
    p->next = q_next;

}

排序时候的代码,切记交换结点都是前后结点交换,所以交换完成后,L就已经被移动到下一个结点了,故不要再执行:L=L->next

//线性表的排序,交换结点
void Listsort_Node(Node* & head) {
    int i = 0;
    int j = 0;
    //用于变量链表
    Node * L = head;
    //作为一个临时量
    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++) {
            //如果我们交换了结点,那么我们就已经在交换结点的时候,把L移动到下一个结点了,所以不要
            //再执行:L = L->next;,否则会报错的
            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 rollback(Node * & head) {
    //先知道了最后一个元素和第一个元素的位置
    int end = head->value;
    int start = 1;
    //两边同时开工
    //进行调换
    while (1) {
        if (end == start)
            return;
        swap_node(head, end, start);
        --end;
        ++start;
    }
}

希望大家,对我写的代码做出一些评价。我想想还是直接贴个完成的代码出来好了,调转代码也在里面了

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

//链式结构,我们打算在链表中添加一个
//保存长度的头结点,加入这个结点可以方便我们对结点做一些
//基本的操作,结点保存的是线性表的长度
struct Node
{
    //结点的值,如果是头结点,保存是链表的长度
    Elemtype value;
    //下一个结点的地址
    Node * next;

};

//创建一个空链表,每个头结点就代表一个链表
void InitList(Node * & head) {
    head = new Node();
    head->value = 0;
    head->next = NULL;
}
//销毁一个链表
void DestroyList(Node * & head) {
    delete head;
    head = NULL;
}

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

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

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

    //得到插入位置的前一个结点
    while (j < i - 1) {
        L = L->next;
        ++j;
    }

    //s是一个临时结点
    Node * s = new Node();
    s->value = value;    //先对临时结点赋值
    s->next = L->next;   //让临时结点下一个位置指向当前需要插入前一个结点的下一个位置
    L->next = s;          //让前一个结点下一个位置指向临时结点,完成
                          //线性表的长度加一
    ++head->value;
    return true;
}
//得到某个位置上的值
Node * getitem(Node * & head, int i) {
    //我们要求程序返回特定位置上的值
    //我们一样是从头结点开始寻找该位置
    int j = 0;
    Node * L = head;
    //想要的那个位置是否合法
    if (i<1 || i >head->value)return NULL;

    //同样是先得到前一个结点
    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;
    //作为一个临时量
    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++) {
            //得到两个值
            p = L;
            p1 = L->next;
            //如果前面的那个比后面的那个大,就交换它们之间的是数据域
            if (p->value > p1->value) {
                Elemtype temp = p->value;
                p->value = p1->value;
                p1->value = temp;
            }
            L = L->next;
        }
    }
}
//通过数组来完成我的排序
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];
    //变量链表,存放数组
    for (i = 0; i < head->value; i++) {
        L = L->next;
        copy[i] = L->value;
    }
    //调用STL中的sort函数
    sort(copy, copy + head->value);
    L = head;
    //存放回链表中
    for (i = 0; i < head->value; i++) {
        L = L->next;
        L->value = copy[i];
    }
}

//参数为头结点和需要交换的两个结点的位置(起点为1)
void swap_node(Node * & head,int i,int j) {
    //位置不合法
    if (i<1 || j<1 || i>head->value || j >head->value) {
        cout << "请检查位置是否合法" << endl;
        return;
    }
    //同一个位置不用交换
    if (i == j)
    {
        return;
    }
    //相邻两个交换比较简单
    if (abs(i - j) == 1) {
        //位置靠前的那个结点的前一个结点
        Node * pre;
        if (i < j)
            pre = getitem(head, i);
        else
            pre = getitem(head, j);

        //保存第一个结点
        Node * a = pre->next;
        //保存第二结点
        Node * b = a->next;
        //改变pre下一个结点的值
        pre->next = b;
        //必须先把b的下一个结点值给a先
        a->next = b->next;
        //让b的下一个结点等于a
        b->next = a;
        return;
    }

    //第一个结点前一个结点
    Node * a = getitem(head, i);
    //第二个结点的前一个结点
    Node * b = getitem(head, j);
    //第一个结点
    Node * p = a->next;
    //第二个结点
    Node * q = b->next;
    //第一个结点的下一个结点
    Node * p_next = p->next;
    //第二结点的下一个结点
    Node * q_next = q->next;

    //a的下一个结点指向第二个结点q
    a->next = q;
    //第二结点的下一个结点指向第一个结点的下一个结点
    q->next = p_next;
    //b的下一个结点指向第一个结点p
    b->next = p;
    //第一个结点的下一个结点指向第二个结点的下一个结点
    p->next = q_next;

}
//反转
void rollback(Node * & head) {
    //先知道了最后一个元素和第一个元素的位置
    int end = head->value;
    int start = 1;
    //两边同时开工
    //进行调换
    while (1) {
        if (end <= start)
            return;
        swap_node(head, end, start);
        --end;
        ++start;
    }
}
void print(Node * & head);
//线性表的排序,采用冒泡排序,直接遍历链表
//线性表的排序,交换结点
void Listsort_node(Node* & head) {
    int i = 0;
    int j = 0;
    //用于变量链表
    Node * L = head;
    //作为一个临时量
    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++) {
            //如果我们交换了结点,那么我们就已经在交换结点的时候,把L移动到下一个结点了,所以不要
            //再执行:L = L->next;,否则会报错的
            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) {
    //输出我们只需要传入头结点,然后循环判断当前结点下一个结点是否为空,
    //这样就可以输出所有内容
    Node * L = head;
    while (L->next) {
        L = L->next;
        cout << L->value << " ";
    }
    cout << endl;
}
int main() {
    //链表的头结点,不存放任何值,首先初始化头结点
    Node * head;

    Node * head_array;
    Node * head_node;
    Node * head_roll;
    srand((int)time(NULL));     //每次执行种子不同,生成不同的随机数
    //创建一个链表

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

    int i;
    cout << "请输入需要插入元素个数" << endl;
    int n;
    cin >> n;//5
    //cout << "请输入" << n << "个值" << 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 << "初始化结果" << endl;
    print(head);
    cout << "反转结果" << endl;
    rollback(head_roll);
    print(head_roll);
    cout << "冒泡排序(数据域交换)" << endl;
    Listsort(head);
    print(head);
    cout << "借数组为媒介进行排序(数据域交换)" << endl;
    Listsort_by_array(head_array);
    print(head_array);
    cout << "冒泡排序(结点交换)" << endl;
    Listsort_node(head_node);
    print(head_node);
    system("pause");
    return 0;

}

运行环境:vs2015

输出结果:

以上就是详解C++实现链表的排序算法的详细内容,更多关于C++ 链表排序算法的资料请关注我们其它相关文章!

时间: 2021-06-09

C语言单链表实现通讯录管理系统

本文实例为大家分享了C语言单链表实现通讯录管理系统的具体代码,供大家参考,具体内容如下 本人前几天刚刚自学了单链表,趁热打铁,赶紧写一个小小的项目练练手. 单链表的实现在本人之前的博客中有:C语言编写一个链表 通讯录管理系统 保存人的信息有:  名字   name 电话   telephone 性别   sex 年龄   age 用一个结构体来装这些信息: struct infor{ char name[20]; int age; char sex[8]; char telephone[16];

Java实现单链表反转的多种方法总结

对于单链表不熟悉的可以看一下基于Java实现单链表的增删改查 一.原地反转 1.新建一个哨兵节点下一结点指向头结点 2.把待反转链表的下一节点插入到哨兵节点的下一节点 反转之前的链表:1–>2–>3–>4>–>5 加入哨兵节点:dummp–>1–>2–>3–>4>–>5 原地反转: 定义:prev=dummp.next; pcur=prev.next; prev.next=pcur.next; pcur.next=dummp.next; d

Java数据结构之链表实现(单向、双向链表及链表反转)

前言 之前学习的顺序表查询非常快,时间复杂度为O(1),但是增删改效率非常低,因为每一次增删改都会元素的移动.可以使用另一种存储方式-链式存储结构. 链表是一种物理存储单元上非连续.非顺序的存储结构.链表由一序列的结点(链表中的每一个元素成为结点)组成. 结点API设计: 类名 Node 构造方法 Node(T t,Node next) 创建Node对象 成员变量 T item:存储数据 Node next :指向下一个结点 结点类: public class Node<T>{ Node ne

C++归并法+快速排序实现链表排序的方法

本文主要介绍了C++归并法+快速排序实现链表排序的方法,分享给大家,具体如下: 我们可以试用归并排序解决: 对链表归并排序的过程如下. 找到链表的中点,以中点为分界,将链表拆分成两个子链表.寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点. 对两个子链表分别排序. 将两个排序后的子链表合并,得到完整的排序后的链表 上述过程可以通过递归实现.递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链

C语言基于单链表实现通讯录功能

本文实例为大家分享了C语言基于单链表实现通讯录功能的具体代码,供大家参考,具体内容如下 #include<stdio.h> #include<stdlib.h> #include<string.h> #pragma warning(disable:4996)://解决VS报严重性代码错误 typedef struct LNode { char name[20]; double ph_number; struct LNode* next; }LinkNode; //创建通

C语言链表实现简易通讯录

本文实例为大家分享了C语言链表实现简易通讯录的具体代码,供大家参考,具体内容如下 链表实现通讯录功能: 1.添加–(输入 姓名,电话) 2.删除-- (输入人名,删除该人) 3.查询-- (直接打印所有联系人) 4.修改-- (输入人名,修改电话) 运行效果: 代码分主函数块 和 链表块: Linklist.h #ifndef LINKLIST_H_INCLUDED #define LINKLIST_H_INCLUDED //链表节点 typedef struct Node { char nam

Java如何实现单链表的增删改查

一.新建学生节点类 Stu_Node节点包含: 学号:int num; 姓名:String name; 性别:String gender; 下一个节点:Stu_Node next; 为了便于打印节点内容需要重写toString方法 class Stu_Node{ int num; String name; String gender; Stu_Node next; @Override public String toString() { return "Stu_Node{" + &qu

java jdbc连接mysql数据库实现增删改查操作

jdbc相信大家都不陌生,只要是个搞java的,最初接触j2ee的时候都是要学习这么个东西的,谁叫程序得和数据库打交道呢!而jdbc就是和数据库打交道非常基础的一个知识,也是比较接近底层的,在实际的工作中大家用得更多的其实还是比较成熟的框架,例如Hibernate.Mybatis. 但是作为这些成熟框架的底层的jdbc却也是我们应该去掌握的,只有了解了jdbc的增删改查,这样在以后如果有兴趣去研究Hibernate或者Mybatis的源代码的时候才能更好的去理解这些成熟的框架是如何去实现增删改查

java对xml节点属性的增删改查实现方法

学习本文之前请先看我的另一篇文章JAVA对XML节点的操作可以对XML操作有更好的了解. package vastsum; import java.io.File; import java.io.FileWriter; import java.util.Iterator; import org.dom4j.Attribute; import org.dom4j.Document; import org.dom4j.Element; import org.dom4j.io.SAXReader; i

Java描述数据结构学习之链表的增删改查详解

前言 链表是一种常见的基础数据结构,它是一种线性表,但在内存中它并不是顺序存储的,它是以链式进行存储的,每一个节点里存放的是下一个节点的"指针".在Java中的数据分为引用数据类型和基础数据类型,在Java中不存在指针的概念,但是对于链表而言的指针,指的就是引用数据类型的地址. 链表和数组都是线性的数据结构,对于数组而言其长度是固定的,由于在内存中其是连续的,因此更适合做查找与遍历,而链表在内存中是并不是顺序存储的,但是由于其是通过"指针"构成的,因此在插入.删除时

C#在winform中实现数据增删改查等功能

winform中利用ado.net实现对单表的增删改查的详细例子,具体如下: 1.前言: 运行环境:VS2013+SQL2008+Windows10 程序界面预览: 使用的主要控件:dataGridview和menuStrip等.  2.功能具体介绍: 1.首先,我们要先实现基本的数据操作,增删改查这几个操作. (1)先定义一个数据库操作的公共类: using System; using System.Collections.Generic; using System.Linq; using S

java实现单链表增删改查的实例代码详解

package 数据结构算法.链表; /* *定义节点 * 链表由节点构成 */ public class Node<E> { private E e; //数据data private Node<E> next; //指向下一个节点 public Node() { } public Node(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node&l

java操作mysql实现增删改查的方法

本文实例讲述了java操作mysql实现增删改查的方法.分享给大家供大家参考,具体如下: 首先,需要把MySQL与Java连接的jar(mysql-connector-java-5.1.6-bin.jar)包导入工程. package com.cn.edu; import java.beans.Statement; import java.sql.Connection; import java.sql.DriverManager; import java.sql.PreparedStatemen

Java编程通过list接口实现数据的增删改查代码示例

List接口常用的实现ArrayList. 常用方法:add(Object obj)  增加一个元素                      add(int index,Object obj) 在指定索引位置添加元素                      remove(int index) 删除指定位置的元素                      remove(Objiect)  从列表中删除元素                      set(index,Object) 修改指定位

Java语言实现对MySql数据库中数据的增删改查操作的代码

简单说操作的步骤: 1.连接数据库 2.将SQL语句发送到数据库 3.执行SQL语句 这里举个例子: 在一个数据库中有个students表,表中有学号(Id),姓名(Name),性别(Sex),地址(Address),电话(Phone),专业(Dept). 这里把这个表写成一个学生信息类(Info_student) (请先确保看了例子说明,不然代码有的地方可能看不明白) 要实现操纵我们首先得连接数据库,因为每个操作都要进行连接操作,所以我们直接把连接的操作封装在一个类中,需要连接的时候直接调用可

Java连接MongoDB进行增删改查的操作

Java连接MongoDB进行增删改查的操作 1.创建数据库的连接,进行增删改查 (分别为接口和实现类) package com.dao; import java.util.List; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.data.mongodb.core.MongoTemplate; import org.springframework.data.mo

mybatis实现增删改查_动力节点Java学院整理

所需要用到的其他工具或技术: 项目管理工具 : Maven 测试运行工具 : Junit 数据库 : Derby Maven Dependencies: <dependencies> <dependency> <groupId>org.mybatis</groupId> <artifactId>mybatis</artifactId> <version>3.2.7</version> </dependen