以相反的顺序打印双向链表? [英] Print a doubly linked list in reverse order?

问题描述

我的最小可重复示例:

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

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};

/** Structure for the whole list, including head and tail pointers. */
typedef struct {
    /** Pointer to the first node on the list (or NULL ). */
    Node *head;
    Node *last;
} List;

List *list;

List *makeList();
static void *addRecord(List *list, int newID);
static void printReverse(List *list);

int main(int argc, char **argv) {
    //Create an empty list for you to start.
    list = (List *)makeList();

    addRecord(list, 1);
    addRecord(list, 2);
    addRecord(list, 3);
    addRecord(list, 4);
    addRecord(list, 15);
    printReverse(list);
    return 0;
}

List *makeList() {
    List *list = (List *)malloc(sizeof(List));
    list->head = NULL;
    return list;
}

static void *addRecord(List *list, int newID) {
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node)); 

    //Add in data
    new->id = newID; 

    //New node has no next, yet
    new->next = NULL;

    Node **next_p = &list->head;
    while (*next_p) {
        next_p = &(*next_p)->next;
    }
    *next_p = new;

    return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

输入:

1-> 2-> 3-> 4-> 15

1 -> 2 -> 3 -> 4 -> 15

预期输出:

15-> 4-> 3-> 2-> 1

15 -> 4 -> 3 -> 2 -> 1

实际输出:

分段错误

---

在链接列表中设置prev节点:

---

Set the prev node in the linked list:

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

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};

/** Structure for the whole list, including head and tail pointers. */
typedef struct {
    /** Pointer to the first node on the list (or NULL ). */
    Node *head;
    Node *last;
} List;

List *list;

List *makeList();
static void *addRecord(List *list, int newID);
static void printReverse(List *list);

int main(int argc, char **argv) {
    // Create an empty list for you to start.
    list = (List *)makeList();

    addRecord(list, 1);
    addRecord(list, 2);
    addRecord(list, 3);
    addRecord(list, 4);
    addRecord(list, 15);
    printReverse(list);
    return 0;
}

List *makeList() {
    List *list = (List *)malloc(sizeof(List));
    list->head = NULL;
    return list;
}

static void *addRecord(List *list, int newID) {
    //Allocate memory for the node
    Node *new = (Node *)malloc(sizeof(Node)); 

    //Add in data
    new->id = newID; 
    new->prev = NULL;

    //New node has no next, yet
    new->next = NULL;

    Node **next_p = &list->head;
    while (*next_p) {
        next_p = &(*next_p)->next;
    }
    *next_p = new;
    list->last = new;
    new->prev = *next_p;

    return EXIT_SUCCESS;
}

static void printReverse(List *list) {
    Node **tail = &list->last;
    printf("LIST IN REVERSE ORDER:\n");

    //Traversing until tail end of linked list
    while (*tail) {
        printf("Item ID: %d\n", (*tail)->id);
        tail = &(*tail)->prev;
    }
}

对addRecord进行此修改后，我不断获得一个无限循环，可以反复打印Item ID: 15.

With this edit made to addRecord, I keep getting an infinite loop that prints Item ID: 15 over and over again.

推荐答案

1)您将第一个节点添加(准确地说，将其添加到末尾)，其值为1，并将head设置为它.但是last呢?您列表中的最后一个节点也不也是第一个节点吗?是的！此外，将next指针设置为NULL，正确...但是prev指针呢?既然也没有以前的节点，也应该不将其设置为NULL吗?再次是.

1) You add (append to be exact, you add it to end) your first node, with a value of 1, and you set head to it. But what about last? Isn't the last node also the first node in your list? Yes it is! Moreover, you set the next pointer to NULL, correct... But what about the prev pointer? Shouldn't it be set to NULL too, since their so no previous node? Yes again.

2)list不必是全局的，老实说，它不必是全局的.

2) list does not need to be global, and to be honest, it shouldn't be.

3)当您这样做:

*next_p = new;
new->prev = *next_p;

然后，您说新添加的节点的前一个节点是新节点.它应该是最后一个，我们知道先验，所以我们可以这样做:

then you say that the previous node of the newly appended node is the new node. It should be the last, which we know apriori, so we can do:

new->prev = list->last;

就在构造节点之后.

4)此外，当创建空列表时，状态应为头指针和最后一个指针都设置为NULL.

4) Furthermore, when you create the empty list, the status should be that both head and last pointers are set to NULL.

5)最后，您可以简化打印功能，以不使用双指针，而只需使用指针.

5) Finally, you could simplify your print function to not use a double pointer, but just a pointer.

将所有内容放在一起，我们得到:

Putting everything together, we get:

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

typedef struct NodeStruct Node;

//struct for each office item
struct NodeStruct {
    int id;
    struct NodeStruct *next;
    struct NodeStruct *prev; //Create doubly linked list node
};

/** Structure for the whole list, including head and tail pointers. */
typedef struct {
  /** Pointer to the first node on the list (or NULL ). */
  Node *head;
  Node *last;
} List;

List *makeList();
static void *addRecordAtEnd(List *list, int newID);
void print(List *list);
void printReverse(List *list);

int main() 
{
  // Create an empty list for you to start.
  List* list = makeList();

  addRecordAtEnd(list, 1);
  addRecordAtEnd(list, 2);
  addRecordAtEnd(list, 3);
  addRecordAtEnd(list, 4);
  addRecordAtEnd(list, 15);
  print(list);
  printReverse(list);
  return 0;
}

List *makeList()
{
  List *list = malloc( sizeof( List ) );
  if(list != NULL)
  {
    list->head = NULL;
    list->last = NULL;
  }
  return list;
}

static void *addRecordAtEnd(List *list, int newID) 
{
  //Allocate memory for the node
  Node *new = malloc(sizeof(Node)); 

  //Add in data
  new->id = newID; 

  new->prev = list->last;
  new->next = NULL;

  list->last = new;

  // if list is empty
  if(!list->head)
  {
    list->head = new;
    return EXIT_SUCCESS;
  }

  Node **next_p = &list->head;
  while (*next_p) {
    next_p = &(*next_p)->next;
  }
  *next_p = new;

  return EXIT_SUCCESS;
}


void print(List *list)
{
  Node *current_node = list->head;
  while (current_node) {
    printf("Item ID: %d\n", current_node->id);
    current_node = current_node->next;
  }
}

void printReverse(List *list)
{
  Node *current_node = list->last;
  printf("LIST IN REVERSE ORDER:\n");

  //Traversing until tail end of linked list
  while (current_node) {
    printf("Item ID: %d\n", current_node->id);
    current_node = current_node->prev;
  }
}

输出(还要检查是否正确设置了下一个指针):

Output (to also check that the next pointers are correctly set):

Item ID: 1
Item ID: 2
Item ID: 3
Item ID: 4
Item ID: 15
LIST IN REVERSE ORDER:
Item ID: 15
Item ID: 4
Item ID: 3
Item ID: 2
Item ID: 1

PS:我是否强制转换malloc的结果?否！

这篇关于以相反的顺序打印双向链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！