单链表——“数据结构与算法”

简介: 单链表——“数据结构与算法”

顺序表存在一些问题:

  • 中间/头部的插入删除,时间复杂度为O(N)
  • 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
  • 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

 

 

 

思考:如何解决以上问题呢?下面给出了链表的结构来看看。


链表

链表的概念及结构

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

现实中 数据结构中


结构体里面的数据类型:

typedef int SLTDataType;

定义一个结构体,结构体内部嵌套了一个结构体的指针:

这个就是单链表

typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;

单链表的打印:

//单链表的打印
void SLTPrint(SLTNode* phead)
{
  //可以不需要断言
  //因为:空链表也是可以打印的
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

意思是:首先,定义一个结构体的指针,该指针指向1,然后,对于cur,cur->data表示的是此结构体中的整型数据,cur->next表示的是2的地址,把cur->next赋值给cur,就是把这几块不连续的空间链接起来

表示:phead存的是第一个结点的地址,cur也存的是第一个节点的地址,就是把phead赋值给cur

头插

//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
  //assert(*pphead);
  //不能断言,链表为空,也需要能插入
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
 
  newnode->next = *pphead;
  *pphead = newnode;
}

测试一下头插的功能:

void TestSList1()
{
  SLTNode* plist = NULL;
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  SLTPrint(plist);
}
int main()
{
  TestSList1();
  return 0;
}

在写这段代码的过程中,很容易犯错误,可能会有很多人这样写代码:

//头插
void SLPushFront(SLTNode* phead, SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
 
  newnode->next = phead;
  phead = newnode;
}
void TestSList1()
{
  SLTNode* plist = NULL;
  SLPushFront(plist, 1);
  SLPushFront(plist, 2);
  SLPushFront(plist, 3);
  SLPushFront(plist, 4);
  SLPushFront(plist, 5);
  SLTPrint(plist);
}
int main()
{
  TestSList1();
  return 0;
}

这是一个十分经典的错误:

传值调用了!!!

实参是形参的一份临时拷贝,对形参的修改并不会影响实参,所以phead的改变并不会影响plist

举一个简单的例子:Swap

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int main()
{
  int a = 10;
  int b = 20;
  Swap(&a, &b);
  printf("%d %d\n", a, b);
  return 0;
}

毫无疑问,这样写确实是正确的。

有的人在这边可能就会想:是不是只要用了指针就可以了呢?

void Swap(int* p1, int* p2)
{
  int tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int main()
{
  int* px = 10;
  int* py = 20;
  Swap(px, py);
  printf("%d %d\n", px, py);
  return 0;
}

这样写,那是绝对不行的,接下来,来看看正确的写法:

void Swap(int** p1, int** p2)
{
  int* tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
int main()
{
  int* px = 10;
  int* py = 20;
  Swap(&px, &py);
  printf("%d %d\n", px, py);
  return 0;
}


我们会发现,在后续很多函数中,都需要用到创建结点这样一个功能,所以,可以把此功能封装成一个函数

//创建结点
void BuyLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;//就相当于初始化一下
}

尾插

从指向1的地址变为指向2的地址

循环所做的事

//尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  SLTNode* newnode = BuyLTNode(x);
  //1.空链表
  //2.非空链表
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;//tail->next本质是解引用,用tail的值找到指向的那个内存块,在内存块里面找到tail
    }
    tail->next = newnode;
  }
}
 

测试一下尾插的功能:

void TestSList2()
{
  SLTNode* plist = NULL;
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  SLTPrint(plist);
  SLPushBack(&plist, 6);
  SLPushBack(&plist, 7);
  SLPushBack(&plist, 8);
  SLPushBack(&plist, 9);
  SLPushBack(&plist, 10);
  SLTPrint(plist);
}
int main()
{
  TestSList2();
  return 0;
}

下面,来更好地解释一下为什么这边需要用到二级指针:

void func1(int* p)
{
  *p = 10;
}
void func2(int** pp)
{
  *pp = (int*)malloc(sizeof(int) * 10);
}
void func3(SLTNode* pnode)
{
  pnode->next = NULL;
}
void func4(SLTNode** ppnode)
{
  *ppnode = NULL;
}
int main()
{
  //要改变int,就要传int的地址
  int a = 0;
  func1(&a);
  //要改变int*,就要传int*的地址
  int* ptr = NULL;
  func2(&ptr);
  //要改变结构体,就要传结构体的地址
  SLTNode node;
  func3(&node);
  //要改变结构体的指针,传结构体的指针的地址
  SLTNode* pnode;
  func4(&pnode);
  return 0;
}

