順序表

一、數據是如何在內存中存儲的？

32位系統中char，int型數據在內存中的存儲方式：

• char占1byte（8bit）
• int占4byte（32bit）

假設我們有一個int類型的值，它從0x01開始，一個int占據4個字節，則其結束于0x04。

二、數據類型有什么意義？

它確定了一個特定類型的數據到底要申請多大的內存地址來存儲數據，并且決定取到的二進制數應該如何解釋。

三、同類型的數據在內存中是如何連續存儲的？

假設有一個四個數的集合 1、20、300、4000，將它們連續地存儲在一起時，在內存里的表現就像是它們緊挨著擠在一起。如果第一個元素從0x01開始，那整個集合就在0x16結束。代表集合的變量指向集合的開始地址0x01，因為一個int類型數據占據4個字節，所以第一個元素就是存儲在0x01-0x04的內存地址中，以此類推，就可以得到其他元素。

這種叫做：順序表的基本布局

四、不同類型的數據集合在內存中是如何存儲的？

當不同的元素要存儲一個集合里時，用偏移量定位獲取每個元素就靠不住了，因為不用數據類型在內存中占用的空間（字節）是不同的。

假設集合里有10、"a"、20、"b" 這四個元素，這時就不能采用上面那種連續存儲布局；而是，它們分散存儲在不同的地方。這時，就可以申請一塊4個元素大小的連續內存區域，里面存的就是對應的元素的內存地址。

這種叫做：元素外置的順序表

五、順序表在內存中的結構

要在內存中給集合開辟一塊區域，先要確定集合大小（容量）。另外，確定區域后，還要知道當前已經占用了幾個元素，一旦溢出，就需要重新申請更大的空間。

要表達這種結構，有兩種實現方式：

圖a是一體式結構：存儲表信息與元素存儲區信息安排在一塊存儲區里
圖b是分離式結構：表對象里只保存于整個表有關的信息（容量和元素個數），實際數據元素存放在另一個獨立的元素存儲區里，通過指針鏈接

二者區別：
如果增加元素超過了列表的最大存儲量時，則需要新建一個數據區.。
一體式結構若想更換數據區，則要整體更改；而分離式結構則只需要更改表信息區中的數據區鏈接地址即可，即該順序表對象不變。

六、順序表擴充

線性擴充：每次擴充增加固定數目的存儲位置，節省空間，操作次數多（以時間換空間）。

倍數擴充：浪費空間（以空間換時間），操作次數少，推薦。

?