首页 > 代码库 > c语言链表升级

c语言链表升级

2024-11-23 01:48:02   202人阅读

之前的链表就是一个普通的带头的单向链表，我们不自觉的会发现这样的链表有缺陷，有关链表的删除新增查找跟链表的结构体内容耦合性太强

什么意思呢？

比如我们之前的链表的结构体

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[50];
}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 = 0;
    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 = 0;
    tlinkList->header.next = NULL;

}

int LinkList_Length(LinkList* list)
{
    if (list == NULL)
    {
        return 0;
    }
    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 -1;
    }
    //校验下标
    if (pos<0)
    {
        return -2;
    }
    TLinkList *tlinkList = (TLinkList *)list;
    if (pos>tlinkList->length - 1)
    {
        pos = tlinkList->length;
    }
    pre = (LinkListNode *)list;//初始化指向头节点
    cur = tlinkList->header.next;//初始化指向第一个节点，如果空链表指向空
    for (i = 0; i < pos; i++)
    {
        pre = cur;
        cur = cur->next;//最终让当前指针指向要插入的位置
    }
    pre->next = node;
    node->next = cur;

    tlinkList->length++;
    return 0;
}

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 < 0)
    {
        return NULL;
    }
    cur = tlinkList->header.next;//初始化指向第一个节点，如果空链表指向空
    for (i = 0; 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 < 0)
    {
        return NULL;
    }
    pre = (LinkListNode *)list;//初始化指向头节点
    cur = tlinkList->header.next;//初始化指向第一个节点，如果空链表指向空
    for (i = 0; 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[50];
}Teacher;
void main()
{
    LinkList* linkList;
    Teacher t1, t2, t3;
    int len;
    int i;
    linkList = LinkList_Create();
    t1.age = 11;
    t2.age = 22;
    t3.age = 33;
    LinkList_Insert(linkList, (LinkListNode*)&t1, 0);
    LinkList_Insert(linkList, (LinkListNode*)&t2, 0);
    LinkList_Insert(linkList, (LinkListNode*)&t3, 0);

    len = LinkList_Length(linkList);

    for (i = 0; i < len; i++)
    {
        Teacher * t = (Teacher *)LinkList_Get(linkList, i);
        printf("cur teacher age=%d\n", t->age);
    }

    LinkList_Delete(linkList, 0);
    LinkList_Delete(linkList, 1);
    len = LinkList_Length(linkList);
    for (i = 0; i < len; i++)
    {
        Teacher * t = (Teacher *)LinkList_Get(linkList, i);
        printf("cur teacher age=%d\n", t->age);
    }
    system("pause");


}

接下来，如果我们有新的结构体，只要在测试代码那边做修改，而不需要动我们的核心代码了。

 

c语言链表升级


联系
我们