【数据结构】C--单链表(小白入门基础知识)（上）

前段时间写了一篇关于顺序表的博客，http://t.csdn.cn/0gCRp

顺序表在某些时候存在着一些不可避免的缺点:

问题：

1. 中间 / 头部的插入删除，时间复杂度为 O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100 ，满了以后增容到 200，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。

寻求其他解决方案:

1、不扩容

2、按需申请释放

3、解决头部/中间插入删除需要挪动数据的问题(一块连续的物理空间)

   一.单链表的概念、结构和优缺点

1.1概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表

中的指针链接次序实现的 。

1.2单链表的结构

单链表是由一系列结点组成的线性结构，每个结点包含两个域：数据域和指针域。

数据域用来存储数据，指针域用来存储下一个结点的指针。单链表的头结点指向第一个结点，最后一个结点的指针域为空。

一个结点的结构：

逻辑结构:为了方便形象理解，想象出来的。

物理结构: 实际内存中，真实的样子。

1.3单链表的优缺点

单链表是一种常见的数据结构，它具有以下优缺点：

优点：

1.        插入和删除操作效率高：由于单链表的节点包含指向下一个节点的指针，因此在插入和删除节点时，只需要修改指针的指向，不需要移动大量的数据元素，因此效率较高。
2.        空间利用率高：单链表的节点只包含数据和指针两部分，不需要预先分配内存空间，因此空间利用率相对较高。
3.        长度可变：单链表的长度可以根据需要动态增长或缩小，不需要预先定义数组大小，具有较好的灵活性。

缺点：

1.        随机访问效率低：由于单链表的节点只包含指向下一个节点的指针，因此无法直接访问某个节点之前的节点，需要从头节点开始遍历到该节点，因此随机访问效率较低。
2.        存储空间浪费：由于单链表的每个节点都需要存储下一个节点的指针，因此在存储相同数据量的情况下，单链表需要更多的存储空间。
3.        链接信息的丢失：单链表中只有指向下一个节点的指针，无法直接访问前一个节点，因此在需要反向遍历链表或者删除节点时，需要保存前一个节点的指针，否则将无法完成操作。

二.单链表的实现

