数据结构第二课 -----线性表之单向链表

简介: 数据结构第二课 -----线性表之单向链表

动态顺序表的缺陷

  1. 尾部插入效率还不错,但是头部 和随机删除和随机插入效率很低
  2. 容量满了就要扩容。扩容分为两种,一种为原地扩容,一种为异地扩容(效率低下),扩容一般都会存在一定的空间浪费,(一次扩大50,而使用就使用一两个)


动态顺序表的优点

  1. 连续存储说明只需要知道一个地址就可以访问剩下的元素


链表

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

这个图是我们想象出来的,图中的方框就是一个节点

为了解决这个问题,前面的大佬就想到了通过地址访问空间,每一个节点存放下一个节点的地址

用plist存放第一个节点的地址,然后通过遍历一一访问

注意:


1.从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续般都是从堆上申请出来的

2.现实中的结点一般都是在堆上申请出来的(动态开辟)

3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

服设在32位系统上,结点中值域为int类型,则一个节点的大小为8个字节,则也可能有下述链表


链表的分类

链表有8种,下面我来一一介绍

  1. 单向或者双向

  2. 带头或者不带头

  3. 循环或者非循环

8种链表就是这么来的


单向链表

单向链表是链表中最常用的一种,一个列表节点有两个字段,即数据域和指针域。在单向链表中,指向第一个节点的节点称为“头结点”,最后一个节点的指针域设为null。


单项链表的操作

单链表的结构体

typedef int SLDataType;
//链表元素
typedef struct SListNode
{
  SLDataType val;
  struct SListNode *next;
  //这里只是一个指针,大小是4/8个大小,如果是定义成结构体变量就会出错
}SListNode;

这里要注意的就是struct SListNode next不能写成SListNodenext

打印输出

思路图:

//输出链表内容
void SLPrint(SListNode* phead)
{
  assert(phead);
  //防止phead的值改变
  SListNode* cur = phead;
  while (cur!= NULL)
  {
    printf("%d ", cur->val);
    cur = cur->next;
  }
  printf("\n");

}


这里很容易搞混,一些写出的错误可能就是链表的结尾和地址搞不明白很容易混淆

错误写法

void SLPrint(SListNode* phead)
{
  assert(phead);
  //防止phead的值改变
  SListNode* cur = phead;
  while (cur->next!= NULL)
  {
    printf("%d ", cur->val);
    cur = cur->next;
  }
  printf("\n");
}


这种情况就会导致最后一个无法打印出来

创建节点

//创建节点(动态开辟,防止出作用域销毁)
SListNode* CreateNode(SLDataType elemest)
{
  SListNode* p = (SListNode*)malloc(sizeof(SListNode));
  if (p == NULL)
  {
    perror("CreateNode -malloc");
    return;
  }
  p->next = NULL;
  p->val = elemest;
  return p;

}

尾插数据

思路: 我们要判断传入的链表中是不是空链表,空链表就是phead =NULL,如果是空链表,我们只需要phead指向插入数据的地址就行,如果不是,我们就要找到最后一个节点,把该节点的成员next的值是该数据的地址,然后把该数据的next改为NULL

void SLPushBack(SListNode** pphead, SLDataType elemest)
{
  //创建一个节点
  SListNode* Node = CreateNode(elemest);
  //找到最后一个节点,判断phead是否是NULL
  if (*pphead)
  {
    SListNode* stall = *pphead;
    while (stall->next != NULL)
    {
      stall = stall->next;
    }
    //插入
    stall->next = Node;
  }
  else
  {
    *pphead = Node;
  }
}

这里我们要判断两种情况的过程中有一些人可能会写成以下错误:

1.

3a93c6b8ae2ccf45ea56675ad88570b9_591200237c764ea8837df26351d346f2.png

这个错误就是让stall的地址指向的不是最后一个节点了


2.

b6c633fd844145c7648b458956a3f739_c87782fda8db440f824423bcf21a5f64.png

就是这里是传值调用,无法更改phead 的值,有很多就误以为更改这个形参就会更改实参了,所以我们要传入phead的地址,改变外面结构体的指针(phead)就要用二级指针


链表头插

思路图:

思路:让phead指向节点2

//头插
void SLPushFront(SListNode** pphead, SLDataType elemest)
{
  //创建节点
  SListNode* Node = CreateNode(elemest);
  //插入
  SListNode* tail = *pphead;
  *pphead = Node;
  (*pphead)->next = tail;
}

尾删

思路:

我们要分三种情况

一种是空链表 : 直接判断*phead

一种是只有一个节点 :判断(*pphead)->next 是否是 NULL

一种是多个节点:

思路:只要tail->next不是NULL,prev=tail,然后 tail指向下一个节点,否则free(tail),然后把prev->next =NULL

//尾删
void SLPopBack(SListNode** pphead)
{
  assert(*pphead && pphead);
  //一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//多个节点
  {
    SListNode* prev = *pphead;
    SListNode* tail = (*pphead)->next;
    while (tail->next != NULL)
    {
      prev = tail;
      tail = tail->next;
    }
    free(tail);
    tail == NULL;
    prev->next = NULL;
  }
}

或者这样写

//尾删
void SLPopBack(SListNode** pphead)
{
  assert(*pphead && pphead);
  //一个节点
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else//多个节点
  {
    
    SListNode* tail = *pphead;
    while (tail->next ->next != NULL)
    {
      tail = tail->next;
    }
    free(tail ->next);
    tail->next = NULL;

  }
}

错误写法:

这种写法就是一个大错误,主要是分不清prev和tail都是指向同一块空间,且没有考虑一个节点的情况

头删

思路图:

