C++数据结构之单链表的实现

更新时间：2022年6月1日 09:15 点击：228 作者：Kinght_123

一、单链表的定义

线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

单链表中结点类型的描述如下：

typedef struct  LNode{  // 定义单链表节点类型
  ElemType data;    // 数据域
  struct LNode* next; // 指针域
};LNode, *LinkList;

二、单链表的基本操作的实现

1.初始化

单链表的初始化操作就是构造一个空表。

具体代码：

// 初始化单链表
void InitList(LinkList &L) // 构造一个空的单链表L
{
  L=new LNode;  // 生成新节点作为头节点，用头指针L指向头节点
  L->next=NULL; // 头节点的指针域置空
}

2.取值

和顺序表不同，在链表中并没有存储在物理相邻的单元中。所以我们只能从链表的首节点出发，顺着链域next逐个节点向下访问。

具体代码：

// 单链表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
  LinkList p=L->next;int j=1; // 初始化，p指向首元节点，计数器j初值为1
  while(p&&j<i) // 顺着链域向后查找，直到p为空或p指向第i个元素
  {
    p=p->next;  // p指向下一个节点
    ++j;  // 计数器j相应加1
  }
  if(!p||j>i)return false;   // i值不合法
  e=p->data;  // 取第i个节点的数据域
  return true;
}

3.查找

从链表的首元节点出发，依次将节点值和给定值e进行比较，返回查找结果。

具体代码：

//单链表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
  //在单链表中查找第一个数据为e的结点
  p = L->next;//p指向首元结点
  while (p && p->data != e)
  {
    p = p->next;
  }
  if (p)
  {
    return true;
  }
  return false;
}

4.插入

// 单链表的插入
bool ListInsert(LinkList &L, int i, ElemType e)
{

  LinkList p = L;
  LNode* s;
  int j = 0;
  while (p && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!p || i < 1)//i大于表长+1或小于1，插入位置不合法
  {
    return false;
  }
  s = new LNode;
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

5.删除

//单链表的删除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
  //将单链表的第i个结点删除
  LinkList p = L;
  LNode* q;
  int j = 0;
  while (p->next && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!(p->next) || i < 1)//i大于表长或小于1，删除位置不合法
  {
    return false;
  }
  q = p->next;//临时保存被删结点的地址以备释放
  p->next = q->next;
  e = q->data;//保存被删结点的数据
  delete q;//释放被删结点的空间
  return true;
}

三、完整代码

#include<iostream>
using namespace std;
#define ElemType int

typedef struct  LNode{  // 定义单链表节点类型
  ElemType data;    // 数据域
  struct LNode* next; // 指针域
}LNode,*LinkList;


// 初始化单链表
void InitList(LinkList &L) // 构造一个空的单链表L
{
  L=new LNode;  // 生成新节点作为头节点，用头指针L指向头节点
  L->next=NULL; // 头节点的指针域置空
}


//单链表的创建
void CreateList_H(LinkList& L)//前插法创建单链表
{
  //创建一个长度为n的单链表L,逆序位插入
  int n;
  LNode *p;
  cout << "请输入创建的单链表长度：" << endl;
  cin >> n;
  for (int i = 0; i < n; i++) {
    p = new LNode;
    cout << "请输入插入的第" << i + 1 << "个数据值" << endl;
    cin >> p->data;
    p->next = L->next;
    L->next = p;
  }
}


// 单链表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
  LinkList p=L->next;int j=1; // 初始化，p指向首元节点，计数器j初值为1
  while(p&&j<i) // 顺着链域向后查找，直到p为空或p指向第i个元素
  {
    p=p->next;  // p指向下一个节点
    ++j;  // 计数器j相应加1
  }
  if(!p||j>i)return false;   // i值不合法
  e=p->data;  // 取第i个节点的数据域
  return true;
}



//单链表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
  //在单链表中查找第一个数据为e的结点
  p = L->next;//p指向首元结点
  while (p && p->data != e)
  {
    p = p->next;
  }
  if (p)
  {
    return true;
  }
  return false;
}


