順序存儲鏈式存儲有哪些查找方法

Ⅰ 順序查找與索引查找的區別

1、順序查找的基本思想
基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結點關鍵宇和給定值K相比較。若當前掃描到的結點關鍵字與K相等，則查找成功；若掃描結束後，仍未找到關鍵字等於K的結點，則查找失敗。

2、順序查找的存儲結構要求
順序查找方法既適用於線性表的順序存儲結構，也適用於線性表的鏈式存儲結構（使用單鏈表作存儲結構時，掃描必須從第一個結點開始）。

3、基於順序結構的順序查找演算法
（1）類型說明
typedef struct{
KeyType key；
InfoType otherinfo； //此類型依賴於應用
}NodeType；
typedef NodeType SeqList[n+1]； //0號單元用作哨兵

（2）具體演算法
int SeqSearch(Seqlist R，KeyType K)
{ //在順序表R[1..n]中順序查找關鍵字為K的結點，
//成功時返回找到的結點位置，失敗時返回0
int i；
R[0].key=K； //設置哨兵
for(i=n；R[i].key!=K;i--)； //從表後往前找
return i； //若i為0，表示查找失敗，否則R[i]是要找的結點
} //SeqSearch
④順序查找的優點
演算法簡單，且對表的結構無任何要求，無論是用向量還是用鏈表來存放結點，也無論結點之間是否按關鍵字有序，它都同樣適用。

⑤順序查找的缺點
查找效率低，因此，當n較大時不宜採用順序查找

索引查找分兩步進行：
① 將外存上含有索引區的頁塊送人內存，查找所需記錄的物理地址
② 將含有該記錄的頁塊送人內存
注意：
①索引表不大時，索引表可一次讀入內存，在索引文件中檢索只需兩次訪問外存：一次讀索引，一次讀記錄。
②由於索引表有序，對索引表的查找可用順序查找或二分查找等方法。

索引查找主要針對文件的

Ⅱ 順序查找法適用於查找順序存儲或鏈式存儲的線性表

對。

鏈式存儲的線性表的存取機制是順序的，要想查找位置為i的元素必須採用順序查找法；

順序存儲的線性表的存取機制是隨機的，要想查找位置為i的元素直接用下標法就可以了。

如果要查找元素e在線性表中的位置那麼對這兩種存儲結構而言，必須採用順序查找法了。

(2)順序存儲鏈式存儲有哪些查找方法擴展閱讀：

線性表結構特點：

1、均勻性：雖然不同數據表的數據元素可以是各種各樣的，但對於同一線性表的各數據元素必定具有相同的數據類型和長度。

2、有序性：各數據元素在線性表中的位置只取決於它們的序號，數據元素之前的相對位置是線性的，即存在唯一的「第一個「和「最後一個」的數據元素，除了第一個和最後一個外，其它元素前面均只有一個數據元素(直接前驅)和後面均只有一個數據元素（直接後繼）。

Ⅲ 在鏈式存儲的有序列表中進行查找

1、請您點擊好友列表上的「刷新」按鈕，嘗試多刷新幾次；
2、若刷新之後仍無法顯示好友，請您調整flash本地存儲，清空ie緩存後重新打開查看；
清空ie緩存方法請點擊這里查看。

Ⅳ 無序線性表和線性表的鏈式存儲結構用什麼方法查找

順序查找。回答完畢

Ⅳ 每種數據結構都具有插入、刪除和查找三種基本運算，這種說法對不對請詳細解答

每種數據結構都具有插入、刪除和查找三種基本運算，這種說法並不正確。

一般而言，並不是所有的數據結構都有這三種基本運算。

1. 比如多維數組，就沒有插入和刪除，可以看看，哪怕是二維數組，如果刪除其中某個元素，用行還是列來頂替，頂替後，二維數組不就出現缺口了。

2. 再比如說棧和隊列，一般並不需要查找(其實原則上說也不能查找，因為邏輯上其訪問點被嚴格限制在線性表的端點了，即使用順序存儲或者鏈式存儲可以在存儲結構中查找)

