C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解
更新時(shí)間：2022年08月17日 15:36:54 作者：胡安民
單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問(wèn)要通過(guò)順序讀取從頭部開(kāi)始。本文將為大家詳細(xì)講講單向鏈表的實(shí)現(xiàn)與使用，需要的可以參考一下
鏈表
鏈表實(shí)現(xiàn)了，內(nèi)存零碎數(shù)據(jù)的有效組織。比如，當(dāng)我們用 malloc 來(lái)進(jìn)行內(nèi)存申請(qǐng)的時(shí)候，當(dāng)內(nèi)存足夠，但是由于碎片太多，沒(méi)有連續(xù)內(nèi)存時(shí)，只能以申請(qǐng)失敗而告終，而用鏈表這種數(shù)據(jù)結(jié)構(gòu)來(lái)組織數(shù)據(jù)，就可以解決上類問(wèn)題。
靜態(tài)鏈表
#include <stdio.h>
// 1.定義鏈表節(jié)點(diǎn)
typedef struct node{
int data;
struct node *next;
}Node;
int main(int argc, char *argv[]) {
// 2.創(chuàng)建鏈表節(jié)點(diǎn)
Node a;
Node b;
Node c;
// 3.初始化節(jié)點(diǎn)數(shù)據(jù)
a.data = 1;
b.data = 3;
c.data = 5;
// 4.鏈接節(jié)點(diǎn)
a.next = &b;
b.next = &c;
c.next = NULL;
// 5.創(chuàng)建鏈表頭
Node *head = &a;
// 6.使用鏈表
while(head != NULL){
int currentData = head->data;
printf("currentData = %i\n", currentData);
head = head->next;//指向下一個(gè)節(jié)點(diǎn)
}
return 0;
}動(dòng)態(tài)鏈表
靜態(tài)鏈表的意義不是很大，主要原因，數(shù)據(jù)存儲(chǔ)在棧上，棧的存儲(chǔ)空間有限，不能動(dòng)態(tài)分配。所以鏈表要實(shí)現(xiàn)存儲(chǔ)的自由，要?jiǎng)討B(tài)的申請(qǐng)堆里的空間。
有頭鏈表
無(wú)頭鏈表
單向鏈表有有頭節(jié)點(diǎn)和無(wú)頭節(jié)點(diǎn)兩種列表, 有頭節(jié)點(diǎn)在列表的刪除,反轉(zhuǎn),插入等操作會(huì)比無(wú)頭節(jié)點(diǎn)簡(jiǎn)單,但是不好之處就是多占用些空間,而且在多個(gè)鏈表結(jié)合處理的時(shí)候有頭鏈表每次都需要過(guò)濾頭節(jié)點(diǎn),而無(wú)頭鏈表直接完美融合 ,而且很多高級(jí)語(yǔ)言都是無(wú)頭鏈表的便于日后的擴(kuò)展 ,下面都是依據(jù)無(wú)頭節(jié)點(diǎn)進(jìn)行演示
定義鏈表節(jié)點(diǎn)
// 1.定義鏈表節(jié)點(diǎn)
typedef struct node {
void *data;
struct node *next;
} Node;創(chuàng)建鏈表
/**
* 創(chuàng)建鏈表
*/
Node *createList() {
// 1.創(chuàng)建頭節(jié)點(diǎn)
Node *root = (Node *) malloc(sizeof(Node));
root->data = NULL;
root->next = NULL;
//返回頭節(jié)點(diǎn)
return root;
}
創(chuàng)建一個(gè)空節(jié)點(diǎn)
/**
* 創(chuàng)建一個(gè)空節(jié)點(diǎn)
*/
Node *createNode() {
Node *node = (Node *) malloc(sizeof(Node));
node->data = NULL;
node->next = NULL;
return node;
}尾插法
/**
* @brief insertEndNode 尾插法插入節(jié)點(diǎn)
* @param head 需要插入的頭指針
* @param data 需要插入的數(shù)據(jù)
*/
void insertEndNode(Node *node, void *data) {
Node *head = node;
//找到數(shù)據(jù)為空的節(jié)點(diǎn),沒(méi)有節(jié)點(diǎn)那么就擴(kuò)展
while (head->data != NULL) {
//擴(kuò)容
if(head->next == NULL) {
Node *pNode = createNode();
head->next = pNode;
head = pNode;
break;
}
head = head->next;
}
//插入數(shù)據(jù)
head->data = data;
}頭插法
/**
* @brief insertHeadNode 頭插法插入節(jié)點(diǎn)
* @param head 需要插入的頭指針
* @param data 需要插入的數(shù)據(jù)
*/
void insertHeadNode(Node **node, void *data) {
Node *pNode = createNode();
pNode->data = data;
pNode->next = *node;
*node = pNode;
}
指定位置插入一個(gè)結(jié)點(diǎn)
簡(jiǎn)單來(lái)說(shuō)就是先找到需要插入的位置,然后將當(dāng)前位置節(jié)點(diǎn)和他前一個(gè)節(jié)點(diǎn)連接到需要插入的節(jié)點(diǎn)就行了
/**
* @brief insertNOde 將數(shù)據(jù)節(jié)點(diǎn)插入到指定數(shù)據(jù)位置節(jié)點(diǎn),指定數(shù)據(jù)節(jié)點(diǎn)向后移動(dòng), 如果沒(méi)有找到插入的位置,那么就插入到最后
* @param insertionPoint 指定的數(shù)據(jù)節(jié)點(diǎn)
* @param data 需要插入的數(shù)據(jù)
*/
void insertNode(Node *node ,void *insertionPoint,void *data){
Node *pNode = node;
Node *pre = pNode;//父節(jié)點(diǎn)
while (pNode!=NULL){
if(pNode->data == insertionPoint){
break;
}
pre=pNode; //保留當(dāng)前節(jié)點(diǎn)
pNode=pNode->next;
}
//如果沒(méi)有找到那么就插入到最后
if(pNode==NULL){
insertEndNode(node,data);
return;
}
Node *dataNode = createNode();
dataNode->data= data;
pre->next = dataNode;
dataNode->next = pNode;
}遍歷鏈表
因?yàn)槲覀冎荡鎯?chǔ)是使用無(wú)類型的指針,所以需要轉(zhuǎn)換為插入時(shí)候的類型才行
/**
* @brief printNodeListDouble 遍歷鏈表
* @param node 鏈表指針頭
*/
void printNodeListDouble(Node *node) {
Node *head = node;
while (head!=NULL&&head->data!=NULL){
double *currentData = head->data;
printf("currentData = %f\n", *currentData);
head = head->next;
}
}
獲取鏈表長(zhǎng)度
/**
* @brief listLength 計(jì)算鏈表長(zhǎng)度
* @param head 鏈表頭指針
* @return 鏈表長(zhǎng)度
*/
int listLength(Node *head){
int count = 0;
head = head;
while(head){
count++;
head = head->next;
}
return count;
}
鏈表搜索
/**
* @brief searchList 查找指定節(jié)點(diǎn)
* @param head 鏈表頭指針
* @param key 需要查找的值
* @return
*/
Node *searchList(Node *head, void *key){
head = head;
while(head){
if(head->data == key){
break;
}else{
head = head->next;
}
}
return head;
}鏈表數(shù)據(jù)排序
因?yàn)槲覀兇鎯?chǔ)數(shù)據(jù)類型是使用無(wú)類型的指針,那么在排序的時(shí)候需要轉(zhuǎn)換為指定類型才行
/**
* @brief bubbleSort 對(duì)鏈表值進(jìn)行排序 小到大
* @param head 鏈表頭指針
*/
void sortDouble(Node *head){
// 1.計(jì)算鏈表長(zhǎng)度
int len = listLength(head);
// 2.定義變量記錄前后節(jié)點(diǎn)
Node *cur = head;
while (cur!=NULL){
Node *cur1=cur->next;
while (cur1!=NULL){
//比較大小 ,然后交換數(shù)據(jù)
if(*((double *)cur->data) > *((double *)cur1->data)){
double *temp = (double *)cur->data;
cur->data = cur1->data;
cur1->data = temp;
}
cur1 = cur1->next;
}
cur= cur->next;
}
}反轉(zhuǎn)鏈表
斷開(kāi)鏈表頭，然后以頭插法的方式將原鏈表的數(shù)據(jù)添加鏈表。
/**
* @brief reverseList 反轉(zhuǎn)鏈表
* @param head 鏈表頭指針
*/
void reverseList(Node **root){
Node *head = *root;
Node *pre=head, *cur=head->next;
pre->next = NULL;
while (cur!=NULL){
Node *node = cur->next;
cur->next = pre;
pre = cur;
cur=node;
}
*root=pre;
}刪除節(jié)點(diǎn)數(shù)據(jù)
先找到需要?jiǎng)h除的節(jié)點(diǎn),之后將后一個(gè)結(jié)點(diǎn)賦值給前一個(gè)結(jié)點(diǎn)的next,然后將刪除位置的結(jié)點(diǎn)釋放即可
/**
* @brief delNode 刪除指定節(jié)點(diǎn)
*/
void delNode(Node **root, void *key){
Node *head = *root;
//根節(jié)點(diǎn)單獨(dú)處理
if(head->data == key&&head->next != NULL){
*root = head->next;
free(head->data);
free(head);
return;
}
Node *head1 = head->next;
Node *pre = head;//根節(jié)點(diǎn)
while (head1!=NULL){
if(head1->data == key){
pre->next = head1->next;
free(head1->data);
free(head1);
break;
}
pre = head1;//當(dāng)前節(jié)點(diǎn)
head1 = head1->next; //下一個(gè)節(jié)點(diǎn)
}
}銷毀鏈表
/**
* @brief destroyList 銷毀鏈表
* @param head 鏈表頭指針
*/
void destroyList(Node *head){
Node *cur = head;
while(head != NULL){
cur = head->next;
free(head->data);//清除當(dāng)前節(jié)點(diǎn)數(shù)據(jù)內(nèi)存
free(head);//清除當(dāng)前節(jié)點(diǎn)內(nèi)存
head = cur;
}
}
測(cè)試
int main(int argc, char *argv[]) {
//創(chuàng)建鏈表
Node *head = createList();
//插入數(shù)據(jù)
printf("insert ====================\n");
double *f = (double *)malloc(sizeof(double));
*f=2.1;
insertEndNode(head, f);
double *f1 = (double *)malloc(sizeof(double));
*f1=1.1;
insertEndNode(head, f1);
double *f2= (double *)malloc(sizeof(double));
*f2=0.1;
insertEndNode(head, f2);
double *f3= (double *)malloc(sizeof(double));
*f3=3.1;
insertHeadNode(&head, f3);
double *se = (double *)malloc(sizeof(double));
*se=111.1;
double *f4= (double *)malloc(sizeof(double));
*f4=7.1;
insertNode(head,se, f4);
free(se);
printNodeListDouble(head);
//獲取長(zhǎng)度
printf("listLength ====================\n");
int i = listLength(head);
printf("listLength = %d\n", i);
//搜索
printf("searchList ====================\n");
Node *pNode = searchList(head, f1);
printf("currentData = %f\n", *((double *)pNode->data));
//排序
printf("sortDouble ====================\n");
sortDouble(head);
printNodeListDouble(head);
//反轉(zhuǎn)
printf("reverseList ====================\n");
reverseList(&head);
printNodeListDouble(head);
//刪除節(jié)點(diǎn)
printf("delNode ====================\n");
delNode(&head, f1);
printNodeListDouble(head);
//銷毀
destroyList(head);
return 0;
}
到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言單向鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
shared_ptr能夠記錄對(duì)象被引用的次數(shù),主要被用來(lái)管理動(dòng)態(tài)創(chuàng)建的對(duì)象的銷毀,這里我們就來(lái)詳解C++中shared_ptr的使用教程,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了C語(yǔ)言中的數(shù)組基礎(chǔ)，介紹了其相關(guān)概念，具有一定參考價(jià)值。需要的朋友可以了解下，希望能夠給你帶來(lái)幫助2021-11-11
利用C語(yǔ)言來(lái)求最大連續(xù)子序列乘積的方法
這篇文章主要介紹了利用C語(yǔ)言來(lái)求最大連續(xù)子序列乘積的方法,基本的思路以外文中還附有相關(guān)ACM題目,需要的朋友可以參考下2015-08-08
QT通過(guò)C++線程池運(yùn)行Lambda自定義函數(shù)流程詳解
最近在接觸公司的一個(gè)QT桌面項(xiàng)目，其中里面有一個(gè)模塊是使用線程池去運(yùn)行自定義函數(shù)的，自己潛心研究那個(gè)線程池代碼一天，發(fā)現(xiàn)研究不透，看不懂，里面幾乎都是使用C++11的新特性進(jìn)行編寫2022-10-10
一篇文章帶你了解C++多態(tài)的實(shí)現(xiàn)原理
這篇文章主要介紹了C++多態(tài)的實(shí)現(xiàn)機(jī)制理解的相關(guān)資料,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下，希望能給你帶來(lái)幫助2021-08-08
既然在創(chuàng)建對(duì)象時(shí)有構(gòu)造函數(shù)（給成員初始化），那么在銷毀對(duì)象時(shí)應(yīng)該還有一個(gè)清除成員變量數(shù)據(jù)的操作咯，析構(gòu)函數(shù)與構(gòu)造函數(shù)功能相反，析構(gòu)函數(shù)不是完成對(duì)象的銷毀，局部對(duì)象銷毀工作是由編譯器完成的。而對(duì)象在銷毀時(shí)會(huì)自動(dòng)調(diào)用析構(gòu)函數(shù)，完成類的一些資源清理工作2022-06-06
c++動(dòng)態(tài)規(guī)劃經(jīng)典算法
動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。本文主要介紹了c++動(dòng)態(tài)規(guī)劃經(jīng)典算法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
OpenCV圖像變換與處理實(shí)戰(zhàn)方法記錄
這篇文章主要給大家介紹了關(guān)于OpenCV圖像變換與處理實(shí)戰(zhàn)的相關(guān)資料,包括重映射、縮放、旋轉(zhuǎn)、顏色變換、邊緣檢測(cè)、高斯模糊、圖像銳化和顏色反轉(zhuǎn)等,通過(guò)實(shí)例分析詳細(xì)解釋了這些功能的實(shí)現(xiàn)原理和代碼實(shí)現(xiàn),需要的朋友可以參考下2024-12-12
這篇文章主要介紹了在C++中加載TorchScript模型的方法，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-02-02
Windows注冊(cè)表中修改UAC(用戶賬號(hào)控制)及批處理腳本
今天小編就為大家分享一篇關(guān)于Windows注冊(cè)表中修改UAC(用戶賬號(hào)控制)及批處理腳本，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12