// 单链表的插入
bool ListInsert(LinkList &L, int i, ElemType e)
{

  LinkList p = L;
  LNode* s;
  int j = 0;
  while (p && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!p || i < 1)//i大于表长+1或小于1，插入位置不合法
  {
    return false;
  }
  s = new LNode;
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}


//单链表的删除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
  //将单链表的第i个结点删除
  LinkList p = L;
  LNode* q;
  int j = 0;
  while (p->next && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!(p->next) || i < 1)//i大于表长或小于1，删除位置不合法
  {
    return false;
  }
  q = p->next;//临时保存被删结点的地址以备释放
  p->next = q->next;
  e = q->data;//保存被删结点的数据
  delete q;//释放被删结点的空间
  return true;
}

四、测试一下代码

#include<iostream>
using namespace std;
#define ElemType int

//************************单链表的存储结构********************
typedef struct LNode
{
  ElemType data;//结点的数据域
  struct LNode* next;//结点的指针域
}LNode, * LinkList;//LinkList为指向结构体LNode的指针类型

//***********************单链表的基本操作函数******************

//单链表的初始化
void InitList(LinkList& L)
{
  //构造一个空的单链表
  L = new LNode;
  L->next = NULL;
}
//单链表的创建
void CreateList_H(LinkList& L)//前插法创建单链表
{
  //创建一个长度为n的单链表L,逆序位插入
  int n;
  LNode* p;
  cout << "请输入创建的单链表长度：" << endl;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    p = new LNode;
    cout << "请输入插入的第" << i + 1 << "个数据值" << endl;
    cin >> p->data;
    p->next = L->next;
    L->next = p;
  }
}

void CreateList_R(LinkList& L)//后插法创建单链表
{
  //创建一个长度为n的单链表L,正序位插入
  int n;
  LNode* p, * r;
  r = L;//尾指针r指向头结点
  cout << "请输入创建的单链表长度：" << endl;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    p = new LNode;
    cout << "请输入插入的第" << i + 1 << "个数据值" << endl;
    cin >> p->data;
    p->next = NULL;
    r->next = p;
    r = p;
  }
}

//单链表的插入
bool ListInsert(LinkList& L, int i, ElemType e)
{
  //在带头结点的单链表L的第i个结点前插入新结点
  LinkList p = L;
  LNode* s;
  int j = 0;
  while (p && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!p || i < 1)//i大于表长+1或小于1，插入位置不合法
  {
    return false;
  }
  s = new LNode;
  s->data = e;
  s->next = p->next;
  p->next = s;
  return true;
}

//单链表的删除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
  //将单链表的第i个结点删除
  LinkList p = L;
  LNode* q;
  int j = 0;
  while (p->next && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!(p->next) || i < 1)//i大于表长或小于1，删除位置不合法
  {
    return false;
  }
  q = p->next;//临时保存被删结点的地址以备释放
  p->next = q->next;
  e = q->data;//保存被删结点的数据
  delete q;//释放被删结点的空间
  return true;
}

//单链表的取值
bool GetElem(LinkList L, int i, ElemType& e)
{
  //获取单链表中第i个结点的数据
  LinkList p = L;
  int j = 0;
  while (p->next && j < i - 1)//p指向第i-1个结点
  {
    p = p->next;
    j++;
  }
  if (!(p->next) || i < 1)//i大于表长或小于1，第i个结点不存在
  {
    return false;
  }
  e = p->next->data;//获取第i个结点的数据
  return true;
}

//单链表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
  //在单链表中查找第一个数据为e的结点
  p = L->next;//p指向首元结点
  while (p && p->data != e)
  {
    p = p->next;
  }
  if (p)
  {
    return true;
  }
  return false;
}

//*********************************单链表的基本功能函数******************************

