【C语言入门数据结构】单链表实现详解(二)

简介: c语言实现单链表详解

2、单链表(single linked list)程序:

经过上面简单的单链表链接,想必你已经对单链表有了些许认识,下面让我们来实现单链表吧!!

1、结构体定义结点

typedef int SLTDataType;//重定义数据类型,方便切换数据类型
typedef struct SListNode//定义单链表结构   32位环境下共8个字节,
{
    SLTDataType data;//定义数据
    struct SListNode* next;//指向下一个结构的指针,指向同类
    //SLTNode* next;
}SLTNode;//重定义 缩写,在本行之后起效,在结构体中不能使用

注意:这里重定义的结构名,只能在定义之后使用,不能在结构体中使用。

2、尾插

tail->next是结构体指针指向结构体成员next,而next存放的是下一个结点的地址,next指向下一个结点。

初始代码:

//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  SLTNode* tail = phead;
  //找尾
  while (tail->next)
  {
    tail = tail->next;//不是结尾,tail向后移动。
  }
  tail->next = newnode;//是结尾,tail->next链接新结点
}

测试:

void TestSList2()
{
  SLTNode* plist = CreateSList(5);
  SLTPushBack(plist, 100);
  SLTPushBack(plist, 200);
  SLTPushBack(plist, 300);
  SLTPrint(plist);
}
void TestSList3()
{
  SLTNode* plist = NULL;
  SLTPushBack(plist, 100);
  SLTPushBack(plist, 200);
  SLTPushBack(plist, 300);
  SLTPrint(plist);
}
int main()
{
  TestSList2();
    //TestSList3();
  return 0;
}

调用TestSList2时:

调用TestSList3时:

此时,我们插入的数据并没有插进去,所以要考虑到链表为空的情况

改进代码:

//尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (phead == NULL)
  {
    phead = newnode;
  }
  else
  {
    SLTNode* tail = phead;
    //找尾
    while (tail->next)
    {
      tail = tail->next;//不是结尾,tail向后移动。
    }
    tail->next = newnode;//是结尾,tail->next链接新结点
  }
}

如图,还是没插入进来

这里就要注意,phead是plist的拷贝,phead的改变不会影响plist,phead出作用域销毁,plist此时还是NULL。

这就涉及到实参传给形参,形参是实参的临时拷贝,形参的改变不会影响实参

举一个经典的例子:

如图:

1、改变int,传递int给形参,解引用形参进行交换改变。
2、改变int
,传递int**给形参,解引用形参进行交换改变。

所以需要进行修改,这里的pphead是为了方便区分,也可以直接使用phead。

左图代码phead的改变是无法影响plist的值的,所以我们用到二级指针做如下改变(函数栈帧):

注意:想要改变结构体,只需要使用结构体的指针tail->next,无需使用二级指针。

正确代码:

//尾插
void SLTPushBack(SLTNode** phead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*phead == NULL)
  {
    *phead = newnode;
  }
  else
  {
    SLTNode* tail = *phead;
    //找尾
    while (tail->next)
    {
      tail = tail->next;//不是结尾,tail向后移动。
    }
    tail->next = newnode;//是结尾,tail->next链接新结点
  }
}

3、尾删

经典错误:

当我们将tail释放时,d2->next还指向tail,这就形成了野指针。

tail是局部变量,不需要置空。

改进方法:

方法一:

如图,在tail往下走之前,我们可以将tail赋值给一个新的变量prev,从而找到最后一个结点之前的结点,释放tail之后,再使用结构体指针将前一个结点的指针域置为空。

void SLTPopBack(SLTNode* phead)
{
  SLTNode* tail = phead;
  SLTNode* prev = NULL;
  while (tail->next)
  {
    prev = tail;
    tail = tail->next;
  }
  free(tail);
  prev->next = NULL;
}

方法二:

如图,当tail指向d1时,tail->next->next就是d2->next不为空,tail指d2,此时tail->next->next为空,tail->next为d2->next,将其释放并置为空。

void SLTPopBack(SLTNode* phead)
{
  SLTNode* tail = phead;
  while (tail->next->next)
  {
    tail = tail->next;
  }
  free(tail->next);
  tail->next = NULL;
}

但是上面代码并不完善,当我们进行多次删除打印,错误就会暴露出来,如下图,我们进行了四次打印,但却只输出了3次。

