这里有新鲜出炉的 Javascript 教程,程序狗速度看过来!
Javascript 是一种由 Netscape 的 LiveScript 发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言,主要目的是为了解决服务器端语言,比如 Perl,遗留的速度问题,为客户提供更流畅的浏览效果。
这篇文章主要介绍了 JavaScript 实现链表插入排序和链表归并排序, 较为详细的分析了插入排序和归并排序, 对于学习 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 个结点有序。
实现方法:
将链表上第一个结点拆下来,成为含有一个结点的链表 (head1),其余的结点自然成为另外一个链表 (head2),此时 head1 为含有
一个结点的有序链表;
将链表 head2 上第一个结点拆下来,插入到链表 head1 的适当位置,使 head1 仍有序,此时 head1 成为含有两个结点的有序链表;
依次从链表 head2 上拆下一个结点,插入到链表 head1 中,直到链表 head2 为空链表为止。最后,链表 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 < 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);
- /*
- * 创建链表。
- * 形参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. 链表归并排序
基本思想:如果链表为空或者含有一个结点,链表自然有序。否则,将链表分成两部分,对每一部分分别进行归并排序,然后将已排序的两个链表归并在一起。
归并排序代码:
- /*
- * 链表归并排序(由小到大)。
- * 输入:链表的头指针,
- * 输出:排序后链表的头指针。
- * 递归实现方法:将链表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;
- }
其中链表分割函数如下,基本思想是利用 slow/fast 指针,具体实现方法见注释。
- /*
- * 链表分割函数。
- * 将链表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;
- }
链表归并函数有递归实现和非递归实现两种方法:
非递归实现:
- /*
- * 链表归并。
- * 将两个有序的链表归并在一起,使总链表有序。
- * 输入:链表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;
- }
来源: http://www.phperz.com/article/17/0811/339043.html