当前位置： 首页 > article >正文

数据结构————链表

article 2024/11/13 12:24:30

 一、引言

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

要想学好数据结构 一定要画图 

下面我们要实现链表 首先我们应该仔细想想链表是什么  为什么使用链表 使用链表与顺序表相比有什么不同吗 如果不用有那些不同能  有为什么通过顺序表引入链表  学习链表应该掌握哪些知识  又是什么思想  接下来我们实现链表  链表的基本功能 增删改查   顺序表存在什么缺点呢？接下来我们好好分析以上问题

 二、链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

其实就是内存块  需要利用指针来链接起来

在设计链表之前应该先知道链表的样子 在我们假象中的样子 与实际的样子 为了更好的理解代码 我们应该经常画图构思 画图 就是逻辑结构 还有真实的物理图

物理结构：真实的数据在内存中的变化

逻辑结构：我们想象出的箭头。实际上没有cur在动。

三、链表的实现

typedef int SLTDataType；
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;//结构体指针
}SLTNode;

定义结构体的中查找规则是指针类型

1.1链表的打印

void SLTNode(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while(cur->next!=NULL)
	//while(cur!=NULL)
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

指针phead指向第一个结点  phead赋值给cur物理上就是把phead的值给cur 就如同cur有个箭头指向1的结点，cur的值不断被覆盖，也是逻辑上箭头移动的过程

next表示下一个结点的地zhi  循环变量 

phead赋值给cur物理上就是把phead的值给cur 就如同cur有个箭头指向1的结点，cur的值不断被覆盖，也是逻辑上箭头移动的过程

1.1.1链表打印与顺序表打印对比 

void SLPrint(SL* PS)
{
	assert(ps);
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

 顺序表

1.1.2链表为什么不断言

如果链表为NULL，那就是指针为NULL，链表是一个一个的结点，每个结点存下一个地址，每个结点就是一个结构以体，就是一个内存。可以打印空的数据。

1.2顺序表为什么断言

顺序表 指针指向结构体，数据不是存在结构体里，数据存在一段空间a，结构体的指针不能为NULL，要么就没法判断了，访问size判断顺序表是不是空，如果指针都是空了，就没办法访问size

如果size是0 就没有数据 没法访问

1.1.3  为什么不能用cur++代替cur=cur->next

由于链表的每一个结点都是单独malloc出来的，只有当malloc一次开辟很多个的时候才能保证空间是连续的，链表不能保证是连续的。

我们知道cur是指针 指向的是下一个结点的地址 要想实现对链表内容的打印 就要一个结点一个结点的访问，每一个结点存下一个结点的地址 通过指针访问每个结点，然后通过cur->next!=NULL判断访问结束。由于最后一个元素没有打印  next下一个结点的地址为NULL。

注意：循环语句不能使用cur++ 代替cur=cur->next 由于不能保证是连续的对于顺序表而言 他里面的数据放在一段空间中，他是连续的  可以用通过移动指针来遍历数组的内容  然而 对于一个链表来说 不能保证结点与另一个的地址是连续的 ，因为是malloc开辟的空间 地址可能连续 也可能不连续

1.2、链表的尾插

在实现尾插之前我们应先了解函数的传参  了解了这个 就会很容易的理解链表的尾插 思想类似

接下来我们看几组代码  观察一下有什么不同

1.2.1分析以下函数的调用

void Func(int y)
{
	y = 1;
}

int main()
{
	int x = 0;
	Func(x);
	return 0；
｝
void Func(int *p)
{
	*p = 1;
}

int main()
{
	int x = 0;
	Func(&x);
	return 0；
｝

void Func(int* ptr)
{
	ptr = (int*)malloc(sizeof(int));
}

int main()
{
	int* px = NULL;
	Func(px);
  free(px);
 

	return 0;
}
void Func(int** pptr)
{
	*pptr = (int*)malloc(sizeof(int));
}

int main()
{
	int* px = NULL;
	Func(&px);

	free(px);

	return 0;
}

  

1.2.2对以上函数解析 

二级指针传参，二级指针接收

从根本上来讨论，地址是不变的，不像是传值调用在内存中开辟的不是同一块空间，就会导致函数用一下就没了  如果打印实参的值 是没有改变的 

注意：想改变int，就是用int*的指针

通过C语言的学习我们很清楚的知道 函数在传参的过程中 形参是实参的临时拷贝  由于局部变量存放在内存的栈区 函数在使用过程中它的生命周期是 调用的时候作用 出作用域销毁 这种情况是传值调用  还有传址调用   实参传地址  形参就应该用指针接收  还应该注意 对于链表插入一个结点  就 既然插入新的结点 就代表着 这个链表是该变的 只要是改变的 如果要传int类型 就应该用int*的指针接收 才能保证函数调用完不会销毁  因为在内存malloc开辟的空间 才可以一直使用 变成自己的   我们通过几组图片 一次对应上方代码  就会很容易理解 

对于修改结点  多了一个少一个这种情况  还需要具体函数  实现具体功能  也就是说  传个二级指针   只是为了在以后实现链表多了一个少了一个问题的基础上  能够合理实现  不至于功能是写的挺好  但是没用到地方  就是传地址挺重要的  为了真正实现功能  

SLTNode* BuySLTNode(SLTDataType x)
{
    assert(pphead);
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
}
void  SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = nnewnode;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail ->next=newnode;
	}
}

1.2.3链表尾插代码解析

tail = tail->newnode;

找尾的特征  是tail->next == NULL

newnode是指针变量 存的是结点的地址

尾插的实质是：尾插的结点要存储新的结点的地址

对于

if (*pphead == NULL)
    {
        *pphead = nnewnode;
    }
    else
    {
        //找尾
        SLTNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
     tail ->next=newnode;
    
    }
}   

else以下代码 意思是  如果tail的下一个结点不能空  就一直找下一个结点 直到下一个结点为空  由于要改变结构体 就用结构体的指针  指向newnode 根据图片可知 也不需要利用二级指针   为什么不要改变tail的类型 就是因为该函数的调用 对于实参和形参的改变没有影响 以至于出了作用域销毁 对于链表没有什么影响  只能说函数想要实现的内容不同 要根据具体情况具体分析  最主要和和上面的区别 对于改变谁要搞清楚  上面是改变SLTNode*    就要用SLTNode**的指针接收  改变的是整个链表 这个改变的是newnode

*ppead就是plist的地址 

1.3、链表的头插

void SLTPushFront(SLTNode**pphead,SLTDataType x)
{
    assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnide->next = *pphead;
	*pphead = newnode;
}

  为空插入是合理的就不用断言   传的是二级指针 解引用是原先传进来的那个一级指针的地址 

1.4、链表的尾删

void SLTPopBack(SLTNode** pphead)
{
	//暴力检查
    assert(pphead);
	assert(*pphead);

	//只有一个结点  
	//多个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail -> tail->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

 注意

错误代码如下

void SLTPopBack(SLTNode** pphead)
{
	//暴力检查
    assert(pphead);
	assert(*pphead);

	//只有一个结点  
	//多个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		free(tail);
		tail NULL;
	}
}

这种代码插入时就会出现下图的情况 

说明 由于释放掉了  前一个结点的next变成野指针  由于释放掉了   通过调试我们也可以发现问题  应该释放tail->next->next  ;避免把前一个结点变成野指针

 

正确写法是找了一个假的尾  避免了空指针的问题

还应该注意链表为空的情况  如果删除一个数据就不合理 所以需要断言  但是 为空插入是合理的就不用断言

 1.5、链表的头删

SLTNode* SLTPopFront(SLTNode** pphead)
{
    assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

1.6、链表的查找（修改）

void SLTFind(SLTNode* phead, SLTSDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


1.7、链表在pos位置之前插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	//找到pos前一个位置
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

  

注意

 默认pos能找到 找不到则出现空指针问题  

pphead是plist的地址  地址不能为空  需要断言

plist 可能为NULL

pphead一定不是NULL

所以pphead需要断言  防止不小心传错 数据结构这段期间的断言与C语言有所不同 要具体问题具体分析    最重要的问题是  空链表可以打印 刻印插入 无需断言 

空链表不能删除所以需要

assert（*pphead）

1.8、链表在pos位置之后删除

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到pos前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
        //pos=NULL;
	}
}

这里的pos=NULL;由于形参的改变 对于实参没有影响  以至于 不需要  其实也可以传SLTNode**pos; 但是形式上不美观  可以在操作的时候 在将其置空 

1.9、链表在pos位置之后插入

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

 

1.10、链表在pos位置删除

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

四、完整代码 

 SList.h  SList.c text.c   

//SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
void SLTPopBack(SLTNode** PPhead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTEraseAfter(SLTNode* pos);
//SList.c
#define _CRT_SECURE_NO_WARNINGS 
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while(cur->next!=NULL)
	//while(cur!=NULL)
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
}
void  SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next=newnode;
	}
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
	//暴力检查
	assert(*pphead);
	//只有一个结点  
	//多个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	assert(pphead);
	
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	//找到pos前一个位置
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		//找到pos前一个位置
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//pos位置后面删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}
//text.c
#define _CRT_SECURE_NO_WARNINGS 
#include"SList.h"
void TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	printf("链表的尾插\n");
	SLTPrint(plist);
	SLTPushFront(&plist, 8);
	printf("链表的头插\n");
	SLTPrint(plist);
	SLTPopFront(&plist);
	printf("链表的头删\n");
	SLTPrint(plist);
	SLTPopBack(&plist);
	printf("链表的尾删\n");
	SLTPrint(plist);
	// 值为2那个节点  *2
	SLTNode* ret = SLTFind(plist, 2);
	ret->data *= 8;
	printf("链表的查找并修改\n");
	SLTPrint(plist);
	SLTInsert(&plist, ret, 66);
	printf("链表的某位置之前插入\n");
	SLTPrint(plist);

	SLTInsertAfter(ret, 88);
	printf("链表的某位置之后插入\n");
	SLTPrint(plist);
	SLTEraseAfter(ret);
	printf("链表的某位置之后删除\n");
	SLTPrint(plist);
	SLTErase(&plist, ret);
	ret = NULL;
	printf("链表的某位删除\n");
	SLTPrint(plist);
 }
