C语言数据结构-链表

学习笔记 C语言 数据结构
发布日期:   2021-03-15
更新日期:   2021-05-19
文章字数:   3k
阅读次数:  
作者: LightningMaster

C语言数据结构-链表

前言

这篇博客属于学习笔记，是博主在学习链表时的一些笔记，所以不保证内容的完全正确性和严谨性以及简洁等。

此外由于属于学习笔记所以不会对原理性知识进行讲解，博客重点放在代码上。

使用环境：

  • C语言
  • VS2019

创建链表

创建链表的方法可能会有很多种，博主这里使用的是把头结点空出来也就是不给头节点赋值的一种创建方式。

/*结点结构体*/
struct Node
{
	int data;
	struct Node* next;
};
typedef struct Node Node;

/*创建链表*/
Node* createNode()
{
	/* head,tail分别指向链表的头结点和尾结点*/
	Node* head, * tail, * p;
	int num;
	head = (Node*)malloc(sizeof(Node));    /*申请内存*/
	tail = head;
	printf("请输入一组数据，结尾使用'-9999'\n");
	(void)scanf("%d", &num);
	while (num != -9999)
	{
		p = (Node*)malloc(sizeof(Node));    /*申请内存*/
		p->data = num;    /*结点赋值*/
		tail->next = p;    /*当前链表尾指向结点p*/
		tail = p;    /*将结点p设为尾结点*/
		(void)scanf("%d", &num);
	}
	tail->next = NULL;    /*最后一个结点指向NULL*/
    printf("链表创建成功\n");
	return head;
}

打印链表内容

因为创建链表是从首结点开始的（从首结点开始赋值），所以打印的时候也要从首结点开始。

/*打印链表*/
void displayNode(Node* head)
{
	if (head->next == NULL)    /*判断链表是否为空*/
		printf("链表为空\n");
	else
	{
		Node* p;
		p = head->next;    /*从首结点开始*/
		printf("链表如下\n");
		while (p != NULL)    /*遍历打印*/
		{
			printf("%d    ", p->data);
			p = p->next;
		}
        printf("\n");
	}
}

打印链表内容-效果图

在这里为了更好的理解代码引用其他博主的博客中的一句话，（出处原地址:C语言链表操作详解)

我在这着重解释一下p->next = NULL和p!=NULL的区别，因为我刚开始也经常弄错！！
while(p->next ！= NULL) 循环结束时，此时p的位置是尾节点的位置，但如果用于输出函数的判断条件，则尾节点的数据不会输出。
while(p!=NULL) 循环结束时， 此时p指向的位置为尾节点的下一个节点，因为没有申请内存空间，所以是一个未知的区域。

理解这两句话的话就可以继续下面的学习了。

释放链表内存

在结束链表使用的时候需要释放一下内存。

/*释放链表内存*/
void releaseNode(Node* head)
{
	Node* p1, * p2;
	p1 = head;
	while (p1 != NULL)
	{
		p2 = p1;
		p1 = p1->next;
		free(p2);
	}
	printf("链表释放内存成功\n");
}

删除结点

这里提供两种不同目的的删除方式，一种是根据结点值删除，另一种是根据结点位置删除。

根据结点值删除

/*根据结点的值删除链表中结点*/
void deleteNode_val(Node* head)
{
	
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		Node* p1, * p2;
		int num;
		printf("请输入要删除的结点数值：\n");
		(void)scanf("%d", &num);
		p1 = head->next;    /*使用p1逐个寻找数据*/
		p2 = NULL;
		while ((p1->data != num) && (p1->next != NULL))    /*遍历寻找*/
		{
			p2 = p1;    /*用p2记录p1原来的位置*/
			p1 = p1->next;
		}
		if (p1->data == num)
		{
			if (p1 == head->next)    /*判断p1是否为首结点*/
			{
				head->next = p1->next;    /*如果是则将头结点与首结点的下一个结点链接*/
			}
			else
				p2->next = p1->next;   /*将p1前一个结点p2直接与p1下一个结点链接*/
			free(p1);    /*释放p1的内存*/
			printf("删除成功\n");
		}
		else
			printf("删除失败\n");
	}
}

根据结点值删除结点-效果图

根据结点位置删除

这里的位置索引是从“1”开始的，可以通过修改变量now_pos改变位置索引。

