单向链表
单向链表是由若干个节点组成的数据结构，每个节点包含两个部分：数据域和指针域。数据域存储节点的数据，指针域存储下一个节点的地址。
#include "03.h"
void fn3()
{
int order = 0;
elementType val;
elementType elementVal;
LinkNode* ListNode = NULL;
print_menu();
while (1)
{
printf("请输入您的操作指令：");
scanf("%d", &order);
switch (order)
{
case 1:
//初始化 初始化一个头节点(包含元素)
printf("链表初始化，请输入头节点的值：");
scanf(" %d", &val);
ListNode = init_list(val);
break;
case 2:
//遍历
print_list(ListNode);
break;
case 3:
//头插 需要改变头结点，所以需要传址
printf("请输入要头插的值：");
scanf(" %d", &val);
head_insert(&ListNode, val);
break;
case 4:
//尾插 不需要改变头结点，所以不需要传址，传值即可
printf("请输入要尾插的值：");
scanf(" %d", &val);
tail_insert(ListNode,val);
break;
case 5:
//头删
head_delete(&ListNode);
break;
case 6:
//尾删
tail_delete(&ListNode);
break;
case 7:
//查找 找到了返回这个元素的指针
printf("请输入要查找的元素的值：");
scanf(" %d", &val);
LinkNode* temp1 = find_list(ListNode, val);
if (temp1)
{
printf("找到了，链表里面有改元素：%d\n", temp1->value);
}
else
{
printf("链表里面没有该元素\n");
}
break;
case 8:
//中间删1 通过元素本身的值删除
printf("请输入要删除的元素的值：");
scanf(" %d", &val);
middle_delete1(&ListNode,val);
/*中间删2 通过要删除的前一个元素的值来删除
printf("请输入您要删除的元素的前一个元素值:");
scanf("%d", &val);
LinkNode* temp = find_list(ListNode, val);
if (temp == NULL)
{
printf("没有此元素\n");
}
else
{
middle_delete2(temp);
}
*/
break;
case 9:
//中间插
printf("请输入你要插入的元素值：");
scanf(" %d", &val);
printf("请输入你要在哪个元素的后边插入：");
scanf(" %d", &elementVal);
LinkNode* temp2 = find_list(ListNode, elementVal);
if (temp2 == NULL)
{
printf("没有此元素\n");
}
else
{
middle_insert(temp2, val);
}
break;
case 10:
//销毁
destory_list(&ListNode);
break;
case 11:
//退出
return;
default:
printf("指令有误重新输入\n");
}
}
}
//菜单
void print_menu()
{
system("cls");//屏幕清空
printf("操作指令说明:\n");
printf("1:链表初始化\n2:打印链表\n");
printf("3:链表头插\n4:链表尾插\n");
printf("5:链表头删\n6:链表尾删\n");
printf("7:链表的查找\n8:链表的中间删\n");
printf("9:链表的中间插\n10:链表销毁\n");
printf("11:退出\n");
}
//链表初始化
LinkNode* init_list(elementType val)
{
LinkNode* newLinkNode = (LinkNode*)malloc(sizeof(LinkNode));
//判断内存是否申请成功
/*if (newLinkNode == NULL)
{
printf("内存申请失败\n");
return NULL;
}*/
/*两个调试代码常用的方式：
1.exit(number) 用于终止程序执行，来判断程序正不正常
程序终止执行的时候会返回n
number的值一般用0表示正常退出 非0异常退出
2.assert(条件) 条件为真，程序正常执行
头文件assert.h 条件为假，程序报错，退出*/
assert(newLinkNode); //内存创建失败，则程序报错退出
newLinkNode->value = val;
newLinkNode->next = NULL;//初始化链表里面只有一个节点，所以这里的指针要值空
printf("链表初始化成功\n");
return newLinkNode;
}
//打印链表
void print_list(LinkNode* ListNode)
{
assert(ListNode);
//遍历，定义一个临时的节点来存储头节点 然后往后遍历
LinkNode* temp = ListNode;
while (1)
{
printf(" %d ", temp->value);
if (temp->next == NULL)
{
break;
}
temp = temp->next;
}
printf("\n");
}
//链表头插
void head_insert(LinkNode** ListNode, elementType val)
{
assert(*ListNode);//判断是否是空表
//1.创建新节点
LinkNode* newLinkNode = (LinkNode*)malloc(sizeof(LinkNode));
assert(newLinkNode);
//2.给新节点赋值
newLinkNode->value = val;
//3.让新节点指向头结点 此时新节点已经是头结点了
newLinkNode->next = *ListNode;
//4.更新头节点
*ListNode = newLinkNode;
printf("链表头插成功\n");
}
//链表尾插
void tail_insert(LinkNode* ListNode, elementType val)
{
assert(ListNode);//判断是否是空表
//1.创建新节点
LinkNode* newLinkNode = (LinkNode*)malloc(sizeof(LinkNode));
assert(newLinkNode);
//2.给新节点赋值
newLinkNode->value = val;
newLinkNode->next = NULL;
//3.遍历链表，找到尾节点
LinkNode* temp = ListNode;//定义一个临时节点
while (1)
{
if (temp->next == NULL)//找到最后一个节点
{
temp->next = newLinkNode;//将最后一个节点的指针指向新节点
break;
}
temp = temp->next;
}
printf("链表尾插成功\n");
}
//链表头删
void head_delete(LinkNode** ListNode)
{
assert(*ListNode);//判断是否是空表
LinkNode* temp = *ListNode;//定义一个临时节点储存头结点
*ListNode = temp->next;//更新头节点，把第二个节点变成头结点
free(temp);
temp = NULL;//释放后制空
printf("链表头删成功\n");
}
//链表尾删
void tail_delete(LinkNode** ListNode)
{
assert(*ListNode);//判断是否是空表
//如果只有一个头节点，则直接调用头删函数
if ((*ListNode)->next == NULL)
{
printf("只有头节点，只能头删\n");
head_delete(&(*ListNode));
}
else
{
LinkNode* temp = *ListNode;
while (1)
{
//找到次尾节点
if (temp->next->next == NULL)
{
free(temp->next);//释放尾节点
temp->next = NULL;//将次尾节点的指针制空——>变成尾节点
break;
}
temp = temp->next;
}
//
printf("链表尾删成功\n");
}
}
//链表查找
LinkNode* find_list(LinkNode* ListNode,elementType val)
{
assert(ListNode);//判断是否是空表
//遍历链表
LinkNode* temp = ListNode;
while (temp)
{
if (temp->value == val)
{
return temp;
}
temp = temp->next;
}
return NULL;
}
//链表中间删除1 删除元素本身的值
void middle_delete1(LinkNode** ListNode,elementType val)
{
assert(*ListNode);//判断是否是空表
//只有一个头节点且要删除的就是头节点
if ((*ListNode)->next == NULL && (*ListNode)->value==val)
{
printf("删除的是头节点，只能头删\n");
head_delete(&(*ListNode));
}
else if ((*ListNode)->next->next == NULL)
{
//只有两个节点
if ((*ListNode)->value == val)
{
LinkNode* ptr = *ListNode;
*ListNode = ptr->next;
free(ptr);
ptr = NULL;
printf("中间删除成功\n");
}
else if ((*ListNode)->next->value == val)
{
LinkNode* ptr = (*ListNode)->next;
free(ptr);
ptr= NULL;
printf("中间删除成功\n");
}
}
else
{
//不只二个节点的情况
LinkNode* temp = *ListNode;//
int label = 0;
while (temp)
{
if (temp->next->value == val)
{
label = 1;
LinkNode* ptr = temp->next;//保存要删除的节点
temp->next = temp->next->next;
free(ptr);
ptr = NULL;
printf("中间删除成功\n");
break;
}
temp = temp->next;
}
if (label == 0)
{
printf("链表里没有你要删除的元素\n");
}
}
}
//链表中间删除2 通过要删除的前一个元素的值来删除
void middle_delete2(LinkNode* temp)
{
//如果这个元素是尾元素
if (temp->next == NULL)
{
printf("后面没有元素无法删除！！\n");
return;
}
else
{
LinkNode* ptr = temp->next->next;//保存要删除的元素的后一个元素
free(temp->next);//释放掉要删除的元素节点
temp->next = ptr;//释放后的指针如果没有指向具体的地址，则需要指空
printf("中间删除成功！！\n");
}
}
//
void middle_insert(LinkNode* temp,elementType val)
{
LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
assert(newNode);
//给新节点数据域赋值
newNode->value = val;
//将新节点插入
newNode->next = temp->next;
temp->next = newNode;
}
void destory_list(LinkNode** ListNode)
{
assert(*ListNode);
while (*ListNode)
{
LinkNode* temp = (*ListNode)->next;
free((*ListNode));
*ListNode = temp;
}
*ListNode = NULL;
printf("销毁成功\n");
}