C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之單鏈表
更新時(shí)間：2021年12月23日 14:22:50 作者：玄澈_
單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。本文將為大家介紹C語(yǔ)言中單鏈表的基本概念與讀取數(shù)據(jù)元素，需要的可以參考一下
基本概念
鏈表的每一個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域
優(yōu)點(diǎn) : 儲(chǔ)存空間利用高效
舉例來說：
typedef struct student{
int id; //學(xué)生編號(hào)
char* name; //學(xué)生名稱
//指向下一結(jié)點(diǎn)的指針
struct Student* pNext;
}Student;
與之相反的是多鏈表
typedef struct student{
int id; //學(xué)生編號(hào)
char* name; //學(xué)生名稱
//指向下一結(jié)點(diǎn)的指針
struct Student* pNext;
struct Student* qNext;
}Student;
讀取數(shù)據(jù)元素
獲取第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素
- 聲明一個(gè)結(jié)點(diǎn)指針p指向鏈表的第一個(gè)結(jié)點(diǎn)a1，初始化j從1開始
- 當(dāng)j < i 時(shí)，遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j 累加 1
- 當(dāng)鏈表末尾 p 為空時(shí)，則說明第 i 個(gè)元素不存在；否則查找成功，返回結(jié)點(diǎn) p 的數(shù)據(jù)
?
1.定義數(shù)據(jù)元素
//定義數(shù)據(jù)元素
typedef struct student{
int id;
char* name;
}ElementType;
2.定義順序表結(jié)構(gòu)
typedef struct {
ElementType dates[MAX_SIZE]; //當(dāng)前順序表中的數(shù)據(jù)集合
int length; //當(dāng)前順序表中的元素個(gè)數(shù)
}SeqList;
3.定義鏈表的結(jié)點(diǎn)（包括數(shù)據(jù)域和指針域）
typedef struct Node {
ElementType date; //數(shù)據(jù)域
struct Node* node; //指針域，指向下一個(gè)結(jié)點(diǎn)
}Node;
4.設(shè)置頭結(jié)點(diǎn)
我們?cè)诙x鏈表時(shí)，習(xí)慣性的會(huì)定義頭結(jié)點(diǎn)，以便統(tǒng)一鏈表結(jié)點(diǎn)的插入和刪除操作
typedef struct Linklist {
Node* next; //頭指針
int length;
}Linklist;
如果鏈表有頭結(jié)點(diǎn)，next就指向頭結(jié)點(diǎn)，沒有就指向第一個(gè)結(jié)點(diǎn)
鏈表的長(zhǎng)度初始值為0
插入數(shù)據(jù)元素?
在第i個(gè)結(jié)點(diǎn)后插入數(shù)據(jù)元素 ?
- 創(chuàng)建一個(gè)空節(jié)點(diǎn)，分配內(nèi)存空間，設(shè)置數(shù)據(jù)元素
- 獲取第i個(gè)結(jié)點(diǎn)，設(shè)置新結(jié)點(diǎn)的后繼結(jié)點(diǎn)為該結(jié)點(diǎn)的后繼結(jié)點(diǎn)
- 設(shè)置第i個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)為該結(jié)點(diǎn)
1.創(chuàng)建空節(jié)點(diǎn)并為數(shù)據(jù)域賦值
//創(chuàng)建空節(jié)點(diǎn)并為數(shù)據(jù)賦值
Node* node = (Node*)malloc(sizeof(Node));
node -> date = element;
node -> next = NULL;
2.通過循環(huán)找到要插入的結(jié)點(diǎn)
for (int i = 1; currNode && i < pos - 1; i++)
{
currNode = currNode->next;
}
3.將結(jié)點(diǎn)插入并對(duì)接前面的結(jié)點(diǎn)
if (currNode) {
node->next = currNode->next;
currNode->next = node;
linkList->length++;
}
初始化鏈表
void InitLinkList(LinkList* linkList, ElementType* dateArrar, int length)
{
for (int i = 0; i < length; i++) {
InsertLinkList(linkList, i + 1, dateArrar[i]);
}
}
打印鏈表
void PrintLinkList(LinkList* linklist)
{
Node* node = linklist->next;
if (!node)
{
printf("鏈表為空！\n");
linklist->length = 0;
return 0;
}
for (int i = 0; i < linklist->length; i++) {
printf("%d\t%s\t\n", node->date.id, node->date.name);
node = node->next;
}
}
順序表查空
int IsLinkListEmpty(LinkList* linkList) {
return linkList->length == 0 ? TRUE : FALSE;
}
順序表的刪除?
刪除第i個(gè)結(jié)點(diǎn)及其數(shù)據(jù)元素
- 獲取第i個(gè)結(jié)點(diǎn)，若該結(jié)點(diǎn)不是第一個(gè)結(jié)點(diǎn)，則獲取第i - 1個(gè)結(jié)點(diǎn)
- 將第i -1個(gè)結(jié)點(diǎn)的后綴結(jié)點(diǎn)設(shè)為第i個(gè)結(jié)點(diǎn)的后綴結(jié)點(diǎn)
- 刪除第i個(gè)結(jié)點(diǎn)，釋放內(nèi)存空間，記錄并返回刪除數(shù)據(jù)元素的值
情況1：當(dāng)刪除的是第一個(gè)元素
if (pos == 1)
{
node = linkList->next;
if (node) {
element = node->date;
linkList->next = node->next;
free(node); //釋放被刪除的結(jié)點(diǎn)
linkList->length--;
}
return element;
}
情況2：除第一個(gè)結(jié)點(diǎn)外
- 找到要?jiǎng)h除的結(jié)點(diǎn)和他的前綴結(jié)點(diǎn)
- 要?jiǎng)h除結(jié)點(diǎn)的next 賦值給前綴結(jié)點(diǎn)
- 釋放要?jiǎng)h除的結(jié)點(diǎn)
Node* preNode; //前綴結(jié)點(diǎn)
node = linkList->next;
for (int i = 1; node && i < pos; i++)
{
preNode = node;
node = node->next;
}
if (node)
{
element = node->date;
preNode->next = node->next;
free(node);
linkList->length--;
}
return element;
完整代碼
ElementType DeleteLinkListElement(LinkList* linkList, int pos)
{
ElementType element; //被刪除的元素
element.id = -999; //賦一個(gè)不可能的值，來判斷刪除是否成功
Node* node = NULL;
if (pos == 1)
{
node = linkList->next;
if (node) {
element = node->date;
linkList->next = node->next;
free(node); //釋放被刪除的結(jié)點(diǎn)
linkList->length--;
}
}
Node* preNode; //前綴結(jié)點(diǎn)
node = linkList->next;
for (int i = 1; node && i < pos; i++)
{
preNode = node;
node = node->next;
}
if (node)
{
element = node->date;
preNode->next = node->next;
free(node);
linkList->length--;
}
return element;
}
刪除單鏈表整表
- 聲明結(jié)點(diǎn)p 和 q
- 將第一個(gè)結(jié)點(diǎn)賦值給p
- 循環(huán)將下一個(gè)結(jié)點(diǎn)賦值給q，釋放p，將q賦值給p
?
void CleatLinkList(LinkList* linkList)
{
Node* node = linkList->next;
Node* nextNode;
while (node) {
nextNode = node->next; //先記錄當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，以便釋放當(dāng)前結(jié)點(diǎn)的內(nèi)存
free(node);
node = nextNode;
}
linkList->next = NULL;
linkList->length = 0;
}
單鏈表VS順序表
?
?
以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之單鏈表的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言單鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
關(guān)于嘗試開發(fā)PHP的MYSQL擴(kuò)展的使用
本篇文章小編將為大家介紹，關(guān)于嘗試開發(fā)PHP的MYSQL擴(kuò)展的使用，需要的朋友可以參考一下2013-04-04
C語(yǔ)言實(shí)現(xiàn)線性表的基本操作詳解
線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列，這篇文章帶你學(xué)習(xí)如何通過C語(yǔ)言實(shí)現(xiàn)線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)2021-11-11
C語(yǔ)言實(shí)現(xiàn)變色進(jìn)度條
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)一個(gè)變色的進(jìn)度條，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
C語(yǔ)言深入探究動(dòng)態(tài)規(guī)劃之線性DP
線性動(dòng)態(tài)規(guī)劃，是較常見的一類動(dòng)態(tài)規(guī)劃問題，其是在線性結(jié)構(gòu)上進(jìn)行狀態(tài)轉(zhuǎn)移，這類問題不像背包問題、區(qū)間DP等有固定的模板，線性動(dòng)態(tài)規(guī)劃的目標(biāo)函數(shù)為特定變量的線性函數(shù)，約束是這些變量的線性不等式或等式，目的是求目標(biāo)函數(shù)的最大值或最小值2022-04-04
關(guān)于Qt添加opencv和libtorch庫(kù)的問題
這篇文章主要介紹了Qt添加opencv和libtorch庫(kù)的相關(guān)知識(shí)，兩種方法一種是通過手動(dòng)添加，一種是通過qt creator添加,需要的朋友可以參考下2022-01-01
這篇文章介紹了Qt設(shè)置QTextEdit行高的方法，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
c++實(shí)現(xiàn)reactor高并發(fā)服務(wù)器的詳細(xì)教程
這篇文章主要介紹了c++從零實(shí)現(xiàn)reactor高并發(fā)服務(wù)器,包括環(huán)境準(zhǔn)備和基礎(chǔ)知識(shí)介紹,本文給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-03-03
這篇文章主要介紹了c++自帶的查找函數(shù),本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-09-09
這篇文章主要介紹了c++ 智能指針基礎(chǔ)的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)使用c++，感興趣的朋友可以了解下2021-02-02
Inline Hook(ring3)的簡(jiǎn)單C++實(shí)現(xiàn)方法
這篇文章主要介紹了Inline Hook(ring3)的簡(jiǎn)單C++實(shí)現(xiàn)方法,需要的朋友可以參考下2014-08-08