【数据结构】第二章小结
|
副标题[/!--empirenews.page--]
ps：第一次用博客园写，记录第一次 一、数据结构第二章主要为：顺序表和链表的构造及其增删查改的一些基本操作，以及粗略计算它们的时间or空间的复杂度。 ? ? ? 1、顺序表： ? ? ? ? ? ? ? ? ? ? ? ? ?（1）? 特点：逻辑结构上相邻，物理存储上也是相邻的，属于随机存储； ? ? ? ? ? ? ? ? ? ? ? ? ?（2）? 优点：便于使用下标进行查找，例如：查找某数组的第6项的数据是几； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?存储密度为1； ? ? ? ? ? ? ? ? ? ? ? ? ?（3）? ? 缺点：由于其物理存储相邻，故无法将空间中零零散散的碎片空间利用起来； ? ? ? ? 2、链表： ? ? ? ? ? ? ? ? ? ? ? ? ?（1）? ?特点：逻辑结构上相邻，物理存储上不一定相邻的，属于顺序存储； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 单链表有头指针指向； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 含头结点的空表：L->next=NULL//（头结点的指针域为空） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 无头结点的空表：L==NULL//（L为单链表的头指针） ? ? ? ? ? ? ? ? ? ? ? ? ?（2）? ? 优点：可以充分利用碎片空间； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?可以便于增删--改变指针的指向； ? ? ? ? ? ? ? ? ? ? ? ? ?（3）? ? 缺点：存储密度小于1； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?需要为指针腾出空间； ? ? ? ? ?3、链表vs顺序表： ? ? ? ? ? ? ? ? ? ? ? ? ? （1）在增删工作为主的问题中，主要使用链表，时间复杂度较低； ? ? ? ? ? ? ? ? ? ? ? ? ? （2）在查询工作中，且使用下标查询为主的问题中，使用顺序表为好； ? ? ? ? ? ? ? ? ? ? ? ? ? （3）时间复杂度： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 顺序表： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?取值算法：O（1） 、 查找算法：O（n）、增加or删除算法：O（n） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?空间复杂度S（n）=O（1）? ? 均没有占用辅助空间； ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 链表： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?取值算法：O（n）、查找算法：O（n）、增加or删除算法：O（n） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?空间复杂度S（n）=O（1）? ? 均没有占用辅助空间； 二、做题过程中遇到的其他问题 1、心理上：上个学期c++打题过少，对于使用一些函数，指针类型的代码充满恐惧与抗拒，甚至于数组都有那么一点 2、现实中：书本给的代码不够详细，得自己上网搜代码 3、题目上：【1】new运算符的应用： ? ? ? ? ? ? ? ? ? ? （1）、开辟单变量地址空间 ? ? ? ? ? ? ? ? ? ? 指针在初始化时需要动态申请空间 int*a=new int [空间大小] 等同于int*a; a = new int [空间大小]， ? ? ? ? ? ? ? ? ? ?例如：int *a = new int(5) 作用同上,但是同时将整数赋值为5； ? ? ? ? ? ? ? ? ? ? （2）、开辟数组空间 ? ? ? ? ? ? ? ? ? ?要访问new所开辟的结构体空间,无法直接通过变量名进行，只能通过赋值的指针进行访问。 ? ? ? ? ? ? ? ? ? ? （3）、C++中使用new的注意事项： ? ? ? ? ? ? ? ? ? ? ? ?1、、用户是无法主动调用构造函数的，所以需要借助placement new，但是用户可以主动调用析构函数，所以用完这些对象后，调用析构函数，然后用对应分配内存的方法去释放内存。 ? ? ? ? ? ? ? ? ? ? ? ?2、、事实上malloc并不一定比operatornew节省多少时间，用placement new常常是为了考虑性能，所以会配合内存池一起使用。 （ps：?内存池(Memory Pool)是一种内存分配方式。通常我们习惯直接使用new、malloc等API申请分配内存，这样做的缺点在于：由于所申请内存块的大小不定，当频繁使用时会造成大量的内存碎片并进而降低性能。） ? ? ? ? ? ? ? ? ? ? ? ?补充：malloc的全称是memory allocation，中文叫动态内存分配，用于申请一块连续的指定大小的内存块区域以void*类型返回分配的内存区域地址，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存。 ? ? ? ? ? ? ? ? ? ? ? ? ?3、、new与malloc、operator new、placement new 的区别： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??从本质上来说，malloc（Linux上具体实现可以参考man malloc，glibc通过brk()&mmap()实现）是libc里面实现的一个函数，如果在source code中没有直接或者间接include过stdlib.h，那么gcc就会报出error：‘malloc’ was not declared in this scope。如果生成了目标文件（假定动态链接malloc），如果运行平台上没有libc（Linux平台，手动指定LD_LIBRARY_PATH到一个空目录即可），或者libc中没有malloc函数，那么会在运行时（Run-time）出错。new则不然，是c++的关键字，它本身不是函数。new不依赖于头文件，c++编译器就可以把new编译成目标代码（g++4.6.3会向目标中插入_Znwm这个函数，另外，编译器还会根据参数的类型，插入相应的构造函数）。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?在使用上，malloc 和 new 至少有两个不同: new 返回指定类型的指针，并且可以自动计算所需要大小。第一、malloc 函数返回的是 void * 类型。第二、函数的实参为 sizeof(int) ，用于指明一个整型数据需要的大小。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?....... ? ? ? ? ? ? ? ? ? ? ? ? ?（此后省略，直接放网址，因为发现越查越深入，待以后化成自己知识的时候再写几篇关于这些函数不同的博客） ? ? ? ? ? ? ? ? ? ? ?参考资料来源：https://zhidao.baidu.com/question/393285989.html（new的运算符的作用） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?https://baike.baidu.com/item/%E5%86%85%E5%AD%98%E6%B1%A0/8577153?fr=aladdin（内存池） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?https://baike.baidu.com/item/malloc%E5%87%BD%E6%95%B0/8582146?fr=aladdin（malloc函数（含有其与new的区别）） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?https://blog.csdn.net/caimagic/article/details/51493741（operator new与new的区别） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?https://blog.csdn.net/songchuwang1868/article/details/81353577（较为简单的解释了一下其区别：new、operator new、::new、placement new） ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?【2】关于sort函数的应用及其compare函数的机制： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1、、sort的定义：用于C++中，对给定区间所有元素进行排序。头文件是#include <algorithm> （编辑：济源站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
