使用int*指针特性来遍历链表

一种使用int*指针来访问链表元素的方法 (并非使用next指针的方法)

编译环境:TDM-GCC 4.9.2 32-Bit Release

众所周知 c与cpp中的链表可以通过结构体或class创建。比如:

class ListNode{

private:

       int val;

public:

       ListNode* next;

       int get(){return  val;}

       ListNode(int v):val(v),next(NULL){

              cout<<"this is a start function\n";

       }

       ListNode(const ListNode& node):val(node.val),next(node.next){

              cout<<"the second start\n";

       }

};

当我们要遍历链表所有元素,一种方法众所周知:

void print(ListNode* head){
	ListNode* cur=head;
	while (cur){
		cout<val<<" ";
		cur=cur->next;
	}
}

       但我们是否有别的方案来访问链表节点呢换句话说,我们是否可以使用c和c++中的类以及结构体的数据存储特点,来完成对链表节点的访问?

答案是yes!!!

        

前置知识:

在三十二位的情况下,地址大小为4字节,根据结构体地址对齐原则(如果结构成员的大小为4,那么它只会出现在4的倍数的位置上,比如0,4,8,12这样的位置。对size为8的结构变量,它只会出现在0,8,16这样的位置上,通过实践,你会发现class中也适用)。在我们当前这个包含了一个int(4字节)和一个指针(4字节的)的结构体中,它的大小为8。

由于链表的特性,一个node节点中保存当前节点的元素值,以及下一个节点的位置。在我们当前的结构中,int元素和next元素相邻,所以可以通过使指针向后移动一位的方式,拿到当前节点中的next元素的地址(该地址存储着下一个节点的地址信息),然后获取该地址上存着的地址信息,让指针指向那里。这样,我们就集齐了一次访问的所有条件。

核心代码如下:

void printList(ListNode* head){

       int* p=(int* )head;

       ListNode* cur=head;

       while (p!=NULL){

              cout<<*p<<' '<

我们看一下运行结果

使用int*指针特性来遍历链表_第1张图片

我们发现地址的访问和我们意想的相符合,印证了我们学习的链表存储方式的正确性。

Ps:这里只保证在32位下的运行,64位的情况下,指针大小为8,你需要移动ptr指针两次才能获得正确的结果:(因为对齐原则)

void printList(ListNode* head){

       int* p=(int* )head;

       while (p!=NULL){

              cout<<*p<<' ';

              int * ptr=p;

              ptr+=2;

              p=(int*)*ptr;

       }

       cout<<'\n';

}

现在我们看一点邪恶的事情,我们知道私有变量的访问限制,我们无法通过直接访问对象私有变量的方式来改变该对象的值,只能通过get和set方法来访问(java的开发者应该对此最为熟悉),如果强行访问的话,编译器会告诉我们结果: val是private的,我们无法直接访问。

(编译报错如下)

使用int*指针特性来遍历链表_第2张图片

 那我们是否可以绕开这一限制,从而来访问私有变量成员,或者修改它呢?

答案是 yes!!!!! 还是通过指针。

为了便于接下来内容的讲解,我们先来看一下递归打印链表的例子,传入参数为const


void recursivePrint(const ListNode* head){
	//为了方便 这里我把val写为public的了 
	if (!head)return;
	//head->val+=1;  //加上这句就会报错 因为修改了const变量
	cout<val<<" ";
	return recursivePrint(head->next);
}

         如果对head修改的话,编译器会提示我们这是一个 read-only object 会编译不过,而且,当我们的val声明为私有成员的话,head->val的访问也会受到限制。

但如果我们使用指针来访问呢(我发出邪恶的笑声hhhhhh)

我们来看实现过程

同样接口的递归函数,在内部我们使用强转指针的方式来访问,会产生意想不到的结果,私有成员和const变量的面纱在强大的指针面前,被揭开了:

void recursivePrint(const ListNode* head){
	int* p=(int*)head;
	if (p== NULL)return;
	(*p)++;//我们做邪恶的事情,对const对象的private成员变量来执行加一操作
	cout<<*p<<" ";
	p++;
	ListNode* next=(ListNode*)*p;//*p取到当前p上存放的下一个节点的地址,然后把它强转为ListNode*
	return recursivePrint(next);//递归访问来遍历链表
}

PS(实际写代码的话,使用这种代码风格,很可能被同事或者队友暴捶,所以自己自娱自乐就行qaq)

让我们看一下运行的效果:打印两次,初值为1,2,3,4,5,6,7,8,9;我们发现当我们执行recursivePrint以后,变为了2,3,4,5,6,7,8,9,10,11;我们单纯靠指针就修改了const 对象的private成员遍历。

使用int*指针特性来遍历链表_第3张图片

 这让我们看到了c和c++中指针的强大性,也提醒了我们这可能带来的安全隐患,毕竟,在熟悉较为底层知识的cpp程序员这里,对象中一切的秘密和限制都不复存在了。

我不知道java中有没有这样的操作,欢迎大家评论留言来告诉我。

附加:

一点有趣的知识点,也是我无意中发现到的:

在当前的32位环境下,

我们打印当前节点的位置,以及它所指向的下一个节点的地址:

使用int*指针特性来遍历链表_第4张图片

我们发现元素地址之间没有什么联系,可以说是随机的位置,符合我们对链表的认知。 

如果切换到clion中使用MinGW64来进行编译运行,(我们之前提过64位下,指针大小为8)会发现一个很有趣的现象:链表的节点地址是连续的。

使用int*指针特性来遍历链表_第5张图片

这几个节点的地址只有后两位是不同的,让我们计算一下距离c8-a8=32, e8-c8=32,两个节点之间距离差值为32,我们的指针一次后移4个单位,也就是说,如果我们让指针自加8,那么理论上也是能访问元素的!

我们试一下:

void printList(ListNode* head){
	int* p=(int* )head;
	while (*p<1000){//我设置的访问控制条件 因为我不会在这种情况判断截至 qaq 有会的老哥教教我
		cout<<*p<<' ';
		int * ptr=p;
		p+=8;
		cout<<" the next address is: "<

运行结果如下:

使用int*指针特性来遍历链表_第6张图片

 哈哈哈哈哈哈哈,似乎我们借助平台特性,实现了按照数组顺序访问的方法来访问链表的操作!

如果这篇文章对你有帮助,那不妨在评论区留言吧,2333333。