室内设计学校网站,惠州seo排名,哈尔滨品牌网站建设,公路建设项目可行性研究报告编制办法哪个网站查最新版一、简介概述
1、普通链表数据结构 每个节点的next指针指向下一个节点的首地址。这样会有如下的限制#xff1a;
一条链表上的所有节点的数据类型需要完全一致。对某条链表的操作如插入#xff0c;删除等只能对这种类型的链表进行操作#xff0c;如果链表的类型换了#…一、简介概述
1、普通链表数据结构 每个节点的next指针指向下一个节点的首地址。这样会有如下的限制
一条链表上的所有节点的数据类型需要完全一致。对某条链表的操作如插入删除等只能对这种类型的链表进行操作如果链表的类型换了就要重新再封装出一套一样的操作泛化能力差
2、侵入式链表数据结构 节点的链接成员指向的是下一个节点的链接成员。使用侵入式链表的好处是
节点类型无需一致只需要成员节点element_t包含list_node_t成员即可泛化能力强所有链表的操作方式均可统一
typedef struct list_node list_node_t;//链表节点结构体定义
typedef struct list_node {list_node_t* prev;list_node_t* next;
} list_node_t;//链表结构体定义
typedef struct list {int list_size;list_node_t head;
} list_t;//链表成员结构体定义重点需要包含list_node_t定义
typedef struct element {list_node_t list_node;int element_type;int element_size;char element_data[1];
} element_t;
二、详细介绍
侵入式链表中的节点只有地址信息能够访问节点上的数据成员变量主要靠两个核心函数
offsetofcontainer_of
1、offsetof
1宏原型
#if defined _MSC_VER !defined _CRT_USE_BUILTIN_OFFSETOF#ifdef __cplusplus#define offsetof(s,m) \((::size_t)reinterpret_castchar const volatile((((s*)0)-m)))#else#define offsetof(s,m) ((size_t)(((s*)0)-m))#endif
#else#define offsetof(s,m) __builtin_offsetof(s,m)
#endif
2宏作用
计算结构体成员相对于结构体的偏移
3参数说明
type 结构体类型member结构体成员
4原理分析
偏移 成员地址 - 结构体地址若结构体地址为0则偏移 成员地址
5应用示例
typedef struct element {list_node_t list_node;int element_type;int element_size;char element_data[1];
} element_t;printf(offset: %zd %zd %zd\r\n, offsetof(element_t, list_node), offsetof(element_t, element_type), offsetof(element_t, element_size));//打印结果
offset: 0 16 20
2、container_of
1宏原型
#define container_of(ptr, type, member) \((type*)(((char*)((type*)(ptr))) - offsetof(type, member)))
2宏作用 通过结构体的成员结构体成员的地址以及结构体的类型来获取结构体的首地址。
3参数说明 ptr 结构体成员的地址 type 结构体类型 member结构体成员
4原理分析 结构体首地址 成员地址 - 成员偏移成员偏移通过offsetof宏求出
5应用示例
int main()
{element_t element, *p_element;element.element_type 1234;element.element_size 5678;p_element container_of(element.list_node, element_t, list_node);printf(p_element-element_type :%d p_element-element_size :%d\n, p_element-element_type, p_element-element_size);
}p_element-element_type :1234 p_element-element_size :5678
3、侵入式链表
介绍到这里就可以理解面前第一章第2小节介绍的节点类型无需一致只需要成员节点element_t包含list_node_t成员即可。我们只要知道list_node_t成员地址就可以通过offsetofcontainer_of获取整个element_t的成员变量。
示例代码如下
#include list.h
#include assert.h
#include stdio.h
#include stdlib.h
#include windows.hvoid ListInit(list_t* list) {list-list_size 0;ListNodeInit(list-head);
}void ListAppend(list_t* list, list_node_t* node) {node-next list-head;node-prev list-head.prev;node-prev-next node;list-head.prev node;list-list_size;
}void ListRemove(list_t* list, list_node_t* node) {ListNodeDetach(node);ListNodeInit(node);list-list_size--;
}list_node_t* ListFirstGet(const list_t* list) {return !ListEmpty(list) ? list-head.next : NULL;
}list_node_t* ListLastGet(const list_t* list) {return !ListEmpty(list) ? list-head.prev : NULL;
}bool ListEmpty(const list_t* list) {return !ListEnlisted(list-head);
}void ListNodeInit(list_node_t* node) {node-prev node;node-next node;
}void ListNodeDetach(list_node_t* node) {node-prev-next node-next;node-next-prev node-prev;
}bool ListEnlisted(const list_node_t* node) {return node-prev ! node;
}list_t list_;int main()
{list_node_t* list_node NULL;ListInit(list_);for (int i 0; i 15; i) {element_t* element (element_t*)malloc(sizeof(element_t) sizeof(AI_UPLOAD_ALL_INFO_T));element-element_type i;element-element_size sizeof(AI_UPLOAD_ALL_INFO_T);ListAppend(list_, element-list_node);printf(push element :%d queue_size :%d\n, element-element_type, list_.list_size);list_node ListLastGet(list_);element_t* element1 GetListNode(list_node, element_t);printf(QueueLastGet element :%d queue_size :%d\n, element1-element_type, list_.list_size);}printf(list_size :%d\n, list_.list_size);while ((list_node ListFirstGet(list_)) ! NULL) {element_t* element GetListNode(list_node, element_t);printf(pop element :%d queue_size :%d\n, element-element_type, list_.list_size);ListRemove(list_, list_node);}return 0;
}