//1、插入
void ListInsert(LinkList& L)
{

  ElemType e;
  int i;
  bool flag;
  cout << "请输入要插入的数据：" << endl;
  cin >> e;
  cout << "请输入要插入的位置：" << endl;
  cin >> i;
  flag = ListInsert(L, i, e);
  if (flag)
    cout << "插入成功!" << endl;
  else
    cout << "位置不对，插入失败！" << endl;
}

//2、删除
void ListDelete(LinkList& L)
{
  ElemType e;
  int i;
  bool flag;
  cout << "请输入要删除数据的位置：" << endl;
  cin >> i;
  flag = ListDelete(L, i, e);
  if (flag)
    cout << "删除成功，删除的数据为：" << e << endl;
  else
    cout << "位置不对，删除失败！" << endl;
}

//3、取值
void GetElem(LinkList L)
{
  ElemType e;
  int i;
  bool flag;
  cout << "请输入要获取数据的位置：" << endl;
  cin >> i;
  flag = GetElem(L, i, e);
  if (flag)
    cout << "获取的数据为：" << e << endl;
  else
    cout << "位置不对，获取数据失败！" << endl;
}

//4、查找
void LocateElem(LinkList L)
{
  ElemType e;
  LNode* p = NULL;
  bool flag;
  cout << "请输入要查找的数据：" << endl;
  cin >> e;
  flag = LocateElem(L, p, e);
  if (flag)
    cout << "查找成功，该数据的地址为：" << p << endl;
  else
    cout << "查找失败！" << endl;
}

//5、判空
void ListEmpty(LinkList L)
{
  if (L->next)
    cout << "链表不为空！" << endl;
  else
    cout << "链表为空！" << endl;
}

//6、求长
void ListLength(LinkList L)
{
  LinkList p = L->next;//p指向第一个结点
  int i = 0;
  while (p)//遍历单链表，统计结点数
  {
    i++;
    p = p->next;
  }
  cout << "链表的长度为：" << i << endl;
}

//7、清空
void ClearList(LinkList& L)
{
  LNode* p, * q;
  p = L->next;
  while (p)//从首元结点开始，依次删除
  {
    q = p->next;
    delete p;
    p = q;
  }
  L->next = NULL;//头结点指针域置空
}

//8、销毁
void DestroyList(LinkList& L)
{
  LNode* p;
  while (L)//从头结点开始依次删除
  {
    p = L;
    L = L->next;
    delete p;
  }
}

//9、打印
void PrintList(LinkList L)
{
  LinkList p = L->next;//p指向第一个结点
  int i = 0;
  while (p)//遍历单链表
  {
    i++;
    cout << "链表第" << i << "个数据为：" << p->data << endl;
    p = p->next;
  }
}

//菜单
void menu()
{
  cout << "***************************************************************************" << endl;
  cout << "***********************************1、插入*********************************" << endl;
  cout << "***********************************2、删除*********************************" << endl;
  cout << "***********************************3、取值*********************************" << endl;
  cout << "***********************************4、查找*********************************" << endl;
  cout << "***********************************5、判空*********************************" << endl;
  cout << "***********************************6、求长*********************************" << endl;
  cout << "***********************************7、清空*********************************" << endl;
  cout << "***********************************8、销毁*********************************" << endl;
  cout << "***********************************9、打印*********************************" << endl;
  cout << "***********************************0、退出*********************************" << endl;
  cout << "***************************************************************************" << endl;
}

