目录

前言

本实验的所有代码都经过Dev c++测试，若有错误或表达不当之处，望指出。

一、单链表相关知识点

（一）单链表与顺序表的对比

单链表是链式存储的，其每个结点除了存放数据元素之外，还存储指向下一个结点的指针，链表中不要求结点所占空间连续，但是一个结点内部空间必须连续；而顺序表是顺序存储的，其每个结点只存放数据元素。
【顺序存储结构可以随机存取、顺序存取，而链式存储结构只能顺序存取】
线性表
顺序表
单链表
随机存取和顺序存取
顺序存取

顺序存储结构不仅可用于存储线性结构，还能用于树、图；
顺序表的存储密度=1，而链表的存储密度<1，是由于结点中含有指针域。

  • 若需对表进行频繁的插入、删除操作，此时适合选链式存储，因为顺序表平均需要移动近一半的元素且耗费时间（其插入和删除算法的平均时间复杂度为O(n)），而链表在插入和删除操作时不需要移动元素，只需修改指针；当若表的总数基本稳定，且很少进行插入和删除操作，则顺序表相较于链表可以充分发挥其存取速度块、存储利用率高的优点。

（二）带头结点和不带头结点的单链表

1、带头结点的单链表
单链表无论是否带有头结点，其头指针都指向单链表中第一个结点，在带头结点的单链表中，头结点只作为单链表存在的标志且不存储数据，带头结点的单链表，若L->next==NULL时，则该单链表为空，即头结点的指针域next为空时，此时单链表为空表。
在这里插入图片描述

2、不带头结点的单链表
不带头节点的单链表，若L==NULL时，则该单链表为空。
在这里插入图片描述

（三）访问单链表的结点

在单链表中，访问后继结点的时间复杂度为O(1)，而访问前驱结点的时间复杂度为O(n)。

这里可以将单链表与双链表联合记忆，双链表由于每个结点都包含其前驱结点和后继结点，所以访问它们的时间复杂度都为O(1)。

（四）单链表的插入操作

1、单链表的后插
若要在单链表的第i个位置插入一个结点，首先要找到插入位置的前驱结点，即第i-1个结点，然后再将其插入，这里的主要时间开销是在寻找第i-1个元素的时间上，所以时间复杂度为O(n)。这种插入方法称为后插，查找后插入的步骤可概括为【先连后，再连前】，若在指针*p指向的结点后插一个新结点s，如下代码：

//先将*s与原本*p的指针域指向的结点，再与p相连
s->next=p->next;
p->next=s;

在这里插入图片描述

若要插入的元素位于第一位，则插入操作的最好时间复杂度为O(1)，另外，其最坏、平均时间复杂度为O(n)。

另外，若在给定的结点后面插入新结点，则此时插入的时间复杂度为O(1)。
2、单链表的前插
前插的操作可概括为【先后插，再交换】，这样可以使原本O(n)的时间复杂度转变为O(1)常数数量级，比较上面的后插代码，多了通过中间变量temp来交换数据域data的代码部分，如下：

//前插操作
s->next=p->next;
p->next=s;
temp=p->data;	//交换数据域，通过中间变量temp
p->data=s->data;
s->data=temp;

（五）单链表的删除操作

1、单链表的删除
单链表的删除第i个结点操作与插入操作相同，都是要先找到其前驱结点，即i-1个结点，然后再将其插入或删除，主要时间开销是在寻找第i-1个元素的时间上，删除操作的时间复杂度也为O(n)。查找后删除的步骤可概括为【先定位，后断开释放】，将*q指针指向要删除的结点，p为其前驱结点，如下代码：

q=p->next;	//先定位，定位删除位置
p->next=q->next;	//断开q与p的连接，p与下一个结点连接
free(q);	//通过free()函数进行释放

在这里插入图片描述

若要删除的元素位于第一位，则删除结点操作的最好时间复杂度为O(1)，另外，其最坏、平均时间复杂度为O(n)。

2、单链表的删除的优化
可以通过交换两个指针的数据域，从而使时间复杂度达到O(1)，这对删除操作也是一样，交换两个指针的数据域，即此时后继结点的值赋予自身，通过free()函数删除后继结点，从而使时间复杂度为O(1)。

q=p->next;	//先定位，定位删除位置
p->data=p->next->data;	//与后继结点交换数据域data
p->next=q->next;	//断开q与p的连接，p与下一个结点连接
free(q);	//通过free()函数进行释放

三、顺序表的代码实现

（一）单链表的定义

带头结点和不带头结点的单链表定义，都为下列代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

（二）单链表的初始化和空表判断

1、带头结点的单链表
由于带有头结点，所以要通过malloc()函数分配一个头结点L（注：malloc()函数和free()在头文件#include<stdlib.h>中），如下代码分配一个头结点：

L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点

在一个带头结点的单链表，当L->next==NULL时，表示该单链表为空，带头结点的单链表初始化的完整代码如下：

/*初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

带头结点的单链表判断是否为空的代码如下：

/*判断单链表（带头结点）是否为空*/
bool H_Empty(LinkList L) {
	if(L->next==NULL)	//若单链表的头结点的指针域为空，则表示单链表为空
		return true;
	else
		return false;
}

2、不带头结点的单链表
因为当L==NULL时，则该单链表为空，所以直接将单链表置为空，如下不带头结点的单链表的初始化代码：

//初始化一个不带头结点的空单链表
bool InitList(LinkList &L) {
	L=NULL;		//表示这是一个空表，暂时还没有任何结点
	return true;
}

判断不带头结点的单链表是否为空，return返回L==NULL是否为true或false，如下代码：

//判断单链表（不带头结点）是否为空
bool Empty(LinkList L) {
	return (L==NULL);
}

（三）单链表的输出

1、带头结点的单链表的输出
通过设置一个指针p，使其指向头结点的next域，即指向第一个数据元素，经过while()循环输出每次p指针的数据域（p最终不为空时输出每个结点的数据域），然后依次先后移动p指针，从而输出单链表的所有数据元素。

//单链表（带头结点）的输出
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

