本章重點(diǎn)
鏈表的分類
帶頭雙向循環(huán)鏈表接口實(shí)現(xiàn)
順序表和鏈表的區(qū)別
緩存利用率參考存儲(chǔ)體系結(jié)構(gòu) 以及 局部原理性。
一、鏈表的分類
實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：
1. 單向或者雙向
2. 帶頭或者不帶頭
3. 循環(huán)或者非循環(huán)?
雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)：
- 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會(huì)單獨(dú)用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
- 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都 是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶 來很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡單了，后面我們代碼實(shí)現(xiàn)了就知道了。
二、帶頭雙向循環(huán)鏈表接口實(shí)現(xiàn)
1.申請(qǐng)結(jié)點(diǎn)：struct ListNode* BuyLTNode(LTDataType x)
動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)，函數(shù)返回的是一個(gè)指針類型，用malloc開辟一個(gè)LTNode大小的空間，并用node指向這個(gè)空間，再判斷是否為空，如為空就perror，顯示錯(cuò)誤信息。反之則把要存的數(shù)據(jù)x存到newnode指向的空間里面，把指針置為空。
// 申請(qǐng)結(jié)點(diǎn)
struct ListNode* BuyLTNode(LTDataType x)
{
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->data = x;
node->prev = node;
node->next = node;
return node;
}
2.初始化：struct ListNode* LTInit()
// 初始化
void LTInit(struct ListNode* phead)
{
phead = BuyLTNode(-1);
phead->prev = phead;
phead->next = phead;
}
我們首先看看這個(gè)初始化有什么問題嘛？
phead為空指針，說明我們的初始化沒有效果，這是因?yàn)閜head是函數(shù)里面的形參，出了作用域就銷毀，plsit仍然是空指針，形參的改變不能影響實(shí)參，但是我們可以通過返回phead的地址解決問題。
單鏈表開始是沒有節(jié)點(diǎn)的，可以定義一個(gè)指向空指針的結(jié)點(diǎn)指針，但是此鏈表不同，需要在初始化函數(shù)中創(chuàng)建個(gè)頭結(jié)點(diǎn)，它不用存儲(chǔ)有效數(shù)據(jù)。因?yàn)殒湵硎茄h(huán)的，在最開始需要讓頭結(jié)點(diǎn)的next和pre指向頭結(jié)點(diǎn)自己。
因?yàn)槠渌瘮?shù)也不需要用二級(jí)指針（因?yàn)轭^結(jié)點(diǎn)指針是不會(huì)變的，變的是next和pre，改變的是結(jié)構(gòu)體，只需要用結(jié)構(gòu)體針即可，也就是一級(jí)指針）為了保持一致此函數(shù)也不用二級(jí)指針，把返回類型設(shè)置為結(jié)構(gòu)體指針類型。
// 初始化 - 改變實(shí)參plsit
struct ListNode* LTInit()
{
struct ListNode* phead = BuyLTNode(-1);
phead->prev = phead;
phead->next = phead;
return phead;
}3.尾插：void LTPushBack(struct ListNode* phead, LTDataType x)
尾插首先要找到尾結(jié)點(diǎn)，再將要尾插的結(jié)點(diǎn)與尾結(jié)點(diǎn)和帶頭結(jié)點(diǎn)鏈接，由于是帶頭結(jié)點(diǎn)，所以此處不需要關(guān)注頭結(jié)點(diǎn)為空的問題。
// 尾插
void LTPushBack(struct ListNode* phead, LTDataType x)
{
assert(phead);
struct ListNode* tail = phead->prev;
struct ListNode* newnode = BuyLTNode(x);
newnode->prev = tail;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;
}
4.尾刪：void LTPopBack(struct ListNode* phead)
尾刪只需要找到尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，再把帶頭結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)鏈接，釋放尾結(jié)點(diǎn)就完成了尾刪。
不過這里需要處理一下只有帶頭結(jié)點(diǎn)的刪除，此時(shí)真正的鏈表為空，此時(shí)就不能刪除了。
// 尾刪
void LTPopBack(struct ListNode* phead)
{
assert(phead);
assert(phead->next != phead);//鏈表為空
struct ListNode* tail = phead->prev;
struct ListNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->next = tailPrev;
}
5.頭插：void LTPushFront(struct ListNode* phead, LTDataType x)
頭插需要注意順序，如果先讓phead和newnode鏈接，那么就找不到phead結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，這樣就無法讓newnode和phead結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)鏈接。
// 頭插
void LTPushFront(struct ListNode* phead, LTDataType x)
{
assert(phead);
struct ListNode* newnode = BuyLTNode(x);
//順序不可顛倒
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
6.頭刪：void LTPopFront(struct ListNode* phead)
// 頭刪
void LTPopFront(struct ListNode* phead)
{
assert(phead);
assert(phead->next != phead);//鏈表為空
struct ListNode* first = phead->next;
struct ListNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
}
7.鏈表長度：int LTSize(struct ListNode* phead)
????????求鏈表長度，先把頭結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)存到cur中，再用while循環(huán)遍歷終止條件是cur等于頭結(jié)點(diǎn)，用size++記錄長度，并更新cur，最后返回size，32位機(jī)器下是無符號(hào)整型size_t。
（ 此類型可以提高代碼的可移植性，有效性，可讀性。此鏈表長度可能是字符型或者數(shù)組整型，他可以提供一種可移植方法來聲明與系統(tǒng)中可尋址的內(nèi)存區(qū)域一致的長度，而且被設(shè)計(jì)的足夠大，能表示內(nèi)存中任意對(duì)象的大?。?/p>
????????注意這里求鏈表長度不需要求帶頭結(jié)點(diǎn)，我們有時(shí)也經(jīng)?？吹接捎趲ь^結(jié)點(diǎn)的數(shù)據(jù)沒有使用，就有的書上會(huì)把該數(shù)據(jù)存儲(chǔ)上鏈表的長度size=phead->data，然后插入數(shù)據(jù)phead->data++,刪除phead->--，但是這有個(gè)限制，這種寫法只適合int類型，如果我們寫出char類型的數(shù)據(jù)，存儲(chǔ)幾個(gè)數(shù)據(jù)char就保存不了，char類型的phead->data一直++最后就會(huì)溢出，所以不建議這種寫法。
// 鏈表長度
int LTSize(struct ListNode* phead)
{
assert(phead);
int size = 0;
struct ListNode* cur = phead->next;
while (cur != phead)
{
size++;
cur = cur->next;
}
return size;
}8.在pos的前面進(jìn)行插入：void LTInsert(struct ListNode* pos, LTDataType x)
斷言pos，不能為空，插入數(shù)據(jù)先申請(qǐng)一結(jié)點(diǎn)放到定義的newnode指針變量中，為了不用考慮插入順序，先把pos前面的存到posPrev中，然后就可以隨意鏈接：
posPrev指向新節(jié)點(diǎn)，新節(jié)點(diǎn)前驅(qū)指針指向posPrev，新節(jié)點(diǎn)指向pos，pos前驅(qū)指針指向新節(jié)點(diǎn)。
// 在pos的前面進(jìn)行插入
void LTInsert(struct ListNode* pos, LTDataType x)
{
assert(pos);
struct ListNode* posPrev = pos->prev;
struct ListNode* newnode = BuyLTNode(x);
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
9.刪除pos位置的結(jié)點(diǎn)：void LTErase(struct ListNode* pos)
刪除把pos位置之前的結(jié)點(diǎn)直接指向pos的下一個(gè)結(jié)點(diǎn)，把pos下一個(gè)結(jié)點(diǎn)的前驅(qū)指針指向pos之前的結(jié)點(diǎn)。
// 刪除pos位置的結(jié)點(diǎn)
void LTErase(struct ListNode* pos)
{
assert(pos);
struct ListNode* posPrev = pos->prev;
struct ListNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}?
10.雙向鏈表查找：struct ListNode* ListFind(struct ListNode* phead, LTDataType x)
查找把頭結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)存到cur，然后用while循環(huán)遍歷，終止條件是cur等于頭結(jié)點(diǎn)指針，如果cur等于x，直接返回cur指針，再更新cur，最后遍歷完返回NULL，表示沒有該數(shù)據(jù)。
// 雙向鏈表查找
struct ListNode* ListFind(struct ListNode* phead, LTDataType x)
{
assert(phead);
struct ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}11.銷毀：void LTDestroy(struct ListNode* phead)
釋放鏈表從頭開始釋放，把頭結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)存到cur中，再用用while循環(huán)，終止條件是cur不等于頭指針，在里面把cur下一個(gè)指針存到next中，釋放掉cur，再把next更新為cur。最后頭結(jié)點(diǎn)也是申請(qǐng)的，也得釋放。
這里需要注意，由于形參的改變不會(huì)影響實(shí)參，我們?cè)诤瘮?shù)內(nèi)部將phead置空是無意義的，我們需要在函數(shù)外面調(diào)用LTDestroy函數(shù)后，需要手動(dòng)將phead置空。
// 銷毀
void LTDestroy(struct ListNode* phead)
{
assert(phead);
struct ListNode* cur = phead->next;
while (cur != phead)
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}12.打?。簐oid LTPrint(struct ListNode* phead)
打印鏈表，先斷言phead，它不能為空，再把頭結(jié)點(diǎn)下個(gè)地址存到cur中，用while循環(huán)去遍歷，終止條件是等于頭指針停止，因?yàn)樗茄h(huán)的，并更新cur。
// 打印
void LTPrint(struct ListNode* phead)
{
assert(phead);
printf("phead<=>");
struct ListNode* cur = phead->next;
while (cur != phead)
{
printf("%d<=>", cur->data);
cur = cur->next;
}
}三、順序表和鏈表的區(qū)別
| 不同點(diǎn) | 順序表 | 鏈表 |
| 存儲(chǔ)空間上 | 物理上一定連續(xù) | 邏輯上連續(xù)，但物理上不一定 連續(xù) |
| 隨機(jī)訪問 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者刪除 元素 | 可能需要搬移元素，效率低 O(N) | 只需修改指針指向 |
| 插入 | 動(dòng)態(tài)順序表，空間不夠時(shí)需要 擴(kuò)容 | 沒有容量的概念 |
| 應(yīng)用場景 | 元素高效存儲(chǔ)+頻繁訪問 | 任意位置插入和刪除頻繁 |
| 緩存利用率 | 高 | 低 |
四、緩存利用率參考存儲(chǔ)體系結(jié)構(gòu) 以及 局部原理性。
1.存儲(chǔ)體系結(jié)構(gòu)
寄存器（Registers）：寄存器是CPU內(nèi)部的最快速存儲(chǔ)，用于存儲(chǔ)最常用的數(shù)據(jù)和指令。它們?cè)趫?zhí)行指令時(shí)起著重要作用，速度非常快。
高速緩存（Cache）：高速緩存是位于中央處理器（CPU）和主存儲(chǔ)器之間的一層快速存儲(chǔ)，用于臨時(shí)存放經(jīng)常訪問的數(shù)據(jù)和指令。它可以分為多個(gè)層次，如L1、L2和L3緩存，隨著級(jí)別的升高，容量逐漸增大，但速度逐漸降低。
主存儲(chǔ)器（Main Memory）：也稱為RAM（Random Access Memory），主存儲(chǔ)器是計(jì)算機(jī)中用于存放運(yùn)行中程序和數(shù)據(jù)的地方。它是CPU能夠直接訪問的存儲(chǔ)設(shè)備，速度比較快，但容量通常相對(duì)有限。
輔助存儲(chǔ)器（Secondary Storage）：這包括各種長期存儲(chǔ)設(shè)備，如硬盤驅(qū)動(dòng)器、固態(tài)硬盤、光盤、磁帶等。這些設(shè)備的容量通常很大，但速度較慢，用于持久性存儲(chǔ)和備份。
虛擬內(nèi)存（Virtual Memory）：虛擬內(nèi)存是一種在主存和輔助存儲(chǔ)之間創(chuàng)建的抽象層，允許程序使用比主存更大的地址空間。操作系統(tǒng)可以根據(jù)需要將數(shù)據(jù)從主存移到輔助存儲(chǔ)，以優(yōu)化內(nèi)存使用。
2.局部性原理
????????存儲(chǔ)體系結(jié)構(gòu)的局部性原理是指在計(jì)算機(jī)程序執(zhí)行過程中，訪問內(nèi)存的模式往往呈現(xiàn)出一定的規(guī)律性，即數(shù)據(jù)和指令的訪問并不是完全隨機(jī)的，而是傾向于集中在某些特定的內(nèi)存區(qū)域或者特定的數(shù)據(jù)塊上。這個(gè)原理分為兩種類型：時(shí)間局部性和空間局部性。
時(shí)間局部性（Temporal Locality）：時(shí)間局部性指的是一個(gè)被訪問過的內(nèi)存位置在未來的一段時(shí)間內(nèi)很可能會(huì)再次被訪問。這意味著程序在不久的將來可能會(huì)多次使用相同的數(shù)據(jù)或指令。時(shí)間局部性的實(shí)現(xiàn)依賴于高速緩存，因?yàn)榫彺婵梢詴簳r(shí)存儲(chǔ)最近使用過的數(shù)據(jù)，從而在未來的訪問中加速存取。
空間局部性（Spatial Locality）：空間局部性指的是在訪問某個(gè)內(nèi)存位置時(shí)，附近的內(nèi)存位置也很可能會(huì)被訪問。這種情況在程序中存在連續(xù)存儲(chǔ)、數(shù)組訪問等情況下特別明顯?？臻g局部性的實(shí)現(xiàn)同樣依賴于高速緩存，因?yàn)榫彺婵梢栽谝粋€(gè)較小的區(qū)域內(nèi)存儲(chǔ)多個(gè)相鄰的數(shù)據(jù)塊。
????????局部性原理對(duì)計(jì)算機(jī)性能具有重要意義。通過充分利用局部性，計(jì)算機(jī)系統(tǒng)可以更有效地使用高速緩存，減少主存訪問次數(shù)，從而提高數(shù)據(jù)訪問的速度和效率。這對(duì)于減少存儲(chǔ)層次之間的數(shù)據(jù)傳輸時(shí)間以及提高程序的整體性能至關(guān)重要。
????????舉例來說，如果一個(gè)循環(huán)中多次使用相同的數(shù)組元素，由于時(shí)間局部性，這些數(shù)組元素會(huì)被緩存在高速緩存中，從而避免了多次訪問主存。同樣，如果一個(gè)算法中需要順序訪問數(shù)組的各個(gè)元素，由于空間局部性，緩存中可能會(huì)存儲(chǔ)這些相鄰的數(shù)據(jù)塊，從而加速了后續(xù)的訪問。
3.為什么順序表的效率比鏈表效率高
順序表：順序表是一種將元素順序存儲(chǔ)在一塊連續(xù)的內(nèi)存區(qū)域中的數(shù)據(jù)結(jié)構(gòu)。由于順序表的元素在內(nèi)存中是相鄰存儲(chǔ)的，因此它充分利用了空間局部性。當(dāng)訪問一個(gè)元素時(shí)，由于它的相鄰元素也在內(nèi)存中，這些相鄰元素很可能也會(huì)被加載到高速緩存中，從而減少了主存訪問的次數(shù)。此外，由于順序表的元素是連續(xù)存儲(chǔ)的，通過數(shù)組索引可以直接計(jì)算出元素的地址，避免了鏈表節(jié)點(diǎn)的跳轉(zhuǎn)操作。
鏈表：鏈表是一種通過節(jié)點(diǎn)和指針連接元素的數(shù)據(jù)結(jié)構(gòu)，它的元素在內(nèi)存中不一定是連續(xù)存儲(chǔ)的。在鏈表中，每個(gè)節(jié)點(diǎn)都包含了數(shù)據(jù)以及指向下一個(gè)節(jié)點(diǎn)的指針。這種非連續(xù)的存儲(chǔ)方式可能導(dǎo)致空間局部性較差，因?yàn)樵谠L問一個(gè)節(jié)點(diǎn)時(shí)，并不保證它的相鄰節(jié)點(diǎn)會(huì)被加載到高速緩存中。這會(huì)導(dǎo)致更頻繁的主存訪問，從而降低了效率。
????????綜上所述，順序表相比鏈表具有更好的空間局部性。它的元素連續(xù)存儲(chǔ)，使得訪問一個(gè)元素時(shí)，附近的元素也可能在緩存中，從而減少了主存訪問的需求，提高了數(shù)據(jù)訪問的速度和效率。而鏈表的節(jié)點(diǎn)之間不一定相鄰存儲(chǔ)，導(dǎo)致空間局部性不如順序表，因此鏈表在訪問數(shù)據(jù)時(shí)可能需要更多的主存訪問操作，從而效率相對(duì)較低。
????????需要注意的是，對(duì)于插入、刪除等操作，鏈表在某些情況下可能更加靈活，因?yàn)樗鼈儾恍枰苿?dòng)大量的數(shù)據(jù)，而順序表在插入、刪除操作時(shí)可能需要進(jìn)行元素的移動(dòng)，可能會(huì)帶來一些開銷。所以，在選擇使用順序表還是鏈表時(shí)，需要根據(jù)具體的應(yīng)用場景和操作需求綜合考慮。
本章結(jié)束啦?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-660872.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-660872.html
到了這里，關(guān)于【編織時(shí)空四：探究順序表與鏈表的數(shù)據(jù)之旅】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
