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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

像WR和RD這樣可以讓IC運(yùn)行的信號(hào)稱為 「控制信號(hào)」 。

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

?

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

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

?

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

不過(guò)，在實(shí)際的 「編程環(huán)境」 下，還包含著物理內(nèi)存中不存在的概念，那就是 「數(shù)據(jù)類型」 。在編程語(yǔ)言中的 「數(shù)據(jù)類型」 表示存儲(chǔ)的是何種類型的數(shù)據(jù)。從內(nèi)存來(lái)看，就是占用的內(nèi)存大小（占有的樓層數(shù)）的意思。

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

?

我們通過(guò)一個(gè)具體示例來(lái)進(jìn)行說(shuō)明。

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

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

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

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

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

?

這是因?yàn)椋诔绦蜻\(yùn)行時(shí)候，操作系統(tǒng)會(huì) 「自動(dòng)決定」 變量的物理地址。

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

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

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

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

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

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

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

?

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

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

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

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

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

?

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

?棧和隊(duì)列，都可以不通過(guò)指定地址和索引來(lái)對(duì)數(shù)組的元素進(jìn)行讀寫(xiě)。

?

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

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

?

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

使用棧

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

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

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

?

使用隊(duì)列

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

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

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

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

?

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

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

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

鏈表

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

?

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

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

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

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

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

?

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

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

function append(head,value) {
  // 哨兵節(jié)點(diǎn) 
  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)建一個(gè) 「哨兵節(jié)點(diǎn)」 （該節(jié)點(diǎn)的 「值」 沒(méi)有意義 -即ListNode(0)參數(shù)為啥不重要），并把該節(jié)點(diǎn)當(dāng)做鏈表的頭節(jié)點(diǎn)， 「把原始的鏈表添加到哨兵節(jié)點(diǎn)的后面」 （dumy.next = head）。

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

這里有一個(gè)小的注意點(diǎn)，就是在 「遍歷」 鏈表的時(shí)候，并不是直接對(duì)dumy進(jìn)行處理，而是用了一個(gè) 「零時(shí)游標(biāo)節(jié)點(diǎn)」 (node)。這樣做的好處就是，在append操作完成以后，還可以通過(guò)dumy節(jié)點(diǎn)來(lái)，直接返回鏈表的頭節(jié)點(diǎn)dumy.next。因?yàn)?dumy一直沒(méi)參與遍歷過(guò)程。

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

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

?

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

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

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

二叉樹(shù)

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

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

?

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