2、不带头结点的单链表的输出
由于不带头结点的单链表的头指针L直接指向第一个结点，当L！=NULL，不等于空时，每次输出其数据域，然后每次移动头指针，从而输出单链表的所有数据元素。

/*单链表（不带头结点）的输出*/
void DispList(LinkList L) {
	while(L!=NULL) {
		printf("%d ",L->data);
		L=L->next;
	}
}

（四）单链表的建立

1、带头结点的单链表的建立
有两种方式建立带头结点的单链表，分别是头插法和尾插法，头插法即将新结点插入到当前单链表的表头（头结点之后），由于是头插，所以最后生成的元素顺序与原输入的元素顺序刚好相反，这就是头插法和尾插法的区别。
在这里插入图片描述

  • 头插法中每次通过malloc()函数生成一个新的结点，通过&s->data读取该新结点的数据域，然后将新结点的next域指向头结点的next域，再将其赋值给L->next即放在头结点其后。

如下代码：

//（1）头插法建立单链表（带头结点）
void H_CreateHead(LinkList L,int n) {
	for(int i=0; i<n; i++) {
		int number=i+1; 
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
		scanf("%d",&s->data);			//读入新结点的数据域
		s->next=L->next;		//将新结点的指针域存放在头结点的指针域
		L->next=s;				//将新结点连到头结点之后
	}
}

可以加上以下代码，从而使其逆序，从而使头插法建立的单链表与建立的元素顺序是一样的：

void H_CreateHead(LinkList L,int n) {
	/*LNode *p,*q;*/
	for(int i=0; i<n; i++) {
		int number=i+1; 
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
		scanf("%d",&s->data);			//读入新结点的数据域
		s->next=L->next;		//将新结点的指针域存放在头结点的指针域
		L->next=s;				//将新结点连到头结点之后
	}
	/*将其逆序
	p=L->next;			//从第一个结点开始（而不是头结点）
	L->next=NULL;		//将头结点的指针域置NULL
	while(p!=NULL) {
		q=p;	//使p和q的指针结点位置相同
		p=p->next;	//p指针指向q指针的下一个结点，即q指针存储p指针的指针域
		q->next=L->next; //使q结点指向空，将头结点的指针域存放在q结点的指针域中
		L->next=q;	//将q结点连在头结点后，即q结点赋给头结点的指针域
	}*/
}

例如，通过头插法建立一个单链表并输出单链表，通过头插法建立的单链表刚好与正常输入顺序相反：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、头插法建立单链表（带头结点）*/
void H_CreateHead(LinkList L,int n) {
	for(int i=0; i<n; i++) {
		int number=i+1; 
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
		scanf("%d",&s->data);			//读入新结点的数据域
		s->next=L->next;		//将新结点的指针域存放在头结点的指针域
		L->next=s;				//将新结点连到头结点之后
	}
}

/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateHead(L,n);
	printf("建立的单链表如下：\n");
	H_DispList(L);
}

运行结果如下：
在这里插入图片描述

  1. 尾插法建立单链表，通过添加一个尾指针last，指向单链表的最后一个结点，每次申请一个新结点s，将其读取的数据存放到s的数据域中，然后将s的尾指针指向空，将新结点插入到单链表的尾部，从而完成建立单链表。

如下代码，通过尾插法建立的单链表是正常的输入顺序：

//尾插法建立单链表（带头结点）
void H_CreateTail(LinkList L,int n) {
	LNode *last=L;	//last指针始终指向当前单链表的末尾结点
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); 	//申请一个新结点s
		scanf("%d",&s->data);			//将数据读入至新结点s的数据域中
		s->next=NULL;	//将新结点s的指针域置为空
		last->next=s; 	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;		//然后将last指针指向单链表的末尾结点，即指向新结点的后面
	}
}

例如，通过尾插法建立一个单链表，并输出单链表：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、尾插法建立单链表（带头结点）*/
void H_CreateTail(LinkList L,int n) {
	LNode *last=L;	//last指针始终指向当前单链表的末尾结点
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); 	//申请一个新结点s
		scanf("%d",&s->data);			//将数据读入至新结点s的数据域中
		s->next=NULL;	//将新结点s的指针域置为空
		last->next=s; 	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;		//然后将last指针指向单链表的末尾结点，即指向新结点的后面
	}
}

/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateTail(L,n);
	printf("建立的单链表如下：\n");
	H_DispList(L);
}

运行结果如下：
在这里插入图片描述
2、不带头结点的单链表的建立
不带头结点的单链表的建立也是采用头插法和尾插法，与带头结点差不多，注意这里是LinkList &L，要不然无结果输出，代码如下：

//头插法建立单链表（不带头结点）
void Creatlist(LinkList &L,int n){
	for(int i=0;i<n;i++){
		int x;
		int number=i+1;
		printf("请输入第%d个整数：\n",number);	
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		scanf("%d",&x);	
		s->data=x;	//将输入的数据至赋予新结点s的数据域 
		s->next=L;	//将新结点的指针域存放在头指针 
		L=s;//将头指针指向新结点s，即指向新结点的前面
	}
}

例如，通过头插法建立一个不带头结点的单链表，并输出单链表：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
	L=NULL;		//表示这是一个空表，暂时还没有任何结点
	return true;
}

/*2、头插法建立单链表（不带头结点）*/
void Creatlist(LinkList &L,int n){
	for(int i=0;i<n;i++){
		int x;
		int number=i+1;
		printf("请输入第%d个整数：\n",number);	
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		scanf("%d",&x);	
		s->data=x;	//将输入的数据至赋予新结点s的数据域 
		s->next=L;	//将新结点的指针域存放在头指针 
		L=s;//将头指针指向新结点s，即指向新结点的前面
	}
}

