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

双向链表排序[通俗易懂]双向链表的结构体,包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的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)


相关推荐

  • 关于递归和迭代[通俗易懂]

    关于递归和迭代[通俗易懂]首先明确递归和迭代的概念。递归:程序调用自身的编程技巧(将大问题化解为相同结构的小问题,从待解问题一直分解到已知答案的最小问题,在逐级返回得      到原解)    使用递归的两个阶段:    1)递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;    2)回归:当获得最简单的情况后,逐步返回,依次得到复杂的解.迭代:从已知式出发

  • linux udp端口怎么打开_debian防火墙开放端口

    linux udp端口怎么打开_debian防火墙开放端口iptables是linux下的防火墙,同时也是服务名称。那么你知道Linux防火墙怎么开放端口么?接下来是小编为大家收集的Linux防火墙开放端口,欢迎大家阅读:Linux防火墙开放端口serviceiptablesstatus查看防火墙状态serviceiptablesstart开启防火墙serviceiptablesstop关闭防火墙serviceiptablesres…

  • webstorm2021激活码【最新永久激活】

    (webstorm2021激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • vb.net 教程 12-4 msHtml 3

    版权声明:本文为博主原创文章,转载请在显著位置标明本文出处以及作者网名,未经作者允许不得用于商业目的。相比之前学习的HtmlDocument类和HtmlElement类,mshtml还提供了网页元素更详细的分类,比如IHTMLScriptElement:脚本元素IHTMLStyleSheet:样式表IHTMLFormElement:表单元素等等这些不同的元素分类有着自己的…

  • 如何获取uuid_uuid是怎么生成的

    如何获取uuid_uuid是怎么生成的item.id=UUID.randomUUID().toString();

  • apache2.2 虚拟主机配置

    apache2.2 虚拟主机配置

    2021年12月10日

发表回复

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

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