今天复习了顺序表,顺序表是线性表的一种存储结构,它把线性表中的所有元素按照其逻辑顺序,依次存储到从计算机存储器中指定存储位置开始的一块连续的存储单元中。简单来说,就是用一组连续的内存单元来存放数据元素,数据元素之间的逻辑关系通过物理存储位置相邻来体现。
优点有:
随机访问效率高:由于元素存储在连续的内存单元中,因此可以通过数组下标快速定位到任意一个元素,时间复杂度为 。例如,对于一个顺序表 ,访问 可以直接通过计算内存地址快速获取元素值。存储密度高:顺序表中每个元素只存储自身的数据,没有额外的指针等辅助信息(与链表相比),所以存储密度大,能有效利用存储空间。
缺点有:
插入和删除操作效率低:在顺序表中插入或删除元素时,需要移动大量元素来保持顺序表的连续性。例如,在表头插入一个元素,需要将后面的所有元素依次向后移动一位,时间复杂度为 ,其中 是顺序表中元素的个数。
大小固定,灵活性差:在创建顺序表时需要预先分配一定大小的存储空间,如果后续数据量变化较大,可能会出现空间不足或浪费的情况。
基本操作有:
初始化:创建一个空的顺序表或指定大小的顺序表,并分配相应的内存空间。
插入:在顺序表的指定位置插入一个新元素,需要将插入位置之后的元素依次向后移动。
删除:删除顺序表中指定位置的元素,之后的元素依次向前移动。
查找:根据给定的元素值或位置信息,在顺序表中查找相应的元素。
修改:修改顺序表中指定位置的元素值。