JavaScript實(shí)現(xiàn)鏈表插入排序和鏈表歸并排序
本篇文章詳細(xì)的介紹了JavaScript實(shí)現(xiàn)鏈表插入排序和鏈表歸并排序,鏈表的歸并排序就是對(duì)每個(gè)部分都進(jìn)行歸并排序,然后合并在一起。
1.鏈表
1.1鏈表的存儲(chǔ)表示
//鏈表的存儲(chǔ)表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList;
1.2基本操作
創(chuàng)建鏈表:
/* * 創(chuàng)建鏈表。 * 形參num為鏈表的長(zhǎng)度,函數(shù)返回鏈表的頭指針。 */ LinkList CreatLink(int num) { int i, data; //p指向當(dāng)前鏈表中最后一個(gè)結(jié)點(diǎn),q指向準(zhǔn)備插入的結(jié)點(diǎn)。 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é)點(diǎn)值。 */ int PrintLink(LinkList head) { LinkList p; for (p = head; p ;p = p->next) { printf("%-3d ", p->data); } return 0; }
2.鏈表插入排序
基本思想:假設(shè)前面n-1個(gè)結(jié)點(diǎn)有序,將第n個(gè)結(jié)點(diǎn)插入到前面結(jié)點(diǎn)的適當(dāng)位置,使這n個(gè)結(jié)點(diǎn)有序。
實(shí)現(xiàn)方法:
將鏈表上第一個(gè)結(jié)點(diǎn)拆下來(lái),成為含有一個(gè)結(jié)點(diǎn)的鏈表(head1),其余的結(jié)點(diǎn)自然成為另外一個(gè)鏈表(head2),此時(shí)head1為含有
一個(gè)結(jié)點(diǎn)的有序鏈表;
將鏈表head2上第一個(gè)結(jié)點(diǎn)拆下來(lái),插入到鏈表head1的適當(dāng)位置,使head1仍有序,此時(shí)head1成為含有兩個(gè)結(jié)點(diǎn)的有序鏈表;
依次從鏈表head2上拆下一個(gè)結(jié)點(diǎn),插入到鏈表head1中,直到鏈表head2為空鏈表為止。最后,鏈表head1上含所有結(jié)點(diǎn),且結(jié)點(diǎn)有序。
插入排序代碼:
/* * 鏈表插入排序(由小到大)。 * 輸入:鏈表的頭指針, * 輸出:排序后鏈表的頭指針。 * 實(shí)現(xiàn)方法:將原鏈表拆成兩部分:鏈表1仍以head為頭指針,鏈表結(jié)點(diǎn)有序。鏈表2以head2為頭指針,鏈表結(jié)點(diǎn)無(wú)序。 * 將鏈表2中的結(jié)點(diǎn)依次插入到鏈表1中,并保持鏈表1有序。 * 最后鏈表1中包含所有結(jié)點(diǎn),且有序。 */ LinkList LinkInsertSort(LinkList head) { //current指向當(dāng)前待插入的結(jié)點(diǎn)。 LinkList head2, current, p, q; if (head == NULL) return head; //第一次拆分。 head2 = head->next; head->next = NULL; while (head2) { current = head2; head2 = head2->next; //尋找插入位置,插入位置為結(jié)點(diǎn)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 //鏈表長(zhǎng)度 //鏈表的存儲(chǔ)表示 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為鏈表的長(zhǎng)度,函數(shù)返回鏈表的頭指針。 */ LinkList CreatLink(int num) { int i, data; //p指向當(dāng)前鏈表中最后一個(gè)結(jié)點(diǎn),q指向準(zhǔn)備插入的結(jié)點(diǎn)。 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; } /* * 鏈表插入排序(由小到大)。 * 輸入:鏈表的頭指針, * 輸出:排序后鏈表的頭指針。 * 實(shí)現(xiàn)方法:將原鏈表拆成兩部分:鏈表1仍以head為頭指針,鏈表結(jié)點(diǎn)有序。鏈表2以head2為頭指針,鏈表結(jié)點(diǎn)無(wú)序。 * 將鏈表2中的結(jié)點(diǎn)依次插入到鏈表1中,并保持鏈表1有序。 * 最后鏈表1中包含所有結(jié)點(diǎn),且有序。 */ LinkList LinkInsertSort(LinkList head) { //current指向當(dāng)前待插入的結(jié)點(diǎn)。 LinkList head2, current, p, q; if (head == NULL) return head; //第一次拆分。 head2 = head->next; head->next = NULL; while (head2) { current = head2; head2 = head2->next; //尋找插入位置,插入位置為結(jié)點(diǎn)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é)點(diǎn)值。 */ 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個(gè)數(shù)以創(chuàng)建鏈表:\n"); head = CreatLink(TOTAL); head = LinkInsertSort(head); printf("排序后:\n"); PrintLink(head); putchar('\n'); return 0; }
3.鏈表歸并排序
基本思想:如果鏈表為空或者含有一個(gè)結(jié)點(diǎn),鏈表自然有序。否則,將鏈表分成兩部分,對(duì)每一部分分別進(jìn)行歸并排序,然后將已排序的兩個(gè)鏈表歸并在一起。
歸并排序代碼:
/* * 鏈表歸并排序(由小到大)。 * 輸入:鏈表的頭指針, * 輸出:排序后鏈表的頭指針。 * 遞歸實(shí)現(xiàn)方法:將鏈表head分為兩部分,分別進(jìn)行歸并排序,再將排序后的兩部分歸并在一起。 * 遞歸結(jié)束條件:進(jìn)行遞歸排序的鏈表為空或者只有一個(gè)結(jié)點(diǎn)。 */ 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指針,具體實(shí)現(xiàn)方法見(jiàn)注釋。
/* * 鏈表分割函數(shù)。 * 將鏈表head均分為兩部分head1和head2,若鏈表長(zhǎng)度為奇數(shù),多出的結(jié)點(diǎn)從屬于第一部分。 * 實(shí)現(xiàn)方法:首先使指針slow/fast指向鏈?zhǔn)祝? * 然后使fast指針向前移動(dòng)兩個(gè)結(jié)點(diǎn)的同時(shí),slow指針向前移動(dòng)一個(gè)結(jié)點(diǎn), * 循環(huán)移動(dòng),直至fast指針指向鏈尾。結(jié)束時(shí),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ù)有遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)兩種方法:
非遞歸實(shí)現(xiàn):
/* * 鏈表歸并。 * 將兩個(gè)有序的鏈表歸并在一起,使總鏈表有序。 * 輸入:鏈表head1和鏈表head2 * 輸出:歸并后的鏈表 * 實(shí)現(xiàn)方法:將鏈表head2中的結(jié)點(diǎn)依次插入到鏈表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é)點(diǎn),p為q的前驅(qū)。 p = NULL; q = head1; while (head2) { //t為待插入結(jié)點(diǎn)。 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é)點(diǎn)t插入到p和q之間后,使p重新指向q的前驅(qū)。 p = t; } return head1; }
遞歸實(shí)現(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 //鏈表長(zhǎng)度 //鏈表的存儲(chǔ)表示 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為鏈表的長(zhǎng)度,函數(shù)返回鏈表的頭指針。 */ LinkList CreatLink(int num) { int i, data; //p指向當(dāng)前鏈表中最后一個(gè)結(jié)點(diǎn),q指向準(zhǔn)備插入的結(jié)點(diǎn)。 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é)點(diǎn)值。 */ 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個(gè)數(shù)以創(chuàng)建鏈表:\n"); head = CreatLink(TOTAL); head = LinkMergeSort(head); printf("排序后:\n"); PrintLink(head); putchar('\n'); return 0; } /* * 鏈表歸并排序(由小到大)。 * 輸入:鏈表的頭指針, * 輸出:排序后鏈表的頭指針。 * 遞歸實(shí)現(xiàn)方法:將鏈表head分為兩部分,分別進(jìn)行歸并排序,再將排序后的兩部分歸并在一起。 * 遞歸結(jié)束條件:進(jìn)行遞歸排序的鏈表為空或者只有一個(gè)結(jié)點(diǎn)。 */ 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); //非遞歸實(shí)現(xiàn) //head = LinkMerge2(head1, head2); //遞歸實(shí)現(xiàn) return head; } /* * 鏈表歸并。 * 將兩個(gè)有序的鏈表歸并在一起,使總鏈表有序。 * 輸入:鏈表head1和鏈表head2 * 輸出:歸并后的鏈表 * 實(shí)現(xiàn)方法:將鏈表head2中的結(jié)點(diǎn)依次插入到鏈表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é)點(diǎn),p為q的前驅(qū)。 p = NULL; q = head1; while (head2) { //t為待插入結(jié)點(diǎn)。 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é)點(diǎn)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,若鏈表長(zhǎng)度為奇數(shù),多出的結(jié)點(diǎn)從屬于第一部分。 * 實(shí)現(xiàn)方法:首先使指針slow/fast指向鏈?zhǔn)祝? * 然后使fast指針向前移動(dòng)兩個(gè)結(jié)點(diǎn)的同時(shí),slow指針向前移動(dòng)一個(gè)結(jié)點(diǎn), * 循環(huán)移動(dòng),直至fast指針指向鏈尾。結(jié)束時(shí),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; }
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
- js單向鏈表的具體實(shí)現(xiàn)實(shí)例
- JavaScript 雙向鏈表操作實(shí)例分析【創(chuàng)建、增加、查找、刪除等】
- JavaScript將數(shù)組轉(zhuǎn)換為鏈表的方法
- JS中的算法與數(shù)據(jù)結(jié)構(gòu)之鏈表(Linked-list)實(shí)例詳解
- JS實(shí)現(xiàn)的合并兩個(gè)有序鏈表算法示例
- 使用JavaScript實(shí)現(xiàn)鏈表的數(shù)據(jù)結(jié)構(gòu)的代碼
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表的實(shí)現(xiàn)
- javascript循環(huán)鏈表之約瑟夫環(huán)的實(shí)現(xiàn)方法
- JS使用單鏈表統(tǒng)計(jì)英語(yǔ)單詞出現(xiàn)次數(shù)
- JavaScript封裝單向鏈表的示例代碼
相關(guān)文章
JSP學(xué)習(xí)經(jīng)驗(yàn)小結(jié)分享
本文介紹的是JSP的學(xué)習(xí)經(jīng)驗(yàn)總結(jié),希望對(duì)你有幫助,一起來(lái)看。2015-09-09基于jsp實(shí)現(xiàn)新聞管理系統(tǒng) 附完整源碼
這篇文章主要介紹了基于jsp的新聞管理系統(tǒng),具有一定的參考價(jià)值,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-09-09Action中ArrayList顯示到JSP頁(yè)面的具體實(shí)例
UserAciton中通過(guò)hibernate查詢(xún)到的數(shù)據(jù)保存到ArrayList中,JSP頁(yè)面希望表格輸出ArrayList對(duì)象,有兩種方法,有需要的朋友可以參考一下2013-09-09JAVA/JSP學(xué)習(xí)系列之八(改寫(xiě)MySQL翻頁(yè)例子)
JAVA/JSP學(xué)習(xí)系列之八(改寫(xiě)MySQL翻頁(yè)例子)...2006-10-10JSP 中response.setContentType()的作用及參數(shù)
這篇文章主要介紹了JSP 中response.setContentType()的作用及參數(shù) 的相關(guān)資料,希望通過(guò)本能幫助到大家,讓大家理解使用這部分內(nèi)容,需要的朋友可以參考下2017-09-09用連接池提高Servlet訪問(wèn)數(shù)據(jù)庫(kù)的效率(2)
用連接池提高Servlet訪問(wèn)數(shù)據(jù)庫(kù)的效率(2)...2006-10-10