dw制作asp网站模板下载,驻马店网站建设zmdsem,如何配置 网站二级域名,简历模板制作神器记录下C语言中数据结构链表的2种方式#xff0c;其中内核的表达方式可谓是经典。
一、数据和指针域混合 数据域和指针域定义在同一个结构体定义中#xff0c;C语言中没有模板#xff0c;意味着一个代码工程有多少数据结构就需要多少对链表的.c和.h#xff0c;事实上这样会… 记录下C语言中数据结构链表的2种方式其中内核的表达方式可谓是经典。
一、数据和指针域混合 数据域和指针域定义在同一个结构体定义中C语言中没有模板意味着一个代码工程有多少数据结构就需要多少对链表的.c和.h事实上这样会导致很多的冗余代码。
头文件 list.h
#includestdio.htypedef struct node
{DATATYPE data; //数据域struct node *next; //指针域
}node;typedef struct list
{node *first; //指向头节点node *last; //指向尾节点该成员可以要可以不要int size
};//初始化单链表
void init_list(list *list);
//尾部新增数据node
void push_back(list *list, DATATYPE buf);
//头部新增数据node
void push_front(list *list, DATATYPE buf);
//打印链表数据结构
void show_list(list *list);
//尾部删除数据node
void pop_back(list *list, DATATYPE buf);
//头部删除数据node
void pop_front(list *list, DATATYPE buf);
//获取链表数据深度
int length(list *list);
//清空链表数据结构
void clear(list *list);
//销毁链表
void destroy(list *list);
接口文件 list.c
#include list.h
#include stdio.h//初始化链表head结点不计入size且数据域无值
void init_list(list *list)
{list-first list-last (node *)malloc(sizeof(node));assert(NULL ! list-first);//为head节点赋NULL初始值list-first-next NULL;list-size 0;
}//尾插存入新结点数据
void push_back(list *list, DATATYPE buf)
{//创建尾插节点node *s (node *)malloc(sizeof(node));assert(NULL ! s);s-data buf; //根据数据结构DATATYPE做相应处理s-next NULL;//将尾插节点连接到链表尾部list-last-next s;//更改管理节点中last的指向list-last s;//更改有效节点的个数list-size;
}//头插存入新节点数据
void push_front(list *list, DATATYPE buf)
{node *s (node *)malloc(sizeof(node));assert(NULL ! s);s-data buf;s-next list-first-next;list-first-next s;//如果是链表的第一个有效节点需要改变尾指针的指向if(list-size 0){list-last s;}//更改有效节点的个数list-size;
}//尾删取出结点数据
void pop_back(list *list, DATATYPE* buf)
{//链表中是否还有结点if(list-size 0)return ;//寻找倒数第二个结点node *p list-first;while(p-next ! list-last)p p-next;//取出尾部节点数据buf p-next-data;//删除尾部结点free(p-next);//更改尾指针的指向list-last p;//更改现尾结点的指针域list-last-next NULL;list-size --;
}//头删取出结点数据
void pop_front(list *list, DATATYPE* buf)
{//链表中是否有元素if(list-size 0)return;//临时保存要删除结点的地址Node *p list-first-next;//删除该结点与链表的连接list-first-next p-next;//取出头节点数据buf p;//删除结点free(p);//该链表是否只有一个有效结点if(list-size 1){//更改尾指针的指向list-last list-first;}//更改有效结点个数list-size--;
}
二、数据和指针域分离 数据域与指针域分离是Linux内核的写法非常有特点抽象了链表中共性的指针操作让使用者只需要关注自己的数据域。
头文件list_common.h
只构造小结构体 list 相关的宏或则接口该部分是共用的只需要一份
//2024-04-01 实践记录
#includestdio.h
#includestdlib.h//遍历链表typeof内建函数在vc下无法编译不确定什么原因
//返回结构体成员在内存中的偏移量
#define offsetof(type, memb) (unsigned long)(((type *)0)-memb)
//返回通过结构体变量的一个成员的地址找到这个结构体变量的首地址ptr,type,member分别代表指针、类型、成员
#define container_of(ptr, type, member) ({ \const typeof(((type *)0)-member)*__mptr (ptr); \(type *)((char *)__mptr - offsetof(type, member)); })//以pos遍历以head为头的链表
#define list_entry(ptr, type, member) \((type *)((char *)(ptr)-(unsigned long)(((type *)0)-member)))
#define list_for_each(pos, head) \for (pos (head)-next; pos ! (head); pos pos-next)
#define list_for_each_entry(pos, head, member) \for (pos container_of((head)-next, typeof(*pos), member); \pos-member ! (head); \pos container_of(pos-member.next, typeof(*pos), member))//定义一个双向链表
struct list_head {struct list_head *next, *prev;
};
//初始化链表
static inline void
INIT_LIST_HEAD(struct list_head *list)
{list-next list-prev list;
}//链表操作
static inline void
__list_add(struct list_head *entry,struct list_head *prev, struct list_head *next)
{next-prev entry;entry-next next;entry-prev prev;prev-next entry;
}//在head之后插入节点
static inline void
list_add(struct list_head *entry, struct list_head *head)
{__list_add(entry, head, head-next);
}//在尾部添加节点
static inline void
list_add_tail(struct list_head *entry, struct list_head *head)
{__list_add(entry, head-prev, head);
}//删除链表结点
static inline void __list_del(struct list_head* prev, struct list_head* next)
{next-prev prev;prev-next next;
}static inline void list_del(struct list_head *entry)
{__list_del(entry-prev, entry-next);entry-next (void *) 0;entry-prev (void *) 0;
}
头文件xxx_list.h
构造大结构体的定义与具体的数据结构相关需要定义多份
#includestdio.h
#includestdlib.h
#includelist_common.h#define DATATYPE inttypedef struct node{int data;struct list_head list;
}node, *pnode;pnode init_list(void);
int push_front(pnode head, DATATYPE buf);
void list_front(pnode node);
int pop_front(pnode head, DATATYPE buf);
int show(pnode head);
接口文件xxx_list.c
构造大结构体的接口与具体的数据结构相关需要定义多份
//2024-04-02 实践记录
#includestdio.h
#includestdlib.h
#includelist_common.h//借助内核链表宏定义完成双向循环链表空表初始化
pnode init_list(void)
{pnode head (pnode)malloc(sizeof(node));if(NULL head){perror(malloc failed.\n);return NULL;}INIT_LIST_HEAD(head-list);return head;
}int push_front(pnode head, DATATYPE buf)
{pnode newnode (pnode)malloc(sizeof(node));if(NULL newnode){perror(malloc failed.\n);return -1;}newnode-data buf;//根据实际数据结构操作 list_add((newnode-list), (head-list));return 0;
}//删除结点
void list_front(pnode node)
{list_del((node-list));free(node);
}int pop_front(pnode head, DATATYPE buf)
{node p;struct list_head *pos ((head-list))-next;p list_entry(pos, node, list);buf p-data; //根据实际数据结构赋值list_front(p);
}//结点打印
int show(struct node *head)
{node *pos;list_for_each_entry(pos, (head-list), list){printf(data is:, pos-data);//与大结构的具体定义相关 }return 0;
}
测试代码
//2024-04-02 实践记录#includestdio.h
#includestdlib.h
#includenode_list.hint main()
{int i, n;int num;pnode head init_list();printf(please input num you want create node: \n);scanf(%d, n);for(i 1; i n; i ){push_front(head, i);}show(head);pop_front(p, num);printf(“get node.data: %d.\n”, num);show(head);return 0;
}
