数据结构顺序表链表的操作

《数据结构》顺序表、链表的操作<复杂度>判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注最高项目、的阶数。推导大O阶方法：1、用常数1取代运行时间中的所有加法常数2、在修改后的运行次数函数中，只保留最高阶项3、如果最高阶项存在且不是1，则去除系数O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)口诀：常对幂指阶<线性表>由零个或多个数据元素组成的有限序列1、首先它是一个序列，有前后关系2、若元素存在多个，第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继抽象的数据类型就是把数据类型和相关操作捆绑在一起OperationInitList(*L)初始化建立一个空的线性表LListEmpty(L)判断是否为空表，是返回true，否返回falseClearList(*L)清空线性表GetElem(L,i,*e)将线性表L中更多第i个位置元素值返回给eLocateElem(L,e)在线性表L当中查找与给定值e相等的元素ListInsert(*L,i,e)在L的第i个位置插入新元素eListDelete(*L,i,*e)删除L中第i个位置元素，并用e返回其值ListLength(L)返回L的元素个数<顺序存储结构封装需要三个属性>1、存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置2、线性表的最大存储容量：数组长度MaxSize线性表的当前长度：length<顺序表的实现-静态分配><关于typedef>1、相当于给自定义的数据结构取个昵称…<关于插入>1、首先进行判断i的范围，注意i>L.length+1这一句实际上是在检测是否插入的数据能使顺序表是连续的（比如原表在1-5位有数据了，但是在插入时要求在第7位插入，这是不合理的）2、难点在于位次序是从1开始的，而数组的存储是从0开始的<其他>1、感觉没啥好总结的，虽然这个代码写了好一会，但是感觉最大的困难就是上面的图片了2、感觉这一次写的代码起以往来说交互性更好了3、源码指路github（全部贴上来真的太长啦……）/Sherlock-White/Learning-note/tree/DataStructure<malloc和new的区别>1、new从自由存储区分配内存，而malloc从堆分配内存。自由存储区能否是堆，取决于operatornew的实现细节。2、new分配内存成功时，返回的是一个与对象类型严格匹配的指针，符合类型安全性；而malloc分配成功返回void*，需要进行强制类型转换。3、new分配内存失败时，会抛出bac_alloc异常；而malloc会返回NULL那么对new失败应该使用try-catch的异常机制4、new无需指定内存块的大小，编译器会完成的；malloc需要指出（利用sizeof）5、new会调用对象的构造函数/析构函数，而malloc不会6、new的实现可以基于malloc，反之不可以7、new允许被重载，malloc不行new不能扩容，而malloc可以用realloc原地扩大/ywliao/articles/8116622.html<malloc>1、进行malloc的时候要进行强制类型转化，并且要显式说明分配的内存大小2、建议用memset或者是别的方法对脏数据进行处理3、下面的博客界面真香啊，javascript马上学qaqq/ybqjymy/p/12365716.html<单链表>1、一个技巧是可以将结构体命名为两个形式，一个是LNode，另一个是*LinkList，在书写的过程中，前者更强调是一个指针，后者更强调是一个单链表，可以增强代码的可读性2、千万别在里面放string，char真的很香3、带头结点的单链表思路是在main当中声明一个listPoint*类型的指针L作为头结点，然后对其初始化，接着调用insert函数将元素插入4、遍历的核心就是用一个临时的指针p去指向头结点L，用p=p->next实现遍历，难点是边界条件的判定5、在释放内存的时候，同样是用一个p去遍历，因为我们要释放的只有malloc的内存，所以从头结点走到NULL的时候应该可以把内存放干净<其他>1