/*3、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
	while(L!=NULL) {
		printf("%d ",L->data);
		L=L->next;
	}
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n;
	InitList(L);
	printf("请输入要建立单链表的长度：\n");
	scanf("%d",&n); 
	Creatlist(L,n);
	printf("建立的单链表如下：\n");
	DispList(L);
}

运行结果如下：
在这里插入图片描述
不带头结点的尾插法中，设置了一个尾指针last，首先对单链表的第一个结点进行特殊处理，使头指针L和尾指针last都指向该结点，然后再从该结点，每次通过尾指针last，将新结点s插入到单链表的表尾，从而使顺序与输入的顺序是一样的，代码如下：

//尾插法建立单链表（不带头结点）
void Creatlist_Tail(LinkList &L,int n) {
	int x;
	bool head_node=true;
	LNode *last=L;
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		if(head_node) {		//对第一个结点特殊处理
			head_node=false;
			s->data=x;
			s->next=NULL;
			L=s;  //将头指针指向新结点s
			last=s;	//将尾指针指向新结点s
		}
		scanf("%d",&x);
		s->data=x;	//将输入的数据至赋予新结点s的数据域
		s->next=NULL;	//将新结点s的指针域置为空
		last->next=s;	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;	//last指针指向尾部
	}
}

例如，通过尾插法创建一个不带头结点的单链表：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
	L=NULL;		//表示这是一个空表，暂时还没有任何结点
	return true;
}

/*2、尾插法建立单链表（不带头结点）*/
void Creatlist_Tail(LinkList &L,int n) {
	int x;
	bool head_node=true;
	LNode *last=L;
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		if(head_node) {		//对第一个结点特殊处理
			head_node=false;
			s->data=x;
			s->next=NULL;
			L=s;  //将头指针指向新结点s
			last=s;	//将尾指针指向新结点s
		}
		scanf("%d",&x);
		s->data=x;	//将输入的数据至赋予新结点s的数据域
		s->next=NULL;	//将新结点s的指针域置为空
		last->next=s;	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;	//last指针指向尾部
	}
}

/*3、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
	while(L!=NULL) {
		printf("%d ",L->data);
		L=L->next;
	}
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n;
	InitList(L);
	printf("请输入要建立单链表的长度：\n");
	scanf("%d",&n); 
	Creatlist_Tail(L,n);
	printf("建立的单链表如下：\n");
	DispList(L);
}

运行结果如下：
在这里插入图片描述

注：不带头结点的尾插法代码参考文章：https://blog.csdn.net/qq_43619271/article/details/120694642

（五）单链表的逆序输出

1、带头结点的单链表
定义两个指针p和q，p为工作指针，q为p的后继为防止断链，其中指针p一开始指向单链表的第一个结点，即从单链表的第一个元素开始，此时并将头结点L的next域置为NULL，然后通过一个while()循环，条件是p指针不为空:

while(p!=NULL)

每次依次将元素结点摘下，q指针用于暂存p的后继，然后依次将p结点插入到头结点后，逆序处理的代码如下，其时间复杂度为O(n)，空间复杂度为O(1)：

//单链表的逆序处理
void ReverseList(LinkList L) {
	LNode *p,*q;	//p为工作指针，q为其后继防止断链 
	p=L->next;		//指向第一个结点 
	L->next=NULL;	//将头结点L的next域置为NULL 
	while(p!=NULL) {
		q=p->next;	//q指针用于暂存p的后继 
		p->next=L->next;	//将p结点插入到头结点后 
		L->next=p;
		p=q;
	}
}

当想对一个单链表进行逆序处理，其实可以直接在创建单链表时，通过头插法建立单链表，从而使得到的结果是逆序的。

例如对一个通过头插法创建单链表的单链表逆序处理后输出，如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、头插法建立单链表（带头结点））*/
void H_CreateHead(LinkList L,int n) {
	for(int i=0; i<n; i++) {
		int number=i+1; 
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
		scanf("%d",&s->data);			//读入新结点的数据域
		s->next=L->next;		//将新结点的指针域存放在头结点的指针域
		L->next=s;				//将新结点连到头结点之后
	}

/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*4、单链表（带头结点）的逆序*/
void ReverseList(LinkList L) {
	LNode *p,*q;	//p为工作指针，q为其后继防止断链 
	p=L->next;		//指向第一个结点 
	L->next=NULL;	//将头结点L的next域置为NULL 
	while(p!=NULL) {
		q=p->next;	//q指针用于暂存p的后继 
		p->next=L->next;	//将p结点插入到头结点后 
		L->next=p;
		p=q;
	}
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateHead(L,n);
	printf("建立的单链表如下：\n");
	H_DispList(L);
	printf("\n");
	printf("逆序后的单链表如下：\n");
	ReverseList(L);
	H_DispList(L);
}

运行结果如下：
在这里插入图片描述
2、不带头结点的单链表
不带头结点的单链表代码如下：

void ReverseList(LinkList &L) {
	LNode *p,*q;	//定义两个指针p、q 
	p=NULL;	//p指针指向NULL 
	q=L;	//q指针指向第一个数据元素 
	while(q!=NULL){
		L=L->next;	//L指向下一个指针域 
		q->next=p;	//p指针指向第二个数据元素 
		p=q;	//p指针指向q 
		q=L;	 //q指针指向头指针L 
	}
	L=p;	//将头指针指向新结点s
}

例如对一个通过尾插法创建不带头结点的单链表，经逆序处理后输出，如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
	L=NULL;		//表示这是一个空表，暂时还没有任何结点
	return true;
}

/*2、判断单链表（不带头结点）是否为空*/
bool Empty(LinkList L) {
	return (L==NULL);
}

/*3、建立单链表（不带头结点）*/
//尾插法建立单链表（不带头结点）
void Creatlist_Tail(LinkList &L,int n) {
	int x;
	bool head_node=true;
	LNode *last=L;
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		if(head_node) {		//对第一个结点特殊处理
			head_node=false;
			s->data=x;
			s->next=NULL;
			L=s;  //将头指针指向新结点s
			last=s;	//将尾指针指向新结点s
		}
		scanf("%d",&x);
		s->data=x;	//将输入的数据至赋予新结点s的数据域
		s->next=NULL;	//将新结点s的指针域置为空
		last->next=s;	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;	//last指针指向尾部
	}
}

