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