Ⅵ 誰知道數據結構第八章查找演算法中，順序查找法的鏈式存儲結構的演算法

還是遍歷
只不過由i++變成了p=p->next

Ⅶ 1． 用c語言編寫順序存儲結構下的順序查找法和鏈式存儲結構下的順序查找法。

是啊！而且非常重要它在筆試中佔30%！！！
這是我找到的一些資料：第一章 數據結構與演算法
1.1 演算法
1、演算法是指解題方案的准確而完整的描述。換句話說，演算法是對特定問題求解步驟的一種描述。
*：演算法不等於程序，也不等於計算方法。程序的編制不可能優於演算法的設計。
2、演算法的基本特徵
（1）可行性。針對實際問題而設計的演算法，執行後能夠得到滿意的結果。
（2）確定性。每一條指令的含義明確，無二義性。並且在任何條件下，演算法只有唯一的一條執行路徑，即相同的輸入只能得出相同的輸出。
（3）有窮性。演算法必須在有限的時間內完成。有兩重含義，一是演算法中的操作步驟為有限個，二是每個步驟都能在有限時間內完成。
（4）擁有足夠的情報。演算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態，這就是演算法執行的起點或依據。因此，一個演算法執行的結果總是與輸入的初始數據有關，不同的輸入將會有不同的結果輸出。當輸入不夠或輸入錯誤時，演算法將無法執行或執行有錯。一般說來，當演算法擁有足夠的情報時，此演算法才是有效的；而當提供的情報不夠時，演算法可能無效。
*：綜上所述，所謂演算法，是一組嚴謹地定義運算順序的規則，並且每一個規則都是有效的，且是明確的，此順序將在有限的次數下終止。
3、演算法復雜度主要包括時間復雜度和空間復雜度。
（1）演算法時間復雜度是指執行演算法所需要的計算工作量，可以用執行演算法的過程中所需基本運算的執行次數來度量。
（2）演算法空間復雜度是指執行這個演算法所需要的內存空間。
1.2 數據結構的基本概念
1、數據結構是指相互有關聯的數據元素的集合。
2、數據結構主要研究和討論以下三個方面的問題：
（1）數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構。
數據的邏輯結構包含：1）表示數據元素的信息；2）表示各數據元素之間的前後件關系。
（2）在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構。
數據的存儲結構有順序、鏈接、索引等。
1）順序存儲。它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構。
2）鏈接存儲。它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關系是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構。
3）索引存儲：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。
*：數據的邏輯結構反映數據元素之間的邏輯關系，數據的存儲結構（也稱數據的物理結構）是數據的邏輯結構在計算機存儲空間中的存放形式。同一種邏輯結構的數據可以採用不同的存儲結構，但影響數據處理效率。
（3）對各種數據結構進行的運算。
3、數據結構的圖形表示
一個數據結構除了用二元關系表示外，還可以直觀地用圖形表示。在數據結構的圖形表示中，對於數據集合D中的每一個數據元素用中間標有元素值的方框表示，一般稱之為數據結點，並簡稱為結點；為了進一步表示各數據元素之間的前後件關系，對於關系R中的每一個二元組，用一條有向線段從前件結點指向後件結點。
4、數據結構分為兩大類型：線性結構和非線性結構。
（1）線性結構（非空的數據結構）條件：1）有且只有一個根結點；2）每一個結點最多有一個前件，也最多有一個後件。
*：常見的線性結構有線性表、棧、隊列和線性鏈表等。
（2）非線性結構：不滿足線性結構條件的數據結構。
*：常見的非線性結構有樹、二叉樹和圖等。
1.3 線性表及其順序存儲結構
1、線性表由一組數據元素構成，數據元素的位置只取決於自己的序號，元素之間的相對位置是線性的。線性表是由n(n≥0)個數據元素組成的一個有限序列，表中的每一個數據元素，除了第一個外，有且只有一個前件，除了最後一個外，有且只有一個後件。線性表中數據元素的個數稱為線性表的長度。線性表可以為空表。
*：線性表是一種存儲結構，它的存儲方式：順序和鏈式。
2、線性表的順序存儲結構具有兩個基本特點：（1）線性表中所有元素所佔的存儲空間是連續的；（2）線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。
*：由此可以看出，在線性表的順序存儲結構中，其前後件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在後件元素的前面，可以通過計算機直接確定第i個結點的存儲地址。
3、順序表的插入、刪除運算（學吧學吧獨家稿件）
（1）順序表的插入運算：在一般情況下，要在第i（1≤i≤n）個元素之前插入一個新元素時，首先要從最後一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向後移動一個位置，移動結束後，第i個位置就被空出，然後將新元素插入到第i項。插入結束後，線性表的長度就增加了1。
*：順性表的插入運算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。
（2）順序表的刪除運算：在一般情況下，要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結束後，線性表的長度就減小了1。
*：進行順性表的刪除運算時也需要移動元素，在等概率情況下，平均需要移動（n-1）/2個元素。插入、刪除運算不方便。
1.4 棧和隊列
1、棧及其基本運算（學吧學吧獨家稿件）
棧是限定在一端進行插入與刪除運算的線性表。
在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最後被插入的元素，棧底元素總是最先被插入的元素。即棧是按照「先進後出」或「後進先出」的原則組織數據的。
棧具有記憶作用。
棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變數，此時指針無變化。
棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈式棧。
2、隊列及其基本運算
隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。尾指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。
隊列是「先進先出」或「後進後出」的線性表。
隊列運算包括：1）入隊運算：從隊尾插入一個元素；2）退隊運算：從隊頭刪除一個元素。
循環隊列及其運算：所謂循環隊列，就是將隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的後一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。
*：循環隊列中元素的個數=rear-front。
1.5 線性鏈表（學吧學吧獨家稿件）
1、線性表順序存儲的缺點（學吧學吧獨家稿件）：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數據元素時需要移動大量的數據元素；（2）線性表的順序存儲結構下，線性表的存儲空間不便於擴充；（3）線性表的順序存儲結構不便於對存儲空間的動態分配。
2、線性鏈表：線性表的鏈式存儲結構稱為線性鏈表，是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接來實現的。因此，在鏈式存儲方式中，每個結點由兩部分組成：一部分用於存放數據元素的值，稱為數據域；另一部分用於存放指針，稱為指針域，用於指向該結點的前一個或後一個結點（即前件或後件），如下圖所示：

