手把手教你学单链表
本文用到的图片来自csdn中优秀的博主。
为什么我们要学习链表呢?链表到底有什么好处。
链表主要有以下几大好处:
1、解决数组无法存储多种数据类型的问题。
2、解决数组中,元素个数无法改变的限制。
3、数组插入和移动元素的过程中,要对元素进行大范围的移动,很耗时间,效率也不高。
而链表却可以很好地弥补数组不足的缺点。
从这幅图我们得出以下信息:
这个简单链表的构成:
头指针(Header),若干个节点(节点包括了数据域和指针域),最后一个节点要指向空。
实现原理:头指针指向链表的第一个节点,然后第一个节点中的指针指向下一个节点,然后依次指到最后一个节点,这样就构成了一条链表。
换句话说,一个链表一定要有一个表头,表头里的数据没有意义,它的作用是指向链表的第一个节点。并且,最后一个节点的指针域中存储的信息一定要是NULL。
在本篇博文中,我做了一些与链表相关的函数,将以思维导图的形式给大家看看,然后把相应的代码附上。
1.节点的数据结构
//节点的数据结构
typedef struct list_node
{
int val;
struct list_node* next;
}list;
2.链表头的初始化
//表头的初始化
list* header_init(void)
{
list* phead = NULL;
phead = (list*)malloc(sizeof(list));
if (phead == NULL)
printf("malloc faliure");
memset(phead, 0, sizeof(list));//清0
phead->val = 0;
phead->next = NULL;
return phead;
}
3.链表节点的创建
//链表节点的创建
list* creat_list_node(int data)
{
list* node = (list*)malloc(sizeof(list));
if (node == NULL)
printf("node creat failure");
memset(node, 0, sizeof(list));
node->val = data;
node->next = NULL;
return node;
}
4.链表的节点插入
//链表插入
void insert(list * front, list* new)//插入一个节点,第一个参数是插入的位置的前面一个节点
{
if (front->next == NULL)
{
front->next = new;
new->next = NULL;
}//new->next一般来说就是NULL,这里加上这一句是为了说明该节点是链表的尾部
else
{
new->next = front->next;
front->next = new;
}
}
void tail_insert(list* header, list* new)//尾部插入
{
list* p = header;
while (p->next != NULL)
p = p->next;
p->next = new;
new->next = NULL;//new->next一般来说就是NULL,这里加上这一句是为了说明该节点是链表的尾部
}
void top_insert(list* header, list* new)//头部插入
{
new->next = header->next;
header->next = new;
}
5.链表打印(走链)
void print_node(list* header)//走链,把数据都打印出来
{
list* p = header;
while (p->next != NULL)
{
p = p->next;
printf("ID:%d\n", p->val);
}
}
6.链表的逆序
void trave_list(list* header)
{
//保存第一个节点的位置
list* p = header->next;
list* pBack=NULL;
int i = 0;
if (p->next == NULL || p == NULL)
return;
while (NULL != p->next) //遍历链表
{
//保存第一个节点的下一个节点
pBack = p->next;
//找到第一个有效节点,其实就是头指针的下一个节点
if (p == header->next)
{
//第一个有效节点就是最后一个节点,所以要指向NULL
p->next = NULL;
}
else
{
/*
new->next = p->next ;
p->next = new ;
*/
p->next = header->next; //尾部连接
}
header->next = p; //头部连接
p = pBack; //走下一个节点
}
top_insert(header, p); //插入最后一个节点
}
7.删除节点
int delete_list_node(list* header, int data)//链表的删除
{
list* p = header;
list* pback = NULL;
while (p->next != NULL)
{
pback = p;
p = p->next;
if (p->val == data)
{
pback->next = p->next;
free(p);
return 0;//如果每有return语句,你可以想象一下会出现什么情况
}
}
if (p->val == data)
pback->next = NULL;
return 0;
}
以上就是链表相关的函数。
我们调用一下以上的函数,看看结果是否如我们所想的那样。
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
//节点的数据结构
typedef struct list_node
{
int val;
struct list_node* next;
}list;
//表头的初始化
list* header_init(void)
{
list* phead = NULL;
phead = (list*)malloc(sizeof(list));
if (phead == NULL)
printf("malloc faliure");
memset(phead, 0, sizeof(list));//清0
phead->val = 0;
phead->next = NULL;
return phead;
}
//链表节点的创建
list* creat_list_node(int data)
{
list* node = (list*)malloc(sizeof(list));
if (node == NULL)
printf("node creat failure");
memset(node, 0, sizeof(list));
node->val = data;
node->next = NULL;
return node;
}
//链表插入
void insert(list * front, list* new)//插入一个节点,第一个参数是插入的位置的前面一个节点
{
if (front->next == NULL)
{
front->next = new;
new->next = NULL;
}//new->next一般来说就是NULL,这里加上这一句是为了说明该节点是链表的尾部
else
{
new->next = front->next;
front->next = new;
}
}
void tail_insert(list* header, list* new)//尾部插入
{
list* p = header;
while (p->next != NULL)
p = p->next;
p->next = new;
new->next = NULL;//new->next一般来说就是NULL,这里加上这一句是为了说明该节点是链表的尾部
}
void top_insert(list* header, list* new)//头部插入
{
new->next = header->next;
header->next = new;
}
void print_node(list* header)//走链,把数据都打印出来
{
list* p = header;
while (p->next != NULL)
{
p = p->next;
printf("ID:%d\n", p->val);
}
}
int delete_list_node(list* header, int data)//链表的删除
{
list* p = header;
list* pback = NULL;
while (p->next != NULL)
{
pback = p;
p = p->next;
if (p->val == data)
{
pback->next = p->next;
free(p);
return 0;//如果每有return语句,你可以想象一下会出现什么情况
}
}
if (p->val == data)
pback->next = NULL;
return 0;
}
void trave_list(list* header)
{
//保存第一个节点的位置
list* p = header->next;
list* pBack=NULL;
int i = 0;
if (p->next == NULL || p == NULL)
return;
while (NULL != p->next) //遍历链表
{
//保存第一个节点的下一个节点
pBack = p->next;
//找到第一个有效节点,其实就是头指针的下一个节点
if (p == header->next)
{
//第一个有效节点就是最后一个节点,所以要指向NULL
p->next = NULL;
}
else
{
/*
new->next = p->next ;
p->next = new ;
*/
p->next = header->next; //尾部连接
}
header->next = p; //头部连接
p = pBack; //走下一个节点
}
top_insert(header, p); //插入最后一个节点
}
void main()
{
int i;
list* header =header_init();
for (i = 1; i < 10; i++)
{
tail_insert(header, creat_list_node(i));
}
print_node(header);
delete_list_node(header,5);
putchar('\n');
print_node(header);
putchar('\n');
trave_list(header);
print_node(header);
system("pause");
}
结果为
接下来,对与链表相关的函数进行大概的讲解
1.节点的数据结构
1.节点的数据域为一个int类型的数据(也可以是其他类型)
2.节点的指针域为一个同类型的结构体指针变量。
2.表头的初始化
1.在VC编译器下,在堆上开辟的内存块每个字节的内容都是cc,我们在这调用了memset函数,对开辟的内存块全部清零。
2.表头的数据域是没有任何意义的,表头的指针域起作用,目的就是指向第一个节点,在这里,我们赋值为NULL。
3.链表节点的创建
链表节点创建好之后,数据域存储着函数的形参,指针域默认NULL
4.链表的插入
链表插入分为表尾和表头
关于节点插入的函数有三个,和insert函数包含了表头和表尾的插入,但有的时候在某些情况下用起来不方便,所以还是写了表头和表尾插入函数,insert函数也可以在表中插入。
5.打印链表(走链)
走链的主要代码表达式为:p=p->next;
6.链表节点的删除
1.节点的删除分为表尾和非表尾,与链表的插入有异曲同工之妙。
2.值得注意的是当我们删除一个节点的时候,我么要将相应的存储块给释放
,并且链表的删除是根据对比节点的数据域来进行的。而默认节点之间的数据域不相同,所以一次也就删除一个节点,因此在我们的代码中,将节点内存释放后就返回了。
7.单链表的反链
主要的思想就是将第一个节点作为最后一个节点,然后将后续的节点插入到表头和第一个节点之间(这里的第一个节点是相对于表头来说的),这样就会形成原链表的反链。
那与链表相关的函数我们已经讲解完了,那么我们怎么使用上呢,以及有什么小技巧呢。
1.我们在创建一个链表的时候,总不能一直用表头指向下一个节点,然后用表头指向下一个节点再指向下一个节点吧。那太麻烦了,我们要善于运用for循环,看下图
当我们建立好一个表头后
你的链表有多长,你自己决定。
2.如果你想对链表中的某个节点操作,你也可以使用for循环
,比如你想对节点5进行操作,你可以这样。(p最开始指向表头)
执行完这个语句之后,p就指向了第5个节点。这样操作起来就很方便了。
3.最后在这里提醒大家一下,链表的插入和删除,节点在内存中的实体并不会发生改变,本质上是对节点的地址以及它的指针域进行了操作。
以上就是单链表的讲解,下一篇博文将对双链表进行讲解,如果你有什么疑问或者是高见,可以在评论区里留言。