搜索
首页web前端js教程JavaScript实现链表插入排序和链表归并排序

JavaScript实现链表插入排序和链表归并排序

高洛峰
高洛峰
Dec 29, 2016 pm 03:50 PM

本篇文章详细的介绍了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 
#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.链表归并排序

基本思想：如果链表为空或者含有一个结点，链表自然有序。否则，将链表分成两部分，对每一部分分别进行归并排序，然后将已排序的两个链表归并在一起。

归并排序代码：

/*
 * 链表归并排序(由小到大)。
 * 输入：链表的头指针，
 * 输出：排序后链表的头指针。
 * 递归实现方法：将链表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(&#39;\n&#39;);
  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中文网。

更多JavaScript实现链表插入排序和链表归并排序相关文章请关注PHP中文网！


声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
相关文章
JavaScript和Web：核心功能和用例JavaScript和Web：核心功能和用例Apr 18, 2025 am 12:19 AM

JavaScript在Web开发中的主要用途包括客户端交互、表单验证和异步通信。1)通过DOM操作实现动态内容更新和用户交互；2)在用户提交数据前进行客户端验证，提高用户体验；3)通过AJAX技术实现与服务器的无刷新通信。

了解JavaScript引擎：实施详细信息了解JavaScript引擎：实施详细信息Apr 17, 2025 am 12:05 AM

理解JavaScript引擎内部工作原理对开发者重要，因为它能帮助编写更高效的代码并理解性能瓶颈和优化策略。1)引擎的工作流程包括解析、编译和执行三个阶段；2)执行过程中，引擎会进行动态优化，如内联缓存和隐藏类；3)最佳实践包括避免全局变量、优化循环、使用const和let，以及避免过度使用闭包。

Python vs. JavaScript：学习曲线和易用性Python vs. JavaScript：学习曲线和易用性Apr 16, 2025 am 12:12 AM

Python更适合初学者，学习曲线平缓，语法简洁；JavaScript适合前端开发，学习曲线较陡，语法灵活。1.Python语法直观，适用于数据科学和后端开发。2.JavaScript灵活，广泛用于前端和服务器端编程。

Python vs. JavaScript：社区，图书馆和资源Python vs. JavaScript：社区，图书馆和资源Apr 15, 2025 am 12:16 AM

Python和JavaScript在社区、库和资源方面的对比各有优劣。1)Python社区友好，适合初学者，但前端开发资源不如JavaScript丰富。2)Python在数据科学和机器学习库方面强大，JavaScript则在前端开发库和框架上更胜一筹。3)两者的学习资源都丰富，但Python适合从官方文档开始，JavaScript则以MDNWebDocs为佳。选择应基于项目需求和个人兴趣。

从C/C到JavaScript：所有工作方式从C/C到JavaScript：所有工作方式Apr 14, 2025 am 12:05 AM

从C/C 转向JavaScript需要适应动态类型、垃圾回收和异步编程等特点。1）C/C 是静态类型语言，需手动管理内存，而JavaScript是动态类型，垃圾回收自动处理。2）C/C 需编译成机器码，JavaScript则为解释型语言。3）JavaScript引入闭包、原型链和Promise等概念，增强了灵活性和异步编程能力。

JavaScript引擎：比较实施JavaScript引擎：比较实施Apr 13, 2025 am 12:05 AM

不同JavaScript引擎在解析和执行JavaScript代码时，效果会有所不同，因为每个引擎的实现原理和优化策略各有差异。1.词法分析：将源码转换为词法单元。2.语法分析：生成抽象语法树。3.优化和编译：通过JIT编译器生成机器码。4.执行：运行机器码。V8引擎通过即时编译和隐藏类优化，SpiderMonkey使用类型推断系统，导致在相同代码上的性能表现不同。

超越浏览器：现实世界中的JavaScript超越浏览器：现实世界中的JavaScriptApr 12, 2025 am 12:06 AM

JavaScript在现实世界中的应用包括服务器端编程、移动应用开发和物联网控制：1.通过Node.js实现服务器端编程，适用于高并发请求处理。2.通过ReactNative进行移动应用开发，支持跨平台部署。3.通过Johnny-Five库用于物联网设备控制，适用于硬件交互。

使用Next.js（后端集成）构建多租户SaaS应用程序使用Next.js（后端集成）构建多租户SaaS应用程序Apr 11, 2025 am 08:23 AM

我使用您的日常技术工具构建了功能性的多租户SaaS应用程序（一个Edtech应用程序），您可以做同样的事情。 首先，什么是多租户SaaS应用程序？ 多租户SaaS应用程序可让您从唱歌中为多个客户提供服务

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

显示更多

热门文章

R.E.P.O.能量晶体解释及其做什么（黄色晶体）
1 个月前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
1 个月前By尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
3 周前ByDDD
Windows 11 KB5054979中的新功能以及如何解决更新问题
2 周前ByDDD
威尔R.E.P.O.有交叉游戏吗？
1 个月前By尊渡假赌尊渡假赌尊渡假赌
显示更多

热工具

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

WebStorm Mac版

WebStorm Mac版

好用的JavaScript开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序，非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具，帮助Web开发人员更好地理解保护Web应用程序的过程，并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞，难度各不相同。请注意，该软件中

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

显示更多

热门话题

gmail邮箱登陆入口在哪里
7548
15
CakePHP 教程
1382
52
steam的账户名称是什么格式
83
11
win11激活密钥永久
57
19
NYT连接提示和答案
22
90
显示更多