45fan.com - 路饭网

搜索: 您的位置主页 > 电脑频道 > 编程代码 > 阅读资讯:如何通过JavaScript实现链表插入排序和归并?

如何通过JavaScript实现链表插入排序和归并?

2016-11-23 20:22:39 来源:www.45fan.com 【

如何通过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.45fan.com/bcdm/84001.html
Tags: 实现 JavaScript 链表
编辑:路饭网
推广内容
推荐阅读
热门推荐
推荐文章
关于我们 | 联系我们 | 友情链接 | 网站地图 | Sitemap | App | 返回顶部