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;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
JavaScript数据结构和算法之二叉树详解
二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct
-
js单向链表的具体实现实例
复制代码 代码如下: function linkNode(_key, _value){ /// <summary> /// 链表类的节点类 /// </summary> this.Key = _key; this.Value = _value; this.next = null;}function Link(){ /// <summary> /// 创建一个链表类 /// </summary> th
-
JavaScript数据结构之链表的实现
前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一
-
javascript数据结构之双链表插入排序实例详解
本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t
-
js实现双向链表互联网机顶盒实战应用实现
上实战代码: linkedlistnode.js 节点类 复制代码 代码如下: /* * 链表节点 */ Dare.LinkedListNode = function () { this.data = null;//数据域 this.prev = null;//前驱 this.next = null;//后驱 }; Dare.extend(Dare.LinkedListNode, Dare); Dare.LinkedListNode.prototype.getValue = function (
-
JavaScript数据结构和算法之图和图算法
图的定义 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合. 有向图 有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头. 无序图 无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示. 简单图 简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,
-
JavaScript数据结构之双向链表定义与使用方法示例
本文实例讲述了JavaScript数据结构之双向链表定义与使用方法.分享给大家供大家参考,具体如下: 双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素. 双向链表提供了两种迭代列表的方法:从头到尾,或者反过来.我们也可以访问一个特定节点的下一个或前一个元素.在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代.这是双向链表的一个优点. function DoubleLink(
-
Node.js环境下JavaScript实现单链表与双链表结构
单链表(LinkedList)的javascript实现 npmjs相关库: complex-list.smart-list.singly-linked-list 编程思路: add方法用于将元素追加到链表尾部,借由insert方法来实现: 注意各个函数的边界条件处理. 自己的实现: SingleNode.js (function(){ "use strict"; function Node(element){ this.element = element; this.next = n
-
javascript循环链表之约瑟夫环的实现方法
前言 传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围.犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案.他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人.约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存.写一段程序将n 个人围成一圈,并且第m个人会被杀掉,计算一圈人中哪两个人最后会存活.使用循环链表解决该问题. 看到这个问题首先想到的是要用到循环链表,还有就是要计算
-
JavaScript数组实现数据结构中的队列与堆栈
一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组
-
使用JavaScript实现链表的数据结构的代码
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer) - 维基百科 上面是维基百科对 链表 的解读.下面我们用 JavaScript 代码对链表的数据结构进行实现 实现Node类表示节点 /** * Node 类用来表示节点 * element 用来保存节点上的数据 * next 用来保存指向下一个节点的链接 */ function Node(element) { this.elemen
-
JavaScript实现的链表数据结构实例
此例是javascript来建立链表.. 并对此进行了排序.. 还可以在GenericList一般链表上进行扩展. 实现各种排序及增,删,改结点.. 复制代码 代码如下: function Node(){ this.data=null; this.next=null; } function GenericList(){ this.head=null; this.current=null; //打出所有的链表结点 this.print= function(){ this