“兔子dimoo”通过精心收集，向本站投稿了5篇教您在C/C++中如何构造通用的对象链表.net，下面是小编整理后的教您在C/C++中如何构造通用的对象链表.net，欢迎您能喜欢，也请多多分享。
篇1：教您在C/C++中如何构造通用的对象链表.net
一个简化的问题示例 链表的难点在于必须复制链表处理函数来处理不同的对象，即便逻辑是完全相同的，例如两个结构类似的链表: struct Struct_Object_A{int a;int b;Struct_Object_A *next;} OBJECT_A;typedef struct Struct_Object_B{int a;int b;int c;Struct
一个简化的问题示例链表的难点在于必须复制链表处理函数来处理不同的对象，即便逻辑是完全相同的。例如两个结构类似的链表:
struct Struct_Object_A{int a;int b;Struct_Object_A *next;} OBJECT_A;typedef struct Struct_Object_B{int a;int b;int c;Struct_Object_B *next;} OBJECT_B;
上面定义的两个结构只有很小的一点差别。OBJECT_B 和 OBJECT_A 之间只差一个整型变量。但是，在编译器看来，它们仍然是非常不同的。必须为存储在链表中的每个对象复制用来添加、删除和搜索链表的函数。为了解决这个问题，可以使用具有全部三个变量的一个联合或结构，其中整数 c 并不是在所有的情况下都要使用。这可能变得非常复杂，并会形成不良的编程风格。
C 代码解决方案：虚拟链表
此问题更好的解决方案之一是虚拟链表。虚拟链表是只包含链表指针的链表。对象存储在链表结构背后。这一点是这样实现的，首先为链表节点分配内存，接着为对象分配内存，然后将这块内存分配给链表节点指针，如下所示：
虚拟链表结构的一种实现
typedef struct liststruct{liststruct *next;} LIST, *pLIST;pLIST Head = NULL;pLIST AddToList( pLIST Head,void * data, size_t datasize ){pLIST newlist=NULL;void *p;// 分配节点内存和数据内存newlist = (pLIST) malloc( datasize + sizeof( LIST ) );// 为这块数据缓冲区指定一个指针p = (void *)( newlist + 1 );// 复制数据memcpy( p, data, datasize );// 将这个节点指定给链表的表头if( Head ){newlist->next = Head;}elsenewlist->next = NULL;Head = newlist;return Head;}
链表节点现在建立在数据值副本的基本之上。这个版本能很好地处理标量值，但不能处理带有用 malloc 或 new 分配的元素的对象。要处理这些对象，LIST 结构需要包含一个一般的解除函数指针，这个指针可用来在将节点从链表中删除并解除它之前释放内存（或者关闭文件，或者调用关闭方法）。
一个带有解除函数的链表
typedef void (*ListNodeDestructor)( void * );typedef struct liststruct{ListNodeDestructor DestructFunc;liststruct *next;} LIST, *pLIST;pLIST AddToList( pLIST Head, void * data, size_t datasize,ListNodeDestructor Destructor ){pLIST newlist=NULL;void *p;// 分配节点内存和数据内存newlist = (pLIST) malloc( datasize + sizeof( LIST ) );// 为这块数据缓冲区指定一个指针p = (void *)( newlist + 1 );// 复制数据memcpy( p, data, datasize );newlist->DestructFunc = Destructor;// 将这个节点指定给链表的表头if( Head ){newlist->next = Head;}elsenewlist->next = NULL;Head = newlist;return Head;}void DeleteList( pLIST Head ){pLIST Next;while( Head ){Next = Head->next;Head->DestructFunc( (void *) Head );free( Head );Head = Next;}}typedef struct ListDataStruct{LPSTR p;} LIST_DATA, *pLIST_DATA;void ListDataDestructor( void *p ){// 对节点指针进行类型转换pLIST pl = (pLIST)p;// 对数据指针进行类型转换pLIST_DATA pLD = (pLIST_DATA)( pl + 1 );delete pLD->p;}pLIST Head = NULL;void TestList{pLIST_DATA d = new LIST_DATA;d->p = new char[24];strcpy( d->p, “Hello” ); Head = AddToList( Head, (void *) d,sizeof( pLIST_DATA ),ListDataDestructor );// 该对象已被复制，现在删除原来的对象delete d;d = new LIST_DATA;d->p = new char[24];strcpy( d->p, “World” ); Head = AddToList( Head, (void *) d,sizeof( pLIST_DATA ),ListDataDestructor );delete d;// 释放链表DeleteList( Head );}
在每个链表节点中包含同一个解除函数的同一个指针似乎是浪费内存空间，
确实如此，但只有链表始终包含相同的对象才属于这种情况。按这种方式编写链表允许您将任何对象放在链表中的任何位置。大多数链表函数要求对象总是相同的类型或类。
虚拟链表则无此要求。它所需要的只是将对象彼此区分开的一种方法。要实现这一点，您既可以检测解除函数指针的值，也可以在链表中所用的全部结构前添加一个类型值并对它进行检测。
当然，如果要将链表编写为一个 C++ 类，则对指向解除函数的指针的设置和存储只能进行一次。
C++ 解决方案：类链表
本解决方案将 CList 类定义为从 LIST 结构导出的一个类，它通过存储解除函数的单个值来处理单个存储类型。请注意添加的 GetCurrentData() 函数，该函数完成从链表节点指针到数据偏移指针的数学转换。一个虚拟链表对象
// 定义解除函数指针typedef void (*ListNodeDestructor)( void * );// 未添加解除函数指针的链表typedef struct ndliststruct{ndliststruct *next;} ND_LIST, *pND_LIST;// 定义处理一种数据类型的链表类class CList : public ND_LIST{public:CList(ListNodeDestructor);~CList();pND_LIST AddToList( void * data, size_t datasize );void *GetCurrentData();void DeleteList( pND_LIST Head );private:pND_LIST m_HeadOfList;pND_LIST m_CurrentNode;ListNodeDestructorm_DestructFunc;};// 用正确的起始值构造这个链表对象CList::CList(ListNodeDestructor Destructor): m_HeadOfList(NULL), m_CurrentNode(NULL){m_DestructFunc = Destructor;}// 在解除对象以后删除链表CList::~CList(){DeleteList(m_HeadOfList);}// 向链表中添加一个新节点pND_LIST CList::AddToList( void * data, size_t datasize ){pND_LIST newlist=NULL;void *p;// 分配节点内存和数据内存newlist = (pND_LIST) malloc( datasize + sizeof( ND_LIST ) );// 为这块数据缓冲区指定一个指针p = (void *)( newlist + 1 );// 复制数据memcpy( p, data, datasize );// 将这个节点指定给链表的表头if( m_HeadOfList ){newlist->next = m_HeadOfList;}elsenewlist->next = NULL;m_HeadOfList = newlist;return m_HeadOfList;}// 将当前的节点数据作为 void 类型返回，以便调用函数能够将它转换为任何类型void * CList::GetCurrentData(){return (void *)(m_CurrentNode+1);}// 删除已分配的链表void CList::DeleteList( pND_LIST Head ){pND_LIST Next;while( Head ){Next = Head->next;m_DestructFunc( (void *) Head );free( Head );Head = Next;}}// 创建一个要在链表中创建和存储的结构typedef struct ListDataStruct{LPSTR p;} LIST_DATA, *pND_LIST_DATA;// 定义标准解除函数void ClassListDataDestructor( void *p ){// 对节点指针进行类型转换pND_LIST pl = (pND_LIST)p;// 对数据指针进行类型转换pND_LIST_DATA pLD = (pND_LIST_DATA)( pl + 1 );delete pLD->p;}//测试上面的代码void MyCListClassTest(){// 创建链表类CList* pA_List_of_Data =new CList(ClassListDataDestructor);// 创建数据对象pND_LIST_DATA d = new LIST_DATA;d->p = new char[24];strcpy( d->p, “Hello” ); // 创建指向链表顶部的局部指针pND_LIST Head = NULL;//向链表中添加一些数据Head = pA_List_of_Data->AddToList( (void *) d, sizeof( pND_LIST_DATA ) );// 该对象已被复制，现在删除原来的对象delete d;// 确认它已被存储char * p = ((pND_LIST_DATA) pA_List_of_Data->GetCurrentData())->p;d = new LIST_DATA;d->p = new char[24];strcpy( d->p, “World” ); Head = pA_List_of_Data->AddToList( (void *) d, sizeof( pND_LIST_DATA ) );// 该对象已被复制，现在删除原来的对象delete d;// 确认它已被存储p = ((pND_LIST_DATA) pA_List_of_Data->GetCurrentData())->p;// 删除链表类，析构函数将删除链表delete pA_List_of_Data;}
小结
从前面的讨论来看，似乎仅编写一个简单的链表就要做大量的工作，但这只须进行一次。很容易将这段代码扩充为一个处理排序、搜索以及各种其他任务的 C++ 类，并且这个类可以处理任何数据对象或类（在一个项目中，它处理大约二十个不同的对象）。您永远不必重新编写这段代码。
原文转自：www.ltesting.net
篇2：链表的c语言实现③
3、删除
假如我们已经知道了要删除的结点p的位置，那么要删除p结点时只要令p结点的前驱结点的链域由存储p结点的地址该为存储p的后继结点的地址，并回收p结点即可，
以下便是应用删除算法的实例：
#include
#include
#include
#define N 10
typedef struct node
{
char name[20];
struct node *link;
}stud;
stud * creat(int n) /*建立新的链表的函数*/
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
h->name[0]='';
h->link=NULL;
p=h;
for(i=0;i
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
p->link=s;
printf(“请输入第%d个人的姓名”,i+1);
scanf(“%s”,s->name);
s->link=NULL;
p=s;
}
return(h);
}
stud * search(stud *h,char *x) /*查找函数*/
{
stud *p;
char *y;
p=h->link;
while(p!=NULL)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->link;
}
if(p==NULL)
printf(“没有查找到该数据!”);
}
stud * search2(stud *h,char *x) /*另一个查找函数，返回的是上一个查找函数的直接前驱结点的指针，*/
/*h为表头指针，x为指向要查找的姓名的指针*/
/*其实此函数的算法与上面的查找算法是一样的，只是多了一个指针s，并且s总是指向指针p所指向的结点的直接前驱，*/
/*结果返回s即是要查找的结点的前一个结点*/
{
stud *p,*s;
char *y;
p=h->link;
s=h;
while(p!=NULL)
{
y=p->name;
if(strcmp(y,x)==0)
return(s);
else
{
p=p->link;
s=s->link;
}
}
if(p==NULL)
printf(“没有查找到该数据!”);
}
void del(stud *x,stud *y) /*删除函数，其中y为要删除的结点的指针，x为要删除的结点的前一个结点的指针*/
{
stud *s;
s=y;
x->link=y->link;
free(s);
}
main()
{
int number;
char fullname[20];
stud *head,*searchpoint,*forepoint;
number=N;
head=creat(number);
printf(“请输入你要删除的人的姓名:”);
scanf(“%s”,fullname);
searchpoint=search(head,fullname);
forepoint=search2(head,fullname);
del(forepoint,searchpoint);
一、循环链表
循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链，
循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。
二、双向链表
双向链表其实是单链表的改进。
当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。
在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。在c语言中双向链表结点类型可以定义为：
typedef struct node
{
int data; /*数据域*/
struct node *llink,*rlink; /*链域，*llink是左链域指针，*rlink是右链域指针*/
}JD;
当然，也可以把一个双向链表构建成一个双向循环链表。
双向链表与单向链表一样，也有三种基本运算：查找、插入和删除。
篇3：链表的c语言实现⑤
3、删除
删除某个结点，其实就是插入某个结点的逆操作，还是对于双向循环链表，要在连续的三个结点s,p,q中删除p结点，只需把s的右链域指针指向q，q的左链域指针指向s，并收回p结点就完成了。
下面就是一个应用双向循环链表删除算法的例子：
#include
#include
#include
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
h->name[0]='';
h->llink=NULL;
h->rlink=NULL;
p=h;
for(i=0;i〈n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
p-〉rlink=s;
printf(“请输入第%d个人的姓名”,i+1);
scanf(“%s”,s->name);
s->llink=p;
s->rlink=NULL;
p=s;
}
h->llink=s;
p->rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h->rlink;
while(p!=h)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->rlink;
}
printf(“没有查找到该数据!”);
}
void print(stud *h)
{
int n;
stud *p;
p=h->rlink;
printf(“数据信息为：n”);
while(p!=h)
{
printf(“%s ”,&*(p->name));
p=p->rlink;
}
printf(“n”);
}
void del(stud *p)
{
(p->rlink)->llink=p->llink;
(p->llink)->rlink=p->rlink;
free (p);
}
main
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf(“请输入你要查找的人的姓名:”);
scanf(“%s”,studname);
searchpoint=search(head,studname);
printf(“你所要查找的人的姓名是:%sn”,*&searchpoint->name);
del(searchpoint);
print(head);
}
在这里列举了一个应用单链表基本算法的综合程序，双向链表和循环链表的综合程序大家可以自己去试一试。
#include
#include
#include
#define N 10 typedef struct node
{
char name[20];
struct node *link;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
h->name[0]='';
h->link=NULL;
p=h;
for(i=0;i
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
p->link=s;
printf(“请输入第%d个人的姓名”,i+1);
scanf(“%s”,s->name);
s->link=NULL;
p=s;
}
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h->link;
while(p!=NULL)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->link;
}
if(p==NULL)
printf(“没有查找到该数据!”);
}
stud * search2(stud *h,char *x)
{
stud *p,*s;
char *y;
p=h->link;
s=h;
while(p!=NULL)
{
y=p->name;
if(strcmp(y,x)==0)
return(s);
else
{
p=p->link;
s=s->link;
}
}
if(p==NULL)
printf(“没有查找到该数据!”);
}
void insert(stud *p)
{
char stuname[20];
stud *s;
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
printf(“n请输入你要插入的人的姓名:”);
scanf(“%s”,stuname);
strcpy(s->name,stuname);
s->link=p->link;
p->link=s;
}
void del(stud *x,stud *y)
{
stud *s;
s=y;
x->link=y->link;
free(s);
}
void print(stud *h)
{
stud *p;
p=h->link;
printf(“数据信息为：n”);
while(p!=NULL)
{
printf(“%s ”,&*(p->name));
p=p->link;
}
}
void quit()
{
exit(0);
}
void menu(void)
{
clrscr();
printf(“ttt单链表C语言实现实例n”);
printf(“tt|————————————————|n”);
printf(“tt| |n”);
printf(“tt| [1] 建 立 新 表 |n”);
printf(“tt| [2] 查 找 数 据 |n”);
篇4：链表的c语言实现④
双向链表的基本运算：
1、查找
假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时，我们同样从表头结点往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，否则继续往后查，直到表尾，
下例就是应用双向循环链表查找算法的一个程序。
#include
#include
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
h->name[0]='';
h->llink=NULL;
h->rlink=NULL;
p=h;
for(i=0;i
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
p->rlink=s;
printf(“请输入第%d个人的姓名”,i+1);
scanf(“%s”,s->name);
s->llink=p;
s->rlink=NULL;
p=s;
}
h->llink=s;
p->rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h->rlink;
while(p!=h)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->rlink;
}
printf(“没有查找到该数据!”);
}
void print(stud *h)
{
int n;
stud *p;
p=h->rlink;
printf(“数据信息为：n”);
while(p!=h)
{
printf(“%s ”,&*(p->name));
p=p->rlink;
}
printf(“n”);
}
main()
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf(“请输入你要查找的人的姓名:”);
scanf(“%s”,studname);
searchpoint=search(head,studname);
printf(“你所要查找的人的姓名是:%s”,*&searchpoint->name);
}
2、插入
对于双向循环链表，我们现在可以随意地在某已知结点p前或者p后插入一个新的结点。
假若s,p,q是连续三个结点的指针，若我们要在p前插入一个新结点r，则只需把s的右链域指针指向r，r的左链域指针指向s，r的右链域指针指向p，p的左链域指针指向r即可。
在p,q之间插入原理也一样。
下面就是一个应用双向循环链表插入算法的例子：
#include
#include
#include
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
h->name[0]='';
h->llink=NULL;
h->rlink=NULL;
p=h;
for(i=0;i
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
p->rlink=s;
printf(“请输入第%d个人的姓名”,i+1);
scanf(“%s”,s->name);
s->llink=p;
s->rlink=NULL;
p=s;
}
h->llink=s;
p->rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h->rlink;
while(p!=h)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->rlink;
}
printf(“没有查找到该数据!”);
}
void print(stud *h)
{
int n;
stud *p;
p=h->rlink;
printf(“数据信息为：n”);
while(p!=h)
{
printf(“%s ”,&*(p->name));
p=p->rlink;
}
printf(“n”);
}
void insert(stud *p)
{
char stuname[20];
stud *s;
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf(“不能分配内存空间!”);
exit(0);
}
printf(“请输入你要插入的人的姓名:”);
scanf(“%s”,stuname);
strcpy(s->name,stuname);
s->rlink=p->rlink;
p->rlink=s;
s->llink=p;
(s->rlink)->llink=s;
}
main()
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf(“请输入你要查找的人的姓名:”);
scanf(“%s”,studname);
searchpoint=search(head,studname);
printf(“你所要查找的人的姓名是:%sn”,*&searchpoint->name);
insert(searchpoint);
print(head);
}
篇5：C实现通用数据结构单链表
单链表的接口定义：
1、list_init
void list_init(List *list, void (*destroy)(void *data));
返回值 void
描述 初始化由参数list指定的链表，该函数必须在链表做其他操作之前调用，当调用list_destroy时，destroy参数提供了一种释放动态分配数据的方法，如果链表采用malloc动态分配的数据，destroy应该设置为free来释放这些数据
复杂度 O(1)
2、list_destroy
void list_destroy(List *list);
返回值 void
描述 销毁由参数list指定的链表，调用该函数以后任何函数都不能再执行，除非重新执行list_init函数。list_destroy将list中的所有元素都移除，每移除一个元素都会调用此函数
复杂度 O(n) n为链表元素的个数
3、list_ins_next
int list_ins_next(List *list, ListElmt *element, const void *data);
返回值 如果插入元素成功返回0，否则返回-1
描述 在指定的list的element元素后面插入一个元素，如果element为NULL，则在链表的头部插入新的元素，该元素包含一个指向data的指针
复杂度 O(1)
4、list_rem_next
int list_rem_next(List *list, ListElmt *element, void **data);
返回值 如果移除元素成功返回0，否则返回-1
描述 移除在指定的list的element后面的那个元素，如果element为NULL，则移除链表的头元素，调用返回后，data指向已经移除元素的数据
复杂度 O(1)
5、list_size
int list_size(const List *list);
返回值 如果list中元素的个数
描述 这是一个宏，用来计算指定list中元素的个数
复杂度 O(1)
6、list_head
ListElmt *list_head(const List *list);
返回值 指向链表头元素的指针
描述 这是一个宏，返回由参数list指定的链表头元素的指针
复杂度 O(1)
7、list_tail
ListElmt *list_tail(const List *list) ((list)->tail);
返回值 指向链表尾元素的指针
描述 这是一个宏，返回由参数list指定的链表尾元素的指针
复杂度 O(1)
8、list_is_head
int list_is_head(const ListElmt *element);
返回值 如果element元素是链表头元素返回0，否则返回-1
描述 这是一个宏，用来判断element元素是否是list的头元素
复杂度 O(1)
9、list_is_tail
int list_is_tail(const ListElmt *element);
返回值 如果element元素是链表尾元素返回0，否则返回-1
描述 这是一个宏，用来判断element元素是否是list的尾元素
复杂度 O(1)
10、list_data
void *list_data(const ListElmt *element);
返回值 结点中保存的数据
描述 这是一个宏，返回由element元素中保存的数据
复杂度 O(1)
11、list_next
ListElmt *list_next(const ListElmt *element) ;
返回值 返回element所指定结点的下一个结点
描述 这是一个宏，返回链表中element所指定结点的下一个结点
复杂度 O(1)
单链表的实现和分析
抽象数据类型的头文件（list.h）：
#ifndef LIST_H
#define LIST_H
#include
//为单链表的结点定义一个结构体.
typedef struct ListElmt_ {
void *data; //数据域
struct ListElmt_ *next; //指针域
} ListElmt;
//为单链表定义一个结构体.
typedef struct List_ {
int size; //容量
int (*match)(const void *key1, const void *key2); //匹配函数
void (*destroy)(void *data); //撤销操作
ListElmt *head; //头指针
ListElmt *tail; //尾指针
} List;
//公共接口
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElmt *element, const void *data);
int list_rem_next(List *list, ListElmt *element, void **data);
#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)
#endif
初始化单链表：
void list_init(List *list, void (*destroy)(void *data)) { //初始化list
list->size = 0;
list->destroy = destroy; //设置为定义的析构函数
list->head = NULL;
list->tail = NULL;
return;
}
回收单链表：
void list_destroy(List *list) {
//移除每一个元素
while (list_size(list) > 0) {
if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) { //不断地移除链表的头结点
list->destroy(data); //调用一个用户定义的函数来释放动态分配的数据.
}
}
//现在没有操作了,释放结构体作为预防措施
memset(list, 0, sizeof(List));
return;
}
插入新节点作为指定结点的直接后继结点:
int list_ins_next(List *list, ListElmt *element, const void *data) {
ListElmt *new_element; //为结点动态分配存储空间
if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL) //假如分配失败
return -1;
// 将元素插入链表
new_element->data = (void *)data;
if (element == NULL) {
//插入到链表的头部
if (list_size(list) == 0)
list->tail = new_element;
new_element->next = list->head;
list->head = new_element;
} else {
//插入到除了链表头部以外指定的其他地方
if (element->next == NULL)
list->tail = new_element;
new_element->next = element->next;
element->next = new_element;
}
list->size++; //表长增加
return 0;
}
删除指定结点的直接后继结点:
int list_rem_next(List *list, ListElmt *element, void **data) {
ListElmt *old_element;
//不允许从一个空的list中移除元素.
if (list_size(list) == 0)
return -1;
// 从list中移除元素.
if (element == NULL) {
// 移除表头的结点.
*data = list->head->data;
old_element = list->head;
list->head = list->head->next;
if (list_size(list) == 1) //如果list只有一个元素，则直接删除尾结点
list->tail = NULL;
} else {
// 移除非头结点.
if (element->next == NULL)
return -1;
*data = element->next->data;
old_element = element->next;
element->next = element->next->next;
if (element->next == NULL) //移除指定结点后，后继为NULL，则用尾结点指向
list->tail = element;
}
//释放分配的抽象数据类型.
free(old_element);
//调整list的长度. *
list->size--;
return 0;
}
注意：list_size、list_head、list_tail、list_is_head、list_is_tail、list_data、list_next 这些宏实现了链表中的一些简单操作，它们提供了快速访问和检测结构体成员的能力，
这些操作的时间复杂度都是O(1)
完整的测试代码如下：
// Completed on 2014.10.22 21:00
// Language: C99
//
// 版权所有（C）codingwu (mail: oskernel@126.com)
// 博客地址：www.cnblogs.com/archimedes/
#include
#include
#include “list.h”
static void print_list(const List *list) {
ListElmt *element;
int *data, i;
fprintf(stdout, “List size is %dn”, list_size(list));
i = 0;
element = list_head(list);
while (1) {
data = list_data(element);
fprintf(stdout, “list[%03d]=%03dn”, i, *data);
i++;
if (list_is_tail(element))
break;
else
element = list_next(element);
}
return;
}
int main(int argc, char **argv) {
List list;
ListElmt *element;
int *data, i;
//初始化list
list_init(&list, free);
element = list_head(&list);
for (i = 10; i > 0; i--) {
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = i;
if (list_ins_next(&list, NULL, data) != 0) //逐个插入元素
return 1;
}
print_list(&list); //打印初始list
element = list_head(&list); //指向头结点
for (i = 0; i < 7; i++)
element = list_next(element);
data = list_data(element);
fprintf(stdout, “Removing an element after the one containing %03dn”, *data);
if (list_rem_next(&list, element, (void **)&data) != 0) //删除指定结点
return 1;
print_list(&list);
fprintf(stdout, “Inserting 011 at the tail of the listn”);
*data = 11;
if (list_ins_next(&list, list_tail(&list), data) != 0) //插入指定结点
return 1;
print_list(&list);
fprintf(stdout, “Removing an element after the first elementn”);
element = list_head(&list);
if (list_rem_next(&list, element, (void **)&data) != 0)
return 1;
print_list(&list);
fprintf(stdout, “Inserting 012 at the head of the listn”);
*data = 12;
if (list_ins_next(&list, NULL, data) != 0)
return 1;
print_list(&list);
fprintf(stdout, “Iterating and removing the fourth elementn”);
element = list_head(&list);
element = list_next(element);
element = list_next(element);
if (list_rem_next(&list, element, (void **)&data) != 0)
return 1;
print_list(&list);
fprintf(stdout, “Inserting 013 after the first elementn”);
*data = 13;
if (list_ins_next(&list, list_head(&list), data) != 0)
return 1;
print_list(&list);
i = list_is_head(&list, list_head(&list));
fprintf(stdout, “Testing list_is_head...Value=%d (1=OK)n”, i);
i = list_is_head(&list, list_tail(&list));
fprintf(stdout, “Testing list_is_head...Value=%d (0=OK)n”, i);
i = list_is_tail(list_tail(&list));
fprintf(stdout, “Testing list_is_tail...Value=%d (1=OK)n”, i);
i = list_is_tail(list_head(&list));
fprintf(stdout, “Testing list_is_tail...Value=%d (0=OK)n”, i);
fprintf(stdout, “Destroying the listn”);
list_destroy(&list);
return 0;
}
