2023年5月12日22:35:37
1. 数据结构
普通节点:数据域 *data,指针域 *prev、*next
头结点:size + 普通节点
其中:头结点data为NULL,size是指定data空间大小,data数据类型未定,也就是说头结点不同于普通节点
![image-20230512224341995](https://yinxf-note.oss-cn-beijing.aliyuncs.com/PicGo/PicGo-2.3.0/2023-05-12/22:43:42-d6d827.png)
本文想要实现的额外功能: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是当前节点。
![image-20230512224446867](https://yinxf-note.oss-cn-beijing.aliyuncs.com/PicGo/PicGo-2.3.0/2023-05-12/22:44:46-3822cd.png)
代码实现
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;
}
7. 全部代码
2023-05-12-双向链表-llist.c
2023-05-12-双向链表-llist.c
2023-05-12-双向链表-main.c