博客

功能：(9个) 创建 测长 查找 遍历 插入 删除 逆置  查找单链表中间元素 判断单链表是否有环

平台：Windows VS13

代码：

#include <stdio.h>
#include <stdlib.h>//使用malloc free要用到该头文件//【拓展3】函数malloc() free() 在stdlib.h中声明，而C++中的new delete是关键字
#include <stdbool.h>
typedef struct _tag_node
{
	int m_data;//数据域 - 节点内容 //【拓展1】这里的int 可换为 #define TYPE int 【疑问1】但是这样在遍历单链表 用printf函数的时候，如何打印TYPE类型？printf("%TYPE",...)???
								   //【拓展2】结构体首元素是指针，以实现底层算法与上层应用的分离-企业级代码规范 
	struct _tag_node *m_next;//指针域 - 指向下一个节点
}node;

/*
	功能     ：尾插法实现单链表
	变量解释 ：head头指针、p指针 指向开辟的节点、q辅助指针 指向p - 作为尾节点存在
	代码描述 ：第一次while循环，头指针head指向第一个p节点，q指向p；
			   然后每while循环一次开辟一个p节点，辅助指针q指向p；
			   最后退出的时候q作为尾节点指向NULL，实现含有头节点的单链表。
			   该单链表特点 - 有头节点（头节点数据域为空，只存在指针域，且没有前驱），尾节点指向NULL；- 即“头节点没前驱，尾节点没后继。”
	返回值   ：返回链表的头指针
*/
node *create_list()
{
	int num = 0;//链表中节点的个数
	int data;
	node *head, *p, *q;
	q = NULL;//【注意1】指针q需要初始化一下 不然编译器报错
	head = (node *)malloc(sizeof(node));//头节点

	while (1)
	{
		printf("Please input the data: ");
		scanf_s("%d", &data);
	
		if (data == 0)//如果输入的节点内容为0  则表示退出该子函数
			break;
		p = (node *)malloc(sizeof(node));//指针p指向开辟的节点
		p->m_data = data;

		if (++num == 1)//如果链表里只有一个节点
		{
			head->m_next = p;//头指针指向该唯一的节点
		}
		else
		{
			q->m_next = p;
		}
		q = p;//q指向当前节点 说白了即q就是p，while循环每次p都会重新在堆区开辟空间，而q每次都是被覆盖的，即q指向当前节点（尾差的p）
	}
	q->m_next = NULL;//节点数据域给0退出while循环，则尾节点q指向NULL
	return head;
}

/*
	功能     ：测长
	函参解释 ：*head 传址 - 传入的是指向链表首地址的头指针
	代码描述 ：头节点数据域为空，所以从头节点的下一个节点开始算起
	返回值   ：返回单链表长度，为int类型
*/
int length_list(node *head)
{
	int len = 0;
	node *p = NULL;
	p = head->m_next;

	while (p != NULL)
	{
		len++;
		p = p->m_next;
	}
	return len;
}

/*
	功能     ：遍历
	函参解释 ：*head 传址 - 传入的是指向链表首地址的头指针
	代码描述 ：与测长类似，但要多做个空链表的容错
	返回值   ：空
*/
void printf_list(node *head)
{
	int index = 0;//用来表示第几个节点
	node *p = NULL;
	p = head->m_next;//【注意3】传指针的话，子函数内最好再声明一个指针，用来指向传递进来的指针，这样做既能操作原数据还能避免对原指针的指向破坏。

	if (NULL == p)//常量写前面的好处：如果手误写成 NULL = p 编译器能检测出来，反之p = null则不行 //【注意2】NULL是指针常量
	{
		printf("The list is empty !\n");
		return;
	}

	while (p != NULL)
	{
		index++;
		printf("printf_list the %dth node data = %d\n", index, p->m_data);
		p = p->m_next;
	}
}

/*
	功能     ：查询 
	函参解释 ：*head - 传址 - 传入的是指向链表首地址的头指针，pos - 查询单链表中第pos个节点
	代码描述 ：(1)多了几个容错，pos<0、pos==0、空链表即 p == NULL 的情况；
			   (2)--pos先减再while()循环判断，p = head->m_next; p即第一个节点，所以pos==1的时候while()不会循环；
			   因此while()从pos==2开始循环，找到第2个节点
	返回值   ：指向第pos个节点的指针，类型是 node* 
*/
node *search_node(node *head, int pos)
{
	node *p = head->m_next;

	if (0 > pos)
	{
		printf("incorrect position to search node !\n");
		return NULL;
	}
	if (0 == pos)
	{
		return head;
	}
	if (NULL == p)
	{
		printf("Link is empty !\n");
		return NULL;
	}

	while (--pos)
	{
		if (NULL == (p = p->m_next))
		{
			printf("incorrect position to search node!\n");
			break;
		}
	}
	return p;
}

