即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

欢迎运用CSDN-markdown编辑器

编程语言 thief761 14℃ 0评论
本文目录
[隐藏]

单链表结构

每个节点依靠储存的下一个节点的内存地址,从而使得一个一个相连接在一起,而不需要考虑位置在哪

  • 插入删除操作空间复杂度为O(1)
  • 读取某位置节点的空间复杂度O(n)
  • 不需要提前分配空间
  • 若线性表需要频繁的插入删除操作则应该选择链式
  • 结点个数未知的时候采用链式更好
  • 指针的应用

1.链表创建

  • 创建带头结点的指针`
  • 按照结构体开辟一块内存`
  • 头结点指向NULL`
  • 其他的初始化置0`

ps:代码来自网络但没毛病,实现方法很多不是唯一·····

typedef struct _tag_LinkList
{
    LinkListNode header;
    int Length;
}TLinkList;
LinkList *LinkList_Create()
{
    TLinkList *tmp = NULL;

    tmp = (TLinkList *)malloc(sizeof(TLinkList));

    if (tmp == NULL)
    {
        printf("func LinkList_Create()err \n");
        return NULL;
    }

    memset(tmp, 0, sizeof(TLinkList));
    tmp->Length = 0;
    tmp->header.next = NULL;

    return tmp;
}

2.销毁

当链表执行完毕后要进行销毁····

  • 直接free掉链表,不要忘记判断是否为空····

    void LinkList_Destroy(LinkList *list)


    {


    if (list == NULL)


    {


    return;


    }


    free(list);


    return ;


    }

3.清空链表

链表的清空和销毁是不一样的,销毁的话释放了整个内存空间,狗带了就


然而清空的话,保留了内存空间,只是把里面东西弄没了,回到刚刚创建好头指针指向NULL的一个状态

就是相当于,俩人分手了销毁的是自杀,清空是回到单身狗状态

  • 判断链表是否已经空了
  • 链表长度置为零
  • 清空头结点
void LinkList_Clear(LinkList *list)
{
    TLinkList *tList = NULL;
    tList = (TLinkList *)list;

    if (tList == NULL)
    {
        return;
    }

    tList->Length = 0;
    tList->header.next = NULL;

    return ;
}

4.获取链表长度

  • 判断链表是否为空
  • 直接返回长度即可
int LinkList_Length(LinkList *list)
{
    TLinkList *tList = NULL;
    tList = (TLinkList *)list;

    if (tList == NULL)
    {
        return -1;
    }

    return tList->Length;
}

5.链表的插入

就 相当于一堆人手拉手好好的走,突然隔壁老王来了要站在张翠花和赵桂花中间,张翠花和赵桂花拉着的手就得松开,俩人都拉着老王

  • 需要辅助指针用来从头部开始蹦跶走走走走到指向要插入的地方
  • 需要辅助指针变量接过来之前搞好的list
  • 需要知道插入位置
  • 错误判断:list为空,插入位置<0,要来插队的结点为空,三选一就没法玩儿了
  • 这里写图片描述

  • 链表长度再+1!!!

int LinkList_Insert(LinkList *list, LinkListNode *node, int pos)
{
    int                       i = 0;
    LinkListNode             *current = NULL;
    TLinkList                *tList = NULL;

    tList = (TLinkList *)list;

    if (list == NULL || node == NULL || pos < 0)
    {
        return -1;
    }

    current = &(tList->header);

    for (i = 0; i < pos; i++)
    {
        current = current->next;
    }

    node->next = current->next;
    current->next = node;

    tList->Length++;
    return 0;
}

6.获取某个位置上的结点

  • 链表不为空
  • 位置不小于0
  • 辅助指针变量从头节点处跳到位置处
  • 函数返回值为位置处的next中
LinkListNode *LinkList_Get(LinkList *list, int pos)
{
    int                   i = 0;
    LinkListNode          *current = NULL;
    TLinkList             *tList = NULL;

    tList = (TLinkList *)list;

    if (list == NULL || pos < 0)
    {
        return NULL;
    }

    current = &(tList->header);

    for (i = 0; i < pos; i++)
    {
        current = current->next;
    }
    return current->next;
}

7.删除某位置处的结点

  • 插入的反向操作····

    • 从头结点蹦到位置处的指针
  • 缓存要删除的结点的指针
  • 接传入list的指针

  • list不为空,删除位置>=0,函数操作的基本

  • 头指针蹦到删除位置处
  • 辅助缓存指针缓存下即将删除的结点
  • p->next=p->next->next 核心操作
  • 原来的链表长度要减少
LinkListNode *LinkList_Delete(LinkList *list, int pos)
{
    int               i = 0;
    LinkListNode      *current = NULL;
    LinkListNode      *ret = NULL;
    TLinkList         *tList = NULL;

    tList = (TLinkList *)list;

    if (list == NULL || pos < 0)
    {
        return;
    }

    current = &(tList->header);

    for (i = 0; i < pos; i++)
    {
        current = current->next;
    }

    ret = current->next;

    current->next = ret->next;

    tList->Length--;

    return ret;
}

转载请注明:CodingBlog » 欢迎运用CSDN-markdown编辑器

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情