数据结构——单链表(C语言)

简介: 数据结构——单链表(C语言)

链表的概念和结构:

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

下面是我们想象出来的图:


而实际上的图:

 

链表的结构多样,第一个就是不带头节点的链表,第二个是带哨兵位的头节点,而哨兵位是没有任何有效数据的。


下面我将讲解链表的各个实现,源码如下:

SListNode* BuySListNode(SListDateType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->date = x;
  newnode->next = NULL;
  return newnode;
}
void SListPrint(SListNode* plist)
{
  SListNode* cur = plist;
  while(cur)
  {
    printf("%d->", cur->date);
    cur = cur->next;
  }
  printf("NULL\n");
}
void SListPushBack(SListNode** pplist, SListDateType x)
{
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL)
  {
    *pplist = newnode;
  }
  else
  {
    SListNode* tail = *pplist;
    //β
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}
void SListPushFront(SListNode** pplist, SListDateType x)
{
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}
void SListPopFront(SListNode** pplist)
{
  assert(*pplist);
  SListNode* next = (*pplist)->next;
  free(*pplist);
  *pplist = next;
}
void SListPopBack(SListNode** pplist)
{
  assert(*pplist);
  SListNode* tail = *pplist;
  SListNode* newnode = NULL;
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = newnode;
  }
  else
  {
    while (tail->next)
    {
      newnode = tail;
      tail = tail->next;
    }
    free(tail);
    newnode->next = NULL;
  }
}
SListNode* SListFind(SListNode* plist, SListDateType x)
{
  SListNode* tail = plist;
  while (tail->next)
  {
    if (tail->date == x)
    {
      return tail;
    }
    tail = tail->next;
  }
  return NULL;
}
SListNode* SListInsertAfter(SListNode* pos, SListDateType x)
{
  assert(pos);
  SListNode* newnode = BuySListNode(x);
  SListNode* posnext = pos->next;
  pos->next = newnode;
  newnode->next = posnext;
}
void SListDestroy(SListNode* plist)
{
  assert(plist);
  free(plist);
}
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  SListNode* posnext = pos->next->next;
  free(pos->next);
  pos->next = posnext;
}

ps:1.这里我设计的链表函数时没有返回值的,所以我用到了二级指针,因为如果我们传一级指针的话,形参只是实参的一份临时拷贝,当出了作用域后, 创建的newnode等等这些在栈上开辟的变量就会不存在了,不会影响到要改变的plist。

2.当然你也可以设计一个返回结构体,这样就可以直接传值,最后也可以改变链表的结构。

链表的尾插:

  • 这里我是调用了一个BuySListNode的函数来创建一个节点,BuySListNode的实现就是用malloc开辟了结构体类型的空间,然后把SListDateType的类型数据给了结构体中的date,然后把指针域赋为了NULL
  • 尾插的思想:分为2种,第一种是一开始传的plist为NULL时,第二种就是plist不为NULL
  • 第一种情况:当传的plist为NULL时,说明我们链表还没数据,直接把创还能得newnode给给plist就行了。
  • 第二种情况:当plist不为NULL时,我们就用while循环找尾,然后把尾的next给给newnode,就实现了链表的尾插。
SListNode* BuySListNode(SListDateType x)
{
  SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->date = x;
  newnode->next = NULL;
  return newnode;
}
void SListPushBack(SListNode** pplist, SListDateType x)
{
  SListNode* newnode = BuySListNode(x);
  if (*pplist == NULL)
  {
    *pplist = newnode;
  }
  else
  {
    SListNode* tail = *pplist;
    while (tail->next != NULL)
    {
      tail = tail->next;
    }
    tail->next = newnode;
  }
}

链表的头插:

  • 头插的思想:
  • 我们直接让创建出来的newnode指向*pplist,然后更新头结点就可以了。
void SListPushFront(SListNode** pplist, SListDateType x)
{
  SListNode* newnode = BuySListNode(x);
  newnode->next = *pplist;
  *pplist = newnode;
}

链表的尾删:

  • 一开始用断言检查一下,*pplist不能为NULL,这里的意思是如果是NULL,就代表了没有数据了,不能删除
  • 第一种情况:当只有一个节点的时候,我就创建了newnode的节点,只需要free第一个节点,然后把newnode给给它就行了。
  • 第二种情况:当有二个或多个节点的时候,我就定义了一个tail指针来记录尾节点的位置,然后用newnode来记录尾结点前一个的位置,最后free掉tail节点,然后把前一个置为NULL。
void SListPopBack(SListNode** pplist)
{
  assert(*pplist);
  SListNode* tail = *pplist;
  SListNode* newnode = NULL;
  if ((*pplist)->next == NULL)
  {
    free(*pplist);
    *pplist = newnode;
  }
  else
  {
    while (tail->next)
    {
      newnode = tail;
      tail = tail->next;
    }
    free(tail);
    newnode->next = NULL;
  }
}