/*
	功能     ：插入
	函参解释 ：*head - 传址 - 传入的是指向链表首地址的头指针，pos - 查询单链表中第pos个节点，data是输入的节点的数据
	代码描述 ：插入分两种 - 头插、尾插，该函数采用尾差，即插入到第pos个节点的后面。
	返回值   ：头指针
*/
node *insert_node(node *head, int pos, int data)
{
	//node *q = head;

	node *item = NULL;
	node *p = NULL;

	item = (node *)malloc(sizeof(node));
	item->m_data = data;
	
	//if (0 == pos)
	//{
	//	item->m_next = q->m_next;//【划重点 造成野指针场景！】【注意5】尾插 新节点插入时 指针指向的顺序一定不能错！！！ 
	//							 //书上例子就错了  它没写这句话！！！顺序错误，在插入pos=0 data=5之后，调用测长函数的时候，发生指针错误。
	//							 //因为不写这句话新节点就没有后继，测长函数循环里的p = p->m_next;  新节点没有后继导致野指针！！！
	//	head->m_next = item;	 //...多想了 其实这个情况根本不用考虑 下面的代码对pos==0也符合
	//	return head;
	//}

	p = search_node(head, pos);//找到需要插入的节点位置，并尾插在其后
	if (NULL != p)
	{
		item->m_next = p->m_next;
		p->m_next = item;
	}
	return head;
}

/*
	功能     ：删除
	函参解释 ：*head - 传址 - 传入的是指向链表首地址的头指针，pos - 查询单链表中第pos个节点
	代码描述 ：找到所删除的第pos-1个节点，让该节点的next指针指向第pos个节点的下一个即可删除第pos个节点
	返回值   ：只有头指针的空链表时，返回空指针，否则返回头指针
*/
node *delete_node(node *head, int pos)
{
	node *item = NULL;
	node *p = head->m_next;
	if (NULL == p)
	{
		printf("The linklist is empty!\n");
		return NULL;
	}

	p = search_node(head, pos - 1);
	if ((NULL != p) && (NULL != p->m_next))
	{
		item = p->m_next;
		p->m_next = item->m_next;
		free(item);
	}
	return head;
}

/*
	功能     ：单链表逆置
	函参解释 ：*head - 传址 - 传入的是指向链表首地址的头指针
	代码描述 ：遍历链表，利用辅助指针，存储遍历过程中 当前指针指向的下一个元素。然后，将当前节点的指针域反转之后，利用已经存储的指针继续往后遍历
	返回值   ：头指针(头节点地址没变 变的是头节点的next指针)
*/
node *reverse(node *head)
{
	node *p, *q, *r;

	if (NULL == head->m_next)
	{
		return head;
	}

	p = head->m_next;
	q = p->m_next;
	p->m_next = NULL;

	while (NULL != q)
	{
		r = q->m_next;//【注意7】链表节点 指针域 怎么保存 指向谁

		q->m_next = p;//
		p = q;
		q = r;
	}
	head->m_next = p;
	return head;
}

/*
	功能     ：查找单链表的中间元素
	函参解释 ：*head - 传址 - 传入的是指向链表首地址的头指针
	代码描述 ：测链表长，表长对2取余得到mid node位置
	返回值   ：返回单链表的中间元素的位置
*/
int search_mid_node(node *head)
{
	int ret_lem = 0, mid = 0;
	ret_lem = length_list(head);

	if (0 != (ret_lem % 2))
		mid = (ret_lem + 1) / 2;
	else
		mid = ret_lem / 2;

	return mid;
}

/*
	功能     ：判断链表是否存在环
	函参解释 ：*head - 传址 - 传入的是指向链表首地址的头指针  **loop_start - 用来存储回环的起始地址 - 主调用函数传参时，仅需传递&loop_start 主调用函数(node *loop_start 一级指针)
	代码描述 ：每次循环p1向前走一步，p2向前走两步，直到p2碰到NULL指针或p1==p2的情况时，循环结束。若p1==p2存在环，否则不存在。
	返回值   ：bool - false true
*/
bool IsLoop(node *head, node **loop_start)
{
	node *p1 = head, *p2 = head;

	if ((NULL == head) || (NULL == head->m_next))
		return false;

	do
	{
		p1 = p1->m_next;//走一步
		p2 = p2->m_next->m_next;//走两步
	} while ( p2 && p2->m_next && (p1 != p2) );//分别对应 只有一个节点 有两个节点 存在环

	if (p1 == p2)
	{
		*loop_start = p1;//经调试 二级指针loop_start 存储 一级指针p1的地址 //这样主调函数就可以 通过传址（指针）来间接操作环的起始节点p1
						 //二级指针指向一级指针 *二级指针 即取二级指针的值 //https://blog.csdn.net/ye1223/article/details/79674975 二级指针讲得不错
						 //指针只能存储地址，所以主调函数要对 传的一级指针变量 取址//这里的环起始点是人为规定的 - 存储环的起始点（node 1 2 3 4 如果人造环是改变node4为指向node2，则node4为环起始节点）
		return true;
	}
	else
		return false;
}

