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