化抽象为直观理解单链表操作C语言实现

发布时间:2024年01月04日

绪论

单链表是一种常见的线性表数据结构,由一系列节点组成。每个节点包含两个部分:数据域和指针域。

数据域存储节点的数据元素,可以是任意类型的数据。指针域存储指向下一个节点的指针,用来建立节点之间的链接关系。

单链表的特点是每个节点只有一个指针指向下一个节点,最后一个节点的指针指向空(NULL),表示链表的结束。

通过这种方式,多个节点按照顺序连接在一起,形成一个链式结构。我们可以通过头节点来访问整个链表,从头节点开始,沿着指针域依次访问每个节点,直到到达最后一个节点。

单链表的优点是插入和删除操作的时间复杂度为O(1),即常数时间。但是查找某个节点的时间复杂度为O(n),需要从头节点开始遍历整个链表。

总结起来,单链表是一种动态的数据结构,可以高效地进行插入和删除操作,但查找操作相对较慢

一、直接知识点运用

指针:点击查看上期的文章:理解C语言中的指针只需要两个案例
结构体:点击查看上期的文章:理解C语言中的结构体只需要一个案例

二、全局架构

1、实现目标

  • List item

  • 单链表初始化

  • 创建单链表

  • 在单链表中插入元素

  • 打印出单链表元素

  • 删除单链表元素

  • 按位查找单链表元素

  • 按值查找单链表元素

2、实现截图

在这里插入图片描述

3、实现完整代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef struct LNode{
	int data; //节点数据域
	struct LNode* next; //结点指针
}LNode,*LinkList;

//初始化
LNode* Init_LinkList(LNode *L){
	if(L==NULL){
		printf("分配内存失败");
		return NULL;
	}
	L->data=0;
	L->next=NULL;
	return L;
}
//插入链表:头插法 
bool headInsertLink(LNode *L){
	LNode *newCode;
	int newdata;
	printf("输入一个数据,输入9999结束\n");
	scanf("%d",&newdata);
	while(newdata!=9999){
		newCode =(LNode*)malloc(sizeof(LNode));
		newCode->next=L->next;
		L->next=newCode;
		newCode->data=newdata;
		L->data++;
		printf("输入一个数据,输入9999结束\n");
		scanf("%d",&newdata);
	}
}
//尾插法插入元素
bool tailInsertLink(LNode *L){
	LNode *newNode;
	LNode *TailNode=L;
	int newdata;
	while(TailNode->next!=NULL){
		TailNode=TailNode->next;
	}
	printf("请输入插入的元素,输入9999停止\n");
	scanf("%d",&newdata);
	while(newdata!=9999){
		newNode=(LNode*)malloc(sizeof(LNode));
		newNode->data=newdata;
		newNode->next=NULL;
		TailNode->next=newNode;
		TailNode=newNode;
		L->data++;
		printf("请输入插入的元素,输入9999停止\n");
		scanf("%d",&newdata);
	}
} 
//按位查找元素
LNode* getElement(LNode *L,int i){
	//判断i合法性
	LNode *p=L;
	if(i==0){
		printf("i=0不合法\n");
		return 0;
	}if(i<1 || i>L->data){
		printf("超出区域\n"); 
		return 0;
	}
	int j=0;
	for(j=0;j<i;j++){
		p=p->next;
	}
	return p;
} 
//按值查找
LNode* getElementValue(LNode *L,int e){
	int count =0;
	//判断空
	if(L->next==NULL){
		printf("链表为空");
		return NULL;
	} 
	LNode *p=L;
	while(p->next){
		p=p->next;
		count++;
		if(p->data==e){
			return count;
		}
	}
	return NULL; 
} 
//按位删除
bool delLinkList(LNode *L,int i){
	// 鉴定为空
	if(!L->next){
		printf("链表为空\n");
		return false;
	}if(i<1 || i>(L->data)){
		printf("超过阈值\n");
		return false ;
	}
	LNode *p = getElement(L,i-1);
	LNode *q = p->next;
	p->next = q->next;
	free(q);
	L->data--;
	return true;
} 
//打印链表
bool printfLink(LinkList L){
	LNode *p=L;
	while(p->next){
		p=p->next;
		printf("data-->%d\n",p->data);
	}
	printf("结束\n");
	return true;
} 

