Day Vision

Reading Everyday,Extending Vision

C语言深处:通用链表

2022-09-16 06:39:01


来看一下链表节点的数据结构:欢迎大家加入C++学习交流群598131849 群内有资料分享//链表节点数据结构typedef struct linknode{ //唯一标识,按大小升序 int id; //数据通用指针 void *node


在本节中,我们将学习并实现一个通用的单向链表。先来看一下单向链表在内存中的存储形式:

链表中有3个属性,id为数据节点的唯一标识,在构建时按这个id来排序,也就是说我们要构建一个按id升序组成的单向链表。来看一下链表节点的数据结构:

欢迎大家加入C++学习交流群598131849 群内有资料分享

//链表节点数据结构

typedef struct linknode

{

//唯一标识,按大小升序

int id;

//数据通用指针

void *node;

//下一节点指针

struct linknode *next;

} linknode;

另外还要定义链表数据结构,链表头节点和其它个重要的内容都在这个结构中:

//链表数据结构

typedef struct linklist

{

//链表头节点

linknode *header;

//取得数据唯一标识函数指针,回调函数

int (*get_id)(void *);

//显示数据的函数指针,回调函数

void (*display)(void *);

//销毁数据函数指针,回调函数

void (*destructor)(void *);

} linklist;

接下来,我们来实现构建和销毁链表的两个函数:

//构建链表函数

linklist* linklist_init(int (*get_id)(void *), void (*display)(void *), void (*destructor)(void *))

{

//申请链表内存

linklist *l = malloc(sizeof(linklist));

//头节点

l->header = NULL;

//取得数据唯一标识函数指针,回调函数

l->get_id = get_id;

//显示数据的函数指针,回调函数

l->display = display;

//销毁数据函数指针,回调函数

l->destructor = destructor;

return l;

}

//销毁链表函数

void linklist_des(linklist *l)

{

//取得头节点

linknode *p = l->header;

//循环销毁所有节点数据

while (p != NULL)

{

//取得下一个节点

linknode *pNext = p->next;

//销毁节点数据

l->destructor(p->node);

//释放节点内存

free(p);

//下一个节点

p = pNext;

}

//释放链表内存

free(l);

}

然后再来看一下链表的“插入”操作。为链表插入一个新的节点有以下几个步骤:

  1. 从链表头节点开始向下遍历,并比较id的值。

  2. 找到id所应该在的位置,找到前一个节点p和后一个节点pNext。

  3. 断开p到pNext的next指针。

  4. 让p的next指针指向新的节点newNode。

  5. 让新节点newNode的next指针指向pNext。

插入节点的函数如下:

//插入新节点

void linklist_insert(linklist *l, void *node)

{

//取得id

int id = l->get_id(node);

//申请内存

linknode *newNode = malloc(sizeof(linknode));

newNode->id = id;

newNode->node = node;

newNode->next = NULL;

//二级指针

linknode **p = &l->header;

//找到第一个大于key的节点

while ((*p) != NULL && (*p)->id < id)

{

p = &(*p)->next;

}

//插入新节点

newNode->next = *p;

*p = newNode;

}

删除节点操作与插入相反,执行下面步骤:

  1. 从链表头节点开始向下遍历,并比较id的值。

  2. 找到准备删除的节点delNode,其前一个节点p和下一个节点pNext。

  3. 断开p指向delNode的next指针,断开delNode指向pNext的next指针。

  4. 将p的next指针指向pNext。

  5. 释放delNode节点。

再来看一下实现函数:

//删除节点

void linklist_del(linklist *l, int id)

{

//如果头节点为空

if (l->header == NULL)

{

return;

}

//二级指针

linknode **p = &l->header;

while ((*p) != NULL && (*p)->id != id)

{

p = &(*p)->next;

}

//等待释放节点

linknode *del = *p;

if (del == NULL)

{

return;

}

//释放内存

free(del);

*p = (*p)->next;

}

还有两个比较简单的“查找”函数和“显示”函数:

//查找

void* linklist_find(linklist *l, int id)

{

//取得头节点

linknode *p = l->header;

//遍历链表

while (p != NULL)

{

//如果id相等

if (p->id == id)

{

//返回数据节点

return p->node;

}

//下一个节点

p = p->next;

}

return NULL;

}

//显示链表内容

void linklist_display(linklist *l)

{

//取得头节点

linknode *p = l->header;

//遍历链表

while (p != NULL)

{

//显示数据内容

l->display(p->node);

//下一个节点

p = p->next;

}

}

最后通过一个例子来测试一下:

//学生数据结构

typedef struct

{

//学号

int no;

//姓名

char *name;

//性别

char sex;

//年龄

int age;

} student;

//取得学生学号,唯一id

int get_id_student(void *p)

{

student *h = (student *) p;

return h->no;

}

//显示学生信息

void display_student(void *p)

{

student *h = (student *) p;

printf("%d\t%s\t%c\t%d\n", h->no, h->name, h->sex, h->age);

}

//这是专门用于释放student类型元素的回调函数

void destructor_student(void *p)

{

student *h = (student *) p;

//释放名字属性

free(h->name);

//释放student

free(h);

}

主函数实现如下:

#define NAME_LEN (20)

int main(int argc, char **args)

{

linklist *link = linklist_init(&get_id_student, &display_student, &destructor_student);

student *h1 = malloc(sizeof(student));

h1->no = 20150501;

h1->name = malloc(NAME_LEN);

memcpy(h1->name, "Tomsen", NAME_LEN);

h1->sex = 'F';

h1->age = 22;

linklist_insert(link, h1);

student *h2 = malloc(sizeof(student));

h2->no = 20150502;

h2->name = malloc(NAME_LEN);

memcpy(h2->name, "Jerry", NAME_LEN);

h2->sex = 'M';

h2->age = 21;

linklist_insert(link, h2);

student *h3 = malloc(sizeof(student));

h3->no = 20150504;

h3->name = malloc(NAME_LEN);

memcpy(h3->name, "Lily", NAME_LEN);

h3->sex = 'F';

h3->age = 23;

linklist_insert(link, h3);

student *h4 = malloc(sizeof(student));

h4->no = 20150503;

h4->name = malloc(NAME_LEN);

memcpy(h4->name, "Wellean", NAME_LEN);

h4->sex = 'M';

h4->age = 22;

linklist_insert(link, h4);

printf("\nDisplayer all: \n");

linklist_display(link);

printf("\nFind 20150502:\n");

student *h = linklist_find(link, 20150502);

display_student(h);

printf("\nDelete 20150512:\n");

linklist_del(link, 20150502);

printf("\nDisplay all:\n");

linklist_display(link);

linklist_des(link);

return 0;

}

运行结果:

Displayer all:

20150501 Tomsen F 22

20150502 Jerry M 21

20150503 Wellean M 22

20150504 Lily F 23

Find 20150502:

20150502 Jerry M 21

Delete 20150512:

Display all:

20150501 Tomsen F 22

20150503 Wellean M 22

20150504 Lily F 23

欢迎大家加入C++学习交流群598131849 群内有资料分享

MORE