【数据结构与算法学习笔记】01 基本概念 搞要： 本文主要介绍数据结构与算法的基本概念，是本人的学习笔记。对于想学习数据结构与算法的读者，可以作为参考。 以C语言为主，有些地方与C++混合实现。 由于很多草稿图片都绘制在本子上，所以本系列笔记中很多地方并没有给出图片，如有需要读者可自行根据笔记内容绘制图片。 如有错误或者遗漏之处，欢迎指出。 目录： 1，基本概念 2，new和malloc的区别 3，数组回顾 1，基本概念 /* 数据->数据对象->数据素->数据项； 逻辑结构： 集合结构：数据之间没有关系； 线性结构：数据之间1：1； 树形结构：数据之间1：n； 图形结构：数据之间n：n； （前驱，后继） 物理结构： 顺序存储：地址连续，类似数组； 链式存储：地址不连续，用指针来存储，类似链表容器list； */ /* 算法特性： 输入输出：有0个或多个输入，至少要有一个或多个输出； 有穷性：有限步骤，不会出现无限循环，每一步都在可接受的时间内完成； 确定性：每一步都有确定的含义，无二义性； 可行性：每一步必须是可行的，可通过 有限次数完成； 算法设计要求： 正确性： 没有语法错误； 对于合法的输入产生正确的输出结果； 对于非法的输入得出满足规格说明的结果； 对于精心选择的、刁难的数据有满足要求的输出结果； 可读性； 健壮性：输入不合法数据时，能做出相关处理，不会产生异常或奇怪的结果； 时间效率高且存储量低； 时间复杂度： T(n) = O(f(n))，只看最高阶； n为输入规模，f(n)为执行次数，T(n)为时间复杂度； O(1)<O(logn)<O(nlogn)<O(n^2)<O(n^3)<O(n!)<O(n^n)； 空间复杂度：S(n) = O(f(n))； */ 2，new和malloc的区别 /* 0. 属性 new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持。 1. 参数 使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算。 而malloc则需要显式地指出所需内存的尺寸。 2. 返回类型 new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符。 而malloc内存分配成功则是返回void * ，需要通过强制类型转换将void*指针转换成我们需要的类型。 3. 分配失败 new内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL。 4. 自定义类型 new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。 然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。 delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。 malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构工作。 5. 重载 C++允许重载new/delete操作符，特别的，布局new的就不需要为对象分配内存，而是指定了一个地址作为内存起始区域， new在这段内存上为对象调用构造函数完成初始化工作，并返回此地址。 而malloc不允许重载。 6. 内存区域 new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。 自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。 而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存， 使用free释放已分配的对应内存。自由存储区不等于堆，如上所述，布局new就可以不位于堆中。 */ 3，数组回顾 //by CODspielen
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/78363.html
