//
// Created by Liu Xianmeng on 2023/10/3 18:16
//
# include <stdio.h>
# include <stdlib.h>

#ifndef CDATASTRCUTRUES_20230930_DOUBLELINKEDLIST_H
#define CDATASTRCUTRUES_20230930_DOUBLELINKEDLIST_H

// 定义双向链表的结点
typedef struct DoubleLinkedNode{
    int data;
    struct DoubleLinkedNode *pre;
    struct DoubleLinkedNode *next;
}DoubleLinkedNode;

// 定义双向链表本身
typedef struct DoubleLinkedList {
    int size; // 表的实际长度
    DoubleLinkedNode *LNode;     // 表的左边界（不包含数据）
    DoubleLinkedNode *RNode;     // 表的右边界（不包含数据）
}DoubleLinkedList;

/**
 * 初始化算法
 * @param L 传入要初始胡的指针
 */
DoubleLinkedList * initList(DoubleLinkedList *L) {
    ...
}

... 其它函数的声明或实现

#endif //CDATASTRCUTRUES_20230930_DOUBLELINKEDLIST_H

/**
 * 初始化算法
 * @param L 传入要初始化的指针
 */
DoubleLinkedList* initList(DoubleLinkedList *L) {
    L = (DoubleLinkedList *) malloc(sizeof(DoubleLinkedList));
    // 初始化size=0
    L->size = 0;
    // 初始化left结点的存储空间
    L->left = (Node *)malloc(sizeof(Node));
    L->left->prev = NULL;
    L->left->next = NULL;
    L->left->data = -1;
    // 初始化right结点的存储空间
    L->right = (Node *)malloc(sizeof(Node));
    L->right->prev = NULL;
    L->right->next = NULL;
    L->right->data = -1;
    // 初始化left和right结点的指向
    L->left->next = L->right;
    L->right->prev = L->left;
    // 返回初始化的结果
    return L;
}

/**
 * 向双向链表插入单个元素
 * @param DoubleLinkedList  双向链表
 * @param pos               插入元素的位置 序列位置
 * @param e                 要插入的元素
 * @return                  插入位置不合法 返回-1 插入成功返回1
 */
int insertOne(DoubleLinkedList *L, int pos, int data) {
    // 如果插入的位置不合法 返回-1
    if(pos < 1 || pos > L->size + 1) {
        return -1;
    }
    /////////// 接下来执行插入操作 关键是找到插入位置的上一个位置 ///////////
    // 1 先用指针p指向头结点
    Node *p = L->left;
    // 2 然后向后移动pos-1个位置
    for(int i = 1; i <= pos-1; ++i) p = p->next;
    // 3 执行插入
    // 3.1 先创建一个新的结点并分配空间 初始化数据
    Node *curNode;
    curNode = (Node *)malloc(sizeof(Node));
    curNode->data = data;
    // 3.2 执行插入
    curNode->next = p->next;
    curNode->prev = p;
    p->next->prev = curNode;
    p->next = curNode;
    // 3.3 更新DoubleLinkedList的size大小
    ++L->size;

    return 1; // 成功插入数据返回1
}

//
// Created by Liu Xianmeng on 2023/10/3 18:36
//
# include <stdio.h>
# include "DoubleLinkedList.h"

int main() {
    DoubleLinkedList *L;
    L = initList(L); // 初始的时候链表为空
    insertOne(L, 1, 1);
    insertOne(L, 1, 2);
    insertOne(L, 1, 3);
    insertOne(L, 2, 10);
    printf("断点调试");
    return 0;
}

/**
 * 从链表中删除pos位置的元素
 * @param L     带有虚拟头结点的双向链表
 * @param pos   pos是元素的序号（非下标）
 * @param e     接收被删除的值
 * @return 成功删除返回1 删除失败返回0
 */
int deleteOne(DoubleLinkedList *L, int pos, int *e) {
    // 验证序号不合法 返回0
    if(pos < 1 || pos > L->size) return 0;

    // 指针指向虚拟左结点
    Node *p = L->left;
    // 指针向后移动pos-1个位置
    for(int i = 1; i<= pos - 1; ++i) p = p->next;
    // *e接收被删除的值
    *e = p->next->data;
    // toFreeNode指针暂时指向被删除的结点
    Node *toFreeNode = p->next;
    // 执行删除操作
    p->next = p->next->next;
    p->next->prev = p;
    --L->size; // 删除之后size-1
    // 🎯释放被删除的结点的存储空间
    free(toFreeNode);

    // 返回结果
    return 1; // 成功删除
}

//
// Created by Liu Xianmeng on 2023/10/3 18:36
//
# include <stdio.h>
# include "DoubleLinkedList.h"

int main() {
    DoubleLinkedList *L;
    L = initList(L);
    insertOne(L, 1, 1);
    insertOne(L, 1, 2);
    insertOne(L, 1, 3);
    insertOne(L, 2, 10);
    int d;
    deleteOne(L, 2, &d);
    printf("断点调试");
    return 0;
}