/*根据结点位置删除结点*/
void deleteNode_pos(Node* head)
{
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		Node* p1, * p2;
		int  now_pos= 1, pos;
		printf("请输入要输出结点的位置：\n");
		(void)scanf("%d", &pos);
		p1 = head->next;
		p2 = NULL;
		while ((now_pos != pos) && (p1->next != NULL))
		{
			p2 = p1;
			p1 = p1->next;
			now_pos++;
		}
		if (now_pos == pos)
		{
			if (p1 == head->next)
				head->next = p1->next;
			else
				p2->next = p1->next;
			free(p1);
			printf("删除成功\n");
		}
		else
			printf("删除失败\n");
	}
}

根据结点位置删除-效果图

根据结点位置插入新的结点

/*根据结点位置插入新的结点*/
void insertNode(Node* head)
{
	if (head->next != NULL)
	{
		int pos, val, now_pos = 1;
		Node* p, * p1, * p2;
		p = (Node*)malloc(sizeof(Node));
		printf("请输入要插入的值和位置\n");
		(void)scanf("%d %d", &val, &pos);
		p->data = val;
		p->next = NULL;
		p1 = head->next;
		p2 = NULL;
		while ((now_pos != pos) && (p1 != NULL))    /*注意这里，如果使用p1->next则没办法在插入到最后*/
		{
			p2 = p1;
			p1 = p1->next;
			now_pos++;
		}
		if (now_pos == pos)
		{
			if (p1 == head->next)
			{
				head->next = p;
				p->next = p1;
			}
			else
			{
				p2->next = p;
				p->next = p1;
			}
			printf("插入成功\n");
		}
		else
			printf("插入失败\n");
	}
	else
		printf("链表为空\n");
}

根据结点位置插入新的结点-效果图

根据结点位置修改结点的值

/*根据结点位置修改结点的值*/
void changeNode(Node* head)
{
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		int now_pos = 1, pos, val;
		Node* p1;
		printf("请输入要修改的值和位置\n");
		(void)scanf("%d %d", &val, &pos);
		p1 = head->next;
		while ((now_pos != pos) && (p1->next != NULL))
		{
			p1 = p1->next;
			now_pos++;
		}
		if (now_pos == pos)
		{
			p1->data = val;
			printf("修改成功\n");
		}
		else
			printf("修改失败\n");
	}
}

根据结点位置修改结点的值-效果图

根据结点的值查找结点位置

/*根据结点的值查找结点位置*/
void checkNode(Node* head)
{
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		Node* p1;
		int val, now_pos = 1;
		printf("请输入要查询的值：\n");
		(void)scanf("%d", &val);
		p1 = head->next;
		while ((p1->data != val) && (p1->next != NULL))
		{
			now_pos++;
			p1 = p1->next;
		}
		if (p1->data == val)
			printf("位置为：%d\n", now_pos);
		else
			printf("未找到\n");
	}
}

根据结点的值查找结点位置-效果图

根据结点的位置查找结点的值

/*根据结点的位置查找结点的值*/
void checkNode_pos(Node* head)
{
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		Node* p1;
		int pos, now_pos = 1;
		printf("请输入要查询的位置：\n");
		(void)scanf("%d", &pos);
		p1 = head->next;
		while ((now_pos != pos) && (p1->next != NULL))
		{
			p1 = p1->next;
			now_pos++;
		}
		if (now_pos == pos)
			printf("结点值为：%d\n", p1->data);
		else
			printf("未找到\n");
	}
}

根据结点的位置查找结点的值-效果图

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#include <stdlib.h>

struct Node
{
	int data;
	struct Node* next;
};
typedef struct Node Node;

/*创建链表*/
Node* createNode()
{
	/* head,tail分别指向链表的头结点和尾结点*/
	Node* head, * tail, * p;
	int num;
	head = (Node*)malloc(sizeof(Node));
	tail = head;
	printf("请输入一组数据，结尾使用'-9999'\n");
	(void)scanf("%d", &num);
	while (num != -9999)
	{
		p = (Node*)malloc(sizeof(Node));    /*申请内存*/
		//if (p == NULL)
		//	exit(0);
		p->data = num;
		tail->next = p;
		tail = p;
		(void)scanf("%d", &num);
	}
	tail->next = NULL;
	return head;
}

/*打印链表*/
void displayNode(Node* head)
{
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		Node* p;
		p = head->next;    /*从首结点开始*/
		printf("链表如下\n");
		while (p != NULL)
		{
			printf("%d    ", p->data);
			p = p->next;
		}
		printf("\n");
	}
}

/*释放链表内存*/
void releaseNode(Node* head)
{
	Node* p1, * p2;
	p1 = head;
	while (p1 != NULL)
	{
		p2 = p1;
		p1 = p1->next;
		free(p2);
	}
	printf("链表释放内存成功\n");
}

