計算機是進行 「數據處理」 的設備，而程序表示的就是處理順序和數據結構。由于處理對象（數據）是存儲在 「內存」 和 「磁盤」 上的，因此我們今天來聊聊內存和磁盤。

內存的物理機制

?內存實際上是一種名為 「內存IC」 的電子元件。

?

「內存IC」 中有 「電源」 、 「地址信號」 、 「數據信號」 、 「控制信號」 等用于輸入輸出的大量 「引腳」 （IC的引腳），通過為其 「指定地址」 ，來進行數據的讀寫。

下圖是 「內存IC」 的引腳配置示例。

• VCC和GND是**「電源」**
• A0~A9是 「地址信號」 的引腳
• D0~D7是 「數據信號」 的引腳
• RD和WR是 「控制信號」 的引腳

將電源連接到VCC和GND后，就可以給其他引腳傳遞比如0或1這樣的信號。大部分情況下，+5V的 「直流電壓」 表示1,0V表示0。

• 「數據信號」 引腳有D0~D7共8個，表示 「一次可以輸入輸出8位」 (=1字節)的數據。
• 「地址信號」 引腳有A0~A9共10個，表示可以指定0000000000~1111111111共1024個地址

由于地址用來表示數據的存儲場所，因此我們可以得出這個 「內存IC」 可以存儲1024個1字節的數據。又因為1024=1K，所以內存IC的容量就是1KB。

向內存IC讀寫數據

寫入數據

假設我們往內存IC中寫入1字節的數據。

• 可以給VCC接入+5V,給GND接入0V的電源
• 并使用A0~A9的 「地址信號」 來指定**「數據的存儲場所」**
• 然后把數據的值輸入給D0~D7的數據信號
• 并**「把WR(write的縮寫)信號設定為1」**

執行完這些操作，就可以在 「內存IC」 內部寫入數據了。

讀取數據

在讀取數據時，只需要通過A0~A9的地址信號指定數據的存儲場所，然后再 「將RD(read的縮寫)信號設成1」 即可。執行完這些操作，指定地址中存儲的數據就會被輸出到D0~D7的數據信號引腳中。

像WR和RD這樣可以讓IC運行的信號稱為 「控制信號」 。

? 「內存IC」 內部有大量可以存儲8位數據的地方，通過地址指定這些場所，之后即可進行數據的讀寫。

?

內存的邏輯模型

?內存的邏輯模型是樓房

?

上圖表示的是，內存為1KB時，有1024層的樓房，每層都有1字節的數據。并且地址的值是從上往下逐漸變大的。

不過，在實際的 「編程環境」 下，還包含著物理內存中不存在的概念，那就是 「數據類型」 。在編程語言中的 「數據類型」 表示存儲的是何種類型的數據。從內存來看，就是占用的內存大小（占有的樓層數）的意思。

?即使是 「物理」 上以1個字節位單位來逐一讀取數據的內存，在 「程序」 中，通過指定其類型，也能實現以 「特定字節數」 為單位來進行讀寫

?

我們通過一個具體示例來進行說明。

下面是一個往a、b、c這三個變量中寫入數據123的C語言程序，

// 定義變量
char a;
short b;
long c;

// 給變量賦值
a = 123;
b = 123;
c = 123;

這3個變量表示的是內存的特定區域。

?通過使用變量，即便不指定 「物理地址」 ，也可以在程序中對內存進行讀寫。

?

這是因為，在程序運行時候，操作系統會 「自動決定」 變量的物理地址。

在3個變量的數據類型分別是

• char:1字節長度
• short:2字節長度
• long:4字節長度

因此，雖然同樣是數據123，存儲時其占據的內存大小是不一樣的。

上面的示例圖中，采用的是 「將數據低位存儲在內存低位地址」 的低字節序Little Endian方式。

由此，我們可以得出一個結論： 「根據程序中所指定的變量的數據類型的不同，讀寫的物理內存大小也會隨之發生變化」 。

數組是高效使用內存的基礎

? 「數組」 是指多個 「同樣數據類型」 的數據在內存中連續排列的形式。

?

作為數組元素的各個數據會通過 「連續的編號」 被區分開來，這個編號稱為 「索引」 。 「指定索引后，就可以對該索引對應地址的內存進行讀寫操作」 。

如下用C語言定義char類型、short類型、long類型三個數組。

char g[100];
short h[100];
long i[100];

數組的定義中所指定的數據類型，表示一次能夠讀取的內存大小。

?數組是使用內存的基本，因為其他的內存使用技能，每一種都需要以數組為基礎

?

棧、隊列以及環形緩沖區

?棧和隊列，都可以不通過指定地址和索引來對數組的元素進行讀寫。

?

棧和隊列的區別在于 「數據出入的順序是不同的」 。在對內存數據進行讀寫時， 「棧」 用的LIFO(Last Input First Out, 「后入先出」 )方式，而 「隊列」 用的是FIFO(First Input First Out, 「先進先出」 )方式。

