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

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

線性表

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

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

順序存儲結構

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

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

1.數(shù)組

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

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

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

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

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

2.稀疏矩陣

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

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

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元素均為十字鏈表的一個節(jié)點，節(jié)點有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對應一維數(shù)組下標：(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對應一維數(shù)組下標： (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對應一維數(shù)組下標： (i-1)*3-1+j-i+2?化簡后為 2*i+j-2

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

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

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

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

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

網(wǎng)頁題目：VisualC++環(huán)境下調試數(shù)據(jù)結構——線性表（順序存儲結構）-創(chuàng)新互聯(lián)
URL分享：http://weahome.cn/article/ieegg.html