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

2024-04-02 19:04:59 693人浏览独家记忆

摘要

目录一、单链表的定义二、单链表的基本操作的实现1.初始化2.取值3.查找4.插入5.删除三、完整代码四、测试一下代码一、单链表的定义线性表的链式存储又称为单链表，它是指通过一组任意

一、单链表的定义

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

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

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++单链表的资料请关注编程网其它相关文章！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C++数据结构之单链表的实现

本文链接: https://www.lsjlt.com/news/150278.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

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

目录一、单链表的定义二、单链表的基本操作的实现1.初始化2.取值3.查找4.插入5.删除三、完整代码四、测试一下代码一、单链表的定义线性表的链式存储又称为单链表，它是指通过一组任意...

99+

2024-04-02
C++数据结构之单链表

目录单链表结构的定义单链表打印动态申请一个结点单链表尾插单链表尾删单链表头插单链表头删求单链表长度单链表查找单链表在pos位置插入单链表在pos后面位置插入单链表删除pos位置单链表...

99+

2024-04-02
C++数据结构之单链表如何实现

这篇文章主要介绍了C++数据结构之单链表如何实现的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C++数据结构之单链表如何实现文章都会有所收获，下面我们一起来看看吧。一、单链表的定义线性表的链式存储又称为单链表，...

99+

2023-06-30
C语言数据结构之单链表的实现

目录一.为什么使用链表二.链表的概念三.链表的实现3.1 创建链表前须知3.2 定义结构体3.3 申请一个节点3.4 链表的头插3.5 链表的尾插3.6 链表的尾删3.7 链表的头删...

99+

2024-04-02
C语言数据结构之单链表怎么实现

本文小编为大家详细介绍“C语言数据结构之单链表怎么实现”，内容详细，步骤清晰，细节处理妥当，希望这篇“C语言数据结构之单链表怎么实现”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。一.为什么使用链表在学习链表以前，...

99+

2023-07-02
Java数据结构之链表实现（单向、双向链表及链表反转）

前言之前学习的顺序表查询非常快，时间复杂度为O(1)，但是增删改效率非常低，因为每一次增删改都会元素的移动。可以使用另一种存储方式-链式存储结构。链表是一种物理存储单元上非连续、...

99+

2024-04-02
C语言数据结构之顺序表和单链表

一、顺序表的创建、删除和插入 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> struct sqlist { ...

99+

2024-04-02
C++数据结构之双向链表怎么实现

这篇“C++数据结构之双向链表怎么实现”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C++数据结构之双向链表怎么实现”文章吧...

99+

2023-06-30
用Python实现数据结构之链表

链表与栈，队列不一样，它是由一个个节点构成的，每个节点存储着本身的一些信息，也存储着其他一个或多个节点的引用，可以从一个节点找到其他的节点，节点与节点之间就像是有链连在一起一样，这种数据结构就叫做链表单向链表是链表的最简单形式，链表...

99+

2023-01-30

数据结构链表 Python
C++数据结构之双向链表

本文实例为大家分享了C++数据结构之双向链表的具体代码，供大家参考，具体内容如下 #include <iostream> using std::cout; using ...

99+

2024-04-02
C语言数据结构与算法之单链表

目录基本概念读取数据元素获取第i个结点的数据元素插入数据元素初始化链表打印链表顺序表查空顺序表的删除删除第i个结点及其数据元素情况1：当删除的是第一个元素情况2：除第一个结点外完...

99+

2024-04-02
C++数据结构之链表详解

目录前言一、删除链表中给定值为key的节点二、反转链表三、返回链表的中间节点四、删除链表的倒数第K个节点五、分割链表六、合并两个有序链表七、删除有序链表中重复节点八、环形链表九、相交...

99+

2024-04-02
C语言数据结构之单链表与双链表的增删改查操作实现

目录前言单链表的增删改查定义结构体以及初始化增加结点删除结点查找修改结点移除结点最终效果双链表的基本操作初始化建表遍历双链表指定位置插入结点指定位置删除结点查找结点位置最终效果结语前...

99+

2024-04-02
Java数据结构之单链表详解

目录一、图示二、链表的概念及结构三、单链表的实现四、完整代码的展示一、图示二、链表的概念及结构链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的...

99+

2024-04-02
C语言数据结构实例讲解单链表的实现

目录1、单链表2、单链表的实现头文件函数的实现（1）打印链表（2）动态申请结点（3）尾插（4）头插（5）尾删（6）头删（7）查找（8）在pos之前插入（9）删除pos（10）在pos...

99+

2024-04-02
C语言数据结构之单链表操作详解

目录1、插入操作2、删除操作3、查找操作4、修改操作5、完整代码1、插入操作（1）创建一个新的要插入的结点（2）将新结点的 next 指针指向插入位置后的结点（3）将插入位置前...

99+

2024-04-02
Java数据结构之双向链表的实现

目录1 双向链表1.1 双向链表介绍1.2 双向链表实现思路2 双向链表实现完整代码2.1 节点类 Student.java2.2 双向链表实现类 StudentDoubleLink...

99+

2022-11-13

Java 数据结构双向链表 Java 双向链表
C语言数据结构之单链表存储详解

目录1、定义一个链表结点2、初始化单链表3、输出链表数据4、完整代码如果说，顺序表的所占用的内存空间是连续的，那么链表则是随机分配的不连续的，那么为了使随机分散的内存空间串联在一起形...

99+

2024-04-02
数据结构TypeScript之链表实现详解

目录链表结构特点面向对象方法封装链表构造函数基本单元：链表节点主体：链表查找节点增加节点删除节点链表结构特点链表是线性表的其中一种，用于存储有固定顺序的元素。而元素之间会通过&r...

99+

2023-01-30

TypeScript数据结构链表 TypeScript数据结构
Java数据结构之单链表是什么

这篇文章给大家分享的是有关Java数据结构之单链表是什么的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。一、图示二、链表的概念及结构链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接...

99+

2023-06-15