1.線性表
線性表是n個型別相同資料元素的有限序列，通常記作(a 0 , a 1 , …a i-1 , a i , a i+1 …,a n-1 )，
特性：相同資料型別，序列(順序性)，有限，
2.線性表的存盤結構
1.順序表--順序存盤結構
特點：在記憶體中分配連續的空間，只存盤資料，不需要存盤地址資訊，位置就隱含著地址，
優點：
1.節省存盤空間，因為分配給資料的存盤單元全用存放結點的資料（不考慮c/c++語言中陣列需指定大小的情況），結點之間的邏輯關系沒有占用額外的存盤空間，
2.索引查找效率高，即每一個結點對應一個序號，由該序號可以直接計算出來結點的存盤地址，
假設線性表的每個資料元素需占用K個存盤單元，并以元素所占的第一個存盤單元的地址作為資料元素的存盤地址，則線性表中序號為i的資料元素的存盤地址LOC(a i )與序號為i+1 的資料元素的存盤地址LOC(a i+1 )之間的關系為
LOC(a i+1 ) = LOC(a i ) + K
通常來說，線性表的i號元素a i 的存盤地址為
LOC(a i ) = LOC(a 0 ) + i×K
其中LOC(a 0 )為 0 號元素a 0 的存盤地址，通常稱為線性表的起始地址，
缺點：
1.插入和洗掉操作需要移動元素，效率較低，
2.必須提前分配固定數量的空間，如果存盤元素少，可能導致空閑浪費，
3.按照內容查詢效率低，因為需要逐個比較判斷
例：長度為n的陣列中洗掉元素，假設每個元素洗掉的概率是相同的，問時間復雜度是？
刪掉第n個元素，需要移動0個元素
刪掉第n-1個元素，需要移動1個元素
刪掉第n-2個元素，需要移動2個元素
....
刪掉第2個元素，需要移動n-2個元素
刪掉第1個元素，需要移動n-1個元素
所以平均時間頻度是：0*1/n + 1*1/n + 2*1/n + 3*1/n + + (n-1)*1/n = (n-1)*n/2 * 1/n = (n-1)/2
T(n) = (n-1)/2
T(n)= O(n)
2.鏈表--鏈式存盤結構
特點：資料元素的存盤對應的是不連續的存盤空間，每個存盤結點對應一個需要存盤的資料元素，
每個結點是由資料域和指標域組成， 元素之間的邏輯關系通過存盤節點之間的鏈接關系反映出來，
邏輯上相鄰的節點物理上不必相鄰，
缺點：
1、比順序存盤結構的存盤密度小 (每個節點都由資料域和指標域組成，所以相同空間內假設全存滿的話順序比鏈式存盤更多)，
2、查找結點時鏈式存盤要比順序存盤慢（每個節點地址不連續、無規律，導致按照索引查詢效率低下），
優點：
1、插入、洗掉靈活 (不必移動節點，只要改變節點中的指標，但是需要先定位到元素上)，
2、有元素才會分配結點空間，不會有閑置的結點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144281.html
標籤：其他