精华内容
下载资源
问答
  • 双向链表排序

    万次阅读 2018-07-17 20:52:18
    双向链表的结构体,包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的data域,initList函数初始化单节点的双链表,addList函数采用头插入方法添加一个节点到双链表中,sort函数实现了对双链表排序,...

    双向链表的结构体,包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的data域,initList函数初始化单节点的双链表,addList函数采用头插入方法添加一个节点到双链表中,sort函数实现了对双链表的排序,采用头插入方式建成的双链表的头结点(存储65535的那个节点)必然在末尾(其实双链表没有首尾之说,只是把它当作末尾),排序的时候,1.首先从该节点处,每次查找前驱节点,并记录data获取链表中data最大的节点,并记录指向这个节点的指针和其值。2.将此节点采用头插入的方式插入到链表中(注意要先删除这个节点在链表中的位置)3.再次从头节点处,通过前驱节点遍历整个链表(此时要去掉第一次找到的最大值)找到最大值。

    typedef struct node{
        int data;
        struct node *prior,*next;
    }Link;

     

    void initList(Link *head){//初始化头结点

        head->next = head;
        head->prior = head;
        head->data = 65535;
    }

    void addList(Link *head,int data){//创建链表

        Link *tmp;
        tmp = (Link *)malloc(sizeof(Link));
        tmp->data = data;
        tmp->next = head->next;
        head->next->prior = tmp;
        head->next = tmp;
        tmp->prior= head;
    }

     

    void sort(Link *head){

    Link *p,*tmp,*flag;

    int max;

    p = (Link *)malloc(sizeof(Link));

    tmp = (Link *)malloc(sizeof(Link));

    flag = (Link *)malloc(sizeof(Link));

    tmp  = head->prior;

    max = tmp->data;

    flag = tmp;

    p = tmp->prior;

    while(p->data != 65535){//找到值最大的节点并且标记

    if(p->data > max){

    max = p->data;

    flag = p;

    flag->data = max;

    }

    p = p->prior;

    }

    if(flag->data!=head->next->data)

    {//交换最大值点到头节点后

    flag->prior->next = flag->next;

    flag->next->prior = flag->prior;

    flag->next = head->next;

    flag->prior = head;

    head->next->prior = flag;

    head->next = flag;

    }

    while(head->prior->data != flag->data){

    tmp = head->prior;//重新寻找时总是从表尾,也就是头结点的前驱开始。

    p = tmp->prior;   //从后往前寻找

    while(p->data != flag->data){//找到要交换的节点

    if(p->data > tmp->data){

    tmp = p;

    }

    p = p->prior;

    }

    {//交换两个节点

    tmp->prior->next = tmp->next;

    tmp->next->prior = tmp->prior;

    tmp->next = head->next;

    tmp->prior = head;

    head->next->prior = tmp;

    head->next = tmp;

    }

    }

    }

    主函数的调用代码就比较简单了。

    int _tmain(int argc, _TCHAR* argv[])
    {
        Link *head,*p;

        head =(Link *)malloc(sizeof(Link));

        p =(Link *)malloc(sizeof(Link));

        int i;

        int a[15]={7,4,2,7,5,8,6,3,2,4,5,7,98,3,4};

        initList(head);

        for(i=0;i<15;i++){

            addList(head,a[i]);

        }

        p = head->next;

        while(p->data!=65535){

            printf("%d<-->",p->data);    

            p = p->next;

        }

        printf("\n");

        sort(head);

        p = head->next;

        while(p->data!=65535){

            printf("%d<-->",p->data);    

            p = p->next;

        }

        printf("\n");
        getchar();
    }

    展开全文
  • 函数打印链表函数PrintLinkedList 和 排序函数SortLinkedList注:下面代码中的链表每项都是double类型,如果换做其他的类型或结构,则需要适当修改/// /// 打印链表各结点信息/// /// private static void ...

    本文实例讲述了C#双向链表LinkedList排序实现方法。分享给大家供大家参考。具体如下:

    1.函数

    打印链表函数PrintLinkedList 和 排序函数SortLinkedList

    注:下面代码中的链表每项都是double类型,如果换做其他的类型或结构,则需要适当修改

    ///

    /// 打印链表各结点信息

    ///

    ///

    private static void PrintLinkedList(LinkedList ll, string title = "")

    {

    //打印标题

    Console.WriteLine(string.Format("-- {0} --",

    string.IsNullOrWhiteSpace(title) ? "打印链表" : title));

    //逐个结点打印链表

    LinkedListNode lln = ll.First;

    int counter = 0;

    while (lln != null)

    {

    Console.WriteLine(string.Format("第 {0} 个结点值为 {1}",

    counter++, lln.Value.ToString("#0.0")));

    lln = lln.Next;

    }

    }

    ///

    /// 返回一个排序后的链表

    ///

    /// 待排序链表

    /// true:升序/false:降序

    ///

    private static LinkedList SortLinkedList(

    LinkedList linkedlist, bool isAsc = true)

    {

    LinkedList result = new LinkedList();

    foreach (double nodevalue in linkedlist)

    {

    LinkedListNode lln = result.First;

    while (true)

    {

    if (isAsc) //升序排列时情况

    {

    if (lln == null)

    {

    result.AddLast(nodevalue);

    break;

    }

    else if (nodevalue <= lln.Value)

    {

    result.AddBefore(lln, nodevalue);

    break;

    }

    else

    {

    lln = lln.Next;

    }

    }

    else //降序排列时情况

    {

    if (lln == null)

    {

    result.AddLast(nodevalue);

    break;

    }

    else if (nodevalue >= lln.Value)

    {

    result.AddBefore(lln, nodevalue);

    break;

    }

    else

    {

    lln = lln.Next;

    }

    }

    }

    }

    return result;

    }

    2.Main函数调用

    static void Main(string[] args)

    {

    //测试用数组

    double[] array = new double[]

    {

    3.5, 2.5, 6.2, 8.0, 1.3,

    4.6, 5.5, 2.7, 8.4, 9.7

    };

    //生成链表ll

    LinkedList ll = new LinkedList();

    for (int i = 1; i < array.Length; i++)

    {

    ll.AddLast(array[i]);

    }

    //打印链表ll

    PrintLinkedList(ll, "原链表");

    //对链表ll进行排序(升序)

    ll = SortLinkedList(ll);

    //打印排序后的链表ll

    PrintLinkedList(ll, "链表(升序)");

    //对链表ll进行排序(降序)

    ll = SortLinkedList(ll, false);

    //打印排序后的链表ll

    PrintLinkedList(ll, "链表(降序)");

    Console.ReadLine();

    }

    3.运行结果:

    1ff0942243ac17a03c7885d45906fcfb.png

    希望本文所述对大家的C#程序设计有所帮助。

    展开全文
  • 双向链表循环的快速排序调用函数 #include #include #include #define T 1 #define F -1 typedef int bo; typedef char Type; struct Address { struct Address* next;

    补充昨天的通讯录程序,对双向链表快速排序调用程序进行修改

    双向链表循环的快速排序调用函数

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>


    #define T 1
    #define F -1


    typedef int bo;
    typedef char Type;


    struct Address
    {
    struct Address* next;
    struct Address* prior;
    int id;
    Type name[20];
    Type num[12];
    };


    void rank_num(address head, int begin, int end);
    address unit(address head, int index);
    void print(address head);

    main函数过长且与主题关系不大,省略。

    address unit(address head, int index)        /*address是struct Address* 的自定义类型,unit函数是将address类型变量head指向它的第index个除头结点的结点*/

    {
    int i;
    address temp = head;


    for (i = 0; i < index; i++)
    {
    temp = temp->next;
    }


    return (temp);
    }


    void rank_num(address head, int begin, int end)           //快速排序
    {
    if (begin  >= end)         //排错,加强执行效率
    {
    return;
    }

    int i = begin;           //i是开始的结点位数
    int j = end;              //j是结束的结点位数
    char name[20];       //name[20]和num[12]是暂存数据的过渡char类型数组
    char num[12];


    strcpy(name, unit(head, begin)->name);          //将开始的结点的数据暂存进name,num
    strcpy(num, unit(head, begin)->num);

    while (i < j)
    {
    while (i < j && (strcmp(unit(head, j)->num, num) >= 0))            /*当最后结点的num比暂存的num大或相等,最后结点向前推一位*/
    {
    j--;
    }

    strcpy(unit(head, i)->name, unit(head, j)->name);           //第i,j位结点的数据互换
    strcpy(unit(head, i)->num, unit(head, j)->num);

    while (i < j && strcmp(unit(head, i)->num, num) <= 0)          /*当最初结点的num比暂存的num小或相等,最初结点向前推一位*/
    {
    i++;
    }

    strcpy(unit(head, j)->name, unit(head, i)->name);                  //第i,j位结点数据互换
    strcpy(unit(head, j)->num, unit(head, i)->num);
    }


    strcpy(unit(head, i)->name, name);                    //将暂存的数据返回最初结点
    strcpy(unit(head, i)->num, num);


    rank_num(head, begin, i - 1);            //对最初结点到i - 1位进行排序
    rank_num(head, i + 1, end);             //对i + 1位到最后结点进行排序
    }
    展开全文
  • 打印链表函数PrintLinkedList 和 排序函数SortLinkedList 注:下面代码中的链表每项都是double类型,如果换做其他的类型或结构,则需要适当修改 /// /// 打印链表各结点信息 /// /// <param name=ll></param> ...
  • 双向链表的归并排序

    千次阅读 2016-04-17 19:59:25
    方法二改变指针指向归并排序分为两个部分: MergeSort 和 MergeMergeSort 是一个递归函数,在这个函数里面把待排序的数组或链表分段,直到每段的长度为1为止。Merge 在这个函数中把分开的两段结合起来,并且在结合的...

    双向链表的归并排序

    归并排序分为两个部分: MergeSortMerge

    MergeSort 是一个递归函数,在这个函数里面把待排序的数组或链表分段,直到每段的长度为1为止。

    Merge 在这个函数中把分开的两段结合起来,并且在结合的过程中排序

    对于一个数组用归并排序是比较方便的,而在对双向链表用归并排序时就会发现next/prev指针指向哪里以及一些边界问题很麻烦。

    下面给出两种对双向链表使用归并排序的方法

    LinkedList类的定义

    class LinkedList : virtual public List {
     public:
      typedef struct node {
        int data;
        struct node* next;
        struct node* prev;
        node(E data, struct node* next = NULL, struct node*                 prev = NULL): data(data), next(next), prev(prev) {}
      } node;
      LinkedList();  //这个函数对归并排序没什么用可以无视
      ~LinkedList();  //这个函数对归并排序没什么用可以无视
      virtual void add(int e);  //这个函数对归并排序没什么用可以无视
      virtual void clear(void);  //这个函数对归并排序没什么用可以无视
      virtual bool contain(int e);  //这个函数对归并排序没什么用可以无视
      virtual bool isEmpty(void);  //这个函数对归并排序没什么用可以无视
      virtual void remove(int e);  //这个函数对归并排序没什么用可以无视
      virtual int& operator[](int index); //传入结点序号(从0开始计算)返回第index个结点的data的引用,这个函数会用到
      virtual int& get(int index);  //同上,然而这个函数不会被用到
      virtual int indexOf(int element);  //这个函数对归并排序没什么用可以无视
      virtual void sort(void);  //排序(归并排序)
      virtual int size(void);  //这个函数对归并排序没什么用可以无视
    
     private:
      node* head;  //链表头指针
      node* tail;  //链表尾指针
      int _size;  //结点总个数
    };
    
    //下面是virtual int& operator[](int index);的定义
    int& LinkedList::operator[](int index) {
        node *p = head;
        for (int i = 0; i < index; i++) {
            p = p->next;
        }
        return p->data;
    }

    方法一:在Merge函数中使用数组

    inline void MergeSort(LinkedList *li, LinkedList::node *low, LinkedList::node *high,
    LinkedList::node *head, int i) {
    // li就是待排序的链表,head是头指针,在Merge函数里要用到这两个东西
    //i=high-low,比如high是第3个结点,low是第0个结点,那么i就是3-0=3,i用来找到low与high的中间结点
        LinkedList::node *mid = low, *p = low;
        if (low != high) {
            int m = i/2, n = i/2;  //m和n是i的1/2
            while (m--) {
                mid = mid->next;   //经过m次循环,mid指向了low到high中间位置的结点
            }
            MergeSort(li, low, mid, head, n);  //继续分离左半部分,此时的low就是上面的low,而high是上面的mid,high(即mid)-low = i/2 = n
            MergeSort(li, mid->next, high, head, i-n-1);  //分离右半部分,此时的low是mid->next, high就是上面的high,high-low(即mid->next) = i-n-1
            Merge(li, low, mid, high, i+1, head);  //合并两部分
        }
    }
    
    inline void Merge(LinkedList *li, LinkedList::node *low, LinkedList::node *mid, LinkedList::node *high,  
    int size, LinkedList::node *head) {
    //size是从low到high的结点总个数,包括low和high,所以上面传入的是i+1
        LinkedList::node *p = low, *q = mid->next, *r = head; //r用于找到low所指向的结点的序号
        int a[size], i = 0, j = 0, k;  //建一个数组用于记录排序后的数字顺序
        while (p != mid->next && q != high->next) {
            if (p->data <= q->data) {
                a[i++] = p->data;
                p = p->next;
            } else {
                a[i++] = q->data;
                q = q->next;
            }
        }  //比较两部分的数字的大小,把小的先输出到数组a中
        while (p != mid->next) {
            a[i++] = p->data;
            p = p->next;
        }  //若第一部分有剩余则全部输出到数组a中
        while (q != high->next) {
            a[i++] = q->data;
            q = q->next;
        }  //若第二部分有剩余则全部输出到数组a中
        while (r != low) {
            r = r->next;
            j++;
        }  找到low指向的结点的序号,用j记录
        i = 0;
        for (k = j; k < j+size; k++) {
            (*li)[k] = a[i++];
        }  //把数组a中数字按顺序复制到low到high这个区间里
    }
    /*接下来在sort中只要写一句就够了*/
    void LinkedList::sort(void) {
        MergeSort(this, head, tail, head, _size-1);
    }

    这个方法优点在于思考起来比较方便,而且不用改变next/prev指向的地址,缺点在于比较耗时

    for (k = j; k < j+size; k++) {
            (*li)[k] = a[i++];
        }  //把数组a中数字按顺序复制到low到high这个区间里
    
    //下面是virtual int& operator[](int index);的定义
    int& LinkedList::operator[](int index) {
        node *p = head;
        for (int i = 0; i < index; i++) {
            p = p->next;
        }
        return p->data;
    }

    可以发现每用一次(*li)[k],都会从头搜索一次,当size很大的时候会消耗很多时间,下面提一种优化的方法(虽然只能优化那么一点点)

    /*如index大于size/2,那么就从尾部开始搜索*/
    LinkedList::int& LinkedList::operator[](int index) {
        node *p;
        if (index < _size/2) {
            p = head;
            for (int i = 0; i < index; i++) {
                p = p->next;
            }
        } else {
            p = tail;
            int k = _size-index-1;
            for (int i = 0; i < k; i++) {
                p = p->prev;
            }
        }
        return p->data;
    }

    2.方法二:改变指针指向

    void LinkedList::sort(void) {
      if (this->size() > 1) {
        node* fast = this->head;
        node* slow = this->head;
        LinkedList li_left;
        LinkedList li_right;
    
        li_left.head = this->head;
        while (fast != NULL && fast->next != NULL) {
          li_left._size++;
          fast = fast->next->next;
          slow = slow->next;
        }  //fast一次走两步,slow一次走一步,当fast到底时,slow就处于中间位置
        //从head到slow->prev为一段
        li_left.tail = slow->prev;
        li_left.tail->next = NULL;
        //从slow到tail为另一段
        li_right.head = slow;
        li_right.head->prev = NULL;
        li_right.tail = this->tail;
        li_right._size = this->_size - li_left._size;
    
        this->head = NULL;
        this->tail = NULL;
        //继续对两段进行分割、排序
        li_left.sort();
        li_right.sort();
    
        node* pointer_left = li_left.head;
        node* pointer_right = li_right.head;
    
        node* pointer_head = NULL;
        node* pointer_tail = NULL;
    
        while (pointer_left != NULL && pointer_right != NULL) {
          node* temp;
          if (pointer_left->data <= pointer_right->data) {
            temp = pointer_left;
            pointer_left = pointer_left->next;
          } else {
            temp = pointer_right;
            pointer_right = pointer_right->next;
          }  //temp指向pointer_left与pointer_right中数值较小的结点
          if (pointer_head == NULL) {
            pointer_head = pointer_tail = temp;
          } else {
            pointer_tail->next = temp;
            temp->prev = pointer_tail;
            pointer_tail = temp;
          }  //把temp接到链表中
          pointer_head->prev = NULL;
          pointer_tail->next = NULL;
        }
    
        while (pointer_left != NULL) {
          pointer_tail->next = pointer_left;
          pointer_left->prev = pointer_tail;
          pointer_tail = pointer_left;
          pointer_left = pointer_left->next;
        }
    
        while (pointer_right != NULL) {
          pointer_tail->next = pointer_right;
          pointer_right->prev = pointer_tail;
          pointer_tail = pointer_right;
          pointer_right = pointer_right->next;
        }
    
        this->head = pointer_head;
        this->tail = pointer_tail;
        //注意要把left,right的head,tail指针清空,否则由于是浅拷贝,退出函数栈的时候会把this的空间都释放。
        li_left.head = li_left.tail = NULL;
        li_right.head = li_right.tail = NULL;
      }
    }

    这种方法比较高效,可是需要思考的很严密,一不小心就会出错。

    展开全文
  • 双向链表的选择排序算法

    千次阅读 2014-12-16 18:27:31
    前日遇到一个问题:对双向链表按关键字域进行排序。  在网上找了一下,都只一种算法,而且...于是自己想了一下,写了个带头结点的双向链表的选择排序算法,指针的交换浓缩到4种情况,而且自认为选择排序函数中的结
  • 构建一个递归函数treeToList(Node root),将一棵已排序的二叉树,调整内部指针,使之从外面看起来,是一个循环双向链表。其中前向指针存储在"small"区域,后向指针存储在"large"区域。链表需要进行调整进行升序排序...
  • 打印链表函数PrintLinkedList 和 排序函数SortLinkedList 注:下面代码中的链表每项都是double类型,如果换做其他的类型或结构,则需要适当修改 /// <summary> /// 打印链表各结点信息 /// </summary&g.....
  • void insert_sort(Link head, Link new_node) //边排边插函数,将结点有序的插在链表中 {  Link p;  p = head->prior;  int number = new_node->num;    if (p == head)  {  head->next = ...
  • 【C语言】双链表的实现与冒泡排序

    千次阅读 2019-07-28 12:16:58
    【C语言】双链表的实现与冒泡排序 基于C语言,不做标题党,LInux下GCC通过编译,大致流程(底部附图,源码): 新建双链表(节点数自定义),对节点data域用随机数种子进行随机赋值,并对该链表进行冒泡排序。 ...
  • 创建双向链表类,该类有默认构造函数、类的拷贝函数、类的析构函数、实现链表添加数据、升序排序、查找链表中某个节点及删除链表中某个节点的操作(禁用STL及String类))。 “dLinkList.h” #pragma once #ifndef _...
  • 基于c++11编写的双向链表 实现:dlist.h #ifndef DLIST_H #define DLIST_H #include <iostream> #include <string> #include <stdexcept> using namespace std; typedef int ElemData; struct ...
  • 创写一个双向链表的类和一个结构体,类中包含构造函数、拷贝函数、析构函数、链表的添加数据函数、链表排序函数、输出链表元素函数、删除一结点函数、查找某个结点的函数和修改某个结点数据函数。 类和结构体的.h...
  • STL的list链表排序

    千次阅读 2011-06-26 19:43:00
    在MSVC8.0里,STL给std::list提供了两种排序方法,一个是std::list的sort成员函数,一个是里的std::stable_sort排序函数。 这两种方法的实现是不同的,list::sort()成员函数是针对list容器定制的排序方法,而stable...
  • 把二元查找树转变成排序的双向链表  题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。    10  / \  6 14  / \ / \ 4 8 12 16 ...
  • #题目描述#思路排序链表即可以考虑到中序遍历(即左子树调用递归函数,处理中间节点,右子树调用递归函数)即将当前节点保留为cur变量,把上个处理的节点作为pre变量(通过指针传递)即在中序遍历中:左子节点会变为...
  • 写一个string双向链表模块. 通过建立一一个程序设计语言名字的表来 演习这个模块. 为这个表提供一个sort()函数, 并提供一个函数去反转 表中字符串的顺序. --------------------------------------------------*/ #...
  • C++编写双向链表

    2019-09-25 07:41:56
    创建双向链表类,该类有默认构造函数、类的拷贝函数、类的、实现链表添加数据、升序排序、查找链表中某个节点及删除链表中某个节点的操作 代码实现: #include<iostream> #include<string.h> ...
  • list双向链表容器

    2019-09-29 17:41:26
    list是双向链表的泛化容器,提供了splice和merge归并函数,sort函数利用list的数据结构特点对元素进行了归并排序。 创建list对象 创建list对象的方式主要有下面几种。 (1) list() list<int> l; (2) ...
  • #include using namespace std; //创建树结构 typedef struct node { int data; struct node *ltree,*rtree;...//创建树函数 void creat_tree(BitTree &tree); void mid_travel(BitTree tree,BitTree &bs
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 /** 明确Convert函数的功能。 输入:输入一个二叉搜索树的根节点。 过程:将其转化为一个...
  • 有序双向链表的实现

    2019-10-08 08:46:44
    包含插入、删除、排序、遍历输出等函数。 详见代码: #include <iostream> using namespace std; template<class T> struct Node { T data; Node<T> *rlink,*llink; }; template...
  • 链表的基本操作与链表的逆置,排序等操作结合起来,整理出来 链表是由结点构成的,关键是定义结点C语言程序设计上两大特例:①链表节点的定义②递归函数的定义。这两个违反了先定义再使用。 一、链表的分类 ...
  • list双向链表在任何位置的插入和删除为常数时间,不支持根据下标随机存取元素,具有所有顺序容器都有的成员函数。 list的成员函数: push_front 在链表最前面插入 pop_front 删除链表最前面的元素 sort 排序 (list ...
  • 单项链表的 建立、插入(有序,构造有序链表),删除节点,头插法,尾插法,排序(交换数据)及输出函数,释放节点; #include<stdio.h> #include<stdlib.h> struct node{ int data; struct node *...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 333
精华内容 133
热门标签
关键字:

双链表排序函数