int main()
{
	TestSList1();
	return 0;
}

五、运行结果 

 谢谢观看  


http://www.kler.cn/a/386485.html

相关文章：

  • 01-Ajax入门与axios使用、URL知识
  • FFmpeg 4.3 音视频-多路H265监控录放C++开发十三：将AVFrame转换成AVPacket。视频编码原理.编码相关api
  • Java项目实战II基于微信小程序的个人行政复议在线预约系统微信小程序（开发文档+数据库+源码）
  • ISAAC SIM踩坑记录--ubuntu 22.04操作系统安装
  • 第三十六章 Vue之路由重定向/404页面设置/路径模式设置
  • Stable Diffusion：照片转视频插件
  • 论文阅读《机器人状态估计中的李群》
  • 理解鸿蒙app 开发中的 context
  • Centos 网络接口打vlan标签
  • 三周精通FastAPI：38 针对不同的编程语言来生成客户端
  • 『事善能』MySQL基础 — 2.MySQL 5.7安装（一）
  • 玩的花，云产品也能拼团了！！！
  • typescript 补充
  • Spring Boot技术在导师双选系统中的应用
  • uniapp中使用全局样式文件引入的三种方式
  • 高德地图通过经纬度查找位置和轨迹回放
  • Uboot移植
  • 题解：AtCoder Beginner Contest AT_abc379_d ABC379D Home Garden
  • SpringBoot在线教育系统：数据分析与报告
  • IO同步异步/阻塞非阻塞
  • Flutter中的Extension关键字
  • 桥接 设计模式 软考
  • BIM 地铁站智能可视化应用
  • 简单介绍Nginx服务器的反向代理、负载均衡
  • 小柯剧场“真人秀”：如何玩转情感与竞技的双重游戏？
  • 学习记录：js算法（八十九）：电话号码的字母组合