1.顺序表的定义
顺序表--用顺序存储的方式实现线性表,把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中.
2.顺序表的实现--静态分配
2.1 顺序表的定义
#define MaxSize 10
typedef struct {
int data[MaxSize];
int length;
}SqList;
int main()
{
SqList L;
}
2.2 顺序表的初始化
- 初始化顺序表传入顺序表的地址
- 通过循环把全部数据元素置为初始值(0)
- 设置顺序表初始长度为0
下面演示由C语言实现
void InitList(SqList &L)
{
for(int i=0;i<MaxSize;i++)
{
L.data[i]=0;
}
L.length=0;
}
int main()
{
SqList L;
InitList(L);
}
2.3 顺序表的插入
在第i个元素后插入元素值为e的元素
- 把原先的第i个元素及之后的元素向后移动一位
- 更新第i个元素(即下标为i-1)为新的元素值
- 表的长度+1
void ListInsert(SqList &L,int i,int e){
for(int j=L.length;j>=i;j--)
{
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
}
int main()
{
SqList L;
InitList(L);
ListInsert(L,3,3);
}
加上一些范围判断,让插入操作更严谨(用bool类型)
- 判断i的范围是否有效,不能小于1,也不能插入最后一个元素的下下一个
- 储存空间也不能满,才能插入
bool ListInsert(SqList &L,int i,int e){
if(i<1||i>L.length+1)
return false;
if(L.length+1>MaxSize)
return false;
for(int j=L.length;j>=i;j--)
{
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;
L.length++;
return true;
}
2.4 顺序表的删除
删除第i个元素
- 将第i+1个元素及之后的元素前移一位,把删除的元素覆盖掉
- 注意删除元素的值用引用e带回来
bool ListDelete(SqList &L,int i,int &e){
if(i<1||i>L.length+1)
return false;
e=L.data[i-1];
for(int j=i;j<L.length;j++)
{
L.data[j-1]=L.data[j];
}
L.length--;
return true;
}
int e=-1; //用来接收删除的值
if (ListDelete(L,3,e))
printf("已删除第3个元素,删除元素值为=%d\n" , e);
else
printf( "位序i不合法，删除失败\n" );
2.5 顺序表的按值查找和按位查找
- 按位查找:找第几个元素
- 按值查找,从头到尾循环一遍
按位查找
int GetElem(SqList L,int i){
return L.data[i-1];
}
按值查找
int LocateElem(SqList L,int e)
{
for(int i=0;i<L.length;i++)
{
if(L.data[i]==e)
{
return i+1; //下标是i,是第i+1个元素
}
}
return 0;
}
3.顺序表的实现--动态分配
MaxSize通过输入动态的调整
注意:在王道中动态存储顺序表写的SeqList,我这里统一写成SqList
3.1 顺序表的定义
动态分配内存使用指针指向数据
#define InitSize 10
typedef struct {
int *data;
int MaxSize;
int length;
}SqList;
3.2 顺序表的初始化
void InitList(SqList &L)
{
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
int main()
{
SqList L;
InitList(L);
}
3.3 增加动态数组的长度
值得说明的,重新分配一个动态空间,原先那个动态空间不会消失,但是如果不记住它的地址,会找不到它.所以增加动态数组的长度,我们采取的方法是,用一个指针变量记住原先data动态数组的位置,重新分配一个新的增大的内存空间,然后将原先的数据复制到新的空间里,再释放掉原先的空间.
void IncreaseSize(SqList &L,int len) //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];
}
L.MaxSize=L.MaxSize+len;
free(p); //释放原先的空间
}
int main()
{
SqList L;
InitList(L);
IncreaseSize(L,10);
}
3.4 删除插入按位查找按值查找操作
和静态数组基本上一致
4.顺序表的特点
- 随机访问,即可以在O(1)时间内找到第i个元素
- 存储密度高,每个节点只存储数据元素
- 拓展容量不方便(即使采用动态分配的方式实现,拓展长度复杂度也比较高
- 插入和删除操作不方便,需要移动大量元素