線性鏈表分為單鏈表、雙向鏈表和循環鏈表三種類型。
在單鏈表中，每一個結點只有一個指針域，由這個指針只能找到其後件結點，而不能找到其前件結點。因此，在某些應用中，對於線性鏈表中的每個結點設置兩個指針，一個稱為左指針，指向其前件結點；另一個稱為右指針，指向其後件結點，這種鏈表稱為雙向鏈表，如下圖所示：

3、線性鏈表的基本運算
（1）在線性鏈表中包含指定元素的結點之前插入一個新元素。
*：在線性鏈表中插入元素時，不需要移動數據元素，只需要修改相關結點指針即可，也不會出現「上溢」現象（學吧學吧獨家稿件）。
（2）在線性鏈表中刪除包含指定元素的結點。
*：在線性鏈表中刪除元素時，也不需要移動數據元素，只需要修改相關結點指針即可。
（3）將兩個線性鏈表按要求合並成一個線性鏈表。
（4）將一個線性鏈表按要求進行分解。
（5）逆轉線性鏈表。
（6）復制線性鏈表。
（7）線性鏈表的排序。
（8）線性鏈表的查找。
*：線性鏈表不能隨機存取。
4、循環鏈表及其基本運算
在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對於空表和對第一個結點的處理必須單獨考慮，使空表與非空表的運算不統一。為了克服線性鏈表的這個缺點，可以採用另一種鏈接方式，即循環鏈表。
與前面所討論的線性鏈表相比，循環鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點，而循環鏈表的頭指針指向表頭結點；2）循環鏈表中最後一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。
下圖a是一個非空的循環鏈表，圖b是一個空的循環鏈表：

