专栏首页C语言入门到精通数据结构 | 每日一练(47)

数据结构 | 每日一练(47)

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1.设 L 为单链表的头结点地址,其数据结点的数据都是正整数且无相同的,试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。

类似本题的另外叙述有:

(1)设一单向链表的头指针为 head,链表的记录中包含着整数类型的 key 域,试设计算法,将此链表的记录按照 key 递增的次序进行就地排序.

正确答案

ps:||代表注释

1.[题目分析]本题明确指出单链表带头结点,其结点数据是正整数且不相同,要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开释,将各结点依次插入到有序链表中。

LinkedList LinkListInsertSort(LinkedList la)∥la是带头结点的单链表,其数据域是正整数。本算法利用直接插入原则将链表整理成递增的有序链表。

{ if(la->next!=null)∥链表不为空表。

{p=la->next->next;∥p指向第一结点的后继。

la->next->next=null;∥直接插入原则认为第一元素有序,然后从第二元素起依次插入。

while(p!=null)

{r=p->next;∥暂存p的后继。

q=la;

while(q->next!=null&&q->next->data<p->data)q=q->next;∥查找插入位置。

p->next=q->next;∥将p结点链入链表。

q->next=p;

p=r;

}

与本题有类似叙述的题的解答:

(1)本题也是链表排序问题,虽没象上题那样明确要求“利用直接插入的原则”来排序,仍可用上述算法求解,这里不再赘述。

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

本文分享自微信公众号 - C语言入门到精通(gh_780327809188)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 | 每日一练(28)

    ——老子

    闫小林
  • 数据结构 | 每日一练(102)

    ——老子

    闫小林
  • 数据结构 | 每日一练(108)

    ——老子

    闫小林
  • 【算法】213-每周一练 之 数据结构与算法(LinkedList)

    这些都是数据结构与算法,一部分方法是团队其他成员实现的,一部分我自己做的,有什么其他实现方法或错误,欢迎各位大佬指点,感谢。

    pingan8787
  • Leetcode: Swap Nodes in Pairs

    题目: Given a linked list, swap every two adjacent nodes and return its head.

    卡尔曼和玻尔兹曼谁曼
  • Data Structures and Algorithms Basics(006):Link list

    用户5473628
  • [PHP] 数据结构-链表创建-插入-删除-查找的PHP实现

    链表获取元素 1.声明结点p指向链表第一个结点,j初始化1开始 2.j<i,p指向下一结点,因为此时p是指向的p的next,因此不需要等于 3.如果到末尾了,p...

    陶士涵
  • JDK源码分析-LinkedList

    LinkedList 内部是一个双向链表,并且实现了 List 接口和 Deque 接口,因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如...

    WriteOnRead
  • 用原生js写一个"多动症"的简历

    想象一下你要往一张网页每间隔0.1秒增加一个啊字,是不是开个定时器,间断地往body里面塞啊,就可以啊!没错,做到这一步就完成了原理的第一部分

    IMWeb前端团队
  • 用原生js写一个"多动症"的简历

    用原生js写一个"多动症"的简历 预览地址 源码地址 最近在知乎上看到@方应杭用vue写了一个会动的简历,觉得挺好玩的,研究一下其实现思路,决定试试用原生js...

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券