/*4、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
	while(L!=NULL) {
		printf("%d ",L->data);
		L=L->next;
	}
}

/*5、单链表（不带头结点）的逆序输出*/
void ReverseList(LinkList &L) {
	LNode *p,*q;	//定义两个指针p、q 
	p=NULL;	//p指针指向NULL 
	q=L;	//q指针指向第一个数据元素 
	while(q!=NULL){
		L=L->next;	//L指向下一个指针域 
		q->next=p;	//p指针指向第二个数据元素 
		p=q;	//p指针指向q 
		q=L;	 //q指针指向头指针L 
	}
	L=p;	//将头指针指向新结点s
}

//主函数
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n,i,e;
	InitList(L);
	printf("请输入要建立单链表的长度：\n");
	scanf("%d",&n);
	Creatlist_Tail(L,n);
	printf("建立的单链表如下：\n");
	DispList(L);
	printf("\n");
	printf("逆序输出单链表：\n");
	ReverseList(L); 
	DispList(L);
}

运行结果如下：
在这里插入图片描述

（六）单链表的插入操作

1、带头结点的单链表
将要插入的结点插到单链表的第i个位置上，也就是要找到其前驱结点，即i-1结点的位置，然后在其后插入新的结点。
代码如下【时间复杂度为O(n)】：

/*按位序插入元素至单链表中（找到i-1个结点【p】，然后将新结点【s】插入其后）*/
bool H_ListInsert(LinkList &L,int i,int e) {
	if(i<1)
		return false;
	LNode *p=L;//指针p为当前扫描的结点，且L指向头结点（第0个结点，不存储结点） 
	int j=0;	//j的值代表p指向的是第几个结点
	while(p!=NULL&&j<i-1) {
		p=p->next;		//循环找到i-1个结点，且该结点为不为空
		j++;
	}
	if(p==NULL)	//i值不合法
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));	//申请一个新结点s
	s->data=e;		//将要插入的结点的值赋给该新结点的数据域
	s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
	p->next=s;		//s结点指到p结点的指针域，即将s连到p之后
	return true;
}

另一种后插操作如下，参数为将指针s插入到指针p的后面【这种方法的时间复杂度为O(1)】：

/*后插法直接插入新结点*/
bool InserprioNode(LNode *p,LNode *s) {
	if(p==NULL||s==NULL)
		return false;
	s->next=p->next;		//修改指针域
	p->next=s;
	int temp=p->data;		//交换数据域
	p->data=s->data;
	s->data=temp;
	return true;
}

例如创建一个带头结点的单链表，在单链表的第2个位置插入元素“0”，最后输出插入后的单链表，通过第一种方法实现如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、尾插法建立单链表（带头结点）*/
void H_CreateTail(LinkList L,int n) {
	LNode *last;
	int i;
	last=L;		//last指针始终指向当前单链表的末尾结点
	for(i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); 	//申请一个新结点s
		scanf("%d",&s->data);			//将数据读入至新结点s的数据域中
		s->next=NULL;	//将新结点s的指针域置为空，即空指针NULL
		last->next=s; 	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;		//然后将last指针指向单链表的末尾结点，即指向新结点的后面
	}
}

/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*4、按位序插入元素至单链表中（找到i-1个结点【p】，然后将新结点【s】插入其后）*/
bool H_ListInsert(LinkList &L,int i,int e) {
	if(i<1)
		return false;
	LNode *p;	//指针p为当前扫描的结点，且L指向头结点（第0个结点，不存储结点） 
	int j=0;	//j的值代表p指向的是第几个结点
	while(p!=NULL&&j<i-1) {
		p=p->next;		//循环找到i-1个结点，且该结点为不为空
		j++;
	}
	if(p==NULL)	//i值不合法
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));	//申请一个新结点s
	s->data=e;		//将要插入的结点的值赋给该新结点的数据域
	s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
	p->next=s;		//s结点指到p结点的指针域，即将s连到p之后
	return true;
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateTail(L,n);
	printf("建立的单链表如下：\n");
	H_DispList(L);
	H_ListInsert(L,2,0);
	printf("\n");
	printf("插入后的单链表如下：\n");
	H_DispList(L);
}

运行结果如下：
在这里插入图片描述
2、不带头结点的单链表

不带头结点的单链表的插入和删除操作中，由于不含有头结点，若对表头元素进行操作，则需要另外的附加代码，修改头指针L。

若要将元素插入至单链表中第i个位置，首先要找到其前驱结点，即i-1结点的位置，然后在其后插入新的结点。但由于是不带头结点的单链表，所以就有两种情况，也就是插入至表头或其他位置，对于第1个位置需特别处理，即此时要修改头指针L。

//按位序插入元素至（不带头结点）的单链表
bool ListInsert(LinkList &L,int i,int e) {
	if(i<1)		//若插入位序小于1，则报错 
		return false;
	if(i==1) {		//插入至单链表的表头，插入第1个结点的操作如下 
		LNode *s=(LNode *)malloc(sizeof(LNode));	//创建一个新结点s 
		s->data=e;	//将e的值赋给新结点s的数据域中 
		s->next=L;	//将新结点s的next域指向原本头指针L指向的结点，从而连接起来 
		L=s;		//修改头指针L，头指针L指向新结点s
		return true;
	}
	LNode *p=L;	//指针p为当前扫描到的结点，p指向第一个结点
	int j=1;	//j表示当前指针p扫描的是第几个结点
	while(p!=NULL&&j<i-1) {
		p=p->next;		//循环找到i-1个结点，且该结点为不为空
		j++;
	}
	if(p==NULL)	//i值不合法
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));	//申请一个新结点s
	s->data=e;		//将要插入的结点的值赋给该新结点的数据域
	s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
	p->next=s;		//s结点指到p结点的指针域，即将s连到p之后
	return true;
}

例如创建一个不带头结点的单链表，在单链表的第3个位置插入元素“9”，最后输出插入后的单链表，实现如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
	L=NULL;		//表示这是一个空表，暂时还没有任何结点
	return true;
}

/*2、判断单链表（不带头结点）是否为空*/
bool Empty(LinkList L) {
	return (L==NULL);
}

