c - 列表反向打印

Question

列表中的每个节点都包含连续节点的地址和数据。这就是为什么递归效果很好，如以下示例所示：它接受输入，例如123456，然后将其打印为列表6 -> 5 -> 4 -> 3 -> 2 -> 1 -> NULL.

/* Structure types ----------------------------------------------*/
typedef int data;
struct list_element {
   int                     data;
   struct list_element     *next;
};
typedef struct list_element ELEM;
typedef ELEM *LINK;

/* Recursive list create and list print---------------*/
LINK create_list(int n) {
   if (n == 0) {
      return NULL;
   }
   else {
      LINK head = (LINK) malloc(sizeof(ELEM));
      head -> data = n % 10;
      head -> next = create_list(n / 10);
      return head;
   }
}
void print_list(LINK head) {
   if(head == NULL)
      printf("NULLn");
   else {
      printf("%d -> ", head -> data);
      print_list(head -> next);
   }
}
/* MAIN ---------------------------------------------------------*/
int main(int argc, char *argv[]) {
   int n; LINK ls;
   printf("nType an integer:n");
   scanf("%d", &n);
   ls = create_list(n);
   print_list(ls);
   return 0;
}

节点不保存其前一个邻居的地址。从这个考虑出发，问题：

如何从其最后一个节点打印列表，以便NULL -> 6 -> 5 -> 4 -> 3 -> 2 -> 1？

在 c 中递归反转链接列表的答案实际上指向了一个略有不同的问题。他们的目标是扭转名单本身。我不打算改变列表中数据的顺序。

Answer 1

您可以通过更改打印调用的顺序来执行此操作。如果先打印列表的其余部分，则顺序将反转。

print_list(head -> next);
printf("%d -> ", head -> data);

这实际上是一个如何浏览列表的问题。

Answer 2

你只需要交换 printf 语句和递归调用。

void print_list(LINK head){ 
     if(head == NULL)
          printf("NULLn"); 
     else{
          print_list(head -> next);
          printf("%d -> ", head -> data);
      }
 } 

然后，最后一个递归调用中的 printf 语句将首先执行，然后执行其他语句。

Answer 3

当你的列表变得非常大时，递归将无济于事，因为你最终会运行我们的堆栈空间。

如果要求可以反向打印列表，则必须调整数据结构(和算法(以实现要求，而不会耗尽堆栈空间。

简而言之，你必须实现一个双向链表，也就是说，不仅要有next成员，还要有一个prev成员。

Answer 4

只需遍历到最后一个节点，同时将 printf 语句推送到堆栈上。到达列表末尾后，堆栈将开始展开，并且您的打印函数将被调用。

void print_list_reverse(LINK head){                                                                                                                                                                                                             
    if(head == NULL)                                                                                                                                                                                                                        
            printf("NULL -> ");                                                                                                                                                                                                             
    else{                                                                                                                                                                                                                                   
            print_list_reverse(head -> next);                                                                                                                                                                                               
            printf("%d -> ", head -> data);                                                                                                                                                                                                 
    }                                                                                                                                                                                                                                       
}