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つのパスが必要です（1つはリストを通過し、もう1つはスタックを通過します）。このようなスタックを管理するには、複数のオプションがあります。2つを以下に示します。

  2. 単純なリバース/プリント/リバースを実行します。3つのパスが必要です（1つは反転用、1つは印刷用、もう1つは元に戻る-反転用）。

これらの前者は、スタックの管理に必要なスペースを犠牲にして、リストを一定に保つ（ノードの反転は行われない）という利点を提供します。これらの後者は、追加のスペース要件がないという利点を提供しますが、リストの3パスを犠牲にして、一時的ではありますが、リストの変更を許可する必要があります。

どちらを選ぶかはあなた次第です。

ローカルスタックの実装：（2パス、2 * N * sizeof（ポインター）スペース）

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（ポインター）スペース）

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 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

関数呼び出しスタックを悪用して、それを行う醜い方法：

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 PrintBackwards (node * head)
     {
       if(head)
        {
          PrintBackwards(head->next);
          printf("%d",head->data);
        }
       return;
      }
于 2013-10-09T09:13:13.303 に答える
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 に答える