C語言實現(xiàn)單鏈表的基本操作分享

更新時間：2022年10月23日 14:53:48 作者：從未止步..

單鏈表是一種鏈式存取的數(shù)據(jù)結構，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。本文將為大家介紹C語言中單鏈表的基本操作，需要的可以參考一下

導語

無論是順序存儲結構還是鏈式存儲結構，在內存中進行存放元素的時候，不僅需要存放該元素的相關信息，還需要存放該元素和其他元素之間的關系，而我們之前所學的順序表“與生俱來”的物理結構自然地能夠表達出元素和元素之間的關系，不需要額外的信息去表達元素和元素之間的關系，而對于鏈式存儲這種非順序存儲的結構，需要額外附加指針去表示這種關系。

單鏈表

每個結點除了存放數(shù)據(jù)元素外，還要存儲指向下一個節(jié)點的指針。

單鏈表的特點

優(yōu)點：不要求大片連續(xù)空間，改變容量方便

缺點：不可隨機存取，要耗費一定空間存放指針

定義

typedef struct LNode {
	int data;
	struct LNode* next;//指針指向下一個節(jié)點，指針的類型為節(jié)點類型；
}*LinkNode;//聲明*LinkNode為結構體指針類型

除了上述這種方法外，我們還可以先先聲明LinkNode為結構體類型，在使用該類型的時候，將對應的變量定義為指針即可。

單鏈表分為帶頭結點和不帶頭結點，我們一般主要學習帶頭結點的。

初始化操作

在所有的操作之前，我們首先需要建立一個空的單鏈表，那么首先需要做的就是分配頭結點。

void InistLinkNode(LinkNode& L) {
	L = (LNode*)malloc(sizeof(LNode));//分配頭結點
	L->next = NULL;
}

頭插法

“頭插法”顧名思義就是將元素插入到頭結點之后，插入一次好像和我們通常所講的插入沒什么區(qū)別，但多次這樣插到頭結點之后，也就是“第一個真正的節(jié)點”，那么是不是會產生一種現(xiàn)象，它最終的存儲數(shù)據(jù)和我們所插入時的順序是相反的。

void InsertLinkNode(LinkNode& L) {
	LNode* s;
	int x,Length;
	printf("請輸入你要插入的元素個數(shù)：");
	scanf("%d", &Length);
	printf("請輸入你要插入的元素：\n");
	for (int j = 0; j < Length; j++) {
		s = (LNode*)malloc(sizeof(LNode));//每插入一個元素之前，都需要給它分配節(jié)點空間
		scanf("%d", &x);
		s->data = x;
		s->next = L->next;
		L->next = s;
	}

}

通過程序驗證以下：

尾插法

“尾插法”顧名思義就是將元素插入到表尾，也就是我們普通的插入，那么怎么要找到表尾的位置呢？在順序表中，我們完全可以利用它順序存儲結構的天然特性，通過下標即可以找到，但是單鏈表是沒有辦法的，我們只有兩種方式，要么循環(huán)遍歷，要么嘗試在表尾的地方做個標記。

那么那種方法是好的呢？

答案是第二種！循環(huán)遍歷的方式，如果只插入一個元素看似沒什么問題，但如果多次的重復遍歷循環(huán)無疑增加了時間復雜度，這顯然不是好的方法。

第二個方法就不存在時間復雜度的問題，只需要在表尾位置做個標記，使它永遠指向表尾即可。

void TailInsertLinkNode(LinkNode& L) {
	LNode* s,*r;
	int x,Length;
	r = L;//r為表尾指針
	printf("請輸入你要插入的元素個數(shù)：");
	scanf("%d", &Length);
	printf("請輸入你要插入的元素：\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為當前的表尾指針，將他的值賦值給r----使r永遠指向表尾
	}
	printf("\n");
	r->next = NULL;
}

刪除第i個元素

既然要刪除某個元素，那么首先我們需要保證這個元素是非NULL，其次，我們還需要保證它前面的那個節(jié)點也是非NULL，為什么呢？因為如果將該元素從鏈表中刪除后，只有前面節(jié)點非NULL的情況下，才可以實現(xiàn)后續(xù)元素和前面子表的連接。

void DeleteLinkNode(LinkNode& L) {
	int x, j = 0,e;
	printf("請輸入你要刪除的元素位序：\n");
	scanf("%d", &x);
	LNode*p = L;
	while (p != NULL && j < x - 1) {//尋找要刪除元素前的元素
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		printf("不存在我們要刪除的元素！");
	}
	if (p->next == NULL)//判斷該要刪除的節(jié)點是否為NULL
	{
		printf("不存在我們要刪除的元素！");
	}
	LNode* q = p->next;//q為我們要刪除的節(jié)點
	e = q->data;
	p->next = q->next;
	free(q);//需要及時的將刪除了的元素空間進行釋放
}

其他的基本操作都是很常規(guī)化的，這里就不單獨的進行解釋了，需要注意的點，我會在文章結尾部分的完整代碼的注釋中展出。

