用於排序鏈接列表的常規函數

是否有任何通用用戶定義的函數可用於對給定鏈接列表進行排序，因爲它具有指針字段和數據字段。用於排序鏈接列表的常規函數

函數不應該交換節點之間的數據。交換應通過使用pointers完成。

我在網上發現了一個，但它使用的是用戶定義的功能。我不允許使用任何其他功能，但泡泡排序。

我們被要求不要初始化函數內的任何新變量，而不是temp structs。所以，我不能使用整數或像swapped這樣的變量。

，我用的是一個如下：

/* Bubble sort the given linked lsit */ 
void bubbleSort(struct node *start) 
{ 
    int swapped, i; 
    struct node *ptr1; 
    struct node *lptr = NULL; 

    /* Checking for empty list */ 
    if (ptr1 == NULL) 
     return; 

    do 
    { 
     swapped = 0; 
     ptr1 = start; 

     while (ptr1->next != lptr) 
     { 
      if (ptr1->data > ptr1->next->data) 
      { 
       swap(ptr1, ptr1->next); 
       swapped = 1; 
      } 
      ptr1 = ptr1->next; 
     } 
     lptr = ptr1; 
    } 
    while (swapped); 
} 

/* function to swap data of two nodes a and b*/ 
void swap(struct node *a, struct node *b) 
{ 
    int temp = a->data; 
    a->data = b->data; 
    b->data = temp; 
}

鑑於我的鏈表結構如下：

struct node 
{ 
    int data; 
    struct node *next; 
};

來源

2016-01-13 jakline nataly

不，不，我所知道的。如果不使用用戶定義的函數，您如何設想一個泛型函數可能會對**（a）**有哪些成員用於比較以及**（b）**是否有任何給定節點應該在或者在任何其他任意節點之後？如果你看看'qsort'函數（在stdlib.h中可以找到），你可以看到它需要定義一個比較函數。它會對任何你喜歡的數組進行排序，但是你必須告訴它（a）每個元素有多大，以及（b）用哪個函數來比較2個元素。 – enhzflep

如果它是真正的通用的，你將不得不提供一個函數來比較節點，但你也必須處理不同的節點佈局（指向下一個節點的指針可能有不同的偏移量）。否則，應該可以使用具有'O（N log N）'複雜度的算法，即使對於單個鏈表也是如此。 – skyking

我的意思是用戶定義的函數。不是使用c語言構建的函數，但函數可以通用方式解決問題。讓我們說它是按升序排序，所以我可以改變它以降序排序。此外，我可以編輯一些字段，以獲得所需的輸出。 –

對於你的情況，你可以使用您所提供的功能的編輯版本。 這裏省略了交換功能。

//Sorting according to the data, ascending order 
void bubbleSortLL(struct node *header){ 

struct node *temp1, *temp2, *temp3, *temp4, *temp5; 

temp4=NULL; 

while(temp4!=header->next) 
{ 
    temp3=temp1=header; 
    temp2=temp1->next; 

    while(temp1!=temp4) 
    { 
     if(temp1->data > temp2->data) 
     { 
      if(temp1==header) 
      { 
       temp5=temp2->next; 
       temp2->next=temp1; 
       temp1->next=temp5; 
       header=temp2; 
       temp3=temp2; 
      } 
      else 
      { 
       temp5=temp2->next; 
       temp2->next=temp1; 
       temp1->next=temp5; 
       temp3->next=temp2; 
       temp3=temp2; 
      } 
     } 
     else 
     { 
      temp3=temp1; 
      temp1=temp1->next; 
     } 

     temp2=temp1->next; 
     if(temp2==temp4) 
      temp4=temp1; 

     } 
    } 
}

這將通過傳遞指定的列表作爲參數來工作。不過，我不明白你爲什麼不能使用交換功能。

來源

2016-01-13 10:34:23 yasserkabbout

一位仙女，10只小狗和3位天使剛剛去世。：p爲了其他人和你自己（今後）我強烈建議你養成給予不同有意義名字的習慣。 'temp1'，'temp2'，'temp3'，'temp4'和'temp5'是_really_討厭的名字，並且使其不必要地難以閱讀代碼。當你回頭看舊代碼時，你會感謝你自己。 :) – enhzflep

會做：D謝謝。 – yasserkabbout

要擺脫掉函數的調用，其內容替換函數調用：

而不是

swap(ptr1, ptr1->next);

寫

int temp = ptr1->data; 
ptr1->data = ptr1->next->data; 
ptr1->next->data = temp;

要交換元素而不是數據，你需要來追蹤previo我們的元素。

這裏的元素交換的建議（不含也許需要NULL檢查）

previous->next = ptr1->next; 
previous->next->next=ptr1;

相反的ptr1=ptr1->next您需要：

 previous=previous->next; 
    ptr1=previous->next;

來源

2016-01-13 10:36:57 jofel

非常感謝。這個應該可以工作，但我們被要求不要定義任何新的變量，除了函數中的臨時結構。所以我不能使用整數「交換」或整數「溫度」。 –

我會將這一點作爲建議的編輯添加。 @jaklinenataly – yasserkabbout

用於排序鏈接列表的常規函數​​

回答

相關問題

用於排序鏈接列表的常規函數