如图,当删除tail后面的两个结点后,tail->next为空,这时就再去使用tail->next就是错误的。

初步改进:

void SLTPopBack(SLTNode* phead)
{
  if (phead->next == NULL)
  {
    free(phead);
    phead = NULL;
  }
  else
  {
    SLTNode* tail = phead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}


分析原因,我们发现phead的改变不会影响plist,而我们这里释放了phead并且将phead置为了空,所以尾删也得用二级指针。

注意:链表为空不能删除,所以我们需要assert断言

正确代码:

void SLTPopBack(SLTNode** phead)
{
    assert(*phead);//链表为空,不可删除,为空直接报错,终止
  if ((*phead)->next == NULL)
  {
    free(*phead);
    *phead = NULL;
  }
  else
  {
    SLTNode* tail = *phead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}


4、头插

如图,我们看出头插相对比较简单,我们只需要将newnode->next指向原来的开始结点,再将phead指针指向新的开始,也不必考虑空的情况:

正确代码:

//头插
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *phead;
  *phead = newnode;
}

5、头删

当链表为空时,不能进行头删,所以这里同样需要断言。

头删不能直接删,直接删会导致找不到链表

先创建一个变量next间接指向下一个结点,再释放前一个结点,最后再将phead指向next,保证第一个节点的指针。

//头删
void SLTPopFront(SLTNode** phead)
{
  assert(*phead);
  SLTNode* next = (*phead)->next;
  free(*phead);
  *phead = next;
}

链表的优势在于头删,又快又简洁。


6、查找数据指定位置pos

在查找时,最好用一个变量来接收phead,保证phead在过程中一直指向链表的开始。

经典错误:

//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur->next != NULL)
  {
      if (cur->data == x)
    {
      return cur;
    }
        cur=cur->next;
  }
}

问题:

1、当链表为空时,进行查找,此时phead为空,cur也为空,那么cur->next,解引用失败,程序就会崩。

2、这样会漏掉最后一个结点,如下图,当cur->next为空时,循环结束,最后一个结点的data没有查找到。

所以最好不要写这样的代码。

最终代码:

//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
}

7、在指定位置pos之后插入x

和顺序表的最大区别:给的位置不再是下标,而是结点的指针

经典错误:

如图,将pos->next先指向了新节点newnode,此时无法找到4的位置,所以newnode->next又指向了自己,形成了带环链表。此时程序是死循环:

此时,我们可以先保存4的位置,再进行链接,或者直接将上面的两步跌倒。

这里只写第二种:

最终代码:

注意这里需要检查pos是否为空

如图,先将newnode和4链接,再进行前面的链接就不会出现上面的错误,代码如下:

//在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}

这里改变的是结构体成员,有结构体的指针足以,不需要二级指针。


8、在指定位置pos之前插入x

如图,分析可知有下面两种情况:

//在pos位置之前插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  if (*phead == pos)//头插
  {
    SLTPushFront(phead, x);//复用
  }
  else
  {
    SLTNode* prev = *phead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

9、删除指定位置pos之后的值

可能遇到两种情况:

1、pos指向最后一个结点,pos之后的值为空,适合用温柔的检查(如下if语句)

2、pos在中间,直接链接3和5会找不到4,从而无法释放造成内存泄漏。所以需要将4的位置给一个新的变量nextNode以便释放。

经过分析,


10、删除指定位置pos的值

//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  if (pos == *phead)
  {
    SLTPopFront(phead);
  }
  else
  {
    SLTNode* prev = *phead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}

11、释放单链表

//单链表的释放
void SLTDestory(SLTNode** phead)
{
  SLTNode* cur = *phead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *phead = NULL;//plist置空,防止释放后再调用
}

总代码:

1、SList.h文件

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//相当于下面的重定义
//struct SListNode
//{
//  STLDataType data;
//  struct SListNode* next;
//};
//typedef struct SListNode SLTNode;
//void SLTPushBack(SLTDataType x)
//{
//  SLTNode node;//这样定义的结点出作用域销毁
//}
typedef int SLTDataType;//重定义数据类型,方便切换数据类型
typedef struct SListNode//定义单链表结构   32位环境下共8个字节,
{
  SLTDataType data;//定义数据
  struct SListNode* next;//指向下一个结构的指针,指向同类
  //SLTNode* next;
}SLTNode;//重定义 缩写,在本行之后起效,在结构体中不能使用
SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);
//尾插尾删
void SLTPushBack(SLTNode** phead, SLTDataType x);
void SLTPopBack(SLTNode** phead);
//头插头删
void SLTPushFront(SLTNode** phead, SLTDataType x);
void SLTPopFront(SLTNode** phead);
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置之后的值
void SListEraseAfter(SLTNode* pos);
//在pos位置之前插入x
void SListInsert(SLTNode** phead,SLTNode* pos, SLTDataType x);
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos);
//单链表的释放
void SLTDestory(SLTNode** phead);

