- 知识点
|
- 顺序表的定义
顺序表——用顺序存储的方式实现线性表顺序存储。
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
线性表L的逻辑结构：
|
线性表的顺序存储：
|
- 顺序表的实现--静态分配法
给各个数据元素一次性分配连续的存储空间，大小为MaxSize*sizeof(ElemType)
/*定义最大长度*/
#define MaxSize 10
/*顺序表的类型定义*/
typedef struct{
/*静态数组存放元素*/
int data[MaxSize];
/*顺序表的当前长度*/
int length;
}SqList;
/*初始化顺序表*/
void InitList(SqList &L)
{
/*将所有数据元素设置为默认值0*/
for(int i=0;i<MaxSize;i++)
L.data[i]=0;
/*将顺序表的初始长度设置为0*/
L.length=0;
}
顺序表的表长刚开始确定后就无法更改；存储空间是静态的 ；当数据存满后将不能再存放新的数据；
如果刚开始就声明一个很大的空间，则会造成内存空间的浪费。
- 顺序表的实现--动态分配法
通过C语言的malloc、free 函数来动态申请和释放空间:
L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize); free(L.data);
malloc 函数返回一个指针， 需要强制转型为你定义的数据元素类型指针
/*默认的最大长度*/
#define InitSize 10
/*顺序表的类型定义*/
typedef struct{
/*指向动态分配数组的指针*/
int *data;
/*顺序表的最大长度*/
int MaxSize;
/*顺序表的当前长度*/
int length;
}SeqList;
void InitList(SeqList &L)
{
/*用malloc函数申请一片连续的内存空间*/
L.data=(int *)malloc(InitSize*sizeof(int));
/*设置顺序表的初始长度为0*/
L.length=0;
/*设置顺序表的最大长度*/
L.MaxSize=InitSize;
}
void IncreaseSize(SeqList &L,int len)
{
/*重新申请新的空间*/
int *p=L.data;
L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
/*将原来的数据复制到新的空间里*/
for(int i=0;i<L.length;i++)
L.data[i]=p[i];
/*顺序表的长度增加len*/
L.MaxSize=L.MaxSize+len;
/*释放原来的内存空间*/
free(p);
}
复制元素时，时间开销较大
- 顺序表的特点
①随机访问，即可以在 O(1) 时间内找到第 i 个元素。
②存储密度高，每个节点只存储数据元素
③拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
④插入、删除操作不方便，需要移动大量元素
|
