c - 双连接列表中的插入位置和弹出位置功能

Question

我的双连接列表有问题，我必须添加 2 个函数。首先在指定位置添加元素(如果位置不存在，则必须在列表末尾添加元素)，例如:

Elements: 1 2 3
Add on position (we start numbering from 0): 1 element: 21
Elements after adding: 1 21 2 3

第二个删除指定位置上的元素(如果位置不存在则不执行任何操作)，例如:

Elements: 1 2 3
Delete position: 1
Elements after deleting: 1 3

这是我尝试编写的内容，问题是当我尝试向列表添加或从列表中删除元素时，我的程序崩溃了。感谢您的时间和帮助!

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

struct ellist2c {
    int x;
    struct ellist2c * right;
    struct ellist2c * left;

    };
struct list2c {
    struct ellist2c * begining;
    struct ellist2c * end;
    int position;
};
void push(int newdata, struct list2c * list) {
    struct ellist2c * newEl = (struct ellist2c * ) malloc(sizeof(struct ellist2c ));
    newEl -> x = newdata;
    newEl -> left= NULL;
    if (list -> position == 0) {
        list -> begining= newEl;
        list -> end= newEl;
        newEl -> right= NULL;
    } else {
        newEl -> right= list -> end;
        list -> end-> left= newEl;
        list -> end= newEl;
    }
    list -> position++;
}
void pushonposition(int newData, int poz, struct list2c * list){
    struct ellist2c * sk = (struct ellist2c * ) malloc(sizeof(struct ellist2c ));
    sk -> x = newData;
    struct ellist2c * el = (struct ellist2c * ) malloc(sizeof(struct ellist2c ));
    el = list -> begining;
    if (poz == 0) {
        el -> x = newData;
        if (list -> begining == NULL) {
            el -> right = NULL;
            el -> left = NULL;
            list -> begining = el;
            list -> end = el;
        } else {
            el -> left = NULL;
            list -> begining -> left = el;
            el -> right = list -> begining;
            list -> begining = el;
        }
        list -> position++;
        return;
    }
    if (poz >= list -> position - 1) {
        el -> x = newData;
        if (list -> begining == NULL) {
            el -> right = NULL;
            el -> left = NULL;
            list -> begining = el;
            list -> end = el;
        } else {
            el -> right = NULL;
            el -> left = list -> end;
            list -> end -> right = el;
            list -> end = el;
        }
        list -> position++;
        return;
    }
    for (int i = 0; i < poz; i++) {
        el = el -> right;
    }
    sk -> left = el -> left;
    struct ellist2c * before = (struct ellist2c * ) malloc(sizeof(struct ellist2c ));
    before = list -> begining;
    for (int i = 0; i < poz - 1; i++) {
        before = before -> right;
    }

    sk -> right = before -> right;
    before -> right = sk;
    sk -> right -> left = sk;
}
void popposition(struct list2c * list, int index) {
    struct ellist2c * el = (struct ellist2c * ) malloc(sizeof(struct ellist2c ));
    if (list -> begining == NULL) {
        return;
    }
    if (index == 0) {
        if (list -> begining == NULL) {
            return;
        }

        if (list -> begining == list -> end) {
            el = list -> end;
            free(el);
            list -> end = NULL;
            list -> begining = NULL;
            printf("Empty list");
        } else {
            el = list -> end;
            list -> end = el -> left;
            free(el);
            list -> end -> right = NULL;
        }
        list -> position--;
        return;
    }
    el = list -> begining;
    for (int i = 0; i < index; i++) {
        el = el -> right;
        if (el == NULL) {
            return;
        }
    }
    if (el != list -> end && el != list -> begining) {
        el -> right -> left = el -> left;
        el -> left -> right = el -> right;
        free(el);
        return;
    }
    if (el == list -> end) {
        list -> end = el -> left;
        list -> end -> right = NULL;
        free(el);
        return;
    }
    if (el == list -> begining) {
        list -> begining = el -> right;
        list -> begining -> left = NULL;
        free(el);
        return;
    }}
void print(struct list2c * list) {
        struct ellist2c * el = (struct ellist2c * ) malloc(sizeof(struct ellist2c ));
        el = list -> begining;
        while (el) {
            printf("%d\n", el -> x);
            el = el -> left;
}
}
int main(){
    struct list2c * list = (struct list2c * ) malloc(sizeof(struct list2c ));
    list -> begining= NULL;
    list -> end = NULL;
    list -> position = 0;
    push(5, list);
    push(6, list);
    push(7, list);
    pushonposition(1, 1, list);
    pushonposition(1, 1, list);
    popposition(1, list);
    print(list);
return (0);
}

Answer 1

您的代码非常困惑，并且有许多未使用的变量和内存泄漏。

我稍微修复了代码，您应该从重写 pop_position 函数开始:

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


#define EMPTY 0

typedef struct list_node {
    int x;
    struct list_node *first;
    struct list_node *last;
} *ListNode;

typedef struct list_master {
    ListNode first;
    ListNode last;
    int size;
} *ListMaster;

void push(int value, struct list_master *list) {
    ListNode node = malloc(sizeof(ListNode));
    node->x = value;
    node->last = NULL;
    if (list->size == EMPTY) {
        list->first = node;
        list->last = node;
        node->first = NULL;
    } else {
        node->first = list->last;
        list->last->last = node;
        list->last = node;
    }
    ++list->size;
}

void print(ListMaster list) {
    ListNode el;
    el = list->first;
    while (el) {
        printf("%d\n", el->x);
        el = el->last;
    }
}

void push_on_position(int newData, int position, ListMaster list) {
    ListNode sk = malloc(sizeof(ListNode));
    sk->x = newData;
    ListNode el = list->first;
    if (position == EMPTY) {
        el->x = newData;
        if (list->first == NULL) {
            el->last = NULL;
            el->first = NULL;
            list->first = el;
            list->last = el;
        } else {
            el->first = NULL;
            list->first->first = el;
            el->last = list->first;
            list->first = el;
        }
        ++list->size;
        return;
    }
    if (position >= list->size - 1) {
        el->x = newData;
        if (list->first == NULL) {
            el->last = NULL;
            el->first = NULL;
            list->first = el;
            list->last = el;
        } else {
            el->last = NULL;
            el->first = list->last;
            list->last->last = el;
            list->last = el;
        }
        ++list->size;
        return;
    }
    for (int i = 0; i < position; i++) {
        el = el->last;
    }
    sk->first = el->first;
    ListNode before = list->first;
    for (int i = 0; i < position - 1; i++) {
        before = before->last;
    }

    sk->last = before->last;
    before->last = sk;
    sk->last->first = sk;
}

int main() {
    ListMaster list = malloc(sizeof(ListMaster));
    list->first = NULL;
    list->last = NULL;
    list->size = 0;
    push(5, list);
    push(6, list);
    push(7, list);

    push_on_position(1, 1, list);
    push_on_position(1, 1, list);

    //Need to be fixed
    //pop_position(1, list);
    print(list);

    //implement destroy - free all nodes and master
    //destroy(list)

    return (0);
}

输出

5
1
1
6
7