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

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

一、单链表的定义

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

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

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 inttypedef 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//单链表的初始化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++数据结构之单链表如何实现”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注编程网其他教程频道。