化抽象为直观理解单链表操作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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- Pytest自动化的坑
- CSharp--复习篇
- 基于 pytorch-openpose 实现 “多目标” 人体姿态估计
- 完全卸载 Office 2019 for Mac
- 动态新增input输入框
- phpyun 7.0补丁升级后由于缓存极致bug造成“网络招聘会”栏目不能显示，给小程序上架审核造成影响解决方法如下
- 浅谈安科瑞ADL200仪表在爱尔兰工厂的应用
- 变分自编码器VAE模型与应用
- python之pyQt5实例：鼠标点击+输入创建点
- 深入理解Java反射机制