尾删

一个典型的错误的写法:野指针问题

解决方式:

找到尾结点以及它的前一个结点

//尾删
void SLPopBack(SLTNode** pphead)
{
  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
  assert(*pphead);
  SLTNode* prev = NULL;//前一个结点
  SLTNode* tail = *pphead;
  //找尾
  while (tail->next != NULL)
  {
    prev = tail;
    tail = tail->next;
  }
  free(tail);
  prev->next = NULL;
}

还可以找倒数第二个

//尾删
//找倒数第二个
void SLPopBack(SLTNode** pphead)
{
  //没有结点(空链表)
  //一个结点
  //多个结点
  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
  assert(*pphead);//暴力的检查
 
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    //找尾
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
  
}

测试一下尾删的功能:

void TestSList3()
{
  SLTNode* plist = NULL;
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  SLTPrint(plist);
  SLPushBack(&plist, 6);
  SLPushBack(&plist, 7);
  SLPushBack(&plist, 8);
  SLPushBack(&plist, 9);
  SLPushBack(&plist, 10);
  SLTPrint(plist);
  SLPopBack(&plist);
  SLPopBack(&plist);
  SLTPrint(plist);
}

头删

头删和尾删都有三种情况:

  • 没有结点(也就是空链表)
  • 有一个结点
  • 有多个结点

//头删
void SLPopFront(SLTNode** pphead)
{
  //没有结点(空链表)
  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
  assert(*pphead);//暴力的检查
  //链表为空,不能头删
  //一个结点
  //多个结点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* del = *pphead;//不能直接free掉
    //如果直接free的话,就找不到下一个结点的地址啦
    *pphead = del->next;
    free(del);
  }
}

测试一下头删的功能:

void TestSList4()
{
  SLTNode* plist = NULL;
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  SLTPrint(plist);
  SLPushBack(&plist, 6);
  SLPushBack(&plist, 7);
  SLPushBack(&plist, 8);
  SLPushBack(&plist, 9);
  SLPushBack(&plist, 10);
  SLTPrint(plist);
  SLPopBack(&plist);
  SLPopBack(&plist);
  SLTPrint(plist);
  SLPopFront(&plist);
  SLPopFront(&plist);
  SLTPrint(plist);
}


单链表查找

//头插、尾插、头删、尾删都要修改链表,所以要传二级指针
//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  //不用assert,因为空链表也是可以查找的
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}

测试一下单链表查找的功能:

void TestSList4()
{
  SLTNode* plist = NULL;
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  SLTPrint(plist);
  SLPushBack(&plist, 6);
  SLPushBack(&plist, 7);
  SLPushBack(&plist, 8);
  SLPushBack(&plist, 9);
  SLPushBack(&plist, 10);
  SLTPrint(plist);
  SLPopBack(&plist);
  SLPopBack(&plist);
  SLTPrint(plist);
  SLPopFront(&plist);
  SLPopFront(&plist);
  SLTPrint(plist);
  SLTNode* pos = SLTFind(plist, 2);
  pos->data = 30;
  SLTPrint(plist);
 
}


任意位置数据的插入(pos之前插入)

//在pos的位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  assert(*pphead);
  if (*pphead == pos)
  {
    SLPushFront(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuyLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

后插

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

测试一下前插和后插的功能:

void TestSList5()
{
  SLTNode* plist = NULL;
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  SLTPrint(plist);
  SLPushBack(&plist, 6);
  SLPushBack(&plist, 7);
  SLPushBack(&plist, 8);
  SLPushBack(&plist, 9);
  SLPushBack(&plist, 10);
  SLTPrint(plist);
  SLPopBack(&plist);
  SLPopBack(&plist);
  SLTPrint(plist);
  SLPopFront(&plist);
  SLPopFront(&plist);
  SLTPrint(plist);
  SLTNode* pos = SLTFind(plist, 3);
  if (pos != NULL)
  {
    SLTInsert(&plist, pos, 20);
  }
  SLTPrint(plist);
  pos = SLTFind(plist, 2);
  if (pos != NULL)
  {
    SLTInsertAfter(pos, 30);
  }
  SLTPrint(plist);
}

删除pos位置的值

//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  assert(*pphead);
  if (pos == *pphead)
  {
    SLPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}

后删

//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
}
void TestSList5()
{
  SLTNode* plist = NULL;
  SLPushFront(&plist, 1);
  SLPushFront(&plist, 2);
  SLPushFront(&plist, 3);
  SLPushFront(&plist, 4);
  SLPushFront(&plist, 5);
  SLTPrint(plist);
  SLPushBack(&plist, 6);
  SLPushBack(&plist, 7);
  SLPushBack(&plist, 8);
  SLPushBack(&plist, 9);
  SLPushBack(&plist, 10);
  SLTPrint(plist);
  SLPopBack(&plist);
  SLPopBack(&plist);
  SLTPrint(plist);
  SLPopFront(&plist);
  SLPopFront(&plist);
  SLTPrint(plist);
  SLTNode* pos = SLTFind(plist, 3);
  if (pos != NULL)
  {
    SLTInsert(&plist, pos, 20);
  }
  SLTPrint(plist);
  pos = SLTFind(plist, 2);
  if (pos != NULL)
  {
    SLTInsertAfter(pos, 30);
  }
  SLTPrint(plist);
  pos = SLTFind(plist, 7);
  if (pos != NULL)
  {
    SLTErase(&plist,pos);
  }
  SLTPrint(plist);
 
}


源代码如下:

SList.h的内容:

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
  SLTDataType data;
  struct SListNode* next;
}SLTNode;
//单链表的打印
void SLTPrint(SLTNode* phead);
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType x);
//头删
void SLPopFront(SLTNode** pphead);
//尾删
void SLPopBack(SLTNode** pphead);
//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos的位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDataType x);
//在pos的位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置之前的值
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);