2、SList.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//直接用malloc需要自行赋值,检查空,很烦,所以封装一个函数
SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);//未开辟成功,结束程序
  }
  newnode->data = x;
  newnode->next = NULL;//最后一个结点默认为空
  return newnode;
}
SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL, * ptail = NULL;
  /*int x = 0;*/
  for (int i = 0; i < n; ++i)
  {
    /*scanf("%d", &x);
    SLTNode* newnode = BuySLTNode(x);*/
    SLTNode* newnode = BuySLTNode(i);
    if (phead == NULL)
    {
      ptail = phead = newnode;
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode;
    }
  }
  return phead;
}
//打印函数封装
void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("[%d|%p]->", cur->data,cur->next);
    cur = cur->next;
  }
  printf("NULL\n");
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    //找尾
    while (tail->next)
    {
      tail = tail->next;//不是结尾,tail向后移动。
    }
    tail->next = newnode;//是结尾,tail->next链接新结点
  }
}
//尾删
//void SLTPopBack(SLTNode* phead)
//{
//  SLTNode* tail = phead;
//  SLTNode* prev = NULL;
//  while (tail->next)
//  {
//    prev = tail;
//    tail = tail->next;
//  }
//  free(tail);
//  prev->next = NULL;
//}
//尾删
void SLTPopBack(SLTNode** phead)
{
  assert(*phead);
  if ((*phead)->next == NULL)
  {
    free(*phead);
    *phead = NULL;
  }
  else
  {
    SLTNode* tail = *phead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}
//头插
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *phead;
  *phead = newnode;
}
//头删
void SLTPopFront(SLTNode** phead)
{
  assert(*phead);
  SLTNode* next = (*phead)->next;
  free(*phead);
  *phead = next;
}
//查找数据指定位置pos
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  SLTNode* cur = phead;
  while (cur)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
}
//在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//在pos位置之前插入x
void SListInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
  assert(pos);
  if (*phead == pos)
  {
    SLTPushFront(phead, x);
  }
  else
  {
    SLTNode* prev = *phead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//删除pos位置之后的值
void SListEraseAfter(SLTNode* pos)
{
  assert(pos);
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    /*free(pos->next);
    pos->next = pos->next->next;*///错误,释放了后一个,这个空间被置为随机值,找不到后面的结点
    SLTNode* nextNode = pos->next;
    pos->next = nextNode->next;
    free(nextNode);
  }
}
//删除pos位置
void SListErase(SLTNode** phead, SLTNode* pos)
{
  assert(pos);
  if (pos == *phead)
  {
    SLTPopFront(phead);
  }
  else
  {
    SLTNode* prev = *phead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
//单链表的释放
void SLTDestory(SLTNode** phead)
{
  SLTNode* cur = *phead;
  while (cur)
  {
    SLTNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *phead = NULL;//plist置空,防止释放后再调用
}

3、test.c测试文件

#include"SList.h"
void TestSList1()
{
  //SLTNode* n1 = malloc();//直接用malloc需要自行赋值,检查空,很烦,所以封装一个函数
  SLTNode* n1 = BuySLTNode(1);
  SLTNode* n2 = BuySLTNode(2);
  SLTNode* n3 = BuySLTNode(3);
  SLTNode* n4 = BuySLTNode(4);
  n1->next = n2;
  n2->next = n3;
  n3->next = n4;
  n4->next = NULL;
  //SLTNode n1;//为什么不直接定义结构体变量
  //SLTNode n2;
  //n1.next = &n2;//这样也可以链接,但是不可行
  //SLTNode* plist = CreateSList(5);
  //SLTPrint(plist);
}
//初始测试代码
void TestSList2()
{
  SLTNode* plist = CreateSList(5);
  SLTPushBack(&plist, 100);
  SLTPushBack(&plist, 200);
  SLTPushBack(&plist, 300);
  SLTPrint(plist);
}
void TestSList3()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 100);
  SLTPushBack(&plist, 200);
  SLTPushBack(&plist, 300);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
  SLTPopBack(&plist);
  SLTPrint(plist);
}
void TestSList4()
{
  SLTNode* plist = NULL;
  SLTPushFront(&plist, 100);
  SLTPushFront(&plist, 200);
  SLTPushFront(&plist, 300);
  SLTPushFront(&plist, 400);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
  SLTPopFront(&plist);
  SLTPrint(plist);
}
void TestSList5()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  SListInsertAfter(pos, 30);
  pos = SListFind(plist, 2);
  SListInsert(&plist, pos, 200);
  SLTPrint(plist);
  //  if (pos)
  //  {
  //    SListInsertAfter(pos, 30);//找到之后在后面插入30
  //    printf("找到了\n");
  //
  //  }
  //  else
  //  {
  //    printf("找不到\n");
  //  }
  //  SLTPrint(plist);
}
void TestSList6()
{
  SLTNode* plist = NULL;
  SLTPushBack(&plist, 1);
  SLTPushBack(&plist, 2);
  SLTPushBack(&plist, 3);
  SLTPushBack(&plist, 4);
  SLTPushBack(&plist, 5);
  SLTPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  SListEraseAfter(pos);
  SLTPrint(plist);
  pos = SListFind(plist, 3);
  SListErase(&plist,pos);
  pos = NULL;
  SLTPrint(plist);
  SLTDestory(&plist);
  SLTPrint(plist);
}
int main()
{
  //TestSList1();
  //TestSList2();
  //TestSList3();
  //TestSList4();
  //TestSList5();
  TestSList6();
  return 0;
}
////二级指针经典例子
//void Swap1(int* p1, int* p2)
//{
//  int tmp = *p1;
//  *p1 = *p2;
//  *p2 = tmp;
//}
//void Swap2(int** pp1, int** pp2)
//{
//  int tmp = *pp1;
//  *pp1 = *pp2;
//  *pp2 = tmp;
//}
//
//int main()
//{
//  int a = 0, b = 1;
//  swap1(&a, &b);
//  
//  int* ptr1 = &a, * ptr2 = &b;
//  swap2(&ptr1, &ptr2);
//
//  return 0;
//
//}

