单链表
- 大体思路
- 1.创建结构体---------具体事物的抽象(这里指链表的每一个节点）
- 2.创建链表
- 3.创建节点
- 4.插入操作
- 4.1 表头插入
- 4.2 表尾插入
- 4.3 指定位置插入（指定位置的前面）
- 5.删除操作
- 5.1表头删除
- 5.2 表尾删除
- 5.3指定位置删除
- 6.判断是否为空
- 7.打印链表
//本程序所需要的头文件
#include<stdio.h>
#include<stdlib.h> //包含了exit函数
#include<malloc.h>
//1.创建结构体
//如果把数据域写成结构体的话，就可以存储许多的数据了。
typedef struct singlelist {
int data; //数据域
struct singlelist *next; //指针域
}LIST, *LPLIST;
一定要把这个结构体的含义理解清楚
//2.创建链表--------我们可以理解成创建了第一个节点，索引的节点(头节点)
LPLIST CreateList() {
//创建过程就是初始化过程------初始化基本数据成员
//需要分配内存空间
LPLIST List = (LPLIST)malloc(sizeof(LIST));
if (List ==NULL) {
printf("分配内存空间失败，创建链表不成功。
");
system("pause");
exit(0);
}
//初始化数据成员 有表头的链表.
List->next = NULL;
return List;
}
//3.创建节点
LPLIST CreateNode(int data) {
//首先分配内存
//只是比创建链表多了数据域
LPLIST Node = (LPLIST)malloc(sizeof(LIST));
if (Node == NULL) {
printf("分配内存空间失败，创建节点不成功
");
system("pause");
exit(0);
}
Node->data = data;
Node->next = NULL;
return Node;
}
//4.插入操作
//4.1头插法:在头节点的后面插入
//函数写法：形参可以表示要操作的东西
//插入的链表是（List），插入的数据是多少(data)
void InsertHeadNode(LPLIST List,int data) {
//在实行链表的插入是一定要先连接后断开；
//插入:创建插入的节点
LPLIST NewNode = CreateNode(data);
//插入操作
NewNode->next = List->next;
List->next = NewNode;
}
//4.2 尾插法
void InsertTailNode(LPLIST List, int data) {
//找到表尾----》定义一个移动的指针tailNode来找到尾节点
LPLIST tailNode = List;
while (tailNode->next != NULL) {
tailNode = tailNode->next;
}
//插入：创建插入的节点；
LPLIST NewNode = CreateNode(data);
//插入操作
tailNode->next = NewNode;
}
//4.3 指定位置插入(这里面是在指定位置的前面插入）
int IsEmptyList(LPLIST List); //这里是为了在指定位置插入函数里面调用链表是否为空的函数说明。
void InsertMiddleNode(LPLIST List, int data,int middle){
//创建两个移动的指针,去找指定位置和指定位置的前面
LPLIST frontNode= List;
LPLIST tailNode = List->next;
//判断是否为空
if (IsEmptyList(List)) {
printf("链表为空无法从指定位置插入
");
system("pause");
exit(0);
}
while (tailNode->data != middle) {
//frontNode = frontNode->next;
//tailNode = tailNode->next; //这里有两种写法，看个人喜好。
frontNode = tailNode;
tailNode = frontNode->next;
if (tailNode == NULL) {
printf("没有缘分，无法找到");
system("pause");
exit(0);
}
}
//创建要插入的新节点
LPLIST NewNode=CreateNode(data);
/*NewNode->next = tailNode;
frontNode->next = NewNode;
*/
frontNode->next = NewNode;
NewNode->next = tailNode;
}
//5.----------判断链表是否为空
//和创建的时候比较
int IsEmptyList(LPLIST List) {
if (List->next == NULL)
return 1;
return 0;
}
//6.------>遍历链表
void PrintfList(LPLIST List) {
if (IsEmptyList(List)) {
printf("链表为空无法打印
");
system("pause");
exit(0);
}
//定义一个移动指针p来遍历链表
LPLIST p = List->next;
while (p != NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("
");
}
//7.删除操作
// 7.1 头删发
void DeleteListHeade(LPLIST List) {
if (IsEmptyList(List)) {
printf("链表为空无法删除
");
system("pause");
exit(0);
}
//把首节点(就是头节点的下一个节点)的地址赋值给一个临时指针tmp
LPLIST tmp = List->next;
List->next = tmp->next;
free(tmp);
tmp=NULL; //防止野指针的情况出现。
}
//7.2尾删除法
void DeleListTail(LPLIST List) {
if (IsEmptyList(List)) {
printf("链表为空无法删除
");
system("pause");
exit(0);
}
LPLIST tailNode = List->next;
LPLIST frontNode = List;
//找到尾节点
while (tailNode->next!=NULL) {
frontNode = tailNode;
tailNode = frontNode->next;
}
frontNode->next = NULL;
free(tailNode);
tailNode = NULL;
}
//.3指定位置删除
void deletemiddle(LPLIST list, int data) {
//创建两个移动的指针；去找指定为位置和指定位置的前面
LPLIST frontNode = list;
//frontNode->next==tailNode;判断相邻
LPLIST tailNode = list->next;
//判断是否为空
while (tailNode->data != data) {
/*
frontNode=frontNode->next;
tailNode=tailNode->next;
*/
frontNode = tailNode;
tailNode = frontNode->next;
if (tailNode == NULL) {
printf("未找到指定位置
");
system("pause");
exit(0);
}
}
frontNode->next = tailNode->next;
free(tailNode);
}
下面我们来用main()函数测试以下
int main() {
LPLIST List = CreateList(); //创建成功；
InsertHeadNode(List, 1); //头插法
InsertHeadNode(List, 2); //头插法
InsertHeadNode(List, 3); //头插法
PrintfList(List);
InsertHeadNode(List, 4); //头插法
PrintfList(List);
InsertTailNode(List, 0); //尾插法
PrintfList(List);
InsertMiddleNode(List, 6, 3); //在指定位置插入
PrintfList(List);
DeleteListHeade(List); //头删法
PrintfList(List);
DeleListTail( List); //尾删除法
PrintfList(List);
deletemiddle(List, 3); //指定位置删除
PrintfList(List);
system("pause");
return 0;
}
测试结果如下图
欢迎加我qq485536603一起讨论