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; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。