数据结构（使用头插法实现单链表）_头插法建立单链表-程序员宅基地
一.定义
1.线性表的链式存储就是单链表，单链表通过一组任意的存储单元来存储线性表的数据元素（逻辑相邻，存储离散），单链表对于每一个链表结点，不但存储自身数据，还开辟了存储一个指向后继结点的指针。
2.单链表相比顺序表：
优点：解决了顺序表需要大量连续存储单元的问题，单链表的数据元素离散的分布在存储空间中。
缺点：需要额外的存储空间存放指针域。
3.建立单链表可以使用头插法和尾插法两种操作，其中头插法创建的单链表数据有逆置效果。
头插法：
尾插法：
4.创建单链表可以使用头结点方便编码，也可以不使用头结点，本代码使用了头结点。
二.代码
1.使用头插法建立单链表
LinkList AddList(LinkList L){//头插法增添元素
L = (LinkList)malloc(sizeof(LNode));//创建头结点
L->length = 0;
L->next=NULL;
LNode *addPoint;
int addNum;
printf("向链表输入初始值\n");
printf("请输入要插入的内容：");
scanf("%d",&addNum);//获取插入内容
while(addNum != 99){//当输入99时结束循环
addPoint = (LNode *)malloc(sizeof(LNode));
L->length++;
addPoint->next = L->next;
L->next = addPoint;
addPoint->data = addNum;
printf("\n请输入要插入的内容(输入99结束)：");//继续输入新元素
scanf("%d",&addNum);//获取插入内容
}
return L;
}
2.遍历展示单链表
void ShowList(LinkList L){
LNode *x;//定义一个指针
int num = L->length;//num用于暂存该链表长度
printf("该链表一共有%d个元素\n",num);
// x = (LNode *)malloc(sizeof(LNode));
x = L;//将头结点的信息赋给x
x = x->next;//跳过头结点，因为头结点不存储数据
while(num>0){
printf("%d\n",x->data);//输出该节点的数据
x = x->next;//移向下一个结点
num--;//遍历总数减一
}
}3.插入数据元素
bool ListInsert(LinkList L){
int inputPosition = 0;//定义记录插入位置并初始化
int inputNum = 0;//定义记录插入数据元素的值并初始化
printf("请输入要插入的位置：");
scanf("%d",&inputPosition);//获取插入位置
printf("请输入要插入的内容：");
scanf("%d",&inputNum);//获取插入内容
if(inputPosition<1){//插入位置不能小于1
return false;
}
LNode *AtPresent;// 定义指向当前遍历到的结点的指针 （遍历指针）
int record = 0;//记录该节点的位置
AtPresent = L;// 让 遍历指针指向头结点
while(AtPresent!=NULL&&record < inputPosition-1){
//遍历条件：1.当前指针不为空 2.当前结点与目标结点位置不匹配
record++;//位置信息累加
AtPresent=AtPresent->next;//遍历指针指向下一个结点
}
if(AtPresent==NULL){//若遍历指针为空，则该链表没有目标位置结点
return false;
}
//找到目标位置后：
LNode *s = (LNode *)malloc(sizeof(LNode));//生成一个新结点
s->data = inputNum;//新结点赋值
s->next = AtPresent->next;//新结点的后继指针指向遍历结点的后继结点
AtPresent->next = s;// 遍历结点的后继指针指向新结点
L->length++;//长度+1
return true;
} 
4.按位查找（两种方法的区别在于返回值）
代码一：
bool GetElem(LinkList L){//按位查找
int getPos = 0;//定义输入位置变量
printf("请输入要查找的位置：");
scanf("%d",&getPos);//获取查找位置
LNode *x;//定义遍历指针
x = L;//将链表头指针位置赋给x
x = x->next;//头结点没有取值，因此跳过
if(getPos<1||getPos>L->length){
//判断输入是否合法
return false;
}
for(int curPos = 1;curPos<getPos;curPos++){
//遍历位置
x=x->next;
}
if(x==NULL){//没有找到
return false;
}
printf("第%d位置元素为%d\n",getPos,x->data);
return true;
}
代码二：
LinkList GetNodeElem(LinkList L,int findPos){
int record = 1;//记录位置
LNode *searchPoint = L->next;//使遍历指针指向第一个结点
if(findPos==0){
return L;//返回头结点
} else if(findPos<1){
return NULL;
}
while(searchPoint&&record<findPos){
searchPoint = searchPoint->next;
record++;
}
return searchPoint;
}5.按值查找
代码一：
bool LocateElem(LinkList L){//按值查找
int getNum = 0;
int accumulation = 0;
printf("请输入要查找的值：");
scanf("%d",&getNum);//获取要查询的值
LNode *x;//定义遍历指针
x = L;
x = x->next;
for(int record = 1;record<L->length;record++){//遍历链表
if(x->data == getNum){
printf("第%d个位置存储了%d\n",record,getNum);
accumulation++;
}
x = x->next;
}
if(accumulation>0){
printf("链表中有%d个%d值\n",accumulation,getNum);
return true;
}else{
printf("链表中没有%d\n",getNum);
return false;
}
}
代码二：
LinkList LocateNodeElem(LinkList L,int findNum){//按值查找
LNode *searchNumP = L->next;//获取第一个结点的位置
int record = 1;
while(searchNumP!=NULL&&searchNumP->data!=findNum){
searchNumP = searchNumP->next;
record++;
}
printf("值%d的位置是%d",searchNumP->data,record);
return searchNumP;
}
6.删除操作
void DelList(LinkList L){//删除操作
int delPos = 0;//定义删除位置变量
printf("\n请输入要删除的位置：");
scanf("%d",&delPos);//获取删除位置
LNode *x,*y;
x = GetNodeElem(L,delPos-1);//查找要删除位置的前驱结点
y = x->next;//要删除的结点
x->next = y->next;//将前驱结点的后继改为删除结点的后继
L->length--;//链表长度-1
free(y);//释放被删除元素的空间
}
三.整体代码
//头插法实现单链表
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
int data;//每个结点存放的数据元素
int length;
struct LNode *next;//指向的下一个结点
}LNode,*LinkList;//均表示一个指向单链表第一个结点的指针
//LNode 强调第一个结点
//LinkList 强调表示的是一个单链表
LinkList AddList(LinkList L){//头插法增添元素
L = (LinkList)malloc(sizeof(LNode));//创建头结点
L->length = 0;
L->next=NULL;
LNode *addPoint;
int addNum;
printf("向链表输入初始值\n");
printf("请输入要插入的内容：");
scanf("%d",&addNum);//获取插入内容
while(addNum != 99){//当输入99时结束循环
addPoint = (LNode *)malloc(sizeof(LNode));
L->length++;
addPoint->next = L->next;
L->next = addPoint;
addPoint->data = addNum;
printf("\n请输入要插入的内容(输入99结束)：");//继续输入新元素
scanf("%d",&addNum);//获取插入内容
}
return L;
}
bool ListInsert(LinkList L){
int inputPosition = 0;//定义记录插入位置并初始化
int inputNum = 0;//定义记录插入数据元素的值并初始化
printf("请输入要插入的位置：");
scanf("%d",&inputPosition);//获取插入位置
printf("请输入要插入的内容：");
scanf("%d",&inputNum);//获取插入内容
if(inputPosition<1){//插入位置不能小于1
return false;
}
LNode *AtPresent;// 定义指向当前遍历到的结点的指针 （遍历指针）
int record = 0;//记录该节点的位置
AtPresent = L;// 让 遍历指针指向头结点
while(AtPresent!=NULL&&record < inputPosition-1){
//遍历条件：1.当前指针不为空 2.当前结点与目标结点位置不匹配
record++;//位置信息累加
AtPresent=AtPresent->next;//遍历指针指向下一个结点
}
if(AtPresent==NULL){//若遍历指针为空，则该链表没有目标位置结点
return false;
}
//找到目标位置后：
LNode *s = (LNode *)malloc(sizeof(LNode));//生成一个新结点
s->data = inputNum;//新结点赋值
s->next = AtPresent->next;//新结点的后继指针指向遍历结点的后继结点
AtPresent->next = s;// 遍历结点的后继指针指向新结点
L->length++;//长度+1
return true;
}
void ShowList(LinkList L){
LNode *x;//定义一个指针
int num = L->length;//num用于暂存该链表长度
printf("该链表一共有%d个元素\n",num);
// x = (LNode *)malloc(sizeof(LNode));
x = L;//将头结点的信息赋给x
x = x->next;//跳过头结点，因为头结点不存储数据
while(num>0){
printf("%d\n",x->data);//输出该节点的数据
x = x->next;//移向下一个结点
num--;//遍历总数减一
}
}
bool GetElem(LinkList L){//按位查找
int getPos = 0;//定义输入位置变量
printf("请输入要查找的位置：");
scanf("%d",&getPos);//获取查找位置
LNode *x;//定义遍历指针
x = L;//将链表头指针位置赋给x
x = x->next;//头结点没有取值，因此跳过
if(getPos<1||getPos>L->length){
//判断输入是否合法
return false;
}
for(int curPos = 1;curPos<getPos;curPos++){
//遍历位置
x=x->next;
}
if(x==NULL){//没有找到
return false;
}
printf("第%d位置元素为%d\n",getPos,x->data);
return true;
}
bool LocateElem(LinkList L){//按值查找
int getNum = 0;
int accumulation = 0;
printf("请输入要查找的值：");
scanf("%d",&getNum);//获取要查询的值
LNode *x;//定义遍历指针
x = L;
x = x->next;
for(int record = 1;record<L->length;record++){//遍历链表
if(x->data == getNum){
printf("第%d个位置存储了%d\n",record,getNum);
accumulation++;
}
x = x->next;
}
if(accumulation>0){
printf("链表中有%d个%d值\n",accumulation,getNum);
return true;
}else{
printf("链表中没有%d\n",getNum);
return false;
}
}
LinkList GetNodeElem(LinkList L,int findPos){
int record = 1;//记录位置
LNode *searchPoint = L->next;//使遍历指针指向第一个结点
if(findPos==0){
return L;//返回头结点
} else if(findPos<1){
return NULL;
}
while(searchPoint&&record<findPos){
searchPoint = searchPoint->next;
record++;
}
return searchPoint;
}
LinkList LocateNodeElem(LinkList L,int findNum){//按值查找
LNode *searchNumP = L->next;//获取第一个结点的位置
int record = 1;
while(searchNumP!=NULL&&searchNumP->data!=findNum){
searchNumP = searchNumP->next;
record++;
}
printf("值%d的位置是%d",searchNumP->data,record);
return searchNumP;
}
void DelList(LinkList L){//删除操作
int delPos = 0;//定义删除位置变量
printf("\n请输入要删除的位置：");
scanf("%d",&delPos);//获取删除位置
LNode *x,*y;
x = GetNodeElem(L,delPos-1);//查找要删除位置的前驱结点
y = x->next;//要删除的结点
x->next = y->next;//将前驱结点的后继改为删除结点的后继
L->length--;//链表长度-1
free(y);//释放被删除元素的空间
}
int main(){
LinkList L;//声明一个指向单链表的指针
// InitList(L);//初始化链表
L = AddList(L);//批量向链表添加数据 并且完成初始化
ShowList(L);//展示链表
ListInsert(L); //按位插入
ShowList(L);//展示链表
//方法一，返回布尔类型
GetElem(L);//按位查找 (方法一)
LocateElem(L);//按值查找（方法一）
//方法二：返回结点
// int findPos=5;
// int findNum=1;
// LNode *searchPoint;
// LNode *searchNumP;
// searchPoint = GetNodeElem(L,findPos);//按位查找
// if(searchPoint!=NULL){
// printf("%d位置上的元素值为%d\n",findPos,searchPoint->data);
// }
// searchNumP = LocateNodeElem(L,findNum); //按值查找
DelList(L);//删除操作
ShowList(L);
} 智能推荐
c# 调用c++ lib静态库_c#调用lib-程序员宅基地
文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加 外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib
deepin/ubuntu安装苹方字体-程序员宅基地
文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang
html表单常见操作汇总_html表单的处理程序有那些-程序员宅基地
文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--action,当提交表单时，向何处发送表单中的数据，地址可以是相对地址也可以是绝对地址--><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些
PHP设置谷歌验证器（Google Authenticator）实现操作二步验证_php otp 验证器-程序员宅基地
文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器
【Python】matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距-程序员宅基地
文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距
docker — 容器存储_docker 保存容器-程序员宅基地
文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户 提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器
随便推点
网络拓扑结构_网络拓扑csdn-程序员宅基地
文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn
JS重写Date函数，兼容IOS系统_date.prototype 将所有 ios-程序员宅基地
文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios
如何将EXCEL表导入plsql数据库中-程序员宅基地
文章浏览阅读5.3k次。方法一：用PLSQL Developer工具。 1 在PLSQL Developer的sql window里输入select * from test for update; 2 按F8执行 3 打开锁, 再按一下加号. 鼠标点到第一列的列头，使全列成选中状态，然后粘贴，最后commit提交即可。（前提..._excel导入pl/sql
Git常用命令速查手册-程序员宅基地
文章浏览阅读83次。Git常用命令速查手册1、初始化仓库git init2、将文件添加到仓库git add 文件名 # 将工作区的某个文件添加到暂存区 git add -u # 添加所有被tracked文件中被修改或删除的文件信息到暂存区，不处理untracked的文件git add -A # 添加所有被tracked文件中被修改或删除的文件信息到暂存区，包括untracked的文件...
分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120-程序员宅基地
文章浏览阅读202次。分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120
【C++缺省函数】 空类默认产生的6个类成员函数_空类默认产生哪些类成员函数-程序员宅基地
文章浏览阅读1.8k次。版权声明：转载请注明出处 http://blog.csdn.net/irean_lau。目录(?)[+]1、缺省构造函数。2、缺省拷贝构造函数。3、 缺省析构函数。4、缺省赋值运算符。5、缺省取址运算符。6、 缺省取址运算符 const。[cpp] view plain copy_空类默认产生哪些类成员函数