成都網站建設、成都做網站的開發，更需要了解用戶，從用戶角度來建設網站，獲得較好的用戶體驗。創新互聯建站多年互聯網經驗，見的多，溝通容易、能幫助客戶提出的運營建議。作為成都一家網絡公司，打造的就是網站建設產品直銷的概念。選擇創新互聯建站，不只是建站，我們把建站作為產品，不斷的更新、完善，讓每位來訪用戶感受到浩方產品的價值服務。

我是荔園微風，作為一名在IT界整整25年的老兵，今天總結一下Visual C++環境下調試數據結構——線性表之順序存儲結構。?

線性表

線性表(Linear List):有限多個相同類型的數據元素類（集合）線性表是最簡單、最基本的數據結構。通俗地講，線性表就是所有的節點按“一個連著一個”的方式組成的一個整體。

線性表主要的存儲結構有順序存儲結構和鏈式存儲結構。線性表的基本運算主要有創建線性表、求線性表長度、取第i個節點、插入數據元素、刪除數據元素、按值查找數據元素。在實際的算法實現中，這些基本運算一般會放入程序頭部進行說明，供程序員進行調用。

順序存儲結構

順序存儲結構常采用數組方式實現。一維數組形式的順序存儲結構具體如下所示。順序表使用一個連續存儲空間相繼存放線性表的各個節點。

a1? ?a2? ?a3? ?a4? ?......? ?an? ?......? ......

1.數組

數組是一種把相同類型的若干元素，有序地組織起來的集合。集合名就是數組名。組成數組的各個元素稱為數組元素。通過數組元素的位置序號（下標），可獲得某數組元素的地址，進而得到該數組元素的值。數組在數據結構中常常用來實現向量和矩陣。

數據結構中，數組的運算通常有兩個：
(1)給定數組的下標，存取相應的數據元素
(2)給定數組的下標，修改對應的數據元素的值。

數組的運算通常不涉及插入和刪除運算。

一維數組即數組中每個元素都只有一個下標的數組。兩個一維數組組成二維數組，n個一維數組組成n維數組。假定a是數組的首地址，L是數組元素的長度，行優先存儲（先存儲第一行，然后存儲第二行，……，直至最后一行)，則數組某元素的地址對應關系見下。

數組類型? ? ? ? ? 數組表示形式? ? ? ? ? 某元素對應的存儲地址 一維數組? ? ? ? ? a[n]? ? ? ? ? ? ? ? ? ? ? ? ? 元素a[i]的存儲地址：a+(i-1)*L 二維數組? ? ? ? ? a[m][n](m行n列)? ? ? ?元素a[i][j]的存儲地址：a+(i*n+j)*L

2.稀疏矩陣

稀疏矩陣即矩陣中0元素個數遠遠多于非0元素，并且非0元素分布沒有規律。稀疏矩陣可以采用三元組數組和十字鏈表兩種存儲方式，兩種方式均只存儲非0元素。

三元組數組：非0元素用三元組(行號、列號、值)表示，并全部存儲在數組中。這也完成了稀疏矩陣的壓縮。下面給出了一個稀疏矩陣用三元組數組表示的例子。

0? ?0? ?6? ?0? ?9? ?0

7? ?0? ?0? ?0? ?0? ?0

0? ?0? ?0? ?0? ?0? ?0

0? ?0? ?6? ?0? ?0? ?0

0? ?3? ?0? ?0? ?2? ?0

0? ?0? ?0? ?0? ?0? ?1

以上矩陣用三無組表示為：

(1? ?3? ?6)

(1? ?5? ?9)

(2? ?1? ?7)

(4? ?3? ?6)

(5? ?2? ?3)

(5? ?5? ?2)

(6? ?6? ?1)

十字鏈表：非0元素均為十字鏈表的一個節點，節點有5個域(行號、列號、值、行和列的后繼指針)。 常見的特殊稀疏矩陣有上三角、下三角和三對角矩陣。具體特點見下。

上三角矩陣（當i>j時，矩陣元素aij=0）

a11? ?a12? ?a13? ?a14? ?a15

0? ? ? ?a22? ?a23? ?a24? ?a25

0? ? ? ?0? ? ? ?a33? ?a34? ?a35

0? ? ? ?0? ? ? ?0? ? ? ?a44? ?a45

0? ? ? ?0? ? ? ?0? ? ? ?0? ? ? ?a55

矩陣元素aij對應一維數組下標：(2n-i+2)*(i-1)/2+j-i+1 化簡為 (2n-i)*(i-1)/2+j

下三角矩陣（當i

a11? ?0? ? ? ?0? ? ? ?0? ? ? ?0

a21? ?a22? ?0? ? ? ?0? ? ? ?0

a31? ?a32? ?a33? ?0? ? ? ?0

a41? ?a42? ?a43? ?a44? ?0

a51? ?a52? ?a53? ?a54? ?a55

矩陣元素aij對應一維數組下標： (i+1)*i/2+j

三對角矩陣

a11? ?a12? ? 0??? ? ?0? ??? ?0??

a21? ?a22? ?a23? ??0? ? ? ?0

0? ? ? ?a32? ?a33? ?a34? ? 0

0? ? ? ?0? ? ? ?a43? ?a44? ?a45

0? ? ? ?0? ? ? ?0? ? ? ?a54? ?a55

矩陣元素aij對應一維數組下標： (i-1)*3-1+j-i+2?化簡后為 2*i+j-2

3.順序表的查找、插入和刪除

順序表的特點是：邏輯相鄰的數據元素，物理結構必相鄰。

(1)順序表的查找。順序表的查找需要比較元素大小。若順序表有Ｎ個元素，每個元素被找到的概率都是1/N；針對不特定的數據元素，查找第Ｍ個元素需要比較Ｍ次。故而比較次數的平均次數為：(1+…+N)/N=(N+1)/2，這也是順序表的平均查找長度。 (2)順序表的插入。若順序表有N個元素，在順序表的任何位置插入數據的概率相等，總的插入位置有N+1種可能，當插入在第Ｍ個元素前時，需要往后移動N-M+1個位置。插入一個元素，需移動的次數平均數為：[N+(N-1)+…+1]/(N+1)=Ｎ/2，這就是順序表的插入平均移動長度。 (3)順序表的刪除。在順序表的任何數據元素位置刪除數據元素的概率相等，被刪除的概率都是1/N，針對不特定的數據元素，刪除第Ｍ個元素后，需要移動后面(N-M)元素往前一位。 刪除一個元素，比較次數的平均數為：[(N-1)+(N-2)+…+1]/N=(N-1)/2，也就是順序表的平均刪除長度。

作者簡介：荔園微風，1981年生，高級工程師，浙大工學碩士，軟件工程項目主管，做過程序員、軟件設計師、系統架構師，早期的Windows程序員，Visual Studio忠實用戶，C/C++使用者，是一位在計算機界學習、拼搏、奮斗了25年的老將，經歷了UNIX時代、桌面WIN32時代、Web應用時代、云計算時代、手機安卓時代、大數據時代、ICT時代、AI深度學習時代、智能機器時代，我不知道未來還會有什么時代，只記得這一路走來，充滿著艱辛與收獲，愿同大家一起走下去，充滿希望的走下去。

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站名稱：VisualC++環境下調試數據結構——線性表（順序存儲結構）-創新互聯
URL網址：http://vcdvsql.cn/article16/ieegg.html

成都網站建設公司_創新互聯，為您提供做網站、電子商務、動態網站、微信小程序、企業網站制作、網站改版

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