/*3、建立单链表（不带头结点）*/
//（2）尾插法建立单链表（不带头结点）
void Creatlist_Tail(LinkList &L,int n) {
	int x;
	bool head_node=true;
	LNode *last=L;
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		if(head_node) {		//对第一个结点特殊处理
			head_node=false;
			s->data=x;
			s->next=NULL;
			L=s;  //将头指针指向新结点s
			last=s;	//将尾指针指向新结点s
		}
		scanf("%d",&x);
		s->data=x;	//将输入的数据至赋予新结点s的数据域
		s->next=NULL;	//将新结点s的指针域置为空
		last->next=s;	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;	//last指针指向尾部
	}
}

/*4、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
	while(L!=NULL) {
		printf("%d ",L->data);
		L=L->next;
	}
}

/*5、单链表（不带头结点）的插入操作*/
//按位序插入元素至（不带头结点）的单链表
bool ListInsert(LinkList &L,int i,int e) {
	if(i<1)		//若插入位序小于1，则报错 
		return false;
	if(i==1) {		//插入至单链表的表头，插入第1个结点的操作如下 
		LNode *s=(LNode *)malloc(sizeof(LNode));	//创建一个新结点s 
		s->data=e;	//将e的值赋给新结点s的数据域中 
		s->next=L;	//将新结点s的next域指向原本头指针L指向的结点，从而连接起来 
		L=s;		//修改头指针L，头指针L指向新结点s
		return true;
	}
	LNode *p=L;	//指针p为当前扫描到的结点，p指向第一个结点
	int j=1;	//j表示当前指针p扫描的是第几个结点
	while(p!=NULL&&j<i-1) {
		p=p->next;		//循环找到i-1个结点，且该结点为不为空
		j++;
	}
	if(p==NULL)	//i值不合法
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));	//申请一个新结点s
	s->data=e;		//将要插入的结点的值赋给该新结点的数据域
	s->next=p->next; //将p结点的指针域存放在s结点的指针域，即将s的指针域与p结点后面元素相连
	p->next=s;		//s结点指到p结点的指针域，即将s连到p之后
	return true;
}

//主函数
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n,i,e;
	InitList(L);
	printf("请输入要建立单链表的长度：\n");
	scanf("%d",&n);
	Creatlist_Tail(L,n);
	printf("建立的单链表如下：\n");
	DispList(L);
	printf("\n");
	printf("请输入要插入的元素位置和元素数据：\n");
	scanf("%d %d",&i,&e);
	printf("插入后的单链表如下：\n");
	ListInsert(L,i,e);
	DispList(L);
}

运行结果如下：
在这里插入图片描述
以下是带头结点的单链表插入操作和不带头结点的单链表的代码比较，其中查找前驱结点和将新结点插入等操作代码是相同的，但不带头结点的单链表的代码较麻烦，所以一般不带头结点的使用的较少，如下图：
在这里插入图片描述

（七）单链表的删除操作

1、带头结点的单链表
删除操作，也就是将单链表的第i个结点删除，这里也就是要找到其前驱结点，即i-1结点的位置（要删除的结点的前驱结点），将其指针指向第i+1个结点，并释放第i个结点。（通过free()函数实现，注意要加#include<stdlib.h>头文件）
代码如下：

/*单链表（带头结点）删除元素*/
bool ListDelete(LinkList &L,int i/*,int &e*/) {
	if(i<1)
		return false;
	int j=0;			//j的值代表p指向的是第几个结点
	LNode *p=L;			//指针p为当前扫描的结点,L指向头结点（第0个结点，不存储结点）
	while(p!=NULL&&j<i-1) {
		p=p->next;		//循环找到i-1个结点，且该结点为不为空
		j++;
	}
	if(p==NULL || p->next==NULL)
		return false;
	LNode *q=p->next;		//令q指向被删除的结点
	//e=q->data;			//用e返回元素的值
	p->next=q->next;		//将*q结点从链表中断开
	free(q);
	return true;
}

例如，创建一个带头结点的单链表，删除带头结点的单链表第3位元素，如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、尾插法建立单链表（带头结点）*/
void H_CreateTail(LinkList L,int n) {
	LNode *last;
	int i;
	last=L;		//last指针始终指向当前单链表的末尾结点
	for(i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); 	//申请一个新结点s
		scanf("%d",&s->data);			//将数据读入至新结点s的数据域中
		s->next=NULL;	//将新结点s的指针域置为空，即空指针NULL
		last->next=s; 	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;		//然后将last指针指向单链表的末尾结点，即指向新结点的后面
	}
}

/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*4、单链表（带头结点）删除元素*/
bool ListDelete(LinkList &L,int i/*,int &e*/) {
	if(i<1)
		return false;
	int j=0;			//j的值代表p指向的是第几个结点
	LNode *p=L;			//指针p为当前扫描的结点,L指向头结点（第0个结点，不存储结点）
	while(p!=NULL&&j<i-1) {
		p=p->next;		//循环找到i-1个结点，且该结点为不为空
		j++;
	}
	if(p==NULL || p->next==NULL)
		return false;
	LNode *q=p->next;		//令q指向被删除的结点
	//e=q->data;			//用e返回元素的值
	p->next=q->next;		//将*q结点从链表中断开
	free(q);
	return true;
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n,i;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateTail(L,n);
	printf("建立的单链表如下：\n");
	H_DispList(L);
	printf("\n");
	printf("请输入要建删除的元素位序：\n");
	scanf("%d",&i);
	ListDelete(L,i);
	printf("删除后的单链表如下：\n");
	H_DispList(L);
}

运行结果如下：
在这里插入图片描述
另一种删除方法是删除该结点的后继结点从而实现删除一个结点，首先将其后继结点的值赋给自身，然后再删除后继结点，这样可以使时间复杂度达到O(1)，代码如下：

bool DeleteNode(LNode *p) {
	if(p==NULL)
		return false;
	LNode *q=p->next;	//q指向*p的后继结点
	p->data=p->next->data;  //交换数据域
	p->next=q->next;	//将*q结点从链表中断开
	free(q);
	return true;
}

2、不带头结点的单链表
不带头结点的单链表的删除操作，与带头结点的部分代码相似，不过也是要对表头元素操作时需特殊处理，即当i==1时进行处理。
在这里插入图片描述
在这里插入图片描述
代码如下：

