【数据结构】第二章小结

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>

                                2、、

                                       Sort函数包含在头文件为#include<algorithm>的c++标准库中
                                      Sort函数有三个参数:
                                   (1)第一个是要排序的数组的起始地址。
                                   (2)第二个是结束的地址(最后一位要排序的地址的下一地址)
                                   (3)第三个参数是排序的方法,可以是从大到小也可是从小到大,还可以不写第三个参数,此时默认的排序方法是从小到大排序。
                                              ps:如果要改变排序方法:需要加入一个比较函数compare(),如:
                          bool  compare( int  a, int  b)
                               {
                                  return  a>b;
                                }
 
                                   参考资料:https://baike.baidu.com/item/sort%E5%87%BD%E6%95%B0/11042699?fr=aladdin

                                                     https://www.cnblogs.com/argenbarbie/p/5266603.html    

三、接下来

当然是好好的打代码,与同学多多交流

相关文章
相关标签/搜索