鏈表
- 鏈表就是將零碎的內(nèi)存組織起來
靜態(tài)鏈表
image
#include <stdio.h>
typedef struct node{
int data;
struct node *next;
} Node;
int main()
{
/*
靜態(tài)鏈表:
*/
// 定義三個結(jié)構(gòu)體
Node a;
Node b;
Node c;
// 讓三個結(jié)構(gòu)體保存數(shù)據(jù)
a.data = 1;
b.data = 3;
c.data = 5;
// 將三個結(jié)構(gòu)體鏈接在一起
a.next = &b;
b.next = &c;
// 如果指針沒有值,那么可以賦值為NULL,明確告訴系統(tǒng)該指針沒有值;
c.next = NULL;
// 定義鏈表的頭指針
Node *head = &a;
printf("a.data = %i\n", a.data);
return 0;
}
動態(tài)鏈表
- 空鏈表
- 只有頭指針和一個節(jié)點,并且節(jié)點沒有數(shù)據(jù), 也沒有下一個節(jié)點
#include <stdio.h> #include <stdlib.h> typedef struct node{ int data; struct node *next; } Node; Node *creatList(); void insertNode(Node *head, int num); void printList(Node *head); int main() { // 1. 創(chuàng)建空鏈表 Node *head = creatList(); // 插入節(jié)點,并保存數(shù)據(jù) insertNode(head, 1); insertNode(head, 3); insertNode(head, 5); // 打印鏈表 printList(head); return 0; } // 1.創(chuàng)建空鏈表 /** * @brief creatList 創(chuàng)建空鏈表 * @return 返回頭指針 */ Node *creatList(){ // 定義頭指針并開辟一個空節(jié)點 Node *head = (Node *)malloc(sizeof(Node)); head->next = NULL; // 返回頭指針 return head; }
頭插法
-
規(guī)則:
- 1.讓新節(jié)點的下一個節(jié)點 等于 頭結(jié)點的下一個節(jié)點(頭節(jié)點next的內(nèi)容)
- node->next = head->next;
- 2.讓頭結(jié)點的下一個節(jié)點等于新的節(jié)點(地址)
- head->next = node;
- 規(guī)律
- : 新的節(jié)點永遠(yuǎn)都是插入到了頭結(jié)點的后面
- 1.讓新節(jié)點的下一個節(jié)點 等于 頭結(jié)點的下一個節(jié)點(頭節(jié)點next的內(nèi)容)
-
圖示:
- 1.創(chuàng)建空鏈
- image
- 2.第一步:讓頭結(jié)點的下一個節(jié)點 等于 新的節(jié)點
- image
- 3.讓頭結(jié)點的下一個節(jié)點 等于 新的節(jié)點
- image
- 4.繼續(xù)插入鏈表:
- image
- 5.第一步:讓頭結(jié)點的下一個節(jié)點 等于 新的節(jié)點
- image
- 6.第二步:讓頭結(jié)點的下一個節(jié)點 等于 新的節(jié)點
- image
- 7.結(jié)果如圖
- image
- 以此類推
/ 頭插法插法插入鏈表 /** * @brief insertListF 頭插法給鏈表插入新的節(jié)點 * @param head 鏈表的頭指針 * @param num 需要新節(jié)點保存的數(shù)據(jù) */ void insertListF(Node *head , int num){ // 創(chuàng)建一個新的節(jié)點 Node *node = (Node *)malloc(sizeof(Node)); // 將數(shù)據(jù)保持到新節(jié)點中 node->data = num; // 讓新節(jié)點的下一個節(jié)點 等于 頭節(jié)點的下一個節(jié)點 node->next = head->next; // 讓頭結(jié)點的下一個節(jié)點 等于 新節(jié)點 head->next = node; }
尾插法
-
規(guī)則:
- 1.定義變量記錄新節(jié)點的上一個節(jié)點
- 2.將新節(jié)點添加到上一個節(jié)點后面
- 3.讓新節(jié)點成為下一個節(jié)點的上一個節(jié)點
-
圖示:
- 1.創(chuàng)建空鏈
- image
- 2.定義變量記錄新節(jié)點的上一個節(jié)點
- 3.將新節(jié)點添加到上一個節(jié)點后面
- image
- 4.讓新節(jié)點成為下一個節(jié)點的上一個節(jié)點
- image
- 5.繼續(xù)插入
- image
- 6.將新節(jié)點添加到上一個節(jié)點后面
- image
- 7.讓新節(jié)點成為下一個節(jié)點的上一個節(jié)點
- image
- 以此類推
// 尾插法插入鏈表 /** * @brief insertListR 尾插法給鏈表插入新的節(jié)點 * @param head 鏈表的頭指針 * @param num 需要新節(jié)點保存的數(shù)據(jù) */ void insertListR(Node *head , int num){ // 定義一個變量保存最后一個節(jié)點 Node *pre = head; while(pre != NULL && pre->next != NULL){ pre = pre->next; } // 創(chuàng)建一個新的節(jié)點 Node *node = (Node *)malloc(sizeof(Node)); // 將數(shù)據(jù)保持到節(jié)點中 node->data = num; node->next = NULL; // 將新節(jié)點添加到上一個節(jié)點后面 pre->next = node; // 讓新節(jié)點稱為下一個節(jié)點的上一個節(jié)點(就是尾節(jié)點) pre = node; }
輸出鏈表
// 輸出鏈表
/**
* @brief printList 遍歷鏈表
* @param head 鏈表的頭指針
*/
void printList(Node *head){
// 取出頭節(jié)點的下一個節(jié)點: 默認(rèn)頭節(jié)點為空
Node *cur = head->next;
// 判斷是否為NULL, 如果不為NULL就開始遍歷
while (cur != NULL) {
// 取出當(dāng)前數(shù)據(jù)
printf("data = %i\n", cur->data);
// 讓當(dāng)前節(jié)點往后移動
cur = cur->next;
}
}
摧毀鏈表
// 摧毀鏈表
/**
* @brief destroyList 摧毀鏈表
* @param head 鏈表的頭指針
*/
void destroyList(Node *head){
Node *cur = NULL;
while(head != NULL){
cur = head->next;
free(head);
head = cur;
}
}
鏈表的長度
// 計算鏈表的長度
/**
* @brief listLength 計算鏈表的長度
* @param head 鏈表的頭指針
* @return
*/
int listLength(Node *head){
// 定義變量記錄節(jié)點的個數(shù)
int count = 0;
// 注意點: 要先去除頭結(jié)點
Node *cur = head->next;
while (cur != NULL) {
count++;
cur = cur->next;
}
return count; // 返回長度
}
查找節(jié)點
/**
* @brief findNode 查找節(jié)點
* @param head 鏈表需要的頭指針
* @param key 需要查找的key
* @return 符合要求的節(jié)點, 如果找不到返回NULL
*/
Node *findNode(Node *head, int key){
head = head->next;
while(head != NULL){
if(head->data == key){
return head;
}else{
head = head->next;
}
}
return NULL;
}
刪除節(jié)點
// 刪除節(jié)點
void deleteNode(Node *head, Node *node){
// 找到需要刪除的節(jié)點的上一個節(jié)點
while (head->next != node) {
head = head->next;
}
// 將刪除節(jié)點上一個節(jié)點next改為, 刪除節(jié)點的下一個節(jié)點
head->next = node->next;
free(node);
}
鏈表排序
/**
* @brief sortList 鏈表排序
* @param head 傳入頭指針
*/
void sortList(Node *head){
// 排序
int len = listLength(head);
Node *cur = NULL;
for(int i = 0; i < len - 1; i++){
cur = head->next;
for(int j = 0; j < len - i -1; j++){
// printf("*");
if(cur->data > cur->next->data){
int temp = cur->data;
cur->data = cur->next->data;
cur->next->data = temp;
}
cur = cur->next;
}
// printf("\n");
}
}
鏈表反轉(zhuǎn)
- 思路就是將鏈表從頭節(jié)點拆開, 一分為二, 然后用頭插法插入
- 圖示
- 1.鏈表的原始位置:
- image
- 2.將鏈表拆開
- image
- 3.頭插法思想重新插入 ; 新節(jié)點的下一個節(jié)點等于頭結(jié)點的下一個節(jié)點
- image
- 讓頭節(jié)點的下一個 等于 當(dāng)前節(jié)點
- image
- 使pre = cur;
- image
- 用頭插法, 以此類推, cur = pre->next;
void reverseList(Node *head){
// 思路:將鏈表從頭結(jié)點拆開 一分為二, 并記錄當(dāng)前位置
// pre 是記錄新節(jié)點的地址; cur記錄是剩余鏈表的首地址
Node *pre, *cur;
pre = head->next;
// 讓head 成為空鏈表
head->next = NULL;
// 重新插入節(jié)點
while(pre){
// 保存剩余的空鏈表防止后面的鏈表丟失
cur = pre->next;
// 按頭插法進(jìn)行插入, 因為頭插法是逆序輸出
// 新節(jié)點的下一個節(jié)點 等于 頭節(jié)點的下一個節(jié)點
pre->next = head->next;
// 頭節(jié)點的下一個節(jié)點 等于 頭結(jié)點
head->next = pre;
// 讓新節(jié)點成為下一個節(jié)點的上一個節(jié)點
pre = cur;
}
}