int main(){
	LNode *L_Init=(LNode*)malloc(sizeof(LNode));
	//初始化 
	LinkList L = Init_LinkList(L_Init);
	printf("初始化后的链表内容:%d\n",L->data);
	//头插法插入元素
	printf("开始头插法插入元素\n");
	headInsertLink(L); 
	//打印链表
	printfLink(L); 
	printf("开始尾插法插入元素\n");
	//尾插法插入元素
	tailInsertLink(L); 
	//打印链表
	printfLink(L); 
	//查找元素
	printf("L[4]的元素是:%d\n",getElement(L,4)->data);
	//按值查找
	printf("2在链表中的%d位置",getElementValue(L,2)); 
	printf("删除链表元素\n") ;
	//删除操作
	delLinkList(L,2);
	//打印链表
	printfLink(L);  
	free(L);
	return 0;
}

三、逐步分析

1、结构体设计

单链表节点中有一个数据域和一个节点指针,所以先构建一一个结构体

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//结构体
typedef struct LNode{
	int data;//数据域
	struct LNode* next; //指针域 
}LNode; 

int main(){
	return 0;
}

2、进行初始化

所谓的初始化就是创建一个头节点
在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//结构体
typedef struct LNode{
	int data;//数据域
	struct LNode* next;  //指针域 
}LNode; 
//初始化 
LNode* Init_Link(LNode *L){
	//鉴定是否分配空间成功 
	if(L==NULL){
		printf("内存分配失败,初始化失败\n");
		return NULL; 
	}
	L->data=0;
	L->next=NULL;//初始化头节点指针指向的数据为空 
}
int main(){
	LNode *L_Room=(LNode*)malloc(sizeof(LNode));//为其分配一个空间内存 
	//初始化调用 
	LNode *L=Init_Link(L_Room);
	//打印初始化链表
	printf("初始化头节点:%d\n",L->data);
	return 0;
}

3、打印节点元素数据

因为我们现在已经创建了一个节点所以可以进行打印操作
打印操作的逻辑是:在单链表中一直循环,只要节点的元素指针指向部位NULL说明还未循环结束。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//结构体
typedef struct LNode{
	int data;//数据域
	struct LNode* next;  //指针域 
}LNode; 

//初始化 
LNode* Init_Link(LNode *L){
	//鉴定是否分配空间成功 
	if(L==NULL){
		printf("内存分配失败,初始化失败\n");
		return NULL; 
	}
	L->data=0;
	L->next=NULL;//初始化头节点指针指向的数据为空 
	return L; 
}

//打印数据元素
bool print_Link(LNode *L){
	LNode *p=L;
	while(p->next){
		p=p->next;
		printf("data-->%d\n",p->data); 
	}
	printf("####打印结束####\n");
	return true; 
}
int main(){
	LNode *L_Room=(LNode*)malloc(sizeof(LNode));//为其分配一个空间内存 
	//初始化调用 
	LNode *L=Init_Link(L_Room);
	//打印初始化链表
	printf("初始化头节点:%d\n",L->data); 
	printf("###打印初始单链表节点####\n");
	print_Link(L); 
	return 0;
}

4、插入元素操作

插入元素分为两种:

  • 头插法
  • 尾插法
    区别就是表面的意思:从头节点插入,从尾节点插入。
    在这里插入图片描述

4.1头节点代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//结构体
typedef struct LNode{
	int data;//数据域
	struct LNode* next;  //指针域 
}LNode; 

//初始化 
LNode* Init_Link(LNode *L){
	//鉴定是否分配空间成功 
	if(L==NULL){
		printf("内存分配失败,初始化失败\n");
		return NULL; 
	}
	L->data=0;
	L->next=NULL;//初始化头节点指针指向的数据为空 
	return L; 
}
//头节点插入法
bool headInsert(LNode *L){
	//创建一个节点 
	LNode *newNode;
	//判断链表初始化是否成功
	if(L==NULL){
		printf("链表未能初始化成功,请检查\n");
		return false; 
	} 
	//开始定义创建的节点数据域元素
	int newData;
	printf("开始输入数据域元素,输入9999结束\n");
	scanf("%d",&newData);
	while(newData!=9999){
		newNode = (LNode*)malloc(sizeof(LNode)); //为新节点分配一个内存空间 
		newNode->next= L->next; //新节点连接头节点的下一个节点 
		L->next=newNode;//头节点下一个节点为新插入节点 
		newNode->data=newData;//新插入节点数据域赋值 
		L->data++; //增加链表的长度 
		printf("开始输入数据域元素,输入9999结束\n");
		scanf("%d",&newData);
	}
	printf("####头插法结束####\n");
} 
//打印数据元素
bool print_Link(LNode *L){
	LNode *p=L;
	while(p->next){
		p=p->next;
		printf("data-->%d\n",p->data); 
	}
	printf("####打印结束####\n");
	return true; 
}
int main(){
	LNode *L_Room=(LNode*)malloc(sizeof(LNode));//为其分配一个空间内存 
	//初始化调用 
	LNode *L=Init_Link(L_Room);
	//打印初始化链表
	printf("初始化头节点:%d\n",L->data); 
	//头插法插入元素
	headInsert(L); 
	printf("###打印初始单链表节点####\n");
	print_Link(L); 
	return 0;
}

