6

我目前正在编写一个程序，该程序具有反向打印链表的功能。

我需要使用迭代方法打印此代码打印的相反内容。

编辑：它是一个单链表。

提前致谢。

void print_backward_iteration(NODE *ptr) {
    NODE *last, *current;

    last = NULL;

    printf("\n");

    while (ptr != last) {
        current = ptr;

        while (current -> next != last) {
            current= current -> next;
        }

        printf("%d  ", current -> data);
        last = current;
    }

    printf("\n");

}

这是我的完整代码：

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

/* declaration of structure */
typedef struct node {
    int data;
    struct node *next;
} NODE;

/* declaration of functions */
NODE* insert_node(NODE *ptr, NODE *new);
NODE* find_node(NODE *ptr, int n);
NODE* delete_node(NODE *ptr, int n, int *success_flag_ptr);
void print_backward_iteration(NODE *ptr);
void print_backward_recursion(NODE *ptr);

int main(int argc, char *argv[]) {
    int choice, x, flag_success;
    NODE *ptr, *new, *result;

    ptr = NULL;

    do {
        printf("\n1.\tInsert Integer into linked list\n");
        printf("2.\tFind integer in linked list\n");
        printf("3.\tDelete integer from linked list\n");
        printf("4.\tPrint out integers backward using the iterative strategy\n");
        printf("5.\tPrint out integers backward using the recursive strategy\n");
        printf("6.\tQuit\n");
        printf("\nEnter 1,2,3,4,5, or 6: ");
        scanf("%d", &choice);

        switch(choice) {
        case 1:
            printf("\nPlease enter an integer: ");
            scanf("%d", &x);
            new = (NODE *)malloc(sizeof(NODE));
            new->data = x;
            ptr = insert_node(ptr, new);
            printf("\nNode Inserted with value of %d.\n", ptr->data);
            break;

        case 2:
            printf("\nPlease enter an integer: ");
            scanf("%d", &x);
            result = find_node(ptr, x);

            if (result == NULL) {
                printf("\nValue could not be found.\n");
            } else {
                printf("\nValue %d was found.\n", x);
            }
            break;

        case 3:
            printf("\nPlease enter an integer: ");
            scanf("%d", &x);
            ptr = delete_node(ptr, x, &flag_success);

            if (result == NULL) {
                printf("\nValue could not be found.\n");
            } else {
                printf("\nValue %d was deleted.\n", x);
            }
            break;

        case 4:
            print_backward_iteration(ptr);
            break;

        case 5:
            printf("\n");
            print_backward_recursion(ptr);
            printf("\n");
            break;

        case 6:
            printf("\nThank you for using this program.\n");
            break;

        default:
            printf("\nInvalid Choice. Please try again.\n");
            break;
        }
    }
    while (choice != 6);

    printf("\n*** End of Program ***\n");
    return 0;
}

/* definition of function insert_node */
NODE* insert_node(NODE *ptr, NODE *new) {
    new -> next = ptr;
    return new;
}

/* definition of function find_node */
NODE* find_node(NODE *ptr, int n) {
    while (ptr != NULL) {
        if (ptr->data == n) {
            return ptr;
        } else {
            ptr = ptr->next;
        }
    }

    return NULL;
}

/* definition of function delete_node */
NODE* delete_node(NODE *ptr, int n, int *success_flag_ptr) {
    NODE *temp = NULL;

    if (ptr == NULL) {
        *success_flag_ptr = 0;
        return NULL;
    }

    if (ptr -> data == n) {     
        temp = ptr->next;  
        free(ptr);         
        *success_flag_ptr = 1;
        return temp;
    } else
        ptr->next = delete_node(ptr->next,n,success_flag_ptr); 

    return ptr;
}

/* definition of function print_backward_iteration */
void print_backward_iteration(NODE *ptr) {
    NODE *last, *current;

    last = NULL;

    printf("\n");

    while (ptr != last) {
        current = ptr;

        while (current != last) {
            current =  current -> next;
        }

        printf("%d  ", current -> data);
        last = current -> next;
    }

    printf("\n");
}

/* definition of function print_backward_recursion */
void print_backward_recursion(NODE *ptr) {
    NODE *last, *current;

    last = NULL;

    while (ptr != last) {
        current = ptr;
        printf("%d  ", current -> data);
        print_backward_recursion(current -> next);
        last = current;
    }
}
4

7 回答 7

7

更新-我将下面的代码保留在希望使用所提供的任何方法实际反向打印链接列表无递归的人可能会从中获得某种用途。与此同时，OP的真正问题是：

“我如何打印一个从头到尾的链表？”

谁看到了它的到来？反正，

void print_node_list(const NODE* p)
{
    printf("\n");
    for (;p;printf("%d ",p->data),p=p->next);
    printf("\n");
}

是的，就是这么简单。

现在几乎一文不值的反向打印讨论

符合您对这是一个迭代解决方案的要求，更重要的是，假设您的列表顺序在此操作完成后保持不变，您可以：

  1. 在迭代中管理节点指针堆栈，在单次遍历列表时推送指针，然后从堆栈中弹出指针以打印反向。需要两次通过（一次通过列表，一次通过堆栈）。管理这样的堆栈有多种选择；下面介绍两个。

  2. 执行简单的反转/打印/反转。需要 3 次通过（1 次用于反转，1 次用于打印，1 次用于撤消反转）。

