C語言實現(xiàn)無頭單鏈表詳解

更新時間：2022年02月14日 15:09:59 作者：考拉愛睡覺鴨~

大家好，本篇文章主要講的是C語言實現(xiàn)無頭單鏈表詳解，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下

鏈表的結(jié)構(gòu)體描述(節(jié)點)
再定義一個結(jié)構(gòu)體(鏈表)
斷言處理 & 判空處理
創(chuàng)建鏈表
創(chuàng)建節(jié)點
頭插法
打印鏈表
尾插法
指定位置插入
頭刪法
尾刪法
指定位置刪除
查找鏈表
刪除所有指定相同的元素
總結(jié)

再封裝的方式，用 c++ 的思想做無頭鏈表

鏈表的結(jié)構(gòu)體描述(節(jié)點)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>       
typedef int DataType;
//節(jié)點
typedef struct Node        
{
	DataType data;
	struct Node* next;
}NODE,*LPNODE;

再定義一個結(jié)構(gòu)體(鏈表)

通過記錄頭節(jié)點和尾節(jié)點的方式去描述鏈表

typedef struct list 
{
	LPNODE frontNode;        //頭節(jié)點
	LPNODE backNode;         //尾節(jié)點
	int curSize;	         //當前節(jié)點個數(shù)
}LIST,*LPLIST;

斷言處理 & 判空處理

如果 list 為空，會引發(fā)中斷(申請內(nèi)存可能失敗)

防御性編程，如果申請內(nèi)存失敗，操作無效，NULL 里面沒有 frontNode，backNode，curSize，存在安全隱患C6011：取消對 NULL 指針"list"的引用

如果申請內(nèi)存失敗，assert()直接讓程序直接中斷，并且告訴你程序斷在哪一行

#include<assert>    //斷言處理宏
   #define assert(expression) (void)(  \
            (!!(expression)) ||        \
