ホームページ > 記事 > ウェブフロントエンド > JavaScript はリンク リストの挿入ソートとリンク リストのマージ ソートを実装します。
この記事では、リンク リスト挿入ソートとリンク リスト マージ ソートの JavaScript 実装を詳しく紹介します。
1. リンクリスト
1.1 リンクリストの格納表現
//链表的存储表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList;
1.2 基本操作
リンクリストの作成:
/* * 创建链表。 * 形参num为链表的长度,函数返回链表的头指针。 */ LinkList CreatLink(int num) { int i, data; //p指向当前链表中最后一个结点,q指向准备插入的结点。 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; }
リンクリストの出力:
/* * 输出链表结点值。 */ int PrintLink(LinkList head) { LinkList p; for (p = head; p ;p = p->next) { printf("%-3d ", p->data); } return 0; }
2. リンクリストの挿入ソート
: n-1 ノードが順番にあると仮定し、n 番目のノードを前のノードの適切な位置に挿入して、これらの n ノードが順番になるようにします。
実装方法:
連結リストの最初のノードを削除すると、1つのノードを含む連結リスト(head1)になり、残りのノードは自然に別の連結リスト(head2)になります。このとき、head1には
が含まれます。1 つのノードの順序付けされたリンク リスト;
リンク リスト head2 の最初のノードを削除し、それをリンク リスト head1 の適切な位置に挿入して、head1 が順序付けされたままになるようにします。 2 つのノード。リンク リスト。
リンク リスト head2 が空になるまで、リンク リスト head2 からノードを順番に削除し、リンク リスト head1 に挿入します。最後に、リンク リスト head1 にはすべてのノードが含まれており、ノードは順番に並んでいます。
挿入ソートコード:
/* * 链表插入排序(由小到大)。 * 输入:链表的头指针, * 输出:排序后链表的头指针。 * 实现方法:将原链表拆成两部分:链表1仍以head为头指针,链表结点有序。链表2以head2为头指针,链表结点无序。 * 将链表2中的结点依次插入到链表1中,并保持链表1有序。 * 最后链表1中包含所有结点,且有序。 */ LinkList LinkInsertSort(LinkList head) { //current指向当前待插入的结点。 LinkList head2, current, p, q; if (head == NULL) return head; //第一次拆分。 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; } return head; }
完全なソースコード:
/* * 链表插入排序,由小到大 */ #define _CRT_SECURE_NO_WARNINGS #include#include #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); /* * 创建链表。 * 形参num为链表的长度,函数返回链表的头指针。 */ LinkList CreatLink(int num) { int i, data; //p指向当前链表中最后一个结点,q指向准备插入的结点。 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; } /* * 链表插入排序(由小到大)。 * 输入:链表的头指针, * 输出:排序后链表的头指针。 * 实现方法:将原链表拆成两部分:链表1仍以head为头指针,链表结点有序。链表2以head2为头指针,链表结点无序。 * 将链表2中的结点依次插入到链表1中,并保持链表1有序。 * 最后链表1中包含所有结点,且有序。 */ LinkList LinkInsertSort(LinkList head) { //current指向当前待插入的结点。 LinkList head2, current, p, q; if (head == NULL) return head; //第一次拆分。 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; } return head; } /* * 输出链表结点值。 */ 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个数以创建链表:\n"); head = CreatLink(TOTAL); head = LinkInsertSort(head); printf("排序后:\n"); PrintLink(head); putchar('\n'); return 0; }
3. リンクリストのマージソート
基本的な考え方: リンクリストが空であるか、ノードが含まれている場合、リンクリストは自然に順序付けされます。それ以外の場合は、リンク リストを 2 つの部分に分割し、各部分を個別にマージ ソートしてから、ソートされた 2 つのリンク リストをマージします。
マージソートコード:
/* * 链表归并排序(由小到大)。 * 输入:链表的头指针, * 输出:排序后链表的头指针。 * 递归实现方法:将链表head分为两部分,分别进行归并排序,再将排序后的两部分归并在一起。 * 递归结束条件:进行递归排序的链表为空或者只有一个结点。 */ 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; }
リンクリスト分割関数は次のとおりです。具体的な実装方法については、コメントを参照してください。
/* * 链表分割函数。 * 将链表head均分为两部分head1和head2,若链表长度为奇数,多出的结点从属于第一部分。 * 实现方法:首先使指针slow/fast指向链首, * 然后使fast指针向前移动两个结点的同时,slow指针向前移动一个结点, * 循环移动,直至fast指针指向链尾。结束时,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; }
リンクリストマージ関数には再帰実装と非再帰実装の2つの方法があります:
非再帰実装:
/* * 链表归并。 * 将两个有序的链表归并在一起,使总链表有序。 * 输入:链表head1和链表head2 * 输出:归并后的链表 * 实现方法:将链表head2中的结点依次插入到链表head1中的适当位置,使head1仍为有序链表。 */ LinkList LinkMerge(LinkList head1, LinkList head2) { LinkList p, q, t; if (!head1) return head2; if (!head2) return head1; //循环变量的初始化,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; } 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; }
完全なソースコード:
/* * 链表归并排序,由小到大。 */ #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); /* * 创建链表。 * 形参num为链表的长度,函数返回链表的头指针。 */ LinkList CreatLink(int num) { int i, data; //p指向当前链表中最后一个结点,q指向准备插入的结点。 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; } /* * 输出链表结点值。 */ 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个数以创建链表:\n"); head = CreatLink(TOTAL); head = LinkMergeSort(head); printf("排序后:\n"); PrintLink(head); putchar('\n'); return 0; } /* * 链表归并排序(由小到大)。 * 输入:链表的头指针, * 输出:排序后链表的头指针。 * 递归实现方法:将链表head分为两部分,分别进行归并排序,再将排序后的两部分归并在一起。 * 递归结束条件:进行递归排序的链表为空或者只有一个结点。 */ 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); //非递归实现 //head = LinkMerge2(head1, head2); //递归实现 return head; } /* * 链表归并。 * 将两个有序的链表归并在一起,使总链表有序。 * 输入:链表head1和链表head2 * 输出:归并后的链表 * 实现方法:将链表head2中的结点依次插入到链表head1中的适当位置,使head1仍为有序链表。 */ LinkList LinkMerge(LinkList head1, LinkList head2) { LinkList p, q, t; if (!head1) return head2; if (!head2) return head1; //循环变量的初始化,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; } 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; } /* * 链表分割函数。 * 将链表head均分为两部分head1和head2,若链表长度为奇数,多出的结点从属于第一部分。 * 实现方法:首先使指针slow/fast指向链首, * 然后使fast指针向前移动两个结点的同时,slow指针向前移动一个结点, * 循环移动,直至fast指针指向链尾。结束时,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; }
上記が全内容ですこの記事の内容が皆様のお役に立てば幸いです。 この学習は役に立ちますので、皆様にも PHP 中国語 Web サイトをサポートしていただければ幸いです。
リンク リスト挿入ソートおよびリンク リスト マージ ソートの JavaScript 実装に関する詳細については、PHP 中国語 Web サイトに注目してください。