C語言實(shí)現(xiàn)單鏈表的基本操作分享
導(dǎo)語
無論是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，在內(nèi)存中進(jìn)行存放元素的時(shí)候，不僅需要存放該元素的相關(guān)信息，還需要存放該元素和其他元素之間的關(guān)系，而我們之前所學(xué)的順序表“與生俱來”的物理結(jié)構(gòu)自然地能夠表達(dá)出元素和元素之間的關(guān)系，不需要額外的信息去表達(dá)元素和元素之間的關(guān)系，而對(duì)于鏈?zhǔn)酱鎯?chǔ)這種非順序存儲(chǔ)的結(jié)構(gòu)，需要額外附加指針去表示這種關(guān)系。
單鏈表
每個(gè)結(jié)點(diǎn)除了存放數(shù)據(jù)元素外，還要存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針。
單鏈表的特點(diǎn)
優(yōu)點(diǎn)：不要求大片連續(xù)空間，改變?nèi)萘糠奖?/p>
缺點(diǎn)：不可隨機(jī)存取，要耗費(fèi)一定空間存放指針
定義
typedef struct LNode {
int data;
struct LNode* next;//指針指向下一個(gè)節(jié)點(diǎn)，指針的類型為節(jié)點(diǎn)類型；
}*LinkNode;//聲明*LinkNode為結(jié)構(gòu)體指針類型
除了上述這種方法外，我們還可以先先聲明LinkNode為結(jié)構(gòu)體類型，在使用該類型的時(shí)候，將對(duì)應(yīng)的變量定義為指針即可。
單鏈表分為帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)，我們一般主要學(xué)習(xí)帶頭結(jié)點(diǎn)的。
初始化操作
在所有的操作之前，我們首先需要建立一個(gè)空的單鏈表，那么首先需要做的就是分配頭結(jié)點(diǎn)。
void InistLinkNode(LinkNode& L) {
L = (LNode*)malloc(sizeof(LNode));//分配頭結(jié)點(diǎn)
L->next = NULL;
}
頭插法
“頭插法”顧名思義就是將元素插入到頭結(jié)點(diǎn)之后，插入一次好像和我們通常所講的插入沒什么區(qū)別，但多次這樣插到頭結(jié)點(diǎn)之后，也就是“第一個(gè)真正的節(jié)點(diǎn)”，那么是不是會(huì)產(chǎn)生一種現(xiàn)象，它最終的存儲(chǔ)數(shù)據(jù)和我們所插入時(shí)的順序是相反的。
void InsertLinkNode(LinkNode& L) {
LNode* s;
int x,Length;
printf("請(qǐng)輸入你要插入的元素個(gè)數(shù)：");
scanf("%d", &Length);
printf("請(qǐng)輸入你要插入的元素：\n");
for (int j = 0; j < Length; j++) {
s = (LNode*)malloc(sizeof(LNode));//每插入一個(gè)元素之前，都需要給它分配節(jié)點(diǎn)空間
scanf("%d", &x);
s->data = x;
s->next = L->next;
L->next = s;
}
}
通過程序驗(yàn)證以下：
尾插法
“尾插法”顧名思義就是將元素插入到表尾，也就是我們普通的插入，那么怎么要找到表尾的位置呢？在順序表中，我們完全可以利用它順序存儲(chǔ)結(jié)構(gòu)的天然特性，通過下標(biāo)即可以找到，但是單鏈表是沒有辦法的，我們只有兩種方式，要么循環(huán)遍歷，要么嘗試在表尾的地方做個(gè)標(biāo)記。
那么那種方法是好的呢？
答案是第二種！循環(huán)遍歷的方式，如果只插入一個(gè)元素看似沒什么問題，但如果多次的重復(fù)遍歷循環(huán)無疑增加了時(shí)間復(fù)雜度，這顯然不是好的方法。
第二個(gè)方法就不存在時(shí)間復(fù)雜度的問題，只需要在表尾位置做個(gè)標(biāo)記，使它永遠(yuǎn)指向表尾即可。
void TailInsertLinkNode(LinkNode& L) {
LNode* s,*r;
int x,Length;
r = L;//r為表尾指針
printf("請(qǐng)輸入你要插入的元素個(gè)數(shù)：");
scanf("%d", &Length);
printf("請(qǐng)輸入你要插入的元素：\n");
for (int j = 0; j < Length; j++) {
s = (LNode*)malloc(sizeof(LNode));
scanf("%d", &x);
s->data = x;
r->next = s;
r = s;//s為當(dāng)前的表尾指針，將他的值賦值給r----使r永遠(yuǎn)指向表尾
}
printf("\n");
r->next = NULL;
}
刪除第i個(gè)元素
既然要?jiǎng)h除某個(gè)元素，那么首先我們需要保證這個(gè)元素是非NULL，其次，我們還需要保證它前面的那個(gè)節(jié)點(diǎn)也是非NULL，為什么呢？因?yàn)槿绻麑⒃撛貜逆湵碇袆h除后，只有前面節(jié)點(diǎn)非NULL的情況下，才可以實(shí)現(xiàn)后續(xù)元素和前面子表的連接。
void DeleteLinkNode(LinkNode& L) {
int x, j = 0,e;
printf("請(qǐng)輸入你要?jiǎng)h除的元素位序：\n");
scanf("%d", &x);
LNode*p = L;
while (p != NULL && j < x - 1) {//尋找要?jiǎng)h除元素前的元素
p = p->next;
j++;
}
if (p == NULL)
{
printf("不存在我們要?jiǎng)h除的元素！");
}
if (p->next == NULL)//判斷該要?jiǎng)h除的節(jié)點(diǎn)是否為NULL
{
printf("不存在我們要?jiǎng)h除的元素！");
}
LNode* q = p->next;//q為我們要?jiǎng)h除的節(jié)點(diǎn)
e = q->data;
p->next = q->next;
free(q);//需要及時(shí)的將刪除了的元素空間進(jìn)行釋放
}
其他的基本操作都是很常規(guī)化的，這里就不單獨(dú)的進(jìn)行解釋了，需要注意的點(diǎn)，我會(huì)在文章結(jié)尾部分的完整代碼的注釋中展出。
在第i個(gè)位置插入
void IncreaseLinkNode(LinkNode& L) {
printf("請(qǐng)輸入你要插入的元素和位序：（元素和位序之間用逗號(hào)隔開）\n");
int x, j = 0, e;
scanf("%d,%d",&e, &x);
LNode* s = L, * r= (LNode*)malloc(sizeof(LNode));
while (j < x-1 && s != NULL) {
j++;
s = s->next;
}
r->data = e;
r->next = s->next;
s->next = r;
}
如下所示的代碼順序不能發(fā)生改變，否則會(huì)出現(xiàn)無法和后面的節(jié)點(diǎn)；
r->next = s->next; s->next = r;
完整代碼如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
int data;
struct LNode* next;
}*LinkNode;
//初始化
void InistLinkNode(LinkNode& L) {
L = (LNode*)malloc(sizeof(LNode));//分配頭結(jié)點(diǎn)
L->next = NULL;
}
//頭插法
void InsertLinkNode(LinkNode& L) {
LNode* s;
int x,Length;
printf("請(qǐng)輸入你要插入的元素個(gè)數(shù)：");
scanf("%d", &Length);
printf("請(qǐng)輸入你要插入的元素：\n");
for (int j = 0; j < Length; j++) {
s = (LNode*)malloc(sizeof(LNode));
scanf("%d", &x);
s->data = x;
s->next = L->next;
L->next = s;
}
}
//尾插法
void TailInsertLinkNode(LinkNode& L) {
LNode* s,*r;
int x,Length;
r = L;
printf("請(qǐng)輸入你要插入的元素個(gè)數(shù)：");
scanf("%d", &Length);
printf("請(qǐng)輸入你要插入的元素：\n");
for (int j = 0; j < Length; j++) {
s = (LNode*)malloc(sizeof(LNode));
scanf("%d", &x);
s->data = x;
r->next = s;
r = s;
}
printf("\n");
r->next = NULL;
}
//輸出單鏈表
void PrintLinkNode(LinkNode& L)
{
LNode* s=L->next;
printf("單鏈表元素如下：\n");
while (s != NULL) {
printf("%d", s->data);
s =s->next;
}
printf("\n");
}
//求線性表長度
void lengthLinkNode(LinkNode& L)
{
LNode* s = L->next;
int n=0;
while (s != NULL) {
n++;
s = s->next;
}
printf("單鏈表長度為：%d",n);
printf("\n");
}
//取第i個(gè)元素
void GetElemLinkNode(LinkNode& L) {
printf("請(qǐng)輸入你要查找的元素位序：\n");
int i, j = 0;
LNode* s=L;
scanf("%d", &i);
while (j < i && s != NULL) {
j++;
s = s->next;
}
if (s == NULL) {
printf("不存在我們要查找的元素！");
}
else {
printf("元素位序?yàn)?d的元素是%d",i, s->data);
}
printf("\n");
}
//刪除第i個(gè)元素
void DeleteLinkNode(LinkNode& L) {
int x, j = 0,e;
printf("請(qǐng)輸入你要?jiǎng)h除的元素位序：\n");
scanf("%d", &x);
LNode*p = L;
while (p != NULL && j < x - 1) {
p = p->next;
j++;
}
if (p == NULL)
{
printf("不存在我們要?jiǎng)h除的元素！");
}
if (p->next == NULL)
{
printf("不存在我們要?jiǎng)h除的元素！");
}
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
}
//在第i個(gè)位置插入
void IncreaseLinkNode(LinkNode& L) {
printf("請(qǐng)輸入你要插入的元素和位序：（元素和位序之間用逗號(hào)隔開）\n");
int x, j = 0, e;
scanf("%d,%d",&e, &x);
LNode* s = L, * r= (LNode*)malloc(sizeof(LNode));
while (j < x-1 && s != NULL) {
j++;
s = s->next;
}
r->data = e;
r->next = s->next;
s->next = r;
}
//查找位序
void SearchLinkNode(LinkNode &L) {
int x,j=1;
LNode* p=L->next;
printf("請(qǐng)輸入你要查找的元素:\n");
scanf("%d", &x);
while (p != NULL && p->data != x) {
p = p->next;
j++;
}
if (p == NULL) {
printf("您要查找的元素不存在！");
}
else {
printf("你要查找的元素%d的位序?yàn)?d", x, j);
}
}
int main() {
LinkNode L;
InistLinkNode(L);
/*InsertLinkNode(L);*/
TailInsertLinkNode(L);
PrintLinkNode(L);
lengthLinkNode(L);
GetElemLinkNode(L);
IncreaseLinkNode(L);
PrintLinkNode(L);
DeleteLinkNode(L);
PrintLinkNode( L);
SearchLinkNode(L);
}
輸出：
到此這篇關(guān)于C語言實(shí)現(xiàn)單鏈表的基本操作分享的文章就介紹到這了,更多相關(guān)C語言單鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++中Copy-Swap實(shí)現(xiàn)拷貝交換
本文主要介紹了C++中Copy-Swap實(shí)現(xiàn)拷貝交換，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
C++ inline內(nèi)聯(lián)函數(shù)詳解
這篇文章主要介紹了C++ inline內(nèi)聯(lián)函數(shù)詳解,有感興趣的同學(xué)可以借鑒參考下2021-02-02
這篇文章主要介紹了c語言實(shí)現(xiàn)單鏈表算法示例,需要的朋友可以參考下2014-02-02
這篇文章主要介紹了在C語言中轉(zhuǎn)換時(shí)間的基本方法,分別是mktime()函數(shù)和localtime()函數(shù)的使用,需要的朋友可以參考下2015-08-08
C語言學(xué)習(xí)之函數(shù)知識(shí)總結(jié)
函數(shù)是一組一起執(zhí)行一個(gè)任務(wù)的語句。每個(gè)?C?程序都至少有一個(gè)函數(shù)，即主函數(shù)?main()?，所有簡(jiǎn)單的程序都可以定義其他額外的函數(shù)。本文就為大家詳細(xì)講講C語言中函數(shù)的相關(guān)知識(shí)點(diǎn)，希望有所幫助2022-07-07
C++ OpenCV實(shí)戰(zhàn)之形狀識(shí)別
本案例通過使用OpenCV中的approxPolyDP進(jìn)行多邊形近似，進(jìn)而進(jìn)行基礎(chǔ)形狀識(shí)別（圓、三角形、矩形、星形…），快跟隨小編一起動(dòng)手嘗試一下2022-07-07
C++如何獲取當(dāng)前系統(tǒng)時(shí)間及格式化輸出
這篇文章主要介紹了C++如何獲取當(dāng)前系統(tǒng)時(shí)間及格式化輸出的實(shí)例代碼，主要用到time()及strftime()函數(shù)，通過實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-02-02
使用VS2022開發(fā)在線遠(yuǎn)程編譯部署的C++程序(圖文詳解)
這篇文章主要介紹了使用VS2022開發(fā)可以在線遠(yuǎn)程編譯部署的C++程序,本文分步驟通過圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-12-12
這篇文章主要為大家詳細(xì)介紹了C語言二維數(shù)組應(yīng)用之掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
特別是對(duì)源文件和頭文件的概念，需要深入對(duì)它了解,本文將詳細(xì)介紹，需要了解的朋友可以參考下2012-11-11