/*
 * 线性表的链式存储结构（双向链表）
 */
#ifndef DLINKLIST_H__
#define DLINKLIST_H__

// 宏定义
#define DLINKLIST_FORWARD 1  // 首部插入
#define DLINKLIST_BACKWARD 2  // 尾部插入

/*
 * 双向链表结构（普通结点）
 */
struct node_st {
    struct node_st *prev; // 前驱结点
    struct node_st *next; // 后继结点
    char data[1]; // 用来存储数据的占位符
};

/*
 * 双向链表结构（头结点）
 */
typedef struct {
    int size; // 存放数据类型的大小
    struct node_st head; // 头结点
}dlinklist;

/*
 * 封装给用户的两个接口函数
 */
typedef void dlinklist_show(const void *);
typedef int dlinklist_cmp(const void *, const void *);

/*
 * 初始化，创建双向链表
 */
dlinklist * dlinklist_create(int);

/*
 * 往双向链表中插入数据
 */
int dlinklist_insert(dlinklist *, const void *, int);

/*
 * 从双向链表中查找数据
 */
void * dlinklist_find(dlinklist *, const void *, dlinklist_cmp *);

/*
 * 从双向链表中删除数据
 */
int dlinklist_delete(dlinklist *, const void *, dlinklist_cmp *);

/*
 * 从双向链表中取出数据
 */
int dlinklist_fetch(dlinklist *, const void *, dlinklist_cmp *, void *);

/*
 * 遍历双向链表
 */
void dlinklist_travel(dlinklist *, dlinklist_show *);

/*
 * 销毁双向链表
 * 释放双向链表所占内存
 */
void dlinklist_destroy(dlinklist *);

#endif

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

#include "dlinklist.h"

/*
 * 初始化，创建双向链表
 */
dlinklist * dlinklist_create(int size) {
    dlinklist *node; // 头结点
    node = malloc(sizeof(*node));
    if (node == NULL) {
        return NULL;
    }

    // 给头结点赋值
    node->size = size;
    // 头结点的前驱指向到头结点的地址
    node->head.prev = &node->head;
    // 头结点的后继指向到头结点的地址
    node->head.next = &node->head;

    return node;
}

/*
 * 往双向链表中插入数据
 */
int dlinklist_insert(dlinklist *ptr, const void *data, int mode) {
    struct node_st *node; // 要插入数据的结点
    node = malloc(sizeof(*node) + ptr->size);
    if (node == NULL) {
        return -1;
    }

    // 给结点赋值
    memcpy(node->data, data, ptr->size);
    if (mode == DLINKLIST_FORWARD) {
        // 首部插入
        // 要插入结点的前驱结点指向到链表头结点的地址
        node->prev = &ptr->head;
        // 要插入结点的后继结点指向到链表头结点的后继结点
        node->next = ptr->head.next;
    } else if (mode == DLINKLIST_BACKWARD) {
        // 尾部插入
        // 要插入结点的前驱结点指向到链表头结点的前驱结点
        node->prev = ptr->head.prev;
        // 要插入结点的后继结点指向到链表头结点的地址
        node->next = &ptr->head;
    } else {
        return -3;
    }

    // 要插入结点的前驱结点的后继结点为当前要插入的结点
    node->prev->next = node;
    // 要插入结点的后继结点的前驱结点为当前要插入的结点
    node->next->prev = node;

    // 成功插入
    return 0;
}

/*
 * 从双向链表中查找结点
 */
static struct node_st * _find(dlinklist *ptr, const void *key, dlinklist_cmp *cmp) {
    struct node_st *node; // 要查找的结点
    // 遍历双向链表
    for (node = ptr->head.next; node != &ptr->head; node=node->next) {
        // 用户提供的比较函数，返回值为 0 表示查找到目标结点
        if (cmp(key, node->data) == 0) {
            break;
        }
    }

    return node;
}

/*
 * 从双向链表中查找数据
 */
void *dlinklist_find(dlinklist *ptr, const void *key, dlinklist_cmp *cmp) {
    struct node_st *node; // 要查找的结点
    node = _find(ptr, key, cmp);
    if (node == &ptr->head) {
        // 空链表，即没有找到目标结点
        return NULL;
    } else {
        // 返回结点的数据
        return node->data;
    }
}

/*
 * 从双向链表中删除数据
 */
int dlinklist_delete(dlinklist *ptr, const void *key, dlinklist_cmp *cmp) {
    struct node_st *node; // 要删除的结点
    // 从双向链表中查找结点
    node = _find(ptr, key, cmp);
    if (node == &ptr->head) {
        // 空链表，即没有找到目标结点
        return -1;
    }

    // 要删除结点的前驱结点的后继结点，指向到要删除结点的后继结点
    node->prev->next = node->next;
    // 要删除结点的后继结点的前驱结点，指向到要删除结点的前驱结点
    node->next->prev = node->prev;

    // 释放要删除结点所占内存
    free(node);
    // 将要删除结点指向为 NULL
    node = NULL;

    // 删除成功
    return 0;
}

/*
 * 从双向链表中取出数据
 */
int dlinklist_fetch(dlinklist *ptr, const void *key, dlinklist_cmp *cmp, void *data) {
    struct node_st *node; // 要取出的结点
    // 从双向链表中查找结点
    node = _find(ptr, key, cmp);
    if (node == &ptr->head) {
        // 空链表，即没有找到目标结点
        return -1;
    }

    // 要取出结点的前驱结点的后继结点，指向到要取出结点的后继结点
    node->prev->next = node->next;
    // 要取出结点的后继结点的前驱结点，指向到要取出结点的前驱结点
    node->next->prev = node->prev;

    if (data != NULL) {
        // 取出结点的数据，存放到 data 所指向的内存空间
        memcpy(data, node->data, ptr->size);
    }

    // 释放取出结点所占内存
    free(node);
    // 将取出结点指向为 NULL
    node = NULL;

    // 成功取出数据
    return 0;
}