在第i個位置插入

void IncreaseLinkNode(LinkNode& L) {
	printf("請輸入你要插入的元素和位序：（元素和位序之間用逗號隔開）\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ā)生改變，否則會出現(xiàn)無法和后面的節(jié)點；

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));//分配頭結點
	L->next = NULL;
}
//頭插法
void InsertLinkNode(LinkNode& L) {
	LNode* s;
	int x,Length;
	printf("請輸入你要插入的元素個數(shù)：");
	scanf("%d", &Length);
	printf("請輸入你要插入的元素：\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("請輸入你要插入的元素個數(shù)：");
	scanf("%d", &Length);
	printf("請輸入你要插入的元素：\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個元素
void GetElemLinkNode(LinkNode& L) {
	printf("請輸入你要查找的元素位序：\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("元素位序為%d的元素是%d",i, s->data);
	}
	printf("\n");
}
//刪除第i個元素
void DeleteLinkNode(LinkNode& L) {
	int x, j = 0,e;
	printf("請輸入你要刪除的元素位序：\n");
	scanf("%d", &x);
	LNode*p = L;
	while (p != NULL && j < x - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		printf("不存在我們要刪除的元素！");
	}
	if (p->next == NULL)
	{
		printf("不存在我們要刪除的元素！");
	}
	LNode* q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
}
//在第i個位置插入
void IncreaseLinkNode(LinkNode& L) {
	printf("請輸入你要插入的元素和位序：（元素和位序之間用逗號隔開）\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("請輸入你要查找的元素:\n");
	scanf("%d", &x);
	while (p != NULL && p->data != x) {
		p = p->next;
		j++;
	}
	if (p == NULL) {
		printf("您要查找的元素不存在！");
	}
	else {
		printf("你要查找的元素%d的位序為%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);
}

輸出：

到此這篇關于C語言實現(xiàn)單鏈表的基本操作分享的文章就介紹到這了,更多相關C語言單鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

你真的理解C語言qsort函數(shù)嗎?帶你深度剖析qsort函數(shù)
這篇文章主要介紹了你真的理解C語言qsort函數(shù)嗎?帶你深度剖析qsort函數(shù),本篇將引入一個庫函數(shù)來實現(xiàn)我們希望的順序，結合示例代碼給大家介紹的非常詳細，需要的朋友可以參考下
2023-02-02
C語言斷言函數(shù)assert()的學習筆記
在C語言庫函數(shù)中提供了一個輔助調試程序的小型庫，它是由assert()宏組成，本文就詳細的介紹了一下如何使用，感興趣的可以了解一下
2021-11-11
如何使用C++結合OpenCV進行圖像處理與分類
在計算機視覺領域,OpenCV與C++結合能高效處理和分類圖像,C++的高執(zhí)行效率適合大規(guī)模數(shù)據(jù)處理,OpenCV提供豐富的功能,如圖像預處理和機器學習算法,安裝OpenCV需要配置環(huán)境和添加庫文件,本文詳細介紹了使用C++和OpenCV進行圖像分類的過程,包括使用SVM和深度學習模型
2024-09-09
C++類和對象到底是什么
C++ 是一門面向對象的編程語言，理解 C++，首先要理解類（Class）和對象（Object）這兩個概念。下面和小編一起來學習吧
2021-09-09
C++實現(xiàn)Matlab的zp2tf函數(shù)的示例代碼
matlab?的?zp2tf?函數(shù)的作用是將極點形式的?H(s)?函數(shù)的分母展開，本文主要為大家介紹了C++實現(xiàn)Matlab的zp2tf函數(shù)示例代碼，需要的可以參考一下
2023-04-04
深入探究C++中的容器適配器與仿函數(shù)技術
C++中的容器適配器和仿函數(shù)是實現(xiàn)數(shù)據(jù)結構與算法的重要技術，容器適配器可以將一個容器轉換為另一個形式，仿函數(shù)則可以自定義數(shù)據(jù)類型的比較、排序、計算等行為，提高程序的靈活性和可重用性
2023-04-04
C++適用入門同學的模板講解
人們需要編寫多個形式和功能都相似的函數(shù)，因此有了函數(shù)模板來減少重復勞動；人們也需要編寫多個形式和功能都相似的類，于是?C++?引人了類模板的概念，編譯器從類模板可以自動生成多個類，避免了程序員的重復勞動
2022-07-07
使用C/C++讀寫.mat文件的方法詳解
這篇文章主要為大家詳細介紹了使用C/C++讀寫.mat文件的方法，使用數(shù)據(jù)庫，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-03-03
C語言統(tǒng)計輸入字符各個字母出現(xiàn)頻率的解題思路
這篇文章主要介紹了C語言統(tǒng)計輸入字符各個字母出現(xiàn)頻率的解題思路，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2015-08-08
C++ xxx_cast實現(xiàn)轉換代碼實例解析
這篇文章主要介紹了C++xxx_cast轉換代碼實例解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-07-07