<数据结构> 链表 - 单链表(c语言实现)(二)

简介: <数据结构> 链表 - 单链表(c语言实现)(二)

五、功能的实现


1)打印单链表

//打印 单链表
void SLTPrint(SLTNode* phead);
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;//①
  while (cur != NULL)//②
  {
  printf("%d -> ",cur->data);
  cur = cur->next;//③
  }
  printf("NULL\n");
}


① 这里也可以直接用phead进行循环,但是像这样创建一个 “当前节点” (cur源自单词current)会比较“美观”。(But 如果这个函数内部后面还需要用头节点的话就不能直接用phead,否则会找不到头)

② 控制结束的条件

③ 遍历


2)创建新节点

链表的结点:按需分配,随用随创

链表的头插、尾插(只要是插入)都需要创建一个新节点,然后插到对应位置。所以我们可以直接把“创建新节点”封装成一个函数,以便后面直接调用:👇

SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//①
  if(newnode == NULL)//②
  {
  perror("malloc newnode fail: ");
  return;
  }
  //③给新节点赋值
  newnode->x;
  newnode->next = NULL;
  return newnode;//别忘了返回newnode
}


①动态开辟一个新节点,.h头文件里要包含 <stdlib.h>

②判断开辟是否成功,如果不成功则输出错误并返回

③给新节点的数据域赋值,指针域赋为空:NULL,这样做的好处是: 不需要最后对链表尾结点的指针域置空。


3)尾插

在链表尾部插入一个节点

先看这段代码:

void SLTPushBack(SLTNode** pphead, SLTDataType x);
{
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    tail->next = newnode;
}


上面这段代码的前提是,我们已经假定这个链表有>=1个节点,但是如果*pphead为空呢?

如果为空,则只执行:

SLTNode* newnode = BuySLTNode(x);
SLTNode*tail = *pphead;


初始化:SLTNode* phead = NULL;

传参: SLTPushBack(&phead, x);)

当phead为NULL时,也就不存在tail->next了


所以切记要先判断*pphead是否为空:

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
  *pphead = newnode;
  }
  else
  {
  SLTNode* tail = *pphead;
  //找原链表的尾结点
  while (tail->next != NULL)
  {
    tail = tail->next;
  }
  tail->next = newnode;
  }
}


4)尾删

尾删比较麻烦,因为要判断链表是否为空以及分情况讨论结点个数。


先看这段代码:

void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead);//①
    SLTNode* tail, * tailpre;//②
    tail = *pphead->next;
    tailpre = *pphead;
    while (tail->next)
    {
        tail = tail->next;
        tailpre = tailpre->next;
    }
    free(tail);//③
    tailpre->next = NULL;//④
}


①pphead(二级指针)和*pphead绝对不可以为空,最好断言一下

②定义tail和tail前一个结点tailpre,目的是释放tail后,直接得到新的尾结点,方便置空

③没必要再把tail置空:tail = NULL;因为tail是局部变量,函数结束就自动销毁了

④释放后,新的尾结点的next置空

看似没什么毛病·······


但是,上面没有考虑只有一个结点的情况!!

⚡如果只有一个结点, tail = *pphead->next;后,tail为NULL,下面的执行就出大问题了


解决办法是判断一下:

void SLTPopBack(SLTNode** pphead)
{
    assert(pphead && *pphead);
    if ((*pphead)->next == NULL)//只有一个结点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else//    >=2个结点
    {
        SLTNode* tail, * tailpre;
        tail = *pphead->next;
        tailpre = *pphead;
        while (tail->next)
        {
            tail = tail->next;
            tailpre = tailpre->next;
        }
        free(tail);
        tailpre->next = NULL;
    }
}


5)头插

按照尾插的路子,可能会这样写:

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuySLTNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
}


当然没有错,但是仔细想一想,其实没有必要判断*pphead是否为空,因为即使*pphead为空,执行else部分依然没毛病!


化简为:

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}


6)头删

头删相比较尾删很简单,因为不需要像尾删一样找tail前一个结点。


头删可以直接删:

void SLPopFront(SLTNode** pphead)
{
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;//临时存一下第二个元素的结点
    free(*pphead);
    *pphead = next;
}


7)查找

查找链表中的某个元素,只需遍历一遍链表。返回data == 要查找的元素第一次出现的节点的地址;如果链表中没有要查找的元素,返回NULL。


<注意,空链表也可以查找,返回NULL即可>↓

SLTNode* SLFind(SLTNode* phead, SLDataType x)
{
    SLTNode* cur = phead;
    while (cur)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}


8)删除

分两种情况:链表只有一个节点、链表有多个节点。

1、只有一个节点:如果*pphead == pos,相当于头删,直接调用前面的函数即可。

2、有多个节点:遍历链表,直到找到地址为pos的结点,按照尾删的思路,删除即可。

void SLErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead && pos);//都不能为空
    if (*pphead == pos)
    {
        SLPopFront(pphead);
    }
    else
    {
        SLTNode* cur = *pphead;
        while (cur->next != pos)
        {
            cur = cur->next;
        }
        SLTNode* next = cur->next->next;
        cur->next = next;
        free(pos);//一定要free
    }
}


9)插入结点

在pos前插入:

void SLInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
    assert(pphead && pos);
    if (pos == *pphead)
    {
        SLPushFront(pphead, x);
    }
    else
    {
        SLTNode* cur = *pphead;
        while (cur->next != pos)
        {
            cur = cur->next;
        }
        SLTNode* insnode = BuyNode(x);
        cur->next = insnode;
        insnode->next = pos;
    }
}


10)销毁

对于销毁链表,如果只free掉 *pphead行么?

当然不行!!


因为单链表由一个一个的结点连接起来的。如果只free(*pphead),头结点是释放了,但是后面的节点没被释放,还占用着空间但是已经找不到他们的地址了。


所以应该逐个释放👇

void SLDestroy(ListNode** pphead)
{
  ListNode* cur = *pphead;
  while (cur)
  {
  ListNode* next = cur->next;
  free(cur);
  cur = next;
  }
  *pphead = NULL; //最后别忘了置空
}


销毁完后 最好把*pphead 置空,防止销毁链表后对链表误操作而导致的野指针问题。

相关文章
|
2天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
2天前
|
存储
数据结构——带头双向循环链表
数据结构——带头双向循环链表
|
3天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
5天前
|
存储
初阶数据结构 带头双链表
初阶数据结构 带头双链表
8 0
|
5天前
数据结构初阶 链表的补充
数据结构初阶 链表的补充
7 0
|
5天前
|
存储
数据结构初阶 链表详解
数据结构初阶 链表详解
7 0
|
10天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
9 0
|
10天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
10 1
|
10天前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
10 0
|
10天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
9 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)