反直觀的隨機存取與串

記憶體

計算機資料結構是研究如何有效率運用計算機解決問題的資料組織方式，所以首要了解計算機最為重要的資料結構，記憶體，一個巨大規模的位元組集合。舉如作者本人使用型號 ASUS VivoBook S13 筆電的記憶體，共有8,434,892,800個位元組。

隨機存取

計算機的記憶體每個位元組均配發一個位址，處理器依位址存取記憶體位元組，所以處理器能處理的位址長度，決定其可存取記憶體的範圍。舉如 32 位元處理器可處理的位址長度為 32 位元，故至多存取容量為\(2^{32}=4,294,967,296\)以下位元組的記憶體。

直觀而言，存取檔案的時間與儲存位置有關，舉如作者公司檔案室自門口向前方配置多列檔案架，顯然要取離門口遠架上的檔案，較離門口近要多費一點時間。但是記憶體一個違反直觀特性是隨機存取，指的是存取記憶體位元組所需要的時間，與位元組所在的位置無關，亦即處理器存取位置1的位元組時間，與存取位置1,000,000者並無差異，在之後的資料結構設計經常可以發現運用上述特性來提供資料結構的組織。

再舉如一張周杰倫范特西卡帶， A面有愛在西元前、爸我回來了、簡單愛、忍者及開不了口五首歌，如聽完「愛在西元前」，相較於接續聽「爸我回來了」，相直接聽「開不了口」，先得讓卡帶快轉一陣子，顯示存取離卡帶目前位置較遠的歌，需要花費較長的時間。

同樣的鏈結串列結構、順序存取記憶體（磁帶）及直接存取記憶體（磁碟），位址大的資料比位址小的資料要花較多的時間存取。

串

串一組序對<索引,值>的集合，索引為一個整數，而值則為任意物件。索引可用來取存放特定的值。如下表為一個用來儲存前 5 個質數的序列：

索引	1	2	3	4	5
數	2	3	5	7	11

第一列為索引，第二列為值。像是索引 1 可存取 2 這個質數，索引 5 可存取 11 這個質數，串可以將物件集合使用簡單的整數來組織。

記憶體可視為一個巨大的串，其索引即位址，每個位址可存取 1 位元組(8位元)的資料，

如果想組織一組元素超過1位元組的串，則可以將一組連續記憶體區塊劃分成串元素個數之槽，每個槽即串元素長度上開記憶體區塊的起始位元組稱基底，而該區塊各個槽的起始位址算法如下：

\[ 槽起始位址 = 串起始位址 + 槽長度 * 索引值 \]

算法僅需讀取3項資料對其進行加法及乘法來求出槽起始位址，依記憶體隨機存取特性，讀取槽起始位址資料亦係常數時間，存取串元素係費時常數時間。

大部份程式語言都以 Array[index] 作為索引取值的語法，其中 index 為索引值；以 Array[index]=rvalue 作為索引賦值，其中 rvalue 為所要存放到槽中的新值，如下例：

/* array_memory.c */
#include <stdio.h>

void main(void) {
    int i;
    int a[5] = {2, 3, 5, 7, 11};
    for(i=0;i<5;i++)
       printf("%p %i\n", &a[i], a[i]);
}

上面 c 程式會印出 5 個整數串的位址如下：

位址	值
0060FEE8	2
0060FEEC	3
0060FEF0	5
0060FEF4	7
0060FEF8	11

從上表可以看到這個串起始位址為 0060FEE8，由相鄰槽位址差距 0060FEEC - 0060FEE8 = 4，可得串每個槽長度為 4 個位元組，表示機器上每個 int 型別佔 4 個位元組。