数据结构--单链表C++(模板类实现)
作者:
AmbitionX
,
2022-04-28 20:51:38
,
所有人可见
,
阅读 282
C++
#include <iostream>
using namespace std;
template <typename DataType>
struct Node
{
DataType data; // 数据域
Node<DataType>* next; // 指针域
};
template <typename DataType>
class LinkList
{
public:
LinkList(); // 初始化一个带有头结点的单链表
LinkList(DataType a[], int n); //建n个元素单链表:1.头插法建单2.尾差法建单链表
~LinkList(); // 析构函数 链表的销毁
int Length(); // 链表的长度
DataType Get(int i); // 按位查找 查找第i个节点的元素值
int Locate(DataType x); // 按值查找 查找值为x的元素序号
void Insert(int i, DataType x); // 插入操作 第i个位置上插入值位x的结点
DataType Delete(int i); // 删除操作 删除第i个结点
void Empty(); // 判断线性表是否为空
void PrintList(); // 遍历操作,按序号依次输出各元素
private:
Node<DataType>* head;
};
// 初始化
template <typename DataType>
LinkList<DataType>:: LinkList()
{
head = new Node<DataType>; // 生成头结点
head->next = nullptr;
}
// 建n个元素的单链表
// 1.头插法建单链表
// template <typename DataType>
// LinkList<DataType>:: LinkList(DataType a[], int n)
// {
// head = new Node<DataType>;
// head->next = nullptr;
// for (int i = 0; i < n; i++)
// {
// Node<DataType> *s = nullptr;
// s = new Node<DataType>;
// s->data = a[i];
// s->next = head->next;
// head->next = s;
// }
// }
// 2.尾差法建单链表
template <typename DataType>
LinkList<DataType> :: LinkList(DataType a[ ], int n)
{
Node<DataType> *r, *s;
head = new Node<DataType>; //生成头结点
r = head; //尾指针初始化
for (int i = 0; i < n; i++)
{
s = new Node<DataType>; s->data = a[i]; //为每个数组元素建立一个结点
r->next = s; r = s; //将结点s插入到终端结点之后
}
r->next = NULL; //单链表建立完毕,将终端结点的指针域置空
}
// 析构函数 链表的销毁
template <typename DataType>
LinkList<DataType> :: ~LinkList( )
{
Node<DataType> *q;
while (head != NULL) //释放单链表的每一个结点的存储空间
{
q = head; //暂存被释放结点
head = head->next; // first指向被释放结点的下一个结点
delete q;
}
}
// 链表的长度
template <typename DataType>
int LinkList<DataType>:: Length()
{
Node<DataType> *p = head->next; //初始化工作指针
int count = 1;
while (p != nullptr)
{
p = p->next;
count ++;
}
return count;
}
// 按位查找
template <typename DataType>
DataType LinkList<DataType>:: Get(int i)
{
Node<DataType> *p = head->next;
int count = 1;
while (p != nullptr && count < i)
{
p = p->next;
count ++;
}
if (p == nullptr) throw "查找位置错误";
else return p;
}
// 按值查找
template <typename DataType>
int LinkList<DataType>:: Locate(DataType x)
{
Node<DataType> *p = head->next;
int count = 1;
while (p != nullptr)
{
if (p->data == x) return count;
p = p->next;
count ++;
}
return 0;
}
// 插入操作
template <typename DataType>
void LinkList<DataType>:: Insert(int i, DataType x)
{
Node<DataType> *p = head, *s;
int count = 0; //工作指针p应指向头结点
while (p != NULL && count < i - 1) //查找第i - 1个结点
{
p = p->next; //工作指针p后移
count++;
}
if (p == nullptr) throw "插入位置错误";
else
{
s = new Node<DataType>;
s->data = x;
s->next = p->next;
p->next = s;
}
}
// 删除操作
template <typename DataType>
DataType LinkList<DataType>:: Delete(int i)
{
DataType x;
Node<DataType> *p, *q;
int count = 0;
p = head; //注意工作指针p要指向头结点
while (p != NULL && count < i - 1) //查找第i-1个结点
{
p = p->next;
count++;
}
if (p == nullptr || p->next == nullptr) throw "删除位置错误";
else
{
q = p->next;
x = q->data;
p->next = q->next;
delete q;
return x;
}
}
// 判断线性表是否为空
template <typename DataType>
void LinkList<DataType>:: Empty()
{
if (head->next == nullptr) cout << "为空" << endl;
else cout << "不为空" << endl;
}
// 遍历操作
template <typename DataType>
void LinkList<DataType>:: PrintList()
{
Node<DataType> *p = head->next;
while (p != nullptr)
{
cout << p->data<<"\t";
p = p->next;
}
cout << endl;
}
int main()
{
int r[5]={1, 2, 3, 4, 5};
LinkList<int> L(r, 5);
//判空操作
L.Empty();
cout<<"执行插入操作前数据为:"<<endl;
// 打印遍历操作
L.PrintList( ); //显示链表中所有元素
try
{
L.Insert(2, 3);
}
catch (char *s)
{
cout<<s<<endl;
}
cout<<"执行插入操作后数据为:"<<endl;
L.PrintList( ); //显示链表中所有元素
cout<<"值为5的元素位置为:";
// 按值查找操作
cout<<L.Locate(5)<<endl; //查找元素5,并返回在单链表中位置
cout<<"执行删除操作前数据为:"<<endl;
L.PrintList( ); //显示链表中所有元素
// 删除操作
try
{
L.Delete(1); //删除元素4
}
catch (char *s)
{
cout<<s<<endl;
}
cout<<"执行删除操作后数据为:"<<endl;
L.PrintList( ); //显示链表中所有元素
return 0;
}