/*按位序删除元素*/
bool ListDelete(LinkList &L,int i/*,int &e*/) {
	if(i<1)	//位序小于1，则报错 
		return false;
	LNode *p,*q;
	p=L;			//指针p为当前扫描的结点,L指向第一个结点 
	int j=1;			//j的值代表p指向的是第几个结点
	if(i==1){	//对删除第一个结点的特殊情况 
		q=L->next;
		free(p);
		L=q;
		return true;
	}	
	while(p!=NULL&&j<i-1) {
		p=p->next;		//循环找到i-1个结点，且该结点为不为空
		j++;
	}
	if(p==NULL || p->next==NULL)
		return false;
	q=p->next;		//令q指向被删除的结点
	//e=q->data;			//用e返回元素的值
	p->next=q->next;		//将*q结点从链表中断开
	free(q);
	return true;
}

例如，创建一个不带头结点的单链表，删除单链表第3位元素，如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
	L=NULL;		//表示这是一个空表，暂时还没有任何结点
	return true;
}

/*2、判断单链表（不带头结点）是否为空*/
bool Empty(LinkList L) {
	return (L==NULL);
}

/*3、建立单链表（不带头结点）*/
//尾插法建立单链表（不带头结点）
void Creatlist_Tail(LinkList &L,int n) {
	int x;
	bool head_node=true;
	LNode *last=L;
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		if(head_node) {		//对第一个结点特殊处理
			head_node=false;
			s->data=x;
			s->next=NULL;
			L=s;  //将头指针指向新结点s
			last=s;	//将尾指针指向新结点s
		}
		scanf("%d",&x);
		s->data=x;	//将输入的数据至赋予新结点s的数据域
		s->next=NULL;	//将新结点s的指针域置为空
		last->next=s;	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;	//last指针指向尾部
	}
}

/*4、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
	while(L!=NULL) {
		printf("%d ",L->data);
		L=L->next;
	}
}

/*5、按位序删除元素*/
bool ListDelete(LinkList &L,int i/*,int &e*/) {
	if(i<1)	//位序小于1，则报错 
		return false;
	LNode *p,*q;
	p=L;			//指针p为当前扫描的结点,L指向第一个结点 
	int j=1;			//j的值代表p指向的是第几个结点
	if(i==1){	//对删除第一个结点的特殊情况 
		q=L->next;
		free(p);
		L=q;
		return true;
	}	
	while(p!=NULL&&j<i-1) {
		p=p->next;		//循环找到i-1个结点，且该结点为不为空
		j++;
	}
	if(p==NULL || p->next==NULL)
		return false;
	q=p->next;		//令q指向被删除的结点
	//e=q->data;			//用e返回元素的值
	p->next=q->next;		//将*q结点从链表中断开
	free(q);
	return true;
}

//主函数
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n,i;
	InitList(L);
	printf("请输入要建立单链表的长度：\n");
	scanf("%d",&n);
	Creatlist_Tail(L,n);
	printf("建立的单链表如下：\n");
	DispList(L);
	printf("\n");
	printf("请输入要删除的元素位序：\n");
	scanf("%d",&i);
	ListDelete(L,i);
	printf("删除后的单链表如下：\n");
	DispList(L);
}

运行结果如下：
在这里插入图片描述
##（八）单链表的查找操作
单链表的查找操作分为按值查找和按位查找（注：位序是从1开始）：
查找操作
按值查找
位序查找

1、带头结点的单链表

  • 按值查找的操作通过比较data数据域，即从单链表的第一个结点开始（不是头结点，而是p=L->next），依次比较各个结点的data数据域，若某结点的data数据域等于查找值，再通过一个if语句判断该指针是否为空，若为空则表示单链表中有该结点并输出该结点的位序和值，然后返回true；否则返回false。

按值查找的代码如下：

/*按值查找（比较data数据域）*/
bool Locatexdata(LinkList L,int x) {
	int i=1;
	LNode *p=L->next;
	while(p!=NULL&&p->data!=x) {
		p=p->next;
		i++;
	}
	if(p!=NULL) {
		printf("已找到表中第%d位且值为%d的结点",i,x);
		return true;
	} else
		return false;
}

例如创建一个单链表，然后查找值为0的元素，如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、尾插法建立单链表（带头结点）*/
void H_CreateTail(LinkList L,int n) {
	LNode *last;
	int i;
	last=L;		//last指针始终指向当前单链表的末尾结点
	for(i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); 	//申请一个新结点s
		scanf("%d",&s->data);			//将数据读入至新结点s的数据域中
		s->next=NULL;	//将新结点s的指针域置为空，即空指针NULL
		last->next=s; 	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;		//然后将last指针指向单链表的末尾结点，即指向新结点的后面
	}
}

/*3、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*4、按值查找（比较data数据域）*/
bool Locatexdata(LinkList L,int x) {
	int i=1;
	LNode *p=L->next;
	while(p!=NULL&&p->data!=x) {
		p=p->next;
		i++;
	}
	if(p!=NULL) {
		printf("已找到表中第%d位且值为%d的结点",i,x);
		return true;
	} else
		return false;
}

/*5、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n,x,a;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateTail(L,n);
	printf("建立的单链表如下：\n");
	H_DispList(L);
	printf("\n");
	printf("请输入要查找的值！\n");
	scanf("%d",&x);
	a=Locatexdata(L,x);
	printf("\n");
	printf("返回值为：%d",a);
}

运行结果如下：
在这里插入图片描述

  • 按位查找的操作是从头结点开始，通过next指针域依次搜索链表，直到找到第i个结点（要搜索的结点的位序）为止，若找到则输出第i个结点的值和位序并返回true；若没有找到则返回false。

按位查找的代码如下：

/*带头结点的单链表按位查找*/
bool Searchlocate(LinkList L,int i){
	if(i==0 || i<1)
		return false;
	int j=1;
	LNode *p=L->next;
	while(p!=NULL&&j<i){
		p=p->next;
		j++;
	}
	printf("已找到表中第%d位且值为%d的结点",j,p->data);
	return true;
}

