지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > 웹 프론트엔드 > JS 튜토리얼 > 본문

JavaScript는 연결 목록 삽입 정렬 및 연결 목록 병합 정렬을 구현합니다.

高洛峰
풀어 주다： 2016-12-29 15:50:17
원래의
1316명이 탐색했습니다.

이 기사에서는 연결 목록 삽입 정렬과 연결 목록 병합 정렬의 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은 두 개의 노드를 포함하는 순서 연결 리스트가 됩니다.

연결 리스트 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;
}
로그인 후 복사

연결된 목록 분할 기능은 기본 아이디어는 느린/빠른 포인터를 사용하는 것입니다. 구체적인 구현 방법은 주석을 참조하세요. . 

/*
 * 链表分割函数。
 * 将链表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 중국어 웹사이트에 주목하세요!


관련 라벨：
JavaScript 链表 归并
원천：php.cn
이전 기사：동적 jsp 페이지를 PDF 출력으로 페이지로 변환하는 구현 방법 다음 기사：JS는 버블 정렬, 삽입 정렬 및 빠른 정렬을 구현하고 출력을 정렬합니다.
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
Javascript/Jquery를 사용하여 버튼 없이 양식 제출 JavaScript 함수를 호출하고 JQUERY/PHP를 사용하여 양식을 실행하여 버튼 없이 양식을 제출하려고 합니다. 페이지를 다시 로드하지 않고 백엔드에서 양...
에서 2024-04-06 14:54:03
0
2
421
Zoom URL을 가로채는 Cypress 테스트 Zoom 링크로 리디렉션되는 테스트 사례가 있습니다. 테스트를 올바르게 완료하고 브라우저 세션을 중단하고 JavaScript 실행을 중지하지 않고 브라우저가 실제...
에서 2024-04-04 16:16:37
0
1
340
CSS: 목록 항목 사이의 간격 수정 목록의 CSS를 편집하려고 시도했지만 행으로 올바르게 이동하고 목록 요소 사이의 높이를 조정하는 방법을 찾지 못했습니다. 웹사이트 링크: https://denki...
에서 2024-04-02 15:46:38
0
1
342
요소 내에서 여러 항목 정렬: 단계별 가이드 하나의 요소 안에 다른 항목을 정렬하고 싶습니다! Element에 flexbox를 제공하고 그 안의 항목을 직접 조정해 보았습니다! 하지만 제대로 반응하지 않습니...
에서 2024-04-01 23:21:40
0
2
366
vue-router를 사용하여 API의 테이블 데이터 하이퍼링크 API(https://restcountries.com/)에서 데이터를 가져와 표시하고 있지만 라우터 링크 태그를 사용하여 각 테이블 항목을 자체 페이지에 하이퍼링...
에서 2024-03-30 14:06:41
0
1
417
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