数据结构（使用头插法实现单链表）

article/2025/9/30 2:04:23

一.定义

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);}


http://chatgpt.dhexx.cn/article/jXcDVM4d.shtml

相关文章

【Java】JDK 7 HashMap 头插法在并发情况下的成环问题

【Java】JDK 7 HashMap 头插法在并发情况下的成环问题

CONTENT 问题描述成因详解总结Reference 问题描述 JDK 7 的 HashMap 解决冲突用的是拉链法&#xff0c;在拉链的时候用的是头插&#xff0c;每次在链表的头部插入新元素。resize() 的时候用的依然是头插&#xff0c;头插的话&#xff0c;如果某个下标中的链表在新的 table 中依…
阅读更多...
java 如何实现单链表中的头插法

java 如何实现单链表中的头插法

文章目录 头插法1 思路2 插入过程2.1 定义node节点2.2 将node插入到原来head前面的位置2.3 将node节点与下一个结点链接起来2.4 更改head的指向 3 注意点4 为空的情况5 代码实现 头插法 1 思路 先定义一个新的节点&#xff0c;命名为node。将node插入到原来单链表头节点的前面…
阅读更多...
头插法建立链表详解

头插法建立链表详解

头插法就是建立一个头节点&#xff0c;进行初始化定义&#xff0c;next存储下一个节点位置的地址&#xff0c;初始化定义指针域为空&#xff0c;表示该头部节点后面指向任何位置的地址&#xff0c;开始时只有一个头部节点。 head -> next NULL; 图形化表示为 申请一个新节…
阅读更多...
头插法创建单链表

头插法创建单链表

1.对单链表的解释 链表与顺序表不同&#xff0c;它是一种动态管理的存储结构&#xff0c;链表中的每个结点占用的存储空间不是预先分配的&#xff0c;而是运行时系统根据需求生成的&#xff0c;因此建立单列表要从空表开始&#xff0c;每读入一个数据元素则申请一个结点&#…
阅读更多...
头插法逆置单向链表c语言,单链表的逆置（头插法和就地逆置）

头插法逆置单向链表c语言,单链表的逆置（头插法和就地逆置）

今天课间的时候偶然看到了一个面试题&#xff1a;单链表的逆置&#xff0c;看了题解感觉乖乖的&#xff0c;貌似和以前看的版本不搭&#xff0c;于是重新进行了一番探究 单链表的逆置分为两种方法&#xff1a;头插法和就地逆置法&#xff0c;这两种方法虽然都能够达到逆置的效果…
阅读更多...
头插法和尾插法

头插法和尾插法

链表的头插法和尾插法 表结构的声明 typedef int ElemType; typedef struct node //定义链表的结点的结构 {ElemType data;//定义链表的数据域struct node *next;//定义链表中的指针域 }slink;头插法 1&#xff0c;从一个空表开始&#xff0c;重复读入数据&#xff0c;生成新…
阅读更多...
单链表之头插法

单链表之头插法

1、前言&#xff1a; 什么是头插法&#xff1f;说白了头插法就是新增节的点总是插在头节点后面&#xff0c;然后大家可能会有疑惑&#xff0c;什么是新增节点&#xff0c;什么是头节点呢&#xff0c;下面请听俺娓娓道来。。。 2、预前准备&#xff1a; 头节点&#xff1a;一…
阅读更多...
单链表的头插法和尾插法的示例

单链表的头插法和尾插法的示例

单链表是数据结构中最基本的数据结构&#xff0c;单链表有头插法和尾插法&#xff0c;今天有空把这两者做成一个实验示例以作比较。 提示&#xff1a;编译代码是否通过可能与编译器的版本有关&#xff0c;本程序是在 Android 操作系统下的 Compiler C语言编译器下编译通过。 一…
阅读更多...
头插法实现单链表逆置

头插法实现单链表逆置

在头结点的后面依次插入后面的结点&#xff0c;q从第二个结点向后移动遍历&#xff0c;p永远在第一个结点完成头插法逆置单链表。 void reverseL(Linklist &L){//头插法逆转单链表if(L!NULL){LNode* pL->next;//p等于第一个结点LNode* qp->next;//q等于第二个结点p-…
阅读更多...
HashMap/ConcurrentHashMap/头插法/尾插法

HashMap/ConcurrentHashMap/头插法/尾插法