注意:

如果不用二级指针,我们可以用返回值,但是每次返回得接收,c++中可以用引用

不需要修改头指针就用一级,需要修改就用二级,必须将实参的地址传给形参


结语:

这里本章内容就介绍完了,文章中某些内容我们之前有介绍,所以只是一笔带过,还请谅解。希望以上内容对大家有所帮助👀,如有不足望指出🙏

前路漫漫!努力变强💪💪 吧!!c

相关文章
|
5天前
|
存储 自然语言处理 编译器
振南技术干货集:振南当年入门C语言和单片机的那些事儿(3)
振南技术干货集:振南当年入门C语言和单片机的那些事儿(3)
|
1天前
|
存储 NoSQL 算法
Redis入门到通关之Redis数据结构-Hash篇
Redis入门到通关之Redis数据结构-Hash篇
10 1
|
1天前
|
存储 NoSQL Redis
Redis入门到通关之Redis数据结构-List篇
Redis入门到通关之Redis数据结构-List篇
|
1天前
|
存储 NoSQL 安全
Redis入门到通关之Redis数据结构-String篇
Redis入门到通关之Redis数据结构-String篇
|
1天前
|
存储 NoSQL Redis
Redis入门到通关之数据结构解析-SkipList
Redis入门到通关之数据结构解析-SkipList
|
1天前
|
存储 NoSQL 安全
Redis入门到通关之数据结构解析-动态字符串SDS
Redis入门到通关之数据结构解析-动态字符串SDS
|
1天前
|
存储 NoSQL Java
Redis入门到通关之数据结构解析-Dict
Redis入门到通关之数据结构解析-Dict
|
1天前
|
C语言
C语言用头插法建立单链表
C语言用头插法建立单链表
4 0
|
1天前
|
存储 算法 C语言
C语言进阶:顺序表(数据结构基础) (以通讯录项目为代码练习)
C语言进阶:顺序表(数据结构基础) (以通讯录项目为代码练习)
|
2天前
|
C语言
数据结构中顺序栈的进栈和出栈用C语言表示
数据结构中顺序栈的进栈和出栈用C语言表示
11 1