使用遞歸技術在C中反轉鏈接列表C

Question

我有以下C代碼，它返回鏈接列表的反轉。

儘管它顛倒了鏈表，但我從來沒有得到反向鏈表的頭部，因爲restofElements節點正在被覆蓋。

S *reverseRecursive(S *headref) 
{ 
    S *firstElement = NULL; 
    S *restOfElements = NULL; 
    if (headref==NULL) 
    { 
    return ; 
    } 
    firstElement = headref; 
    restOfElements = headref->next; 
    if (restOfElements == NULL) 
     return headref; 
    reverseRecursive(restOfElements); 
    firstElement->next->next = firstElement; 
    firstElement->next = NULL;   
    headref = restOfElements;  
    return headref; 
} 

如何獲得返回到調用程序的反轉鏈表節點的頭部？

Answer 1

如果你想改變頭指針，你必須通過引用來傳遞它（作爲一個指針）。原型應該修改爲接收頭爲S **。

S *reverseRecursive(S **headref); 

Answer 2

顛倒鏈表的頭等於開始restOfElements（因爲原headref有可能成爲逆轉名單的塔最後一個元素）反轉列表的頭部。因此，存儲回調呼叫的結果應該如下（如Jim已經在他的評論中提出的那樣）：

... 
headref = reverseRecursive(restOfElements); 
firstElement->next->next = firstElement; 
firstElement->next = NULL;   
/* headref = restOfElements; that's wrong */  
return headref; 

Answer 3

可能更接近。

S *reverseRecursive(S *headref) 
{ 
    S *firstElement = NULL; 
    S *restOfElements = NULL; 
    S *new_head = NULL; 
    if (headref==NULL) 
    { 
    return ; 
    } 
    firstElement = headref; 
    restOfElements = headref->next; 
    if (restOfElements == NULL) 
     return headref; 
    new_head = reverseRecursive(restOfElements); 
    restOfElements->next = new_head;   
    return restOfElements; 
} 

Answer 4

謝謝大家。我已經修改了一點，現在它可以工作。讓我知道你的意見。 new_head是一個全局變量。

S *reverseRecursive(S *headref) 
{ 
    S *firstElement = NULL; 
    S *restOfElements = NULL; 

    if (headref==NULL) 
    { 
    return ; 
    } 
    firstElement = headref; 


    if (headref->next == NULL) 
     return headref; 
    else 
    restOfElements = headref->next; 


    reverseRecursive(restOfElements); 

    firstElement->next->next = firstElement; 

    firstElement->next = NULL;   

    if(new_head == NULL) //just dont take it ervery time 
     new_head = restOfElements; 

    return new_head; 

    } 

Answer 5

$ GCC -std = C99 -Wall -Wextra reverse.c

#include <stdlib.h> 
#include <stdio.h> 

typedef struct list { 
    struct list* next; 
    int data; 
} S; 

void print_list(S* list) { 
    if (list == NULL) { printf("NULL\n"); return; } 
    printf("%d ", list->data); 
    print_list(list->next); 
} 

S* reverse_aux(S* list, S* tail) { 
    // invalid arg 
    if (list == NULL) { return NULL; } 

    // base case 
    if (list->next == NULL) { 
    list->next = tail; 
    return list; 
    } 

    // general case 
    S* tmp = list->next; 
    list->next = tail; 

    return reverse_aux(tmp, list); 
} 

S* reverse(S* list) { return reverse_aux(list, NULL); } 

int main(int argc, char* argv[]) { 
    // build a list with which to test 
    S a[10]; 
    for (unsigned i = 0; i < sizeof(a)/sizeof(S); ++i) { 
    a[i].data = i; 
    a[i].next = &a[i+1]; 
    } 
    a[sizeof(a)/sizeof(S) - 1].next = NULL; 
    S* list = &a[0]; 

    print_list(list); 
    list = reverse(list); 
    print_list(list); 

    return 0; 
} 

