在很多家公司面試，也包括在攜程，大多都會被問到一些算法的問題，其中機票事業部的面試，基本上算是算法問題的重災區，沒辦法，有幾個領導喜歡
用數據結構來考人家，其中包括一些常見數據結構的復雜度以及手寫一些算法，比如快排，單鏈表等等，前幾天我一個推薦過來的朋友膝蓋就被中了一箭。
題目就不方便具體說了，第一小問就是用非遞歸來構建一個單鏈表，我們知道構建單鏈表可以說是學數據結構的基本功，一說到用鏈式結構，它跟遞歸
又有了千絲萬縷的聯系，很多鏈式的問題，我們用遞歸就可以輕輕松松的解決，幾乎不需要動一下腦子，但是如果用非遞歸的話，那就稍微比遞歸要復雜一點
了，起碼會多考一個引用類型內存分配的問題。
后來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，這個也就是朋友疑惑的地方，如果看到這個內存分配圖的話，
也許會豁然開朗，當然這篇博文沒什么技術含量，也是自己一時有感而發。
文章列表
留言列表