链表的头删:

  • 一开始也是和尾删一样的思路,用assert断言一下,防止没节点了还删除。
  • 头删的思路:记录头结点下一个节点的位置,然后free掉头结点,然后让下一个节点当头节点。
void SListPopFront(SListNode** pplist)
{
  assert(*pplist);
  SListNode* next = (*pplist)->next;
  free(*pplist);
  *pplist = next;
}

链表的查找:

  • 如果我们要查找链表中某个节点,直接遍历链表,当我们查找的数据和X相同时,就是我们要找的节点了,如果没有,就返回NULL。
SListNode* SListFind(SListNode* plist, SListDateType x)
{
  SListNode* tail = plist;
  while (tail->next)
  {
    if (tail->date == x)
    {
      return tail;
    }
    tail = tail->next;
  }
  return NULL;
}

链表指定位置之后的插入:

  • 首先先断言一下,pos是有效的节点
  • 我先创建了一个节点,然后用posnext来记录pos之后的节点,最后我让pos指向newnode,然后用newnode的next指向posnext。这样我就实现了链表指定位置之后的插入了。
SListNode* SListInsertAfter(SListNode* pos, SListDateType x)
{
  assert(pos);
  SListNode* newnode = BuySListNode(x);
  SListNode* posnext = pos->next;
  pos->next = newnode;
  newnode->next = posnext;
}

链表指定位置之前的插入:

  • 首先也是老套路,先断言一下,让pos和pplist为有效。
  • 这里分为二种情况
  1. 第一种:当pos是第一个节点的时候,就复用头插的函数。
  2. 第二种:当pos指向第二个或后面的节点的时候,用prev来记录pos之前节点的位置,然后让prev指向创建的newnode,newnode指向pos。
void SLTInsert(SLTNode** pplist, SLTNode* pos, SLTDataType x)
{
  assert(pplist);
  assert(pos);
  if (pos == *pplist)
  {
    SLTPushFront(pplist, x);
  }
  else
  {
    SLTNode* prev = *pplist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    SLTNode* newnode = BuySListNode(x);
    prev->next = newnode;
    newnode->next = pos;
  }
}

链表指定位置之后的删除:

  • 老套路,先断言一下(保持好习惯)。
  • 用posnext来记录pos的下下的节点,free掉pos之后的节点,然后让pos指向posnext。
void SListEraseAfter(SListNode* pos)
{
  assert(pos);
  SListNode* posnext = pos->next->next;
  free(pos->next);
  pos->next = posnext;
}

链表指定位置的删除:

  • 先断言,这里就不再叙述了。
  • 第一种情况:当pos为第一个节点的时候,就是头删,复用头删的函数就可以了。
  • 第二种情况:用prev来记录pos之前的节点,然后让prev指向pos之后的节点,最后free掉pos节点。
void SLTErase(SLTNode** pplist, SLTNode* pos)
{
  assert(pplist);
  assert(pos);
  if (pos == *pplist)
  {
    SLTPopFront(pplist);
  }
  else
  {
    SLTNode* prev = *pplist;
    while (prev->next != pos)
    {
      prev = prev->next;
    }
    prev->next = pos->next;
    free(pos);
    //pos = NULL;
  }

链表最后的处理:

  • 还是先断言。
  • 然后用把第一个节点赋给cur,迭代往后走,用next来记录cur的下一个节点,free掉cur节点,最后让把cur下一个节点给给cur。
void SListDestroy(SListNode** pplist)
{
  assert(pplist);
  SListNode* cur = *pplist;
  while (cur)
  {
    SListNode* next = cur->next;
    free(cur);
    cur = next;
  }
}
#pragma once
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef int SListDateType;
typedef struct SListNode
{
  SListDateType date;
  struct SListNode* next;
}SListNode;
SListNode* BuySListNode(SListDateType x);
void SListPrint(SListNode* plist);
void SListPushBack(SListNode** pplist, SListDateType x);
void SListPushFront(SListNode** pplist, SListDateType x);
void SListPopFront(SListNode** pplist);
void SListPopBack(SListNode** pplist);
SListNode* SListFind(SListNode* plist, SListDateType x);
void SListInsertAfter(SListNode* pos, SListDateType x);
void SLTInsert(SLTNode** pplist, SLTNode* pos, SLTDataType x);
void SListEraseAfter(SListNode* plist);
void SLTErase(SLTNode** pplist, SLTNode* pos);
void SListDestroy(SListNode** pplist);
相关文章
|
24天前
|
存储
[数据结构]——单链表——超详解
[数据结构]——单链表——超详解
|
1天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
9天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
9 0
|
9天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
9 1
|
9天前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
10 0
|
9天前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
7 0
|
9天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
8 0
|
9天前
数据结构——栈(C语言版)
数据结构——栈(C语言版)
|
9天前
数据结构——队列(C语言版)
数据结构——队列(C语言版)
|
9天前
|
存储 C语言
数据结构——顺序表(C语言版)
数据结构——顺序表(C语言版)
10 5