在这里插入图片描述
不难看出头插法插入的元素是反着的

4.2尾节点代码

给出核心代码部分

//尾插法
bool TailInsert(LNode *L){
	//创建一个新插入的元素
	LNode *newNode;
	int  newData;
	//创建一个尾节点
	LNode *TailNode =L;
	//初始化尾节点
	while(TailNode->next!=NULL){
		TailNode=TailNode->next;
	} 
	printf("开始输入数据域元素,输入9999结束\n");
	scanf("%d",&newData);
	while(newData!=9999){
		newNode = (LNode*)malloc(sizeof(newNode));
		newNode->data=newData;
		newNode->next=NULL;
		TailNode->next=newNode;
		TailNode=newNode;
		L->data++;
		printf("开始输入数据域元素,输入9999结束\n");
		scanf("%d",&newData);
	} 
}

在这里插入图片描述

5、按位查找元素操作

这个就相对简单些,按位查找顾名思义就是按找链表中的位置查找,我们已查找第2位元素为例看完整代码:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
//结构体
typedef struct LNode{
	int data;//数据域
	struct LNode* next;  //指针域 
}LNode; 

//初始化 
LNode* Init_Link(LNode *L){
	//鉴定是否分配空间成功 
	if(L==NULL){
		printf("内存分配失败,初始化失败\n");
		return NULL; 
	}
	L->data=0;
	L->next=NULL;//初始化头节点指针指向的数据为空 
	return L; 
}
//头节点插入法
bool headInsert(LNode *L){
	//创建一个节点 
	LNode *newNode;
	//判断链表初始化是否成功
	if(L==NULL){
		printf("链表未能初始化成功,请检查\n");
		return false; 
	} 
	//开始定义创建的节点数据域元素
	int newData;
	printf("开始输入数据域元素,输入9999结束\n");
	scanf("%d",&newData);
	while(newData!=9999){
		newNode = (LNode*)malloc(sizeof(LNode)); //为新节点分配一个内存空间 
		newNode->next= L->next; //新节点连接头节点的下一个节点 
		L->next=newNode;//头节点下一个节点为新插入节点 
		newNode->data=newData;//新插入节点数据域赋值 
		L->data++; //增加链表的长度 
		printf("开始输入数据域元素,输入9999结束\n");
		scanf("%d",&newData);
	}
	printf("####头插法结束####\n");
}
//尾插法
bool TailInsert(LNode *L){
	//创建一个新插入的元素
	LNode *newNode;
	int  newData;
	//创建一个尾节点
	LNode *TailNode =L;
	//初始化尾节点
	while(TailNode->next!=NULL){
		TailNode=TailNode->next;
	} 
	printf("开始输入数据域元素,输入9999结束\n");
	scanf("%d",&newData);
	while(newData!=9999){
		newNode = (LNode*)malloc(sizeof(newNode));
		newNode->data=newData;
		newNode->next=NULL;
		TailNode->next=newNode;
		TailNode=newNode;
		L->data++;
		printf("开始输入数据域元素,输入9999结束\n");
		scanf("%d",&newData);
	} 
} 
//按位查找
LNode* LocGetElement(LNode *L,int i){
	LNode *p=L;
	//判断i是否 
	if(i<1 || i>i){
		printf("超出范围\n");
		return NULL;
	}if(i==0){
		printf("不合法");
		return NULL;
	}
	int j=0;
	for(j=0;j<i;j++){
		p=p->next;
	}
	return p;
} 

//打印数据元素
bool print_Link(LNode *L){
	LNode *p=L;
	while(p->next){
		p=p->next;
		printf("data-->%d\n",p->data); 
	}
	printf("####打印结束####\n");
	return true; 
}

int main(){
	LNode *L_Room=(LNode*)malloc(sizeof(LNode));//为其分配一个空间内存 
	//初始化调用 
	LNode *L=Init_Link(L_Room);
	//打印初始化链表
	printf("初始化头节点:%d\n",L->data); 
	//头插法插入元素
	headInsert(L); 
	//尾插法插入元素 
	TailInsert(L); 
	printf("###打印初始单链表节点####\n");
	print_Link(L); 
	printf("###打印初始单链表节点####\n");
	printf("按位查找第2个元素是%d\n",LocGetElement(L,2)->data) ;
	return 0;
}

在这里插入图片描述

文章来源:https://blog.csdn.net/weixin_52312427/article/details/135361466
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。