欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript實(shí)現(xiàn)鏈表插入排序和鏈表歸并排序

 更新時(shí)間:2016年10月25日 12:27:02   作者:Andy Cheung  
這篇文章主要介紹了JavaScript實(shí)現(xiàn)鏈表插入排序和鏈表歸并排序,較為詳細(xì)的分析了插入排序和歸并排序,對(duì)于學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)具有一定參考借鑒價(jià)值,需要的朋友可以參考下。

本篇文章詳細(xì)的介紹了JavaScript實(shí)現(xiàn)鏈表插入排序和鏈表歸并排序,鏈表的歸并排序就是對(duì)每個(gè)部分都進(jìn)行歸并排序,然后合并在一起。

1.鏈表

1.1鏈表的存儲(chǔ)表示

//鏈表的存儲(chǔ)表示
typedef int ElemType;
typedef struct LNode
{
  ElemType data;
  struct LNode *next;
}LNode, *LinkList;

1.2基本操作

創(chuàng)建鏈表:

/*
 * 創(chuàng)建鏈表。
 * 形參num為鏈表的長(zhǎng)度,函數(shù)返回鏈表的頭指針。
 */
LinkList CreatLink(int num)
{
  int i, data;
 
  //p指向當(dāng)前鏈表中最后一個(gè)結(jié)點(diǎn),q指向準(zhǔn)備插入的結(jié)點(diǎn)。
  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;
}

輸出鏈表:

/*
 * 輸出鏈表結(jié)點(diǎn)值。
 */
int PrintLink(LinkList head)
{
  LinkList p;
  for (p = head; p ;p = p->next)
  {
    printf("%-3d ", p->data);
  }
  return 0;
}

2.鏈表插入排序

基本思想:假設(shè)前面n-1個(gè)結(jié)點(diǎn)有序,將第n個(gè)結(jié)點(diǎn)插入到前面結(jié)點(diǎn)的適當(dāng)位置,使這n個(gè)結(jié)點(diǎn)有序。

實(shí)現(xiàn)方法:

將鏈表上第一個(gè)結(jié)點(diǎn)拆下來,成為含有一個(gè)結(jié)點(diǎn)的鏈表(head1),其余的結(jié)點(diǎn)自然成為另外一個(gè)鏈表(head2),此時(shí)head1為含有

一個(gè)結(jié)點(diǎn)的有序鏈表;

將鏈表head2上第一個(gè)結(jié)點(diǎn)拆下來,插入到鏈表head1的適當(dāng)位置,使head1仍有序,此時(shí)head1成為含有兩個(gè)結(jié)點(diǎn)的有序鏈表;

依次從鏈表head2上拆下一個(gè)結(jié)點(diǎn),插入到鏈表head1中,直到鏈表head2為空鏈表為止。最后,鏈表head1上含所有結(jié)點(diǎn),且結(jié)點(diǎn)有序。

插入排序代碼:

/*
 * 鏈表插入排序(由小到大)。
 * 輸入:鏈表的頭指針,
 * 輸出:排序后鏈表的頭指針。
 * 實(shí)現(xiàn)方法:將原鏈表拆成兩部分:鏈表1仍以head為頭指針,鏈表結(jié)點(diǎn)有序。鏈表2以head2為頭指針,鏈表結(jié)點(diǎn)無序。
 * 將鏈表2中的結(jié)點(diǎn)依次插入到鏈表1中,并保持鏈表1有序。
 * 最后鏈表1中包含所有結(jié)點(diǎn),且有序。
 */