實際上，由於反向是破壞性的（發生變異它的參數），更好的界面設計很可能會

void reverse(S** plist); 
reverse(&list); 

Answer 6

所以有兩種方法可以遞歸地反轉列表。

首先，一些設置。讓我們可以很容易地加載鏈表串 並打印出來，所以我們可以肯定這東西的作品：

倒車列表

// linked_list.c 
#include <stdio.h> 
#include <stdlib.h> 

// a linked lis of strings 
typedef struct S { 
    struct S * next; 
    char * val; 
} S; 

// print out the list 
void showS(char * const name, S * head) { 
    printf("%s: (", name); 
    while (head){ 
    printf(" "); 
    printf("%s",head->val); 
    head = head->next; 
    printf("%c", head ? ',' : ' '); 
    } 
    printf(")\n"); 
} 

// convert an array of strings into a linked list of strings 
S * mkS(int n, char ** args) { 
    S * head = NULL; 

    if (n > 0 && (head = calloc(n, sizeof(S)))){ 
    S * curr = head - 1; 

    while (n-- > 0) { 
     curr++; 
     curr->val = *args++; 
     curr->next = curr + 1; 
    } 
    curr->next = NULL; 
    } 

    return head; 
} 

一種方式包括使 列表後面的新掌門人，一旦我們找到它。我們本地不需要它（因爲我們只是將當前元素移動到新的末端），但是我們需要它，以便調用者 在完成後有一個指向列表頭的指針。

// reverse a list one way 
S * revS1(S * const head){ 
    if (head && head->next) { 
    S * const new_head = revS1(head->next); 
    head->next->next = head; 
    head->next = NULL; 
    return new_head; 
    } else { 
    return head; 
    } 
} 

另一種方法需要一個指針指針。唯一的區別是 我們不需要返回任何東西，因爲我們直接修改調用者具有的變量 。我更喜歡這種調用方法，因爲它更清晰 我們正在修改列表，而不是返回副本。呼叫者以這種方式意外鬆開指向新頭部的指針也很難。

// reverse a list another way 
void revS2(S ** phead){ 
    S * const head = *phead; 
    if (head && head->next) { 
    *phead = head->next; 
    revS2(phead); 
    head->next->next = head; 
    head->next = NULL; 
    } 
} 

但是，比這兩者中的任何一個都更好的是以非遞歸方式反轉列表。 這兩個函數都不是尾遞歸的，所以編譯器有 爲列表中的每個元素分配新的堆棧幀。嘗試將足夠的列表反轉一個長的列表，然後你就會炸燬你的堆棧。更好地使用while循環來逆轉列表 。

// reverse a list non-recursively 
void revS3(S ** phead){ 
    S * head = *phead; 
    S * reversed = NULL; 

    while (head) { 
    S * curr = head; 
    head = curr->next; 
    curr->next = reversed; 
    reversed = curr; 
    } 
    *phead = reversed; 
} 

現在我們可以只通過建立列出了命令行的測試我們的研究結果：

// just use the command line arguments as our list 
int main(int argc, char** argv){ 

    S* list1 = mkS(argc - 1, argv + 1); 
    S* list2 = mkS(argc - 1, argv + 1); 
    S* list3 = mkS(argc - 1, argv + 1); 

    showS("given", list1); 

    showS("revS1", revS1(list1)); 

    revS2(&list2); 
    showS("revS2", list2); 

    revS2(&list3); 
    showS("revS3", list3); 

    return 0; 
} 

因此，讓我們編譯：

% gcc -Wall linked_list.c -o linked_list 

，並做一些測試運行

% ./linked_list 
given:() 
revS1:() 
revS2:() 
revS3:() 
% ./linked_list first second third 
given: (first, second, third) 
revS1: (third, second, first) 
revS2: (third, second, first) 
revS3: (third, second, first) 
% ./linked_list only 
given: (only) 
revS1: (only) 
revS2: (only) 
revS3: (only)