链表-有头链表链表-有头链表

119 阅读 0 评论 79 点赞

我是靠谱客的博主激情荔枝，这篇文章主要介绍链表-有头链表链表-有头链表，现在分享给大家，希望可以做个参考。

链表-有头链表

一、什么是链表

链表是一种数据结构，数据结构也就是存取数据的一种方式。它是指相互之间存在一种或多种特定关系的数据元素的集合。而链表是由多个一样特点基本单位组成(我们用结构体来表示这个基本单位)的，而每一个单位只负责下一个数据的位置，要知道它是怎么连接的那就要知道，在基本单位结构体中的分为两种数据分别是:数据域和指针域，它是由每个基本单位结构体的指针域指向下一个位置的地址，从而将它们连接起来。链表在内存空间中数据存储的位置的特点是分布离散的、随机的。它们像串珠子一样一个接一个的线性结构。
在这里插入图片描述 头指针与头结点
头指针：头指针是指向链表第一个结点的的指针，如果有头结点那么头指针就是头结点的指针。

头结点：头结点是为了操作统一和方便而设立的，即放在第一个元素的结点之前，数据域一般没有意义（也可以放链表长度）

链表的分成
有头链表、无头链表、双向链表、双向循环链表。

二、有头链表

我们今天来说说有头链表，顾名思义有头链表一定有一个领头羊（头结点）去引导下面的数据。但是要注意的是有头链表它的头节点是不放数据的。

有头链表的思路

1.每个链表都是由多个一样的单元构成所以要先用结构体创建一个最小的特征单位。

复制代码

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdlib.h>
//最小的单位
struct Node
{
	int data;//数据域
	struct Node* next;//指针域
};

2.有头链表要有一个头部去引导下一个数据所以第二步要创建一个头出来

复制代码

1
2
3
4
5
6
7
8
//创建表头（链表）
struct Node* createHead()
{
	struct Node* Nodehead = (struct Node*)malloc(sizeof(struct Node));//用malloc在堆区开辟一个空间
	Nodehead->next = NULL;//创建的表头没有数据跟着所以要NULL
	return Nodehead;
}

3.有了头之后，我们要创建结点，因为每个链表都是由许多的节点构成的，所以要创建节点

复制代码

1
2
3
4
5
6
7
8
9
//创建结点
struct Node* createNode(int data)
{
	struct Node* Noded = (struct Node*)malloc(sizeof(struct Node));
	Noded->data = data;
	Noded->next = NULL;
	return Noded;
}

5.创建好链表之后，我们必然要对其进行数据的扩增和无用数据的删除（在数据的添加和删除时都要记得保存下一个结点防止数据丢失）。数据的添加有以下三种方式：

表头插入

复制代码

1
2
3
4
5
6
7
8
//头结点插入
void insertHeaders(struct Node* head, int data)
{
	struct Node* NodeDian = Nodedian(data);//要想插入一个新的结点就要先创造一个
	NodeDian->next = head->next;
	head->next = NodeDian;
}

表尾插入

在这里插入图片描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
/表尾插入
void insertFooter(struct Node* list, int data)
{
	struct Node* newNode = createNode(data);//创建结点
	struct Node* movNode = list->next;      //创建一个移动结点
	while (movNode->next)//找表尾 当movNode->next为空时跳出，表示movNode是表尾
	{
		movNode = movNode->next;
	}
	movNode->next = newNode;  //连接
}

指定数据插入
（查找时:我们可以定义2个节点，进行交替寻找，一个节点指向另一个节点的下一个地址，反复循环直到找指定位置，判断条件有两种情况
①没有找到指定数据(即最后地址指向为NULL)
②找到指定数据
当满足以上条件时，在对其进行判断是哪种情况。）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void addSpecify(struct Node* list,int data,int find)
{
	struct Node* ChaNode = list;
	struct Node* chaNode = list->next;
	while (chaNode->next!=NULL&&chaNode->data!=find) //找指定位置
	{
		ChaNode = chaNode;
		chaNode = ChaNode->next;
	}
	if (ChaNode->next == NULL)//当指向为NULL，即没有找到指定数据
	{
		printf("没有此结点");
	}
	else                      //否则就是找到该数据
	{
		struct Node* NewNode = createNode(data);  //创建要插入的新结点
		NewNode->next = chaNode;      //连接
		ChaNode->next = NewNode;
	}
}

数据的删除有以下三种方式：

头删除

在这里插入图片描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//删除头结点
void DeletnNodeHead(struct Node* list)
{
	struct Node* head = list;
	struct Node* Node = head->next;
	if (head->next == NULL) // 判断有没有数据，没有数据就不能删除
	{
		printf("没有链表");
	}
	else
	{
		head->next = Node->next;  //
		free(Node);               //删除申请空间，不删除就会出现“内存泄漏”
		Node = NULL;              
	}
}

尾删除

在这里插入图片描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//删除尾巴
void deletFooter(struct Node* list)
{
	struct Node* Node = list;
	struct Node* Nodet = Node->next;
	if (Nodet == NULL)
	{
		printf("没有链表");
		return;
	}
	while (Nodet ->next!= NULL)//查找表尾
	{
		Node = Nodet;
		Nodet = Node->next;
	}
	Node->next = NULL;
	free(Nodet);
	Nodet = NULL;
}

指定删除

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//删除指定节点
void DeleteNode(struct Node* list,int data)
{
	struct Node* Dode = list;
	struct Node* Dodet = list->next;
	while (Dodet->next!=NULL&&Dodet->data!=data) //找指定位置
	{
		Dode = Dodet;
		Dodet = Dode->next;
	}
	if (Dodet->next == NULL)  //当指向为NULL，即没有找到指定数据
	{
		printf("没有这个节点");
	}
	else                     //否则就是找到该数据
	{
		Dode->next = Dodet->next;
		free(Dodet);
		Dodet = NULL;
	}

}

6.打印函数

复制代码

1
2
3
4
5
6
7
8
9
10
11
void PrintList(struct Node* list)
{
	struct Node* PNode = list->next;
	while (PNode)
	{
		printf("%d-->",PNode->data);
		PNode = PNode->next;
	}
	printf("n");
}

main函数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
	int i = 0;                      
	struct Node* list = createHead();                       
	for (i = 0; i < 10; i++)
	{
		insertHeaders(list, i);//头插法存储数据0、1、2、3、4、5、6、7、8、9
	}
	PrintfList(list);          //打印
	insertFooter(list,-100);   //尾插法存储数据
	PrintfList(list);          //打印
	deletFooter(list);         //尾删法
	PrintfList(list);          //打印
	DeletnNodeHead(list);      //头删法
	PrintfList(list);          //打印
	DeleteNode(list,5);        //指定删除      
	PrintfList(list);          //打印
	addSpecify(list, 3, -7);   //指定添加
	PrintfList(list);          //打印
	system("pause");
	return 0;
}