无序列表

发布时间:2019-07-09 作者:大扑棱蛾子 阅读次数:
版权声明:未经允许不得转载至微信公众号,转载至个人博客请注明出处。 阅读原文

无序列表的性质

无序列表
无序列表是项的线性集合,各项的相对位置之间彼此无关。

与顺序无关,各项都为独立个体。顺序的改变对列表无影响。无序列表的顺序是物理顺序,即各项添加的先后顺序。这个顺序与列表内数据没有任何意义。

操作 说明
Append 在列表的末尾添加一项
Enumerate 逐项检查所有列表项
Remove 从列表中删除指定项
Contains 搜索列表以便确定它是否包含指定项

顺序搜索

顺序搜索
把一个目标一次地与列表中的每一项比较。如果目标与某一项匹配,那么这个搜索成功。如果没有发现匹配,那么这一搜索失败。

假设一个列表中有nn个元素(项),搜索最好的情况就是11,第一个就是要找的元素,最坏的情况是nn直到最后一个才找到,或列表中不包含要查找的元素。
平均比较次数是多少?直觉告诉你是n2\displaystyle\frac{n}{2},另一种猜测是n+12\displaystyle\frac{n+1}{2}

平均分布情况

搜索的平均比较次数/
在一个数据结构中搜索一个元素所需的平均比较次数。

可利用求和公式算平均值,假设每个次数出现的概率是相等的。也就是每个元素被搜索到的概率是相等的,都为1n\displaystyle\frac{1}{n}\:

总次数S=n(n+1)2avg(S)=Sn=n+12\text{总次数}\: S = \frac{n(n+1)}{2},avg(S) = \frac{S}{n}=\frac{n+1}{2}

一个不符合假设的例子。假设维护一个7个元素的列表,且每个元素有如下所示的非平均搜索概率分布。

元素编号1234567312861715256比较次数1234567搜索概率1711412111412147121\begin{array}{rrrrrrrr} \text{元素编号}&1 & 2 & 3 & 4 & 5 & 6 & 7\\ &\longrightarrow\boxed3&\to\boxed{12}&\to\boxed{86}&\to\boxed{17}&\to\boxed{15}&\to\boxed{25}&\to\boxed{6}\\ \\ \text{比较次数}&1 & 2 & 3 & 4 & 5 & 6 & 7\\ \\ \text{搜索概率}&\displaystyle\frac{1}{7} & \displaystyle\frac{1}{14} & \displaystyle\frac{1}{21} &\displaystyle \frac{1}{14} & \displaystyle\frac{1}{21} & \displaystyle\frac{4}{7} &\displaystyle \frac{1}{21}\\ \end{array}

平均次数的计算如下:

1×17+2×114+3×121+4×114+5×121+6×47+7×121=9921=4.71 \times\frac{1}{7} + 2 \times\frac{1}{14} + 3 \times\frac{1}{21} + 4 \times\frac{1}{14} + 5 \times\frac{1}{21} + 6 \times\frac{4}{7} + 7 \times\frac{1}{21} = \frac{99}{21} = 4.7

带概率搜索的平均比较次数
设数据结构包含nn个元素,且搜索元素ii的概率是PiP_i。假设给定的搜索算法成功搜索到元素ii需要CiC_i次比较。那么,成功搜索到任意元素所需的平均比较次数是:

P1×C1+P2×C2+...+Pn×CnP_1\times{C_1}+P_2\times{C_2}+...+P_n\times{C_n}

如果假设有相同的搜索概率,那么PiP_i等于1n\displaystyle\frac{1}{n}。对于无序列表上的顺序搜索,平均比较次数是n+12\displaystyle\frac{n+1}{2}。

基于搜索概率的数据重排列

如果基于搜索概率递降地从第一个位置到最后一个位置排列元素的话,那么可以花费最少的平均比较次数成本。

数据的重排列
当一个列表的各项从头到尾都是按搜索概率递降顺序排列时,在所得列表中搜索的平均比较次数最少。

在运用搜索的新情况或者搜索模式不稳定的情况下,存在于搜索过程中动态地运用的简单技术。如果对列表中的元素xx做了搜索,那么在找到这个元素之后,把它移到列表的前头。因此,被搜索的频率越高的项越靠近列表的前端。这种移项到前端(move-to-front)方案在实践中很好用,而且也很容易实现。

List

运行时间

方法 描述 运行时间
add(T item) 把指定项添加到列表的末尾 O(1)O(1)
size() 获取元素数量 O(1)O(1)
isEmpty() 是否为空 O(1)O(1)
get(int index) 获取第i个元素 O(1)O(1)
contains(T item) 是否包含指定元素 O(n)O(n)
clear() 清空列表 O(1)O(1)
remove(T item) 移除第一个出现的给定的元素 O(n)O(n)
removeAll(T item) 移除所有给定的元素 O(n)O(n)
first() 第一个元素 O(1)O(1)
next() 下一个元素 O(1)O(1)
对象的关键字部分
对象的关键字部分是用作与另一对象比较是,看是否相等的依据的部分。

链表

数据 链接面包next牛奶next黄油next蜂蜜end\text{数据 \quad 链接}\\ \Rightarrow\boxed{\text{面包}}\boxed{next}\longrightarrow\boxed{\text{牛奶}}\boxed{next}\longrightarrow\boxed{\text{黄油}}\boxed{next}\longrightarrow\boxed{\text{蜂蜜}}\boxed{end}

链表
链表是由节点组成的线性结构。每个节点有保存客户提供的信息的数据部分和一个指向列表下一个节点的链接。

链接把内存区域中没有关联的节点捆绑在一起,提供表观邻接

循环链表
循环链表是一个链表,其中最后的节点返回来指向第一项。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×