0.本篇问题
- 什么是顺序表的位序,他和顺序表的下标有什么关系?
- 顺序表的优缺点?
- 动静态内存分配如何实现?
- 动静态的初始化如何实现?
- 插入操作有哪些参数?实现过程?时间复杂度?
- 删除操作实现了什么?有哪些参数?实现过程?时间复杂度?
- 按值查找操作实现了什么?有哪些参数?实现过程?时间复杂度?
- 随机存取?按位查找时间复杂度?
★错题
1.①“顺序表可以利用一维数组表示,因此顺序表与一维数组在逻辑结构上是相同的”(对or错)
②顺序表和一维数组一样,都可以进行随机存取。(对or错)
2.线性表的顺序存储结构是一种( )
A.随机存取的存储结构 B.顺序存取的存储结构
C.索引存取的存储结构 D.散列存取的存储结构
一、顺序表知识点
- ai 是顺序表中的第i个元素,i称为位序。(线性表中的元素的位序是从1开始的,而数组元素的下标是从0开始的)。
- 顺序表是一种支持随机存取的存储结构,根据起始地址加上元素的序号,可以很方便地访问任意一个元素,这就是随机存取的概念。
- 顺序表的优点:
二、顺序表的基本操作的实现
(本篇代码和王道考研书中的代码基本吻合,重在算法的思想,不要求代码具有可执行性。)
2.1 静态分配VS动态分配
2.1.1 静态分配
静态分配数组的大小和空间事先已经固定,顺序表会出现空间已满无法加入的情况。
//线性表最大长度
#define MaxSize 50
typedef struct {
ElemType data[MaxSize];
int length; //顺序表当前长度
}SqList;
2.1.2 动态分配
//表长度初始定义,满了动态扩容
#define MaxSize 50
typedef struct {
ElemType data[MaxSize];
//顺序表的容量和顺序表的长度
int MaxSize,length;
}SqList;
如果满了就扩容:
//C,最后可以不* InitSize,*2(二倍扩)...都是可以的
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
//C++
L.data = new ElemType[InitSize];
2.2 初始化
2.2.1 静态顺序表初始化
//声明一个顺序表
//SqList L;
void InitList(SqList& L) {
//顺序表的初始长度为0
L.length = 0;
}
2.2.2 动态顺序表初始化
void InitList(SqList& L) {
//为顺序表分配InitSize个空间
L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
L.length = 0;
L.MaxSize = InitSize;
}
2.3 插入操作
在顺序表L的第i个位置(下标为i- 1)插入新元素e。
- 时间复杂度:O(N)
- 最好O(1),最坏O(N),平均O(N/2)
bool ListInsert(SqList& L, int i, ElemType e) {
//i的范围无效,插入失败
if (i < 1 || i >L.length + 1)
return false;
//存储空间满,插入失败
if (L.length >= MaxSize)
return flase;
//将第i个元素及之后的元素后移
for (int j = L.length; j >= i; i--)
L.data[j] = L.data[j - 1];
//插入
L.data[i - 1] = e;
//顺序表长度+1
L.length++;
return true;
}
2.4 删除操作
删除表中第i个位置(下标为i - 1)的元素,用引用变量e返回。
- 时间复杂度:O(N)
- 最好O(1),最坏O(N),平均O((N-1)/2)
//e要改变,传入实参
bool ListDelete(SqList& L, int i, ElemType& e) {
if (i < 1 || i >L.length)
return false;
//被删除元素的元素赋给e
//第i个位置元素的下标是i - 1
e = L.data[i - 1];
//元素前移
for (int j = i; j < Length; j++)
L.data[j - 1] = L.data[j];
//元素删除,顺序表长度-1
L.length--;
return true;
}
2.5 按值查找(顺序查找)
在顺序表中查找第一个元素值等于e的元素,并返回其位序(数组下标+1)。
- 时间复杂度:O(N)
- 最好O(1),最坏O(N),平均O((N+1)/2)
顺序表还可以按位查找,就是利用数组下标访问,时间复杂度为O(1).
int LocateElem(SeqList L, ElemType e) {
int i;
for (i = 0; i < L.length; i++)
if (L.data[i] == e)
//返回的是位序
return i + 1;
return 0;
}
1.错 对
顺序表中所有元素的类型必须相同,且必须连续存放,一维数组中的元素可以不连续存放。
栈,队列,树也可以利用一维数组表示,它们的逻辑结构就完全不同。
顺序表和一维数组的物理结构相似,基本一样(都连续存放,但顺序表除存取外还有其他操作。)
2.A
存/取方式是指读/写方式,顺序表是一种支持随机存取的存储结构,根据起始地址加上元素的序号,可以很方便地访问任意一个元素,这就是随机存取的概念。
顺序存取是按照数据存储的物理位置顺序依次进行访问。就像听磁带,要先听完前面的内容才能听到后面的内容,数据的读取必须从起始位置开始,按顺序逐个读取。
-THE END-