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

article/2025/9/30 3:27:54

  单链表是数据结构中最基本的数据结构，单链表有头插法和尾插法，今天有空把这两者做成一个实验示例以作比较。

 

  提示：编译代码是否通过可能与编译器的版本有关，本程序是在 Android 操作系统下的 Compiler C语言编译器下编译通过。

 

  一、头插法和尾插法创建单链表

  增、删、改、查的算法只写了增、查两个，其它省略。

/*程序功能：单链表的头插法和尾插法实验示例说明：本程序的增删改查功能部分实现作者：九天一声啸邮箱：946585434@qq.com日期：2022.09.09
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#include<assert.h>#define BOOL  int
#define TRUE  1
#define OK    1
#define FALSE 0
#define NO    0
#define ERROR -1//链表长度int length = 16;//TRUE 为自然数列，FALSE 为随机数
bool choose = true;
//bool choose = false;//定义结构体
typedef struct Node 
{int data;struct Node *next;}Node, *LinkList;LinkList head = NULL;
LinkList end = NULL; //尾插法时使用的结构体指针//头插法函数
void addHead(int data)
{LinkList L;L = (LinkList)malloc(sizeof(Node));L->data = data;L->next = head->next;head->next = L;}//尾插法函数
void addEnd(int data) {LinkList L;L = (LinkList)malloc(sizeof(Node));L->next = NULL;L->data = data;if(NULL == head){head = L;} else {end->next = L;}end = L;}//头插法遍历链表并输出
void showListHead()
{LinkList tmp;tmp = head->next;while (tmp != NULL){printf ("%d ", tmp->data);tmp = tmp->next;}}//尾插法遍历链表并输出
void showListEnd()
{LinkList tmp;tmp = head;while(tmp){printf("%d ", tmp->data);tmp = tmp->next;}}int main()
{int i;char str[10];BOOL tag;srand(time(0));printf("请输入内容，true 是尾插法；false 是头插法：\n\t->");scanf("%s",&str);/*判断输入内容tag = 1  为true；tag = 0  为falsetag = -1 为error*/if(strcmp(str, "true") == 0)tag = TRUE;else if(strcmp(str, "false") == 0)tag = FALSE;elsetag = ERROR;if(tag == TRUE) {//头插法需要这段代码，否则错误head = (LinkList)malloc(sizeof(Node));head->next = NULL;//头插法插入数据for(i = 0; i < length; i++){if(choose == true)addHead(i);else//随机数addHead(rand()%100 + 1);}printf("头插法：\n");//头插法显示showListHead();} else if(tag == FALSE) {//尾插法插入数据for(i = 0; i < length; i++){if(choose == true)addEnd(i);else//随机数addEnd(rand()%100 + 1);}printf("尾插法：\n");//尾插法显示showListEnd();} else {printf("输入错误！");}return 0;}
wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

 

程序执行后的效果：

3711f63a522247fb9bc6b634387421a5.png

 

 

  二、完整的单链表数据结构如下：

  在实际应用中，结构体中 data 的数据类型应该是另一个结构体数据类型，即 data 代表数据元素，用于定义姓名、姓别、年龄、地址等等数据项。

/*程序功能：单链表的头插法和尾插法实验示例说明：本程序的增删改查功能全部实现作者：九天一声啸邮箱：946585434@qq.com日期：2022.09.09
*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#include<assert.h>//自定义布尔类型
#define BOOL int
#define TRUE  1
#define OK    1
#define FALSE 0
#define ERROR -1BOOL tag;//自定义数据类型 ElemType
#define ElemType int//链表长度
int length = 16;/*true 为自然数列，false 为随机数
*/
//bool choose = true;
bool choose = false;//定义结构体
typedef struct Node{/*data 代表的是数据元素，实际应用中 data 应该是另一个结构体，并且在结构体中定义数据项。*/int data;          //结点数据struct Node *next; //结点指针
}Node, *LinkList;LinkList head = NULL;
LinkList end  = NULL;  //尾插法时使用的结构体指针/*功能：头插法算法函数@param int data 链表数据@return void
*/
void addHead(int data){LinkList L;//头插法核心代码 beginif(NULL == head){//如果没有头节点，创建头节点head = (LinkList)malloc(sizeof(Node));head->next = NULL;}else{L = (LinkList)malloc(sizeof(Node));L->data = data;L->next = head->next;head->next = L;}//头插法核心代码 end.
}/*功能：尾插法算法函数@param int data 链表数据@return void
*/
void addEnd(ElemType data){LinkList L;//尾插法核心代码 beginL = (LinkList)malloc(sizeof(Node));L->data = data;L->next = NULL;if(NULL == head){//如果没有头节点，创建头节点head = (LinkList)malloc(sizeof(Node));head->next = L;}else{end->next = L;}end = L;//尾插法核心代码 end.
}/*功能：返回头结点指针@return LinkList 自定义结构体指针类型
*/
LinkList getLinkNode()
{LinkList L;L = head->next;return L;
}/*功能：根据输入链表的位置查询链表数据@param  int num 待查询链表的位置@return int
*/
int getElem(int num)
{LinkList L;int i;/*由于程序是从 0 开始计数的，见 linkCreate() 函数内容，我们数数时是从 1 开始的，为了让认知一致，i 应该从 1 开始计数。*/i = 1;L = getLinkNode();//循环移动指针到指定位置while(L && i < num){//指针向后移动一位L = L->next;++i;}if(!L || i > num)return ERROR;//查询节点数据的核心代码，直接返回数据即可return L->data;
}/*功能：根据数据位置修改链表@param  int num  待查询链表的位置@param  int data 待修改的数据@return BOOL     自定义的布尔类型
*/
BOOL changeElem(int num, ElemType data)
{LinkList L;int i;i = 1;L = getLinkNode();//循环移动指针到指定位置while(L && i < num){//指针向后移动一位L = L->next;++i;}if(!L || i > num)return ERROR;//修改节点数据的核心代码 beginL->data = data;//修改节点数据的核心代码 endreturn OK;
}/*功能：根据输入链表的位置插入链表节点@param  int num  待插入链表的位置@param  int data 待插入的数据@return BOOL     自定义的布尔类型
*/
BOOL insertList(int num, ElemType data)
{LinkList L, s;int j;j = 1;L = getLinkNode();//循环移动指针到指定位置while(L && j < num){//指针向后移动一个节点L = L->next;++j;}if(!L || j > num)return ERROR;//插入节点和数据的核心代码 begins = (LinkList)malloc(sizeof(Node));s->data = data;s->next = L->next;L->next = s;//插入节点和数据的核心代码 endreturn OK;
}/*功能：根据输入链表的位置删除链表的节点@param int num   要删除链表的位置@return ElemType 自定义类型
*/
ElemType deleteList(int num)
{LinkList L, s;ElemType tmp;int j;/*由于程序是从0开始计数的，见 linkCreate() 函数内容，我们数数时是从1开始的，为了让认知一致，j 应该从 1 开始计数；再由于，要删除的数据是从查询到的位置的下一个位置开始删的，所以这里 j 再加1，即 j = 2。*/j = 2;/*双向链表有前驱指针可以在删除第一个节点时，直接指向头节点。然而，由于单向链表没有前驱指针，在指向头节点后的第一个节点时，在删除第一个节点时删除不了第一个节点，还是删除的是第二个节点，因此这里如果要删除第一个节点的话，要把指针指向头节点。*/if (num == 1)/*删除第一个节点时，指针指向头节点，头节点没有数据内容，即 head->data 为空。*/L = head;else/*删除其它节点时，指针指向头节点后有数据内容的第一个节点，即 head->next->data 是 head 头节点后，第一个节点的数据。注意：head->next 是 head 节点后的第一个节点。*/L = getLinkNode();//循环移动指针到指定位置while(L && j < num){//指针向后移动一个节点L = L->next;j++;}if((!L || j > num) && num != 1)return ERROR;//删除节点的核心代码 begins = L->next ;L->next = s->next ;tmp = s->data;free(s);//删除节点的核心代码 endreturn tmp;
}/*功能：链表的整表删除@return BOOL 自定义布尔类型
*/
BOOL allDeletList()
{LinkList L, s;s = head->next;//整表删除的核心代码 beginwhile(s){L = s->next;free(s);s =L;}//整表删除的核心代码 end//TRUE：头插法；FALSE：尾插法if(tag == TRUE)head->next = NULL;elsehead = NULL;return OK;
}//----------- 以上是单链表的算法实现
//----------- 以下是辅助函数和程序，不必深究。/*功能：头插法遍历链表并输出@return void
*/
void showListHead()
{LinkList tmp;tmp = head->next;while (tmp != NULL){printf ("%d ", tmp->data);tmp = tmp->next;}
}/*功能：尾插法遍历链表并输出@return void
*/
void showListEnd()
{LinkList tmp;bool flag = false ;tmp = head;while(tmp != NULL){if (flag)printf("%d ", tmp->data);else flag = true;tmp = tmp->next;}
}/*功能：遍历单链表并显示@return void
*/
void showList()
{//TRUE：头插法；FALSE：尾插法if(tag == TRUE){//头插法遍历显示showListHead();}else if(tag == FALSE){//尾插法遍历显示showListEnd();}
}/*功能：创建单链表@return BOOL 自定义的布尔类型
*/
BOOL linkCreate()
{int i;char str[10];srand(time(0));printf("1.请输入内容，true 是头插法；false 是尾插法：\n\t-> ");scanf("%s",&str);/*判断输入内容tag = 1    为true；tag = 0    为falsetag = -1   为error*/if(strcmp(str, "true") == 0)tag = TRUE;else if(strcmp(str, "false") == 0)tag = FALSE;elsetag = ERROR;//TRUE：头插法；FALSE：尾插法；ERROR：错误if(tag == TRUE){//头插法插入数据for(i = 0; i < length; ++i){if(choose == TRUE)addHead(i);else//随机数addHead(rand()%100 + 1);}printf("头插法：\n");//头插法遍历显示showListHead();return OK;}else if(tag == FALSE){//尾插法插入数据for(i = 0; i < length; i++){if(choose == TRUE)addEnd(i);else//随机数addEnd(rand()%100 + 1);}printf("尾插法：\n");//尾插法遍历显示showListEnd();return OK;}else{printf("输入错误！");return ERROR;}}/*功能：根据输入链表的位置查询数据@return void
*/
void linkQuery()
{int input;printf("\n\n2.请输入要查询的位置：\n\t-> ");scanf("%d", &input);if(input <= length){int getNum = getElem(input);printf("\n获取到的值：%d", getNum);}else{printf("\n╳ 没有这么长的链表！");}
}/*功能：根据输入链表的位置修改数据@return void
*/
void linkRevise()
{int input, data;printf("\n\n3.请输入要修改的位置和数据，两个数据用空格隔开：\n\t-> ");scanf("%d%d", &input, &data);if(input <= length){changeElem(input, data);printf("\n链表修改后的值：\n");showList();}else{printf("\n╳ 没有这么长的链表！");}
}/*功能：根据输入链表的位置插入数据@return void
*/
void linkInsert()
{int input, data;printf("\n\n4.请输入要插入的位置和数据，两个数据用空格隔开：\n\t-> ");scanf("%d%d", &input, &data);if(input <= length){int ret = insertList(input, data);if(ret == OK)length++;printf("\n链表修改后的值：\n");showList();}else{printf("\n╳ 没有这么长的链表！");}
}/*功能：根据输入链表的位置删除数据@return void
*/
void linkDelete()
{int input, data, tmp;printf("\n\n5.请输入要删除的位置：\n\t-> ");scanf("%d", &input);if(input <= length){tmp = deleteList(input);if(tmp != ERROR)length--;printf("\n->被删除的值：%d\n\n", tmp);printf("\n链表删除后的值：\n");showList();}else{printf("\n╳ 没有这么长的链表！");}
}/*功能：主函数入口@return int
*/
int main()
{//链表操作：创建链表BOOL val = linkCreate();if(val != ERROR){printf("\n--------------------------------\n");//链表查询linkQuery();printf("\n--------------------------------\n");//链表修改linkRevise();printf("\n--------------------------------\n");//链表插入linkInsert();printf("\n--------------------------------\n");//链表删除linkDelete();printf("\n--------------------------------\n");//整表删除allDeletList();printf("\n6.整表删除后的链表数据：");showList();}return 0;
}
wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

 

程序执行后的效果：

ac3100ce8fb443ed82268c203f1684a7.jpg

 

 

三、结构体定义的完整的数据结构演示如下：

  把结构体的数据域写全，并用最原始的方法来演示一下单链表。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>//结构体定义的数据域
typedef struct myData{int  id;char name[20];short int  sex; //0为男；1为女char address[100];
}myData;//结构体定义的节点
typedef struct Node{//数据域，这里用结构体变量，不能直接用指针，//如果没有变量，指针就不能指向变量的地址。struct myData data;//指针域struct Node *next;
}Node, *LinkList;//性别判断
void determine(short int flag, char* e)
{if(flag == 0)strcpy(e, "男");else if(flag == 1)strcpy(e, "女");elsestrcpy(e, "未知");
}//主函数入口
int main()
{char ssex[10] ="未知";//1.结构体变量,静态分配内存Node link1; //赋值link1.data.id = 12;strcpy(link1.data.name, "孙悟空");link1.data.sex = 0;strcpy(link1.data.address, "花果山水帘洞");//性别判断determine(link1.data.sex, ssex);printf("编号：%d\n姓名：%s\n姓别：%s\n地址：%s\n\n", link1.data.id, link1.data.name, ssex, link1.data.address);//2.malloc() 函数动态分配内存LinkList link2 = (LinkList)malloc(sizeof(Node));//赋值link2->data.id = 13;strcpy(link2->data.name, "嫦娥");link2->data.sex = 1;strcpy(link2->data.address, "月亮广寒宫");//性别判断determine(link2->data.sex, ssex);printf("编号：%d\n姓名：%s\n姓别：%s\n地址：%s\n\n", link2->data.id, link2->data.name, ssex, link2->data.address);//3.如果把上面的两个结构体变量组合成一个单向链表/*用这种最原始的方法，才能看清楚它们的关系这里 link1 是结构体变量，而 link2 是 malloc() 直接返回的就是指针，非常方便。*/Node L; //内存分配一个头节点Node* head = &L;//这里等效于：Node* head = (Node*)malloc(sizeof(Node));head->next = &link1;head->next->next = link2;head->next->next->next = NULL; //单链表要求尾节点的 next 为空/*单链表生成完毕，这是最直观的单链表了，上面的五段代码看明白了，单链表的算法已就能写出来了。说明：1.一般要求头节点除了 next 指针域是有效数据，data 数据域是无效数据，不用管它；2.也可以在头节点放置链表长度，这时头节点要单独定义一个结构体，指针域不变，数据域为：int length; 只需把 next 指向其它有数据的节点即可。这样的好处就是在获取单链表的长度时，不用遍历整个链表，也就是时间复杂度由 O(n) 变为了 O(1)，但是，也可以不需要头节点。3.一个 next 其实就是一个有数据内容的节点，而最后的尾节点为 NULL 而已。*/printf("以下内容是从单链表输出的：\n\n");//显示第一个有数据的节点内容determine(head->next->data.sex, ssex);printf("编号：%d\n姓名：%s\n姓别：%s\n地址：%s\n\n", head->next->data.id, head->next->data.name, ssex, head->next->data.address);//显示第二个有数据的节点内容determine(head->next->next->data.sex, ssex);printf("编号：%d\n姓名：%s\n姓别：%s\n地址：%s\n", head->next->next->data.id, head->next->next->data.name, ssex, head->next->next->data.address);return 0;
}
wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==

 

  程序执行后的效果：

3d80c9c3ca07421ca15bd83ec0412c8c.jpg

 

 

 

 


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

相关文章

头插法实现单链表逆置

头插法实现单链表逆置

在头结点的后面依次插入后面的结点&#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){//头指…
阅读更多...
头插法和尾插法建立单链表详解与实现

头插法和尾插法建立单链表详解与实现

写在前面&#xff1a;本文使用C语言和C引用&#xff0c;学C和C的同学都是可以看懂的&#xff0c;C毕竟向下兼容C。很详细&#xff0c;一篇能搞懂代码和原理。 先来了解几个简单概念 单链表就是线性表的链式存储&#xff1b; 头结点&#xff1a;单链表在第一个结点之前附加了一个…
阅读更多...
链表的三种插入方法（头插法，尾插法，任意位置插入）

链表的三种插入方法（头插法，尾插法，任意位置插入）

插入作为链表的四大基本操作之一&#xff08;增删改查&#xff09;&#xff0c;通常都会借助插入的方法增添信息&#xff0c;这一部分为大家着重讲解插入法。 1.头插法 简而言之&#xff0c;就是从链表的头部进行一个插入&#xff0c;定义一个结构体指针的新节点&#xff0c;…
阅读更多...
【数据结构】：单链表之头插法和尾插法（动图+图解）

【数据结构】：单链表之头插法和尾插法（动图+图解）

头插法和尾插法 一、头插法&#x1f4a4;思考一&#xff1a;头插法的核心是什么❓❗❗ 重点一&#xff1a;以带头结点方式实现头插法❗❗ 重点二&#xff1a;以不带头结点方式实现头插法 二、尾插法&#x1f4a4;思考二&#xff1a;尾插法的核心是什么❓❗❗ 重点三&#xff1a…
阅读更多...
链表：头插法与尾插法（简易图解和代码）

链表：头插法与尾插法（简易图解和代码）

头插法 定义&#xff1a;输入的数据次序生成的链表节点次序相反&#xff0c;例如&#xff1a;按1,2,3顺序进行头插之后&#xff0c;最终排序却变成了3,2,1。简而言之就是逆序插入。 定义图解&#xff1a; 代码图解&#xff1a; 代码&#xff1a;&#xff08;使用头插法建立单…
阅读更多...
未声明的标识符

未声明的标识符

出现未声明的标识符错误&#xff0c;有可能是真的没有声明。但是也有可能是代码中有些注释&#xff0c;格式不对&#xff0c;导致声明的变量的作用域提前结束了。可以把注释都删掉试试
阅读更多...
c2065 未声明的标识符 解决ok

c2065 未声明的标识符 解决ok

场景1&#xff1a; cv::Mat pad_img; cv::Mat img; img 在一个if else后面声明&#xff0c;就报错了 解决方法&#xff0c;把cv::Mat 声明放到前面就行了&#xff0c;原因未知。 场景2&#xff1a; int a3; a为未声明的标识符&#xff0c;加了各种头文件&#xff0c;都不起…
阅读更多...
已经包含头文件仍然出现，错误C2065“未声明的标识符”

已经包含头文件仍然出现，错误C2065“未声明的标识符”

由于当前在往一个比较大的项目中添加文件&#xff0c;文件又有相似性所以采取了复制的方式&#xff0c;最后出现了一个大疏漏。 在总的.cpp文件中调用新文件中的函数&#xff0c;在包含了新文件的.h头文件的情况下仍然说没有找到标识符&#xff0c;在网上找了很多方法&#xff…
阅读更多...
c++： “default”: 未声明的标识符

c++： “default”: 未声明的标识符

c&#xff1a; “default”: 未声明的标识符 c&#xff1a; “default”: 未声明的标识符 1、错误描述 2、错误原因&#xff1a; 3、解决方案&#xff1a; 1、错误描述 错误 C2065 “default”: 未声明的标识符 2、错误原因&#xff1a; C11 标准的新特性…
阅读更多...
推荐文章

Copyright @ 2022~2023