鏈表
補充知識
typedef
給類型換名字，比如
typedef struct Student
{
int sid;
char name[100];
char sex;
}ST;//ST就代表了struct Student
//即這上方一大坨都可以用ST表示
//原先結(jié)構(gòu)體定義對象是通過下面這種方式實現(xiàn)的
struct Student st;
//現(xiàn)在使用typedef后，即可用下方方式定義
ST st;
或者來一個結(jié)構(gòu)體指針定義。
typedef struct Student
{
int sid;
char name[100];
char sex;
}*PST;
//這樣PST等價于struct Student *
//這樣初始化后就可以直接初始化一個結(jié)構(gòu)體指針
PST ps = &st;
//之后ps進行指針的調(diào)用就行，例如下所示
ps->sid = 99;
離散存儲
離散的含義，任何一個點到其他點之間是有間距的。
定義
n個節(jié)點離散分配，彼此通過指針相連接，每個節(jié)點只有一個前驅(qū)節(jié)點，每個節(jié)點只有一個后繼節(jié)點，首節(jié)點沒有前驅(qū)節(jié)點，尾節(jié)點沒有后繼節(jié)點。
專業(yè)術(shù)語
- 首節(jié)點：第一個有效的節(jié)點。
- 尾節(jié)點：最后一個有效節(jié)點。
- 頭結(jié)點：在首節(jié)點的前面加上這個結(jié)點，即第一個有效節(jié)點前的節(jié)點叫做頭結(jié)點。頭結(jié)點里面沒有存放有效數(shù)據(jù)，也沒有存放鏈表有效節(jié)點的個數(shù)，其真正含義是可以方便我們對鏈表進行操作（增刪改查）。
- 頭指針：指向頭結(jié)點的指針變量（存放了頭結(jié)點的地址）。
- 尾指針：指向尾節(jié)點的指針變量。
確定一個鏈表需要幾個參數(shù)？
首節(jié)點可以通過頭結(jié)點推出來，所以不是必須的，尾指針是0，因為沒有后繼節(jié)點，所以尾指針也不是必須的。尾節(jié)點也不是必須的，找到最后空的就知道尾節(jié)點，所以也不是必須的。頭指針包含了指向頭結(jié)點的地址，所以頭結(jié)點也不是必須的，記下頭指針就行。首節(jié)點可以由頭結(jié)點推出來，所以首節(jié)點也不是必須的。所以綜上，只要知道頭結(jié)點的地址，就可以把整個鏈表的所有信息都找到。所以說確定一個鏈表只需要一個參數(shù)，即為頭指針。
頭結(jié)點的數(shù)據(jù)類型和首節(jié)點的數(shù)據(jù)類型是一樣的。
代碼
通過代碼來模擬鏈表。
每一個節(jié)點的數(shù)據(jù)類型都是一模一樣的，一個節(jié)點可以分成兩部分，一部分是存放有效的數(shù)據(jù)，另有一部分是存放指針，指向后面的一個節(jié)點。這樣就造成了每一個節(jié)點的數(shù)據(jù)類型是一樣的。這里面的指針指向的是第二個節(jié)點的整體。
所以現(xiàn)在是包含了一個數(shù)據(jù)域一個指針域，
typedef struct Node{
int data;//數(shù)據(jù)域
struct Node *pNext;//指針域
//這里的指針域指向的是與其數(shù)據(jù)類型一致，但是另外一個節(jié)點。（下一節(jié)點的地址）（本節(jié)點的指針指向了下一節(jié)點）
}NODE, *PNODE;
//NODE是struct Node類型，*PNODE是struct Node *類型，記住struct Node是包含了整個整體的，要帶上花括號{}，即struct Node{}
鏈表分類
- 單向鏈表
- 雙向鏈表：這下相比單鏈表，每個節(jié)點分成了三個部分，分別有指向自己的前驅(qū)和后繼的指針，以及存放有效值。
- 循環(huán)鏈表：能通過任何一個節(jié)點找到其他所有的節(jié)點，就是首尾節(jié)點連接了。
- 非循環(huán)鏈表
常見算法
- 遍歷
- 查找
- 清空
- 銷毀
- 求長度
- 排序
- 刪除節(jié)點
- 插入節(jié)點
狹義的算法是與數(shù)據(jù)的存儲方式密切相關(guān)的，廣義的算法是與數(shù)據(jù)的存儲方式無關(guān)。泛型是利用某種技術(shù)達到的效果就是，不同的存存儲方式，執(zhí)行的操作時是一樣的。(泛型是一種假象)
插入節(jié)點偽代碼：
r = p->next;
p->next = q;
q->next = r;
//
q->next = p->next;
p->next = q;
//以上兩種方法都能實現(xiàn)q節(jié)點插入到p和p.next中間
刪除節(jié)點的偽代碼：
r = p->next;
p->next = p-next->next;
free(r);
//C當中不會自動釋放內(nèi)存，所以得手動釋放內(nèi)存，free
//C++當中是delete
鏈表創(chuàng)建和常用算法
#include <iostream>
#include <cmalloc>
using namespace std;
typedef struct Node{
int data;//數(shù)據(jù)域
struct Node *pNext;//指針域
}Node, *PNODE;
//現(xiàn)在就是定義了這么一個數(shù)據(jù)類型，叫做struct Node。
//函數(shù)聲明
PNODE create_list(void);
void traverse_list(PNODE pHead);//遍歷
bool is_empty(PNODE pHead);//判斷是否為空，就看pHead->pNext == nullptr的結(jié)果
int length_list(PNODE);//鏈表長度
bool insert_list(PNODE, int, int);
bool delete_list(PNODE, int, int*);
//可以把刪除的結(jié)點放到第三個參數(shù)當中去，也就是delete刪除的元素可以暫存到第三個參數(shù)當中去。delete_list(pHead, 3, &val);
void sort_list(PNODE);//排序
int main(void){
PNODE pHead = nullptr;
//等價于struct Node *pHead = nullptr;
pHead = create_list();
//create_list()函數(shù)的功能就是創(chuàng)建一個非循環(huán)單向鏈表，然后把單向鏈表的首地址賦給pHead。
//創(chuàng)建一個非循環(huán)單向鏈表，并將該鏈表的頭結(jié)點地址，賦給pHead。
sort_list(pHead);
traverse_list(pHead);
//insert_list(pHead, 4, 33);
int len = length_list(pHead);
cout << "鏈表長度是： " << endl;
//這是代表遍歷的意思，之前也說了，推出鏈表的所有參數(shù)只需要一個頭結(jié)點指針（頭指針）就行。
if (is_empty(pHead))
cout << "鏈表為空" << "\n" << endl;
else
cout << "鏈表非空" << "\n" << endl;
return 0;
}
//因為動態(tài)內(nèi)存管理，在一個函數(shù)當中申請的內(nèi)存可以在另外一個函數(shù)當中調(diào)用。
//創(chuàng)建函數(shù)
PNODE create_list(void)//最后只要分配好的內(nèi)存地址就行
{
int len;//存放有效節(jié)點的個數(shù)
int val;//臨時存放用戶輸入的結(jié)點的值
//分配了一個不存放數(shù)據(jù)的頭結(jié)點
PNODE pHead = (PNODE)malloc(sizeof(NODE));
if (pHead == nullptr)
{
cout << "分配失敗，程序終止" << endl;
return -1;
}
PNODE pTail = pHead;
pTail->pNext = nullptr;//這樣永遠指向尾節(jié)點
cout << "請輸入您需要生產(chǎn)的鏈表節(jié)點的個數(shù)：len = " << endl;
cin >> len;
for(int i = 0; i < len; ++i)
{
cout << "請輸入第 " << i+1 << " 個節(jié)點的值： " << endl;//i+1是因為鏈表從1開始的，這里的i是從0開始的
cin >> val;
//每循環(huán)一次，就用pNew造出一個新的節(jié)點
PNODE pNew = (PNODE)malloc(sizeof(NODE));//臨時節(jié)點
if (pNew == nullptr)
{
cout << "分配失敗，程序終止" << endl;
return -1;
}
//總而言之就是利用pHead生成一個臨時節(jié)點，然后把數(shù)值放到臨時節(jié)點的數(shù)據(jù)域當中去，再把臨時節(jié)點掛到之前一個節(jié)點的后面，最后再把臨時節(jié)點清空。但是這樣有問題，每次新生成的結(jié)點都會掛到之前一個節(jié)點的后面，造成“一對多”的現(xiàn)象，所以解決方法就是，每次新生成的結(jié)點都要掛到整個鏈表的尾節(jié)點的后面。所以定義一個pTail永遠指向尾節(jié)點。
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = nullptr;
pTail = pNew;
}
return pHead;//返回頭結(jié)點地址
}
//遍歷函數(shù)
//主要思路，先定義一個指針p，指向第一個有效的結(jié)點，如果此時指向的結(jié)點不為空，就把數(shù)據(jù)域給輸出就行，再往后移一個。
void travese_list(PNODE pHead)
{
PNONDE p = pHead->pNext;
while(p != nullptr)
{
cout << p_data << endl;
p = p->pNext;//一定要往后移，往后移才能指向下一個
}
cout << "\n" << "輸出完畢" << endl;
return;
}
//判斷是否為空的函數(shù)
bool is_empty(PNODE pHead)
{
if(pHead->pNext == nullptr)
return true;
else
return false;
}
//長度函數(shù)
int length_list(PNODE pHead)
{
PNODE p = pHead->pNext;
int cnt = 0;
while(p->pNext != nullptr)
{
++cnt;
p = p->pNext;
}
return cnt;
}
//排序函數(shù)
//依次把數(shù)每次和后面的數(shù)進行比較，這下就是升序排序的
void sort_list(PNODE pHead)
{
int i, j, t;
int len = length_list(pHead);
PNODE p, q;
for (i = 0 ,p = pHead->pNext; i<len-1; ++i, p = p->pNext)
{
for (j = j+1, q = p->pNext; j<len; ++j, q = q->pNext)
{
if (p->data > q->data) //類似于數(shù)組中的a[i]>a[j]
{
t = p->data;//t = a[i];
p->data = q->data;//a[i] = a[j];
q->data = t;//a[j] = t;
}
}
}
return;
}
//聽完郝老師講的這里，我才真正知道在C++當中函數(shù)重載的具體意思，operator之類的醍醐灌頂。
//插入函數(shù)
//在pHead所指向的鏈表的第pos個節(jié)點的前面插入一個新的節(jié)點，該節(jié)點的值是val，并且pos的值是從1開始。記住pos不包含頭結(jié)點，而是從首節(jié)點（有效節(jié)點）開始。
bool insert_list(PNODE pHead, int pos, int val)
{
int i = 0;
PNODE p = pHead;
while(p != nullptr && i < pos-1)
//這里的p是代表不是最后一個，i<pos-1表示找到插入位置之前的結(jié)點。
//while函數(shù)的作用是將p移動到pos-1的位置，畫圖就好理解。
{
p = p->pNext;
++i;
}
if (i > pos-1 || p == nullptr)
//這里的if是判斷要插入的位置是否超出了鏈表多一個位置
//i>pos-1是判斷pos是否為小于1的數(shù)，若是則直接false
//p = nullptr是為了處理插入的位置，例如有5個節(jié)點，現(xiàn)在在第7個節(jié)點位置插入。因為這是接著while循環(huán)的，所以多一層if判斷經(jīng)過while循環(huán)后的p的變化，同時還能判斷是否為空鏈表的存在。
return false;
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if (pNew == nullptr)
{
cout << "動態(tài)內(nèi)存分配失敗" << "\n" << endl;
return -1;
}
//以上pos等于1的時候，不執(zhí)行前面兩個表達式，即while和if，直接執(zhí)行后面的，此時將新元素插入到頭結(jié)點和第一個有效節(jié)點之間。
pNew->data = val;
PNODE q = p->pNext;
p->pNext = pNew;
pNew->pNext = q;
return true;
}
//刪除函數(shù)
bool delete_list(PNODE p, int pos, int*pVal)
{
int i = 0;
PNODE p = pHead;
while(p->pNext != nullptr && i < pos-1)
{
p = p->pNext;
++i;
}
if (i > pos-1 || p->pNext == nullptr)
return false;
PNODE q = p->pNext;
*pVal = q->data;
//刪除p節(jié)點后面的結(jié)點
p->pNext = p->pNext->pNext;
free(q);
q = nullptr;
return true;
}
鏈表總結(jié)
狹義的講：數(shù)據(jù)結(jié)構(gòu)是專門研究數(shù)據(jù)存儲的問題，數(shù)據(jù)的存儲包含兩方面，個體的存儲，以及個體關(guān)系的存儲。算法是對存儲數(shù)據(jù)的操作。
廣義的講：數(shù)據(jù)結(jié)構(gòu)既包含數(shù)據(jù)的存儲也包含數(shù)據(jù)的操作，對存儲數(shù)據(jù)的操作就是算法。
算法：
狹義的講：算法是和數(shù)據(jù)的存儲方式密切相關(guān)。
廣義的講：算法和數(shù)據(jù)的存儲方式無關(guān)。
這就是泛型的思想。
數(shù)據(jù)的存儲結(jié)構(gòu)有幾種：
線性：連續(xù)存儲【數(shù)組】，離散存儲【鏈表】，線性結(jié)構(gòu)的應(yīng)用—棧，隊列。
鏈表的優(yōu)缺點：文章來源：http://www.zghlxwxcb.cn/news/detail-616747.html
- 插入和刪除快
- 存取元素速度慢
- 存儲容量無限
數(shù)組的優(yōu)缺點：文章來源地址http://www.zghlxwxcb.cn/news/detail-616747.html
- 存取速度很快
- 但事先必須知道數(shù)組的長度
- 插入刪除元素很慢
- 空間通常是有限制的
- 需要大塊連續(xù)的內(nèi)存塊
到了這里，關(guān)于Linked List的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
