数据结构--双链表 C++(模板类实现)
作者:
AmbitionX
,
2022-05-01 19:52:30
,
所有人可见
,
阅读 232
#include <iostream>
using namespace std;
template <typename DataType>
struct DulNode
{
DataType data;
DulNode<DataType> * prior, * next;
}; // 注意 : new DulNode<DataType> 是定义一个结点 DulNode<DataType> * p 是定义一个叫做p的指针
template <typename DataType>
class DulLinkList
{
public:
DulLinkList(); // 初始化一个带有头结点的双链表
DulLinkList(DataType a[], int n); //建n个元素单链表:1.头插法 2.尾差法
~DulLinkList(); // 析构函数 链表的销毁
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:
DulNode<DataType>* head;
};
// 初始化 与单链表同
template <typename DataType>
DulLinkList<DataType>:: DulLinkList()
{
head = new DulNode<DataType>;
head->next = nullptr;
}
// 头插 (依次插入到头结点的后面 逆序插入)
// template <typename DataType>
// DulLinkList<DataType>:: DulLinkList(int a[], int n)
// {
// head = new DulNode<DataType>;
// head->next = nullptr;
// for (int i = 0; i < n; i++)
// {
// DulNode<DataType> * p = nullptr;
// s = new Node<DataType>;
// s->data = a[i];
// s->next = head->next;
// head->next = s;
// }
// }
// 尾插 (依次插入到尾结点的后面)
template <typename DataType>
DulLinkList<DataType>:: DulLinkList(DataType a[], int n)
{
DulNode<DataType> * r, *s;
head = new DulNode<DataType>; // 生成头结点
r = head; // 尾指针初始化
for (int i = 0; i < n; i++)
{
s = new DulNode<DataType>;
s->data = a[i];
r->next = s;
r = s;
}
r->next = NULL;
}
// 析构函数 双链表的销毁(与单链表同)
template <typename DataType>
DulLinkList<DataType>:: ~DulLinkList()
{
DulNode<DataType> *p; // 工具指针 用来保存结点 方便删除
while (head != NULL)
{
p = head;
head = head->next;
delete(p);
}
}
// 双链表的长度 (与单链表同)
template <typename DataType>
int DulLinkList<DataType>:: Length()
{
DulNode<DataType> *p = head->next; //初始化工作指针
int count = 1; // 初始是从第一个有值的结点开始的
while (p != nullptr)
{
p = p->next;
count ++;
}
return count;
}
// 按位查找 查找第i个节点的元素值 (与单链表同)
template <typename DataType>
DataType DulLinkList<DataType>:: Get(int i)
{
DulNode<DataType> *p = head->next;
int count = 1;
while (p != nullptr && count < i)
{
p = p->next;
count ++;
}
if (p == nullptr) throw "查找失败";
else return p;
}
// 按值查找 查找值为x的元素序号(与单链表同)
template <typename DataType>
int DulLinkList<DataType>:: Locate(DataType x)
{
DulNode<DataType> *p = head->next;
int count = 1;
while (p != nullptr)
{
if (p->data == x) return count;
p = p->next;
count ++;
}
return 0; // 没找到的返回
}
// 插入操作 第i个位置上插入值位x的结点 与单链表不同
template <typename DataType>
void DulLinkList<DataType>:: Insert(int i, DataType x)
{
DulNode<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 DulNode<DataType>;
s->data = x;
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
}
}
// 删除操作 删除第i个结点 与单链表不同
template <typename DataType>
DataType DulLinkList<DataType>:: Delete(int i)
{
DataType x;
DulNode<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 || p->prior == nullptr) throw "删除位置错误";
else
{
q = p->next;
x = q->data;
q->prior->next = q->next;
q->next->prior = q->prior;
delete q;
return x;
}
}
// 判断线性表是否为空 (与单链表同)
template <typename DataType>
void DulLinkList<DataType>:: Empty()
{
if (head->next == NULL) cout << "为空" << endl;
else cout << "不为空" << endl;
}
// 遍历操作,按序号依次输出各元素 (与单链表同)
template <typename DataType>
void DulLinkList<DataType>:: PrintList()
{
DulNode<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};
DulLinkList<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(3); //删除元素2
}
catch (char *s)
{
cout<<s<<endl;
}
cout<<"执行删除操作后数据为:"<<endl;
L.PrintList( ); //显示链表中所有元素
return 0;
}