线性表嘛，算是数据结构里最基础的东西了。而顺序表，说白了，就是用一段连续的内存空间，按顺序存放数据元素。这么一说好像很简单，但是，这连续存储的特性，决定了它的很多行为，也影响了我们如何高效地使用它。尤其是元素的存储地址，更是重中之重，理解透彻了，对性能优化非常有帮助。
想象一下，你手里拿着一串钥匙，每把钥匙对应着一个房间。顺序表就像这串钥匙，而每个数据元素，就是那些房间。钥匙是按顺序排列的，房间号也是连续的。如果你想找到第5个房间，直接从头数5下就行了。
在计算机里，这个“数5下”的过程，就是通过计算元素的存储地址来实现的。每个元素都占据一定的内存空间，比如一个整数可能占4个字节。假设顺序表的起始地址是baseAddress，每个元素占size个字节，那么第i个元素的地址就是：baseAddress + (i – 1) * size。注意这里索引是从1开始算的哈。
这个公式看上去很简单，但它揭示了顺序表的一个关键优势：随机访问。只要知道了索引，就可以直接算出元素的地址，不需要像链表那样，一个一个节点地遍历。所以，如果你需要频繁地根据索引来访问元素，顺序表绝对是首选。
不过，这个“连续”的特性，也给顺序表带来了一些麻烦。比如，插入和删除操作。如果你想在顺序表的中间插入一个元素，就必须把后面的所有元素都往后移动一位，腾出空间。同理，删除一个元素，也要把后面的元素都往前移动一位，填补空缺。
想想就很麻烦，对吧？尤其是当顺序表很大的时候，这个移动的代价就非常高了。这也就是为什么顺序表的插入和删除操作的时间复杂度是O(n)，而链表只需要O(1)。
但是，我们也不是没有办法来优化顺序表的插入和删除操作。
一个方法是，我们可以预先分配更大的内存空间。也就是说，顺序表的容量可以大于实际存储的元素个数。这样，在插入元素的时候，如果还有空余空间，就不需要移动元素了。当然，这个方法也有缺点，就是会浪费一些内存空间。
另外一个方法是，我们可以采用一些特殊的技巧来优化插入和删除操作。比如，我们可以使用“懒删除”策略，也就是在删除元素的时候，并不真正地删除它，而是把它标记为已删除。这样，插入元素的时候，就可以直接覆盖这些被标记为已删除的元素，而不需要移动其他元素。
还有，关于顺序表的元素存储地址，其实还有一个很重要的概念，就是内存对齐。
内存对齐是为了提高CPU的访问效率。CPU在访问内存的时候，通常会按照一定的粒度来读取数据，比如4个字节或者8个字节。如果数据没有按照这个粒度对齐，CPU就需要进行多次读取才能获取完整的数据，这会降低访问效率。
所以，编译器通常会对数据进行内存对齐，保证每个数据的起始地址都是某个倍数。这个倍数通常是2的幂，比如4、8、16等等。
内存对齐会影响顺序表的存储空间大小。比如，如果一个结构体包含了多个不同类型的数据，那么编译器可能会在结构体内部插入一些填充字节，以保证结构体的大小是某个倍数的。这些填充字节会浪费一些存储空间，但可以提高CPU的访问效率。
在设计顺序表的时候，我们需要考虑到内存对齐的问题，尽量减少填充字节的浪费。一个方法是，我们可以按照数据类型的大小，从小到大排列结构体中的成员变量。这样可以减少填充字节的数量。
再说说我之前遇到的一个坑吧。当时我在用C++写一个图像处理的程序，用顺序表来存储图像的像素数据。图像很大，每个像素占3个字节（RGB）。结果程序跑起来速度非常慢。
后来我才发现，问题出在内存对齐上。因为每个像素占3个字节，不是4的倍数，所以编译器会在每个像素之间插入一个填充字节，导致顺序表的大小增加了1/4。这样不仅浪费了内存空间，还降低了CPU的访问效率。
解决这个问题的方法很简单，就是把像素的存储方式改为RGBA，也就是每个像素占4个字节。这样就避免了内存对齐的问题，程序的性能也得到了显著提升。
总之，顺序表虽然简单，但要用好它，也需要深入理解其底层原理，尤其是元素的存储地址、随机访问特性、以及内存对齐等概念。只有掌握了这些知识，才能写出高效、稳定的代码。别小看这些基础知识，它们往往决定了程序的性能上限。
发表回复