JavaScript는 연결 목록 삽입 정렬 및 연결 목록 병합 정렬을 구현합니다.-JS 튜토리얼-php.cn

집

웹 프론트엔드

JS 튜토리얼

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은 두 개의 노드를 포함하는 순서 연결 리스트가 됩니다.

연결 리스트 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 중국어 웹사이트에 주목하세요!

본 웹사이트의 성명

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

뜨거운 주제

Gmail 이메일의 로그인 입구는 어디에 있나요?

7640

Cakephp 튜토리얼

1391

Steam의 계정 이름 형식은 무엇입니까?

Win11 활성화 키 영구

NYT 연결 힌트와 답변

150

Related knowledge

프론트 엔드 열 용지 영수증에 대한 차량 코드 인쇄를 만나면 어떻게해야합니까? Apr 04, 2025 pm 02:42 PM

프론트 엔드 개발시 프론트 엔드 열지대 티켓 인쇄를위한 자주 묻는 질문과 솔루션, 티켓 인쇄는 일반적인 요구 사항입니다. 그러나 많은 개발자들이 구현하고 있습니다 ...

누가 더 많은 파이썬이나 자바 스크립트를 지불합니까? Apr 04, 2025 am 12:09 AM

기술 및 산업 요구에 따라 Python 및 JavaScript 개발자에 대한 절대 급여는 없습니다. 1. 파이썬은 데이터 과학 및 기계 학습에서 더 많은 비용을 지불 할 수 있습니다. 2. JavaScript는 프론트 엔드 및 풀 스택 개발에 큰 수요가 있으며 급여도 상당합니다. 3. 영향 요인에는 경험, 지리적 위치, 회사 규모 및 특정 기술이 포함됩니다.

Demystifying JavaScript : 그것이하는 일과 중요한 이유 Apr 09, 2025 am 12:07 AM

JavaScript는 현대 웹 개발의 초석이며 주요 기능에는 이벤트 중심 프로그래밍, 동적 컨텐츠 생성 및 비동기 프로그래밍이 포함됩니다. 1) 이벤트 중심 프로그래밍을 사용하면 사용자 작업에 따라 웹 페이지가 동적으로 변경 될 수 있습니다. 2) 동적 컨텐츠 생성을 사용하면 조건에 따라 페이지 컨텐츠를 조정할 수 있습니다. 3) 비동기 프로그래밍은 사용자 인터페이스가 차단되지 않도록합니다. JavaScript는 웹 상호 작용, 단일 페이지 응용 프로그램 및 서버 측 개발에 널리 사용되며 사용자 경험 및 크로스 플랫폼 개발의 유연성을 크게 향상시킵니다.

JavaScript를 사용하여 동일한 ID와 동일한 ID로 배열 요소를 하나의 객체로 병합하는 방법은 무엇입니까? Apr 04, 2025 pm 05:09 PM

동일한 ID로 배열 요소를 JavaScript의 하나의 객체로 병합하는 방법은 무엇입니까? 데이터를 처리 할 때 종종 동일한 ID를 가질 필요가 있습니다 ...

Shiseido의 공식 웹 사이트와 같은 시차 스크롤 및 요소 애니메이션 효과를 달성하는 방법은 무엇입니까? 또는: Shiseido의 공식 웹 사이트와 같은 페이지 스크롤과 함께 애니메이션 효과를 어떻게 달성 할 수 있습니까? Apr 04, 2025 pm 05:36 PM

이 기사에서 시차 스크롤 및 요소 애니메이션 효과 실현에 대한 토론은 Shiseido 공식 웹 사이트 (https://www.shiseido.co.jp/sb/wonderland/)와 유사하게 달성하는 방법을 살펴볼 것입니다.

Console.log 출력 결과의 차이 : 두 통화가 다른 이유는 무엇입니까? Apr 04, 2025 pm 05:12 PM

Console.log 출력의 차이의 근본 원인에 대한 심층적 인 논의. 이 기사에서는 Console.log 함수의 출력 결과의 차이점을 코드에서 분석하고 그에 따른 이유를 설명합니다. � ...

JavaScript는 배우기가 어렵습니까? Apr 03, 2025 am 12:20 AM

JavaScript를 배우는 것은 어렵지 않지만 어려운 일입니다. 1) 변수, 데이터 유형, 기능 등과 같은 기본 개념을 이해합니다. 2) 마스터 비동기 프로그래밍 및 이벤트 루프를 통해이를 구현하십시오. 3) DOM 운영을 사용하고 비동기 요청을 처리합니다. 4) 일반적인 실수를 피하고 디버깅 기술을 사용하십시오. 5) 성능을 최적화하고 모범 사례를 따르십시오.