前者提供了以管理堆栈所需的空间为代价保持列表不变（不进行节点反转）的优势。后者的好处是没有额外的空间要求，但代价是列表上的三遍，并且要求允许修改列表，尽管是暂时的。

你选择哪一个取决于你。

本地堆栈实现：（2 遍，2*N*sizeof(pointer) 空间）

void print_reverse_node_list(const NODE* head)
{
    struct stnode
    {
        struct stnode* next;
        const NODE* node;
    } *st = NULL;

    while (head)
    {
        struct stnode* p = malloc(sizeof(*p));
        if (p)
        {
            p->next = st;
            p->node = head;
            st = p;
            head = head->next;
        }
        else
        {
            perror("Could not allocate space for reverse-print.");
            exit(EXIT_FAILURE);
        }
    }

    // walks stack, popping off nodes and printing them.
    printf("\n");
    while (st)
    {
        struct stnode* p = st;
        st = st->next;
        printf("%d ", p->node->data);
        free(p);
    }
    printf("\n");
}

另一个本地堆栈实现（2 遍，N*sizeof(pointer) 空间）

void print_reverse_node_list(const NODE* head)
{
    NODE const **ar = NULL;
    size_t i=0;
    while (head)
    {
        // reallocate pointer array
        NODE const **tmp = realloc(ar, ++i * sizeof(*tmp));
        if (tmp)
        {
            ar = tmp;           // remember new array
            ar[i-1] = head;     // last index gets the ptr
            head = head->next;  // advance to next node
        }
        else
        {
            perror("Could not allocate space for reverse-print.");
            exit(EXIT_FAILURE);
        }
    }

    // print nodes from [i-1] to [0]
    printf("\n");
    for (; i!=0; printf("%d ", ar[--i]->data));
    printf("\n");
    // don't forget to release the block (NULL is ok)
    free(ar);
}

反向/打印/反向实现：（3遍，没有额外的空间）

// print a node list.
void print_node_list(const NODE* p)
{
    printf("\n");
    for (;p;printf("%d ",p->data),p=p->next);
    printf("\n");
}

// reverses a linked list in-place.
void reverse_node_list(NODE **headp)
{
    if (!headp || !*headp)
        return;

    NODE *ptr = *headp, *next = NULL, *prev = NULL;
    while (ptr)
    {
        next = ptr->next;      // remember next node (1)
        ptr->next = prev;      // wire next to prev
        prev = ptr;            // set prev to current
        ptr = next;            // move to remembered next (see 1)
    }

    *headp = prev;
}

void print_reverse_node_list(NODE* head)
{
    reverse_node_list(&head);
    print_node_list(head);
    reverse_node_list(&head);
}
于 2012-11-30T23:27:21.520 回答
2 
void print_Linked_List_iteration(NODE *ptr)
{

  printf("\n");

  while (ptr != NULL)
  {

      printf("%d  ", ptr->data);
      ptr = ptr->next;
  }

  printf("\n");

}
于 2012-12-01T04:46:01.947 回答
1

答案取决于列表的性质：

  • 如果这是一个双向链表，只需反向迭代。

  • 如果这是一个单链表，您将不得不自己维护一个堆栈，基本上做递归解决方案会做的事情，但要迭代。这基本上与制作列表的反向副本（这可以迭代地完成）并打印副本相同。

于 2012-11-30T23:14:18.477 回答
0 
    void PrintBackwards (node * head)
     {
       if(head)
        {
          PrintBackwards(head->next);
          printf("%d",head->data);
        }
       return;
      }
于 2013-10-09T09:13:13.303 回答
0

丑陋的做法，滥用函数调用堆栈：

void print_reverse_iteration(NODE *ptr)
{
    if (ptr != NULL) 
    {
        print_reverse_iteration( ptr->next);
        printf( "%d  ", ptr->data);
    }
}

print_reverse_iteration( head);
puts( "");

仅适用于不会溢出堆栈的短列表。

于 2012-12-01T00:20:04.100 回答
0

我假设该列表是单独链接的，否则问题将是微不足道的。我会以相反的顺序制作一份清单，然后打印出来。基本上;

 void print_reverse_iteration(NODE *ptr)
 {
        NODE *previous = head;
        NODE *current = head;
        bool trailing = false; //used to ensure we're on head->next before we begin moving prev
        last = NULL;

        printf("\n");

        while (current->next != NULL)
        {
               current->next = previous;
               if (trailing)
                   previous = previous->next;
               else
               {
                   trailing = true;
                   current->next = NULL; // this is now the end of the list so we need to set it's next pointer to null to ensure we halt in other methods that rely on node->next == NULL
                }
               current = current->next
         }

         //the list is now in reverse order. print it with your regular print method.
         normalPrint(current);
        // current is the head of this temporary list so pass it current.    

    }
于 2012-11-30T23:24:19.267 回答
0

使用堆栈的 Java 解决方案：

public void printReverseUsingStack(Node head){

    if(head == null){
        return;
    }
    Node current = head;
    Stack<Integer> s = new Stack<Integer>();

    while(current != null){
        s.push(current.data);
        current = current.next;
    }
    while(!s.isEmpty()){
        System.out.print(s.pop() + " -> ");
    }
}
于 2015-06-25T04:35:09.513 回答