当前位置：首页 > 编程日记 > 正文

带哨兵节点的链_【算法导论】10.2不带哨兵节点和带哨兵节点的双向链表

编程日记 2024-08-31 19:00:00

不带哨兵节点的双向链表即一般的双向链表，有一个头指针指向第一个节点，每个节点有key值和两个指针next和pre，分别指向前后相邻的节点，头结点的pre=NULL，尾节点的next=NULL，比较明了，但是也有麻烦的地方：在做查找删除节点等操作的时候，免不了要判断边界条件，比如node==NULL等。先来看看这种链表的代码：

* 实现没有哨兵节点的双向链表，需要自己判断边界条件

#include

using namespace std;

class list {

struct node {

int key;

node* next;

node* pre;

node(int k) :

key(k), next(NULL), pre(NULL) {

}

};

public:

node* head;

int len;

list() :

head(NULL), len(0) {

}

~list() {

node* tmp1 = head, *tmp2;

while (tmp1 != NULL) {

tmp2 = tmp1->next;

delete tmp1;

len--;

cout << "len=" << len << endl;

tmp1 = tmp2;

}

* 在头处插入节点

void insertHead(int k) {

node* n = new node(k);

n->next = head;

head = n;

if (n->next != NULL) {

n->next->pre = n;

}

len++;

}

* 删除指针指向的节点

int del(node* n) {

if (n == NULL) {

return -1;

}

if (n->pre != NULL) {

n->pre->next = n->next;

} else {

head = n->next;

}

if (n->next != NULL) {

n->next->pre = n->pre;

}

delete n;

len--;

return n->key;

}

* 查找具有某个key值的节点

node* searchList(int k) {

if (len == 0) {

return NULL;

}

node* tmp = head;

while (tmp != NULL) {

if (tmp->key == k) {

break;

}

tmp = tmp->next;

}

return tmp;

}

* 遍历list

void travelList() {

node* tmp = head;

while (tmp != NULL) {

cout << tmp->key << ' ';

tmp = tmp->next;

}

cout << endl;

}

};

int main() {

list* l = new list();

l->insertHead(5);

l->insertHead(4);

l->insertHead(3);

l->travelList();

l->del(l->head->next);

l->travelList();

delete l;

return 0;

}

每次判断边界条件，虽然不会从根本上增加时间复杂度，但是对其常数项还是有影响的；而如果使用带哨兵节点构成的双向循环链表，则可以省去这些问题。我们使用一个“哑的”NIL节点来代替之前的head头指针，NIL节点的key值没有实际的意义，主要关注它的next和pre，初始的时候，链表只有一个NIL节点，NIL.next指向自己，NIL.pre也指向自己。当添加了若干个节点之后，NIL.next指向头节点，而NIL.pre则指向尾节点；而同样的，这时头节点的pre不再是NULL而是指向NIL，尾节点的next也不再是NULL，也是指向NIL。

这样的好处在于，我们判断边界条件的时候，不需要再判断是否为空，尤其在删除节点的时候，只需要写两句即可。但是这样也带来一些问题，就是要额外分配空间来存储NIL节点，如果对于多个比较短的链表而言，这样可能会代码比较大的冗余空间。

代码如下：

* 实现带哨兵是双向循环链表

#include

using namespace std;

class list {

struct node {

int key;

node* next;

node* pre;

node(int k) :

key(k), next(NULL), pre(NULL) {

}

};

//node* head;

public:

node* nil; //哨兵节点

int len;

list() :

nil(), len(0) {

nil = new node(0); //初始化哨兵节点

//让链表循环起来

nil->next = nil;

nil->pre = nil;

}

~list() {

//析构的时候要delete掉还存在于list中的节点

if (len == 0) {

delete nil;

return;

}

node* n1 = nil->next;

node* n2 = NULL;

while (n1 != NULL && n1 != nil) {

n2 = n1->next;

delete n1;

len--;

n1 = n2;

}

delete nil;

}

* 在头部插入节点

void insertHead(int k) {

node* n = new node(k);

n->next = nil->next;

n->pre = nil;

nil->next = n;

//这一句不要丢了

n->next->pre = n;

len++;

}

* 删除节点，这里删除的操作只需要写两句，比不带哨兵的链表操作要简洁的多

void del(node* n) {

n->pre->next = n->next;

n->next->pre = n->pre;

delete n;

len--;

}

node* searchList(int k) {

node* tmp = nil->next;

//让nil的key值永远不可能等于k

//nil->key = k + 1;

//while (tmp->key != k) {

while (tmp != nil && tmp->key != k) {

tmp = tmp->next;

}

if (tmp != nil) {

return tmp;

} else {

return NULL;

}

* 从next指针方向遍历链表

void travelClockwise() {

node* tmp = nil->next;

while (tmp != nil) {

cout << tmp->key << ' ';

tmp = tmp->next;

}

cout << endl;

}

* 从pre指针方向遍历链表

void travelAnticlockwise() {

node* tmp = nil->pre;

while (tmp != nil) {

cout << tmp->key << ' ';

tmp = tmp->pre;

}

cout << endl;

}

};

int main() {

list* l = new list();

l->insertHead(5);

l->insertHead(4);

l->insertHead(3);

l->travelClockwise();

l->del(l->nil->pre);

//l->travelClockwise();

l->travelAnticlockwise();

return 0;

}

https://www.dkcj.cn/info/16711.html

Android环境结构--安装Eclipse错

在学习安卓第一步。成立了一个开发环境。经验，知道，所以这一步是不容易，因为你觉得，我可能是太幸运了。我见到题。首先，安装Eclipse的时候。【Problem 1】【问题原因】： （1） 安装…

编程日记2024/08/31 18:50:00

ThinkPHP的标签制作

thinkphp的默认标签解析器在Lib/Template/TagLib/TagLibCx.class中里面定义了常用的volist php 等常用thinkphp的标签这里笔者在这个类中添加一个<category>的标签解析标签格式：<category parentid0 ><{$cat.catname}></category>标签作用&…

编程日记2024/08/31 18:40:00

Go进阶：反射3定律

各位学习Go语言的朋友，周末好，这次跟大家聊一聊Go语言的一个高级话题：反射。这篇文章是从我过去的学习笔记修改来的，内容主要来自Go Blog的一篇文章《The law of reflection》。这篇文章主要介绍反射和接口的关系，解…

编程日记2024/08/31 18:30:00

qlabel可以选中吗_Qt QLabel详解

Qt QLabel详解Qt QLabel详解一、QLabel常用方法1. QLabel设置文本内容ui.label->setText(QStringLiteral("测试中文\n"));2. QLabel设置颜色通过设计器里面的改变样式进行设置：同时可以设置字体、文本对齐方式、背景图片color: rgb(255, 85, 0);backgr…

编程日记2024/08/31 18:20:00

数据库种类以及优缺点

1.MySQL MySQL是最受欢迎的开源SQL数据库管理系统，它由 MySQL AB开发、发布和支持。MySQL AB是一家基于MySQL开发人员的商业公司，它是一家使用了一种成功的商业模式来结合开源价值和方法论的第二代开源公司。MySQL是MySQL AB的注册商标。 MySQL是一个快速…

编程日记2024/08/31 18:10:00

xcode 4.2 不再支持 Window-Based Application 的解决办法（转载）

xcode 4.2 不再支持 Window-Based Application 的解决办法： 1.创建空项目 Empty Application。（在Xcode4.2下创建的这个空项目不再有MainWindow.xib文件了。） 2.CtrlN，创建User Interface下面的Window（选择“i…

编程日记2024/08/31 18:00:00

java知识概论

转载于:https://www.cnblogs.com/arrows/p/10432301.html

编程日记2024/08/31 17:50:00

及cp含义_当我们谈论CP时，我们在谈论什么？

2015年B站UP主剪刀手轩辕投稿了一个名为《【魔性拉郎群像】你问我爱你有多深》的视频，让伏黛(伏地魔林黛玉)这个CP走进了众多二次元观众的视野，让这个超级冷门的小众CP一跃成为微博超话，甚至还上了当时的微博热搜。其实早在2010年&#xff0c…

编程日记2024/08/31 17:40:00

40个出色的Wordpress cms插件

WordPress is a great blogging platform with a potential of being an easy to use content management system. This is the third article of our three-part series, “The Comprehensive Guide for a Powerful CMS using WordPress”. We are taking a look at 40 qualit…

编程日记2024/08/31 17:30:00

带哨兵节点的链_【算法导论】10.2不带哨兵节点和带哨兵节点的双向链表

相关文章：

Android环境结构--安装Eclipse错

ThinkPHP的标签制作

Go进阶：反射3定律

qlabel可以选中吗_Qt QLabel详解

数据库种类以及优缺点

xcode 4.2 不再支持 Window-Based Application 的解决办法（转载）

java知识概论

及cp含义_当我们谈论CP时，我们在谈论什么？

40个出色的Wordpress cms插件

Xcode 添加代码块

软考自查：计算机网络

restful url 设计规范_restFul接口设计规范

Dictionary作为数据源绑定，调用c++库中返回为BYTE*的函数，listView项排序

ES6 新特性

一次被僵尸网络病毒攻击的过程

c2 链路_POS链路不能打开的解决办法

“寒冬”下的金三银四跳槽季来了，帮你客观分析一下局面

TCP拥塞控制算法内核实现剖析（二）

关于IOS中的self关键字

中值定理符号怎么读_微分、微分中值定理、泰勒公式

Java高级特性增强-多线程

微软企业库4.1学习笔记（八）创建对象续集2

Kali Linux python 安装pip

3dmax图像采样器抗锯齿_内幕揭秘！同样的场景同一张图，用3DMAX网渲平台进行二次渲染时间竟然相差3个小时之多！...

2015/8/18

Javascript - prototype、proto、constructor

DOS下读取4GB内存

7纳米duv和euv_要超车台积电三星宣布采用EUV技术7纳米制程完成验证

HDU 1711 Number Sequence(KMP算法)

分享45款高质量的免费(X)HTML/CSS模板