单向链表是数据结构中的一种,它由节点组成,每个节点包含两个部分:数据域和指针域。数据域用于存储节点的值,指针域则用于指向下一个节点。单向链表的特点是只能从头节点开始遍历到尾节点,不能反向遍历。
1 单向链表的节点定义
typedef struct node
{
int data; //数据域 用来存放数据 整型
struct node * next; //指针域 用来存放下一个节点的首地址
}link_node_t;
单向链表的操作
(
有头的单向链表
)
//1.
创建一个空的链表
createEmpty()
//2.
遍历链表的有效元素
showLinknode()
//3.
求链表的长度
getLen()
//4.
向链表的指定位置插入数据
insertInto
//5.
判断链表是否为空
,
空返回
1
,未空返回
0 isEmpty()
//6.
删除链表指定位置的数据
deleteFrom()
//7.
查找指定数据,出现在链表中的位置
findData()
//8.
清空链表
clear()
2.创建一个空的链表
//1.创建一个空的链表(本质上只有一个头节点链表,将头节点的首地址返回)
link_node_t* createEmptyLinklist()
{
//创建一个空的头节点
link_node_t* p = malloc(sizeof(link_node_t));
if(p == NULL)
{
printf("createEmptyLinklist malloc failed!!\n");
return NULL;//表达申请失败
}
//申请空间,就是为了装东西
p->next = NULL;//指针域初始化为NULL,数据域不用初始化,因为头节点数据域无效
//将头节点的首地址返回
return p;
}
3.遍历有头链表的有效元素
void showLinklist(link_node_t* p)
{
while(p->next != NULL)
{
p = p->next;
printf("%d ",p->data);
}
printf("\n");
}
4.求链表的长度
int getLengthLinklist(link_node_t* p)
{
int len = 0;//统计长度
while(p->next != NULL)
{
p = p->next;
len++;//打印一次,就计数一次
}
return len;
}
5.判断链表是否为空,空返回1,未空返回0
//6. 判断链表是否为空 空返回1,未空返回0
int isEmptyLinklist(link_node_t* p)
{
//p指向头节点
//p->next代表头节点的指针域,头节点的指针域为空,说明后面什么没有了
return p->next == NULL ? 1 : 0;
}
6.向链表的指定位置插入数据
编程思想
:
0.
容错判断(
post
<=
0
||
post
>
getLinkLen
(
p
)
+
1
)
1.
创建新的节点,保存插入的数据
x
也就是
100
2.
将头指针移动到插入位置的前一个位置
3.
将新的节点插入
(
先连后面,再连前面
)
int insertIntoLinklist(link_node_t* p, int post, int x)
{
int i;
//0.容错判断
if(post < 1 || post > getLengthLinklist(p)+1)
{
printf("insertIntoLinklist failed!!\n");
return -1;
}
//1.创建一个新的节点,保存插入的数据x
link_node_t* pnew = malloc(sizeof(link_node_t));
if(pnew == NULL)
{
printf("pnew malloc failed!!\n");
return -1;
}
//申请空间,就是为了装东西,立刻装东西
pnew->data = x;
pnew->next = NULL;
//准备开始插入
//2.将头指针指向(移动)插入位置的前一个位置
for(i = 0; i < post-1; i++)
p = p->next;
//3.将新节点插入链表(先连后面,再连前面)
pnew->next = p->next;//连后面
p->next = pnew;//连前面
return 0;
}
7.删除链表指定位置的数据
编程思想
:
1.
将头指针移动到删除位置的前一个位置
2.
定义一个指针,指向被删除节点
3.
跨过被删除节点
4.
释放被删除节点
int deleteFromLinklist(link_node_t* p, int post)
{
//0.容错判断
if(post < 1 || post > getLengthLinklist(p) || isEmptyLinklist(p))
{
printf("deleteFromLinklist failed!!\n");
return -1;
}
//1. 将头指针移动到删除位置的前一个位置
int i;
for(i = 0; i < post-1; i++)
p = p->next;
//2.定义了指针变量4个字节,指向被删除节点
link_node_t* pdel = p->next;
//3.跨过被删除节点
p->next = pdel->next;
//4. 释放被删除节点
free(pdel)
pdel = NULL;
return 0;
}
8.清空链表
编程思想:
1.
将头指针移动到删除位置的前一个位置 可以不写
2.
定义了指针变量
4
个字节
,
指向被删除节点
3.
跨过被删除节点
4.
释放被删除节点
void clearLinklist(link_node_t* p)
{
//砍头思想:每次删除的是头节点的下一个节点
while(p->next != NULL)
//只要链表不为空,就执行删除操作 p->next == NULL循环结束,此时是空的表
{
//1. 将头指针移动到删除位置的前一个位置
//第一步可以省略不写,因为每次删除的是头节点的下一个节点,
//那么头节点就是每次被删除节点的前一个位置
//2.定义了指针变量4个字节,指向被删除节点
link_node_t* pdel = p->next;
//3.跨过被删除节点
p->next = pdel->next;
//4. 释放被删除节点
free(pdel);
pdel = NULL;
}
}
9.查找指定数据x出现的位置
int searchDataLinklist(link_node_t* p, int x)
{
int post = 0;
while(p->next != NULL)
{
p = p->next;
post++;//用来记录第几个
if(p->data == x)
return post;//返回值是第几个
}
return -1;//不存在
}
结语
以上就是单向链表的基本使用,本次代码分享到此结束,后续还会分享单向链表的尾插法以及头插法。最后的最后,还请大家点点赞,点点关注,谢谢大家!