数据结构_单链表-1.23

发布时间:2024年01月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
文章来源:https://blog.csdn.net/weixin_48278060/article/details/135740423
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。