我的一个朋友过来面试引发我要说的一个小话题
2018-06-18 03:09:07来源：未知 阅读 ()
在很多家公司面试，也包括在携程，大多都会被问到一些算法的问题，其中机票事业部的面试，基本上算是算法问题的重灾区，没办法，有几个领导喜欢
用数据结构来考人家，其中包括一些常见数据结构的复杂度以及手写一些算法，比如快排，单链表等等，前几天我一个推荐过来的朋友膝盖就被中了一箭。
题目就不方便具体说了，第一小问就是用非递归来构建一个单链表，我们知道构建单链表可以说是学数据结构的基本功，一说到用链式结构，它跟递归
又有了千丝万缕的联系，很多链式的问题，我们用递归就可以轻轻松松的解决，几乎不需要动一下脑子，但是如果用非递归的话，那就稍微比递归要复杂一点
了，起码会多考一个引用类型内存分配的问题。
后来QQ上我就用递归和非递归的形式构建单链表回复了他，先给了一个递归的版本，这个没问题，可以消化，然后给了一个非递归的版本，看了之后就扛
不住了。
一：递归版本
1 class LinkList 2 { 3 public class LinkNode 4 { 5 public int data; 6 7 public LinkNode next; 8 } 9 10 private LinkNode head; 11 12 public void Add(int data) 13 { 14 if (head == null) 15 { 16 head = new LinkNode() { data = data }; 17 } 18 else 19 { 20 Add(head, data); 21 } 22 } 23 24 public void Add(LinkNode node, int data) 25 { 26 if (node.next == null) 27 { 28 node.next = new LinkNode() { data = data }; 29 return; 30 } 31 32 Add(node.next, data); 33 } 34 }
二：非递归版本
1 class LinkList 2 { 3 public class LinkNode 4 { 5 public int data; 6 7 public LinkNode next; 8 } 9 10 private LinkNode head; 11 12 public void Add(int data) 13 { 14 LinkNode node = new LinkNode() { data = data }; 15 16 if (head == null) 17 { 18 head = node; 19 } 20 else 21 { 22 LinkNode temp = head; 23 24 while (temp.next != null) 25 { 26 temp = temp.next; 27 } 28 29 temp.next = node; 30 } 31 } 32 }
这个非递归不理解的地方在于临时变量temp，提出的问题就是为什么：“temp.next=node” 之后，head的值发生了改变？我想之所以不能理解，绝逼是对
引用类型的内存分配不了解，而这个非递归版本恰恰就是用引用类型这个内存分配技巧来实现 ”非递归构建单链表“。。。为了不让别人踩上这个坑，我还是大
概说一下流程，大概是这样的，当我们在new一个引用类型的时候，CLR就要计算实例字段和所有基类上的实例字段的大小，然后再在堆上分配合理的内存块，
最后把堆上的内存块的首地址保存在栈上面。
为了方便理解，现在假如LinkList里面有三个结点：instance1 -> instance2 -> instance3,
第一句：
1 LinkNode temp = head;
这个句子不难理解吧，把head的地址赋给temp，那么栈上temp的地址也就是head的地址，head的地址就是指向instacnce1内存块地址。
第二句： 从这句while中可以看到，一直在找instance的next，可以看出之后把instance2的内存地址给了temp，再next之后就把instance3的内存地址给
了temp，然后就发现instance3的next为null，然后就跳出循环。
1 while (temp.next != null) 2 { 3 temp = temp.next; 4 }
第三句：从上一句可以看到，instance3的next已经为null了，这时候就把新构建的结点：LinkNode node = new LinkNode() { data = data };赋
给temp的next指针上来继续构建链表。
1 temp.next = node;
可以看到这时候instance4就构造到了instance3之后，同时temp.next已经是保存instance4的内存地址，这一些操作对head来说都是透明的，它也不管
后面怎么操作，当你遍历head的时候会惊奇的发现居然我的链表中多了一个instance4，这个也就是朋友疑惑的地方，如果看到这个内存分配图的话，
也许会豁然开朗，当然这篇博文没什么技术含量，也是自己一时有感而发。
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：我的程序员之路
- 一个工业级、跨平台、轻量级的 tcp 网络服务框架：gevent 2020-06-05
- 分享一个自己项目中用到的c++版的日志类(对初学者十分有用的 2020-05-22
- C++ 单独编译 2020-05-10
- 图 2020-05-02
- STL之map 2020-04-27
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
