双向链表（C++实现）
2024-10-19 16:27:55
//////////////////////////////////////////////////////////////////////////////////////
/////// 这里建立两个类，一个节点类和一个List类，与单链表不同的是双向链表的节点要多一
////// 个前驱指针,相应的，双向链表函数实现要与单链表实现有所差异 typedef int DataType; //struct LinkNode //节点类（复合形态）
//{
// friend class SList;
//将SList设为友元，便于SList类可以访问节点类的私有成员
//public:
// LinkNode(const DataType x);
//private:
// DataType _data; //节点的数据
// LinkNode* _next; //指向该节点的下一个节点
// LinkNode* _prev; //指向该节点的前一个节点
//}; //直接用struct定义LinkNode类，因为struct的成员默认为公有数据成员，所以可直接访问
struct LinkNode //节点类(建议写法)
{
LinkNode(const DataType x);
DataType _data; //节点的数据
LinkNode* _next; //后继指针
LinkNode* _prev; //前驱指针
}; class List //链表类
{
public:
List(); //构造函数
List(const List& s); //拷贝构造
List &operator=(List& s); //赋值运算符的重载
~List(); public:
void Reverse();
void Swap(List& s);
void PrintSList(); //打印链表
void PushBack(const DataType& x); //在尾部插入一个节点
void Clear(); //链表置空
void PopBack();
void PushFront(DataType x); //头插
void PopFront(); //删除首节点
void Insert(LinkNode* pos, DataType x);//固定位置插入一个节点
void Erase(LinkNode* pos); //删除某一节点
LinkNode* Find(DataType x); //查找节点并返回这个节点的地址
int Amount(); //计算链表节点的数目
void Remove(DataType x); //查找某节点并删除 private:
LinkNode* _head; //指向头结点
LinkNode* _tail; //指向尾节点
};
List.h
#include<iostream>
using namespace std;
#include<assert.h>
#include"List.h" //节点类构造函数*
LinkNode::LinkNode(const DataType x)
:_data(x)
, _next(NULL)
, _prev(NULL)
{} //链表类*
List::List() //构造函数
: _head(NULL)
, _tail(NULL)
{} List::List(const List& s) //拷贝构造
: _head(NULL)
, _tail(NULL)
{
if (s._head == NULL)
{
return;
}
LinkNode* tmp = s._head;
while (tmp)
{
PushBack(tmp->_data);
tmp = tmp->_next;
} } //赋值运算符的重载（传统方法）
//SList & SList::operator=(const SList& s)
//{
// if (this != &s)
// {
// _head = NULL;
// _tail = NULL;
// LinkNode* tmp = s._head;
// do{
// PushBack(tmp->_data);
// tmp = tmp->_next;
// } while (tmp != s._head);
// }
// return *this;
//} //赋值运算符的重载（高效写法）*
/*void SList::Swap(SList& s)
{
swap(_head, s._head);
swap(_tail, s._tail); }
SList& SList::operator=(SList &s)
{
if (this != &s)
{
SList tmp(s);
Swap(tmp);
}
return *this;
}*/ List& List::operator=(List &s) //赋值运算符的重载再优化(推荐写法)
{
if (this != &s)
{
swap(_head, s._head);
swap(_tail, s._tail);
}
return *this;
}
List::~List() //析构
{
Clear();
} void List::Reverse() //链表逆置（利用头插新节点的方法）
{
if (_head == NULL || _head== _tail)
{
return;
}
int ret = Amount(); /* // 方法一（相当于用头插的方式重新建立链表）
_tail = new LinkNode(_head->_data);
LinkNode* begin = NULL;
LinkNode* tmp = _tail;
while (--ret)
{
LinkNode* del = _head;
_head = _head->_next;
delete del;
begin = new LinkNode(_head->_data);
begin->_next = tmp;
tmp->_prev = begin;
tmp = begin;
}
_head = begin;*/ ////// 方法二（只是交换对称位置节点的数据）**（高效）
LinkNode* begin = _head;
LinkNode* end = _tail;
while (ret)
{
if (end->_next == begin)
break;
ret /= ;
swap(begin->_data, end->_data);
begin = begin->_next;
end = end->_prev;
} /*// 方法三 交换前驱和后继指针
swap(_head, _tail);
LinkNode* cur = _head;
while (cur)
{
swap(cur->_prev,cur->_next);
cur = cur->_next;
}
*/ } //打印链表*
void List::PrintSList()
{
//头结点为空时，无需打印链表
if (_head == NULL)
{
cout << "This SList is Empty !" << endl;
return;
}
else
{
LinkNode* tmp = _head;
while (tmp)
{
cout << tmp->_data << "-->";
tmp = tmp->_next;
}
cout <<"NULL"<< endl;
}
} void List::PushBack(const DataType& x) //在尾部插入一个节点*
{
//如果链表为空，插入节点后只有一个节点，此时_head=_tail
if (_head == NULL)
{
_head = new LinkNode(x);
_tail = _head;
}
else
{
_tail->_next = new LinkNode(x);
_tail->_next->_prev=_tail;
_tail = _tail->_next;
}
} void List::Clear() //链表置空*
{
LinkNode* begin = _head;
while (begin != _tail)
{
_head = _head->_next;
delete begin;
begin = _head;
}
_head = NULL;
_tail = NULL;
} void List::PopBack() //尾删
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
}
else if (_head == _tail)
{
delete _head;
_head = NULL;
_tail = NULL;
}
else
{
LinkNode* cur = _head;
while (cur->_next != _tail)
{
cur = cur->_next;
}
delete _tail;
_tail = cur;
_tail->_prev = cur->_prev;
_tail->_next = NULL;
}
} void List::PushFront(DataType x) //头插*
{
if (_head == NULL)
{
PushBack(x);
}
else
{
LinkNode* tmp = _head;
_head = new LinkNode(x);
_head->_next = tmp;
tmp->_prev = _head;
}
} void List::PopFront() //删除首节点
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
return;
}
LinkNode* tmp = _head;
_head = _head->_next;
_head->_prev = NULL;
delete tmp;
} //固定位置插入一个节点（这个函数需和Find函数搭配使用）
//先用Find函数找到新节点需要插入的位置
//（将Find函数的返回值传给Insert函数的参数pos），再在pos节点后面插入新节点x
void List::Insert(LinkNode* pos, DataType x) //*
{
assert(pos);
if (pos == _tail)
{
PushBack(x);
}
else
{
LinkNode* tmp = new LinkNode(x);
tmp->_next = pos->_next;
pos->_next = tmp;
tmp->_next->_prev = tmp;
tmp->_prev = pos;
}
} //删除某一节点，同样，要先找到该节点并传参给Erase函数
void List::Erase(LinkNode* pos)
{
assert(pos);
if (pos == _tail)
{
PopBack();
}
else if (pos == _head)
{
PopFront();
}
else
{
pos->_prev->_next = pos->_next;
pos->_next->_prev = pos->_prev;
delete pos;
}
} //查找节点并返回这个节点的地址
LinkNode* List::Find(DataType x)
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
return NULL;
}
else
{
LinkNode* tmp = _head;
while (tmp != NULL)
{
if (tmp->_data == x)
{
return tmp;
}
tmp = tmp->_next;
}
return NULL;
}
} int List::Amount() //计算链表节点的数目
{
if (_head == NULL)
{
return ;
}
else
{
int count = ;
LinkNode* cur = _head;
while (cur != _tail)
{
count++;
cur = cur->_next;
}
return ++count;
}
} void List::Remove(DataType x) //查找某节点并删除
{
if (_head == NULL)
{
cout << "This SList is empty !" << endl;
}
else
{
LinkNode* tmp = Find(x);
if (tmp != NULL)
{
Erase(tmp);
}
}
}
List.cpp
#include"List.h"
#include<stdlib.h>
#include<iostream>
using namespace std; void Test1()
{
List list1;
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.PushBack();
list1.PrintSList(); /* List list2(list1);
list2.PrintSList();*/ List list2=list1;
list2.PrintSList();
//list2.PopBack();
//list2.Clear();
//list2.PushFront(0);
//list2.PopFront(); //////检验Find函数
////LinkNode* ret=list2.Find(4);
////if (ret != NULL)
////{
//// cout << "ret:" << ret << " " << ret->_data << endl;
////}
////else
////{
//// cout << "Not exit !" << endl;
////} /* int ret=list2.Amount();
cout << ret << endl;*/ //list2.Erase(list2.Find(5));
//list2.Insert(list2.Find(2), 0);
//list2.Remove(3);
list2.Reverse();
list2.PrintSList();
} int main()
{
Test1();
system("pause");
}
Test.cpp
最新文章
- 使用 python 收集获取 Linux 系统主机信息
- listview侧滑菜单swipemenulistview的简单使用
- MySQL 中隔离级别 RC 与 RR 的区别
- js图片轮播图
- JSON简介以及用法代码汇总
- 【python】type()、instance()
- MYSQL 二进制安装
- 树的广度优先遍历和深度优先遍历（递归非递归、Java实现）
- Selenium-Switch--切换浏览器tab/iframe/alart
- 2018-2019-2 20165234 《网络对抗技术》 Exp2 后门原理与实践
- js要怎么接收后端传的excel文件流？
- 第四讲 smart qq 获取联系人信息 ，分组 好友 群聊
- 玩转spring boot——结合docker
- zookeeper(1）初识zookeeper
- button 和 submit 的区别
- 2018年10月14日ICPC南京站参赛总结
- tensorflow-训练（train）/测试（test）
- Let the Balloon Rise map一个数组
- 【转】shell命令中>/dev/null 2>&1的实现原理
- jQuery实例化的优势，为什么要有实例化，到底实例化后在解决什么问题？