数据结构——003顺序表

顺序表

定义： 是线性表的顺序存储表示。它用一组地址连续的存储单元，按照线性表中数据元素的顺序，依次存储线性表中的数据元素。实现了逻辑相邻转换成地址相邻。
特点：
①第i个元素存储在第i个物理位置（第i个地址代表的内存空间）（1≤i≤n）
②顺序表中的数据元素可以被顺序访问和随机访问。顺序访问是从第一个数据元素开始逐个访问；随机访问就是根据元素位置（下标）直接访问。

顺序表的存储：（C语言描述）

/*静态存储表示*/
#define maxSize 1000
typedef char DataType;
typedef struct
{
     DataType data[maxSize];
     int n;
}SeqList_V1;

/*动态存储表示*/
#define initSize 1000
typedef char DataType;
typedef struct
{
     DataType *data;
     int maxSize,n;
}SeqList_V2;
/*初始化分配主要语句*/
DataType *data = (DataType *)malloc(sizeof(DataType)*initSize)
maxSize = initSize ;
n = 0;

插入与删除运算

插入运算平均移动次数：
n/2 = (1/(n+1))×SUM(n+1-i),i=1,2,…,n+1
删除运算平均移动次数：
(n-1)/2 = (1/n)×SUM(n-i),i=1,2,…,n

顺序表的优点是存储密度高（存储利用率高）