計算機是進行 「數(shù)據(jù)處理」 的設(shè)備，而程序表示的就是處理順序和數(shù)據(jù)結(jié)構(gòu)。由于處理對象（數(shù)據(jù)）是存儲在 「內(nèi)存」 和 「磁盤」 上的，因此我們今天來聊聊內(nèi)存和磁盤。

內(nèi)存的物理機制

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

?

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

下圖是 「內(nèi)存IC」 的引腳配置示例。

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

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

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

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

向內(nèi)存IC讀寫數(shù)據(jù)

寫入數(shù)據(jù)

假設(shè)我們往內(nèi)存IC中寫入1字節(jié)的數(shù)據(jù)。

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

執(zhí)行完這些操作，就可以在 「內(nèi)存IC」 內(nèi)部寫入數(shù)據(jù)了。

讀取數(shù)據(jù)

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

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

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

?

內(nèi)存的邏輯模型

?內(nèi)存的邏輯模型是樓房

?

上圖表示的是，內(nèi)存為1KB時，有1024層的樓房，每層都有1字節(jié)的數(shù)據(jù)。并且地址的值是從上往下逐漸變大的。

不過，在實際的 「編程環(huán)境」 下，還包含著物理內(nèi)存中不存在的概念，那就是 「數(shù)據(jù)類型」 。在編程語言中的 「數(shù)據(jù)類型」 表示存儲的是何種類型的數(shù)據(jù)。從內(nèi)存來看，就是占用的內(nèi)存大?。ㄕ加械臉菍訑?shù)）的意思。

?即使是 「物理」 上以1個字節(jié)位單位來逐一讀取數(shù)據(jù)的內(nèi)存，在 「程序」 中，通過指定其類型，也能實現(xiàn)以 「特定字節(jié)數(shù)」 為單位來進行讀寫

?

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

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

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

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

這3個變量表示的是內(nèi)存的特定區(qū)域。

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

?

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

在3個變量的數(shù)據(jù)類型分別是

• char:1字節(jié)長度
• short:2字節(jié)長度
• long:4字節(jié)長度

因此，雖然同樣是數(shù)據(jù)123，存儲時其占據(jù)的內(nèi)存大小是不一樣的。

上面的示例圖中，采用的是 「將數(shù)據(jù)低位存儲在內(nèi)存低位地址」 的低字節(jié)序Little Endian方式。

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

數(shù)組是高效使用內(nèi)存的基礎(chǔ)

? 「數(shù)組」 是指多個 「同樣數(shù)據(jù)類型」 的數(shù)據(jù)在內(nèi)存中連續(xù)排列的形式。

?

作為數(shù)組元素的各個數(shù)據(jù)會通過 「連續(xù)的編號」 被區(qū)分開來，這個編號稱為 「索引」 。 「指定索引后，就可以對該索引對應(yīng)地址的內(nèi)存進行讀寫操作」 。

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

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

數(shù)組的定義中所指定的數(shù)據(jù)類型，表示一次能夠讀取的內(nèi)存大小。

?數(shù)組是使用內(nèi)存的基本，因為其他的內(nèi)存使用技能，每一種都需要以數(shù)組為基礎(chǔ)

?

棧、隊列以及環(huán)形緩沖區(qū)

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

?

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

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

?

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

使用棧

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

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

?當(dāng)我們需要 「暫時」 舍棄當(dāng)前的數(shù)據(jù)，隨后再 「恢復(fù)」 原貌時候，優(yōu)先選用棧

?

使用隊列

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

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

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

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

?

隊列一般是以環(huán)形緩沖區(qū)Ring Buffer的方式來實現(xiàn)的。

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

環(huán)形緩沖區(qū)的模型

鏈表

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

?

在數(shù)組的各個元素中， 「除了數(shù)據(jù)的值之外，通過為其附帶上下一個元素的索引」 ，即可實現(xiàn)鏈表。 「數(shù)據(jù)的值和下一個元素的索引組合在一起」 ，就構(gòu)成了數(shù)組的一個元素。

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

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

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

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

?

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

追加數(shù)據(jù)

function append(head,value) {
  // 哨兵節(jié)點 
  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;
}

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

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

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

刪除數(shù)據(jù)

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

?

「哨兵節(jié)點」 ，在刪除指定節(jié)點

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;
}

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

二叉樹

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

?二叉查找樹使 「數(shù)據(jù)搜索」 更有效。

?

?「我們這里不對具體的數(shù)據(jù)結(jié)構(gòu)進行詳細的介紹。如果了解更多關(guān)于數(shù)據(jù)結(jié)構(gòu)的和對應(yīng)的算法的東西，可以移步到我們之前的文章中?！?/strong> 總有一款適合你。