注意：本文討論的是無頭單向非循環鏈表。

假設不采用Linux內核鏈表的思路，怎樣用C語言實現通用鏈表呢？

一種常用的做法是：

typedef int element_t;

struct node_info

{

element_t data;

struct node_info *next;

};

其實這樣的鏈表算不上通用，因為無法同時使用不同的數據類型。參考網友的思路，以上可以改為下面的定義：

//無頭非循環單向鏈表 struct node_info {void *data;struct node_info *next; };

先看看頭文件：

#pragma once//無頭非循環單向鏈表 struct node_info {void *data;struct node_info *next; };struct student {char name[20];unsigned char age;};//for teststruct slist_info {struct node_info *first; //指向第一個節點void (*insert_head)(void *one_data, struct slist_info *info);//頭插int (*del)(struct node_info *node, struct slist_info *info);//刪除節點struct node_info* (*find)(struct slist_info *info,int(*compare)(void *dest,void *key),void *key);//這里的compare是回調函數，由用戶提供void (*for_each)(const struct slist_info *info,void (*todo)(void *one_data));//遍歷，todo是回調函數void (*for_each_safe)(const struct slist_info *info,void (*todo)(void *one_data));//安全遍歷（覺得在這里這個方法意義不大）void (*invert)(struct slist_info *info);//反轉鏈表int (*is_dead_loop)(struct slist_info *info);//判斷是否有死環，是返回1，不是返回0 };#define slist_is_empty(info) ((info)->first == NULL) //鏈表是否為空//構造和析構 void slist_init(struct slist_info *info); void slist_destroy(struct slist_info *info);

與這個鏈表相關的操作如下。

1.插入元素（頭插法）

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include "slist.h"/*無頭非循環單鏈表*/ static void slist_insert_head(void *one_data, struct slist_info *info) {//頭插法assert(one_data != NULL && info != NULL);struct node_info *node = (struct node_info *)malloc(sizeof(struct node_info));//分配內存assert(node!=NULL);node->data = one_data;//注意，這里只是簡單地把指針指向用戶的數據，并沒有把用戶數據復制過來if (slist_is_empty(info)) {//1.空鏈表info->first = node;node->next = NULL;}else { //2. 非空node->next = info->first;info->first = node;} }
2.遍歷

static void slist_for_each(const struct slist_info *info,void (*todo)(void *one_data)) {assert(info != NULL && todo != NULL);struct node_info *cur = NULL;for (cur = info->first; cur != NULL; cur = cur->next) {todo(cur->data);} }static void slist_for_each_safe(const struct slist_info *info,void (*todo)(void *one_data)) {assert(info != NULL && todo != NULL);struct node_info *cur = NULL;struct node_info *Next = NULL;for (cur = info->first; cur != NULL; cur = Next) {Next = cur->next;//Next保存了下一個節點，如果這個節點被刪除了，那么下一個節點還可以找到todo(cur->data);} }
3.反轉（面試的時候，有可能會問到，直接背過好了！）

static void slist_invert(struct slist_info *info) {assert(info != NULL);struct node_info *Cur = NULL;struct node_info *Prev = NULL;struct node_info *Next = NULL;//1.移動Next 2.反向 3.移動Prev 4.移動Curfor (Cur = info->first; Cur != NULL; Cur = Next) {Next = Cur->next;Cur->next = Prev;Prev = Cur;}//修改頭指針，指向首節點info->first = Prev; }
4.查找

struct node_info *slist_find(struct slist_info *info,int(*compare)(void *dest,void *key),void *key) {assert(info != NULL && compare != NULL);struct node_info *cur = NULL;for (cur = info->first; cur != NULL; cur = cur->next) {if(compare(cur->data,key)==1)//回調函數，把鏈表中的每一個數據和用戶傳入的關鍵字做比較，符合條件返回1return cur;//返回節點的地址給用戶}return NULL;//沒有找到返回空指針 }
注意，這里的第三個參數（關鍵字）也是用戶傳進來的。

5.構造和析構

void slist_init(struct slist_info *info) {//空鏈表， 第一個節點為NULLinfo->first = NULL;info->insert_head = slist_insert_head;info->del = slist_del;info->find = slist_find;info->invert = slist_invert;info->is_dead_loop = slist_is_dead_loop;info->for_each = slist_for_each;info->for_each_safe = slist_for_each_safe; }void slist_destroy(struct slist_info *info) {if(!slist_is_empty(info)){struct node_info *cur = NULL;struct node_info *Next = NULL;for (cur = info->first; cur != NULL; cur = Next) {Next = cur->next;//Next保存了下一個節點，如果這個節點被刪除了，那么下一個節點還可以找到free(cur);//釋放每個節點占用的內存}}}
細心的讀者會發現，好像有的函數沒有實現啊。下一篇博文我們再討論！

總結

以上是生活随笔為你收集整理的C语言实现通用链表初步(一)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。