//头删
void SLPopFront(SListNode** pphead)
{
  assert(pphead && *pphead);
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SListNode* p = (*pphead)->next;
    free(*pphead);
    *pphead = p;
  }
}

或者这样写

//头删
void SLPopFront(SListNode** pphead)
{
  assert(pphead && *pphead);
  SListNode* p = (*pphead)->next;
  free(*pphead);
  *pphead = p;
}

这里我们主要还是要区分

pphead = NULL (存储的是空地址)

*pphead = NULL (phead存储的是NULL,但是phead有地址,代表空链表)

(*pphead)->next = NULL(代表的是当前节点是尾节点)


链表查找

思路: 遍历一遍链表,找到就返回地址,找不到就返回NULL


void* SLFind(SListNode* phead, SLDataType elemest)
{
  assert(phead);
  SListNode* tail = phead;
  while (tail != NULL)
  {
    if (tail->val == elemest)
    {
      return tail;
    }
    tail = tail->next;
  }
  return NULL;
}

链表的地址前插入

这里我们要清楚,传入的地址是否为NULL

思路: 插入分两种情况,一种是头插 一种是插入到多个之间

// 插入pos前面
void SLTInsert(SListNode** pphead, SListNode* pos, SLDataType elemest)
{
  //两者不为NULL
  assert(pphead && pos && *pphead);
  SListNode* tail = *pphead;
  // 创建节点
  SListNode* newnode = CreateNode(elemest);
  if (tail == pos)
  {
    //头插
    newnode->next = pos;
    *pphead = newnode;
  }
  else
  {
    while (tail->next != pos)
    {
      tail = tail->next;
    }
    tail->next = newnode;
    newnode->next = pos;
  }
}

这里的断言主要分三种情况 一种是 *phead和pos都可以为NULL,相当于空链表插入 ,一种是两者都不为NULL,一种是同时满足,这个要看自己来规定,这里我规定的是两个不能为空

链表的地址后插入

这里我们还是一样要考虑和前面的一样,

// 插入pos后面
void SLBInsert(SListNode** pphead, SListNode* pos, SLDataType elemest)
{
  assert(pphead && pos);
  //创建节点
  SListNode* newnode = CreateNode(elemest);

  //插入
  SListNode* tail = pos->next;
  pos->next = newnode;
  newnode->next = tail;
}

删除

思路:主要分析只要第一个节点(只有一个和多个)和多个节点


//删除
void SLErase(SListNode** pphead, SListNode* pos)
{
  assert(pphead && pos && *pphead);
  //写法1
  一个节点
  //if ((*pphead)->next == NULL)
  //{
  //  if (pos == *pphead)
  //  {
  //    free(pos);
  //    pos = NULL;
  //    *pphead = NULL;
  //  }
  //}
  //else //多个
  //{
  //  SListNode* tail = *pphead;
  //  if (pos == tail)
  //  {
  //    *pphead = (*pphead)->next;
  //    free(pos);
  //    pos = NULL;
  //  }
  //  else if (pos->next == NULL)
  //  {
  //    while (tail->next != pos)
  //    {
  //      tail = tail->next;
  //      
  //    }
  //    tail->next = NULL;
  //    free(pos);
  //    pos = NULL;
  //  }
  //  else
  //  {
  //    while (tail->next != pos)
  //    {
  //      tail = tail->next;
  //    }
  //    if (pos = tail->next)
  //    {
  //      SListNode* prev = pos->next;
  //      tail->next = prev;
  //      free(pos);
  //      pos = NULL;
  //    }
  //  }
  //}



  //写法2

  SListNode* tail = *pphead;
  if (pos == tail)
  {
    //头删
    SLPopFront(pphead);
  }
  else
  {
    //这个无法释放第一个节点
    while (tail->next != pos)
    {
      tail = tail->next;
    }
    tail->next = pos->next;
    free(pos);
    pos = NULL;
  }
  
}

链表的其他操作

//不传head ,在pos后面插入
void SLTInsertAfter(SListNode* pos, SLDataType elemest)
{
  assert(pos);
  //创建节点
  SListNode* newnode = CreateNode(elemest);
  newnode->next = pos->next;
  pos->next = newnode;
}
//不传head ,在pos前面插入,(交换值)
void SLTInsertFort(SListNode* pos, SLDataType elemest)
{
  assert(pos);
  //创建节点
  SListNode* newnode = CreateNode(elemest);
  newnode->next = pos->next;
  pos->next = newnode;
  //交换值
  SLDataType val = newnode->val;
  newnode->val = pos->val;
  pos->val = val;
}

//不传head ,在pos后面删除
void SLTEraseAfter(SListNode* pos)
{
  //删除尾节点会报错
  assert(pos &&pos->next);
  
  SListNode* prev = pos->next->next;
  free(pos->next);
  pos->next = prev;
}
目录
打赏
0
0
0
0
12
分享
相关文章
|
3月前
|
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
82 4
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
81 29
|
17天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
75 25
【C++数据结构——线性表】求集合的并、交和差运算(头歌实践教学平台习题)【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括: 1. **单链表表示集合**:使用单链表存储集合元素,确保元素唯一且无序。 2. **求并集**:遍历两个集合,将所有不同元素加入新链表。 3. **求交集**:遍历集合A,检查元素是否在集合B中存在,若存在则加入结果链表。 4. **求差集**:遍历集合A,检查元素是否不在集合B中,若满足条件则加入结果链表。 通过C++代码实现上述操作,并提供测试用例验证结果。测试输入为两个集合的元素,输出为有序集合A、B,以及它们的并集、交集和差集。 示例测试输入: ``` a c e f a b d e h i ``` 预期输出:
45 7
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
42 5
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
42 5
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
336 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等