數(shù)據(jù)結(jié)構(gòu)之帶頭結(jié)點的單鏈表
一、單鏈表的概念
單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu),用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點來表示的,每個結(jié)點的構(gòu)成:數(shù)據(jù)域(數(shù)據(jù)元素的映象) + 指針域(指示后繼元素存儲位置),元素就是存儲數(shù)據(jù)的存儲單元,指針就是連接每個結(jié)點的地址數(shù)據(jù)。單鏈表邏輯上相鄰,物理上不一定相鄰
二、結(jié)構(gòu)體聲明:
typedef int ELEM_TYPE; //有效數(shù)據(jù)節(jié)點結(jié)構(gòu)體設(shè)計: typedef struct ListNode { ElemType data;//數(shù)據(jù)域 struct ListNode* next;//指針域 }ListNode,*LinkList;
三、函數(shù)
1.購買節(jié)點
從堆區(qū)申請一個節(jié)點大小的內(nèi)存,并將申請好內(nèi)存的地址返回。代碼如下:
//購買節(jié)點 ListNode* Buynode() { ListNode* s = (ListNode*)malloc(sizeof(ListNode)); if (s == NULL) exit(1); memset(s, 0, sizeof(ListNode));//將節(jié)點內(nèi)數(shù)據(jù)全部填充為0 return s;//返回申請成功的節(jié)點地址 }
2.釋放節(jié)點
每次刪除節(jié)點之后都需要用 free()來釋放,否則會造成嚴(yán)重的內(nèi)存泄漏代碼如下:
//釋放節(jié)點 void Freenode(ListNode*p) { free(p); p = NULL;//防止野指針 }
3.單鏈表的初始化
將頭節(jié)點的數(shù)據(jù)域浪費掉,頭節(jié)點的指針域2指為NULL,等待插入數(shù)據(jù)。
單鏈表設(shè)計頭節(jié)點的目的:
- 防止單鏈表是空的而設(shè)的。當(dāng)鏈表為空的時候,帶頭結(jié)點的頭指針就指向頭結(jié)點,如果當(dāng)鏈表為空的時候,頭結(jié)點的指針域的數(shù)值為NULL。
- 為了方便單鏈表的特殊操作,插入在表頭或者刪除第一個結(jié)點。這樣就保持了單鏈表操作的統(tǒng)一性。
- 單鏈表加上頭結(jié)點之后,無論單鏈表是否為空,頭指針始終指向頭結(jié)點,因此空表和非空表的處理統(tǒng)一,方便了單鏈表的操作,也減少了程序的復(fù)雜性和出現(xiàn)bug的機(jī)會。
代碼實現(xiàn):
//初始化 //對頭結(jié)點進(jìn)行初始化 ListNode* InitList() { ListNode* s = Buynode();//申請一個頭節(jié)點 s->next = NULL;//將頭節(jié)點的next域置為空 return s; }
4.判空函數(shù)
判斷一個單鏈表是否是空鏈,只需要判斷頭節(jié)點的指針域是否為NULL
(如果不是一個空鏈,那么必定存在一個有效值節(jié)點,只要存在有效值節(jié)點,那么頭結(jié)點的指針域必不可能指向空,而是指向第一個有效值節(jié)點)代碼如下:
//判空 bool IsEmpty(LinkList head) { assert(head != NULL); return head->next == NULL; }
5.獲取單鏈表有效值個數(shù)
用for循環(huán)遍歷單鏈表,使用一個變量充當(dāng)計數(shù)器,每次循環(huán)+1,當(dāng) p->next == NULL 的時候,返回計數(shù)器的值。代碼如下:
//獲取單鏈表有效值個數(shù) int GetSize(LinkList head) { assert(head != NULL); int size = 0;//計數(shù)器 LinkList p = head->next;//從頭結(jié)點的下一個開始 while (p != NULL) { size++; p = p->next; } return size; }
6.按數(shù)據(jù)查詢(返回含有此數(shù)據(jù)節(jié)點的前驅(qū))
通過兩個指針 prev 和 p 進(jìn)行遍歷,prev從頭節(jié)點開始,p從 頭節(jié)點的next域開始,兩個指針同步前進(jìn)同步停止。當(dāng) p->data == val(傳進(jìn)來的值)時,循環(huán)結(jié)束返回 prev的值否則當(dāng)p ==NULL 時說明將鏈表遍歷完成都沒有找到。返回NULL;
當(dāng)要查詢 3 的時候,返回的是 2 的地址,此時prev->next->data == 3
代碼如下:
ListNode* FindValue_Prev(LinkList head, ElemType val) { assert(head != NULL); ListNode* prev = head;//head ListNode* p = head->next;//head->next while (p != NULL && p->data != val)//循環(huán)結(jié)束條件 { prev = p;//先將prev向后走一步 p = p->next;//然后p向后走一步 } if (p == NULL)//當(dāng)p ==NULL 說明沒有找到 返回NULL { prev = NULL; } return prev; }
7.按數(shù)據(jù)查詢(返回含有當(dāng)前數(shù)據(jù)的節(jié)點)
通過調(diào)用查找前驅(qū)的函數(shù)找到它的前驅(qū),那么前驅(qū)的后繼就是當(dāng)前查詢的節(jié)點。如果p 是NULL 的話,說明沒有找到代碼如下:
ListNode* FindValue(LinkList head, ElemType val) { assert(head != NULL); ListNode* p = FindPos_Prev(head, val);//調(diào)用查找前驅(qū)的函數(shù) if (p != NULL) { p = p->next; } return p; }
8.按pos位置查節(jié)點的前驅(qū)
通過兩個指針 prev 和 p 和一個計數(shù)器 i 進(jìn)行遍歷,prev從頭節(jié)點開始,p從 頭節(jié)點的next域開始,兩個指針同步前進(jìn)同步停止。但是在循環(huán)之前需要判斷 pos位置是否合法。當(dāng)pos<1 時 返回NULL
當(dāng) p == NULL 的時候說明沒有找到退出循環(huán)返回 NULL當(dāng) i==pos 時 說明找到了這個數(shù)據(jù)的節(jié)點,此時返回prev
代碼如下:
ListNode* FindPos_Prev(LinkList head, int pos) { assert(head != NULL); int i = 1; ListNode* prev = head; ListNode* p = head->next; if (pos < 1) { return NULL; } while (p != NULL && i < pos) { prev = p; p = p->next; i = i + 1; } if (p == NULL) { prev = NULL; } return prev; }
9.按pos位置查節(jié)點
通過調(diào)用查找前驅(qū)的函數(shù)找到它的前驅(qū),那么前驅(qū)的后繼就是當(dāng)前查詢的節(jié)點。如果p 是NULL 的話,說明沒有找到代碼如下:
ListNode* FindPos(LinkList head, int pos) { assert(head != NULL); ListNode* p = FindPos_Prev(head,pos); if (p != NULL) { p = p->next; } return p; }
10.按照節(jié)點插入數(shù)據(jù)
我們認(rèn)為,形參中傳入進(jìn)來的節(jié)點地址就是存在的(通過其他函數(shù)嵌套使用,并不可單獨使用)直接插入即可。
首先通過 **Buynode()**函數(shù)申請一個節(jié)點,保存val值然后把ptr->next賦值給s->next 此時s和ptr都指向 300 這個地址然后將 s 的地址賦值給 ptr->next ,完成插入
代碼如下:
bool Insert_Next(LinkList head, ListNode* ptr, ElemType val) { assert(head != NULL); if (NULL == ptr) { return false; } ListNode* s = Buynode(); s->data = val; s->next = ptr->next; ptr->next = s; return true; }
11.頭插法
首先通過 **Buynode()**函數(shù)申請一個節(jié)點,保存val值然后把頭節(jié)點指向的next的地址賦值給 s->next
最后 把s 的地址賦值給頭節(jié)點的next域
代碼如下:
void Push_Front(LinkList head, ElemType val) { assert(head != NULL); ListNode* s = Buynode(); s->data = val; s->next = head->next; head->next = s; }
12.尾插法
先使用一個p指針遍歷鏈表到 p->next == NULL 說明此時p指針?biāo)赶虻墓?jié)點就是尾節(jié)點使用**Buynode()**申請一個節(jié)點,將val值賦值給s 并且將s->next置為空
最后將 s 的地址賦值給 p->next ,完成尾插
代碼如下:
void Push_Back(LinkList head, ElemType val) { assert(head != NULL); ListNode* p = head; ListNode* s = Buynode(); while (p->next != NULL) { p = p->next; } //退出循環(huán)后p指向尾節(jié)點 s->data = val; s->next = p->next; p->next = s; }
13.按pos位置插入
首先判斷pos的合法性,如果pos<1則退出然后用while循環(huán)判斷鏈表是否結(jié)束以及 計數(shù)鏈表的位置此時while循環(huán)有兩種情況結(jié)束
- 當(dāng) s->next == NULL 時,說明 s指向的鏈表的尾部,此處退出循環(huán),判斷pos和i的關(guān)系如果pos>i 說明pos位置遠(yuǎn)遠(yuǎn)大于鏈表有效長度,無法插入。
- 當(dāng) i>pos 退出循環(huán)時,說明已經(jīng)找到了pos位置,并且s->next就是待插入位置,此時調(diào)用**Insert_Next()**函數(shù),傳入s的地址,完成插入
代碼如下:
bool InsertPos(LinkList head, int pos, ElemType val) { assert(head != NULL); if (pos < 1) { return false; }//判斷p的合法性 ListNode* s = head; int i = 1;//計數(shù)鏈表位置 while (s->next != NULL && i < pos) { s = s->next; i++; } if (pos > i) { return false; } return Insert_Next(head, s, val);
14.刪除ptr指針后續(xù)節(jié)點
我們認(rèn)為,形參中傳入進(jìn)來的節(jié)點地址就是存在的(通過其他函數(shù)嵌套使用,并不可單獨使用)直接刪除即可。首先 用一個指針保存ptr ->next 的值(也就是待刪除結(jié)點的地址)
然后將 p->next 的值賦值給 ptr->next
最后使用 Freenode()函數(shù)釋放p節(jié)點
完成刪除
代碼如下:
bool Earse_Next(LinkList head, ListNode* ptr) { assert(head != NULL); if (ptr == NULL||ptr->next==NULL)//判斷ptr和ptr->next是一個有效值 { return false; } ListNode* p = ptr->next; ptr->next = p->next; Freenode(p);//釋放節(jié)點 return true; }
15.刪除第一個節(jié)點
直接調(diào)用 **Earse_Next()**函數(shù),傳入頭節(jié)點頭節(jié)點的后續(xù)節(jié)點就是第一個節(jié)點。代碼如下:
void Pop_Front(LinkList head) { assert(head != NULL); Earse_Next(head, head); }
16.刪除最后一個節(jié)點
通過兩個指針 pre和 p分別指向頭節(jié)點和頭節(jié)點的下一個節(jié)點使用while循環(huán)找到 最后一個節(jié)點的前驅(qū)然后調(diào)用 **Earse_Next()**函數(shù),完成刪除代碼如下:
void Pop_Back(LinkList head) { assert(head != NULL); ListNode* pre = head; ListNode* p = head->next; while (p != NULL && p->next != NULL) { pre = p; p = p->next; } Earse_Next(head, pre); }
17.刪除數(shù)據(jù)域和val相等的元素
通過 **FindPos_Prev()函數(shù)查到val數(shù)據(jù)的節(jié)點地址然后通過Earse_Next()**函數(shù),完成刪除代碼如下:
bool Remove(LinkList head, ElemType val) { assert(head != NULL); return Earse_Next(head, FindPos_Prev(head, val)); }
18.刪除數(shù)據(jù)域和val相等的所有元素
通過while循環(huán) 不斷調(diào)用**FindValue_Prev()函數(shù)返回地址然后通過通過Earse_Next()函數(shù),完成刪除一個數(shù)據(jù)直到FindValue_Prev()**函數(shù)返回地址為NULL的時候,說明鏈表里沒有這個數(shù)據(jù)退出循環(huán),完成刪除。代碼如下:
void Remove_ALL(LinkList head, ElemType val) { assert(head != NULL); ListNode* s = NULL; while ((s = FindValue_Prev(head, val)) != NULL) { Earse_Next(head, s); } }
19.清空鏈表
不斷調(diào)用頭刪函數(shù),直到除了頭節(jié)點以外沒有任何節(jié)點(判空函數(shù))代碼如下:
void ClearList(LinkList head) { assert(head != NULL); while (!IsEmpty(head)) { Pop_Front(head); } }
20.銷毀鏈表
清空鏈表并且釋放頭節(jié)點代碼如下:
void DestroyList(LinkList head) { assert(head != NULL); ClearList(head); Freenode(head); }
四.完整代碼
1. My_LinkList.h
#ifndef MY_LINKLIST_S#define MY_LINKLIST_Stypedef int ElemType;typedef struct ListNode{<!-- -->ElemType data;//數(shù)據(jù)元素struct ListNode* next;//指針域}ListNode,*LinkList;//初始化函數(shù) headListNode* InitList();//清空鏈表void ClearList(LinkList head);//銷毀鏈表void DestroyList(LinkList head);//判空函數(shù) bool IsEmpty(LinkList head);//返回數(shù)據(jù)節(jié)點的個數(shù)int GetSize(LinkList head);//傳入頭節(jié)點打印函數(shù)void PrintList(LinkList head);//按數(shù)據(jù)查詢返回含有此數(shù)據(jù)節(jié)點的前驅(qū)ListNode* FindValue_Prev(LinkList head, ElemType val);//按數(shù)據(jù)查詢 返回含有當(dāng)前數(shù)據(jù)的節(jié)點ListNode* FindValue(LinkList head, ElemType val);//按pos位置查節(jié)點ListNode* FindPos(LinkList head, int pos);//按pos位置查節(jié)點的前驅(qū)ListNode* FindPos_Prev(LinkList head, int pos);//按節(jié)點插入bool Insert_Next(LinkList head, ListNode* ptr, ElemType val);//從頭插入void Push_Front(LinkList head, ElemType val);//尾插法void Push_Back(LinkList head, ElemType val);//按pos位置插入bool InsertPos(LinkList head, int pos, ElemType val);//刪除ptr指針后續(xù)節(jié)點bool Earse_Next(LinkList head, ListNode* ptr);//刪除第一個節(jié)點void Pop_Front(LinkList head);//刪除最后一個節(jié)點void Pop_Back(LinkList head);//刪除數(shù)據(jù)域和val相等的元素bool Remove(LinkList head, ElemType val);//刪除數(shù)據(jù)域和val相等的所有元素void Remove_ALL(LinkList head, ElemType val);#ifndef MY_LINKLIST_S #define MY_LINKLIST_S typedef int ElemType; typedef struct ListNode { ElemType data;//數(shù)據(jù)元素 struct ListNode* next;//指針域 }ListNode,*LinkList; //初始化函數(shù) head ListNode* InitList(); //清空鏈表 void ClearList(LinkList head); //銷毀鏈表 void DestroyList(LinkList head); //判空函數(shù) bool IsEmpty(LinkList head); //返回數(shù)據(jù)節(jié)點的個數(shù) int GetSize(LinkList head); //傳入頭節(jié)點打印函數(shù) void PrintList(LinkList head); //按數(shù)據(jù)查詢返回含有此數(shù)據(jù)節(jié)點的前驅(qū) ListNode* FindValue_Prev(LinkList head, ElemType val); //按數(shù)據(jù)查詢 返回含有當(dāng)前數(shù)據(jù)的節(jié)點 ListNode* FindValue(LinkList head, ElemType val); //按pos位置查節(jié)點 ListNode* FindPos(LinkList head, int pos); //按pos位置查節(jié)點的前驅(qū) ListNode* FindPos_Prev(LinkList head, int pos); //按節(jié)點插入 bool Insert_Next(LinkList head, ListNode* ptr, ElemType val); //從頭插入 void Push_Front(LinkList head, ElemType val); //尾插法 void Push_Back(LinkList head, ElemType val); //按pos位置插入 bool InsertPos(LinkList head, int pos, ElemType val); //刪除ptr指針后續(xù)節(jié)點 bool Earse_Next(LinkList head, ListNode* ptr); //刪除第一個節(jié)點 void Pop_Front(LinkList head); //刪除最后一個節(jié)點 void Pop_Back(LinkList head); //刪除數(shù)據(jù)域和val相等的元素 bool Remove(LinkList head, ElemType val); //刪除數(shù)據(jù)域和val相等的所有元素 void Remove_ALL(LinkList head, ElemType val);
2. My_LinkList.cpp
#include<stdlib.h> #include<stdio.h> #include<string.h> #include<assert.h> #include"My_LinkList.h" ListNode* Buynode()//購買節(jié)點 { ListNode* s = (ListNode*)malloc(sizeof(ListNode)); if (s == NULL) exit(1); memset(s, 0, sizeof(ListNode));//將節(jié)點內(nèi)數(shù)據(jù)全部填充為0 return s;//返回申請成功的節(jié)點地址 } void Freenode(ListNode*p) { free(p); p = NULL;//防止野指針 } bool IsEmpty(LinkList head) { assert(head != NULL); return head->next == NULL; } int GetSize(LinkList head) { assert(head != NULL); int size = 0; LinkList p = head->next; while (p != NULL) { size++; p = p->next; } return size; } ListNode* InitList() { ListNode* s = Buynode(); s->next = NULL; return s; } void PrintList(LinkList head) { assert(head != NULL); ListNode* p = head->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } ListNode* FindValue(LinkList head, ElemType val) { assert(head != NULL); ListNode* p = FindPos_Prev(head, val); if (p != NULL) { p = p->next; } return p; } ListNode* FindValue_Prev(LinkList head, ElemType val) { assert(head != NULL); ListNode* prev = head;//head ListNode* p = head->next;//head->next while (p != NULL && p->data != val) { prev = p; p = p->next; } if (p == NULL) { prev = NULL; } return prev; } ListNode* FindPos(LinkList head, int pos) { assert(head != NULL); ListNode* p = FindPos_Prev(head,pos); if (p != NULL) { p = p->next; } return p; } ListNode* FindPos_Prev(LinkList head, int pos) { assert(head != NULL); int i = 1; ListNode* pre = head; ListNode* p = head->next; if (pos < 1) { return NULL; } while (p != NULL && i < pos) { pre = p; p = p->next; i = i + 1; } if (p == NULL) { pre = NULL; } return pre; } bool Insert_Next(LinkList head, ListNode* ptr, ElemType val) { assert(head != NULL); if (NULL == ptr) { return false; } ListNode* s = Buynode(); s->data = val; s->next = ptr->next; ptr->next = s; return true; } void Push_Front(LinkList head, ElemType val) { assert(head != NULL); ListNode* s = Buynode(); s->data = val; s->next = head->next; head->next = s; } void Push_Back(LinkList head, ElemType val) { assert(head != NULL); ListNode* p = head; ListNode* s = Buynode(); while (p->next != NULL) { p = p->next; } s->data = val; s->next = p->next; p->next = s; } bool InsertPos(LinkList head, int pos, ElemType val) { assert(head != NULL); if (pos < 1) { return false; } ListNode* s = head; int i = 1; while (s->next != NULL && i < pos) { s = s->next; i++; } if (pos > i) { return false; } return Insert_Next(head, s, val); /* p->data = val; p->next = s->next; s->next = p; */ } bool Earse_Next(LinkList head, ListNode* ptr) { assert(head != NULL); if (ptr == NULL||ptr->next==NULL) { return false; } ListNode* p = ptr->next; ptr->next = p->next; Freenode(p); return true; } void Pop_Front(LinkList head) { assert(head != NULL); Earse_Next(head, head); } void Pop_Back(LinkList head) { assert(head != NULL); ListNode* pre = head; ListNode* p = head->next; while (p != NULL && p->next != NULL) { pre = p; p = p->next; } Earse_Next(head, pre); } bool Remove(LinkList head, ElemType val) { assert(head != NULL); return Earse_Next(head, FindPos_Prev(head, val)); /* ListNode* pre = head; ListNode* p = head->next; while (p != NULL && p->data != val) { pre = p; p = p->next; } if (p != NULL) { Earse_Next(head, pre); } */ } void Remove_ALL(LinkList head, ElemType val) { assert(head != NULL); ListNode* s = NULL; while ((s = FindValue_Prev(head, val)) != NULL) { Earse_Next(head, s); } } void ClearList(LinkList head) { assert(head != NULL); while (!IsEmpty(head)) { Pop_Front(head); } } void DestroyList(LinkList head) { assert(head != NULL); ClearList(head); Freenode(head); }
到此這篇關(guān)于數(shù)據(jù)結(jié)構(gòu)之帶頭結(jié)點的單鏈表的文章就介紹到這了,更多相關(guān)帶頭結(jié)點的單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!