/*
 * 遍历双向链表
 */
void dlinklist_travel(dlinklist *ptr, dlinklist_show *show) {
    struct node_st *node; // 当前结点
    for (node = ptr->head.next; node != &ptr->head; node = node->next) {
        // 用户提供的展示数据的函数
        show(node->data);
    }

    return; // 无返回值
}

/*
 * 销毁双向链表
 * 释放双向链表所占内存
 */
void dlinklist_destroy(dlinklist *ptr) {
    struct node_st *node, *next; // 要释放的结点，下一个结点
    for (node = ptr->head.next; node != &ptr->head; node = next) {
        // 获取下一个要释放的结点
        next = node->next;
        // 释放当前结点
        free(node);
    }

    // 释放当前链表
    free(ptr);

    return; // 无返回值
}

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

#include "dlinklist.h"

#define NAMESIZE 32

/*
 * 用户自定义的结构体
 * 学生信息
 */
struct stu_st {
    int id; // 学号
    char name[NAMESIZE]; // 姓名
    int chinese; // 语文
    int math; // 数学
    int english; // 英语
};

/*
 * 用户自定义的数据输出函数
 */
static void display(const void *ptr) {
    const struct stu_st *stu = ptr;
    printf("%d %s %d %d %d\n", stu->id, stu->name, stu->chinese, stu->math, stu->english);
}

/*
 * 用户自定义的数据比较函数
 */
static int cmp_by_id(const void *key, const void *record) {
    const int *k = key;
    const struct stu_st *r = record;

    return (*k - r->id);
}

/*
 * 用户自定义的数据比较函数
 */
static int cmp_by_name(const void *key, const void *record) {
    const char *k = key;
    const struct stu_st *r = record;
    return strcmp(k, r->name);
}

int main() {
    int i; // 循环索引值
    int ret; // 状态返回值
    dlinklist *list = NULL;
    struct stu_st stuinfo_st, *stuinfo_ptr; // 操作中的学生信息
    int id = 3; // 要查找的学号
    char *stu_name = "stu4"; // 要删除的姓名
    int stu_id; // 取出的学号

    /* 初始化双向链表 */
    list = dlinklist_create(sizeof(struct stu_st));
    if (list == NULL) {
        fprintf(stderr, "初始化双向链表 list 失败！\n");
        exit(1);
    }

    /* 往双向链表中插入 7 条随机数据 */
    for (i = 0; i < 7; i++) {
        stuinfo_st.id = i; // 学号
        snprintf(stuinfo_st.name, NAMESIZE, "stu%d", i); // 姓名
        stuinfo_st.chinese = rand() % 100; // 语文
        stuinfo_st.math = rand() % 100; // 数学
        stuinfo_st.english = rand() % 100; // 英语

        ret = dlinklist_insert(list, &stuinfo_st, DLINKLIST_FORWARD);
        if (ret != 0) {
            fprintf(stderr, "数据插入失败！\n");
            exit(1);
        }
    }

    /* 遍历双向链表 */
    printf("链表中的学生信息：\n");
    dlinklist_travel(list, display);

    /* 从双向链表中查找数据 */
    stuinfo_ptr = dlinklist_find(list, &id, cmp_by_id);
    if (stuinfo_ptr == NULL) {
        printf("没有找到任何数据。\n");
    } else {
        /* 用户自定义的函数显示数据 */
        printf("查找到的学生信息：\n");
        display(stuinfo_ptr);
    }

    /* 从双向链表中删除数据 */
    ret = dlinklist_delete(list, stu_name, cmp_by_name);
    if (ret != 0) {
        printf("数据删除失败！\n");
    }

    /* 从双向链表中取出数据 */
    ret = dlinklist_fetch(list, &id, cmp_by_id, &stu_id);
    if (ret != 0) {
        printf("数据取出失败！\n");
    }
    printf("从链表中取出学号：%d\n", stu_id);

    /* 遍历双向链表 */
    printf("链表中的学生信息：\n");
    dlinklist_travel(list, display);
    /* 销毁双向链表 */
    dlinklist_destroy(list);

    exit(0);
}

OBJS=main.o dlinklist.o
CC=gcc
CFLAGS+=-c -Wall -g
dlinklist: $(OBJS)
    $(CC) $^ -o $@

%.o: %.c
    $(CC) $^ $(CFLAGS) -o $@

clean:
    $(RM) *.o dlinklist -r

root@RicenOS:~# make
gcc main.c -c -Wall -g -o main.o
gcc dlinklist.c -c -Wall -g -o dlinklist.o
gcc main.o dlinklist.o -o dlinklist
root@RicenOS:~# ./dlinklist
链表中的学生信息：
6 stu6 72 36 11
5 stu5 26 40 26
4 stu4 90 59 63
3 stu3 21 62 27
2 stu2 86 92 49
1 stu1 15 93 35
0 stu0 83 86 77
查找到的学生信息：
3 stu3 21 62 27
从链表中取出学号：3
链表中的学生信息：
6 stu6 72 36 11
5 stu5 26 40 26
2 stu2 86 92 49
1 stu1 15 93 35
0 stu0 83 86 77