手把手教你实现链表—单链表(数据结构C语言实现3)

简介: 手把手教你实现链表—单链表(数据结构C语言实现3)

本节目标

1.链表表示和实现(单链表+双向链表)

2.链表的常见OJ题

3.顺序表和链表的区别和联系


链表表示和实现(单链表+双向链表)

顺序表的问题及思考问题:


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

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

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

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

链表的概念

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


逻辑结构

image.png

想必大家看的都是链表的逻辑结构,其实真实并不存在连接两个链表的箭头,为了更好理解罢了。箭头代表前面的节点存了,后面节点的指针。

物理结构

物理结构就是真正的结构,便于初学者学习!

image.png

是不是突然对链表有了更深刻的理解!


单链表的实现

// 1、无头+单向+非循环链表增删查改实现
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
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
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos);

链表节点创建

链表的创建也是用结构体创建。


//类型创建
  typedef int SLDataType;
  typedef struct SListNode
  {
      SLDataType date;   //存值
      struct SListNode* next; //存下一节点的指针
  }SLNode;
// 动态申请一个节点
SLTNode* BuySListNode(SLTDataType x)
{
   SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
   newnode->date = x;
   newnode->next = NULL;
   return newnode;
}
// 打印
void SListPrint(SLTNode* phead)
{
   while (phead != NULL)
   {
    printf("%d ", phead->date);
    phead = phead->next;
   }
   printf("NULL\n");
}
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
   if (*pphead == NULL)
   {
    *pphead = BuySListNode(x);
   }
   else
   {
    SLTNode* tail = *pphead;
    while (tail->next)
    {
      tail = tail->next;
    }
    tail->next = BuySListNode(x);
   }
}
//头插接口测试
void TestSList2()
{
   SLTNode* plist = NULL;
   SListPushFront(&plist, 1);
   SListPushFront(&plist, 2);
   SListPushFront(&plist, 3);
   SListPushFront(&plist, 4);
   SListPushFront(&plist, 5);
   SListPushFront(&plist, 6);
   SListPrint(plist);
}

image.png


//头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
   if (!*pphead)
   {
    *pphead= BuySListNode(x);
   }
   else
   {
    SLTNode* first = BuySListNode(x);
    first->next = *pphead;
    *pphead = first;
   }
}
//头插接口测试
void TestSList2()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
}

image.png

//头删
void SListPopFront(SLTNode** pphead)
{
  if (!*pphead)
  {
  return;
  } 
  else
  {
  *pphead = (*pphead)->next;
  }
}
//头删接口测试
void TestSList3()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPopFront(&plist);
  SListPrint(plist);
}

image.png

//尾删
void SListPopBack(SLTNode** pphead)
{
  //1头结点为空
  //2只有一个节点
  //3多个节点
  if (*pphead == NULL)
  {
  return;
  }
  else if ((*pphead)->next ==NULL)
  {
  *pphead = NULL;
  free(*pphead);
  }
  else
  {
  SLTNode* tail = *pphead;
  SLTNode* ret = *pphead;
  while (tail->next)
  {
    ret = tail;
    tail = tail->next;
  }
  tail = NULL;
  ret->next = NULL;
  free(tail);
  }
}
//尾删接口测试
void TestSList4()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPopBack(&plist);
  SListPrint(plist);
}

image.png


//查找节点x位置并返回节点位置
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  if (phead == NULL)  //节点为空
  {
  return NULL;
  }
  else
  {
  SLTNode *ret= phead;
  while (ret) 
  {
    if (ret->date == x)    //找到了
    {
    return ret;
    }
    ret = ret->next;
  }
  return NULL;           //找不到
  }
}
// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
  SLTNode* newnode = BuySListNode(x);
  if (*pphead == NULL)
  {
  return;
  }
  else if(*pphead==pos)
  {
  *pphead = newnode;
  newnode->next = pos;
  }
  else
  {
  SLTNode* ret = *pphead;
  while (ret->next != pos)
  {
    ret = ret->next;
  }
  ret->next = newnode;
  newnode->next = pos;
  }
}
//任意位置查找插入测试
void TestSList5()
{
  SLTNode* plist = NULL;
  SListPushFront(&plist, 1);
  SListPushFront(&plist, 2);
  SListPushFront(&plist, 3);
  SListPushFront(&plist, 4);
  SListPushFront(&plist, 5);
  SListPushFront(&plist, 6);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist,3);
  if (pos)
  {
  SListInsert(&plist,pos,0);
  }
  SListPrint(plist);
}

image.png

//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
  if (*pphead==NULL)
  {
  return;
  }
  else if (*pphead == pos)
  {
  *pphead = NULL;
  }
  else
  {
  SLTNode* ret = *pphead;
  while (ret->next != pos)
  {
    ret = ret->next;
  }
  ret->next = pos->next;
  pos = NULL;
  free(pos);
  }
}
//任意位置修改接口测试
void TestList6()
{
  SLTNode* plist = NULL;
  SListPushBack(&plist, 1);
  SListPushBack(&plist, 2);
  SListPushBack(&plist, 3);
  SListPushBack(&plist, 4);
  SListPushBack(&plist, 5);
  SListPushBack(&plist, 6);
  SListPrint(plist);
  SLTNode* pos = SListFind(plist, 3);
  if (pos)
  {
  SListErase(&plist, pos);
  }
  SListPrint(plist);
}

image.png

目录
相关文章
|
4天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
11天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
10 0
|
11天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
12 1
|
11天前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
10 0
|
11天前
|
算法
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
数据结构和算法学习记录——线性表之单链表(下)-头插函数、尾删函数、头删函数、查找函数、pos位置插入&删除数据、单链表销毁
8 0
|
11天前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
10 0
|
C语言
C语言学生信息管理系统链表实现
C语言学生信息管理系统链表实现
149 0
C语言学生信息管理系统链表实现
史上最简单的C语言链表实现,没有之一
#include #include #include #define NR(x) (sizeof(x)/sizeof(x[0])) struct node { int data ; struct node *next ; }; void top_append_li...
967 0
|
4天前
|
算法 Unix Linux
C语言随机数的产生(rand、srand、time函数细节讲解)
C语言随机数的产生(rand、srand、time函数细节讲解)
|
2天前
|
安全 C语言
【C语言基础】:内存操作函数
【C语言基础】:内存操作函数