数据结构-单链表

文章 目录

单链表概念

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

链接存储方法

链接方式存储的线性表简称为链表（Lin k e d Li st）。链表的具体存储表示为： ①
用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ②
链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。
结点结构：

data域–存放结点值的数据域 next域–存放结点的直接后继的地址（位置）的指针域（链域）
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Sin gl e Lin k e d
Li st）。

头指针head和终端结点

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head 指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空，即NULL。

链接 过程

从逻辑上：
在这里插入图片描述
从物理上：

单链表的优缺点：

1、优点：

插入和删除操作方便，在单链表中，插入和删除节点时，只需修改相邻节点的游标即可，不需要移动大量数据，因此操作效率较高。适合动态存储，单链表可以随时插入和删除节点，因此适合动态存储数据。空间利用率高，单链表不需要连续的存储空间，因此可以更有效地利用内存空间。

2、缺点：

查找效率低，在单链表中，查找某个元素需要从头节点开始遍历整个链表，因此查找效率较低。
需要额外的空间存储游标，单链表需要额外的空间存储游标，这会增加内存空间的消耗。实现复杂度较高，相比数组等数据结构，单链表的实现复杂度较高，需要维护节点的引用关系。

实现

一.思路
1.利用结构体来储存数据和指针（结构体能够存储不同类型数据）
2.每增加一个数据就通过 malloc 函数来扩展一个空间
3.通过多文件的方式来实现
4.我们实现打印、扩容、尾插、头插、尾删、头删接口函数
二.框架
 结构体创建、一些定义：

#include&lt;stdio.h&gt;
#include<stdlib.h&gt;//动态内存函数的头文件
typedef int SLTDataType;//类型定义
struct SListNode
{
	SLTDataType data;//数据
	struct SListNode* next;//链接点
};
typedef struct SListNode SLTNode;//类型定义

主函数：

void  Test() {
	SLTNode* plist = NULL;//头指针初始化  因为开始是没有数据
	}
int main() {
	Test();//调用函数
	return 0;
}

三.接口函数的实现
1.打印函数：
（1）参数：结构体指针类型（接收头指针），由于不需要改变头指针，所以传一个头指针变量过来就行
（2）迭代：将后一个链接的指针变量 next 传给指针p head来找到下一个结点
代码实现：

void SListPrint(SLTNode* phead) {//打印函数
	//由于不需要改变头指针，所以传一个头指针变量过来就行了
	while (phead != NULL) {//将phead不是空指针之前的数据打印
		printf("%d-&gt;", phead-&gt;data);//打印数据
		phead = phead-&gt;next;//迭代
	}
	printf("NULL");//最后打印指向的NUll
}

2.扩容函数：
（1）我们通过malloc函数来实现扩容
（2）参数：插入的数据
（3）返回类型：返回扩建的空间指针变量
（4）过程：在扩容后将插入的数据存储到这个空间里。并把指针变量置空
代码实现：

SLTNode* uuu(SLTDataType x) {//扩容和储存数据
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode-&gt;data = x;//储存数据
	newnode-&gt;next = NULL;//将扩容和的链接点置空
	return newnode;//放回这个空间的地址
}

3.尾插函数：
有两种情况：
（1）头指针为空，此时将扩建的第一个空间直接当头指针
在这里插入图片描述
（2）头指针不为空，此时将我们要通过头指针找到最后一个结点，再用这个结点来链接我们扩建的空间

注意：
1.在实现这个过程可能会改变头指针，所以传参需要使用传址调用
2.第二种情况不要改变头指针

代码实现：

void SListPushBack(SLTNode** pphead, SLTDataType x) {//尾插
//注意：这里需要传参需要进行传址调用
	SLTNode* newnode = uuu(x);//插入一个数据需要再创建一个新的空间
	if (*pphead == NULL)//判断是否是第一种情况
		*pphead = newnode;
	else
	{
		SLTNode* cat = *pphead;//防止头指针被改变
			while(cat-&gt;next!=NULL){//找到最后一个结点
				cat = cat->next;//迭代
		}
			cat->next = newnode;//将扩展的空间连接在最后一个结点的next上
	}
}

检查：
我们尾插 1、2

SListPushBack(&amp;plist, 1);
SListPushBack(&amp;plist, 2);
SListPrint(plist);

在这里插入图片描述

4.头插函数：
（1）我们直接将创建的空间的next与第一个结点连接即可
在这里插入图片描述
注意：在实现这个过程会改变头指针，所以传参需要使用传址调用
代码实现：

void SListPushFront(SLTNode** pphead, SLTDataType x) {头插
	SLTNode* newnode = uuu(x);//扩建空间
		newnode->next = *pphead;//与第一个结点连接即头指针
		*pphead = newnode;//将头指针改为头插的空间
}

检查：
我们头插一个 0

void  Test() {
	SLTNode* plist = NULL;
	SListPushBack(&amp;plist, 1);
	SListPushBack(&amp;plist, 2);
	SListPushFront(&amp;plist, 0);
		SListPrint(plist);
}