循環鏈表的優點主要體現在兩個方面：一是在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點；二是由於在循環鏈表中設置了一個表頭結點，在任何情況下，循環鏈表中至少有一個結點存在，從而使空表與非空表的運算統一。
*：循環鏈表是在單鏈表的基礎上增加了一個表頭結點，其插入和刪除運算與單鏈表相同。但它可以從任一結點出發來訪問表中其他所有結點，並實現空表與非空表的運算的統一。
1.6 樹與二叉樹（學吧學吧獨家稿件）
1、樹的基本概念
樹是一種簡單的非線性結構。在樹這種數據結構中，所有數據元素之間的關系具有明顯的層次特性。
在樹結構中，每一個結點只有一個前件，稱為父結點。沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
2、二叉樹及其基本性質
（1）什麼是二叉樹
二叉樹是一種很有用的非線性結構，它具有以下兩個特點：1）非空二叉樹只有一個根結點；2）每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹與右子樹。
*：根據二叉樹的概念可知，二叉樹的度可以為0（葉結點）、1（只有一棵子樹）或2（有2棵子樹）。
（2）二叉樹的基本性質（學吧學吧獨家稿件）
性質1 在二叉樹的第k層上，最多有 個結點。
性質2 深度為m的二叉樹最多有個 個結點。
性質3 在任意一棵二叉樹中，度數為0的結點（即葉子結點）總比度為2的結點多一個。性質4 具有n個結點的二叉樹，其深度至少為 ，其中 表示取 的整數部分。
3、滿二叉樹與完全二叉樹
滿二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。
完全二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
*：根據完全二叉樹的定義可得出：度為1的結點的個數為0或1。
下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：

完全二叉樹還具有如下兩個特性：
性質5 具有n個結點的完全二叉樹深度為 。
性質6 設完全二叉樹共有n個結點，如果從根結點開始，按層序（每一層從左到右）用自然數1，2，…，n給結點進行編號，則對於編號為k（k=1，2，…，n）的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點的編號為INT(k/2)。
②若2k≤n，則編號為k的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。
③若2k+1≤n，則編號為k的右子結點編號為2k+1；否則該結點無右子結點。
4、二叉樹的存儲結構
在計算機中，二叉樹通常採用鏈式存儲結構。
與線性鏈表類似，用於存儲二叉樹中各元素的存儲結點也由兩部分組成：數據域和指針域。但在二叉樹中，由於每一個元素可以有兩個後件（即兩個子結點），因此，用於存儲二叉樹的存儲結點的指針域有兩個：一個用於指向該結點的左子結點的存儲地址，稱為左指針域；另一個用於指向該結點的右子結點的存儲地址，稱為右指針域。
*：一般二叉樹通常採用鏈式存儲結構，對於滿二叉樹與完全二叉樹來說，可以按層序進行順序存儲。
5、二叉樹的遍歷（學吧學吧獨家稿件）
二叉樹的遍歷是指不重復地訪問二叉樹中的所有結點。二叉樹的遍歷可以分為以下三種：
（1）前序遍歷（DLR）：若二叉樹為空，則結束返回。否則：首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
（2）中序遍歷（LDR）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
（3）後序遍歷（LRD）：若二叉樹為空，則結束返回。否則：首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
1.7 查找技術（學吧學吧獨家稿件）
查找：根據給定的某個值，在查找表中確定一個其關鍵字等於給定值的數據元素。
查找結果：（查找成功：找到；查找不成功：沒找到。）
平均查找長度：查找過程中關鍵字和給定值比較的平均次數。
1、順序查找
基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。
在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。
順序查找一個具有n個元素的線性表，其平均復雜度為O（n）。
下列兩種情況下只能採用順序查找：
1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結構還是鏈式存儲結構，都只能用順序查找。
2）即使是有序線性表，如果採用鏈式存儲結構，也只能用順序查找。
2、二分法查找
思想：先確定待查找記錄所在的范圍，然後逐步縮小范圍，直到找到或確認找不到該記錄為止。
前提：必須在具有順序存儲結構的有序表中進行。
查找過程：
1）若中間項（中間項mid=(n-1)/2，mid的值四捨五入取整）的值等於x，則說明已查到；
2）若x小於中間項的值，則在線性表的前半部分查找；
3）若x大於中間項的值，則在線性表的後半部分查找。
特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。
*：二分法查找只適用於順序存儲的線性表，且表中元素必須按關鍵字有序（升序）排列。對於無序線性表和線性表的鏈式存儲結構只能用順序查找。在長度為n的有序線性表中進行二分法查找，其時間復雜度為O（log2n）。
1.8 排序技術（學吧學吧獨家稿件）
排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調整為有序記錄序列的一種操作。
1、交換類排序法（方法：冒泡排序，快速排序）。
2、插入類排序法（方法：簡單插入排序，希爾排序）。
3、選擇類排序法（方法：簡單選擇排序，堆排序）。
總結：各種排序法比較：

