【数据结构】顺序表

发布于:2025-03-16 ⋅ 阅读:(16) ⋅ 点赞:(0)

0.本篇问题

  1. 什么是顺序表的位序,他和顺序表的下标有什么关系?
  2. 顺序表的优缺点?
  3. 动静态内存分配如何实现?
  4. 动静态的初始化如何实现?
  5. 插入操作有哪些参数?实现过程?时间复杂度?
  6. 删除操作实现了什么?有哪些参数?实现过程?时间复杂度?
  7. 按值查找操作实现了什么?有哪些参数?实现过程?时间复杂度?
  8. 随机存取?按位查找时间复杂度?

★错题 

1.①“顺序表可以利用一维数组表示,因此顺序表与一维数组在逻辑结构上是相同的”(对or错)

②顺序表和一维数组一样,都可以进行随机存取。(对or错)

2.线性表的顺序存储结构是一种( )

A.随机存取的存储结构        B.顺序存取的存储结构

C.索引存取的存储结构        D.散列存取的存储结构

一、顺序表知识点

  1.  ai 是顺序表中的第i个元素,i称为位序。(线性表中的元素的位序是从1开始的,而数组元素的下标是从0开始的)。
  2. 顺序表是一种支持随机存取的存储结构,根据起始地址加上元素的序号,可以很方便地访问任意一个元素,这就是随机存取的概念。

  3. 顺序表的优点:


二、顺序表的基本操作的实现

(本篇代码和王道考研书中的代码基本吻合,重在算法的思想,不要求代码具有可执行性。)

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-