⑴ 線性表鏈式存儲結構是什麼
線性表是一種邏輯結構，它有兩種存儲方式，順序存儲和鏈式存儲。
順序存儲對應的是順序表，鏈式存儲對應的有單鏈表，雙鏈表，循環鏈表以及靜態鏈表。
其中，線性表的鏈式存儲又稱為單鏈表。
註：雙鏈表、循環鏈表等都是由單鏈表演化而來。
單鏈表：一個後繼指針，一個頭結點和頭指針。每一個結點是存儲下一個結點的存儲位置，因此最後一個結點存儲null，也就是空值。
雙鏈表：雙鏈表結點中有兩個指針，prior和next，即有前驅指針和後繼指針，分別指向前驅和後繼結點。
循環鏈表：循環鏈表和單鏈表的區別在於最後一個結點的指針不是null（回到單鏈表的知識去看一下吧），而是指向頭結點，從而整個鏈表成為了一個環。
循環雙鏈表：循環雙鏈表中頭結點的指針prior指針還要指向表尾結點。
註：在循環雙鏈表L中，當循環雙鏈表為空表時，其頭結點的prior域和next域都等於L。
靜態鏈表：靜態鏈表是藉助數組來描述線性表的鏈式存儲結構。結點有data域和指針域next。按照我的理解：其實靜態鏈表和單鏈表在結構上差不太多，但是靜態鏈表又和順序表很像，可以把靜態鏈表看作是單鏈表和順序表的結合吧。
鏈式存儲結構就這幾種了。
⑵ 線性表- 順序存儲結構- 順序表
順序表
順序表的定義
( ) 順序存儲方法
即把線性表的結點按邏輯次序依次存放在一組地址連續的存儲單元里的方法
( ) 順序表(Sequential List)
用順序存儲方法存儲的線性表簡稱為順序表(Sequential List)
結點a i 的存儲地址
不失一般性 設線性表中所有結點的類型相同 則每個結點所佔用存儲空間大小亦相同 假設表中每個結點佔用c個存儲單元 其中第一個單
元的存儲地址則是該結點的存儲地址 並設表中開始結點a 的存儲地址(簡稱為基地址)是LOC(a ) 那麼結點a i 的存儲地址LOC(a i
)可通過下式計算
LOC(a i )= LOC(a )+(i )*c ≤i≤n
注意
在順序表中 每個結點a i 的存儲地址是該結點在表中的位置i的線性函數 只要知道基地址和每個結點的大小 就可在相同時間內求出任一結
點的存儲地址 是一種 隨機存取結構
順序表類型定義
#define ListSize //表空間的大小可根據實際需要而定 這里假設為
typedef int DataType; //DataType的類型可根據實際情況而定 這里假設為int
typedef struct {
DataType data[ListSize];//向量data用於存放表結點
int length;//當前的表長度
}SeqList;
注意
① 用向量這種順序存儲的數組類型存儲線性表的元素外 順序表還應該用一個變數來表示線性表的長度屬性 因此用結構類型來定義順序表類
型
② 存放線性表結點的向量空間的大小ListSize應仔細選值 使其既能滿足表結點的數目動態增加的需求 又不致於預先定義過大而浪費存儲
空間
③ 由於C語言中向量的下標從 開始 所以若L是SeqList類型的順序表 則線性表的開始結點a 和終端結點a n 分別存儲在L data[ ]和
L Data[L length ]中
④ 若L是SeqList類型的指針變數 則a 和a n 分別存儲在L >data[ ]和L >data[L >length ]中
順序表的特點
順序表是用向量實現的線性表 向量的下標可以看作結點的相對地址 因此順序表的的特點是邏輯上相鄰的結點其物理位置亦相鄰
lishixin/Article/program/sjjg/201311/23372
⑶ 敘述線性表兩種存儲結構各自的主要特點
兩種存儲結構各自的主要特點
1、順序存儲結構：存儲單元地址連續，它以「物理位置相鄰」來表示線性表中數據元素間的邏輯關系，可隨機存取表中任一元素。
2、鏈式存儲結構：存儲單元地址為任意一組，它的存儲單元可以是連續的，也可以是不連續的。
在表示數據元素之間的邏輯關系時，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置），這兩部分信息組成數據元素的存儲映像，稱為結點（node）。
(3)線性表結點的存儲地址擴展閱讀：
線性表結構特點
1、均勻性
雖然不同數據表的數據元素可以是各種各樣的，但對於同一線性表的各數據元素必定具有相同的數據類型和長度。
2、有序性
各數據元素在線性表中的位置只取決於它們的序號，數據元素之前的相對位置是線性的，即存在唯一的「第一個「和「最後一個」的數據元素，除了第一個和最後一個外，其它元素前面均只有一個數據元素(直接前驅)和後面均只有一個數據元素（直接後繼）。
⑷ 線性表的鏈式存儲結構及其內存單元的地址特點
線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。因此，為了表示每個數據元素 與其直接後繼數據元素 之間的邏輯關系，對數據元素 來說，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置）。由這兩部分信息組成一個"結點"（如概述旁的圖所示），表示線性表中一個數據元素。線性表的鏈式存儲表示，有一個缺點就是要找一個數，必須要從頭開始找起，十分麻煩
⑸ 線性表在鏈式存儲中各結點之間的地址
選D，鏈式存儲結構，也就是平時所說的鏈表，是依靠上一個結點記錄下一個結點的地址。。實際結點之間的地址是否連續並無大礙。。線性表中的順序表，也就是數組，各結點之間的地址才是連續的。。
⑹ 數據結構知識點總結
線性表的結點按邏輯順序依次存放在一組地址連續的存儲單元里。是隨機存取的順序存儲結構。順序存儲指內存地址是一塊的，隨機存取指訪問時可以按下標隨機訪問，存儲和存取是不一樣的。
用一組任意的存儲單元來依次存放線性表的結點，這組存儲單元即可以是連續的，也可以是不連續的，甚至是零散分布在內存中的任意位置上的。鏈表中結點的邏輯次序和物理次序不一定相同。
隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。先進先出。
串(String)是零個或多個字元組成的有限序列。長度為零的串稱為空串(Empty String)，它不包含任何字元。通常將僅由一個或多個空格組成的串稱為空白串(Blank String) 注意：空串和空白串的不同，例如「 」和「」分別表示長度為1的空白串和長度為0的空串。
串的表示和實現
數組和廣義表可看成是一種特殊的線性表，其特殊在於: 表中的元素本身也是一種線性表。內存連續。根據下標在O(1)時間讀/寫任何元素。
二維數組，多維數組，廣義表，樹，圖都屬於非線性結構
數組
數組的順序存儲：行優先順序；列優先順序。數組中的任一元素可以在相同的時間內存取，即順序存儲的數組是一個隨機存取結構。
關聯數組(Associative Array)，又稱映射（Map）、字典（ Dictionary）是一個抽象的數據結構，它包含著類似於(鍵，值)的有序對。 不是線性表。
廣義表
廣義表（Lists，又稱列表）是線性表的推廣。廣義表是n(n≥0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。若廣義表LS（n>=1)非空，則a1是LS的表頭，其餘元素組成的表(a2,…an)稱為LS的表尾。廣義表的元素可以是廣義表，也可以是原子，廣義表的元素也可以為空。表尾是指除去表頭後剩下的元素組成的表，表頭可以為表或單元素值。所以表尾不可以是單個元素值。
三個結論
考點
一種非線性結構。樹是遞歸結構，在樹的定義中又用到了樹的概念。
基本術語
1.樹結點：包含一個數據元素及若干指向子樹的分支；
2.孩子結點：結點的子樹的根稱為該結點的孩子；
3.雙親結點：B結點是A結點的孩子，則A結點是B結點的雙親；
4.兄弟結點：同一雙親的孩子結點；
5.堂兄結點：同一層上結點；
6.結點層次：根結點的層定義為1；根的孩子為第二層結點，依此類推；
7.樹的高（深）度：樹中最大的結點層
8.結點的度：結點子樹的個數，就是有幾個孩子
9.樹的度： 樹中最大的結點度。
10.葉子結點：也叫終端結點，是度為0的結點；
11.分枝結點：度不為0的結點（非終端結點）；
12.森林：互不相交的樹集合；
13.有序樹：子樹有序的樹，如：家族樹；
14.無序樹：不考慮子樹的順序；
二叉樹
二叉樹可以為空。二叉樹結點的子樹要區分左子樹和右子樹，即使只有一棵子樹也要進行區分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。
注意區分： 二叉樹、二叉查找樹/二叉排序樹/二叉搜索樹、二叉平衡(查找)樹
二叉樹遍歷
先序遍歷：根左右
中序遍歷：左根右
後序遍歷：左右根
層次遍歷：一維數組存儲二叉樹，總是以層次遍歷的順序存儲結點。層次遍歷應該藉助隊列。
二叉樹性質
1.在二叉樹的第 i 層上至多有2的i次冪-1個結點
2.深度為 k 的二叉樹上至多含 2的k次冪-1 個結點（k≥1）
3.樹與轉換後的二叉樹的關系：轉換後的二叉樹的先序對應樹的先序遍歷；轉換後的二叉樹的中序對應樹的後序遍歷
一些概念
1.路徑：從一個祖先結點到子孫結點之間的分支構成這兩個結點間的路徑；
2.路徑長度：路徑上的分支數目稱為路徑長度；
3.樹的路徑長度：從根到每個結點的路徑長度之和。
4.結點的權：根據應用的需要可以給樹的結點賦權值；
5.結點的帶權路徑長度：從根到該結點的路徑長度與該結點權的乘積；
6.樹的帶權路徑長度=樹中所有葉子結點的帶權路徑之和；通常記作 WPL=∑wi×li
7.哈夫曼樹：假設有n個權值(w1, w2, … , wn)，構造有n個葉子結點的二叉樹，每個葉子結點有一個 wi作為它的權值。則帶權路徑長度最小的二叉樹稱為哈夫曼樹。最優二叉樹。
圖搜索->形成搜索樹
1.窮舉法
2.貪心法。多步決策，每步選擇使得構成一個問題的可能解，同時滿足目標函數
3.回溯法，根據題意，選取度量標准，然後將可能的選擇方法按度量標准所要求順序排好，每次處理一個量，得到該意義下的最優解的分解處理
無向圖
1.迴路或環：第一個頂點和最後一個頂點相同的路徑。
2.簡單迴路或簡單環：除第一個頂點和最後一個頂點之外，其餘頂點不重復出現的迴路
3.連通：頂點v至v』 之間有路徑存在
4.連通圖：無向圖圖 G 的任意兩點之間都是連通的，則稱G是連通圖。
5.連通分量：極大連通子圖，子圖中包含的頂點個數極大
6.所有頂點度的和必須為偶數
有向圖
1.迴路或環：第一個頂點和最後一個頂點相同的路徑。
2.簡單迴路或簡單環：除第一個頂點和最後一個頂點之外，其餘頂點不重復出現的迴路。
3.連通：頂點v至v』之間有路徑存在
4.強連通圖：有向圖G的任意兩點之間都是連通的，則稱G是強連通圖。各個頂點間均可達。
5.強連通分量：極大連通子圖
6.有向圖頂點的度是頂點的入度與出度之和。鄰接矩陣中第V行中的1的個數是V的出度
7.生成樹：極小連通子圖。包含圖的所有n個結點，但只含圖的n-1條邊。在生成樹中添加一條邊之後，必定會形成迴路或環。
8.完全圖：有 n(n-1)/2 條邊的無向圖。其中n是結點個數。必定是連通圖。
9.有向完全圖：有n(n-1)條邊的有向圖。其中n是結點個數。每兩個頂點之間都有兩條方向相反的邊連接的圖。
10.一個無向圖 G=(V,E) 是連通的，那麼邊的數目大於等於頂點的數目減一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向圖，那麼它是強連通圖的必要條件是邊的數目大於等於頂點的數目：|E|>=|V|，而反之不成立。沒有迴路的無向圖是連通的當且僅當它是樹，即等價於：|E|=|V|-1。
圖的鄰接矩陣和鄰接表
1.鄰接矩陣和加權鄰接矩陣
深度優先搜索利用棧
深度優先遍歷類似於樹的先序遍歷，是樹的先序遍歷的推廣
廣度優先遍歷
圖的廣度優先遍歷就類似於樹的層序遍歷
每次遍歷一個連通圖將圖的邊分成遍歷所經過的邊和沒有經過的邊兩部分，將遍歷經過的邊同圖的頂點構成一個子圖，該子圖稱為生成樹。因此有DFS生成樹和BFS生成樹。
生成樹是連通圖的極小子圖，有n個頂點的連通圖的生成樹必定有n-1條邊,在生成樹中任意增加一條邊，必定產生迴路。若砍去它的一條邊，就會把生成樹變成非連通子圖
最小生成樹：生成樹中邊的權值(代價)之和最小的樹。最小生成樹問題是構造連通網的最小代價生成樹。
Kruskal演算法 ：令最小生成樹集合T初始狀態為空，在有n個頂點的圖中選取權值最小的邊並從圖中刪去，若該邊加到T中有迴路則丟棄，否則留在T中；依次類推，知道T中有n-1條邊為止
Prim演算法： 它的基本思想是以頂點為主導地位，從起始頂點出發，通過選擇當前可用的最小權值邊把頂點加入到生成樹當中來：
1.從連通網路N={V,E}中的某一頂點U0出發，選擇與它關聯的具有最小權值的邊（U0,V）,將其頂點加入到生成樹的頂點集合U中。
2.以後每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權值最小的邊(U,V),把它的頂點加入到集合U中。如此繼續下去，直到網路中的所有頂點都加入到生成樹頂點集合U中為止。
Prim演算法，Kruskal演算法和Dijkstra演算法都屬於貪心演算法
Dijkstra演算法適用於邊權值為正的情況，如果邊權值為負數就才用另一種最短路演算法Bellman-Ford演算法。該演算法是指從單個源點到各個結點的最短路，該演算法適用於有向圖和無向圖。復雜度O(n^2)
Dijkstra演算法圖文詳解
若從一個連通圖中刪去任何一個頂點及其相關聯的邊，它仍為一個連通圖的話，則該連通圖被稱為 重（雙）連通圖。
若連通圖中的某個頂點和其相關聯的邊被刪去之後，該連通圖被分割成兩個或兩個以上的連通分量，則稱此頂點為 關節點。
沒有關節點的連通圖稱為雙連通圖
1.生成樹的根結點，有兩個或兩個以上的分支，則此頂點(生成樹的根)必為關節點；
2.對生成樹上的任意一個非葉「頂點」，若其某棵子樹中的所有「頂點」沒有和其祖先相通的回邊，則該「頂點」必為關節點
拓撲排序。在用鄰接表表示圖時,對有n個頂點和e條弧的有向圖而言時間復雜度為O(n+e)。一個有向圖能被拓撲排序的充要條件就是它是一個有向無環圖。
AOV網(Activity On Vertex)：用頂點表示活動，邊表示活動的優先關系的有向圖稱為AOV網。AOV網中不允許有迴路，這意味著某項活動以自己為先決條件。
拓撲有序序列：把AOV網路中各頂點按照它們相互之間的優先關系排列一個線性序列的過程。若vi是vj前驅，則vi一定在vj之前；對於沒有優先關系的點，順序任意。
拓撲排序：對AOV網路中頂點構造拓撲有序序列的過程。方法：
採用 深度優先搜索 或者 拓撲排序 演算法可以判斷出一個有向圖中是否有環（迴路）。
深度優先搜索只要在其中記錄下搜索的節點數n，當n大於圖中節點數時退出，並可以得出有迴路。若有迴路，則拓撲排序訪問不到圖中所有的節點，所以也可以得出迴路。廣度優先搜索過程中如果訪問到一個已經訪問過的節點，可能是多個節點指向這個節點，不一定是存在環。
拓撲演算法描述 ：
AOE網：帶權的有向無環圖，其中頂點表示事件，弧表示活動，權表示活動持續時間。在工程上常用來表示工程進度計劃。
常用哈希函數
1.直接定址法。
2.數字分析法。
3.平方取中法。
4.折疊法。
5.除留余數法。
6.隨機數法。
沖突解決
1.開放定址法：當發生沖突時，形成一個探查序列，沿此序列逐個地址探查，知道找到一個空位置，將發生沖突的記錄放到該地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函數，m哈希表長，di增量序列。
2.鏈地址法：將所有關鍵字為同義詞的記錄存儲在一個單鏈表中，並用一維數組存放頭指針。
3.設有n個關鍵字具有相同的Hash函數值，則用線性探測法把這n個關鍵字映射到Hash表中需要做n (n-1)/2次線性探測。如果使用二次探測再散列法將這n個關鍵字存入哈希表，至少要進行n (n+1)/2次探測
4.Hash查找效率：裝填因子=表中記錄數/表容量
5.開哈希表——鏈地址法；閉哈希表——開放地址法
B樹的查找
時間復雜度O(logn)
B樹的插入
例：用1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15構建5階B樹
因為構建5階的B樹，所以每個節點的關鍵字個數范圍為[2,4]
插入11時，該節點的關鍵字個數超出范圍，進行分裂
之後直接插入4，8，13
當插入10時，節點關鍵字個數再次超出范圍
將子節點分裂
直接插入5，17，9，16，插入20
關鍵字個數超出范圍，進行分裂
繼續插入3
關鍵字個數超出范圍，進行分裂
繼續插入15
關鍵個數超出范圍，進行分裂
這時候根節點關鍵字個數也超出范圍，繼續分裂
B+的優點
1.單一節點存儲更多的元素，使得查詢的IO次數更少。
2.所有查詢都要查詢葉到葉子節點，查詢更加穩定
3.所有葉子節點形成有序鏈表，便於范圍查詢。
⑺ 線性表採用鏈式存儲時，結點的存儲地址是連續的嗎
用任意的一組存儲單元來存放線性表的結點，不同組的存儲單元既可以是連續的，也可以是不連續的。
線性表有順序表和鏈表兩種存儲結構。
順序表：線性表的結點按邏輯次序依次存放在一組地址連續的存儲單元里的方法。
鏈表：用一組任意的存儲單元來存放線性表的結點，這組存儲單元既可以是連續的，也可以是不連續的
(7)線性表結點的存儲地址擴展閱讀：
線性表分類：
我們說「線性」和「非線性」，只在邏輯層次上討論，而不考慮存儲層次，所以雙向鏈表和循環鏈表依舊是線性表。
在數據結構邏輯層次上細分，線性表可分為一般線性表和受限線性表。一般線性表也就是我們通常所說的「線性表」，可以自由的刪除或添加結點。受限線性表主要包括棧和隊列，受限表示對結點的操作受限制。
線性表優點：
線性表的邏輯結構簡單，便於實現和操作。因此，線性表這種數據結構在實際應用中是廣泛採用的一種數據結構。
參考資料：網路——線性表