双向链表_C语言

Kael'thas / 2023-05-13 / 原文

2023年5月12日22:35:37

1. 数据结构

普通节点：数据域 *data，指针域 *prev、*next

头结点：size + 普通节点

其中：头结点data为NULL，size是指定data空间大小，data数据类型未定，也就是说头结点不同于普通节点

本文想要实现的额外功能：data数据无论是多大，无论是什么类型，都能直接存放进去

代码实现：

struct llist_node_st {
    void *data;
    struct llist_node_st *prev;
    struct llist_node_st *next;
};
 
typedef struct {
    int size;
    struct llist_node_st head;
} LLIST;

2. 插入

链表插入操作的思路是：

给newnode和newnode的data动态分配空间（data数据类型未知，因此也需要动态分配空间）
用循环给newnode的data和指针赋值

链表插入方式分为首部插入、尾部插入。new是待插入节点，cur是当前节点。

代码实现

int llist_insert(LLIST *ptr, const void *data, int mode) {
    struct llist_node_st *newnode;
 
//给newnode和对应的data分配空间。原因是保证传入data的任何数据都能接收，所以动态分配
    newnode = malloc(sizeof(*newnode));
    if (newnode == NULL)
        return -1;
 
    newnode->data = malloc(ptr->size);
    if (newnode == NULL)
        return -2;
 
//给newnode的data和指针赋值
    memcpy(newnode->data, data, ptr->size);
 
    if (mode == LLIST_FORWARD) {
        newnode->prev = &ptr->head;
        newnode->next = ptr->head.next;
        newnode->prev->next = newnode;
        newnode->next->prev = newnode;
    } else if (mode == LLIST_BACKWARD) {
        newnode->prev = ptr->head.prev;
        newnode->next = &ptr->head;
    newnode->prev->next = newnode;
        newnode->next->prev = newnode;
    } else {
        return -3;
    }
}

3. 销毁

销毁整个链表：

将cur节点单独保存为del，cur指向下一个
free(cur.data)
free(cur)

free两次，是因为前期malloc两次

代码实现：

void llist_destroy(LLIST *ptr) {
 
    struct llist_node_st *cur, *next;
 
    for (cur = ptr->head.next; cur != &ptr->head; cur = next) {
        next = cur->next;//cur 是要删除的节点，所以单独提取出来
        free(cur->data);
        free(cur);
    }
    free(ptr);
}

4. 遍历链表

具体的data中具体类型无法得知，所以要通过回调函数，等待用户传参，才能实现遍历的具体内容。

typedef void llist_op(const void *);
 
struct llist_node_st {
    void * data;
    struct llist_node_st *prev;
    struct llist_node_st *next;
};
 
typedef struct {
    int size;
    struct llist_node_st head;
} LLIST;
 
 
//遍历链表，op作用于cur->data
void llist_travel(LLIST *ptr, llist_op *op) {
    struct llist_node_st *cur;
 
    for (cur=ptr->head->next;cur!=&(ptr->head); cur=cur->head){
         op(cur->data);
    }
}
 
//回调函数提供op信息,打印每个cur->data中的id、name、math、chinese
static void print_s(const void *record) {//record指代cur->data
    const struct score_st *r = record;
    printf("%d %s %d %d\n", r->id, r->name, r->math, r->chinese);
}
 
 
int main(){
    //用户提供的data信息
    struct score_st {
        int id;
        char name[NAMESIZE];
        int math;
        int chinese;
    };
 
    LLIST *handler;
    handler = llist_create(sizeof(tmp));
    llist_travel(handler, print_s);
    return 0;
}

5. 查找

查找特定节点的数据域，是要根据传入参数查找。传入的key为学生id时，用循环只要node的data的id与key差值为0，说明找到了中断并返回即可。

typedef int llist_cmp(const void *, const void *);

static int id_cmp(const void *key, const void *record) {
    const int *k = key;//key是用户传入参数，是要查找的节点的data的id
    const struct score_st *r = record;//record是节点的data
    return (*k - r->id);
}//返回差值

static struct llist_node_st *find_(LLIST *ptr, const void *key, llist_cmp *cmp) {
    struct llist_node_st *cur;

    for (cur = ptr->head.next; cur != &ptr->head; cur = cur->next) {
        if (cmp(key, cur->data) == 0)
            break;
    }
    return cur;
}//(2)找到并返回key相同的节点，cmp差值为0说明找到

void *llist_find(LLIST *ptr, const void *key, llist_cmp *cmp) {
    return find_(ptr, key, cmp)->data;
}//(1)找到并返回key相同的节点的data
int main{
    
    LLIST *handler;
    int id = 3;
    struct score_st tmp;
    struct score_st * data;
    data = llist_find(handler, &id, id_cmp);//(0)
    llist_destroy(handler);
    return 0;
}

6. 删除/获取

先找到特定元素，即按照比较参数返回0的元素，将被删节点保存到node，断开指针指向，free之前动态分配的空间

//删除指定节点
int llist_delete(LLIST *ptr, const void *key, llist_cmp *cmp) {
    struct llist_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->data);
    free(node);
    return 0;
}

//获取并删除
int llist_fetch(LLIST *ptr, const void *key, llist_cmp *cmp, void *data) {
    struct llist_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)
        //extern void *memcpy(void *dest, void *src, unsigned int count);
        memcpy(data, node->data, ptr->size);
    free(node->data);
    free(node);
    return 0;
}

static struct llist_node_st *find_(LLIST *ptr, const void *key, llist_cmp *cmp) {
    struct llist_node_st *cur;

    for (cur = ptr->head.next; cur != &ptr->head; cur = cur->next) {
        if (cmp(key, cur->data) == 0)
            break;
    }
    return cur;//如果找不到，会返回头结点的地址
}

static int name_cmp(const void *key, const void *record) {
    const char *k = key;
    const struct score_st *r = record;//r是节点的data
    return strcmp(k, r->name);
}

int main() {    
    LLIST *handler;
	char *n = "std_5";
    int ret=llist_delete(handler, n, name_cmp);
   	return 0;
}