双向链表排序[通俗易懂]

双向链表排序[通俗易懂]双向链表的结构体,包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的data域,initList函数初始化单节点的双链表,addList函数采用头插入方法添加一个节点到双链表中,sort函数实现了对双链表的排序,采用头插入方式建成的双链表的头结点(存储65535的那个节点)必然在末尾(其实双链表没有首尾之说,只是把它当作末尾),排序的时候,1.首先从该节点处,每次查找前驱节点,并记录da…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

双向链表的结构体,包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的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();
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/183063.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • vb教程编程实例详解pdf_vb程序设计教程答案刘炳文

    vb教程编程实例详解pdf_vb程序设计教程答案刘炳文实验8-1编写如图2.8.1所示的应用程度。若单击“建立文件”按钮,则分别用Print#和和Write#语句将三个同学的学号、姓名和成绩写入Score.dat和Score1.dat;若单击“读取文件”按钮,则用lineInput语句按行将两个(当前目录)文件中的数据显示在相应的文本框。其中:学号和姓名是字符串类型,成绩是整型。解题,画2个按钮,2个文本框(2个文本框的MultiLin…

  • 十四、迭代器模式—— 一个一个的遍历 #和设计模式一起旅行#「建议收藏」

    套路要深…故事背景今天要介绍一下迭代器,首先简单说明一下,什么是迭代器,为什么要使用迭代器。 迭代器(Iterate) 的意思就是反复做某件事情。那为什么要反复做某件事情呢,比如我们有个容器里面装了很好东西(这些东西都是同一类型的),要从容器中取每一个东西出来,就要反复去做一个取出的事情。故事主角迭代器模式 : 提供一种方法顺序访问一个聚合对象中的各个元素,而…

  • 4种常用扒站工具(webzip、ha_TeleportPro、Offline Explorer、wget)

    4种常用扒站工具(webzip、ha_TeleportPro、Offline Explorer、wget)

  • h3c路由器常用命令汇总_h3c命令手册

    h3c路由器常用命令汇总_h3c命令手册1、进入系统视图模式system-view2、为设备命名sysname3、显示当前配置displaycurrent-configuration4、中英文切换language-modeChinese|English5、进入以太网端口视图interfaceEthernet1/0/16、设置端口访问模式portlink-typeAccess|Trunk|Hybrid7、激活以太网端口undoshutdown8、关闭以太网端口shut

    2022年10月18日
  • pip安装教程

    直接搜索pippip官网地址会得到下面的图像下载短的那个(如果你不知道pip是否安装可以通过命令pip–version来判断是否已安装)下载完成后解压到你自己知道的文件夹防止找不到,,然后有两种方法安装pip第一种在python环境下安装pippy-mensurepip–upgrade(直接在python里面运行cmd输入这一行代码)第二种可以用python中的内置脚本python内置脚本pyget-pip.py(下载到python文件中打开cmd,然后..

  • js 模拟鼠标双击[通俗易懂]

    js 模拟鼠标双击[通俗易懂]vartargLink=document.getElementById(“something”);varclickEvent=document.createEvent(‘MouseEvents’);clickEvent.initEvent(‘dblclick’,true,true);targLink.dispatchEvent(clickEvent);参考https://stackoverflow.com/questions/23926921/how-do-i-d

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号