建立双向链表 实现对双向链表的插入 删除 *** 作·

#include <iostream>

using namespace std

struct Node

{

int data //节点中的数据 结构体Node的成员变量

Node* next//指向下一节点的指针，习惯用next命名 结构体Node的成员变量

Node( const int&d=int() ) //结构体也可以有构造函数 ,d=T()来指定默认值

:data(d),next(NULL) //用构造函数来初始化成员变量data和指针

{} //所有数据类型，默认初始化都为0，这里data默认初始化为0

}

class Chain //封装链表

{

private: //数据成员通常都是private的

Node* head//首先，我们要一个Node型的指针来保存链表的第一个节点；

int length//再用一个整型变量来记录当前链表内的节点数

public:

Chain()//在构造函数里建立一个空链表，即head指向NULL

:head(NULL),length(0){}//节点数为0

//当我们在类中定义函数时（不是声明），相当于在前面加上一个inline修饰

void delall() //这个函数用来删除链表中的所有节点

{

Node* pdel //定义一个Node型指针用来保存要删除的节点

while( head != NULL ) //当head的指向不为NULL时，就是链表中还存在节点

{

pdel = head //这里备份head的当前指向节点

head = head->next//把head的指向改变为下一节点

delete pdel //把head的原指向给删除掉

} //如此一直下去，尾节点的next肯定是指向NULL的，那删除最后一个的时候

//head就被赋值为NULL，不满足循环条件，退出循环

length = 0 //把节点数归零

}

~Chain(){ delall()} //在析构函数中调用delall函数，来完成对象销毁时清理工作

//这样一个链表必须具备的功能就实现了。下面我们来实现他的增、删、查、改功能

Node*&getpoint( int position ) //对链表的 *** 作，其实全部通过指针来实现的，

{//那就需要定义一个函数来返回当前节点的指针（引用）

if( position<0 || position>length ) //对节点编号进行合法检查

position = length //如果是非法节点编号，那么就把他修改为最后一个节点编号

if( position==0 )//如果编号为0，那就是第一个节点了，

return head//直接返回head就是指向第一个节点的，注意返回的是head本身

Node* head_bak = head //如果编号合法并且不是第一个节点，就开始遍历链表

for( int i=1i <positioni++ )//为什么不直接用head

{//注意这里修改的是成员变量。你把head改了，以后到哪找链表

//我们都是通过head一个一个的往下找节点的。head被修改了。后果显而易见

head_bak = head_bak->next //通过备份的指针来遍历到指定编号前一个节点

}//i不从0开始，减少运算，提高效率

return head_bak->next //这里如果返回head_bak的话。那就是需要的前一个节点了

}

void insert( const int&data, int position ) //如果不修改参数的话，使用引用做参数的时候，最好加上const

{

Node* pin = new Node(data) //需要调用Node的构造函数

pin->next = getpoint(position) //把指定位置的指针返回给新节点的指针

//也就是说，把新的节点的next指向原来这个位置的节点。

getpoint(position) = pin //getpoint()返回的是引用，我们可以直接修改它

//前面的一个节点的next指向我们新的节点。

length++ //链表的节点数+1

}

int del( const int&data )

{

int position = find(data)

if( position !=-1 ) //-1代表没找到

{

Node* &pnext = getpoint(position) //用getponit()来获得指定节点的指向信息

Node* pbak = pnext //用来备份节点的指向信息

pnext = pnext->next//把next指向改为下下个节点。

delete pbak

length--

}

return position

}

//把<<重载，直接输出链表

friend ostream&operator<<( ostream&os, const Chain&oc )

{

Node* phead = oc.head

os <<"[ "

while( phead !=NULL )//判断是否到尾节点

{

os <<phead->data <<' '

phead = phead->next

}

os <<"] " //这个函数，应该没什么好说的了

return os //如果还是不理解，当成固定模式去背吧

}

}

void show()

{

cout <<"******************************" <<endl

cout <<"2- 向链表内添加节点（数据，节点号）" <<endl

cout <<"3- 删除链表内某一个数据（数据）" <<endl

cout <<"0- 退出" <<endl

cout <<"******************************" <<endl

}

int main()

{

Chain link

int position, data, choice, data_new

while( choice != 0 )

{

show()

cout <<"请选择："

cin >>choice

switch ( choice )

{

case 2 :

cout <<"请输入要插入的数据和插入位置："

cin >>data >>position

link.insert( data,position )

cout <<link <<endl

break

case 3 :

cout <<"请输入要删除的数据："

cin >>data

link.del( data )

cout <<link <<endl

break

default :

break

}

}

}

#include <iostream>

using namespace std

typedef struct node {

int data

node *prior,*next

}*DLinkList

DLinkList p,q,head

void CreateList(int n) { // 创建双向环形链表

head = new node

head->data = 0

p = head

for(int i = 0i <ni++) {

q = new node

cout <<"请输入第" <<i + 1 <<"/" <<n <<"个数 : "

cin >>q->data

p->next = q// 顺向连接新结点

q->next = head // 始终保持环形连接

q->prior = p // 新结点的反向链接

p = q // 为连接新节点做准备

}

head->prior = p// 头结点的prior指向最后的结点，是实现双向环形链表的最后一步

}

void print() { // 顺向输出链表数据

p = head->next

while(p != head) {

cout<<p->data<<' '

p = p->next

}

cout<<endl

}

