-
C语言实现单链表
一、什么是单链表
1.链表就是一种在物理存储上各个节点非连续的，随机的，元素的逻辑顺序是通过链表中的指针链接的次序而实现的。
图示：
二、单链表中节点的定义
#include
#include
#include
typedef struct node{
int data;//数据域
struct node * next//指向下一个节点的指针
}Lnode,*LinkList;//Lnode 表示链表中的一个节点，二*LinkList表示整个链表，也可以表示单链表的头指针。
三、单链表的实现方式
1.带头节点的单链表：
1.头节点是一种不存数据，只存放下一个的地址的特殊节点，我们使用头节点是为了方便单链表接下来的插入与删除等操作。
2.带头节点的单链表的初始化操作
这里可以只用值传递而不用地址传递就可以完成对L头结点的空间开辟，是由于：
LinkList InitSqList(LinkList L){
L = (Lnode*)malloc(sizeof(Lnode));
if(L == NULL){
printf("单链表初始化失败\n");
return NULL;
}
L->data = 0;
L->next = NULL;
printf("单链表初始化成功\n");
return L;
}
//在main函数里调用该函数
int main(){
L = (Lnode*)malloc(sizeof(Lnode));
}
3.使用头插法创建单链表：
bool CreateListByHead(LinkList L){
if(L == NULL){
printf("链表还未初始化\n");
return false;
}
int x;
printf("请输入你要插入的值\n");
scanf("%d",&x);
Lnode* p = L;
Lnode* node = NULL;
while(x != 999){
node = (Lnode*)malloc(sizeof(Lnode));
node->data = x;
node->next = p->next;
p->next = node;
scanf("%d",&x);
}
return true;
}
4.使用尾差法创建单链表：
开始：
/*4.2 头插法创建链表*/
bool CreateListByHead(LinkList L){
if(L == NULL){
printf("链表还未初始化\n");
return false;
}
int x;
printf("请输入你要插入的值\n");
scanf("%d",&x);
Lnode* p = L;
Lnode* node = NULL;
while(x != 999){
node = (Lnode*)malloc(sizeof(Lnode));
node->data = x;
node->next = p->next;
p->next = node;
scanf("%d",&x);
}
return true;
}
5.根据指定位置插入指定元素
p节点开始指向头节点，定义一个int 类型的i变量初始值为0
我们的目标是找到插入位置的前一个节点，比如我们插入的位置为2，我们寻找的目标节点为1节点，接下来让p向后移动一个节点的位置，让i++
发现找到位置了，就让代插入节点插入1节点之后
这样就完成插入算法了。
我们再解释一下while(p != NULL && i < index - 1)循环推出条件，当满足 i < index - 1退出循环就是上面我说的情况，找到位置了，当满足的是p != NULL说明p指向空时依然没有找到你输入的位置说明你输入的位置过大。
/*2.根据指定位置插入指定元素 */
bool InsertElementByIndex(LinkList L,int index,int element){
if(index < 1){
printf("插入的位置不合法\n");
return false;
}
Lnode* p = L;//定义一个指针指向头结点
int i = 0;
while(p != NULL && i < index - 1){
p = p->next;
i++;
}
if(p == NULL){
printf("插入的位置过大\n");
return false;
}
//创建一个新节点
Lnode* node = (Lnode*)malloc(sizeof(Lnode));
node->data = element;
//插入操作
node->next = p->next;
p->next = node;
printf("插入成功\n");
return true;
}
5.删除指定位置的元素
/*删除指定位置的元素,位置为下表+1,并保存被删除的值*/
bool DeleteElementByIndex(LinkList L,int index,int *element){
if(L->next == NULL){
printf("链表为空\n");
return false;
}
if(index < 1){
printf("删除的位置太小\n");
return false;
}
//定义两个指针，p q
Lnode* p = L;
Lnode* q = L->next;
int i = 1;
while(q != NULL && i <= index-1){
p = q;
q = q->next;
i++;
}
if(q == NULL){
printf("你输入的位置过大\n");
return false;
}
*element = q->data;
p->next = q->next;
free(q);
printf("删除成功\n");
return true;
}
6.删除链表中的元素，根据值删除元素，返回删除元素的个数
int DeleteElementByValue(LinkList L,int element){
if(L->next == NULL){
printf("链表为空\n");
return false;
}
int count = 0;//记录删除元素的个数
Lnode* p = L->next;
Lnode* q = L;
Lnode* f = NULL;
while(p != NULL){
if(p->data == element){
f = p;
p = p->next;
q->next = f->next;
free(f);
f = NULL;
count++;
}else{
q = p;
p = p->next;
}
}
printf("删除成功\n");
return count;
}
7.查找链表中的元素，根据位置index查找对应的元素的值。
/*7,查找链表中的元素，根据位置index查找对应的元素的值。*/
int SelectElementByIndex(LinkList L,int index){
if(L->next == NULL){
printf("链表为空\n");
exit(-1);
}
if(index < 1){
printf("查找的位置太小\n");
exit(-1);
}
//定义一个Lnode类型的指针指向L的头结点后的第一个元素
Lnode* p = L->next;
int i = 1;
while(p != NULL && i <= index - 1){
p = p->next;
i++;
}
if(p == NULL){
printf("你输入的位置过大\n");
exit(-1);
}
printf("查找成功\n");
return p->data;
}
8.修改链表的指定位置的值
/*8.修改链表的指定位置的值*/
bool UpdateElementByIndex(LinkList L,int index,int element){
if(L->next == NULL){
printf("链表为空\n");
return false;
}
if(index < 1){
printf("查找的位置太小\n");
return false;
}
Lnode* p = L->next;
int i = 1;
while(p != NULL && i <= index-1){
p = p->next;
i++;
}
if(p == NULL){
printf("你输入的位置过大\n");
return false;
}
p->data = element;
printf("修改成功\n");
return true;
}
9.求表长
/*9.求表长*/
int ListLength(LinkList L){
int len = 0;
Lnode* p = L;
while(p->next != NULL){
p = p->next;
len++;
}
return len;
}
10.翻转链表的内容
本题的思想是将链表的头结点与其他节点断开，在进行头插法实现链表内容的翻转。
先让指针p指向1节点，
断开头结点与1节点的链接，让头结点指向空
先让q指向p所指向的位置，再让p指向下一个节点
再让q所指向的节点使用头插法重新插入头结点后的位置
插入后再让指针q指向p，p再向后移动一个节点的位置。
再将q指向的2节点使用头插法进入左边的链表，
再将指针q指向指针p指向的节点，p再向后移动一个节点。
再使用头插法将q所指向的3节点插入左边的节点，
当p为空时，循环停止，这样就实现了链表内容的翻转。
/*10.翻转链表的内容*/
void reverseLinkList(LinkList L){
if(L->next == NULL){
printf("链表为空\n");
return;
}
Lnode* p = L->next;
Lnode* q = NULL;
L->next = NULL;
while(p != NULL){
q = p;
p = p->next;
q->next = L->next;
L->next = q;
}
}
11.找到链表中的最大值
/*11.找到链表中的最大值*/
int FindMax(LinkList L){
if(L->next == NULL){
printf("链表为空\n");
exit(-1);
}
Lnode* p = L->next;
int max = p->data;
while(p != NULL){
if(max < p->data){
max = p->data;
}
p = p->next;
}
return max;
}
12.整个代码实现：
#include
#include
#include
typedef struct Lnode{
int data;//单链表中的元素值
struct Lnode* next;//单链表中指向下一个节点的指针
}Lnode,*LinkList;
/*1.初始化单链表*/
LinkList InitLinkList(LinkList L){
//1.创建一个头结点并为其开辟空间
L = (Lnode*)malloc(sizeof(Lnode));
if(L == NULL){
printf("创建失败\n");
return NULL;
}
L->data = 0;
L->next = NULL;
printf("创建成功\n");
return L;
}
/*2.根据指定位置插入指定元素 */
bool InsertElementByIndex(LinkList L,int index,int element){
if(index < 1){
printf("插入的位置不合法\n");
return false;
}
Lnode* p = L;//定义一个指针指向头结点
int i = 0;
while(p != NULL && i < index - 1){
p = p->next;
i++;
}
if(p == NULL){
printf("插入的位置过大\n");
return false;
}
//创建一个新节点
Lnode* node = (Lnode*)malloc(sizeof(Lnode));
node->data = element;
//插入操作
node->next = p->next;
p->next = node;
printf("插入成功\n");
return true;
}
/*3.打印链表*/
void printLinkList(LinkList L){
if(L->next == NULL){
printf("链表为空\n");
return;
}
Lnode* p = L->next;
while(p != NULL){
printf("%d\t",p->data);
p = p->next;
}
printf("\n");
}
/*4.头插法创建链表*/
bool InsertHead(LinkList L,int element){
//判断链表为空
if(L == NULL){
printf("链表未初始化\n");
return false;
}
//创建一个新节点,并插入到头节点后面
Lnode* node = (Lnode*)malloc(sizeof(Lnode));
node->data = element;
node->next = L->next;
L->next = node;
printf("插入成功\n");
return true;
}
/*4.2 头插法创建链表*/
bool CreateListByHead(LinkList L){
if(L == NULL){
printf("链表还未初始化\n");
return false;
}
int x;
printf("请输入你要插入的值\n");
scanf("%d",&x);
Lnode* p = L;
Lnode* node = NULL;
while(x != 999){
node = (Lnode*)malloc(sizeof(Lnode));
node->data = x;
node->next = p->next;
p->next = node;
scanf("%d",&x);
}
return true;
}
/*5.尾差法创建链表*/
bool InsertTail(LinkList L,int element){
if(L == NULL){
printf("链表还未创建\n");
return false;
}
//创建一个节点
Lnode* node = (Lnode*)malloc(sizeof(Lnode));
node->data = element;
//创建一个指针指向头结点，并移动值最后一个节点。
Lnode* p = L;
while(p->next != NULL){
p = p->next;
}
node->next = p->next;
p->next = node;
printf("创建成功\n");
return true;
}
/*6.删除指定位置的元素,位置为下表,并保存被删除的值*/
bool DeleteElementByIndex(LinkList L,int index,int *element){
if(L->next == NULL){
printf("链表为空\n");
return false;
}
if(index < 1){
printf("删除的位置太小\n");
return false;
}
//定义两个指针，p q
Lnode* p = L;
Lnode* q = L->next;
int i = 1;
while(q != NULL && i <= index-1){
p = q;
q = q->next;
i++;
}
if(q == NULL){
printf("你输入的位置过大\n");
return false;
}
*element = q->data;
p->next = q->next;
free(q);
printf("删除成功\n");
return true;
}
/*6.2删除链表中的元素，根据值删除元素，返回删除元素的个数*/
int DeleteElementByValue(LinkList L,int element){
if(L->next == NULL){
printf("链表为空\n");
return false;
}
int count = 0;//记录删除元素的个数
Lnode* p = L->next;
Lnode* q = L;
Lnode* f = NULL;
while(p != NULL){
if(p->data == element){
f = p;
p = p->next;
q->next = f->next;
free(f);
f = NULL;
count++;
}else{
q = p;
p = p->next;
}
}
printf("删除成功\n");
return count;
}
/*7,查找链表中的元素，根据位置index查找对应的元素的值。*/
int SelectElementByIndex(LinkList L,int index){
if(L->next == NULL){
printf("链表为空\n");
exit(-1);
}
if(index < 1){
printf("查找的位置太小\n");
exit(-1);
}
//定义一个Lnode类型的指针指向L的头结点后的第一个元素
Lnode* p = L->next;
int i = 1;
while(p != NULL && i <= index - 1){
p = p->next;
i++;
}
if(p == NULL){
printf("你输入的位置过大\n");
exit(-1);
}
printf("查找成功\n");
return p->data;
}
/*8.修改链表的指定位置的值*/
bool UpdateElementByIndex(LinkList L,int index,int element){
if(L->next == NULL){
printf("链表为空\n");
return false;
}
if(index < 1){
printf("查找的位置太小\n");
return false;
}
Lnode* p = L->next;
int i = 1;
while(p != NULL && i <= index-1){
p = p->next;
i++;
}
if(p == NULL){
printf("你输入的位置过大\n");
return false;
}
p->data = element;
printf("修改成功\n");
return true;
}
/*9.求表长*/
int ListLength(LinkList L){
int len = 0;
Lnode* p = L;
while(p->next != NULL){
p = p->next;
len++;
}
return len;
}
/*10.翻转链表的内容*/
void reverseLinkList(LinkList L){
if(L->next == NULL){
printf("链表为空\n");
return;
}
Lnode* p = L->next;
Lnode* q = NULL;
L->next = NULL;
while(p != NULL){
q = p;
p = p->next;
q->next = L->next;
L->next = q;
}
}
/*11.找到链表中的最大值*/
int FindMax(LinkList L){
if(L->next == NULL){
printf("链表为空\n");
exit(-1);
}
Lnode* p = L->next;
int max = p->data;
while(p != NULL){
if(max < p->data){
max = p->data;
}
p = p->next;
}
return max;
}
int main(){
LinkList L;
L = InitLinkList(L);
CreateListByHead(L);
printLinkList(L);
//InsertElementByIndex(L,6,100);
reverseLinkList(L);
printLinkList(L);
int e = 0;
DeleteElementByIndex(L,5,&e);
printLinkList(L);
//printf("最大值为%d\n",FindMax(L));
// InsertElementByIndex(L,1,10);
// InsertElementByIndex(L,1,20);
// InsertElementByIndex(L,1,30);
// InsertHead(L,10);
// InsertHead(L,20);
// InsertHead(L,30);
// InsertHead(L,40);
// InsertHead(L,50);
// printLinkList(L);
//printf("单链表的长度为:%d\n",ListLength(L));
// InsertElementByIndex(L,2,1000);
// InsertTail(L,10);
// InsertTail(L,20);
// InsertTail(L,10);
// InsertTail(L,40);
// InsertTail(L,10);
// printLinkList(L);
// int count = DeleteElementByValue(L,10);
// printf("被删除的元素个数%d\n",count);
// printLinkList(L);
// int element;
// DeleteElementByIndex(L,2,&element);
// printf("删除的元素为%d\n",element);
// printLinkList(L);
// int e = SelectElementByIndex(L,2);
// printf("查找的元素值为%d\n",e);
// UpdateElementByIndex(L,0,1000);
// printLinkList(L);
}
四、总结：
链表的实现不难，我们在写代码时最好一边写代码一边画图，这样更方便我们理解。
-
相关阅读:
怎么做好企业短信服务呢？（文字短信XML接口示例）
【STM32】CRC（循环冗余校验)
『贪吃蛇』AI 算法简易实现（中秋特别版）
pytorch入门，deep-learning-for-image-processing-master的test3-vggnet
vector实现——memcpy拷贝问题
腾讯云轻量应用服务器使用场景列举说明
《深入浅出.NET框架设计与实现》阅读笔记（一）
Winform DataGridView 跳转到指定数据行
程序设计中遇到的程序不通、逻辑不顺等问题
【PG】PostgreSQL参数格式 配置文件格式
- 原文地址：https://blog.csdn.net/zhangyuanhang123/article/details/140916899