数据结构_单链表-1.23

学习内容

一. 1.19

移除一个元素，删掉重复元素

思路：采用两个下标，一个下标遍历数组，一个下标辨别特殊情况的发生，并将特殊情况的数据结果保存起来。
问题：我用的只有num[i], 其空间复杂度是O(N)，满足题目要求，但是结果就是在oj里栈溢出了。可能它默认有时间复杂 度的限制。
解答：是内存出问题，因为你没有考虑空数组的情况，要先判断输入为空的情况下才行。

C++简介

C++近似=C语言+面向对象+通用编程。

书里说学C++要忘掉写C的一些习惯（我C都不精通呢？还能学C++忘掉C？）
如果你没有学过C，就不用忘记（笑傲江湖的吸星大法散内功？）
书里还说，C++比C不是多学几个关键词那么简单，有很多其它的东西。
（之前我一直觉得C++是C的一种进阶，现在看来几乎可以看作两种不同的语言了）

二. 1.22

链表

链表是逻辑上连续的数据结构。为实现顺序表难以实现的功能而生。

1.顺序表优缺点

优点：
1）可访问你想访问的位置（物理地址上的连续，简单的加减数字即可达到你所要的地址）
2）缓存命中率高（读数据先读缓存中的，缓存里有编译器要的数据就算命中，没有，则去内存里面取数据）
预加载：访问一个数据会把数据那一段都从内存放进缓存里，顺序表是连续的，有效数据存进缓存的概率就高。
缺点：
1）复杂度摆在那，O(N)，插入删除都要挪动整个数组。
2）指数增的扩容很容易就造成资源浪费（这算法没网络阻塞控制的转为加法增好，可具体算法也算顺序表的缺点？不敢苟同，我在超过一万的时候翻倍两万浪费了，下次遇到一万的时候，我加一千不行？我加一百不行？浪费微乎极微。）（虽然相比链表那种，确实是浪费了）

2.尝试先自己写的单链表增删

https://download.csdn.net/download/weixin_48278060/88771732

3.遇到的问题

1.如果确定第一个链表结点？

1）最开始的链表结构体中，我没定义长度len。我在开辟动态空间时，发现每次都会多开辟了一块空间，只要发现链表节点指向的下一个地址为NULL，就自动开辟一块空间（这里导致了一直多开了一个空间）
2）于是我想能不能用第一个链表的data值来确定？不行，如果data值本身就为0或者是你初始化的那个值呢？，之后我想能不能通过第一个链表的next值为NULL确定？还是行不通，因为你通过第一个链表next的值为NULL判断要在第一个链表输入数据，你的第二个链表空间怎么开辟（开辟第二个链表时，第一个链表的next也还是NULL）？
3）在链表结点加一给len搞定，len==1时，数据写在已有链表空间里，len>1,开辟新的空间。这也为之后的展示，提供了方便。

2.第一个链表的位置改变了，其长度len也需要跟着传过去

1）在对第一个链表操作时，比如加一个链表，这时就产生了一个新的首链表地址，这里我忘了讲原来链表中的len值传给这个新的首链表结点，在调试发现，len=8478788878类似这样的。
2）因为你新的首链表节点的len没有被初始化
3）总之，改变就把旧数据先传过来，别给丢了

3. 首链表的考虑情况不周

SListNode* SListPopFront(SListNode* pos)
{   
	assert(pos);
		SListNode* tmp = pos->next;
		//if (tmp == NULL)；
		tmp->len = --pos->len;
		return tmp;
};

调试时，一直遇到写入权限不行啥的，在网上查了下，是因为出现空指针的情况。恍然大悟，pos->next要是第一个链表结点不就是NULL？空指针，就要加个判断，是不是弹出第一个。

三. 1.23的一半

与参考代码的差距

1.找尾可以不用长度len（固化思维了）

我的：
while (cur != NULL)
			{
				store = cur;
				cur = cur->next;
			}
不用len找尾：
while (cur->next != NULL)
			{
				cur = cur->next;
			}

1)之前写了cur！=NULL，默认把它模块化使用了，才导致后来想半天没想明白怎么确定第一个或最后一个链表。
2）直接cur->next！=NULL判断是否有下一个链表，有就走。

2.main（）里面创建的是链表结点指针

我的：
	SListNode pos;
	SListInitial(&pos);
不用len：
	SListNode* pos=NULL;
	SListInitial(&pos);

需要用二级指针，传址才能修改。所以为什么不创建一个链表结点呢？
我能想到的是，指针就一个小变量，创建一个链表结点会固定一个内存空间？那我既然用了一个链表结点，我创建一个怎么了？你二级指针可以之后动态开辟内存，我这就固定开一个有区别吗？

3.pop用free（）

我的：
	pos->len--;
不用len：
	free(*pphead);
	*pphead=NULL;

直接释放的好，内存不能泄露吧。大问题，大问题。一个链表结点不用就释放了。

4.malloc（）没强制类型转换

我没转换为什么还能正常运行？看了别人文章，C环境下确实不用强制类型转换，单但C++要。
https://blog.csdn.net/qq_52959401/article/details/130218761

5.常加#pragma once