之前的链表就是一个普通的带头的单向链表,我们不自觉的会发现这样的链表有缺陷,有关链表的删除新增查找跟链表的结构体内容耦合性太强
什么意思呢?
比如我们之前的链表的结构体
typedef struct _Teacher
{
int age;
struct _Teacher *next;
}Teacher;
我们有关链表所有的操作都跟这个结构体紧密的相连,如果此刻我们有另一个结构体,里面的字段都跟这个不一样,那么,我们可能还需要对这个新的结构体写一套链表操作?
相当于下面的图,呵呵,有点丑
那么我们的解决方案是什么呢?,我们能不能关于不同结构体的所有操作都有一套公共方法呢?
当然是可以的!
在这之前我们必须有一个概念,结构体中的第一个元素的地址就是代表结构体的地址。
我们设计一个单纯代表数据结构的结构体,这个结构体只有下个对象的地址的指针成员
typedef struct _tag_LinkListNode
{
void * next;
}LinkListNode;
比如此刻我们有一个教师结构体,那么我们只需要在结构体的第一个成员是上面的LinkListNode对象。
形成下面的数据结构:
typedef struct _Teacher
{
LinkListNode listNode;
int age;
char name[];
}Teacher;
那么,此刻我们只要在我们的对链表的操作将传过来的Teacher * 指针强转为LinkListNode *类型,查询出来的LinkListNode * 指针变量再强转为Teacher * 对象,从而对LinkListNode形成一套插入删除查询的api就可以了
以下是实现的代码:
接口:
#ifndef _MYLINKLIST_H_
#define _MYLINKLIST_H_typedef void LinkList;typedef struct _tag_LinkListNode
{
struct _tag_LinkListNode* next;
}LinkListNode;LinkList* LinkList_Create();void LinkList_Destroy(LinkList* list);void LinkList_Clear(LinkList* list);int LinkList_Length(LinkList* list);int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);LinkListNode* LinkList_Get(LinkList* list, int pos);LinkListNode* LinkList_Delete(LinkList* list, int pos);#endif
实现:
#include "stdio.h"
#include "stdlib.h"
#include "linklist.h"typedef struct _tag_LinkList
{
//头节点
LinkListNode header;
int length;
}TLinkList;/************************************************************************/
/* 创建list并初始化一个头节点 */
/************************************************************************/
LinkList* LinkList_Create()
{
TLinkList *tlist = (TLinkList *)malloc(sizeof(TLinkList));
if (tlist == NULL)
{
return NULL;
}
tlist->length = ;
tlist->header.next = NULL;
return tlist;
}void LinkList_Destroy(LinkList* list)
{
if (list == NULL)
{
return;
}
free(list);
}
/************************************************************************/
/* 清空list链表 */
/************************************************************************/
void LinkList_Clear(LinkList* list)
{
if (list == NULL)
{
return;
}
TLinkList *tlinkList = (TLinkList *)list;
tlinkList->length = ;
tlinkList->header.next = NULL;}int LinkList_Length(LinkList* list)
{
if (list == NULL)
{
return ;
}
TLinkList *tlinkList = (TLinkList *)list; return tlinkList->length;
}int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
LinkListNode *pre, *cur;
int i;
if (list == NULL || node == NULL)
{
return -;
}
//校验下标
if (pos<)
{
return -;
}
TLinkList *tlinkList = (TLinkList *)list;
if (pos>tlinkList->length - )
{
pos = tlinkList->length;
}
pre = (LinkListNode *)list;//初始化指向头节点
cur = tlinkList->header.next;//初始化指向第一个节点,如果空链表指向空
for (i = ; i < pos; i++)
{
pre = cur;
cur = cur->next;//最终让当前指针指向要插入的位置
}
pre->next = node;
node->next = cur; tlinkList->length++;
return ;
}LinkListNode* LinkList_Get(LinkList* list, int pos)
{
LinkListNode *pre, *cur;
int i;
if (list == NULL)
{
return NULL;
}
TLinkList *tlinkList = (TLinkList *)list;
//校验下标
if (pos >= tlinkList->length || pos < )
{
return NULL;
}
cur = tlinkList->header.next;//初始化指向第一个节点,如果空链表指向空
for (i = ; i < pos; i++)
{
cur = cur->next;
} return cur;
}LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
LinkListNode *pre, *cur;
int i;
if (list == NULL)
{
return NULL;
}
TLinkList *tlinkList = (TLinkList *)list;
//校验下标
if (pos >= tlinkList->length || pos < )
{
return NULL;
}
pre = (LinkListNode *)list;//初始化指向头节点
cur = tlinkList->header.next;//初始化指向第一个节点,如果空链表指向空
for (i = ; i < pos; i++)
{
pre = cur;
cur = cur->next;
}
pre->next = cur->next;
LinkListNode* curnode = cur;
tlinkList->length--;
return curnode;
}
测试代码
#include "stdio.h"
#include "stdlib.h"
#include "linklist.h"typedef struct _Teacher
{
LinkListNode listNode;
int age;
char name[];
}Teacher;
void main()
{
LinkList* linkList;
Teacher t1, t2, t3;
int len;
int i;
linkList = LinkList_Create();
t1.age = ;
t2.age = ;
t3.age = ;
LinkList_Insert(linkList, (LinkListNode*)&t1, );
LinkList_Insert(linkList, (LinkListNode*)&t2, );
LinkList_Insert(linkList, (LinkListNode*)&t3, ); len = LinkList_Length(linkList); for (i = ; i < len; i++)
{
Teacher * t = (Teacher *)LinkList_Get(linkList, i);
printf("cur teacher age=%d\n", t->age);
} LinkList_Delete(linkList, );
LinkList_Delete(linkList, );
len = LinkList_Length(linkList);
for (i = ; i < len; i++)
{
Teacher * t = (Teacher *)LinkList_Get(linkList, i);
printf("cur teacher age=%d\n", t->age);
}
system("pause");}
接下来,如果我们有新的结构体,只要在测试代码那边做修改,而不需要动我们的核心代码了。