用故事解釋順序結構與鏈式結構
好好學習，天天向上
本文已收錄至我的Github倉庫DayDayUP：github.com/RobodLee/DayDayUP，歡迎Star
⭐⭐⭐⭐⭐
轉載請註明出處：//blog.csdn.net/weixin_43461520/article/details/123962053
前言
這個學期我們有一門課，是關於資訊技術教學的，就是每位同學分配數據結構的一個章節，然後上台講一下。分給我的是順序結構和鏈式結構的內容，為了講得有意思點，我編了個小故事，並做了些動畫。感覺還不錯，動畫做了挺長時間的，為了不浪費我辛辛苦苦編的故事和做的動畫，所以水篇文章來分享一下。
電腦記憶體
不管是順序結構還是鏈式結構，都是對數據在記憶體中存儲方式的描述。所以為了能夠講明白這兩種數據結構，有必要先來介紹一下電腦的記憶體。
上面這張圖，圖中的每一行都是一個存儲單元，若干個存儲單元組合構成了存儲體。每個存儲單元都連接有一根字選線，對應記憶體地址。
比如現在讀取記憶體地址為 0 的存儲單元的數據：首先CPU通過地址匯流排將地址資訊發送給MAR，MAR再將地址給解碼器，解碼器可以通過地址選擇對應的字選線，然後給對應的存儲單元一個訊號。最後通過數據線(綠線)就可以將存儲單元中的二進位數據發送到MDR中。這樣就完成了數據的讀操作，如果是寫操作，只要通過讀/寫控制線來控制是讀還是寫，如果是寫，則是將MDR中的數據通過數據線發送到對應的存儲單元中。
這些都是電腦組成原理的一些知識，沒學過的小夥伴可能看的不太明白，沒關係，這裡只要知道一個概念就好，那就是 電腦記憶體是由若干存儲單元構成，每個存儲單元都有獨一無二的編號(記憶體地址)，電腦可以對指定記憶體地址的存儲單元進行讀 / 寫操作。
這就好比，電腦記憶體可以看做是一家賓館，每一個房間都是一個存儲單元，房間號對應的就是記憶體地址，房間里的房客就是存在記憶體中的數據。
順序結構
介紹順序結構之前，先來講一個小故事：
有一天，爺爺帶著七個葫蘆娃來城裡旅遊。
既然是來旅遊的，那麼總不能睡大街吧，所以爺爺和葫蘆娃們準備先找一家賓館住下。他們找了一家空房間比較多的賓館，爺爺一次性開了七個連在一起的房間，然後讓七個葫蘆娃依次住了進去。
從圖中可以看出，七個房間是挨在一起的，所以七個葫蘆娃也是一個一個按順序住在各自的房間里。像這樣的就是順序結構。
順序結構，它是指各數據元素依次存儲在電腦中一組地址連續的存儲單元中。採用這種存儲方式，在邏輯上前後相鄰的兩個元素在電腦記憶體中也是相鄰的。
順序結構對應的其實就是數組，那麼用程式碼該怎麼表示上面的例子呢：
程式碼中，通過new關鍵字開闢了一個大小為7的數組，就相當於爺爺開了七個房間，然後向數組裡存放了七個數據，相當於七個葫蘆娃依次住進了各自的房間里。
鏈式結構
介紹完了順序結構再來介紹一下鏈式結構。還是接著上面的故事說。
葫蘆娃們在這家賓館住了一段時間後，覺得住的有點不得勁，想換一家。但是爺爺想：在這住的好好的為什麼要換呢？但是拗不過這幾個小的，只能依著他們了，畢竟雙拳難敵十四手嘛，雖然爺爺長的比較壯，，，
然後他們就收拾東西來到了一家新的賓館。
由於這家賓館生意比較好，住的人有點多，沒有連在一起的七個房間了，爺爺索性就讓他們隨便住了，挑自己喜歡的房間住。
等住完了之後爺爺心裡想：這幾個小娃娃怎麼住的這麼分散，要是弄丟了可怎麼搞，不得心疼死我呀。
於是乎，爺爺就找到了前台小姐姐，找她要了七張小紙條。
然後爺爺將七張小紙條分給了葫蘆娃們，然後他們每個人都在小紙條上記著下一個葫蘆娃的房間號。這樣雖然幾個葫蘆娃都不住在一起，但是通過紙條上的房間號就可以依次找到下一個葫蘆娃的房間。這樣從大娃開始，就可以找到所有的葫蘆娃了。
鏈式結構的特點是存儲各個數據元素的電腦存儲單元的地址不一定是連續的，但是在邏輯上相鄰的。每個結點都包含數據域和指針域兩部分。
故事中所表示的就是鏈式結構。我們再來思考一個問題，現在通過紙條可以找到下一個葫蘆娃的房間，但是怎麼找到上一個呢？好像不可以，稍微做一下修改，比如現在每個葫蘆娃手上有兩張紙條，另一張紙條上記錄的是上一個葫蘆娃的房間號。
其實這個就是雙鏈表，每個結點都有兩個指針，分別指向上一個結點與下一個結點。
所以說，數據結構研究的就是數據如何在記憶體中存儲。儘管數據結構有多種，但是數據都是在記憶體中存放的，只不過約束條件不同，概念就有所區別。不管是棧、隊列等簡單一點的數據結構，還是樹、圖等複雜一點的數據結構，他們的實現方式無非就三種：順序存儲、鏈式存儲、順序存儲+鏈式存儲。bky
拓展
最後，我們再來拓展一個知識點，就是如何用順序結構和鏈式結構來實現棧。
棧是一種只能從棧頂存放數據和取出數據的數據結構。不能從棧底對元素進行操作。
如果採用順序結構實現，可以準備一個數組，規定數組起始位置為棧底，靠近末尾一側為棧頂。那麼添加和取出元素就只能從末尾一側進行操作了。
typedef struct {
ElemType data[MaxSize]; //用於存放數據
int top; //指向棧頂
} SqStack;
如果換做是鏈式結構。那麼規定表頭為棧底，表尾為棧頂。那麼就只能從表尾添加或移出元素。如果反過來規定表頭為棧頂，表尾為棧底也是可以的，反正只能從一端進行操作就符合棧的定義。
typedef struct StackNode {
ElemType data;
struct StackNode *next;
} *LinkStack;
總結
研究數據結構就是研究數據在記憶體中怎麼存儲，在學習某種新的數據結構時，先了解其定義，再思考它的實現方式以及如何在記憶體中存儲，便能很容易理解。
寫作不易，看完記得點贊哦~~~~
⭐⭐⭐⭐⭐
轉載請註明出處：//blog.csdn.net/weixin_43461520/article/details/123962053本文已收錄至我的Github倉庫DayDayUP：github.com/RobodLee/DayDayUP，歡迎Star
如果您覺得文章還不錯，請給我來個
點贊，收藏，關注學習更多編程知識，WeChat掃描下方二維碼關注公眾號『 R o b o d 』：
