欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

手把手教你学单链表

程序员文章站 2022-06-06 10:03:11
...

本文用到的图片来自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.最后在这里提醒大家一下,链表的插入和删除,节点在内存中的实体并不会发生改变,本质上是对节点的地址以及它的指针域进行了操作。
以上就是单链表的讲解,下一篇博文将对双链表进行讲解,如果你有什么疑问或者是高见,可以在评论区里留言。

相关标签: 数据结构 笔记