?在內存中 「預留」 出棧和隊列所需要的空間，并確定好寫入和讀出的順序，就不用再指定地址和索引了

?

我們假定往棧中寫入數據的函數名為Push，把棧中讀出數據的函數名為Pop

使用棧

// 往棧中寫入數據
Push(123);  // 寫入123
Push(456);  // 寫入456
Push(789);  // 寫入789

// 從棧中讀出數據
j = Pop();  // 讀出789
k = Pop();  // 讀出456
l = Pop();  // 讀出123

?當我們需要 「暫時」 舍棄當前的數據，隨后再 「恢復」 原貌時候，優先選用棧

?

使用隊列

假定往隊列中寫入數據的函數名為EnQueue，把棧中讀出數據的函數名為DeQueue

// 往棧中寫入數據
EnQueue(123);  // 寫入123
EnQueue(456);  // 寫入456
EnQueue(789);  // 寫入789

// 從棧中讀出數據
m = DeQueue();  // 讀出123
n = DeQueue();  // 讀出456
o = DeQueue();  // 讀出789

?當我們需要處理 「通訊」 中發送的數據時，或由 「同時運行的多個程序」 所發送過來的數據時，會用到這種隊列中存儲的不規則數據進行處理的方法

?

隊列一般是以環形緩沖區Ring Buffer的方式來實現的。

假設我們要有6個元素的數組來實現一個隊列。這時可以從數組的 「起始位置」 開始有序地存儲數據，然后再按照存儲時的順序數據讀出。在數組的末尾寫入數據后，后一個數據就會被寫入數據的起始位置（此時數據已經被讀出所以該位置是空的）

環形緩沖區的模型

鏈表

?通過使用鏈表，可以更加高效地對數組數據(元素)進行 「追加」 和 「刪除」 處理

?

在數組的各個元素中， 「除了數據的值之外，通過為其附帶上下一個元素的索引」 ，即可實現鏈表。 「數據的值和下一個元素的索引組合在一起」 ，就構成了數組的一個元素。

由于鏈表末尾的元素沒有 「后續」 的數據，因此就需要用別的值（這里是-1）來填充。

在需要追加或刪除數據的情況下，使用鏈表是很高效的。

這里，我們把之前我們針對JS鏈表相關算法的一些技巧直接遷移過來了。這里使用 「哨兵節點」 來對鏈表操作進行簡化處理。

? 「哨兵節點」 是為了簡化處理鏈表 「邊界條件」 而引入的**「附加鏈表節點」**

?

哨兵節點通常位于 「鏈表的頭部」 ，它的值沒有任何意義。在一個有哨兵節點的鏈表中， 「從第二個節點開始才真正的保存有意義的信息」 。

追加數據

function append(head,value) {
  // 哨兵節點 
  let dumy = new ListNode(0);
  dumy.next = head;
  
  // 遍歷鏈表，直到鏈表尾部
  let node = dumy;
  while(node.next!=null){
    node = node.next;
  }

  node.next = new ListNode(value);
  return dumy.next;
}

首先，創建一個 「哨兵節點」 （該節點的 「值」 沒有意義 -即ListNode(0)參數為啥不重要），并把該節點當做鏈表的頭節點， 「把原始的鏈表添加到哨兵節點的后面」 （dumy.next = head）。

然后，返回真正的頭節點（哨兵節點的下一個節點）node.next

這里有一個小的注意點，就是在 「遍歷」 鏈表的時候，并不是直接對dumy進行處理，而是用了一個 「零時游標節點」 (node)。這樣做的好處就是，在append操作完成以后，還可以通過dumy節點來，直接返回鏈表的頭節點dumy.next。因為,dumy一直沒參與遍歷過程。

刪除數據

?為了刪除一個節點，需要找到被刪除節點的 「前一個節點」 ，然后把該節點的next指針指向它 「下一個節點的下一個節點」 。

?

「哨兵節點」 ，在刪除指定節點

function delete(head ,value){
  let dumy = new ListNode(0);
  dumy.next = head;
  
  let node = dumy;
  while(node.next!=null){
    if(node.next.value==value){
      node.next = node.next.next;
      barek;
    }
    node = node.next;
  }
  return dumy.next;
}

通過哨兵節點(dumy)直接將 「鏈表為空」 和 「被刪除節點是頭節點」 的兩種特殊情況，直接囊括了。用最少的代碼，處理最多的情況

二叉樹

「二叉樹查找樹」 是指在鏈表的基礎上往數組中追加元素時，考慮到數據的大小關系，將其分成左右兩個方向的表現形式。

?二叉查找樹使 「數據搜索」 更有效。

?

?「我們這里不對具體的數據結構進行詳細的介紹。如果了解更多關于數據結構的和對應的算法的東西，可以移步到我們之前的文章中。」 總有一款適合你。