JavaScript实现链表插入排序和链表归并排序
本篇文章详细的介绍了JavaScript实现链表插入排序和链表归并排序，链表的归并排序就是对每个部分都进行归并排序，然后合并在一起。
1.链表
1.1链表的存储表示
//链表的存储表示
typedefintElemType;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
1.2基本操作
创建链表：
/*
*创建链表。
*形参num为链表的长度，函数返回链表的头指针。
*/
LinkListCreatLink(intnum)
{
inti,data;
//p指向当前链表中最后一个结点，q指向准备插入的结点。
LinkListhead=NULL,p=NULL,q;
for(i=0;i<num;i++)
{
scanf("%d",&data);
q=(LinkList)malloc(sizeof(LNode));
q->data=data;
q->next=NULL;
if(i==0)
{
head=q;
}
else
{
p->next=q;
}
p=q;
}
returnhead;
}
输出链表：
/*
*输出链表结点值。
*/
intPrintLink(LinkListhead)
{
LinkListp;
for(p=head;p;p=p->next)
{
printf("%-3d",p->data);
}
return0;
}
2.链表插入排序
基本思想：假设前面n-1个结点有序，将第n个结点插入到前面结点的适当位置，使这n个结点有序。
实现方法：
将链表上第一个结点拆下来，成为含有一个结点的链表(head1)，其余的结点自然成为另外一个链表(head2)，此时head1为含有
一个结点的有序链表；
将链表head2上第一个结点拆下来，插入到链表head1的适当位置，使head1仍有序，此时head1成为含有两个结点的有序链表；
依次从链表head2上拆下一个结点，插入到链表head1中，直到链表head2为空链表为止。最后，链表head1上含所有结点，且结点有序。
插入排序代码：
/*
*链表插入排序(由小到大)。
*输入：链表的头指针，
*输出：排序后链表的头指针。
*实现方法：将原链表拆成两部分：链表1仍以head为头指针，链表结点有序。链表2以head2为头指针，链表结点无序。
*将链表2中的结点依次插入到链表1中，并保持链表1有序。
*最后链表1中包含所有结点，且有序。
*/
LinkListLinkInsertSort(LinkListhead)
{
//current指向当前待插入的结点。
LinkListhead2,current,p,q;
if(head==NULL)
returnhead;
//第一次拆分。
head2=head->next;
head->next=NULL;
while(head2)
{
current=head2;
head2=head2->next;
//寻找插入位置，插入位置为结点p和q中间。
for(p=NULL,q=head;q&&q->data<=current->data;p=q,q=q->next);
if(q==head)
{
//将current插入最前面。
head=current;
}
else
{
p->next=current;
}
current->next=q;
}
returnhead;
}
完整源代码：
/*
*链表插入排序，由小到大
*/
#define_CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#defineTOTAL10//链表长度
//链表的存储表示
typedefintElemType;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
LinkListCreatLink(intnum);
LinkListLinkInsertSort(LinkListhead);
intPrintLink(LinkListhead);
/*
*创建链表。
*形参num为链表的长度，函数返回链表的头指针。
*/
LinkListCreatLink(intnum)
{
inti,data;
//p指向当前链表中最后一个结点，q指向准备插入的结点。
LinkListhead=NULL,p=NULL,q;
for(i=0;i<num;i++)
{
scanf("%d",&data);
q=(LinkList)malloc(sizeof(LNode));
q->data=data;
q->next=NULL;
if(i==0)
{
head=q;
}
else
{
p->next=q;
}
p=q;
}
returnhead;
}
/*
*链表插入排序(由小到大)。
*输入：链表的头指针，
*输出：排序后链表的头指针。
*实现方法：将原链表拆成两部分：链表1仍以head为头指针，链表结点有序。链表2以head2为头指针，链表结点无序。
*将链表2中的结点依次插入到链表1中，并保持链表1有序。
*最后链表1中包含所有结点，且有序。
*/
LinkListLinkInsertSort(LinkListhead)
{
//current指向当前待插入的结点。
LinkListhead2,current,p,q;
if(head==NULL)
returnhead;
//第一次拆分。
head2=head->next;
head->next=NULL;
while(head2)
{
current=head2;
head2=head2->next;
//寻找插入位置，插入位置为结点p和q中间。
for(p=NULL,q=head;q&&q->data<=current->data;p=q,q=q->next);
if(q==head)
{
//将current插入最前面。
head=current;
}
else
{
p->next=current;
}
current->next=q;
}
returnhead;
}
/*
*输出链表结点值。
*/
intPrintLink(LinkListhead)
{
LinkListp;
for(p=head;p;p=p->next)
{
printf("%-3d",p->data);
}
return0;
}
intmain()
{
LinkListhead;
printf("输入Total个数以创建链表：\n");
head=CreatLink(TOTAL);
head=LinkInsertSort(head);
printf("排序后：\n");
PrintLink(head);
putchar('\n');
return0;
}
3.链表归并排序
基本思想：如果链表为空或者含有一个结点，链表自然有序。否则，将链表分成两部分，对每一部分分别进行归并排序，然后将已排序的两个链表归并在一起。
归并排序代码：
/*
*链表归并排序(由小到大)。
*输入：链表的头指针，
*输出：排序后链表的头指针。
*递归实现方法：将链表head分为两部分，分别进行归并排序，再将排序后的两部分归并在一起。
*递归结束条件：进行递归排序的链表为空或者只有一个结点。
*/
LinkListLinkMergeSort(LinkListhead)
{
LinkListhead1,head2;
if(head==NULL||head->next==NULL)
returnhead;
LinkSplit(head,&head1,&head2);
head1=LinkMergeSort(head1);
head2=LinkMergeSort(head2);
head=LinkMerge(head1,head2);
returnhead;
}
其中链表分割函数如下，基本思想是利用slow/fast指针，具体实现方法见注释。
/*
*链表分割函数。
*将链表head均分为两部分head1和head2，若链表长度为奇数，多出的结点从属于第一部分。
*实现方法：首先使指针slow/fast指向链首，
*然后使fast指针向前移动两个结点的同时，slow指针向前移动一个结点，
*循环移动，直至fast指针指向链尾。结束时，slow指向链表head1的链尾。
*/
intLinkSplit(LinkListhead,LinkList*head1,LinkList*head2)
{
LinkListslow,fast;
if(head==NULL||head->next==NULL)
{
*head1=head;
*head2=NULL;
return0;
}
slow=head;
fast=head->next;
while(fast)
{
fast=fast->next;
if(fast)
{
fast=fast->next;
slow=slow->next;
}
}
*head1=head;
*head2=slow->next;
//注意：一定要将链表head1的链尾置空。
slow->next=NULL;
return0;
}
链表归并函数有递归实现和非递归实现两种方法：
非递归实现：
/*
*链表归并。
*将两个有序的链表归并在一起，使总链表有序。
*输入：链表head1和链表head2
*输出：归并后的链表
*实现方法：将链表head2中的结点依次插入到链表head1中的适当位置，使head1仍为有序链表。
*/
LinkListLinkMerge(LinkListhead1,LinkListhead2)
{
LinkListp,q,t;
if(!head1)
returnhead2;
if(!head2)
returnhead1;
//循环变量的初始化，q指向链表head1中的当前结点，p为q的前驱。
p=NULL;
q=head1;
while(head2)
{
//t为待插入结点。
t=head2;
head2=head2->next;
//寻找插入位置，插入位置为p和q之间。
for(;q&&q->data<=t->data;p=q,q=q->next);
if(p==NULL)
head1=t;
else
p->next=t;
t->next=q;
//将结点t插入到p和q之间后，使p重新指向q的前驱。
p=t;
}
returnhead1;
}
递归实现：
LinkListLinkMerge2(LinkListhead1,LinkListhead2)
{
LinkListresult;
if(!head1)
returnhead2;
if(!head2)
returnhead1;
if(head1->data<=head2->data)
{
result=head1;
result->next=LinkMerge(head1->next,head2);
}
else
{
result=head2;
result->next=LinkMerge(head1,head2->next);
}
returnresult;
}
完整源代码：
/*
*链表归并排序，由小到大。
*/
#define_CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#defineTOTAL10//链表长度
//链表的存储表示
typedefintElemType;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
LinkListCreatLink(intnum);
LinkListLinkMergeSort(LinkListhead);
LinkListLinkMerge(LinkListhead1,LinkListhead2);
LinkListLinkMerge2(LinkListhead1,LinkListhead2);
intLinkSplit(LinkListhead,LinkList*head1,LinkList*head2);
intPrintLink(LinkListhead);
/*
*创建链表。
*形参num为链表的长度，函数返回链表的头指针。
*/
LinkListCreatLink(intnum)
{
inti,data;
//p指向当前链表中最后一个结点，q指向准备插入的结点。
LinkListhead=NULL,p=NULL,q;
for(i=0;i<num;i++)
{
scanf("%d",&data);
q=(LinkList)malloc(sizeof(LNode));
q->data=data;
q->next=NULL;
if(i==0)
{
head=q;
}
else
{
p->next=q;
}
p=q;
}
returnhead;
}
/*
*输出链表结点值。
*/
intPrintLink(LinkListhead)
{
LinkListp;
for(p=head;p;p=p->next)
{
printf("%-3d",p->data);
}
return0;
}
intmain()
{
LinkListhead;
printf("输入Total个数以创建链表：\n");
head=CreatLink(TOTAL);
head=LinkMergeSort(head);
printf("排序后：\n");
PrintLink(head);
putchar('\n');
return0;
}
/*
*链表归并排序(由小到大)。
*输入：链表的头指针，
*输出：排序后链表的头指针。
*递归实现方法：将链表head分为两部分，分别进行归并排序，再将排序后的两部分归并在一起。
*递归结束条件：进行递归排序的链表为空或者只有一个结点。
*/
LinkListLinkMergeSort(LinkListhead)
{
LinkListhead1,head2;
if(head==NULL||head->next==NULL)
returnhead;
LinkSplit(head,&head1,&head2);
head1=LinkMergeSort(head1);
head2=LinkMergeSort(head2);
head=LinkMerge(head1,head2);//非递归实现
//head=LinkMerge2(head1,head2);//递归实现
returnhead;
}
/*
*链表归并。
*将两个有序的链表归并在一起，使总链表有序。
*输入：链表head1和链表head2
*输出：归并后的链表
*实现方法：将链表head2中的结点依次插入到链表head1中的适当位置，使head1仍为有序链表。
*/
LinkListLinkMerge(LinkListhead1,LinkListhead2)
{
LinkListp,q,t;
if(!head1)
returnhead2;
if(!head2)
returnhead1;
//循环变量的初始化，q指向链表head1中的当前结点，p为q的前驱。
p=NULL;
q=head1;
while(head2)
{
//t为待插入结点。
t=head2;
head2=head2->next;
//寻找插入位置，插入位置为p和q之间。
for(;q&&q->data<=t->data;p=q,q=q->next);
if(p==NULL)
head1=t;
else
p->next=t;
t->next=q;
//将结点t插入到p和q之间后，使p重新指向q的前驱。
p=t;
}
returnhead1;
}
LinkListLinkMerge2(LinkListhead1,LinkListhead2)
{
LinkListresult;
if(!head1)
returnhead2;
if(!head2)
returnhead1;
if(head1->data<=head2->data)
{
result=head1;
result->next=LinkMerge(head1->next,head2);
}
else
{
result=head2;
result->next=LinkMerge(head1,head2->next);
}
returnresult;
}
/*
*链表分割函数。
*将链表head均分为两部分head1和head2，若链表长度为奇数，多出的结点从属于第一部分。
*实现方法：首先使指针slow/fast指向链首，
*然后使fast指针向前移动两个结点的同时，slow指针向前移动一个结点，
*循环移动，直至fast指针指向链尾。结束时，slow指向链表head1的链尾。
*/
intLinkSplit(LinkListhead,LinkList*head1,LinkList*head2)
{
LinkListslow,fast;
if(head==NULL||head->next==NULL)
{
*head1=head;
*head2=NULL;
return0;
}
slow=head;
fast=head->next;
while(fast)
{
fast=fast->next;
if(fast)
{
fast=fast->next;
slow=slow->next;
}
}
*head1=head;
*head2=slow->next;
//注意：一定要将链表head1的链尾置空。
slow->next=NULL;
return0;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。