mac_05185 2022-08-24 21:31 采纳率: 67.1%
浏览 47
已结题

C语言实现双向链表,无法倒序遍历输出,如何解决?

运行截图如下:

img

问题:

  • 可以正常前序遍历,但是后序遍历就会卡住,这是什么原因导致?

//双向链表C语言实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct node {
    int data;
    int key;
    //Next —— 链表中的每个链接都包含一个指向下一个链接的链接,该链接称为Next
    struct node *next;
    //Prev —— 链表中的每个链接都包含一个指向前一个称为Prev的链接
    struct node *prev;
};

struct node *head = NULL;

//this link always point to last link
struct node *last = NULL;

struct node *current = NULL;

//is the list empty
bool isEmpty() {
    return head == NULL;
}

int length() {
    int length = 0;
    struct node *current;
    for (current = head; current != NULL; current = current->next) {
        length++;
    }
    return length;
}

//display the list in from first to the last
void displayForward() {
    //start from the begin
    struct node *ptr = head;
    //navigate till the end of the list
    printf("\n{ ");
    while (ptr != NULL) {
        printf("(%d, %d) ", ptr->key, ptr->data);
        ptr = ptr->next;
    }
    printf(" }\n");
}

//display the list from last to first
void displayBackword() {
    //start from the last
    struct node *ptr = last;
    //navigate till the start of the list
    printf("\n[ ");
    while (ptr != NULL) {
        //print data
        printf("(%d, %d) ", ptr->key, ptr->data);
        //move to the next elem
        ptr = ptr->prev;
    }
    printf(" ]\n");
}

//insert link at the first location
void insertFirst(int key, int data) {
    //create the link
    struct node *link = (struct node *)malloc(sizeof(struct node));
    link->key = key;
    link->data = data;

    if (isEmpty()) {
        last = link;
    } else {
        //update first prev link
        head->prev = link;
    }
    //point it to lod first link
    link->next = head;
    //point first to new first link
    head = link;
}

//insert link at the last location
void insertLast(int key, int data) {
    //create a link
    struct node *link = (struct node *)malloc(sizeof(struct node));
    link->key = key;
    link->data = data;

    if (isEmpty()) {
        last = link;
    } else {
        //make link a new last link
        last->next = link;
        //make last node as prev of new link
        link->prev = last;
    }
    //point last to new last node
    last = link;
}

//delete first item
struct node *deleteFirst() {
    //save reference to first link
    struct node *tempLink = head;
    //if only one link
    if (head->next == NULL) {
        last = NULL;
    } else {
        head->next->prev = NULL;
    }
    head = head->next;
    //return the delete link
    return tempLink;
}

struct node *deleteLast() {
    //save reference to last link
    struct node *tempLink = last;
    //if only one node
    if (head->next == NULL) {
        head = NULL;
    } else {
        last->next->prev = NULL;
    }
    last = last->prev;
    return tempLink;
}

//delete a link with given key
struct node *delete (int key) {
    //start from the first link
    struct node *current = head;
    struct node *previous = NULL;
    //if list is empty
    if (head == NULL) {
        return NULL;
    }
    //navigate through list
    while (current->key != key) {
        //if is the last
        if (current->next == NULL) {
            return NULL;
        } else {
            //stroe reference to current link
            previous = current;
            //move to next link
            current = current->next;
        }
    }

    //found the match elem, update the link
    if (current == head) {
        //change the first to point to next link
        head = head->next;
    } else {
        //bypass the current link
        current->prev->next = current->next;
    }

    if (current == last) {
        //chage the last elem to prev link
        last = current->prev;
    } else {
        current->next->prev = current->prev;
    }
    return current;
}

bool insertAfter(int key, int newKey, int data) {
    //start from the first link
    struct node *current = head;
    //if list is empty
    if (head == NULL) {
        return false;
    }
    //navigate through list
    while (current->key != key) {

        //if it is last node
        if (current->next == NULL) {
            return false;
        } else {
            //move to next link
            current = current->next;
        }
    }
    //create a link
    struct node *newLink = (struct node *)malloc(sizeof(struct node));
    newLink->key = newKey;
    newLink->data = data;

    if (current == last) {
        newLink->next = NULL;
        last = newLink;
    } else {
        newLink->next = current->next;
        current->next->prev = newLink;
    }

    newLink->prev = current;
    current->next = newLink;
    return true;
}

int main() {
    insertFirst(1, 10);
    insertFirst(2, 30);
    insertFirst(3, 40);
    insertFirst(4, 2);
    insertFirst(5, 23);
    insertFirst(6, 56);
    printf("\nLIST (first to last): ");
    displayForward();

    printf("\n");
    printf("\nLIST (last to first): ");
    displayBackword();

    printf("\n");
    printf("\nLIST (after deleting first record): ");
    deleteFirst();
    displayForward();

    return 0;
}
  • 写回答

1条回答 默认 最新

  • 浪客 2022-08-25 01:06
    关注
    
    void insertFirst(int key, int data)里的
        struct node *link = (struct node *)malloc(sizeof(struct node));
    改为
        struct node *link = (struct node *)calloc(1,sizeof(struct node));
    
    next或prev有一个没有赋值。直接用calloc初始化为0
    下面一个函数的也一样。
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 8月31日
  • 已采纳回答 8月31日
  • 创建了问题 8月24日

悬赏问题

  • ¥20 Yolov5训练报错
  • ¥15 Unity发布gzip压缩的webgl之后让浏览器可以正常显示画面
  • ¥15 有没有人知道这种提示怎么关?现在不做ts项目了不知道咋关了,求解,现在我以前的js项目都是这种提示了
  • ¥15 为什么mysql做了碎片化处理data_free还是很高
  • ¥15 single positional indexer is out-of-bounds
  • ¥15 LSTM 模型数据量需要多少?
  • ¥15 mysql数据抓包开发报表
  • ¥15 linux系统下安装office打不开
  • ¥20 rsync脚本分发错误,文件不齐全
  • ¥15 labview顺序结构与时间延时