如何彌補順序表的不足之處？

第一次學習線性表一定會馬上接觸到一種叫做順序表（順序存儲結構），經(jīng)過上一篇的分析順序表的優(yōu)缺點是很顯然的，它雖然能夠很快的訪問讀取元素，但是在解決如插入和刪除等操作的時候，卻需要移動大量的元素，效率較低，那么是否有一種方法可以改善或者解決這個問題呢？

首先我們需要考慮，為什么順序表中的插入刪除操作會涉及到元素的移動呢？

好家伙，問題就是圍繞著順序表的最大的特點出現(xiàn)的——順序存儲，相鄰放置元素，也就是說每個元素都是根據(jù)編號一個一個挨著的，這就導致了 插入或刪除后，為了仍然呈順序線性存儲，被操作元素后面的元素的位置均需要發(fā)生一定的變化，你應該能想象得到，在擁擠的隊伍中突然從中插入一個學生的場景，后面浩浩蕩蕩的人群，口吐芬芳的向后挪了一個空位，如果人群過大，重新排好隊也需要一定的時間

好嘛，人與人之間別這么擠在一起，每個人與人之間都流出一點空隙來，留一定的位置出來，好了，這好像是個辦法，但是負責一個一個與學生交流填表的老師可就不干了，這意味著我（找人）遍歷的時候，需要多跑好多路，浪費好多時間，先不說這個，體院館又不行了，你們這么個擺法，我這小館可放不下，這也就意味著空間復雜度增加了很多。

我們剛才所圍繞的都是在 "排隊" 的基本前提下的，但我們能想到的方法并不是很理想，那么我們索性就不排隊了，是不是能有更好的解決方式呢？

一個有效的方法：

讓同學們（元素）自己找位置隨便站，不過你要知道相對于自己下一位同學的位置，這樣既解決了空間上的問題，又能通過這種兩兩聯(lián)系的方式訪問（遍歷）到整個隊伍（數(shù)組），最重要的是，插入和離開同學，由于同學（元素）之間不存在了那種排隊，相鄰的特點，所以也不會說影響到過多的同學（元素）只需要和你插入位置的前后兩位同學溝通好就行了，反正別人也不知道你們之間發(fā)生了什么事

好了思路是有了，我們來看一種最常見的鏈表——單鏈表

單鏈表的基本結構

這種鏈表為什么被稱作單鏈表呢？這是因為它只含有一個地址域，這是什么意思呢？

我們在鏈表中擯棄了順序表中那種一板一眼的排隊方式，但是我們必須讓兩個應該相鄰的元素之間有一定的相互關系，所以我們選擇讓每一個元素可以聯(lián)系對應的下一個元素

而這個時候我們就需要給每個元素安排一個額外的位置，來存儲它的后繼元素的存儲地址，這個存儲元素信息的域叫做指針域或地址域，指針域中儲存的信息也叫作指針或者鏈，

我們用一張圖 看一下他的結構

結構中名詞解釋

頭指針：一個指向第一個節(jié)點地址的指針變量

????????頭指針具有標識單鏈表的作用，所以經(jīng)常用頭指針代表單鏈表的名字

頭結點：在單鏈表的第一個結點之前附設一個結點，它沒有直接前驅，稱之為頭結點

????????可不存信息，也可以作為監(jiān)視哨，或用于存放線性表的長度等附加信息

????????指針域中存放首元結點的地址

首元結點：存儲第一個元素的節(jié)點

為什么要附設一個頭結點

我們來解釋一下：

（1）鏈表如果為空的情況下，如果單鏈表沒有頭結點，那么頭指針就會指向NULL，如果加上頭結點，無論單鏈表是否為空，頭指針都會指向頭結點，這樣使得空鏈表與非空鏈表處理一致

（2）使首元結點前插入或刪除元素的時候，與后面操作相同，不需要產(chǎn)生額外的判斷分支，使得算法更加簡單

（以插入為例講解）在帶頭結點的情況下，在首元結點前插入或者刪除元素仍與在其他位置的操作相同，只需要將前一個元素（在這里是頭結點）的指針域指向插入元素，同時將插入元素的指針域指向原來的第二的元素

而無頭結點的情況由于，首元結點前沒有元素，只能通過修改head的前后關系，所以導致了 與在別的位置插入或刪除元素的操作不同，在實現(xiàn)這兩個功能的時候就需要額外的寫一個判斷語句來判斷插入的位置是不是首元結點之前的位置，增加了分支，代碼不夠簡潔

總結：頭結點的存在使得空鏈表與非空鏈表處理一致，也方便對鏈表首元結點前結點的插入或刪除操作

單鏈表的類型定義

###線性表的抽象數(shù)據(jù)類型定義

我們在給出單鏈表的定義之前我們還是需要先引入我們線性表的抽象數(shù)據(jù)類型定義

單鏈表的類型定義

單鏈表上的基本運算實現(xiàn)

(一) 單鏈表的初始化-構造函數(shù)

單鏈表的初始化就是創(chuàng)建一個帶頭節(jié)點的空鏈表，我們不需要設置其指針域，為空即可

注意：new 操作符代表申請堆內存空間，上述代碼中應該判斷是否申請成功，為簡單，默認為申請成功，實際上如果系統(tǒng)沒有足夠的內存可供使用，那么在申請內存的時候會報出一個 bad_alloc exception 異常

(二) 析構函數(shù)

當單鏈表對象脫離其作用域時，系統(tǒng)自動執(zhí)行析構函數(shù)來釋放單鏈表空間，其實也就是清空單鏈表內容，同時釋放頭結點

(三) 清空單鏈表

清空單鏈表的主要思想就是從頭結點開始逐步將后面節(jié)點釋放掉，但是我們又不想輕易的修改頭指針head的指向，所以我們引入一個工作指針，從頭結點一直移動到表尾，逐步釋放節(jié)點

下節(jié)知識分享我們將會講到，如何求單鏈表的表長以及遍歷單鏈表、插入，刪除節(jié)點等方法的實現(xiàn)，記得關注哦~

學習C/C++編程知識，提升C/C++編程能力，歡迎關注UP一起來成長！

另外，UP在主頁上傳了一些學習C/C++編程的視頻教程，有興趣或者正在學習的小伙伴一定要去看一看哦！會對你有幫助的~