軟考之路--數(shù)據(jù)結(jié)構之線性表

數(shù)據(jù)就是數(shù)，也就是我們通過觀察、實驗或計算得出的結(jié)果。數(shù)據(jù)有很多種，最簡單的就是數(shù)字。數(shù)據(jù)也可以是文字、圖像、聲音等。數(shù)據(jù)可以用于科學研究、設計、查證等。結(jié)構，組成整體的各部分的搭配和安排，兩者完美結(jié)合在一起，我們這樣需要重新認識她，對她

數(shù)據(jù)就是數(shù)值，也就是我們通過觀察、實驗或計算得出的結(jié)果。數(shù)據(jù)有很多種，最簡單的就是數(shù)字。數(shù)據(jù)也可以是文字、圖像、聲音等。數(shù)據(jù)可以用于科學研究、設計、查證等。結(jié)構，組成整體的各部分的搭配和安排，兩者完美結(jié)合在一起，我們這樣需要重新認識她，對她重新審視與定義：數(shù)據(jù)結(jié)構是程序設計的重要理論和技術基礎，她所討論的內(nèi)容和技術，對從事軟件項目的開發(fā)有重要作用，通過學習數(shù)據(jù)結(jié)構，我們學會從問題出發(fā)，分析和研究計算機加工的數(shù)據(jù)的特性，以便為應用所設計的數(shù)據(jù)懸著適當?shù)倪壿嫿Y(jié)構、存儲結(jié)構及其相應的操作方法，為提高應用計算機解決問題的效率服務。

學習希賽視頻有一段日子了，這一段日子夾雜的自考和等級考，夸張點兒來說，有過歡笑，也有過淚水，歡笑的是昨天等級考試抽到的兩道大題都是原題，淚水的是，第二題有一個空少些了一個return，又想起那句話，總是要等到考試的時候，才知道該念的書沒有念，大題一共六十分，如果按往年的算分制度，需要占百分之六十，也就是說六十分要考三十六分才算合格，可是我滿打滿算，最后一題只能拿到三十四分，可是后話是，過了我開心，過不了更開心，可以再學一遍C++`(*∩_∩*)′，今天小編主要來講解一下數(shù)據(jù)結(jié)構的數(shù)據(jù)表，首先，我們來看一下基本數(shù)據(jù)結(jié)構的一張圖：

了解了基本數(shù)據(jù)結(jié)構，進入到我們今天的主題線性表，該博文主要圍繞以下內(nèi)容展開進行闡述：

一、線性表<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjwvcD4KPHA+ICAgIDxzdHJvbmc+ICAgILjFxO6jujwvc3Ryb25nPs/f0NSx7crH1+688rWlo6zX7rv5sb6jrNKyysfX7rOj08O1xNK71tbP39DUveG5uaOsy/3T0MG91ta05rSitOa0ore9t6ijrMuz0PK05rSius3BtMq9tOa0oqOs1vfSqrXEu/mxvrLZ1/fKx7LlyOujrMm+s/26zbLp1dK1yKGjPC9wPgo8cD4gICA8c3Ryb25nPjwvc3Ryb25nPjxzdHJvbmc+t9bA4KO6PC9zdHJvbmc+z9/Q1LHtt9bOqsuz0PKx7brNwbSx7aOsxuTW0MG0se3T1rfWzqq1pcG0se2hotGtu7fBtLHtus3Lq8G0se2jrNLAtM69+NDQt9bO9qGjPC9wPgo8cD4gICAgCjxzdHJvbmc+y7PQ8rHtPC9zdHJvbmc+o6zI58/CzbzL+cq+o7o8L3A+CjxwPiAgICA8aW1nIHNyYz0="http://www.2cto.com/uploadfile/Collfiles/20140923/2014092309223650.png" alt="\">

順序結(jié)構：順序結(jié)構是最簡單的程序結(jié)構，也是最常用的程序結(jié)構，只要按照解決問題的順序?qū)懗鱿鄳恼Z句就行，它的執(zhí)行順序是自上而下，依次執(zhí)行。舉個簡單的例子，a = 3，b = 5，現(xiàn)交換a，b的值，這個問題就好像交換兩個杯子水，這當然要用到第三個杯子，假如第三個杯子是c，那么正確的程序為： c = a； a = b； b = c； 執(zhí)行結(jié)果是a = 5，b = c = 3。

鏈表，如下圖所示：

鏈表：鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。 相比于線性表順序結(jié)構，操作復雜。

鏈表的類別：單鏈表、循環(huán)鏈表、雙鏈表。如下圖所示：

數(shù)據(jù)域：存放數(shù)據(jù)；指針域：存放指向下一個節(jié)點的地址；循環(huán)鏈表：最后一個節(jié)點她的下一個節(jié)點是頭節(jié)點。

雙鏈表：有兩個指針域，從兩個不同的方向把鏈表鏈接起來。雙鏈表可以從兩個方向移動，單鏈表朝單一的方向移動，雙鏈表的靈活度優(yōu)于單鏈表。雙鏈表的開支會大一些，因為她有兩個指針域。 單雙鏈表的刪除和插入：單鏈表的刪除：結(jié)點的刪除，刪除a2，方法：把a1的指針域直接指向a3，跳過a2，就可以了，a2就從鏈表中刪除了，還有一個工作需要把a2釋放掉。把要刪除的前序結(jié)點，前序結(jié)點的next域指向她的后序結(jié)點。單鏈表的插入：刪除結(jié)點是把前序指向后序，那么插入一個結(jié)點就是一個逆向的過程，把新的結(jié)點，從需要插入的位置，把她的前序結(jié)點next域指向新加入的結(jié)點，再把新加入的結(jié)點的next域指向下一個結(jié)點，就可以了。雙鏈表的刪除和插入：牽涉兩個方面，從左至右列出來，從右至左列出來，并不是簡單的一條鏈過去，一條鏈過來就完成的，我們需要把四個步驟都寫出來，把兩個操作的第一步都先完成，完成之后，接著第二步。 順序表PK鏈表

二、隊列

概念：隊列是一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。比如，去食堂排隊，排頭最先買到菜，后面來的同學排的隊尾；進車站時，安檢行李，先進去的最先出來，后進去的后出來。

分類：順序隊列和循壞隊列；隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。在隊列這種數(shù)據(jù)結(jié)構中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將是最后被刪除的元素，因此隊列又稱為“先進先出”（FIFO—first in first out）的線性表。如下圖：

順序隊列：

循環(huán)隊列：

ps：“對”字寫錯了，大家不要見笑哦。

三、棧

棧：并不是一個實實在在存在的東西，是邏輯上的一個概念，一種思想，一種理念，她不像鏈式存儲和順序存儲一個一個結(jié)點，很有規(guī)律，她是在順序存儲和鏈式存儲之上的，是邏輯的概念，棧既可以用鏈式結(jié)構來實現(xiàn)，也可以用順序結(jié)構來實現(xiàn)--即數(shù)組。定義一個規(guī)則，先進后出即可。如下：

小編寄語：線性表（亦作順序表）是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構。線性表中數(shù)據(jù)元素之間的關系是一對一的關系，即除了第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。線性表的邏輯結(jié)構簡單，便于實現(xiàn)和操作。因此，線性表這種數(shù)據(jù)結(jié)構在實際應用中是廣泛采用的一種數(shù)據(jù)結(jié)構。其中棧和隊列是一種特殊的線性表，軟考之路，未完待續(xù)......

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com