的？)
顺序表是一种简单的数据结构在学习时我们接收到的一个有关它的信息是顺序表的查找时间复杂度是O(1)。但是计算机要查找数据是一个一个来的它不像人一样可以用“瞪眼法”这其实也是一个一个来的一下子看到数据的所在位置那么它是如何实现如此高效的查找的呢答案是当我们给顺序表一个位置 pos让它返回顺序表中这个位置的数据它可以直接跑到这个位置并不会一个一个地找数据直到 pos 位置。计算机的寻址逻辑想要理解顺序表是如何做到的我们先来看看计算机的寻址逻辑是什么样的。我们常说这个电脑是 32 位的那个电脑是 64 位的这个多少位其实代表的是这台电脑有多少根地址线32 位的电脑就有 32 根地址线 64 位同理。现在大部分电脑都是 64 位的了但是为了讲解方便这里选择用 32 位的来解释64 位的逻辑也是一样的。一根地址线可以有 0 或 1 状态那么 32 根地址线就有 2^32 种状态也就是 32 个 bit 位对应 4 字节也就是我们说 32 位的情况下C 语言指针的大小是 4 字节的原因。这个地址线就是计算机用来查找数据的指针存放的其实就是地址线的状态。假如一个数据存放的内存地址是 0xffffffff 32 根地址线十六进制下每四根地址线为一位即 四个bit位对应一个十六进制位那么计算机通过指针获取这个地址直接就在内存中找到了这个数据。指针理解深化通常情况下我们讲指针其实讲的是 “指针变量” 这个变量里面存放的是 地址 。说到底它也是一种数据这也说明了多级指针并不是什么高深的东西其实就是用一个指针变量存储另一个指针变量的地址以此类推可以无限套娃。好了既然知道指针里面存放的其实也是数据那么可以对他进行运算吗答案是当然可以。两个指针指向同一块连续数组时指针与指针相减有意义得到元素个数两个指针相加无意义参考日期相加也可以用 指针 /- 整数让指针 往前/往后 移动这个移动多少的整数叫做偏移量。最终解释现在想必你已经明白顺序表是如何实现O(1)的查找效率的了。对于一张顺序表它的指针其实就是它首元素的地址。而顺序表的结构特点之一就是它的数据是连续存储的。当我们要查找其 pos 位置的值时虽然我们没有这个位置的相应指针但是只要让其指针 往后偏移 [ pos * 它的一个数据占用的字节]注意C 语言里写arr[pos]等价于*(arr pos)编译器自动帮你乘上单个元素的字节大小不用我们手动计算字节偏移。我们就可以获取到要找的数据的第一个字节的地址再根据数据大小进行解引用我们就得到了这个数据。至此顺序表的 pos 查找完成。顺序表也有一种通过 数据 找 pos 的查找方式这种情况下查找就需要我们对比每一个数据了故时间复杂度是 O(n)的。
