本篇文章詳細(xì)的介紹了JavaScript實現(xiàn)鏈表插入排序和鏈表歸并排序，鏈表的歸并排序就是對每個部分都進(jìn)行歸并排序，然后合并在一起。
1.鏈表
1.1鏈表的存儲表示
//鏈表的存儲表示
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
1.2基本操作
創(chuàng)建鏈表：
/*
* 創(chuàng)建鏈表。
* 形參num為鏈表的長度，函數(shù)返回鏈表的頭指針。
*/
LinkList CreatLink(int num)
{
int i, data;
//p指向當(dāng)前鏈表中最后一個結(jié)點，q指向準(zhǔn)備插入的結(jié)點。
LinkList head = 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;
}
return head;
}
輸出鏈表：
/*
* 輸出鏈表結(jié)點值。
*/
int PrintLink(LinkList head)
{
LinkList p;
for (p = head; p ;p = p->next)
{
printf("%-3d ", p->data);
}
return 0;
}
2.鏈表插入排序
基本思想：假設(shè)前面n-1個結(jié)點有序，將第n個結(jié)點插入到前面結(jié)點的適當(dāng)位置，使這n個結(jié)點有序。
實現(xiàn)方法：
將鏈表上第一個結(jié)點拆下來，成為含有一個結(jié)點的鏈表(head1)，其余的結(jié)點自然成為另外一個鏈表(head2)，此時head1為含有
一個結(jié)點的有序鏈表；
將鏈表head2上第一個結(jié)點拆下來，插入到鏈表head1的適當(dāng)位置，使head1仍有序，此時head1成為含有兩個結(jié)點的有序鏈表；
依次從鏈表head2上拆下一個結(jié)點，插入到鏈表head1中，直到鏈表head2為空鏈表為止。最后，鏈表head1上含所有結(jié)點，且結(jié)點有序。
插入排序代碼：
/*
* 鏈表插入排序(由小到大)。
* 輸入：鏈表的頭指針，
* 輸出：排序后鏈表的頭指針。
* 實現(xiàn)方法：將原鏈表拆成兩部分：鏈表1仍以head為頭指針，鏈表結(jié)點有序。鏈表2以head2為頭指針，鏈表結(jié)點無序。
* 將鏈表2中的結(jié)點依次插入到鏈表1中，并保持鏈表1有序。
* 最后鏈表1中包含所有結(jié)點，且有序。
*/
LinkList LinkInsertSort(LinkList head)
{
//current指向當(dāng)前待插入的結(jié)點。
LinkList head2, current, p, q;
if (head == NULL)
return head;
//第一次拆分。
head2 = head->next;
head->next = NULL;
while (head2)
{
current = head2;
head2 = head2->next;
//尋找插入位置，插入位置為結(jié)點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;
}
return head;
}
完整源代碼：
/*
* 鏈表插入排序，由小到大
*/
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h>
#include stdlib.h>
#define TOTAL 10 //鏈表長度
//鏈表的存儲表示
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatLink(int num);
LinkList LinkInsertSort(LinkList head);
int PrintLink(LinkList head);
/*
* 創(chuàng)建鏈表。
* 形參num為鏈表的長度，函數(shù)返回鏈表的頭指針。
*/
LinkList CreatLink(int num)
{
int i, data;
//p指向當(dāng)前鏈表中最后一個結(jié)點，q指向準(zhǔn)備插入的結(jié)點。
LinkList head = 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;
}
return head;
}
/*
* 鏈表插入排序(由小到大)。
* 輸入：鏈表的頭指針，
* 輸出：排序后鏈表的頭指針。
* 實現(xiàn)方法：將原鏈表拆成兩部分：鏈表1仍以head為頭指針，鏈表結(jié)點有序。鏈表2以head2為頭指針，鏈表結(jié)點無序。
* 將鏈表2中的結(jié)點依次插入到鏈表1中，并保持鏈表1有序。
* 最后鏈表1中包含所有結(jié)點，且有序。
*/
LinkList LinkInsertSort(LinkList head)
{
//current指向當(dāng)前待插入的結(jié)點。
LinkList head2, current, p, q;
if (head == NULL)
return head;
//第一次拆分。
head2 = head->next;
head->next = NULL;
while (head2)
{
current = head2;
head2 = head2->next;
//尋找插入位置，插入位置為結(jié)點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;
}
return head;
}
/*
* 輸出鏈表結(jié)點值。
*/
int PrintLink(LinkList head)
{
LinkList p;
for (p = head; p ;p = p->next)
{
printf("%-3d ", p->data);
}
return 0;
}
int main()
{
LinkList head;
printf("輸入Total個數(shù)以創(chuàng)建鏈表：\n");
head = CreatLink(TOTAL);
head = LinkInsertSort(head);
printf("排序后：\n");
PrintLink(head);
putchar('\n');
return 0;
}
3.鏈表歸并排序
基本思想：如果鏈表為空或者含有一個結(jié)點，鏈表自然有序。否則，將鏈表分成兩部分，對每一部分分別進(jìn)行歸并排序，然后將已排序的兩個鏈表歸并在一起。
歸并排序代碼：
/*
* 鏈表歸并排序(由小到大)。
* 輸入：鏈表的頭指針，
* 輸出：排序后鏈表的頭指針。
* 遞歸實現(xiàn)方法：將鏈表head分為兩部分，分別進(jìn)行歸并排序，再將排序后的兩部分歸并在一起。
* 遞歸結(jié)束條件：進(jìn)行遞歸排序的鏈表為空或者只有一個結(jié)點。
*/
LinkList LinkMergeSort(LinkList head)
{
LinkList head1, head2;
if (head == NULL || head->next == NULL)
return head;
LinkSplit(head, head1, head2);
head1 = LinkMergeSort(head1);
head2 = LinkMergeSort(head2);
head = LinkMerge(head1, head2);
return head;
}
其中鏈表分割函數(shù)如下，基本思想是利用slow/fast指針，具體實現(xiàn)方法見注釋。
/*
* 鏈表分割函數(shù)。
* 將鏈表head均分為兩部分head1和head2，若鏈表長度為奇數(shù)，多出的結(jié)點從屬于第一部分。
* 實現(xiàn)方法：首先使指針slow/fast指向鏈?zhǔn)祝?
* 然后使fast指針向前移動兩個結(jié)點的同時，slow指針向前移動一個結(jié)點，
* 循環(huán)移動，直至fast指針指向鏈尾。結(jié)束時，slow指向鏈表head1的鏈尾。
*/
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2)
{
LinkList slow, fast;
if (head == NULL || head->next == NULL)
{
*head1 = head;
*head2 = NULL;
return 0;
}
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;
return 0;
}
鏈表歸并函數(shù)有遞歸實現(xiàn)和非遞歸實現(xiàn)兩種方法：
非遞歸實現(xiàn)：
/*
* 鏈表歸并。
* 將兩個有序的鏈表歸并在一起，使總鏈表有序。
* 輸入：鏈表head1和鏈表head2
* 輸出：歸并后的鏈表
* 實現(xiàn)方法：將鏈表head2中的結(jié)點依次插入到鏈表head1中的適當(dāng)位置，使head1仍為有序鏈表。
*/
LinkList LinkMerge(LinkList head1, LinkList head2)
{
LinkList p, q, t;
if (!head1)
return head2;
if (!head2)
return head1;
//循環(huán)變量的初始化，q指向鏈表head1中的當(dāng)前結(jié)點，p為q的前驅(qū)。
p = NULL;
q = head1;
while (head2)
{
//t為待插入結(jié)點。
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;
//將結(jié)點t插入到p和q之間后，使p重新指向q的前驅(qū)。
p = t;
}
return head1;
}
遞歸實現(xiàn)：
LinkList LinkMerge2(LinkList head1, LinkList head2)
{
LinkList result;
if (!head1)
return head2;
if (!head2)
return head1;
if (head1->data = head2->data)
{
result = head1;
result->next = LinkMerge(head1->next, head2);
}
else
{
result = head2;
result->next = LinkMerge(head1, head2->next);
}
return result;
}
完整源代碼：
/*
* 鏈表歸并排序，由小到大。
*/
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h>
#include stdlib.h>
#define TOTAL 10 //鏈表長度
//鏈表的存儲表示
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatLink(int num);
LinkList LinkMergeSort(LinkList head);
LinkList LinkMerge(LinkList head1, LinkList head2);
LinkList LinkMerge2(LinkList head1, LinkList head2);
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2);
int PrintLink(LinkList head);
/*
* 創(chuàng)建鏈表。
* 形參num為鏈表的長度，函數(shù)返回鏈表的頭指針。
*/
LinkList CreatLink(int num)
{
int i, data;
//p指向當(dāng)前鏈表中最后一個結(jié)點，q指向準(zhǔn)備插入的結(jié)點。
LinkList head = 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;
}
return head;
}
/*
* 輸出鏈表結(jié)點值。
*/
int PrintLink(LinkList head)
{
LinkList p;
for (p = head; p; p = p->next)
{
printf("%-3d ", p->data);
}
return 0;
}
int main()
{
LinkList head;
printf("輸入Total個數(shù)以創(chuàng)建鏈表：\n");
head = CreatLink(TOTAL);
head = LinkMergeSort(head);
printf("排序后：\n");
PrintLink(head);
putchar('\n');
return 0;
}
/*
* 鏈表歸并排序(由小到大)。
* 輸入：鏈表的頭指針，
* 輸出：排序后鏈表的頭指針。
* 遞歸實現(xiàn)方法：將鏈表head分為兩部分，分別進(jìn)行歸并排序，再將排序后的兩部分歸并在一起。
* 遞歸結(jié)束條件：進(jìn)行遞歸排序的鏈表為空或者只有一個結(jié)點。
*/
LinkList LinkMergeSort(LinkList head)
{
LinkList head1, head2;
if (head == NULL || head->next == NULL)
return head;
LinkSplit(head, head1, head2);
head1 = LinkMergeSort(head1);
head2 = LinkMergeSort(head2);
head = LinkMerge(head1, head2); //非遞歸實現(xiàn)
//head = LinkMerge2(head1, head2); //遞歸實現(xiàn)
return head;
}
/*
* 鏈表歸并。
* 將兩個有序的鏈表歸并在一起，使總鏈表有序。
* 輸入：鏈表head1和鏈表head2
* 輸出：歸并后的鏈表
* 實現(xiàn)方法：將鏈表head2中的結(jié)點依次插入到鏈表head1中的適當(dāng)位置，使head1仍為有序鏈表。
*/
LinkList LinkMerge(LinkList head1, LinkList head2)
{
LinkList p, q, t;
if (!head1)
return head2;
if (!head2)
return head1;
//循環(huán)變量的初始化，q指向鏈表head1中的當(dāng)前結(jié)點，p為q的前驅(qū)。
p = NULL;
q = head1;
while (head2)
{
//t為待插入結(jié)點。
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;
//將結(jié)點t插入到p和q之間后，使p重新指向q的前驅(qū)。
p = t;
}
return head1;
}
LinkList LinkMerge2(LinkList head1, LinkList head2)
{
LinkList result;
if (!head1)
return head2;
if (!head2)
return head1;
if (head1->data = head2->data)
{
result = head1;
result->next = LinkMerge(head1->next, head2);
}
else
{
result = head2;
result->next = LinkMerge(head1, head2->next);
}
return result;
}
/*
* 鏈表分割函數(shù)。
* 將鏈表head均分為兩部分head1和head2，若鏈表長度為奇數(shù)，多出的結(jié)點從屬于第一部分。
* 實現(xiàn)方法：首先使指針slow/fast指向鏈?zhǔn)祝?
* 然后使fast指針向前移動兩個結(jié)點的同時，slow指針向前移動一個結(jié)點，
* 循環(huán)移動，直至fast指針指向鏈尾。結(jié)束時，slow指向鏈表head1的鏈尾。
*/
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2)
{
LinkList slow, fast;
if (head == NULL || head->next == NULL)
{
*head1 = head;
*head2 = NULL;
return 0;
}
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;
return 0;
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- js單向鏈表的具體實現(xiàn)實例
- JavaScript 雙向鏈表操作實例分析【創(chuàng)建、增加、查找、刪除等】
- JavaScript將數(shù)組轉(zhuǎn)換為鏈表的方法
- JS中的算法與數(shù)據(jù)結(jié)構(gòu)之鏈表(Linked-list)實例詳解
- JS實現(xiàn)的合并兩個有序鏈表算法示例
- 使用JavaScript實現(xiàn)鏈表的數(shù)據(jù)結(jié)構(gòu)的代碼
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表的實現(xiàn)
- javascript循環(huán)鏈表之約瑟夫環(huán)的實現(xiàn)方法
- JS使用單鏈表統(tǒng)計英語單詞出現(xiàn)次數(shù)
- JavaScript封裝單向鏈表的示例代碼