LinkList LinkInsertSort(LinkList head)
{
  //current指向當(dāng)前待插入的結(jié)點(diǎn)。
  LinkList head2, current, p, q;
 
  if (head == NULL)
    return head;
 
  //第一次拆分。
  head2 = head->next;
  head->next = NULL;
 
  while (head2)
  {
    current = head2;
    head2 = head2->next;
 
    //尋找插入位置,插入位置為結(jié)點(diǎn)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    //鏈表長(zhǎng)度

//鏈表的存儲(chǔ)表示
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);

/*
 * 創(chuàng)建鏈表。
 * 形參num為鏈表的長(zhǎng)度,函數(shù)返回鏈表的頭指針。
 */
LinkList CreatLink(int num)
{
  int i, data;

  //p指向當(dāng)前鏈表中最后一個(gè)結(jié)點(diǎn),q指向準(zhǔn)備插入的結(jié)點(diǎn)。
  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;
}

/*
 * 鏈表插入排序(由小到大)。
 * 輸入:鏈表的頭指針,
 * 輸出:排序后鏈表的頭指針。
 * 實(shí)現(xiàn)方法:將原鏈表拆成兩部分:鏈表1仍以head為頭指針,鏈表結(jié)點(diǎn)有序。鏈表2以head2為頭指針,鏈表結(jié)點(diǎn)無序。
 * 將鏈表2中的結(jié)點(diǎn)依次插入到鏈表1中,并保持鏈表1有序。
 * 最后鏈表1中包含所有結(jié)點(diǎn),且有序。
 */
LinkList LinkInsertSort(LinkList head)
{
  //current指向當(dāng)前待插入的結(jié)點(diǎn)。
  LinkList head2, current, p, q;

  if (head == NULL)
    return head;

  //第一次拆分。
  head2 = head->next;
  head->next = NULL;

  while (head2)
  {
    current = head2;
    head2 = head2->next;

    //尋找插入位置,插入位置為結(jié)點(diǎn)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;
}

/*
 * 輸出鏈表結(jié)點(diǎn)值。
 */
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個(gè)數(shù)以創(chuàng)建鏈表:\n");
  head = CreatLink(TOTAL);
  
  head = LinkInsertSort(head);
  printf("排序后:\n");
  PrintLink(head);
  putchar('\n');
  return 0;
}

3.鏈表歸并排序

基本思想:如果鏈表為空或者含有一個(gè)結(jié)點(diǎn),鏈表自然有序。否則,將鏈表分成兩部分,對(duì)每一部分分別進(jìn)行歸并排序,然后將已排序的兩個(gè)鏈表歸并在一起。

歸并排序代碼:

/*
 * 鏈表歸并排序(由小到大)。
 * 輸入:鏈表的頭指針,
 * 輸出:排序后鏈表的頭指針。
 * 遞歸實(shí)現(xiàn)方法:將鏈表head分為兩部分,分別進(jìn)行歸并排序,再將排序后的兩部分歸并在一起。
 * 遞歸結(jié)束條件:進(jìn)行遞歸排序的鏈表為空或者只有一個(gè)結(jié)點(diǎn)。
 */
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;
}

其中鏈表分割函數(shù)如下,基本思想是利用slow/fast指針,具體實(shí)現(xiàn)方法見注釋。

/*
 * 鏈表分割函數(shù)。
 * 將鏈表head均分為兩部分head1和head2,若鏈表長(zhǎng)度為奇數(shù),多出的結(jié)點(diǎn)從屬于第一部分。
 * 實(shí)現(xiàn)方法:首先使指針slow/fast指向鏈?zhǔn)祝?
 * 然后使fast指針向前移動(dòng)兩個(gè)結(jié)點(diǎn)的同時(shí),slow指針向前移動(dòng)一個(gè)結(jié)點(diǎn),
 * 循環(huán)移動(dòng),直至fast指針指向鏈尾。結(jié)束時(shí),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;
}

鏈表歸并函數(shù)有遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn)兩種方法:

非遞歸實(shí)現(xiàn):

/*
 * 鏈表歸并。
 * 將兩個(gè)有序的鏈表歸并在一起,使總鏈表有序。
 * 輸入:鏈表head1和鏈表head2
 * 輸出:歸并后的鏈表
 * 實(shí)現(xiàn)方法:將鏈表head2中的結(jié)點(diǎn)依次插入到鏈表head1中的適當(dāng)位置,使head1仍為有序鏈表。
 */