例如创建一个单链表，查找单链表中位序为3的元素（第三个元素），如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、尾插法建立单链表（带头结点）*/
void H_CreateTail(LinkList L,int n) {
	LNode *last;
	int i;
	last=L;		//last指针始终指向当前单链表的末尾结点
	for(i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); 	//申请一个新结点s
		scanf("%d",&s->data);			//将数据读入至新结点s的数据域中
		s->next=NULL;	//将新结点s的指针域置为空，即空指针NULL
		last->next=s; 	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;		//然后将last指针指向单链表的末尾结点，即指向新结点的后面
	}
}

/*4、按位查找*/
bool Searchlocate(LinkList L,int i){
	if(i==0 || i<1)
		return false;
	int j=1;
	LNode *p=L->next;
	while(p!=NULL&&j<i){
		p=p->next;
		j++;
	}
	printf("已找到表中第%d位且值为%d的结点",j,p->data);
	return true;
}

/*5、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n,i,a;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateTail(L,n);
	printf("建立的单链表如下：\n");
	H_DispList(L);
	printf("\n");
	printf("请输入要查找的位序！\n");
	scanf("%d",&i);
	a=Searchlocate(L,i);
	printf("\n");
	printf("返回值为：%d",a);
}

运行结果如下：
在这里插入图片描述
2、不带头结点的单链表
按值查找的代码如下：

/*不带头结点的单链表按值查找*/
bool Locatexdata(LinkList L,int x) {
	int i=1;
	LNode *p=L;
	while(p!=NULL&&p->data!=x) {	//依次查找
		p=p->next;
		i++;
	}
	if(p!=NULL) {
		printf("已找到表中第%d位，值为%d的结点",i,x);
		return true;
	} else
		return false;
}

按位查找的代码如下：

/*不带头结点的单链表按位找*/
bool Searchlocate(LinkList L,int i){
	if(i==0 || i<1)
		return false;
	int j=1;
	LNode *p=L;
	while(p!=NULL&&j<i){
		p=p->next;
		j++;
	}
	printf("已找到表中第%d位且值为%d的结点",j,p->data);
	return true;
}

（九）单链表的求表长操作

1、带头结点的单链表
求表长需定义一个变量来记录链表长度，另外定义一个指针p指向链表的头结点，然后可以通过一个while循环，其循环条件是当p->next!=NULL，即指向第一个数据元素p->next开始，直到指向NULL时结束循环，每次p指针移动至下一个数据元素，然后变量递加，最后返回链表长度，如下代码：

/*带头结点的单链表求表长*/
int LengthList(LinkList L) {
	int length=0;	//定义变量length记录链表长度 
	LNode *p=L;	//指针p从头结点开始，指向头结点 
	while(p->next!=NULL) {
		p=p->next;	//循环中p指针每次移动 
		length++;
	}
	return length;
}

例如，输出一个单链表的表长：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、判断单链表（带头结点）是否为空*/
bool H_Empty(LinkList L) {
	if(L->next==NULL)	//若单链表的头结点的指针域为空，则表示单链表为空
		return true;
	else
		return false;
}
/*3、建立单链表（带头结点）*/
//（1）头插法建立单链表（带头结点）并逆置单链表
void H_CreateHead(LinkList L,int n) {
	/*LNode *p,*q;*/
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); //生成新结点s
		scanf("%d",&s->data);			//读入新结点的数据域
		s->next=L->next;		//将新结点的指针域存放在头结点的指针域
		L->next=s;				//将新结点连到头结点之后
	}
	//将其逆序排列
	/*p=L->next;			//从第一个结点开始（而不是头结点）
	L->next=NULL;		//将头结点的指针域置NULL
	while(p!=NULL) {
		q=p;	//使p和q的指针结点位置相同
		p=p->next;	//p指针指向q指针的下一个结点，即q指针存储p指针的指针域
		q->next=L->next; //使q结点指向空，将头结点的指针域存放在q结点的指针域中
		L->next=q;	//将q结点连在头结点后，即q结点赋给头结点的指针域
	}*/
}

//（2）尾插法建立单链表（带头结点）
void H_CreateTail(LinkList L,int n) {
	LNode *last=L;
	//last=L;		//last指针始终指向当前单链表的末尾结点
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); 	//申请一个新结点s
		scanf("%d",&s->data);			//将数据读入至新结点s的数据域中
		s->next=NULL;	//将新结点s的指针域置为空，即空指针NULL
		last->next=s; 	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;		//然后将last指针指向单链表的末尾结点，即指向新结点的后面
	}
}

/*4、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*5、带头结点的单链表求表长*/
int LengthList(LinkList L) {
	int length=0;	//定义变量length记录链表长度 
	LNode *p=L;	//指针p从头结点开始，指向头结点 
	while(p->next!=NULL) {
		p=p->next;	//循环中p指针每次移动遍历单链表 
		length++;
	}
	return length;
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateTail(L,n);
	printf("建立的单链表如下：\n");
	H_DispList(L);
	printf("\n");
	printf("单链表的长度为：%d\n",LengthList(L));
}

运行结果如下：
在这里插入图片描述
2、不带头结点的单链表
不带头结点的单链表求表长操作，在带头结点的单链表的代码上，将while循环条件改为p!=NULL即可，其他不变，也是定义一个变量来记录链表长度，另外定义一个指针p指向链表的头结点，每次p指针移动至下一个数据元素，然后变量递加，最后返回链表长度，如下代码：

/*单链表（不带头结点）的求表长*/
int LengthList(LinkList L) {
	int length=0;	//定义变量length记录链表长度 
	LNode *p=L;	//指针p从头结点开始，指向头结点 
	while(p!=NULL) {
		p=p->next;	//循环中p指针每次移动遍历单链表 
		length++;
	}
	return length;
}

例如，输出一个单链表的表长：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个不带头结点的空单链表*/
bool InitList(LinkList &L) {
	L=NULL;		//表示这是一个空表，暂时还没有任何结点
	return true;
}

/*2、判断单链表（不带头结点）是否为空*/
bool Empty(LinkList L) {
	return (L==NULL);
}

