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

目录

• 一、单链表的定义
• 二、单链表的基本操作的实现
• 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++单链表的资料请关注我们其它相关文章！