guodong's blog

master@zhejiang university
   

算法3 数据结构

一:紧邻数据结构和链接数据结构

紧接:由许多相邻的内存块组合而成一体,比如数组,矩阵,堆,散列等

链接:分散内存各处,通过指针连接。列表,树,图的邻接表等

1、数组

优点:给定下标,能在常数范围内访问元素。节约空间。内存局部性,便于迭代。

不足:无法调节数组大小

solution:动态数组。每当面临空间耗尽时,使数组长度加倍。加倍过程中的步骤:首先按紧接方式分配一个2倍长度的新数组,其次将原数组的内容复制到新数组的前半部分,最后将原素组所占的空间退还给操作系统。

总共搬运次数

时间复杂度不高,而事先分配足够大的静态数组再逐个放入元素所需的时间也是这个量级

2、指针和链接结构

指针特性:每个节点都包含一个或多个数据域,保留着我们要储存的数据。每个节点至少包含一个指针域,指向下一节点而不是储存数据。还需要头部指针。

链表: 可以用来实现列表,支持三种最基本的操作,查找,插入,删除。在双链表中,还同时包含了指向前驱和后继指针,不过要以多储存一个指针元素为代价。

二:栈和队列




上一篇:
下一篇:

头像

guodong

没有评论


你先离开吧:)



发表评论

电子邮件地址不会被公开。 必填项已用*标注