锐客网

  1. 首页 > it技术 > >

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

一种使用int*指针来访问链表元素的方法 （并非使用next指针的方法）
编译环境：TDM-GCC 4.9.2 32-Bit Release

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

class ListNode{private:int val; public:ListNode* next; int get(){returnval; }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！！！

【c++|使用int*指针特性来遍历链表】前置知识：
在三十二位的情况下，地址大小为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<<' '<

我们看一下运行结果
c++|使用int*指针特性来遍历链表
文章图片

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

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的，我们无法直接访问。
（编译报错如下）
c++|使用int*指针特性来遍历链表
文章图片

那我们是否可以绕开这一限制，从而来访问私有变量成员，或者修改它呢？
答案是 yes!!!!! 还是通过指针。
为了便于接下来内容的讲解，我们先来看一下递归打印链表的例子，传入参数为const
void recursivePrint(const ListNode* head){ //为了方便 这里我把val写为public的了 if (!head)return; //head->val+=1; //加上这句就会报错 因为修改了const变量 coutnext); }

如果对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成员遍历。
c++|使用int*指针特性来遍历链表
文章图片

这让我们看到了c和c++中指针的强大性，也提醒了我们这可能带来的安全隐患，毕竟，在熟悉较为底层知识的cpp程序员这里，对象中一切的秘密和限制都不复存在了。
我不知道java中有没有这样的操作，欢迎大家评论留言来告诉我。

附加：
一点有趣的知识点，也是我无意中发现到的：
在当前的32位环境下，
我们打印当前节点的位置，以及它所指向的下一个节点的地址：
c++|使用int*指针特性来遍历链表
文章图片

我们发现元素地址之间没有什么联系，可以说是随机的位置，符合我们对链表的认知。
如果切换到clion中使用MinGW64来进行编译运行，（我们之前提过64位下，指针大小为8）会发现一个很有趣的现象：链表的节点地址是连续的。

c++|使用int*指针特性来遍历链表
文章图片

这几个节点的地址只有后两位是不同的，让我们计算一下距离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: "<

运行结果如下：
c++|使用int*指针特性来遍历链表
文章图片

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

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

    推荐阅读


    上一篇：IT|为什么这么多应届生要进入互联网行业（）

    下一篇：程序人生|100天涨薪4k！从功能测试到自动化测试，我整理的超全学习指南！