/*3、建立单链表（不带头结点）*/
//（1）头插法建立单链表（不带头结点）【顺序相反】
void Creatlist(LinkList L,int n) {
	for(int i=0; i<n; i++) {
		int x;
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		scanf("%d",&x);
		s->data=x;	//将输入的数据至赋予新结点s的数据域
		s->next=L;	//将新结点的指针域存放在头指针
		L=s;//将头指针指向新结点s，即指向新结点的后面
	}
}

//（2）尾插法建立单链表（不带头结点）
void Creatlist_Tail(LinkList &L,int n) {
	int x;
	bool head_node=true;
	LNode *last=L;
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode));	//生成新结点s
		if(head_node) {		//对第一个结点特殊处理
			head_node=false;
			s->data=x;
			s->next=NULL;
			L=s;  //将头指针指向新结点s
			last=s;	//将尾指针指向新结点s
		}
		scanf("%d",&x);
		s->data=x;	//将输入的数据至赋予新结点s的数据域
		s->next=NULL;	//将新结点s的指针域置为空
		last->next=s;	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;	//last指针指向尾部
	}
}

/*4、单链表（不带头结点）的输出*/
void DispList(LinkList L) {
	while(L!=NULL) {
		printf("%d ",L->data);
		L=L->next;
	}
}

/*5、单链表（不带头结点）的求表长*/
int LengthList(LinkList L) {
	int length=0;	//定义变量length记录链表长度 
	LNode *p=L;	//指针p从头结点开始，指向头结点 
	while(p!=NULL) {
		p=p->next;	//循环中p指针每次移动遍历单链表 
		length++;
	}
	return length;
}

//主函数
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n,i,e;
	InitList(L);
	printf("请输入要建立单链表的长度：\n");
	scanf("%d",&n);
	Creatlist_Tail(L,n);
	printf("建立的单链表如下：\n");
	DispList(L);
	printf("\n");
	printf("单链表的长度为：%d\n",LengthList(L));
}

运行结果如下：
在这里插入图片描述

（十） *单链表的排序

这里采用排序算法是直接排序算法，使带头结点的单链表递增有序，并输出。

//使单链表递增排列有序
void SortList(LinkList L) {
	LNode *p=L->next,*pre;
	LNode *r=p->next;	//r指针用于保持p后继结点指针，保证不断链
	p->next=NULL;	//断链，构造只含有一个数据结点的有序表
	p=r;	//将r指针改为p指针 
	while(p!=NULL) {
		r=p->next;	//保存p的后继结点指针，r指针始终指向p指针的next域 
		pre=L;	//pre指针从头开始 
		while(pre->next!=NULL&&pre->next->data<p->data)
			pre=pre->next;	//在有序表中查找插入p的前驱结点pre 
		p->next=pre->next;	//将p插入到pre之后 
		pre->next=p;
		p=r;	//扫描原单链表中剩下的结点 
	}
}

例如，创建一个带头结点的单链表，然后通过排序算法输出排序后的单链表：

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {
	int data;
	struct LNode *next;
} LNode,*LinkList;

/*1、初始化一个带头结点的空单链表*/
bool H_InitList(LinkList &L) {
	L=(LNode *)malloc(sizeof(LNode));		//分配一个头结点
	if(L==NULL)		//内存不足，分配失败
		return false;
	L->next=NULL;	//头结点之后暂时还没有任何结点，表示空链表
	return true;
}

/*2、判断单链表（带头结点）是否为空*/
bool H_Empty(LinkList L) {
	if(L->next==NULL)	//若单链表的头结点的指针域为空，则表示单链表为空
		return true;
	else
		return false;
}

//3、尾插法建立单链表（带头结点）
void H_CreateTail(LinkList L,int n) {
	LNode *last=L;
	//last=L;		//last指针始终指向当前单链表的末尾结点
	for(int i=0; i<n; i++) {
		int number=i+1;
		printf("请输入第%d个整数：\n",number);
		LNode *s=(LNode *)malloc(sizeof(LNode)); 	//申请一个新结点s
		scanf("%d",&s->data);			//将数据读入至新结点s的数据域中
		s->next=NULL;	//将新结点s的指针域置为空，即空指针NULL
		last->next=s; 	//将新结点s插入至单链表的表尾，即last的指针域（末尾结点的后面）
		last=s;		//然后将last指针指向单链表的末尾结点，即指向新结点的后面
	}
}

/*4、单链表（带头结点）的输出*/
void H_DispList(LinkList L) {
	LNode *p;
	p=L->next;
	while(p!=NULL) {
		printf("%d ",p->data);
		p=p->next;
	}
}

/*5、排序：使单链表递增排有序*/
void SortList(LinkList L) {
	LNode *p=L->next,*pre;
	LNode *r=p->next;	//r指针用于保持p后继结点指针，保证不断链
	p->next=NULL;	//断链，构造只含有一个数据结点的有序表
	p=r;	//将r指针改为p指针 
	while(p!=NULL) {
		r=p->next;	//保存p的后继结点指针，r指针始终指向p指针的next域 
		pre=L;	//pre指针从头开始 
		while(pre->next!=NULL&&pre->next->data<p->data)
			pre=pre->next;	//在有序表中查找插入p的前驱结点pre 
		p->next=pre->next;	//将p插入到pre之后 
		pre->next=p;
		p=r;	//扫描原单链表中剩下的结点 
	}
}

/*主函数*/
int main() {
	LinkList L;		//声明一个指向单链表的指针
	int n;
	H_InitList(L);	//初始化一个空的单链表
	printf("请输入要建立单链表的长度：");
	scanf("%d",&n);
	H_CreateTail(L,n);//创建单链表 
	printf("建立的单链表如下：\n");
	H_DispList(L);//输出单链表 
	printf("\n");
	SortList(L);//排序 
	printf("排序后的单链表如下：\n"); 
	H_DispList(L);
}

运行结果如下：
在这里插入图片描述
若需将排序的结果是递减排序的，将“<”改为“>”，即

while(pre->next!=NULL&&pre->next->data<p->data)
# 数据结构 # 链表
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