- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
看下面的图,就是我今天要给大家分享有结构——带头双向循环链表。这里的头是不存放任何数据的,就是一个哨兵卫的头结点.
用代码来表示每一个节点就是这样的:
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) | 只要改变指针指向 |
插入数据 | 要考虑扩容,会带来一定的空间消耗 | 没有容量这个概念,可以按需申请和释放 |
缓存利用率 | 高 | 低 |
最后此篇关于数据结构初阶--双向循环链表(讲解+类模板实现)的文章就讲到这里了,如果你想了解更多关于数据结构初阶--双向循环链表(讲解+类模板实现)的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
namespace std { template <> class hash{ public : size_t operator()( cons
我正在构建一个 Javascript 交互性有限的 Django 应用程序,并且正在研究如何将 Vue 模板与 Django 模板合并以实现相同的内容。 想象一个无限滚动的页面,其中 SEO 非常重要
我需要一个由游戏逻辑组成的外部类,调用 LitElement 组件,并向其传递一个 html 模板文字,该组件将使用该文字来更新其自己的 html 模板文字的一部分。 在下面的代码中,您将看到组件的一
很简单,我不想在 html 文件中定义所有 Handlebars 模板 我试过了 但这并没有奏效。我是否可以不以编程方式定义模板,甚至只是加载 Handlebars 文件,以便我可以重用,而且我觉得
在此代码中,j 正确地成为对象:j.name、j.addr、j.city、j.state 和 j.zip。但是,成功函数有一个 JavaScript 错误 .tmpl() 不是函数。 {{t
Django模板不会?点进来,总结了模板语法传值取值、过滤器和自定义过滤器、模板标签的分类、中间件403报错如何解决、如何继承模板~👆 Django 模板 模板传值取值 后端传值 键值对形式:{‘n
哈喽大家好,我是鹿 九 丸 \color{red}{鹿九丸}鹿九丸,今天给大家带来的是C++模板。 如果大家在看我的博客的过程中或者学习的过程中以及在学习方向上有什么问题或者想跟我交流的话可以加我的企
我正在用 PHP 编写一个简单的模板层,但我遇到了一些困难。目前它是这样工作的: 首先,我使用 fetch_template 从数据库中加载模板内容 - 这可行(如果您有兴趣,我会在启动时收集所有模板
我正在制作有关模板的 Django 教程。我目前处于此代码: from django.template import Template, Context >>> person = {'name': '
我正在使用 Jquery 模板来显示传入的 JSON 数据我想将模板加载到可缓存的外部文件中。我该怎么做? 更新 http://encosia.com/2010/12/02/jquery-templa
这是我的观点.py: from django.http import HttpResponse from django.template.loader import get_template from
我试图说服一位同事在项目的前端使用 Mustache/Hogan,我提出了以下建议: 有一个 templates.js 文件,大致如下所示: var tpl_alert = '{{msg}}'; va
我想创建一个通用的数组函数。在我的 API 中,我有一个通用容器,我需要将其转换为正确的类,但我想让它通用 template void UT::printArray(CCArray* arr, T t
有谁知道是否有办法在 Genshi 中创建 javascript 模板?我的意思是,我需要一个 .js 文件,可以在其中使用 等指令。等等。 有什么想法吗?谢谢! 最佳答案 你可以直接在html中这
我想知道是否可以设置某种 HTML 模板系统,基本上我有 3 个不同的文件: - header.html - footer.html - landing.html(landing.html 是包含页面
我正在尝试构建以下 HTML 模板: 这很简单,如果我使用红色容器 1-4,语法如下: 1 2 3 4 5 6 7 8 9 https://jsfi
#include "boost/numeric/ublas/matrix.hpp" using namespace boost::numeric::ublas; template class Lay
我在一个类中有一个函数,它传递了一个函数及其参数,然后将它们绑定(bind)到一个函数调用中并调用该函数等。 这已经被快速组合在一起以测试我知道代码不是很好的概念。 class Profiling {
是否有一个 c++ 结构或模板(在任何库中)允许我在十进制和任何其他基数之间进行转换(很像 bitset 可以做的)? 最佳答案 是的,你可以使用unsigned int: unsigned int
来自其他编程语言,许多像我一样的人会感到惊讶。我有一个简单的问题。我有一个列表——比如说,用户。我想遍历用户并显示一些信息。非常简单,直到我被这个难住了: 使用一个 eex 模板,我试图这样做:
我是一名优秀的程序员,十分优秀!