第1章第2节练习题12 单链表之插入排序
最后更新于：2022-04-01 19:51:02
## 问题描述
> 有一个带头结点的单链表对其排序，使之递增有序。
## 算法思想
> 本题是仅仅要求完成排序，因此我们很容易的想到使用插入排序算法完成单链表的排序。
首先将单链表的头结点拆下，用指针p指向剩余的不带头结点的那部分链表的的第一个结点，指针q指向指针p指向的结点的下一个结点。然后将指针p指向的结点摘下，使用指针pre对带有头结点的那部分链表进行遍历，如果指针pre所指结点的下一个结点的数据域值比指针p所指结点的数据域的值大，则将指针p所指结点插入到指针pre所指结点的后面，这样便完成了一次排序过程。重新让指针p指向不带头节点的那部分链表的第一个结点，指针q指向指针p所指结点的下一个结点，重新开始一次排序。
如图所示：
## 算法描述
~~~
void Sort(LNode *head)
{
LNode *pre=head;
LNode *p=pre->next;
LNode *q=p->next;
p->next=NULL;
p=q;
while(q){
q=p->next;
pre=head;
while(pre->next!=NULL&&pre->next->datadata){
pre=pre->next;
}
p->next=pre->next;
pre->next=p;
p=q;
}
}
~~~
具体代码见附件
## 附件
~~~
#include
#include
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
LinkList CreatList(LNode*);
void Sort(LNode*);
void Print(LNode*);
int main(int argc, char* argv[])
{
LNode *head;
head=(LNode*)malloc(sizeof(LNode));
head->next=NULL;
head=CreatList(head);
Print(head);
Sort(head);
Print(head);
return 0;
}
//头插法创建单链表
LinkList CreatList(LNode* head)
{
LNode *L;
ElemType x;
scanf("%d",&x);
while(x!=999){
L=(LNode*)malloc(sizeof(LNode));
L->data=x;
L->next=head->next;
head->next=L;
scanf("%d",&x);
}
return head;
}
//直接插入排序
void Sort(LNode *head)
{
LNode *pre=head;
LNode *p=pre->next;
LNode *q=p->next;
p->next=NULL;
p=q;
while(q){
q=p->next;
pre=head;
while(pre->next!=NULL&&pre->next->datadata){
pre=pre->next;
}
p->next=pre->next;
pre->next=p;
p=q;
}
}
//打印全部结点
void Print(LNode *head)
{
LNode *p=head->next;
while(p){
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
~~~
';