/*根据结点的值删除链表中结点*/
void deleteNode_val(Node* head)
{
	
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		Node* p1, * p2;
		int num;
		printf("请输入要删除的结点数值：\n");
		(void)scanf("%d", &num);
		p1 = head->next;    /*使用p1逐个寻找数据*/
		p2 = NULL;
		while ((p1->data != num) && (p1->next != NULL))
		{
			p2 = p1;    /*用p2记录p1原来的位置*/
			p1 = p1->next;
		}
		if (p1->data == num)
		{
			if (p1 == head->next)
			{
				head->next = p1->next;
			}
			else
				p2->next = p1->next;   /*将p1前一个结点p2直接与p1下一个结点链接*/
			free(p1);
			printf("删除成功\n");
		}
		else
			printf("删除失败\n");
	}
	// return head;
}

/*根据结点位置删除结点*/
void deleteNode_pos(Node* head)
{
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		Node* p1, * p2;
		int  now_pos= 1, pos;
		printf("请输入要输出结点的位置：\n");
		(void)scanf("%d", &pos);
		p1 = head->next;
		p2 = NULL;
		while ((now_pos != pos) && (p1->next != NULL))
		{
			p2 = p1;
			p1 = p1->next;
			now_pos++;
		}
		if (now_pos == pos)
		{
			if (p1 == head->next)
				head->next = p1->next;
			else
				p2->next = p1->next;
			free(p1);
			printf("删除成功\n");
		}
		else
			printf("删除失败\n");
	}
}

/*根据结点位置插入新的结点*/
void insertNode(Node* head)
{
	if (head->next != NULL)
	{
		int pos, val, now_pos = 1;
		Node* p, * p1, * p2;
		p = (Node*)malloc(sizeof(Node));
		printf("请输入要插入的值和位置\n");
		(void)scanf("%d %d", &val, &pos);
		p->data = val;
		p->next = NULL;
		p1 = head->next;
		p2 = NULL;
		while ((now_pos != pos) && (p1 != NULL))
		{
			p2 = p1;
			p1 = p1->next;
			now_pos++;
		}
		if (now_pos == pos)
		{
			if (p1 == head->next)
			{
				head->next = p;
				p->next = p1;
			}
			else
			{
				p2->next = p;
				p->next = p1;
			}
			printf("插入成功\n");
		}
		else
			printf("插入失败\n");
	}
	else
		printf("链表为空\n");
}

/*根据结点位置修改结点的值*/
void changeNode(Node* head)
{
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		int now_pos = 1, pos, val;
		Node* p1;
		printf("请输入要修改的值和位置\n");
		(void)scanf("%d %d", &val, &pos);
		p1 = head->next;
		while ((now_pos != pos) && (p1->next != NULL))
		{
			p1 = p1->next;
			now_pos++;
		}
		if (now_pos == pos)
		{
			p1->data = val;
			printf("修改成功\n");
		}
		else
			printf("修改失败\n");
	}
}

/*根据结点的值查找结点位置*/
void checkNode_val(Node* head)
{
	if (head->data == NULL)
		printf("链表为空\n");
	else
	{
		Node* p1;
		int val, now_pos = 1;
		printf("请输入要查询的值：\n");
		(void)scanf("%d", &val);
		p1 = head->next;
		while ((p1->data != val) && (p1->next != NULL))
		{
			now_pos++;
			p1 = p1->next;
		}
		if (p1->data == val)
			printf("位置为：%d\n", now_pos);
		else
			printf("未找到\n");
	}
}

/*根据结点的位置查找结点的值*/
void checkNode_pos(Node* head)
{
	if (head->next == NULL)
		printf("链表为空\n");
	else
	{
		Node* p1;
		int pos, now_pos = 1;
		printf("请输入要查询的位置：\n");
		(void)scanf("%d", &pos);
		p1 = head->next;
		while ((now_pos != pos) && (p1->next != NULL))
		{
			p1 = p1->next;
			now_pos++;
		}
		if (now_pos == pos)
			printf("结点值为：%d\n", p1->data);
		else
			printf("未找到\n");
	}
}

int main()
{
	Node* head;
	head = createNode();    // 创建列表
	displayNode(head);    // 打印
	// releaseNode(head);
	// deleteNode_val(head);
	// deleteNode_pos(head);
	// insertNode(head);
	// changeNode(head);
	// checkNode_val(head);
	checkNode_pos(head);
	displayNode(head);
	releaseNode(head);
	return 0;
}
文章作者: LightningMaster
文章链接: https://lightningleader.github.io/posts/10.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 LightningMaster !
学习笔记 C语言 数据结构
评论
  目录