Heim > Artikel > Web-Frontend > JavaScript implementiert die Einfügungssortierung verknüpfter Listen und die Zusammenführungssortierung verknüpfter Listen

JavaScript implementiert die Einfügungssortierung verknüpfter Listen und die Zusammenführungssortierung verknüpfter Listen

高洛峰Original: 2016-12-29 15:50:171276Durchsuche

In diesem Artikel wird die JavaScript-Implementierung der Einfügungssortierung verknüpfter Listen und der Zusammenführungssortierung verknüpfter Listen ausführlich vorgestellt. Bei der Zusammenführungssortierung verknüpfter Listen werden die einzelnen Teile zusammengeführt, sortiert und dann zusammengeführt.

1. Verknüpfte Liste

1.1 Speicherdarstellung der verknüpften Liste

//链表的存储表示
typedef int ElemType;
typedef struct LNode
{
  ElemType data;
  struct LNode *next;
}LNode, *LinkList;

1.2 Grundoperationen

Erstellen Verknüpfte Liste:

/*
 * 创建链表。
 * 形参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;
}

Ausgabe der verknüpften Liste:

/*
 * 输出链表结点值。
 */
int PrintLink(LinkList head)
{
  LinkList p;
  for (p = head; p ;p = p->next)
  {
    printf("%-3d ", p->data);
  }
  return 0;
}

2. Sortierung der verknüpften Liste

Grundidee: Nehmen Sie an, dass die erste n-1 Knoten sind in Ordnung, und der n-te Knoten wird an der entsprechenden Position des vorherigen Knotens eingefügt, um diese n Knoten in Ordnung zu bringen.

Implementierungsmethode:

Zerlegen Sie den ersten Knoten in der verknüpften Liste ab, um eine verknüpfte Liste zu werden, die einen Knoten (Kopf1) enthält, und die verbleibenden Knoten werden natürlich zu einem anderen Eine verknüpfte Liste (Kopf2), zu diesem Zeitpunkt ist Kopf1 eine geordnete verknüpfte Liste, die einen Knoten enthält.

Entfernen Sie den ersten Knoten aus der verknüpften Liste Kopf2 und fügen Sie ihn in die verknüpfte Liste ein Listen Sie head1 an der entsprechenden Position auf, sodass head1 noch in Ordnung ist. Zu diesem Zeitpunkt wird head1 zu einer geordneten verknüpften Liste mit zwei Knoten.

entfernt nacheinander einen Knoten aus der verknüpften Liste head2 und fügt ihn in die ein Kopf1 der verknüpften Liste. Bis der Kopf2 der verknüpften Liste eine leere verknüpfte Liste ist. Schließlich enthält die verknüpfte Liste head1 alle Knoten und die Knoten sind in der richtigen Reihenfolge.

Einfügungssortiercode:

Vollständiger Quellcode:

/*
 * 链表插入排序(由小到大)。
 * 输入：链表的头指针，
 * 输出：排序后链表的头指针。
 * 实现方法：将原链表拆成两部分：链表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;
}

3. Sortierung der verknüpften Liste

/*
 * 链表插入排序，由小到大
 */
#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;
}

Grundidee: Wenn die verknüpfte Liste leer ist oder einen Knoten enthält, ist die verknüpfte Liste natürlich geordnet. Andernfalls teilen Sie die verknüpfte Liste in zwei Teile auf, sortieren jeden Teil einzeln zusammen und führen dann die beiden sortierten verknüpften Listen zusammen.

Sortiercode zusammenführen:

Die Grundidee ist die Verwendung langsamer/schneller Zeiger für die spezifische Implementierungsmethode .

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

Die Funktion zum Zusammenführen verknüpfter Listen verfügt über zwei Methoden: rekursive Implementierung und nicht rekursive Implementierung:

/*
 * 链表分割函数。
 * 将链表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;
}

Nicht rekursive Implementierung:

Rekursiv Implementierung:

/*
 * 链表归并。
 * 将两个有序的链表归并在一起，使总链表有序。
 * 输入：链表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;
}

Vollständiger Quellcode:

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;
}

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass er für das Lernen aller hilfreich sein wird wird die chinesische PHP-Website unterstützen.

/*
* 链表归并排序，由小到大。
*/
#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;
}

Weitere JavaScript-Implementierungen für die Sortierung verknüpfter Listen und die Sortierung verknüpfter Listen finden Sie auf der chinesischen PHP-Website!

Stellungnahme：

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Vorheriger Artikel：Implementierungsmethode zum Konvertieren einer dynamischen JSP-Seite in eine PDF-Ausgabe in eine SeiteNächster Artikel：Implementierungsmethode zum Konvertieren einer dynamischen JSP-Seite in eine PDF-Ausgabe in eine Seite

In Verbindung stehende Artikel

Mehr sehen