数据结构——单链表的基本操作

简介: 数据结构——单链表的基本操作

1.首先认识什么是单链表,知道其基本的定义:

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

结构图如下:

2.了解其来源(背景)

1.在顺序表中,对于整体空间的大小,在一定条件下会出现需要扩容的情况,而之前的顺序表在进行次操作时会出现一定的代价;

2.在对表中的元素进行相应的插入和删除操作时,顺序表往往存在一定的效率缺陷。

3.单链表的实现及其相应的操作,主要包括以下的函数,

// 动态申请一个节点

SLTNode* BuySLTNode(SLTDataType x);

//插入多个同时

SLTNode* CreateSList(int n);

// 单链表打印

void SLTPrint(SLTNode* phead);

// 单链表尾插

void SListPushBack(SListNode** pplist, SLTDateType x);

// 单链表的头插

void SListPushFront(SListNode** pplist, SLTDateType x);

// 单链表的尾删

void SListPopBack(SListNode** pplist);

// 单链表头删

void SListPopFront(SListNode** pplist);

// 单链表查找

SListNode* SListFind(SListNode* plist, SLTDateType x);

// 单链表在pos位置之后插入x

// 分析思考为什么不在pos位置之前插入?

void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值

// 分析思考为什么不删除pos位置?

void SListEraseAfter(SListNode* pos);

// 单链表的销毁

void SListDestroy(SList* plist);

//在pos之前插入

void SListInsert(SListNode* pphead, SListNode* pos, SLTDateType x);

//删除pos位置

