阅读量:2
#ifndef LIST_H #define LIST_H #include <stdio.h> #include <stdbool.h> // 通用链表节点 typedef struct ListNode { void* ptr; struct ListNode* prev; struct ListNode* next; }ListNode; // 通用链表结构 typedef struct List { ListNode* head; size_t size; }List; // 创建链表 List* create_list(void); // 追加 void add_list(List* list,void* ptr); // 插入 bool insert_list(List* list,int index,void* ptr); // 按位置删除 bool delete_index_list(List* list,int index); typedef int (*fp)(const void*,const void*); // 按值删除 ? bool delete_value_list(List* list,void* ptr,fp cmp); // 查询 ? void* query_list(List* list,void* ptr,fp cmp); // 访问 void* access_list(List* list,int index); // 排序 ? void sort_list(List* list,fp cmp); // 清空 void clear_list(List* list); // 销毁 void destroy_list(List* list); // 遍历 void show_list(List* list,void (*show)(void*)); #endif//LIST_H #include <stdlib.h> #include "list.h" // 创建节点 static ListNode* create_node(void* ptr) { ListNode* node = malloc(sizeof(ListNode)); node->ptr = ptr; node->next = node; node->prev = node; return node; } // 在两个节点之间插入新节点 static void _add_list(ListNode* p,ListNode* n,void* ptr) { ListNode* node = create_node(ptr); p->next = node; n->prev = node; node->prev = p; node->next = n; } // 删除节点 static void _del_list(ListNode* node) { node->prev->next = node->next; node->next->prev = node->prev; free(node->ptr); //void* ptr = node->ptr; free(node); // return ptr; } // 根据位置访问节点 static ListNode* _index_list(List* list,int index) { if(0 > index || index >= list->size) return NULL; if(index < list->size/2) { ListNode* node = list->head->next; while(index--) node = node->next; return node; } else { ListNode* node = list->head->prev; while(++index < list->size) node = node->prev; return node; } } // 创建链表 List* create_list(void) { List* list = malloc(sizeof(List)); list->head = create_node(NULL); list->size = 0; return list; } // 在末尾追加 void add_list(List* list,void* ptr) { _add_list(list->head->prev,list->head,ptr); list->size++; } // 插入 bool insert_list(List* list,int index,void* ptr) { ListNode* node = _index_list(list,index); if(NULL == node) return false; _add_list(node->prev,node,ptr); list->size++; return true; } // 按位置删除 bool delete_index_list(List* list,int index) { ListNode* node = _index_list(list,index); if(NULL == node) return false; _del_list(node); list->size--; return true; } // 按值删除 ? bool delete_value_list(List* list,void* ptr,fp cmp) { for(ListNode* n=list->head->next; list->head!=n; n=n->next) { // if(n->ptr == ptr) 无法进行直接比较 // 需要通过回调函数让调用者提供值比较的方法 if(0 == cmp(n->ptr,ptr)) { _del_list(n); list->size--; return true; } } return false; } // 查询 void* query_list(List* list,void* ptr,fp cmp) { for(ListNode* n=list->head->next; list->head!=n; n=n->next) { if(0 == cmp(ptr,n->ptr)) { return n->ptr; } } return NULL; } // 访问 void* access_list(List* list,int index) { ListNode* node = _index_list(list,index); if(NULL == node) return NULL; return node->ptr; } // 排序 void sort_list(List* list,fp cmp) { for(ListNode* i=list->head->next; list->head->prev!=i; i=i->next) { ListNode* min = i; for(ListNode* j=i->next; list->head!=j; j=j->next) { if(0 > cmp(j->ptr,min->ptr)) min = j; } if(min != i) { // 不需要交换内存，只需交换指针指向即可 void* tmp = i->ptr; i->ptr = min->ptr; min->ptr = tmp; } } } // 清空 void clear_list(List* list) { while(list->size) delete_index_list(list,0); } // 销毁 void destroy_list(List* list) { clear_list(list); free(list->head); free(list); } // 遍历 void show_list(List* list,void (*show)(void*)) { for(ListNode* n=list->head->next; list->head!=n; n=n->next) { show(n->ptr); } } #include <stdio.h> #include <stdlib.h> #include <string.h> #include "list.h" // 以下都是用户写的代码 typedef struct Student { char name[20]; char sex; int id; }Student; void show_stu(void* ptr) { Student* stu = ptr; printf("%s %c %d\n",stu->name,stu->sex,stu->id); } // 比较的回调函数 int cmp_name(const void* p1,const void* p2) { const Student *s1 = p1,*s2 = p2; return strcmp(s1->name,s2->name); } int cmp_id(const void* p1,const void* p2) { const Student *s1 = p1,*s2 = p2; return s1->id - s2->id; } int main(int argc,const char* argv[]) { // 创建链表 List* list = create_list(); Student* stu = NULL; for(int i=0; i<10; i++) { stu = malloc(sizeof(Student)); sprintf(stu->name,"hehe%d",i); stu->sex = i%2 ? 'w':'m'; stu->id = rand()%1000; add_list(list,stu); } stu = malloc(sizeof(Student)); sprintf(stu->name,"xixi"); stu->sex ='w'; stu->id = 2001; insert_list(list,2,stu); delete_index_list(list,7); Student stu1 = {"hehe4",'w',1010}; delete_value_list(list,&stu1,cmp_name); delete_value_list(list,&stu1,cmp_id); sort_list(list,cmp_id); show_list(list,show_stu); destroy_list(list); } Linux内核链表虽然设计很巧妙，但是不利于初学者使用，另一种通用的设计思路是借助void*的兼容性，来设计一种链表，称为通用链表，这种链表还需要借助回调函数。
// 定义了一个函数指针变量 返回值 (*函数指针变量名)(参数列表); void (*funcp)(int num1,int num2); // 该函数指针的类型是 返回值 (*)(参数列表); void (*)(int,int); // 函数指针类型重定义 typedef 返回值 (*重定义后的类型名)(参数列表); typedef void (*fp)(int,int); fp 就是 void (*)(int,int)这个函数指针类型 可以用来定义该类型的函数指针变量 fp p; // p就是函数指针变量