本章應考點撥：本章內容在筆試中會出現5-6個題目，是公共基礎知識部分出題量比較多的一章，所佔分值也比較大，約10分。

Ⅷ 數據結構的存儲方式有哪幾種

數據結構的存儲方式有順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法這四種。

1、順序存儲方式：順序存儲方式就是在一塊連續的存儲區域一個接著一個的存放數據，把邏輯上相連的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接掛安息來體現。順序存儲方式也稱為順序存儲結構，一般採用數組或者結構數組來描述。

2、鏈接存儲方法：它比較靈活，其不要求邏輯上相鄰的結點在物理位置上相鄰，結點間的邏輯關系由附加的引用欄位表示。一個結點的引用欄位往往指導下一個結點的存放位置。鏈接存儲方式也稱為鏈接式存儲結構，一般在原數據項中增加應用類型來表示結點之間的位置關系。

3、索引存儲方法：除建立存儲結點信息外，還建立附加的索引表來標識結點的地址。它細分為兩類：稠密索引：每個結點在索引表中都有一個索引項，索引項的地址指示結點所在的的存儲位置；稀疏索引：一組結點在索引表中只對應一個索引項，索引項的地址指示一組結點的起始存儲位置。

4、散列存儲方法：就是根據結點的關鍵字直接計算出該結點的存儲地址。

(8)順序存儲鏈式存儲有哪些查找方法擴展閱讀

順序存儲和鏈接存儲的基本原理

在順序存儲中，每個存儲空間含有所存元素本身的信息，元素之間的邏輯關系是通過數組下標位置簡單計算出來的線性表的順序存儲，若一個元素存儲在對應數組中的下標位置為i，則它的前驅元素在對應數組中的下標位置為i-1，它的後繼元素在對應數組中的下標位置為i+1。

在鏈式存儲結構中，存儲結點不僅含有所存元素本身的信息，還含有元素之間邏輯關系的信息。數據的鏈式存儲結構可用鏈接表來表示。其中data表示值域，用來存儲節點的數值部分。Pl，p2，…，Pill(1n≥1)均為指針域，每個指針域為其對應的後繼元素或前驅元素所在結點的存儲位置。

在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同；而在數據的鏈接存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到，訪問任一元素的時間與該元素結點在鏈式存儲結構中的位置有關。

Ⅸ 常用的存儲表示方法有哪幾種

咨詢記錄 · 回答於2021-09-11

Ⅹ 數據結構中有哪些查找，他們分別適用於查詢那種存儲結構

最常見的：
順序查找：適合順序結構和鏈式結構
二分查找：適合順序結構

其他的二叉查找樹、B-樹之類有自己的數據結構