时间戳

首页 > 解决方案 > C删除函数中的循环双向链表

c - C删除函数中的循环双向链表

问题描述

我有一个循环双向链表。

该deletefront()功能不起作用：输出错误。错误是什么？

其他功能正在运行。deletefront但是在调用函数后显示后我得到错误的输出。应该删除的 100 值仍然出现。请改正。

我已经包含了 C 源代码：

// circular doubly linked list
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *rlink;
    struct node *llink;
} node;

node *head = NULL;

node *getnode(int ele) {
    node *ptr;
    ptr = (node *)malloc(sizeof(node));
    if (ptr == NULL) {
        printf("memory not alloc");
        exit(0);
    }
    if (ptr != NULL) {
        ptr->data = ele;
        ptr->rlink = NULL;
        ptr->llink = NULL;
    }
    return ptr;
}

void insertfront(int ele) {
    node *newnode;
    newnode = getnode(ele);
    if (head == NULL) {
        head = newnode;
        head->rlink = head;
        head->llink = head;
    } else {
        head->llink = newnode;
        newnode->rlink = head;
        head = newnode;
    }
}

void insertend(int ele) {
    node *newnode;
    newnode = getnode(ele);
    if (head == NULL) {
        head = newnode;
        head->rlink = head;
        head->llink = head;
    } else {
        node *temp = head;
        do {
            temp = temp->rlink;
        } while (temp != head->llink);

        newnode->rlink = temp->rlink;
        temp->rlink = newnode;
        newnode->llink = temp;
    }
}

int lenlist() {
    node *temp;
    int count = 0;
    temp = head;
    do {
        temp = temp->rlink;
        count++;
    } while (temp != head);

    return count;
}

void insertatpos(int ele,int pos) {
    if (pos == 1) {
        insertfront(ele);
    } else
    if (pos == (lenlist() + 1)) {
        insertend(ele);
    } else
    if (pos > 1 && pos <= (lenlist() + 1)) {
        node *prev, *curr;
        node *newnode = getnode(ele);
        int count = 1;
        curr = head;//curr points to 1st node
        do {
            prev = curr;
            count++;
            curr = curr->rlink;
            if (count == pos) {
                prev->rlink = newnode;
                newnode->llink = prev;
                newnode->rlink = curr;
                curr->llink = newnode;
            }
        } while (curr != head);
    } else {
        printf("invalid position");
    }
}

void delfront() {
    if (head == NULL)
        printf("empty list");

    node *aux;
    node *lastnode, *secondnode;
    aux = head;
    lastnode = head->llink;
    secondnode = head->rlink;

    secondnode->llink = lastnode;
    lastnode->rlink = secondnode;

    free(aux);

    head = secondnode;
}

void display() {
    node *aux = head;
    do {
        printf("%d->", aux->data);
        aux = aux->rlink;
    } while (aux != head);
    printf("\n");
}

int main() {
    insertfront(100);
    insertend(20);
    printf("\n%d\n", lenlist());
    insertatpos(45, 2);
    display();
    delfront();
    display();
}

标签： clistdoubly-linked-list

解决方案

The problem is not in the deletefront() function, instead, you have missed updating a few links in the insertfront() and insertend() functions.

I have updated the code here and also added the comment where I made the changes. Try to visualise it using an example.

However, I suggest that you solve such issues using a debugger or go through the code with a sample test case. It will improve you debugging as well as coding skills!

推荐阅读