SList.c的内容:

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//单链表的打印
void SLTPrint(SLTNode* phead)
{
  //可以不需要断言
  //因为:空链表也是可以打印的
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
  //assert(*pphead);
  //不能断言,链表为空,也需要能插入
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
 
  newnode->next = *pphead;
  *pphead = newnode;
}
//创建结点
SLTNode* BuyLTNode(SLTDataType x)
{
  SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;//就相当于初始化一下
  return newnode;
}
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
  //assert(*pphead);
  //不能断言,链表为空,也需要能插入
  SLTNode* newnode = BuyLTNode(x);
  //1.空链表
  //2.非空链表
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
      tail = tail->next;//tail->next本质是解引用,用tail的值找到指向的那个内存块,在内存块里面找到tail
    }
    tail->next = newnode;
  }
}
尾删
// 找倒数第一个
//void SLPopBack(SLTNode** pphead)
//{
//  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
//  assert(*pphead);
//  SLTNode* prev = NULL;//前一个结点
//  SLTNode* tail = *pphead;
//  //找尾
//  while (tail->next != NULL)
//  {
//    prev = tail;
//    tail = tail->next;
//  }
//  free(tail);
//  prev->next = NULL;
//}
//尾删
//找倒数第二个
void SLPopBack(SLTNode** pphead)
{
  //没有结点(空链表)
  //一个结点
  //多个结点
  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
  assert(*pphead);//暴力的检查
 
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    //找尾
    while (tail->next->next != NULL)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
  
}
//头删
void SLPopFront(SLTNode** pphead)
{
  //没有结点(空链表)
  assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
  assert(*pphead);//暴力的检查
  //链表为空,不能头删
  //一个结点
  //多个结点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* del = *pphead;//不能直接free掉
    //如果直接free的话,就找不到下一个结点的地址啦
    *pphead = del->next;
    free(del);
  }
}
//头插、尾插、头删、尾删都要修改链表,所以要传二级指针
//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
  //不用assert,因为空链表也是可以查找的
  SLTNode* cur = phead;
  while (cur != NULL)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }
  return NULL;
}
//在pos的位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  assert(pphead);
  assert(pos);
  assert(*pphead);
  if (*pphead == pos)
  {
    SLPushFront(pphead, x);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuyLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}
//在pos的位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
  assert(pos);
  SLTNode* newnode = BuyLTNode(x);
  newnode->next = pos->next;
  pos->next = newnode;
}
//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
  assert(pphead);
  assert(pos);
  assert(*pphead);
  if (pos == *pphead)
  {
    SLPopFront(pphead);
  }
  else
  {
    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}
//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
  assert(pos);
  assert(pos->next);
  SLTNode* next = pos->next;
  pos->next = next->next;
  free(next);
}

好啦,小雅兰今天的单链表的内容就到这里啦,内容还是非常多的,也比较难,小雅兰会继续加油学习的,冲冲冲!!!


相关文章
|
4月前
【数据结构】单链表(长期维护)(1)
【数据结构】单链表(长期维护)(1)
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
38 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
26 1
|
3月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
34 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
18 0
|
2月前
|
存储
数据结构--单链表
数据结构--单链表
|
2月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)