鏈表
鏈表：結(jié)構(gòu)定義
鏈表是由一串節(jié)點串聯(lián)在一起的，鏈表的每個節(jié)點存儲兩個信息：數(shù)據(jù)+下一個節(jié)點的地址
分清楚兩個概念：什么是內(nèi)存內(nèi)部，什么是程序內(nèi)部
內(nèi)存內(nèi)部： 信息存儲在內(nèi)存空間里的
程序內(nèi)部： 通過什么信息，去操作結(jié)構(gòu)
如果想操作鏈表的話，我們依靠的是程序內(nèi)部的信息，而不是內(nèi)存內(nèi)部的信息；所以在操作過程中，這些程序內(nèi)部信息千萬不能丟了，因為如果一旦丟了，那么對于內(nèi)存內(nèi)部的信息，就永遠(yuǎn)失去了訪問的權(quán)限。
代碼
結(jié)構(gòu)定義
typedef struct Node{
int data;
struct Node *next;
} Node;
構(gòu)造節(jié)點
Node * getNewNode(int val)
{
Node *p = (Node*)malloc(sizeof(Node));
p->data = val;
p->next = NULL; // 新的節(jié)點的下一個指向空
return p;
}
刪除鏈表
循環(huán)遍歷節(jié)點，先用一個指針p指向頭節(jié)點，因為先需要移動到下一個節(jié)點，再銷毀前一個指針，所以需要一個q指針來記錄下一個節(jié)點，然后銷毀當(dāng)前節(jié)點指針p
void clear(Node *head)
{
if (head == NULL) return;
// 循環(huán)遍歷鏈表中每個節(jié)點, 當(dāng)遍歷不為空，就一直向后走
for (Node *p = head, *q; p; p = q) // p是當(dāng)前節(jié)點
{
q = p->next; // 先讓q指向下一個節(jié)點
free(p); // 再銷毀當(dāng)前節(jié)點
}
return;
}
鏈表：插入元素
插入過程的操作順序，直接影響了我們是否能正確插入一個元素
程序內(nèi)部信息：head變量：指向整個鏈表的頭地址，node變量：指向待插入的新節(jié)點
需要把4號節(jié)點插入到2節(jié)點后面
首先，需要一個指針p, 需要找到待插入位置的前一個元素，即1號節(jié)點，p指向1號元素
然后，讓新的節(jié)點(4號節(jié)點)指向2號元素
然后，讓1號元素指向新的節(jié)點(4號元素)：
此時，在邏輯結(jié)構(gòu)上，就已經(jīng)完成了插入操作：
代碼
因為這是無頭鏈表結(jié)構(gòu)，在實現(xiàn)插入操作的時候，返回的是完成插入之后新鏈表的首地址
無頭鏈表插入操作后鏈表的首地址是可能發(fā)生改變的。
第一種情況：鏈表為空，或者插入的位置是0位置（原來鏈表頭的位置），就會導(dǎo)致整個鏈表的頭地址發(fā)生改變 ，直接返回新節(jié)點
第二種情況： 鏈表不為空，且插入位置在0之后，就是一般的插入操作，返回原鏈表頭節(jié)點指針
p指針是用來找到待插入指針的前一個元素
Node * insert(Node *head, int pos, int val)
{
if (pos == 0)
{
Node *node = getNewNode(val); // 先創(chuàng)建新節(jié)點
node->next = head; // 讓新節(jié)點指向原來的頭節(jié)點
return node; // 直接返回新節(jié)點
}
Node *p = head; // p找到待插入位置的前一個元素
for (int i = 1; i < pos; i++) p = p->next; // p走到待插入位置的前一個位置
Node *node = getNewNode(val); // 創(chuàng)建新節(jié)點
node->next = p->next; // 先讓新節(jié)點的next指向待插入位置的節(jié)點，即p->next
p->next = node; // 再讓p的next指向新節(jié)點
// 此時邏輯上已經(jīng)完成了插入的操作
return head; // 返回原鏈表頭節(jié)點
}
鏈表：錯誤插入
由于鏈表的插入很容易犯錯，這里演示一個錯誤的插入操作
先找到待插入位置的前一個元素
正確的插入順序是，讓新的元素指向2號元素；錯誤的操作是，讓1號元素（待插入元素的前一個元素）指向新的元素(4號元素)，那么就會發(fā)現(xiàn)2號元素的地址信息丟失了，也就是發(fā)生內(nèi)存泄漏。
內(nèi)存泄漏： 其實寫的所有程序都占用內(nèi)存空間，2號元素和3號元素，依然占用著我們的內(nèi)存空間，但在程序中對這段信息沒有辦法進行操作。
對于中大型需要長期線上運行的系統(tǒng)，需要對內(nèi)存泄漏的問題及其關(guān)注和避免的。
鏈表：無頭鏈表
在頭部是不存儲信息的，所以在鏈表的頭部存儲的僅僅是一個指針。
鏈表：有頭鏈表
在頭部存儲信息，在鏈表的頭部存儲的是一個節(jié)點。只不過這個節(jié)點有存儲數(shù)據(jù)的區(qū)域，但我們不使用這個區(qū)域
虛擬頭節(jié)點： 一般就是有頭鏈表的頭節(jié)點
代碼演示
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
typedef struct Node{
int data;
struct Node *next;
} Node;
Node * getNewNode(int val)
{
Node *p = (Node*)malloc(sizeof(Node));
p->data = val;
p->next = NULL; // 新的節(jié)點的下一個指向空
return p;
}
Node *insert(Node *head, int pos, int val)
{
if (pos == 0)
{
Node *node = getNewNode(val); // 先創(chuàng)建新節(jié)點
node->next = head; // 讓新節(jié)點指向原來的頭節(jié)點
return node; // 直接返回新節(jié)點
}
Node *p = head; // p找到待插入位置的前一個元素
for (int i = 1; i < pos; i++) p = p->next; // p走到待插入位置的前一個位置
Node *node = getNewNode(val); // 創(chuàng)建新節(jié)點
node->next = p->next; // 先讓新節(jié)點的next指向待插入位置的節(jié)點，即p->next
p->next = node; // 再讓p的next指向新節(jié)點
// 此時邏輯上已經(jīng)完成了插入的操作
return head; // 返回原鏈表頭節(jié)點
}
void clear(Node *head)
{
if (head == NULL) return;
// 循環(huán)遍歷鏈表中每個節(jié)點, 當(dāng)遍歷不為空，就一直向后走
for (Node *p = head, *q; p; p = q) // p是當(dāng)前節(jié)點
{
q = p->next; // 先讓q指向下一個節(jié)點
free(p); // 再銷毀當(dāng)前節(jié)點
}
return;
}
void output_linklist(Node *head)
{
// 0 1 2
// 22->33->55
int n = 0;
for (Node *p = head; p; p = p->next) n += 1; // 先求鏈表的長度n
// 打印第一行序號
for (int i = 0; i < n; i++)
{
printf("%3d", i);
printf(" "); // 對應(yīng)鏈表的->兩個字符
}
printf("\n");
// 打印第二行鏈表
for (Node *p = head; p; p = p->next)
{
printf("%3d", p->data);
printf("->");
}
printf("\n\n");
return;
}
int main()
{
srand(time(0));
#define MAX_OP 7
Node *head = NULL;
for (int i = 0; i < MAX_OP; i++)
{
int pos = rand() % (i + 1), val = rand() % 100; // 這里的第一個pos因為是隨機數(shù)對1取余，永遠(yuǎn)都是0
printf("insert %d at %d to linklist\n", val, pos);
head = insert(head, pos, val);
output_linklist(head);
}
std::cin.get();
return 0;
}
輸出：
鏈表：花式查找操作的實現(xiàn)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#define DL 3
#define STR(n) #n
#define DIGIT_LEN_STR(n) "%" STR(n) "d"
typedef struct Node{
int data;
struct Node *next;
} Node;
Node * getNewNode(int val)
{
Node *p = (Node*)malloc(sizeof(Node));
p->data = val;
p->next = NULL; // 新的節(jié)點的下一個指向空
return p;
}
Node *insert(Node *head, int pos, int val)
{
if (pos == 0)
{
Node *node = getNewNode(val); // 先創(chuàng)建新節(jié)點
node->next = head; // 讓新節(jié)點指向原來的頭節(jié)點
return node; // 直接返回新節(jié)點
}
Node *p = head; // p找到待插入位置的前一個元素
for (int i = 1; i < pos; i++) p = p->next; // p走到待插入位置的前一個位置
Node *node = getNewNode(val); // 創(chuàng)建新節(jié)點
node->next = p->next; // 先讓新節(jié)點的next指向待插入位置的節(jié)點，即p->next
p->next = node; // 再讓p的next指向新節(jié)點
// 此時邏輯上已經(jīng)完成了插入的操作
return head; // 返回原鏈表頭節(jié)點
}
void clear(Node *head)
{
if (head == NULL) return;
// 循環(huán)遍歷鏈表中每個節(jié)點, 當(dāng)遍歷不為空，就一直向后走
for (Node *p = head, *q; p; p = q) // p是當(dāng)前節(jié)點
{
q = p->next; // 先讓q指向下一個節(jié)點
free(p); // 再銷毀當(dāng)前節(jié)點
}
return;
}
void output_linklist(Node *head, int flag = 0)
{
// 0 1 2
// 22->33->55
int n = 0;
for (Node *p = head; p; p = p->next) n += 1; // 先求鏈表的長度n
// 打印第一行序號
for (int i = 0; i < n; i++)
{
// printf("%3d", i);
printf(DIGIT_LEN_STR(DL), i);
printf(" "); // 對應(yīng)鏈表的->兩個字符
}
printf("\n");
// 打印第二行鏈表
for (Node *p = head; p; p = p->next)
{
// printf("%3d", p->data);
printf(DIGIT_LEN_STR(DL), p->data);
printf("->");
}
printf("\n");
if (flag == 0) printf("\n\n");
return;
}
int find(Node *head, int val)
{
// 查找，遍歷鏈表的每個節(jié)點
Node *p = head; // 當(dāng)前節(jié)點指針
int n = 0; // 用來記錄輸出元素個數(shù)
while (p)
{
if (p->data == val){
output_linklist(head, 1);
int len = n * (DL + 2); // 空字符個數(shù)
for (int i = 0; i < len; i++) printf(" "); // 輸出前面的空格
printf("^\n");
for (int i = 0; i < len; i++) printf(" "); // 輸出前面的空格
printf("|\n");
return 1;
}
n += 1;
p = p->next;
}
return 0;
}
int main()
{
srand(time(0));
#define MAX_OP 7
Node *head = NULL;
// 測試插入操作
for (int i = 0; i < MAX_OP; i++)
{
int pos = rand() % (i + 1), val = rand() % 100; // 這里的第一個pos因為是隨機數(shù)對1取余，永遠(yuǎn)都是0
printf("insert %d at %d to linklist\n", val, pos);
head = insert(head, pos, val);
output_linklist(head);
}
// 測試查找操作
int val;
while (scanf_s("%d", &val)){
if (!find(head, val)) printf("not found\n");
}
std::cin.get();
return 0;
}
輸出鏈表的生成：
輸出查找操作
鏈表：用有頭鏈表改寫插入操作
定義一個虛擬頭節(jié)點，然后定義一個指針p，指向虛擬頭節(jié)點
讓虛擬頭節(jié)點的下一節(jié)點為原來的頭指針，此時形成了一個有頭鏈表
然后開始插入操作，一樣的，先找到待插入位置的前一個元素位置，這時候因為在0位置前有一個虛擬頭節(jié)點，所以對于pos=0的情況，就是虛擬頭節(jié)點本身。
注意：虛擬頭節(jié)點的下一個節(jié)點才是要返回的頭節(jié)點
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#define DL 3
#define STR(n) #n
#define DIGIT_LEN_STR(n) "%" STR(n) "d"
typedef struct Node{
int data;
struct Node *next;
} Node;
Node * getNewNode(int val)
{
Node *p = (Node*)malloc(sizeof(Node));
p->data = val;
p->next = NULL; // 新的節(jié)點的下一個指向空
return p;
}
// 有頭鏈表的插入操作
Node *insert(Node *head, int pos, int val)
{
Node newhead, *p = &newhead;
newhead.next = head; // 讓虛擬頭節(jié)點的下一節(jié)點為head
// 此時已經(jīng)構(gòu)造了一個有頭鏈表
for (int i = 0; i < pos; i++) p = p->next; // 先找到待插入位置的前一位
Node *node = getNewNode(val);
node->next = p->next;
p->next = node;
return newhead.next; // 虛擬頭節(jié)點的下一個節(jié)點才是要返回的頭節(jié)點
}
void clear(Node *head)
{
if (head == NULL) return;
// 循環(huán)遍歷鏈表中每個節(jié)點, 當(dāng)遍歷不為空，就一直向后走
for (Node *p = head, *q; p; p = q) // p是當(dāng)前節(jié)點
{
q = p->next; // 先讓q指向下一個節(jié)點
free(p); // 再銷毀當(dāng)前節(jié)點
}
return;
}
void output_linklist(Node *head, int flag = 0)
{
// 0 1 2
// 22->33->55
int n = 0;
for (Node *p = head; p; p = p->next) n += 1; // 先求鏈表的長度n
// 打印第一行序號
for (int i = 0; i < n; i++)
{
// printf("%3d", i);
printf(DIGIT_LEN_STR(DL), i);
printf(" "); // 對應(yīng)鏈表的->兩個字符
}
printf("\n");
// 打印第二行鏈表
for (Node *p = head; p; p = p->next)
{
// printf("%3d", p->data);
printf(DIGIT_LEN_STR(DL), p->data);
printf("->");
}
printf("\n");
if (flag == 0) printf("\n\n");
return;
}
int find(Node *head, int val)
{
// 查找，遍歷鏈表的每個節(jié)點
Node *p = head; // 當(dāng)前節(jié)點指針
int n = 0; // 用來記錄輸出元素個數(shù)
while (p)
{
if (p->data == val){
output_linklist(head, 1);
int len = n * (DL + 2) + 1; // 空字符個數(shù)
for (int i = 0; i < len; i++) printf(" "); // 輸出前面的空格
printf("^\n");
for (int i = 0; i < len; i++) printf(" "); // 輸出前面的空格
printf("|\n");
return 1;
}
n += 1;
p = p->next;
}
return 0;
}
int main()
{
srand(time(0));
#define MAX_OP 7
Node *head = NULL;
// 測試插入操作
for (int i = 0; i < MAX_OP; i++)
{
int pos = rand() % (i + 1), val = rand() % 100; // 這里的第一個pos因為是隨機數(shù)對1取余，永遠(yuǎn)都是0
printf("insert %d at %d to linklist\n", val, pos);
head = insert(head, pos, val);
output_linklist(head);
}
// 測試查找操作
int val;
while (scanf_s("%d", &val)){
if (!find(head, val)) printf("not found\n");
}
std::cin.get();
return 0;
}
鏈表：循環(huán)鏈表
單向循環(huán)鏈表
單向循環(huán)鏈表：在單向鏈表的基礎(chǔ)上加一個循環(huán)結(jié)構(gòu)，循環(huán)結(jié)構(gòu)是指最后一個節(jié)點指向了第一個節(jié)點
注意： 在單向循環(huán)鏈表中的頭指針head指向整個鏈表的最后一個節(jié)點
為什么要指向最后一個節(jié)點：因為最后一個節(jié)點充當(dāng)著一個實實在在的鏈表中的節(jié)點，也充當(dāng)著一個虛擬頭節(jié)點。有了這個虛擬頭節(jié)點之后，當(dāng)需要插入節(jié)點到鏈表中時，插入到哪個位置就向后走幾步即可
代碼
結(jié)構(gòu)定義
與單向鏈表的節(jié)點定義一樣
typedef struct Node{
int data;
struct Node *next;
} Node;
構(gòu)造循環(huán)
Node *ConstructLoop(Node *head) // 構(gòu)造鏈表循環(huán)
{
if (head == NULL) return head;
Node *p = head;
while (p->next) p = p->next; // 找到鏈表的最后一個節(jié)點
p->next = head; //最后的節(jié)點的下一個節(jié)點指向頭節(jié)點
head = p; // 頭指針指向最后一個節(jié)點
return head; // 返回頭指針
}
刪除循環(huán)鏈表
與單向鏈表的刪除一樣
void clear(Node *head) // 刪除單向鏈表
{
if (head == NULL) return;
// 循環(huán)遍歷鏈表中每個節(jié)點, 當(dāng)遍歷不為空，就一直向后走
for (Node *p = head, *q; p; p = q) // p是當(dāng)前節(jié)點
{
q = p->next; // 先讓q指向下一個節(jié)點
free(p); // 再銷毀當(dāng)前節(jié)點
}
return;
}
單向循環(huán)鏈表：插入
如果頭指針head指向的不是鏈表最后一個節(jié)點，而是第一個節(jié)點，那么在插入元素到index=0的位置時，是不是要先找到0位置節(jié)點的前一個節(jié)點，那就是鏈表的最后一個節(jié)點，也就是說，為了在0位置插入一個節(jié)點，還要先遍歷完鏈表的全部節(jié)點才能進行插入操作，所以將頭指針head設(shè)置為鏈表最后一個節(jié)點是合理。
插入在index=0位置后，不需要修改head指向的節(jié)點，保持指向為最后一個節(jié)點即可。
插入到鏈表的最后一個節(jié)點的后面，則需要在插入完成后修改head指向的節(jié)點
代碼
Node *insertLoop(Node *head, int pos, int val)
{
int n = 1;
Node *q = head->next;
while (q != head) // 記錄循環(huán)鏈表的長度
{
n += 1;
q = q->next;
}
Node *p = head; // 當(dāng)前指針指向頭節(jié)點，相當(dāng)于單向鏈表的虛擬頭節(jié)點
for (int i = 0; i < pos; i++) p = p->next; // 找到待插入位置的前一位
Node *node = getNewNode(val);
// 插入操作
if (pos < n)
{
node->next = p->next;
p->next = node;
return head; // 如果插入的位置不是在最后一個節(jié)點之后，返回原頭指針
}
else
{
node->next = p->next;
p->next = node;
head = node; // 否則，頭指針指向最后一個節(jié)點
return head;
}
}
鏈表：雙向鏈表
雙向鏈表： 除了有指向下一個節(jié)點的變量next指針之外，還有指向上一個節(jié)點的變量pre指針
第一個節(jié)點的pre指針指向空地址
最后一個節(jié)點的next指針指向空地址
代碼
結(jié)構(gòu)定義
typedef struct BiNode{
int data;
struct BiNode *next;
struct BiNode *pre;
} BiNode;
構(gòu)造節(jié)點文章來源：http://www.zghlxwxcb.cn/news/detail-435968.html
BiNode *getNewBiNode(int val)
{
BiNode *p = (BiNode*)malloc(sizeof(BiNode));
p->data = val;
p->next = NULL;
p->pre = NULL;
return p;
}
刪除雙向鏈表
與單向鏈表的刪除一樣文章來源地址http://www.zghlxwxcb.cn/news/detail-435968.html
void clear(Node *head) // 刪除單向鏈表
{
if (head == NULL) return;
// 循環(huán)遍歷鏈表中每個節(jié)點, 當(dāng)遍歷不為空，就一直向后走
for (Node *p = head, *q; p; p = q) // p是當(dāng)前節(jié)點
{
q = p->next; // 先讓q指向下一個節(jié)點
free(p); // 再銷毀當(dāng)前節(jié)點
}
return;
}
到了這里，關(guān)于【算法與數(shù)據(jù)結(jié)構(gòu)】鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