1.1 HashMap JDK1.7 JDK1.8 存储 数组链表 数组链表红黑树 位置算法 h & (length-1) h & (length-1) 链表超过8 链表 红黑对(链表超过8且数组长度超64) 节点结构 Entry<K,V> implements Map.Entry<K,V> Node<K,V> implements Map.Entry…
阅读更多...
C语言 链表 头插法

C语言 链表 头插法

代码&#xff08;VS2017中运行&#xff09; #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct student {int num;float score;struct student *pnext;//*pnext存的是下一个节点的首地址 }stu,*pst…
阅读更多...
头插法建立单链表

头插法建立单链表

头插法建立单链表图示过程&#xff08;其中an表示时间上第n个建立的节点&#xff0c;L为头指针&#xff0c;箭头表指向&#xff0c;sn代表an的地址&#xff09; 结构体代码与主函数如下&#xff1a; struct Link //创建一个结构体类型 {int data; //数据域struct Link* p; /…
阅读更多...
Java实现头插法

Java实现头插法

实现原理&#xff1a; 这是第一个头结点&#xff0c;现在要插入一个节点&#xff0c;也就是让新节点指向该头结点&#xff0c;任何让head指向新节点&#xff0c;新节点变为头结点。 代码实现&#xff1a; 实体类&#xff1a; public class entity {private String data;privat…
阅读更多...
单链表的头插法

单链表的头插法

链表与顺序表不同链表是用一组任意的储存单元来存放线性表的结点&#xff0c;这组结点可以是连续的&#xff0c;也可以是非连续的&#xff0c;甚至可以是零散分布在内存的任何位置&#xff0c;为了能正确的去表达结点的逻辑关系&#xff0c;必须在储存元素值的同时&#xff0c;…
阅读更多...
HashMap在JDK1.7版本头插法实现解析

HashMap在JDK1.7版本头插法实现解析

HashMap在JDK1.7版本头插法实现解析 先解释下何为头插法。大家都知道HashMap在JDK1.7版本的数据结构为数组链表这样的形式。而头插法说的就是在往HashMap里面put元素时&#xff0c;此时新增在链表上元素的位置为链表头部&#xff0c;也就是数组桶位上的那个位置&#xff0c;故…
阅读更多...
头插法链表反转c语言,用头插法反转链表

头插法链表反转c语言,用头插法反转链表

题目&#xff1a;输入一个链表的头结点&#xff0c;反转该链表&#xff0c;并返回反转后链表的头结点。 链表结点定义如下&#xff1a; typedef char item_t; typedef struct node { item_t item; struct node * next; } node_t; 分析&#xff1a; 使用头插法可以快速实现反转。…
阅读更多...
链表头插法

链表头插法

头插法 从一个空表头指针开始&#xff0c;重复读入数据&#xff0c;生成新节点&#xff0c; 将读入数据存放到新节点的数据域中&#xff0c;永远是将新节点插入到当前链表的头节点的后面&#xff0c;第一个创建的节点是放在最后的&#xff0c;直到读入结束标志才停止创建。 #in…
阅读更多...
HashMap头插法

HashMap头插法

HashMap在1.8&#xff08;不含&#xff09;之前对于新增元素的hash冲突的链表插入采用的是头插法&#xff0c;1.8之后开始改用尾插法。那么头插法有什么问题呢&#xff1f;为什么改用尾插法呢&#xff1f;源码学习一下咯 HashMap-jdk1.7.0_80 put新增map元素 public V put(K…
阅读更多...
（最详细）c语言尾插法头插法代码讲解

（最详细）c语言尾插法头插法代码讲解

1.尾插法 尾插法 头指针和尾指针都指向头结点&#xff0c;然后往里边插入元素&#xff0c; 每插入一个元素尾指针就后移一下 其中如下图所示 尾插法的核心代码是&#xff1a; pointer->next s; //pointer指向新生成的节点 pointer pointer->next;//pointer移动至新…
阅读更多...
头插法和尾插法总结（动图版）

头插法和尾插法总结（动图版）

代码使用结构体&#xff1a; typedef struct Node{int value;struct Node* next; }*Link;头插法&#xff1a;利用头指针控制链表节点的增加。 核心&#xff1a; newNode->next head->next; head->next newNode; //头插法创建链表 Link headCreateLink(int n){//头指…
阅读更多...
推荐文章

Copyright @ 2022~2023