【数据结构】顺序表-EW帮帮网

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-

【数据结构】顺序表