看下面的图,就是我今天要给大家分享有结构——带头双向循环链表。这里的头是不存放任何数据的,就是一个哨兵卫的头结点。
用代码来表示每一个节点就是这样的:
- 数据域和指针域
- 两个指针,一个指向前驱结点,一个指向后继结点
- 给定两个构造函数,有参和无参,分别对结点的指针域和数据域进行初始化
template <class DateType>
struct LinkNode
{
//数据域
DateType data;
//两个指针
LinkNode<DateType>* prev;
LinkNode<DateType>* next;
LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next){}
LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next){}
};
带头双向链表的接口实现
要实现的接口
LinkList();//构造函数,初始化头节点
LinkList(const LinkList<DateType>& list2);//拷贝构造,进行两个链表的拷贝
~LinkList();//析构函数,用来清除链表,释放结点空间
int Length();//求双向循环链表的长度
void CreateList(int n);//常见n个结点的双向循环链表
bool GetElem(int pos,DateType& data);//得到pos位置结点的元素值
LinkNode<DateType>* Locate(int i ,int back_pos);//定位元素,当back_pos=0的时候,从头节点向前查询第i个元素,back_pos!=0的时候,从头节点后查询第i个元素
bool Insert(int pos, const DateType& data, int back_pos);//在pos的位置插入元素,当back_pos!=0的时候,在pos位置后插入元素,当back_pos=0的时候,在pos位置前插入元素
void PrintList(int sign);//输出双向循环链表所有结点的元素值,当sign!=0时,正序打印元素值,当sign=0时,逆序打印
bool Delete(int pos, DateType& data,int back_pos);//删除pos位置的结点
双向链表的小框架
template<class DateType>
class LinkList
{
public:
private:
LinkNode<DateType>* head;//头节点
};
初始化双向链表
在初始化双链表的过程中,我们要开好一个头节点,作为哨兵卫的头节点,然后返回这个节点的指针,接口外面只要用一个节点指针接受这个返回值就好了,具体实现如下:
//构造函数,初始化一个循环双链表
LinkList()
{
head = new LinkNode<DateType>;
if (head == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
head->data = 0;
head->next = head;
head->prev = head;
}
拷贝构造
在拷贝构造中,要注意一件事情,就是最后一个结点的next需要指向头节点,头节点的prev需要指向最后一个结点,形成双向循环链表
//拷贝构造
LinkList(const LinkList<DateType>& list2)
{
LinkNode<DateType>* p = list2.head->next;
if (p == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
head = new LinkNode<DateType>;
LinkNode<DateType>* h = head;
while (p!=list2.head)
{
LinkNode<DateType>* t = new LinkNode<DateType>;
h->next = t;
t->prev = h;
t->data = p->data;
p = p->next;
h = h->next;
}
h->next = this->head;
this->head->prev = h;
}
定位结点
因为后面的在指定插入删除元素,需要定位pos位置结点的地址,所以这里旧封装一个函数,直接获取pos位置结点的地址
//定位元素,back_pos=0时从头节点向前查第i个元素,d!=0时,从头节点向后找第i个元素
LinkNode<DateType>* Locate(int i ,int back_pos)
{
if (head->next == head || i == 0) {
return head;
}
int j = 0;
LinkNode<DateType>* p = head;
//从头节点往后找第i个元素
if (back_pos)
{
while (p->next != head && j != i)
{
p = p->next;
++j;
}
if (p->next == head && j != i)
{
return NULL;
}
else
{
return p;
}
}//向前找
else
{
while (p->prev != head && j != i)
{
p = p->prev;
++j;
}
if (p->prev == head && j != i)
return NULL;
else
return p;
}
}
创建双向链表
//创建双循环链表
void CreateList(int n)
{
DateType* nodetemp = new DateType[n];
for (rsize_t i = 0; i < n; i++)
{
cout << "Enter the element: " << endl;
cin >> nodetemp[i];
Insert(i, nodetemp[i], 1);
}
delete[] nodetemp;
}
打印双向循环链表
因为是双向循环链表,可以很简单的实现正序打印和逆序打印,所以这里用一个标志sign,来指定正序还是逆序打印链表元素
//输出双循环链表所有结点的元素值,分为正序打印和逆序打印
void PrintList(int sign)
{
//正序打印
if (sign)
{
cout << "head " ;
LinkNode<DateType>* p = head;
while (p->next != head)
{
p = p->next;
cout << "-> " << p->data;
}
cout << "->over" << endl;
}//逆序打印
else
{
cout << "head " << endl;
LinkNode<DateType>* p = head;
while (p->prev != head)
{
p = p->prev;
cout << "-> " << p->data;
}
cout << "->over" << endl;
}
}
指定位置插入结点
任意位置插入首先要开辟一个节点,然后就是按照所个位置,改变指针的指向来把这个节点连接上去,看具体代码实现如下:
//在pos的位置插入元素
bool Insert(int pos, const DateType& data, int back_pos)
{
LinkNode<DateType>* p = Locate(pos, back_pos);
if (!p)
return false;
LinkNode<DateType>* new_node = new LinkNode<DateType>(data);
if (NULL == new_node)
{
cout << "内存分配失败" << endl;
exit(-1);
}
//p结点后插入
if (back_pos)
{
p->next->prev = new_node;
new_node->prev = p;
new_node->next = p->next;
p->next = new_node;
}//p结点前插入
else
{
p->prev->next = new_node;
new_node->next = p;
new_node->prev = p->prev;
p->prev = new_node;
}return true;
}
指定位置删除结点
删除就要考虑链表是否为空,防止删除头节点
//删除pos位置的结点
bool Delete(int pos, DateType& data,int back_pos)
{
LinkNode<DateType>* p = Locate(pos, back_pos);
if (!p)
{
return false;
}
if (p == head )
{
cout << "请不要删除头节点" << endl;
return false;
}
data = p->data;
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
return true;
}
获取链表长度
int Length()
{
LinkNode<DateType>* p = head;
int i = 0;
while (p->next != head)
{
++i;
p = p->next;
}
return i;
}
销毁链表
在析构函数中实现链表的销毁
//析构函数
~LinkList()
{
LinkNode<DateType>* p, * q = head->next;
while (q != head)
{
p = q;
q = q->next;
delete p;
}
}
整体代码以及测试
#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
using namespace std; //标准命名空间
/*
双向循环链表
*/
template <class DateType>
struct LinkNode
{
//数据域
DateType data;
//两个指针
LinkNode<DateType>* prev;
LinkNode<DateType>* next;
LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next)
{}
LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next)
{}
};
template<class DateType>
class LinkList
{
public:
//构造函数,初始化一个循环双链表
LinkList()
{
head = new LinkNode<DateType>;
if (head == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
head->data = 0;
head->next = head;
head->prev = head;
}
//拷贝构造
LinkList(const LinkList<DateType>& list2)
{
LinkNode<DateType>* p = list2.head->next;
if (p == NULL)
{
cout << "内存分配失败" << endl;
exit(-1);
}
head = new LinkNode<DateType>;
LinkNode<DateType>* h = head;
while (p!=list2.head)
{
LinkNode<DateType>* t = new LinkNode<DateType>;
h->next = t;
t->prev = h;
t->data = p->data;
p = p->next;
h = h->next;
}
h->next = this->head;
this->head->prev = h;
}
//析构函数
~LinkList()
{
LinkNode<DateType>* p, * q = head->next;
while (q != head)
{
p = q;
q = q->next;
delete p;
}
}
//求双循环链表的长度
int Length()
{
LinkNode<DateType>* p = head;
int i = 0;
while (p->next != head)
{
++i;
p = p->next;
}
return i;
}
//创建双循环链表
void CreateList(int n)
{
DateType* nodetemp = new DateType[n];
for (rsize_t i = 0; i < n; i++)
{
cout << "Enter the element: " << endl;
cin >> nodetemp[i];
Insert(i, nodetemp[i], 1);
}
delete[] nodetemp;
}
//得到位置为pos的结点元素值
bool GetElem(int pos,DateType& data)
{
LinkNode<DateType>* p = head;
if (pos<0 || pos>Length())
{
cout << "输入的位置不合法" << endl;
return false;
}
else {
p = Locate(pos, 1);
data = p->data;
}
return true;
}
//定位元素,back_pos=0时从头节点向前查第i个元素,d!=0时,从头节点向后找第i个元素
LinkNode<DateType>* Locate(int i ,int back_pos)
{
if (head->next == head || i == 0) {
return head;
}
int j = 0;
LinkNode<DateType>* p = head;
//从头节点往后找第i个元素
if (back_pos)
{
while (p->next != head && j != i)
{
p = p->next;
++j;
}
if (p->next == head && j != i)
{
return NULL;
}
else
{
return p;
}
}//向前找
else
{
while (p->prev != head && j != i)
{
p = p->prev;
++j;
}
if (p->prev == head && j != i)
return NULL;
else
return p;
}
}
//在pos的位置插入元素
bool Insert(int pos, const DateType& data, int back_pos)
{
LinkNode<DateType>* p = Locate(pos, back_pos);
if (!p)
return false;
LinkNode<DateType>* new_node = new LinkNode<DateType>(data);
if (NULL == new_node)
{
cout << "内存分配失败" << endl;
exit(-1);
}
//p结点后插入
if (back_pos)
{
p->next->prev = new_node;
new_node->prev = p;
new_node->next = p->next;
p->next = new_node;
}//p结点前插入
else
{
p->prev->next = new_node;
new_node->next = p;
new_node->prev = p->prev;
p->prev = new_node;
}return true;
}
//输出双循环链表所有结点的元素值,分为正序打印和逆序打印
void PrintList(int sign)
{
//正序打印
if (sign)
{
cout << "head " ;
LinkNode<DateType>* p = head;
while (p->next != head)
{
p = p->next;
cout << "-> " << p->data;
}
cout << "->over" << endl;
}//逆序打印
else
{
cout << "head " << endl;
LinkNode<DateType>* p = head;
while (p->prev != head)
{
p = p->prev;
cout << "-> " << p->data;
}
cout << "->over" << endl;
}
}
//删除pos位置的结点
bool Delete(int pos, DateType& data,int back_pos)
{
LinkNode<DateType>* p = Locate(pos, back_pos);
if (!p)
{
return false;
}
if (p == head )
{
cout << "请不要删除头节点" << endl;
return false;
}
data = p->data;
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
return true;
}
private:
LinkNode<DateType>* head;//头节点
};
int main()
{
LinkList<int> list;
list.CreateList(5);
list.PrintList(1);
cout << "-----------------------" << endl;
LinkList<int> list2(list);
list2.PrintList(1);
cout << "-----------------------" << endl;
list.Insert(0, 10, 1);
list.PrintList(1);
cout << list.Length() << endl;
cout << "-----------------------" << endl;
int b = 0;
list.Delete(0, b, 1);
cout << b << endl;
list.PrintList(1);
cout << list.Length() << endl;
cout << "-----------------------" << endl;
list.GetElem(3, b);
cout << b << endl;
cout <<"---------------------------" << endl;
system("pause");
return EXIT_SUCCESS;
}
链表和顺序表的对比
参考下表:
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上连续 | 逻辑上连续 |
随机访问 | 支持 | 不支持 |
任意位置插入删除 | 要移动元素,O(N) | 只要改变指针指向 |
插入数据 | 要考虑扩容,会带来一定的空间消耗 | 没有容量这个概念,可以按需申请和释放 |
缓存利用率 | 高 | 低 |