数据结构 | 每日一练（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）本题也是链表排序问题，虽没象上题那样明确要求“利用直接插入的原则”来排序，仍可用上述算法求解，这里不再赘述。

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