void DCprint() { // 反向输出链表数据

p = head->prior

while(p != head) {

cout<<p->data<<' '

p = p->prior

}

cout<<endl

}

void deleteheap() { // 释放占用的堆空间

p = head

q = p->next

while(q != head) {

p = q

q = p->next

delete [] p

}

delete [] head

}

int main () {

int n

cout <<"请输入链表结点数 : "

cin >>n

CreateList(n)

print()

DCprint()

deleteheap()

return 0

}

前几天提到 舞蹈链算法 ，这两天有时间就动手实现了一下。

舞蹈链（Dancing links）实际上是一种数据结构，可以用来实现 X算法，以解决精确覆盖问题。

什么是精确覆盖（Exact Cover）问题呢？维基百科上对精确覆盖的定义如下：在一个全集 X 中若干子集的集合为 S。S* 是 S 的一个子集，当且仅当 X 中的每一个元素在 S* 中恰好出现一次时，S* 称之为一个精确覆盖。在计算机科学中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。这是一个NP-完全问题。

例如，S = {A，B，C，D，E，F} 是全集 X = {1，2，3，4，5，6，7} 的一个子集的集合，其中：

A = {1, 4, 7}

B = {1, 4}

C = {4, 5, 7}

D = {3, 5, 6}

E = {2, 3, 6, 7}

F = {2, 7}

那么，S 的一个子集 S* = {B, D, F} 是 X 的一个精确覆盖，因为 X 中的每个元素恰好在 S* 中出现了一次。

可以用 0-1 矩阵来表示精确覆盖问题。我们用矩阵的每行表示 S 的一个元素，也就是 X 的一个子集；用矩阵的每列表示 X 的一个元素。矩阵中的 1 代表这一列的元素存在于这一行对应的子集中，0 代表不存在。那么精确覆盖问题可以转化成求出矩阵若干行的集合，使得集合中的每一列恰好都有一个 1。

比如前面的问题可以用矩阵的形式表示成

那么选择红色的 B，D，F 能满足每列都恰好包含一个 1。

可以用 Knuth 提出的 X算法 来解决精确覆盖问题。X算法是一个非确定性的深度优先回溯算法。它的具体步骤如下：

让我们用 X算法 解决上面的精确覆盖问题。

首先，当前矩阵不为空，算法继续进行。那么先选择 1 最少的一列。因为 1，2，3，5，6 列都只有 2 个 1，因此我们随便选择 1 个，比如第 1 列。

行 A 和 B 都含有 1，因此要在这两行中进行选择。

第 0 层也没有其他可以选择的行，算法终止。

以上就是 X 算法的执行过程。Knuth 提出 X 算法主要是为了说明舞蹈链的作用，他发现用舞蹈链来执行 X 算法效率特别高。那么什么是舞蹈链呢？它是基于双向链表的一种数据结构。

让我们先来看看双向链表：

上图是一个简单的双向链表，每个节点有两个指针，分别指向自己的前驱和后继节点。那么如果我们想把其中一个节点，比如 B 从链表中删掉，只需要执行下面的 *** 作：

注意：此时虽然 B 从链表中移除了，但它的两个指针依然保持不变，还是指向之前的前驱和后继节点。

因此，如果我想把 B 再添加到链表原来的位置上，此时并不需要修改 B 的指针，只需要再把 B 的前驱和后继节点的指针恢复就可以了：

理解了这一点之后，让我们再来看看舞蹈链的结构是怎么样的：

上面这个图是一个舞蹈链的结构，描述的是前面 X 算法中用到的矩阵。它由几部分构成：

最上面的蓝色部分是一个水平的环状双向链表。最左边是头节点，它是整个数据结构的根节点。其余是列头节点，每个代表矩阵中的一列。

每一列又是一个纵向的环状双向链表。除了最上面的列头节点，其他的每个节点都代表前面的矩阵中的一个 1。这实际上是一个稀疏矩阵，为了优化存储和效率，只保留了值为 1 的节点，把每个节点按顺序保存到数组中。最早的 Dancing Links 算法，也就是 Knuth 在 2000 年发表的论文中，下面的每一行也都是一个双向链表。但后来他发现每一行在算法执行过程中实际上不会发生变化，因此他把水平的双向链表取消了，只保留了最顶上的列头节点之间的水平双向链表。下面的每一行之间的前后节点可以直接通过数组的索引得到。两边是Space节点，用来标记一行的开始和结束。

每个普通节点 A 都包含 4 个 字段，A.up 和 A.down 代表双向链表的两个指针，分别指向 A 上面和下面的节点。还有一个 A.col ，指向 A 所在列的头节点，需要根据这个字段定位到节点所在的列。另外还有一个 A.row，主要是方便在递归的过程中缓存当前的解。

列头节点还要再多几个字段，left 和 right 分别指向水平双向链表的左节点和右节点。另外还有一个 count 字段，代表这一列当前一共有几个元素。X 算法的第 2 步，选择 1 最少的列时会用到这个字段。

理解了舞蹈链的数据结构之后，我们再来看看是怎样用舞蹈链来实现 X 算法的。这部分算法很精妙，也是舞蹈链这个名字的来由，通过对链表上的节点反复删除和插入实现了递归的回溯，就好像一个个链表在舞台上翩翩起舞一样。

具体的算法实现可以参照 Knuth 的论文，我们还是用图的方式来说明一下。

以上就是舞蹈链算法的执行过程。

---