运行结果：
在这里插入图片描述
5，头删函数：
（1）这个我们不用创建新的空间但是要释放空间。释放函数 f err（）
（2）我们可以创建一个新的指针变量来接收第一个结点的next（第二个结点的地址），然后将第一个结点释放掉，再然后将新的指针变量当作头指针
（3）在实现这个过程会改变头指针，所以传参需要使用传址调用
代码实现：

void SListPopFront(SLTNode** pphead) {//头删
	SLTNode* next = (*pphead)->next;//创建一个新的指针变量来接收第一个结点的next（第二个结点的地址）
	free(*pphead);//释放
	*pphead = next;//重新设置头指针
}

检查：
头删一个数据：

void  Test() {
	SLTNode* plist = NULL;
	SListPushBack(&amp;plist, 1);
	SListPushBack(&amp;plist, 2);
	SListPushFront(&amp;plist, 0);
	SListPopFront(&amp;plist);
			SListPrint(plist);
}

运行结果：
在这里插入图片描述
6.尾删函数：
分三种情况：
（1）没有结点
返回NULL
（2）有一个结点
将其直接释放，并置空
（3）多个结点
我们要创建两个新的变量分别来找倒数第一和第二个结点，释放最后一个结点倒数，第二个结点next置空

代码实现：

void SListPopBack(SLTNode** pphead) {//尾删
	if (*pphead == NULL)//当为空是直接返回空
		return;
	else if ((*pphead)->next == NULL) {//只有一个结点时，直接释放掉pphead并将其置空
		free(*pphead);
		*pphead = NULL;
	}
	else {//多个结点
		SLTNode* cat = *pphead;//为了不改变头指针，创建一个新的变量
	    SLTNode* cat1= NULL;//用于找到倒数第二个结点，最后将其next置空
		while (cat->next != NULL) {//找最后一个结点
			cat1 = cat;
			cat = cat->next;
		}
		free(cat);//释放最后一个结点
		cat1->next = NULL;//倒数第二个结点next置空
	}
}

检查：
尾删一个数据

void  Test() {
	SLTNode* plist = NULL;
	SListPushBack(&amp;plist, 1);
	SListPushBack(&amp;plist, 2);
	SListPushFront(&amp;plist, 0);
	SListPopFront(&amp;plist);
	SListPopBack(&amp;plist);		
	SListPrint(plist);
}

运行结果：
在这里插入图片描述

代码一览

SList.h：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>//动态内存函数的头文件
typedef int SLTDataType;//类型定义
struct SListNode
{
	SLTDataType data;//数据
	struct SListNode* next;//链接点
};
typedef struct SListNode SLTNode;//类型定义

// 不会改变链表的头指针，传一级指针
void SListPrint(SLTNode* phead);

// 可能会改变链表的头指针，传二级指针
void SListPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SListPushFront(SLTNode** pphead, SLTDataType x);//头插
void SListPopFront(SLTNode** pphead);头删
void SListPopBack(SLTNode** pphead);//尾删

SList.c：

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"

void SListPrint(SLTNode* phead) {//打印函数
	//由于不需要改变头指针，所以传一个头指针变量过来就行了
	while (phead != NULL) {//将phead不是空指针之前的数据打印
		printf("%d->", phead->data);//打印数据
		phead = phead->next;//迭代
	}
	printf("NULL");//最后打印指向的NUll
}


SLTNode* uuu(SLTDataType x) {//扩容和储存数据
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;//储存数据
	newnode->next = NULL;//将扩容和的链接点置空
	return newnode;//放回这个空间的地址
}

void SListPushBack(SLTNode** pphead, SLTDataType x) {//尾插
	SLTNode* newnode = uuu(x);
	if (*pphead == NULL)
		*pphead = newnode;
	else
	{
		SLTNode* cat = *pphead;
			while(cat->next!=NULL){
				cat = cat->next;
		}
			cat->next = newnode;
	}
}
void SListPushFront(SLTNode** pphead, SLTDataType x) {头插
	SLTNode* newnode = uuu(x);
		newnode->next = *pphead;
		*pphead = newnode;
}
void SListPopFront(SLTNode** pphead) {//头删
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

void SListPopBack(SLTNode** pphead) {//尾删
	if (*pphead == NULL)
		return;
	else if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
		SLTNode* cat = *pphead;
	    SLTNode* cat1= NULL;
		while (cat->next != NULL) {
			cat1 = cat;
			cat = cat->next;
		}
		free(cat);
		cat1->next = NULL;
	}
}

Test:

#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"


void  Test() {
	SLTNode* plist = NULL;
	SListPushBack(&amp;plist, 1);
	SListPushBack(&amp;plist, 2);
	SListPushFront(&amp;plist, 0);
	SListPopFront(&amp;plist);
	SListPopBack(&amp;plist);
	
		SListPrint(plist);
}
int main() {
	Test();
	return 0;
}