void SListEraseAfter((SListNode** pphead ,SListNode* pos);

4.具体操作如下:

(1) 动态申请一个节点,次操作相当于对其初始化的操作,我们可以动态对其进行初始化,这样的好处相比静态初始化后期的操作可能会更方便

void SLTNode* BuySLTNode(SLTDataType x)
{
  SLTNode* newHead = (SLTNode*)malloc(sizeof(SLTNode));
  if (newHead == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newHead->data = x;
  newHead->next = NULL;
  return newHead;
}

(2)插入多个同时

SLTNode* CreateSList(int n)
{
  SLTNode* phead = NULL, *ptail = NULL;
  for (int i - 0; i < n; i++)
  {
    SLTNode* newnode = BuySLTNode(i);
    if (phead == NULL)
    {
      ptail = phead = newhead;
    }
    else
    {
      ptail->next = newnode;
      ptail = newnode;
    }
  }
  return phead;
}

(3) 单链表打印

void SLTPrint(SLTNode* phead)
{
  SLTNode* cur = phead;
  while (cur)
  {
    printf("%d->", cur->data);
    cur = cur->next;
  }
  printf("NULL\n");
}

(4)单链表尾插,在对表链表进行尾删的操作时,只需要两个节点,这里最难的是找尾,我们定义tail->next为尾,同时还要注意链表为空和顺序表为空的区别,同时使用二级指针来进行传递形参指向的内容

// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
  SLTNode* newnode = BuySLTNode(x);
  //判链表开始是否为空
  if (*pphead == NULL)
  {
    *pphead = newnode;
  }
  else
  {
    SLTNode* tail = *pphead;
    // 找尾
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

注意:

1.改变int,传递int*给形参,形参进行交换改变
2.改变int
,传递int**给形参,*形参进行交换改变

(5)单链表的头插,创建新节点newnode 指向第一个,对于第一个元素,又可以用地址来找到,这里为空时不需要单独处理

void SListPushFront(SListNode** pphead, SLTDateType x)
{
  SLTNode* newnode = BuySLTNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

(6)

单链表的尾删,这里有两种写法:

1.第一种我们可以在tail在往下继续指向时定义一个prev,双指针,tail再走之前给到prev,在依次执行,最后在找到tail时,tail的前一个也可以找得到(这里不写出来,大家可以试试!)

2.可以直接通过tail->->next来判断,但需要考虑其中tail->为空的情况

void SListPopBack(SListNode** pphead)
{
  // 暴力的检查
  assert(*pphead);
  // 温柔的检查
  //if (*pphead == NULL)
  //  return;
  //判断开始时链表是否只有一个元素
  if ((*pphead)->next == NULL)
  {
    free(*pphead);
    *pphead = NULL;
  }
  else
  {
    SLTNode* tail = *pphead;
    while (tail->next->next)
    {
      tail = tail->next;
    }
    free(tail->next);
    tail->next = NULL;
  }
}

(7)单链表头删,删除时需要断言一下,不能直接删,不然的话找不到下一个的地址,我们可以保存下一个,之后指向下一个就解决了,这就是单链表的优势所在

// 单链表头删
void SListPopFront(SListNode** pphead)
{
  assert(*pphead);
  SLTNode* next = (*pphead)->next;
  free(*pphead);
  *pphead = next;
}

(8)单链表查找

// 单链表查找
SListNode* SListFind(SListNode* pphead, SLTDateType x)
{
  SListNode* cur = pphead;
  while (cur)
  {
    if (cur->data == x)
      return cur;
    cur = cur->next;
  }
  return NULL;
}

(9)单链表在pos位置之后插入x,给出的位置不再是下标,而是指针,注意地址的衔接情况,这里可以不用二级指针,这里改变的是结构体,只需要结构体指针就可以了

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
  assert(pos);
  SListNode* next = pos->next;
  // pos newnode next
  SListNode* newnode = BuySListNode(x);
  newnode->next = next;
  pos->next = newnode;
}

(10)单链表删除pos位置之后的值

void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  //SListNode* next = pos->next;
  if (pos->next == NULL)
  {
    return;
  }
  else
  {
    SListNode* nextNode = pos->next;
    pos->next = nextNode ->next;
    free(nextNode );
  }
}

(11) 单链表的销毁

// 单链表的销毁
void SListDestroy(SList* pphead)
{
  SListNode* cur = *pphead;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
  *pphead = NULL;
}

(12)在pos之前插入

//在pos之前插入
void SListInsert(SListNode* pphead, SListNode* pos, SLTDateType x)
{
  assert(pos);
  if (*pphead == pos)
  {
    SListPushFront(pphead, x);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SListNode* newnode = BuySLTNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

(13)删除pos位置

//删除pos位置
void SListEraseAfter((SListNode** pphead ,SListNode* pos)
{
  assert(pos);
  if (pos == *pphead)
  {
    SListPopFront(pphead);
  }
  else
  {
    SListNode* prev = *pphead;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
  }
}

5.代码块如下:

test.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;

6.总结

数据结构与算法比较复杂,需要多画图。链表题多判断边界,勤加练习。

相关文章
|
3天前
|
存储 Java
Java数据结构:链表
Java数据结构:链表
16 2
TU^
|
7天前
|
存储 索引
数据结构~~链表
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的
TU^
18 0
|
2天前
|
缓存 算法
【数据结构】----链表--双向链表
【数据结构】----链表--双向链表
7 0
|
2天前
|
存储 缓存 算法
【数据结构】线性表----链表详解
【数据结构】线性表----链表详解
6 0
|
3天前
|
存储
数据结构——链表
数据结构——链表
11 0
|
3天前
<数据结构>栈和队列. 顺序表实现栈,单链表实现队列.
<数据结构>栈和队列. 顺序表实现栈,单链表实现队列
14 3
|
3天前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
11 1
|
3天前
(数据结构)单链表 —— 尾插,尾删,头插,头删,查找,插入,删除。
数据结构单链表 —— 尾插,尾删,头插,头删,查找,插入,删除
14 0
|
3天前
|
索引
【数据结构】单链表代码实现
【数据结构】单链表代码实现
8 1
|
3天前
|
Java
DAY-1 | Java数据结构之链表:删除无头单链表中等于给定值 val 的所有节点
力扣203题解:使用时间复杂度为O(n)的思路删除链表中所有值为key的元素。引入辅助指针pre,记录cur的前一个节点,遍历链表时,若cur.val!=key,pre和cur同时前进;若cur.val==key,则pre.next=cur.next,cur继续前进,确保pre不急于跟随以处理连续相同值的情况。遍历结束后,处理头节点可能需要删除的特殊情况。
15 0