这篇文章主要介绍了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++数据结构之单链表如何实现”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注编程网行业资讯频道。