void main()
{
	int mid = 0;//用于接收寻找出的单链表中间元素的位置
	int pos = 1;//用于单链表查询 pos=0表示查询头节点 pos=1表示查询第一个节点 //含头节点的单链表 查询的时候正好pos=2和第2个在一般认识上匹配
	int len = 0;//用于接收length_list()的返回值
	//node *t;//用于删除所有链表里的节点
	node *ret_head = NULL;//用于接收create_list()返回的指针
	node *ret_search = NULL;//用于接收printf_list()返回的指针
	node *ret_insert = NULL;//用于接收insert_node()返回的指针

	//【1】根据输入的data创建单链表
	ret_head = create_list();

	//【2】测链表长度
	printf("length_list = %d\n", length_list(ret_head));

	//【3】遍历整个单链表
	printf_list(ret_head);//【注意4】比如这里，联系一下【注意3】就可以知道，如果ret_head传参的时候，length_list()子函数直接使用ret_head会导致ret_head指向改变，这样printf_list（）就会得到错误的头指针！

	//【4】查找单链表中的某个节点
	ret_search = search_node(ret_head, pos);
	printf("search_node pos = %d  data = %d\n", pos, ret_search->m_data);

	//【5】插入节点
	insert_node(ret_head, 4, 5);
	printf("\n");
	printf("length_list = %d\n", length_list(ret_head));
	printf_list(ret_head);

	//【6】单链表逆置
	reverse(ret_head);
	printf("\n");
	printf_list(ret_head);

	//【7】查找到单链表的中间元素并打印
	mid = search_mid_node(ret_head);
	ret_search = search_node(ret_head, mid);
	printf("\n");
	printf("search_mid_node mid = %d  data = %d\n", mid, ret_search->m_data);

	//【8】判断链表是否存在环
	//先人为构造一个环 - 所谓环，起实质是改变某一节点指针域指向，使其指向前面的节点。
	//这里构造环：节点node 1 2 3 4，node4指向node2 数据依次是：头节点 5 4 3 2 1 
	//即 输入4个数据 依次为1 2 3 4 再输入0结束链表创建 然后再上面的插入和逆置操作之后 变成 头节点 5 4 3 2 1
	//node **loop_start = NULL;//用来存储环的起始节点的地址 //【注意8】这里对二级指针和传递指针的概念的理解错误！！！
	node *loop_start = NULL;//用来存储环的开始节点//环是没有开始和结束的准确节点的，这里先当于规定的一个开始节点吧(即快慢指针的相遇节点)
	node *loop_node_start = search_node(ret_head, 5);
	node *node = search_node(ret_head, 1);//node1
	loop_node_start->m_next = node->m_next;
	//printf("\n");
	//printf_list(ret_head);//经验证 存在环 //最方便的方式：在IsLoop(ret_head, loop_start);处打断点，进去看链表的存储结构

	bool ret_IsLoop = IsLoop(ret_head, &loop_start);//【注意9】这里传递的是 &loop_start 而不是二级指针**loop_start
	printf("\n");
	printf("loop_start data = %d\n", loop_start->m_data);//IsLoop()子函数已经实现对环起始节点p1的指向，那么直接对主函数的结构体指针操作即可
	
	//想要恢复单链表 只需要将尾节点指针域重新指向NULL即可
	ret_search = search_node(ret_head, 5);
	ret_search->m_next = NULL;
	printf("\n");
	printf_list(ret_head);

	//【9】删除全部节点
	len = length_list(ret_head);
	while (len)
	{
		delete_node(ret_head, len);
		len = len - 1;
	}
	printf("\n");
	printf("length_list = %d\n", len);
	printf_list(ret_head);

	//删除时 出的问题！
	//释放堆区所有开辟的空间 - 即删除所有节点 - 有malloc必有free 以防导致野指针
	//t = ret_head;
	//while (NULL != t)
	//{
	//	t = t->m_next;
	//	
	//	//free(t);//【注意6】这里就犯傻了，free()函数可以释放指向 开辟的堆区空间的 指针，但是节点的释放有delete_node()函数啊
	//			  //这里free()导致的问题是：释放掉第一个指针后，释放第二个时出现野指针
	//	printf("\n");
	//	printf("length_list = %d\n", length_list(ret_head));
	//	printf_list(ret_head);
	//}

	system("pause");
}

结果：