int main()
{
  LinkList L;
  InitList(L);
  int select;
  cout << "请先创建单链表：1、前插法！  2、后插法！" << endl;
  cin >> select;
  switch (select)
  {
  case 1://插入
    CreateList_H(L);
    system("pause");//按任意键继续
    break;
  case 2://删除
    CreateList_R(L);
    system("pause");
    break;
  default:
    cout << "输入有误,创建失败！" << endl;
    system("pause");
    break;
  }
  while (1)
  {
    system("CLS");//清屏操作
    menu();
    cout << "请输入菜单序号：" << endl;
    cin >> select;
    switch (select)
    {
    case 1://插入
      ListInsert(L);
      system("pause");//按任意键继续
      break;
    case 2://删除
      ListDelete(L);
      system("pause");
      break;
    case 3://取值
      GetElem(L);
      system("pause");
      break;
    case 4://查找
      LocateElem(L);
      system("pause");
      break;
    case 5://判断链表是否为空
      ListEmpty(L);
      system("pause");
      break;
    case 6://求单链表的长度
      ListLength(L);
      system("pause");
      break;
    case 7://清空
      ClearList(L);
      system("pause");
      break;
    case 8://销毁
      DestroyList(L);
      system("pause");
      return 0;
      break;
    case 9://打印
      PrintList(L);
      system("pause");
      break;
    case 0:
      cout << "欢迎下次使用!" << endl;//退出
      system("pause");
      return 0;
      break;
    default:
      cout << "菜单序号输入有误！" << endl;
      system("pause");
      break;
    }
  }
  system("pause");
  return 0;
}

以上就是C++数据结构之单链表的实现的详细内容，更多关于C++单链表的资料请关注猪先飞其它相关文章！

原文出处：https://blog.csdn.net/Kinght_123/article/details/125065824

[!--infotagslink--]

上一篇: 超级详细讲解C++中的多态

下一篇: C++和OpenCV实现图像字符化效果

C++ STL标准库std::vector的使用详解
vector是表示可以改变大小的数组的序列容器，本文主要介绍了C++STL标准库std::vector的使用详解，文中通过示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2022-03-06
C++中取余运算的实现
这篇文章主要介绍了C++中取余运算的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
详解C++ string常用截取字符串方法
这篇文章主要介绍了C++ string常用截取字符串方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
C++调用C#的DLL程序实现方法
本文通过例子，讲述了C++调用C#的DLL程序的方法，作出了以下总结，下面就让我们一起来学习吧。...2020-06-25
C++中四种加密算法之AES源代码
本篇文章主要介绍了C++中四种加密算法之AES源代码，小编觉得挺不错的，现在分享给大家，也给大家做个参考。...2020-04-25
C++ 整数拆分方法详解
整数拆分，指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解，非常不错，感兴趣的朋友一起学习吧...2020-04-25
C++中 Sort函数详细解析
这篇文章主要介绍了C++中Sort函数详细解析，sort函数是algorithm库下的一个函数，sort函数是不稳定的，即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
C#数据结构之队列(Quene)实例详解
这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
C++万能库头文件在vs中的安装步骤(图文)
这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文)，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
详解C++ bitset用法
这篇文章主要介绍了C++ bitset用法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
浅谈C++中的string 类型占几个字节
本篇文章小编并不是为大家讲解string类型的用法，而是讲解我个人比较好奇的问题，就是string 类型占几个字节...2020-04-25
C++ Eigen库计算矩阵特征值及特征向量
这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2020-04-25
VSCode C++多文件编译的简单使用方法
这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-03-29
C++ pair的用法实例详解
这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
C++中的循环引用
虽然C++11引入了智能指针的，但是开发人员在与内存的斗争问题上并没有解放，如果我门实用不当仍然有内存泄漏问题，其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用，一起看看吧...2020-04-25
C++随机点名生成器实例代码（老师们的福音！）
这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
C++如何删除map容器中指定值的元素详解
map容器是C++ STL中的重要一员，删除map容器中value为指定元素的问题是我们经常与遇到的一个问题，下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料，需要的朋友可以参考借鉴，下面来一起看看吧。...2020-04-25
C++ 约瑟夫环问题案例详解
这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
C++中cin的用法详细
这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
基于C++中常见编译错误的总结详解
本篇文章是对C++中的常见编译错误进行了详细的分析介绍，需要的朋友参考下...2020-04-25

C++数据结构之单链表的实现

目录

一、单链表的定义

二、单链表的基本操作的实现

1.初始化

2.取值

3.查找

4.插入

5.删除

三、完整代码

四、测试一下代码

相关文章

阁下可能感兴趣的内容

推荐阅读