LinkList LinkMerge(LinkList head1, LinkList head2)
{
  LinkList p, q, t;
 
  if (!head1)
    return head2;
  if (!head2)
    return head1;
 
  //循環(huán)變量的初始化,q指向鏈表head1中的當(dāng)前結(jié)點(diǎn),p為q的前驅(qū)。
  p = NULL;
  q = head1;
  while (head2)
  {
    //t為待插入結(jié)點(diǎn)。
    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;
    //將結(jié)點(diǎn)t插入到p和q之間后,使p重新指向q的前驅(qū)。
    p = t;
  }
  return head1;
}

遞歸實(shí)現(xiàn):

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    //鏈表長(zhǎng)度

//鏈表的存儲(chǔ)表示
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);

/*
* 創(chuàng)建鏈表。
* 形參num為鏈表的長(zhǎng)度,函數(shù)返回鏈表的頭指針。
*/
LinkList CreatLink(int num)
{
  int i, data;

  //p指向當(dāng)前鏈表中最后一個(gè)結(jié)點(diǎn),q指向準(zhǔn)備插入的結(jié)點(diǎn)。
  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;
}

/*
* 輸出鏈表結(jié)點(diǎn)值。
*/
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個(gè)數(shù)以創(chuàng)建鏈表:\n");
  head = CreatLink(TOTAL);

  head = LinkMergeSort(head);
  printf("排序后:\n");
  PrintLink(head);
  putchar('\n');
  return 0;
}

/*
 * 鏈表歸并排序(由小到大)。
 * 輸入:鏈表的頭指針,
 * 輸出:排序后鏈表的頭指針。
 * 遞歸實(shí)現(xiàn)方法:將鏈表head分為兩部分,分別進(jìn)行歸并排序,再將排序后的兩部分歸并在一起。
 * 遞歸結(jié)束條件:進(jìn)行遞歸排序的鏈表為空或者只有一個(gè)結(jié)點(diǎn)。
 */
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);    //非遞歸實(shí)現(xiàn)
  //head = LinkMerge2(head1, head2);  //遞歸實(shí)現(xiàn)
  return head;
}

/*
 * 鏈表歸并。
 * 將兩個(gè)有序的鏈表歸并在一起,使總鏈表有序。
 * 輸入:鏈表head1和鏈表head2
 * 輸出:歸并后的鏈表
 * 實(shí)現(xiàn)方法:將鏈表head2中的結(jié)點(diǎn)依次插入到鏈表head1中的適當(dāng)位置,使head1仍為有序鏈表。
 */
LinkList LinkMerge(LinkList head1, LinkList head2)
{
  LinkList p, q, t;

  if (!head1)
    return head2;
  if (!head2)
    return head1;

  //循環(huán)變量的初始化,q指向鏈表head1中的當(dāng)前結(jié)點(diǎn),p為q的前驅(qū)。
  p = NULL;
  q = head1;
  while (head2)
  {
    //t為待插入結(jié)點(diǎn)。
    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;
    //將結(jié)點(diǎn)t插入到p和q之間后,使p重新指向q的前驅(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;
}

/*
 * 鏈表分割函數(shù)。
 * 將鏈表head均分為兩部分head1和head2,若鏈表長(zhǎng)度為奇數(shù),多出的結(jié)點(diǎn)從屬于第一部分。
 * 實(shí)現(xiàn)方法:首先使指針slow/fast指向鏈?zhǔn)祝?
 * 然后使fast指針向前移動(dòng)兩個(gè)結(jié)點(diǎn)的同時(shí),slow指針向前移動(dòng)一個(gè)結(jié)點(diǎn),
 * 循環(huán)移動(dòng),直至fast指針指向鏈尾。結(jié)束時(shí),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;
}

以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

最新評(píng)論