(_wassert(_CRT_WIDE(#expression), _CRT_WIDE(__FILE__), (unsigned)(__LINE__)), 0) \
        )
 
LPLIST  createList() 
{
	LPLIST list = (LPLIST)malloc(sizeof(LIST)); 
    list = NULL;                        //list為空 引發(fā)中斷
	assert(list);		           
    //if(list == NULL)
    //return NULL;                      //可以替換
	list->frontNode = NULL;                     
	list->backNode = NULL;
	list->curSize = 0;                         
	return list;
}
 
//abort() has been called line 25

創(chuàng)建鏈表

描述鏈表最初的狀態(tài)

LPLIST  createList() 
{
	LPLIST list = (LPLIST)malloc(sizeof(LIST)); //用結(jié)構(gòu)體變量去描述 做動態(tài)內(nèi)存申請
	assert(list);		                   
	list->frontNode = NULL;                     //鏈表剛開始是空的 頭尾節(jié)點指向空
	list->backNode = NULL;
	list->curSize = 0;                          //當前元素個數(shù)為0
	return list;
}

創(chuàng)建節(jié)點

LPNODE createNode(int data) 
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
	assert(newNode);
    //初始化數(shù)據(jù)
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

頭插法

插入一個節(jié)點，節(jié)點插在原表頭前面，表頭會改變，在1(表頭)前面插入666(數(shù)據(jù))

把新節(jié)點的 next 指針指向原來的表頭

把原來表頭指針從原來的位置挪到新節(jié)點的位置

//插入的鏈表 插入的數(shù)據(jù)
void push_front(LPLIST list,int data) 
{
	LPNODE newNode = createNode(data);    //創(chuàng)建新節(jié)點
	newNode->next = list->frontNode;
	list->frontNode = newNode;
	//護頭也要護尾
	if (list->curSize == 0)               //只有一個節(jié)點 鏈表為空尾節(jié)點也是指向新節(jié)點
		list->backNode = newNode;         //把尾節(jié)點置為新節(jié)點
	list->curSize++;
}
//測試代碼
	LPLIST list = createList();
	push_front(list, 1);
	push_front(list, 2);                  //2 1
	printList(list);

打印鏈表

從第1個節(jié)點開始打印

void printList(LPLIST list) 
{
	LPNODE pmove = list->frontNode;
	while (pmove != NULL)             //不為空打印數(shù)據(jù)
	{
		printf("%d\t", pmove->data);   
		pmove = pmove->next;
	}
	printf("\n");
}

尾插法

不需要找尾巴，因為記錄了尾巴的位置

//插入的鏈表 插入的數(shù)據(jù)
void push_back(LPLIST list, int data) 
{
	LPNODE newNode = createNode(data);     //創(chuàng)建新節(jié)點
	if (list->curSize == 0) 
	{
		list->frontNode = newNode;         //只有1個節(jié)點的情況 表頭也是指向新節(jié)點
		//list->backNode = newNode;        //表尾指向新節(jié)點
	}	
	else 
	{
		list->backNode->next = newNode;    //把原來鏈表的尾節(jié)點的next指針置為新節(jié)點
		//list->backNode = newNode;        //原來的表尾挪到新節(jié)點的位置
	}
	list->backNode = newNode;              //相同代碼
	list->curSize++;
}
//測試代碼
    push_back(list, 666);
	push_back(list, 999);                  //2 1 666 999
	printList(list);

指定位置插入

根據(jù)指定數(shù)據(jù)做插入，插在指定位置(數(shù)據(jù))前面，不需要考慮表尾(尾插)

分改變表頭、不改變表頭兩種情況：指定數(shù)據(jù)，數(shù)據(jù)可能插在表頭前面(頭節(jié)點的數(shù)據(jù)==指定數(shù)據(jù))

前驅(qū)節(jié)點的 next 指針指向新節(jié)點，新節(jié)點的 next 指針指向當前節(jié)點

void push_appoin(LPLIST list, int posData, int data) 
{
	if (list == NULL || list->curSize == 0)  //為空無法做插入
	{
		printf("無法插入鏈表為空!\n");
		return;
	}
    //其他情況可以插入
	if (list->frontNode->data == posData)    //頭節(jié)點的數(shù)據(jù)==指定數(shù)據(jù) 
	{
		push_front(list, data);              //會改變表頭 用頭插法插入
		return;
	}
    //正常插入的情況
	LPNODE preNode = list->frontNode;        //定義一個前驅(qū)節(jié)點指向第1個節(jié)點
	LPNODE curNode = list->frontNode->next;  //定義一個當前節(jié)點指向第1個節(jié)點的下一個節(jié)點
    //當前節(jié)點!=NULL && 當前節(jié)點的數(shù)據(jù)!=指定數(shù)據(jù)
	while (curNode != NULL && curNode->data != posData) //并排往下走
	{
		preNode = curNode;                   //前1個節(jié)點走到當前節(jié)點的位置
		curNode = preNode->next;             //當前節(jié)點走到原來位置的下一個
	}
    //分析查找結(jié)果做插入
	if (curNode == NULL)                     //沒找到無法做插入
	{
		printf("沒有找到指定位置，無法插入！\n");
	}
	else 
	{
		LPNODE newNode = createNode(data);   //創(chuàng)建新節(jié)點 
		preNode->next = newNode;             //連接
		newNode->next = curNode;             
		list->curSize++;
	}
}
//測試代碼
    push_appoin(list, 666, 888);
	printList(list);                         //2 1 888 666 999

頭刪法

只有一個節(jié)點的情況：表尾也要改變(表尾指向了一段刪除的內(nèi)存)，表尾也要置為空

void pop_front(LPLIST list)
{
	if (list == NULL || list->curSize == 0)     //判空處理
	{
		printf("鏈表為空，無法刪除!\n");
		return;
	}
	LPNODE nextNode = list->frontNode->next;    //頭節(jié)點的下一個--->第2個節(jié)點
	free(list->frontNode);                      //直接刪除表頭
	list->frontNode = nextNode;                 //把原來的表頭節(jié)點置為下一個節(jié)點
	if (list->curSize == 1)                     //只有1個節(jié)點的情況
	{
		list->backNode = NULL;                  //表尾也要置為空
	}
	list->curSize--;
}
//測試代碼
    pop_front(list);
	pop_front(list);
	pop_front(list);
	pop_front(list);
	printList(list);                             //999

尾刪法

要找到表尾的上一個節(jié)點

//要刪除的鏈表
void pop_back(LPLIST list) 
{
	if (list == NULL || list->curSize == 0)
	{
		printf("鏈表為空，無法刪除!\n");
		return;
	}
    //從第1個節(jié)點開始找 做移動
	LPNODE preNode = list->frontNode;    //頭節(jié)點
	LPNODE backNode = list->frontNode;   //頭節(jié)點的下一個
	while (backNode->next != NULL) 
	{
		preNode = backNode;              //并排往下走
		backNode = preNode->next;
	}
	free(backNode);
	if (list->curSize == 1)              //只有一個節(jié)點的情況
	{
		backNode = NULL;                 //釋放后置空
		list->frontNode = NULL;          //表頭也要置為空
		list->backNode = NULL;           //表尾置為空
		list->curSize--;
	}
	else 
	{
		backNode = NULL;
		preNode->next = NULL;
		list->backNode = preNode;    
		list->curSize--;
	}
}
//測試代碼
    pop_back(list);
	printList(list);

指定位置刪除

void pop_appoin(LPLIST list,int posData) 
{
	if (list == NULL || list->curSize == 0)
	{
		printf("鏈表為空，無法刪除!\n");
		return;
	}
	if (list->frontNode->data == posData) //頭節(jié)點的數(shù)據(jù)==指定數(shù)據(jù) 
	{
		pop_front(list);                  //頭刪法
		return;
	}
	if (list->backNode->data == posData) //尾節(jié)點的數(shù)據(jù)==指定數(shù)據(jù)
	{
		pop_back(list);                  //尾刪法
		return;
	}
    //中間的某個情況
	LPNODE preNode = list->frontNode;    //原來的頭部
	LPNODE curNode = list->frontNode->next;
	while (curNode != NULL && curNode->data != posData) 
	{
		preNode = curNode;               //并排往下走
		curNode = preNode->next;
	}
	if (curNode == NULL) 
	{
		printf("未找到指定位置，無法刪除!\n");
	}
	else 
	{
		preNode->next = curNode->next;   //先連后斷
		free(curNode);
		curNode = NULL;
		list->curSize--;
	}
}
//測試代碼
    pop_appoin(list, 2);
	pop_appoin(list, 999);
	pop_appoin(list, 888);               //2 1 888 666 999
	printList(list);                     //1 666

查找鏈表

//要查找的鏈表 要查找的數(shù)據(jù)
LPNODE searchlist(LPLIST list, int posData)
{
	if (list == NULL)                              //list為空 返回NULL無法做刪除
		return NULL;
	LPNODE pmove = list->frontNode;                //定義一個移動的節(jié)點
	while (pmove != NULL && pmove->data != posData) 
	{
		pmove = pmove->next;                       //數(shù)據(jù)!=指定數(shù)據(jù)一直往下走
	}
	return pmove;                                  //退出循環(huán)直接返回
}

刪除所有指定相同的元素

void pop_all(LPLIST list, int posData) 
{
	while (searchlist(list, posData) != NULL)   //!=NULL說明里面有指定數(shù)據(jù)
	{
		pop_appoin(list, posData);              //持續(xù)做刪除
	}
}
//測試代碼   
	LPLIST test = createList();
	push_back(test, 1);
	push_back(test, 1);
	push_back(test, 1);
	push_back(test, 2);
	pop_all(test, 1);
	printList(test);                            //2