一些建筑设计网站,网站的控制面板,网站推广服务外包有哪些渠道,seo推广的步骤这里比较的是基于C语言实现的顺序表与单链表#xff0c;与其他语言的实现可能会有差异#xff0c;但我相信语言是相通的#xff0c;它们的实现机制应该也差不多。 1、What 什么是顺序表和单链表 ①顺序表#xff1a; 顺序表是在计算机内存中以数组的形式保存的线性表与其他语言的实现可能会有差异但我相信语言是相通的它们的实现机制应该也差不多。 1、What 什么是顺序表和单链表 ①顺序表 顺序表是在计算机内存中以数组的形式保存的线性表是指用一组地址连续的存储单元依次存储数据元素的线性结构。只要确定了起始位置表中任一元素的地址都通过下列公式得到LOCaiLOCa1i-1*L 1≤i≤n 其中L是元素占用存储单元的长度。 ②单链表 单链表是一种链式存取的数据结构用一组地址任意的存储单元存放线性表中的数据元素。它的数据是以结点类型一般为结构体来表示的每个结点的构成数据类型为要存储的数据的类型 指针结构体指针数据就是链表里具体要存储的东西指针就是用来把每个节点都连接起来使它们形成一个链状。
结点
链表 2、Compare 二者的优缺点比较
①空间上的比较Space a. 空间的开辟 顺序表的实现一般是实现连续开辟一段空间然后在进行数据的增删查改静态顺序表所以顺序表一般是固定空间大小的而单链表则是一次只开辟一个结点的空间用来存储当前要保存的数据及指向下一个结点或NULL的指针所以单链表的空间大小时动态变化的。当然顺序表也可以在初始化时利用malloc函数来开辟一块空间每当空间不够用时再用realloc来把当前空间扩容成2倍从而也能实现空间的动态变化动态顺序表。 、 b. 空间的使用 当我们不知道要存储多少数据时用顺序表来开辟的空间如果太大就会造成一定程度上的浪费而用单链表是实现时因为是每需要存储一个数据时才开辟一个空间虽然有非数据项的指针占空间但相比顺序表来说浪费不是那么明显反之当我们知道存储的数据的数量时用顺序表来开辟对应的空间大小来存储数据因为顺序表中每个元素的存储密度为 1就完全不会有浪费的空间而用单链表因为每个结点都会有非数据项得指针那么就会造成空间的浪费。再者编译器会为每个程序从内存上分配一段空间给该程序使用。然而我们每次开辟空间时都是在随机的位置开辟的那么使用单链表就会多次的在程序分配到的这块空间上开辟空间因为每次都是开辟的位置都是随机的那么可能会把这块空间搞得七零八碎出现很多小的一般使用不到的碎片空间这样很大程度上造成了空间的浪费而使用顺序表的话不会经常开辟空间这样就减少了碎片空间的出现那么就一定程度上节省了空间。 c. 对CPU高速缓存的影响 因为顺序表的空间一般是连续开辟的而且一次会开辟存储多个元素的空间所以在使用顺序表时可以一次把多个数据写入高速缓存再写入主存顺序表的CPU高速缓存效率更高且CPU流水线也不会总是被打断而单链表是每需要存储一个数据才开辟一次空间所以每个数据存储时都要单独的写入高速缓存区再写入主存这样就造成了单链表CPU高速缓存效率低且CPU流水线会经常被打断。
从这儿看貌似顺序表要更好一些真是如此吗继续看下去。
②时间上的比较Time
a. 访问随机元素的时间复杂度 因为顺序表的结构就像是数组一样可以用下标来访问它的元素所以它的元素是支持随机访问的相比之下单链表的数据是链式存储的它的元素是不支持随机访问的想要知道某个元素只能从头结点开始遍历整个链表知道找到了该元素为止。因此顺序表访问随机元素的时间复杂度是O1而单链表访问随机元素的平均时间复杂度是On。
b. 随机位置插入、删除元素的时间复杂度 因为顺序表的元素是连续存储的因此要在特定位置插入、删除元素需要把它之后的元素全部后移或前移一个元素的位置时间开销很大而单链表在插入或删除元素时只需要改变它的前驱元素及插入或删除元素的指向即可。因此顺序表在插入随机位置插入、删除元素的平均时间复杂度是On单链表在插入随机位置插入、删除元素的时间复杂度是O1。
一般来说线性表顺序表和单链表都属于线性表的插入删除操作会被执行的频繁一些因此使用单链表的频率较大。
3、Summary
综合上述所言顺序表和单链表各有各的优缺点使用哪一种会好一些要结合具体的问题而言不能一概而论。 比如 在查询操作使用的比较频繁时使用顺序表会好一些在插入、删除操作使用的比较频繁时使用单链表会好一些。
PS使用顺序表和链表都必须满足每个元素占有相同大小的内存空间并且这个大小是固定的
