|
最近被問到鏈表，是一個(gè)朋友和我討論Java的時(shí)候說的。說實(shí)話，我學(xué)習(xí)編程的近一年時(shí)間里，學(xué)到的東西還是挺少的。語言是學(xué)了Java和C#，關(guān)于Web的學(xué)了一點(diǎn)Html+css+javascript。因?yàn)楸容^偏好，學(xué)習(xí)WinForm時(shí)比較認(rèn)真，數(shù)據(jù)庫操作也自己有所研究。但鏈表這個(gè)東西我還真沒有學(xué)習(xí)和研究過，加上最近自己在看WPF，而課程也到了JSP了，比較緊。 但是我還是抽了一個(gè)晚上加半天的時(shí)間看了一下單向鏈表。并且使用Java試著寫了一個(gè)實(shí)例出來。沒有接觸過鏈表的朋友可以作為參考，希望大家多提寶貴意見。 當(dāng)然，我們首先解釋一下什么是鏈表。就我所知，鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組同級(jí)。比如，Java中我們使用的ArrayList，其實(shí)現(xiàn)原理是數(shù)組。而LinkedList的實(shí)現(xiàn)原理就是鏈表了。我的老師說，鏈表在進(jìn)行循環(huán)遍歷時(shí)效率不高，但是插入和刪除時(shí)優(yōu)勢明顯。那么他有著愈十年的編程經(jīng)驗(yàn)，我是相信的。不過不知道他是否是說雙向鏈表，我們?cè)诖四刂粚?duì)單向鏈表做一個(gè)了解。 鏈表（Chain本文所說鏈表均為單向鏈表，以下均簡稱單向鏈表）實(shí)際上是由節(jié)點(diǎn)（Node）組成的，一個(gè)鏈表擁有不定數(shù)量的節(jié)點(diǎn)。而向外暴露的只有一個(gè)頭節(jié)點(diǎn)（Head），我們對(duì)鏈表的所有操作，都是直接或者間接地通過其頭節(jié)點(diǎn)來進(jìn)行的。 節(jié)點(diǎn)（Node）是由一個(gè)需要儲(chǔ)存的對(duì)象及對(duì)下一個(gè)節(jié)點(diǎn)的引用組成的。也就是說，節(jié)點(diǎn)擁有兩個(gè)成員：儲(chǔ)存的對(duì)象、對(duì)下一個(gè)節(jié)點(diǎn)的引用。 這樣說可能大家不是很明白，我貼一張圖大家可能更容易理解。 那么大家可能清除了，為什么說有了頭節(jié)點(diǎn)就可以操作所有節(jié)點(diǎn)。因?yàn)橛兄粩嗟囊寐铮?/p> 那么在鏈表里的屬性大概就只有兩個(gè)了：頭節(jié)點(diǎn)和節(jié)點(diǎn)數(shù)量。當(dāng)然，根據(jù)需要，我們通常需要更多的屬性。 簡單的鏈表可以寫為下面的樣子：  1 package myChain; 2 3 /** 4 * （單向）鏈表 5 * 6 * @author Johness 7 */ 8 public class PersonChain { 9 private PersonChainNode head; // 頭節(jié)點(diǎn) 10 private int size; // 鏈表的實(shí)體（即節(jié)點(diǎn)的數(shù)量） 11 private int modCount; // 鏈表被操作的次數(shù)（備用） 12 13 /** 14 * 獲得鏈表中節(jié)點(diǎn)數(shù)量 15 * 16 * @return 鏈表中節(jié)點(diǎn)數(shù) 17 */ 18 public int getSize() { 19 return this.size; 20 } 21 22 /** 23 * 添加節(jié)點(diǎn)的一般方法 24 * 25 * @param p 26 * 添加到鏈表節(jié)點(diǎn)的對(duì)象 由于實(shí)現(xiàn)細(xì)節(jié)，作為唯一標(biāo)識(shí)，同一個(gè)編號(hào)的Person只能添加一次 27 */ 28 public void addNode(Person p) { 29 if (!contains(p.personNo)) { // 如果鏈表中沒有該對(duì)象，則準(zhǔn)備添加 30 if (head != null) { // 如果有頭節(jié)點(diǎn)，則添加新節(jié)點(diǎn)作為頭節(jié)點(diǎn) 31 head = new PersonChainNode((myChain.Person) p, head); 32 size++; 33 modCount++; 34 } else { // 如果沒有頭節(jié)點(diǎn)，則添加對(duì)象作為頭節(jié)點(diǎn) 35 head = new PersonChainNode((myChain.Person) p, null); 36 size++; 37 modCount++; 38 } 39 } 40 } 41 } 以上的代碼就是一般鏈表的骨架了。擁有兩個(gè)重要屬性。 那么做為能添加到鏈表的節(jié)點(diǎn)又該長什么樣子呢？ 我們可以寫作如下： 1 package myChain; 2 3 /** 4 * （節(jié)點(diǎn)）實(shí)體，封裝了'人'這個(gè)對(duì)象和下一個(gè)實(shí)體的引用 5 * 該實(shí)體將作為（單向）鏈表的節(jié)點(diǎn) 6 * @author Johness 7 */ 8 public class PersonChainNode { 9 Person person; // 人 10 PersonChainNode nextNode; // 該對(duì)象（'人'）保存的下一個(gè)對(duì)象的引用 11 12 // 獲取當(dāng)前實(shí)體對(duì)象（'人'） 13 public Person getPerson(){ 14 return this.person; 15 } 16 17 // 獲取下一個(gè)實(shí)體 18 public PersonChainNode getNextNode(){ 19 return this.nextNode; 20 } 21 22 // 構(gòu)造方法 23 public PersonChainNode (Person p,PersonChainNode ep){ 24 this.person = p; 25 this.nextNode = ep; 26 } 27 } 當(dāng)然了，這只是個(gè)大概的樣子。 那么我最后在把層次梳理一下：鏈表是由不定數(shù)量的節(jié)點(diǎn)連接（通過相互之間的引用）起來的，由于這種關(guān)系，在鏈表里我們只定義了頭節(jié)點(diǎn)和節(jié)點(diǎn)數(shù)量。節(jié)點(diǎn)是由存儲(chǔ)的對(duì)象及對(duì)下一個(gè)“節(jié)點(diǎn)”的引用封裝而成。 在添加節(jié)點(diǎn)到鏈表中時(shí)，首先添加的節(jié)點(diǎn)后置后，新添加的節(jié)點(diǎn)作為頭節(jié)點(diǎn)引用前一個(gè)添加的節(jié)點(diǎn)。 廢話不多說，貼上我的例子，老師說我廢話多…… ?。ㄒ韵碌睦虞^為簡陋，大家不要笑話我哈） 1 package myChain; 2 3 /** 4 * '人' 類 5 * @author Johness 6 * @version 1.0 7 */ 8 public class Person { 9 String name; // 姓名 10 int age; // 年齡 11 int personNo; // 編號(hào)，用作唯一標(biāo)識(shí) 12 13 // 帶參構(gòu)造方法 14 public Person(String name, int age, int personNo) { 15 this.name = name; 16 this.age = age; 17 this.personNo = personNo; 18 } 19 20 // 獲取姓名 21 public String getName(){ 22 return this.name; 23 } 24 25 // 獲取年齡 26 public int getAge(){ 27 return this.age; 28 } 29 30 // 獲取編號(hào) 31 public int getPersonNo(){ 32 return this.personNo; 33 } 34 35 // 用于輸出的信息 36 public String toString(){ 37 return "姓名：" + this.name + "\t年齡：" + this.age +"\t編號(hào)" + this.personNo; 38 } 39 }
1 package myChain; 2 3 /** 4 * （節(jié)點(diǎn)）實(shí)體，封裝了'人'這個(gè)對(duì)象和下一個(gè)實(shí)體的引用 5 * 該實(shí)體將作為（單向）鏈表的節(jié)點(diǎn) 6 * @author Johness 7 */ 8 public class PersonChainNode { 9 Person person; // 人 10 PersonChainNode nextNode; // 該對(duì)象（'人'）保存的下一個(gè)對(duì)象的引用 11 12 // 獲取當(dāng)前實(shí)體對(duì)象（'人'） 13 public Person getPerson(){ 14 return this.person; 15 } 16 17 // 獲取下一個(gè)實(shí)體 18 public PersonChainNode getNextEntity(){ 19 return this.nextNode; 20 } 21 22 // 構(gòu)造方法 23 public PersonChainNode (Person p,PersonChainNode ep){ 24 this.person = p; 25 this.nextNode = ep; 26 } 27 28 // 構(gòu)造方法 29 public PersonChainNode (Person p){ 30 this.person = p; 31 } 32 } 1 package myChain; 2 3 /** 4 * （單向）鏈表 5 * 6 * @author Johness 7 */ 8 public class PersonChain { 9 private PersonChainNode head; // 頭節(jié)點(diǎn) 10 private int size; // 鏈表的實(shí)體（即節(jié)點(diǎn)的數(shù)量） 11 private int modCount; // 鏈表被操作的次數(shù)（備用） 12 13 /** 14 * 獲得鏈表中節(jié)點(diǎn)數(shù)量 15 * 16 * @return 鏈表中節(jié)點(diǎn)數(shù) 17 */ 18 public int getSize() { 19 return this.size; 20 } 21 22 /** 23 * 添加節(jié)點(diǎn)的一般方法 24 * 25 * @param p 26 * 添加到鏈表節(jié)點(diǎn)的對(duì)象 由于實(shí)現(xiàn)細(xì)節(jié)，作為唯一標(biāo)識(shí)，同一個(gè)編號(hào)的Person只能添加一次 27 */ 28 public void addNode(Person p) { 29 if (!contains(p.personNo)) { // 如果鏈表中沒有該對(duì)象，則準(zhǔn)備添加 30 if (head != null) { // 如果有頭節(jié)點(diǎn)，則添加新節(jié)點(diǎn)作為頭節(jié)點(diǎn) 31 head = new PersonChainNode((myChain.Person) p, head); 32 size++; 33 modCount++; 34 } else { // 如果沒有頭節(jié)點(diǎn)，則添加對(duì)象作為頭節(jié)點(diǎn) 35 head = new PersonChainNode((myChain.Person) p, null); 36 size++; 37 modCount++; 38 } 39 } 40 } 41 42 /** 43 * 通過編號(hào)刪除對(duì)象 44 * 45 * @param personNo 46 * 要?jiǎng)h除對(duì)象的編號(hào) 47 */ 48 public void deleteNode(int personNo) { 49 if (size == 0) { // 如果當(dāng)前鏈表節(jié)點(diǎn)數(shù)為零 50 return; 51 } 52 if (size == 1) { 53 // 如果只有一個(gè)節(jié)點(diǎn)并且正是需要?jiǎng)h除的對(duì)象 54 if (head.person.personNo == personNo) { 55 head = null; 56 size = 0; 57 } 58 return; 59 } 60 // 如果不存在該對(duì)象編號(hào) 61 if (!contains(personNo)) { 62 return; 63 } 64 65 // 較為復(fù)雜的刪除，定義整型保存被刪除的節(jié)點(diǎn)的索引 66 //（刪除和索引都是不存在的，這里只是一個(gè)說法） 67 int index = 0; 68 // 循環(huán)遍歷，找到刪除節(jié)點(diǎn)的索引 69 for (PersonChainNode p = head; p != null; p = p.nextNode) { 70 if (!(p.person.personNo == personNo)) { 71 index++; 72 } else { 73 break; 74 } 75 } 76 // 如果刪除的是第一個(gè)節(jié)點(diǎn)（即頭節(jié)點(diǎn)） 77 if (index == 0) { 78 head = new PersonChainNode(head.nextNode.person, 79 head.nextNode.nextNode); // 設(shè)置頭節(jié)點(diǎn)后一個(gè)節(jié)點(diǎn)為新的頭節(jié)點(diǎn) 80 size--; // 鏈表節(jié)點(diǎn)數(shù)減一 81 modCount++; // 鏈表被操作次數(shù)加一 82 return; 83 } 84 85 // 如果刪除的節(jié)點(diǎn)不是第一個(gè)節(jié)點(diǎn) 86 // 循環(huán)遍歷，找到被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) 87 // 其索引下標(biāo)用count保存 88 int count = 0; 89 for (PersonChainNode p = head; p != null; p = p.nextNode) { 90 if (count == index - 1) { // 如果找到了被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn) 91 if (index == size - 1) { // 如果被刪除節(jié)點(diǎn)是最后一個(gè)節(jié)點(diǎn) 92 p.nextNode = null; // 將被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的引用指向空引用 93 } else { // 如果被刪除節(jié)點(diǎn)不是最后一個(gè)節(jié)點(diǎn) 94 p.nextNode = p.nextNode.nextNode; // 將被刪除節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)對(duì)其引用指向被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) 95 } 96 size--; // 減一數(shù)量 97 modCount++; // 加一操作次數(shù) 98 return; 99 } 100 count++; // 沒有找到，索引加一 101 } 102 } 103 104 /** 105 * 通過姓名查找對(duì)象 106 * 未實(shí)現(xiàn) 107 * @param name 108 * 對(duì)象姓名 109 * @return 對(duì)象數(shù)組，可能多個(gè) 110 */ 111 public Person[] searchNodeByPersonName(String name) { 112 return null; 113 } 114 115 /** 116 * 通過年齡查找對(duì)象 117 * 未實(shí)現(xiàn) 118 * @param age 119 * 對(duì)象年齡 120 * @return 對(duì)象數(shù)組，可能多個(gè) 121 */ 122 public Person[] searchPersonByAge(int age) { 123 return null; 124 } 125 126 /** 127 * 通過編號(hào)查找對(duì)象 128 * 由于編號(hào)是唯一標(biāo)識(shí)，循環(huán)遍歷查找并返回即可 129 * @param personNo 130 * 對(duì)象編號(hào) 131 * @return 查找到的對(duì)象或者null 132 */ 133 public Person searchNode(int personNo) { 134 Person p = null; 135 for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) { 136 if (pcn.person.personNo == personNo) { 137 p = pcn.person; 138 } 139 } 140 return p; 141 } 142 143 /** 144 * 通過原對(duì)象修改及傳入值修改該對(duì)象屬性 145 * 146 * @param personNo 147 * 要修改的對(duì)象編號(hào) 148 * @param value 149 * 通過傳入值的類型判斷修改 只能修改姓名或年齡 150 */ 151 public void editNode(int personNo, Object value) { 152 // 通過作為唯一標(biāo)識(shí)的編號(hào)查找到對(duì)象 153 Person target = searchNode(personNo); 154 if (target == null) { // 如果對(duì)象為null 155 return; 156 } 157 if (value == null) { // 如果傳入?yún)?shù)為null 158 return; 159 } 160 // 如果傳入?yún)?shù)為字符串類型 161 if (value.getClass() == java.lang.String.class) { 162 target.name = value.toString(); 163 return; 164 } 165 try { 166 // 如果傳入?yún)?shù)為整型 167 target.age = Integer.parseInt(value.toString()); 168 return; 169 } catch (Exception ex) { 170 // 如果傳入?yún)?shù)類型錯(cuò)誤 171 return; 172 } 173 } 174 175 /** 176 * 通過對(duì)象編號(hào)打印對(duì)象 177 * 178 * @param personNo 179 * 對(duì)象編號(hào) 180 */ 181 public void printNode(int personNo) { 182 Person target = searchNode(personNo); 183 if (target == null) { 184 return; 185 } 186 System.out.println(target.toString()); 187 } 188 189 /** 190 * 判斷指定對(duì)象是否存在鏈表中 191 * 192 * @param personNo 193 * 對(duì)象編號(hào) 194 * @return true表示存在該對(duì)象，false表示不存在該對(duì)象 195 */ 196 public boolean contains(int personNo) { 197 if (size != 0) { 198 for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) { 199 if (pcn.person.personNo == personNo) { 200 return true; 201 } 202 } 203 } 204 return false; 205 } 206 207 // 排序方法 208 209 /** 210 * 通過姓名排序 211 */ 212 public void sortByPersonName() { 213 } 214 215 /** 216 * 通過年齡排序 217 */ 218 public void sortByPersonAge() { 219 } 220 221 /** 222 * 默認(rèn)排序，通過編號(hào)排序 223 * 使用冒泡排序，增加了判斷以提高效率 224 */ 225 public void sort() { 226 boolean jx = true; // 冒泡排序的簡化方法 227 for (PersonChainNode pcn = head; pcn != null && jx; pcn = pcn.nextNode) { 228 jx = false; 229 for (PersonChainNode pc = head; pc != null && pc.nextNode != null; pc = pc.nextNode) { 230 if (pc.person.personNo > pc.nextNode.person.personNo) { 231 Person temp = pc.person; 232 pc.person = pc.nextNode.person; 233 pc.nextNode.person = temp; 234 jx = true; 235 } 236 } 237 } 238 } 239 240 /** 241 * 打印整個(gè)鏈表 242 */ 243 public void printAll() { 244 if (size != 0) { 245 for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) { 246 System.out.println(pcn.person.toString()); 247 } 248 } 249 } 250 }  2012-04-11 21:33:32 那么實(shí)際上呢，我們?cè)贘ava編程中使用的LinkedList就是在其內(nèi)部維護(hù)著一個(gè)鏈表。 實(shí)際上的操作不外乎增刪改查，不同的是由于高度封裝，Jdk的LinkedList是使用索引來取得對(duì)象并進(jìn)行操作的。 和以上我的例子是不盡相同的，因?yàn)槲沂前踩凑兆约旱男枨髞碜龅?，這樣比較簡單，實(shí)際上為了代碼重用復(fù)用和擴(kuò)展。Jdk內(nèi)的鏈表節(jié)點(diǎn)不知道保存的信息，因此沒有辦法以除了索引之外的方式獲取元素。
今天課程到了Java集合框架，老師略微提了一下單向不循環(huán)鏈表。 我將老師的舉例改編一下，幫助大家理解： 老師需要找某一個(gè)同學(xué)，但是碰巧實(shí)在放假的時(shí)間內(nèi)。同學(xué)們所處的位置都不一樣。老師知道班長的手機(jī)號(hào)碼，所以老師打電話給了班長，班長說他也不知道，但是他知道'我'的電話，他又打給我，我也不知道那位同學(xué)的地址，我又繼續(xù)向下一個(gè)同學(xué)打電話，直到找到他。 那么在以上示例中，加入每一個(gè)同學(xué)都有另一個(gè)同學(xué)的電話（有且僅有一個(gè)）。 我們就可以說符合單向鏈表的環(huán)境了。大家可以理解記憶。
大家都知道，我們所創(chuàng)建的對(duì)象是保存在內(nèi)存中的。數(shù)組是如此，鏈表也是如此。 但是數(shù)組是一個(gè)整體空間，所有元素共用。就比如教室內(nèi)上課的同學(xué)們。教室的容量是固定的，同學(xué)可少不可多，老師若希望進(jìn)行查詢，能夠一眼看出來。 鏈表和其節(jié)點(diǎn)是不同的存儲(chǔ)位置，比如我們一個(gè)班畢業(yè)了。有的同學(xué)去了國外，有的去了北京。大家的位置不同，但是有一定聯(lián)系的。
2012-04-23 19:16:20
|
|
|
