帶頭結(jié)點(diǎn)單鏈表(詳解)
更新時(shí)間：2023年07月02日 11:52:01 作者：CD4356
這篇文章主要介紹了帶頭結(jié)點(diǎn)單鏈表?(詳解),需要的朋友可以參考下
單鏈表結(jié)構(gòu)體
- 結(jié)構(gòu)體后的*List是一個(gè)指向結(jié)構(gòu)體的指針類型，我們通過它來定義該類型的指針。
- 如：List p ; 則這個(gè)p就是指向LinkedList結(jié)構(gòu)體的一個(gè)指針，也就是單鏈表的頭指針。（所以說頭指針是必然存在的，但單鏈表不一定有頭結(jié)點(diǎn)，注意區(qū)分頭指針和頭結(jié)點(diǎn)）
typedef struct LinkedList {
int data; //數(shù)據(jù)域
struct LinkedList *next; //指針域，指向后繼結(jié)點(diǎn)，存放后繼結(jié)點(diǎn)的地址
}*List; //List <==> List * ，這里的List是單鏈表的頭指針帶頭結(jié)點(diǎn) 和 不帶頭節(jié)點(diǎn) 的初始化 帶頭結(jié)點(diǎn)單鏈表的初始化。①頭結(jié)點(diǎn)初始化時(shí)，其next域必須置為空 head->next = NULL;。②頭結(jié)點(diǎn)的data數(shù)據(jù)域如果要用來記錄鏈表長(zhǎng)度，則需初始化為0 head->data = 0;
//申請(qǐng)一個(gè)頭結(jié)點(diǎn) 或 初始化一張空表
List create_head_node() {
List head = (List)malloc(sizeof(LinkedList)); //創(chuàng)建頭結(jié)點(diǎn)，并讓頭指針指向頭結(jié)點(diǎn) (帶頭結(jié)點(diǎn)單鏈表)
if (head == 0) { //結(jié)點(diǎn)空間申請(qǐng)失敗，該判斷語(yǔ)句可有可無
return NULL;
}
head->next = NULL; //head是頭結(jié)點(diǎn)，h->next是頭結(jié)點(diǎn)的地址，該地址是第一個(gè)結(jié)點(diǎn)的地址，地址為NULL，即為空表
//head->data不用操作，但若想用頭結(jié)點(diǎn)數(shù)據(jù)域保存鏈表長(zhǎng)度，可以設(shè)置為head->data = 0;
head->data = 0;
return head;
}不帶頭結(jié)點(diǎn)單鏈表的初始化
List link_list_create(){
List p;
p = NULL;
return p;
}求鏈表長(zhǎng)度
單鏈表求長(zhǎng)度有兩種方式
① 用頭結(jié)點(diǎn)的data數(shù)據(jù)域記錄鏈表長(zhǎng)度（只適用于帶頭結(jié)點(diǎn)的鏈表）。創(chuàng)建頭結(jié)點(diǎn)時(shí)，頭結(jié)點(diǎn)的data初始化為0。成功執(zhí)行插入操作后，頭結(jié)點(diǎn)數(shù)據(jù)域+1。成功執(zhí)行刪除操作后，頭結(jié)點(diǎn)數(shù)據(jù)域-1。時(shí)間復(fù)雜度為O(1),（故鏈表帶頭結(jié)點(diǎn)，則推薦用這種方式）
head->data = 0; //創(chuàng)建頭結(jié)點(diǎn)時(shí)，將頭結(jié)點(diǎn)數(shù)據(jù)域初始化為0 head->data++; //每插入一個(gè)元素，頭結(jié)點(diǎn)數(shù)據(jù)域+1 head->data--; //每刪除一個(gè)元素，頭結(jié)點(diǎn)數(shù)據(jù)域-1 head->data; //獲取鏈表長(zhǎng)度
② 遍歷鏈表獲取長(zhǎng)度，時(shí)間復(fù)雜度為O(n)
//求長(zhǎng)度
int link_list_length(List head) {
List p = head->next;
int len = 0;
while (p) {
len++;
p = p->next;
}
return len;
}空表判斷 帶頭結(jié)點(diǎn)的空表判斷head是頭結(jié)點(diǎn)，h->next是頭結(jié)點(diǎn)的地址，該地址是第一個(gè)結(jié)點(diǎn)的地址，地址為NULL，即為空表
boolean isEmpty(List p){
if(p->next == NULL){
return TRUE;
}
return FALSE;
}
或者 (使用頭結(jié)點(diǎn)數(shù)據(jù)域記錄鏈表長(zhǎng)度時(shí)，可用該方法)
boolean isEmpty(List p){
if(p->data == 0){
return TRUE;
}
return FALSE;
}不帶頭結(jié)點(diǎn)的空表判斷 p == NULL; p表示的是第一個(gè)結(jié)點(diǎn)的地址，p = NULL 表示第一個(gè)結(jié)點(diǎn)的地址為空，也就是空表
boolean isEmpty(List p){
if(p == NULL){
return TRUE;
}
return FALSE;
}頭插法
在鏈表頭部插入結(jié)點(diǎn)（即作為鏈表第一個(gè)元素），時(shí)間復(fù)雜度為O(1)
//頭插
boolean head_insert(List head, int x) {
List p = (List)malloc(sizeof(LinkedList)); //申請(qǐng)一個(gè)結(jié)點(diǎn)，并將要插入的元素填入該結(jié)點(diǎn)的數(shù)據(jù)域
p->data = x;
p->next = head->next;
head->next = p;
head->data++; //結(jié)點(diǎn)插入成功，鏈表長(zhǎng)度+1
return TRUE;
}尾插法
在鏈表尾部插入結(jié)點(diǎn)（即作為鏈表最后一個(gè)元素），時(shí)間復(fù)雜度為O(n)。
新結(jié)點(diǎn)插入鏈表尾部時(shí)，新結(jié)點(diǎn)的next域必須置為空，即：newNode->next = NULL; 。因?yàn)閱捂湵砦步Y(jié)點(diǎn)的next域必須為null，否則我們?cè)谡{(diào)用尾結(jié)點(diǎn)的next指針p->next時(shí)，系統(tǒng)判斷尾結(jié)點(diǎn)的next沒有值，就會(huì)動(dòng)態(tài)地給它分配一個(gè)未知地址（而不是幫你將next域置為空）。正常情況下，雖然并不會(huì)出現(xiàn)問題，但在遍歷鏈表 或 按內(nèi)容獲取結(jié)點(diǎn) 或 第二次插入為節(jié)點(diǎn)時(shí)，程序就會(huì)陷入死循環(huán)，最終耗盡cpu性能。你可以將tail_insert()方法中的newNode->next = NULL;這行代碼注釋掉，然后調(diào)用我們后面講到的show()方法進(jìn)行測(cè)試，你就會(huì)看到show()方法會(huì)不停息的打印輸出一個(gè)個(gè)未知地址，直至內(nèi)存耗盡，系統(tǒng)奔潰
//尾插
boolean tail_insert(List head, int x) {
List newNode = (List)malloc(sizeof(LinkedList)); //申請(qǐng)一個(gè)結(jié)點(diǎn)，并將要插入的元素填入該結(jié)點(diǎn)的數(shù)據(jù)域
newNode->data = x;
//newNode->next是動(dòng)態(tài)分配的，如果你不置為空，系統(tǒng)就會(huì)動(dòng)態(tài)地給它分配一個(gè)未知地址。
newNode->next = NULL;
List p = head; //用p結(jié)點(diǎn)做記錄
while (p->next != NULL) { //遍歷鏈表，直至尾結(jié)點(diǎn)
p = p->next;
}
p->next = newNode; //讓尾結(jié)點(diǎn)指針，指向新結(jié)點(diǎn)
head->data++; //新結(jié)點(diǎn)插入成功，鏈表長(zhǎng)度+1
return TRUE;
}指定位置插入 在第k個(gè)位置插入新結(jié)點(diǎn)。需要先遍歷鏈表，找到第k-1個(gè)結(jié)點(diǎn)，然后再修改新結(jié)點(diǎn)指針和第k-1個(gè)結(jié)點(diǎn)的指針，即可實(shí)現(xiàn)在第k個(gè)位置插入新結(jié)點(diǎn)操作。
//指定位置插入
boolean insert(List head, int k, int x) {
if (k < 1) {
printf("插入位置非法！");
return FALSE;
}
List p = head;
int i = 0; //用i來記錄結(jié)點(diǎn)位置
while (p->next != NULL && i < k - 1) {
i++;
p = p->next;
}
if (i + 1 == k) {
List tmp = (List)malloc(sizeof(LinkedList)); //申請(qǐng)一個(gè)結(jié)點(diǎn)，并將要插入的元素填入該結(jié)點(diǎn)的數(shù)據(jù)域
tmp->data = x;
tmp->next = p->next;
p->next = tmp;
head->data++; //新結(jié)點(diǎn)插入成功，鏈表長(zhǎng)度+1
return TRUE;
} else {
printf("插入位置非法！");
return FALSE;
}
}按位序查找
//按位序查找
List get(List head, int k) {
if (k < 1) {
printf("查找位置非法！");
return NULL;
}
List p = head;
int i = 0;
while (p->next != NULL && i < k) { //找到第k個(gè)結(jié)點(diǎn)
i++;
p = p->next;
}
if (i == k) { //判斷i是否等于要查找結(jié)點(diǎn)的位序
return p;
}else{
printf("查找位置非法！");
return NULL;
}
}刪除第1個(gè)結(jié)點(diǎn)
//刪除第1個(gè)結(jié)點(diǎn)
boolean del_first(List head) {
if (head->next != NULL) {
head->next = head->next->next; //讓頭結(jié)點(diǎn)next指針，指向頭結(jié)點(diǎn)下一個(gè)結(jié)點(diǎn)的next指針?biāo)碌刂?
head->data--; //鏈表長(zhǎng)度減1
return TRUE;
}
return FALSE;
}刪除第k個(gè)結(jié)點(diǎn)
//刪除第k個(gè)結(jié)點(diǎn)
boolean del(List head, int k) {
List p = head;
if (p->next == NULL && k < 1) {
printf("刪除位置非法！\n");
return FALSE;
}
int i = 0; //用i記錄結(jié)點(diǎn)位置
while (p->next != NULL && i < k - 1) { //找到待刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
i++;
p = p->next;
}
if (i + 1 == k) { //判斷i是不是k結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的位置
p->next = p->next->next;
head->data--; //鏈表長(zhǎng)度減1
return TRUE;
} else {
printf("刪除位置非法！\n");
return FALSE;
}
}遍歷鏈表，顯示數(shù)據(jù) 前面講到了，如果在新結(jié)點(diǎn)插入鏈表尾部時(shí)，如果新結(jié)點(diǎn)next指針沒有置為NULL，則在show()遍歷鏈表時(shí)，將鏈表的結(jié)點(diǎn)數(shù)據(jù)輸出后，方法不會(huì)中斷，而是繼續(xù)輸出一個(gè)個(gè)未知地址，直至內(nèi)存空間耗盡。
//顯示數(shù)據(jù)
void show(List head) {
List p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}全部代碼
#include <stdio.h>
#include <stdlib.h> //malloc需要此頭文件
typedef enum {FALSE, TRUE} boolean;
//結(jié)構(gòu)體
typedef struct LinkedList {
int data;
struct LinkedList *next;
} *List; //List <==> List *
//申請(qǐng)一個(gè)頭結(jié)點(diǎn)，并初始化
List create_head_node() {
List head = (List)malloc(sizeof(LinkedList)); //創(chuàng)建頭結(jié)點(diǎn)，并讓頭指針指向頭結(jié)點(diǎn) (帶頭結(jié)點(diǎn)單鏈表)
if (head == 0) { //結(jié)點(diǎn)空間申請(qǐng)失敗，該判斷語(yǔ)句可有可無
return NULL;
}
head->next = NULL; //head表示的是頭結(jié)點(diǎn)的地址，h->next就是頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，即第一個(gè)結(jié)點(diǎn)的地址為空，也就是空表
//head->data不用操作，但若想用頭結(jié)點(diǎn)數(shù)據(jù)域保存鏈表長(zhǎng)度，可以設(shè)置為head->data = 0;
head->data = 0;
return head;
}
//頭插
boolean head_insert(List head, int x) {
List p = (List)malloc(sizeof(LinkedList)); //申請(qǐng)一個(gè)結(jié)點(diǎn)，并將要插入的元素填入該結(jié)點(diǎn)的數(shù)據(jù)域
p->data = x;
p->next = head->next;
head->next = p;
head->data++; //結(jié)點(diǎn)插入成功，鏈表長(zhǎng)度+1
return TRUE;
}
//尾插
boolean tail_insert(List head, int x) {
List newNode = (List)malloc(sizeof(LinkedList)); //申請(qǐng)一個(gè)結(jié)點(diǎn)，并將要插入的元素填入該結(jié)點(diǎn)的數(shù)據(jù)域
newNode->data = x;
//newNode->next是動(dòng)態(tài)分配的，如果不置為空，系統(tǒng)就會(huì)默認(rèn)分配一個(gè)未知地址
newNode->next = NULL;
List p = head; //用p結(jié)點(diǎn)做記錄
while (p->next != NULL) { //遍歷鏈表，直至尾結(jié)點(diǎn)
p = p->next;
}
p->next = newNode; //讓尾結(jié)點(diǎn)指針，指向新結(jié)點(diǎn)
head->data++; //新結(jié)點(diǎn)插入成功，鏈表長(zhǎng)度+1
return TRUE;
}
//指定位置插入
boolean insert(List head, int k, int x) {
if (k < 1) {
printf("插入位置非法！");
return FALSE;
}
List p = head;
int i = 0; //用i來記錄結(jié)點(diǎn)位置
while (p->next != NULL && i < k - 1) {
i++;
p = p->next;
}
if (i + 1 == k) {
List tmp = (List)malloc(sizeof(LinkedList)); //申請(qǐng)一個(gè)結(jié)點(diǎn)，并將要插入的元素填入該結(jié)點(diǎn)的數(shù)據(jù)域
tmp->data = x;
tmp->next = p->next;
p->next = tmp;
head->data++; //新結(jié)點(diǎn)插入成功，鏈表長(zhǎng)度+1
return TRUE;
} else {
printf("插入位置非法！");
return FALSE;
}
}
//按序號(hào)查找
List get(List head, int k) {
if (k < 1) {
printf("查找位置非法！");
return NULL;
}
List p = head;
int i = 0;
while (p->next != NULL && i < k) { //找到第k個(gè)結(jié)點(diǎn)
i++;
p = p->next;
}
if (i == k) {
return p;
} else {
printf("查找位置非法！");
return NULL;
}
}
//刪除第1個(gè)結(jié)點(diǎn)
boolean del_first(List head) {
if (head->next != NULL) {
head->next = head->next->next;
head->data--;
return TRUE;
}
return FALSE;
}
//刪除第k個(gè)結(jié)點(diǎn)
boolean del(List head, int k) {
List p = head;
if (p->next == NULL && k < 1) {
printf("刪除位置非法！\n");
return FALSE;
}
int i = 0; //用i記錄結(jié)點(diǎn)位置
while (p->next != NULL && i < k - 1) { //找到待刪結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
i++;
p = p->next;
}
if (i + 1 == k) { //判斷i是不是k結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的位置
p->next = p->next->next;
head->data--;
return TRUE;
} else {
printf("刪除位置非法！\n");
return FALSE;
}
}
//顯示數(shù)據(jù)
void show(List head) {
List p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
int main() {
List head = create_head_node();
printf("當(dāng)前單鏈表長(zhǎng)度為：%d\n\n", head->data);
head_insert(head, 15);
head_insert(head, 25);
head_insert(head, 35);
printf("第1個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 1)->data);
printf("第2個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 2)->data);
printf("第3個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 3)->data);
printf("當(dāng)前單鏈表長(zhǎng)度為：%d\n\n", head->data);
tail_insert(head, 45);
tail_insert(head, 55);
printf("第1個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 1)->data);
printf("第2個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 2)->data);
printf("第3個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 3)->data);
printf("第4個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 4)->data);
printf("第5個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 5)->data);
printf("當(dāng)前單鏈表長(zhǎng)度為：%d\n\n", head->data);
insert(head, 6, 65);
insert(head, 2, 75);
printf("第1個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 1)->data);
printf("第2個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 2)->data);
printf("第3個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 3)->data);
printf("第4個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 4)->data);
printf("第5個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 5)->data);
printf("第4個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 6)->data);
printf("第5個(gè)結(jié)點(diǎn)元素為：%d\n", get(head, 7)->data);
printf("當(dāng)前單鏈表長(zhǎng)度為：%d\n\n", head->data);
show(head);
printf("\n\n");
del_first(head);
show(head);
printf("\n\n");
del(head, 4);
show(head);
return 0;
}到此這篇關(guān)于帶頭結(jié)點(diǎn)單鏈表 (詳解)的文章就介紹到這了,更多相關(guān)帶頭結(jié)點(diǎn)單鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)俄羅斯方塊游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-09-09
C++實(shí)現(xiàn)LeetCode(82.移除有序鏈表中的重復(fù)項(xiàng)之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(82.移除有序鏈表中的重復(fù)項(xiàng)之二),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C++編譯/編輯器對(duì)OIer的必要功能，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-04-04
這篇文章主要為大家詳細(xì)介紹了如何利用C語(yǔ)言實(shí)現(xiàn)軍旗游戲，文中的示例代碼講解詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-11-11
本篇文章是對(duì)C語(yǔ)言指針賦值的問題進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++萬能庫(kù)頭文件在vs中的安裝步驟(圖文)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
這篇文章主要為大家詳細(xì)介紹了基于easyx的C++實(shí)現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
在Qt中QMainWindow是一個(gè)為用戶提供主窗口程序的類，包含了：菜單欄、工具欄、錨接部件、狀態(tài)欄以及一個(gè)中部件。本文將利用QMainWindow制作一個(gè)文本編輯器，感興趣的可以試一試2022-01-01
其實(shí)，單調(diào)隊(duì)列和單調(diào)棧是類似的，在我看來，這兩個(gè)東西只是名字不一樣 - - ! 比較容易想的一道題啦！ 首先，這題的兩個(gè)關(guān)鍵點(diǎn)： 1、區(qū)間的和。這個(gè)簡(jiǎn)單，地球人都知道！ 2、區(qū)間的最小值。2015-07-07
C語(yǔ)言中數(shù)組的一些基本知識(shí)小結(jié)
這篇文章主要介紹了C語(yǔ)言中數(shù)組的一些基本知識(shí)小結(jié),其中重點(diǎn)是對(duì)于數(shù)組的內(nèi)存分配相關(guān)方面的知識(shí)整理,需要的朋友可以參考下2016-04-04