在此之前,先从入门的方面来讲一讲。
在最开始学编程的时候,我们交换两个变量,有两种方法
//方法一
c=a
a=b
b=c
//方法二
a=a+b
b=a-b
a=a-b
从第二种方法我们可以看出,我们可以通过两个数的相加,然后特别取出某个数
那么想一想?我们能否通过两个地址相加,取出一个地址呢?(这个在这里给大家引一个方向)
到了后面,接触了位运算,我们有可以通过异或来进行数据交换
//方法三
a=a^b;
b=a^b;
a=a^b;
这和位运算的自反性有关
那么,我们能否同地址进行异或运算来得出一个地址呢?思路和上面通过加法有点像
双链表
看这个的应该都会,我直接上图
我们把中间某一个节点单独提取出来,就会是这样
其中prev是上一个节点的地址,next是下一个节点的地址
属于两个指针域,那么我们能否用一个指针域来代替两个呢
如果能够代替,那么假设我们某个节点的前驱节点地址如果是已知的,那么他的后继节点地址也能够退出来,比如我们可以设当前节点的指针与为prev+next,然后上一个节点的地址是prev,那么下一个节点的地址不就是prev+next-prev吗?一个简单的函数
Node* sump(Node* a,Node *b){
return (Node*)((unsigned long long)a+(unsigned long long)b)
}
但是为了运算效率快一点,我们直接用异或运算(在单位二进制的情况下,异或运算等同于加法,与运算等同于乘法)
Node* xorp(Node* a,Node *b){
return (Node*)((unsigned long long)a^(unsigned long long)b)
}
我们可以这样存储数据
B的异或指针如下构造
B->xorPtr = addr(A) ⊕ addr(C)
获取B的前驱A的地址
addr(A) = B->xorPtr ⊕ addr(C)
获取B的后继C的地址
addr(C) = B->xorPtr ⊕ addr(A)
通过以上的几种操作,就可以遍历整个链表,在处理添加、插入、删除等操作时同普通的双向链表类似
注意:这些异或和加法相关的操作都是针对指针值的本身,即指针转换为无符号整型数的结构,不能跟指针的运算操作混淆。
下面是代码:
#include <iostream>
using namespace std;
//通过异或运算实现双链表
typedef struct node{
int v;
struct node *xorptr=NULL;//存储相邻两个节点地址的异或值
}Node;
inline Node* xorp(Node* a, Node* b){
return (Node *)((unsigned long long)a^(unsigned long long)b);
}
class List{
Node *Head=NULL;//头节点
Node *Tail=NULL;//尾节点
int Len=0;
public:
List() {
this->Head=new Node ;
this->Tail=new Node ;
Head->xorptr=Tail;
Tail->xorptr=Head;
Len=0;
}
void init(){
int i=10;
srand(time(NULL));
while(i--) {
int x=rand()%100+0;
insert(x);
}
}
void insert(int i){
Node *p=new Node ;
p->v=i;
if(!Len){
Head=p;
p->xorptr=NULL;
Tail=p;
} else{
p->xorptr= Head;
Head->xorptr= xorp(p,Head->xorptr);
Head=p;
}
Len++;
}
void display(bool flag=false){
Node *p=NULL;
Node *t=NULL;
if (!flag)p=Head;
else p=Tail;
for(int i=0;i<Len;i++){
cout<<p->v<<" ";
Node *k=p;
p= xorp(t,p->xorptr);
t=k;
}
}
bool remove(int v){
Node *p=Head;
Node *t=NULL;
bool flag=false;
for(int i=0;i<Len;i++){
if (p->v==v){
flag=true;
Len--;
if (p==Head){
Head=Head->xorptr;
Head->xorptr= xorp(p,Head->xorptr);
p=Head;
continue;
}
Node* m= xorp(t,p->xorptr);
t->xorptr=xorp( t->xorptr,p);
m->xorptr= xorp(m->xorptr,p);
t->xorptr= xorp(t->xorptr,m);
m->xorptr= xorp(m->xorptr,t);
p=m;
}
else{
Node *k=p;
p=xorp(t,p->xorptr);
t=k;
}
}
return flag;
}
};
int main(){
List A;
cout<<"头插顺序:";
A.init();
A.display(true);
cout<<endl;
cout<<"插入后的结果:";
A.display();
cout<<endl;
cout<<"请输入要删除的数字:";
int x;
cin>>x;
if (A.remove(x)){
cout<<"删除成功:";
A.display();
cout<<endl;
}
else{
A.insert(x);
A.display();
}
}
正文完