单链表各接口函数

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;//这样做的目的是为了增加代码的可读性和可维护性，以及提高代码的可移植性，
//因为如果将来需要更改 SLTDataType 的类型，只需要在 typedef 语句中修改一处即可，
// 如果我们在程序的其他地方需要修改 SLTDataType 的类型，
//只需在 typedef 语句中修改 int 为其他类型即可，不需要修改其他代码。
//typedef int SLTADataType;
typedef struct SListNode //--single Linked List
{
  SLTDataType data;//成员变量
  struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
//void SLPushFront(SLTNode* pphead,SLTDataType x);
void SLPushFront(SLTNode** pphead, SLTDataType x);//头部插入
//void SLPushBack(SLTNode* phead, SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);//尾部插入
void SLPopFront(SLTNode** pphead);//头部删除
void SLPopBack(SLTNode** pphead);//尾部删除
//单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x);
//单链表pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//单链表pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);
//单链表pos位置删除
void SLErase(SLTNode** pphead, SLTNode* pos);
//单链表pos之后删除
void SLEraseAfter(SLTNode* phead);

2.1结点的定义

英文简写:

单链表的英文为:Single linked list --简写为SL

而顺序表的英文是:Sequence table -- 简写为Seq

结点的英文为:node

typedef的主要作用有:主要用于提高代码的可读性和可维护性，这样代码的可读性会更好,因为SLTDataType这个名字说明了变量x的类型含义，可以为这个数据类型创建一个更简洁、更明了的别名，这样可以使代码更易读、更易维护。

typedef int SLTDataType;
typedef struct SListNode //--single Linked List
{
  SLTDataType data;//成员变量
  struct SListNode* next;
}SLTNode;

定义了一个单链表节点的结构体 SLTNode，其中包含了两个成员变量：一个名为 data 的int变量SLTDataType，和一个名为 next 的指向下一个节点的指针。

2.2链表的打印

需要了解到的知识:

                              “指针赋值的本质是将一个指针变量的地址复制给另一个指针变量”

int *p1, *p2; 
p1 = (int*)malloc(sizeof(int)); // 为p1分配内存
*p1 = 10; // 设置p1指向的内存的值为10
p2 = p1; // 将p1的地址赋值给p2

上面代码中,p1和p2都是指针变量。p1被分配了内存,并指向该内存。p2 = p1这行代码将p1的地址复制给了p2,使p2也指向p1所指向的内存。

所以指针赋值后,两个指针变量指向同一块内存,通过任一指针变量访问内存的值都会相同。

指针赋值不会复制指针指向的内存内容,仅仅是将指针变量中的地址值进行复制。

画图:

代码实现:

//函数的作用是遍历单链表，并将每个节点的数据元素打印到屏幕上。
void SLTPrint(SLTNode* phead)//参数是一个指向 SLTNode 类型的指针 phead，表示单链表的头节点。
{
  SLTNode* cur = phead;//头结点存储的地址给cur指针。
  while (cur != NULL)//使用一个while循环对单链表进行遍历，循环条件为 cur 不为 NULL。
  {    //cur 可以表示当前正在处理的节点的地址，
    //通过访问 cur->data 和 cur->next 成员变量，可以获取当前节点的数据元素和下一个节点的地址
    printf("%d->", cur->data);
    cur = cur->next;//cur是存着当前结点的地址,cur->next是下一结点地址
  }
  printf("NULL\n");
}

2.3创建一个新结点

SLTNode* BuyLTNode(SLTDataType x)//表示要创建的节点的数据元素。
//函数的作用是创建一个新的单链表节点，并将其初始化为包含数据元素 x 的节点。
{
  //SLTNode node;//这样是不行,处于不同的空间，出了作用域是会销毁的。
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//使用malloc函数动态分配了一个大小为SLTNode的内存块，
  //并将其强制转换为 SLTNode 指针类型，即创建了一个新的节点。
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  //需要注意的是，在使用 malloc 函数动态分配内存时，需要手动释放内存，否则会导致内存泄漏
  //因此，在创建单链表节点后，我们应该在适当的时候使用 free 函数释放节点所占用的内存
  newnode->data = x;
  newnode->next = NULL;
  return newnode;//返回的是一个结点的地址
}

该函数的作用是创建一个新的单链表节点，并将其初始化为包含数据元素 x 的节点。具体实现过程是通过使用 malloc 函数动态分配内存块，然后将其强制转换为 SLTNode 指针类型，即创建了一个新的节点。然后将该节点的 data 成员设置为 x，next 成员设置为 NULL，最后返回新节点的指针地址。

需要注意的是，在使用 malloc 函数动态分配内存时，需要手动释放内存，否则会导致内存泄漏。因此，在创建单链表节点后，我们应该在适当的时候使用 free 函数释放节点所占用的内存。

2.4单链表尾插

错误代码1:

图解:

void SLPushBack(SLTNode* phead, SLTDataType x)

{

   SLTNode* tail = phead;

   while (tail != NULL)

   {

         tail = tail->next;

   }

   SLTNode* newnode = BuyLTNode(x);

   tail = newnode;//这个地方没有链接起来

}

原因:

1.链表没有链接起来

2.出了作用域指针变量销毁，内存泄露

补充一下内存泄露的知识:

如果没有使用free函数释放通过malloc函数分配的内存空间，这些内存空间将一直占用着系统资源，直到程序结束或者操作系统重启。

当程序结束时，操作系统会回收该程序使用的所有内存空间，包括没有通过free函数释放的空间。但是，在程序运行期间，这些没有释放的内存空间会一直占用着系统资源，可能导致系统的内存资源耗尽，从而影响系统的稳定性和性能。

因此，为了避免内存泄漏问题，开发人员需要在程序中显式地使用free函数来释放不再使用的内存空间，以确保系统资源的有效利用。

错误代码2：

void SLPushFront(SLTNode** pphead, SLTDataType x);

void SLPushBack(SLTNode* phead, SLTDataType x);

void TestSList1()

{

   SLTNode* plist = NULL;

   SLPushFront(&plist,1);

   SLPushFront(&plist,2);

   SLPushFront(&plist,3);

   SLPushFront(&plist,4);

   SLTPrint(plist);

   SLPushBack(plist, 5);//这里传了一级指针

   SLTPrint(plist);

}

void SLPushBack(SLTNode* phead, SLTDataType x)

{

   SLTNode* tail = phead;

   while (tail->next!= NULL)

   {

       tail = tail->next;

   }

   SLTNode* newnode = BuyLTNode(x);

   tail->next = newnode;

}

这种情况是先头插然后再尾插，头插每次都需要二级指针，然而尾插需要第一次是传二级指针，后面可以传一级指针，但是参数是统一的，无法实现写两个相同的函数,第一次传一级指针，后面传二级指针。

所以一致传二级指针。

这种情况前提条件是链表不为空，可以直接修改结构体的next，存下新结点的地址。

执行：