网业怎么做_大型网站制作都有哪些_广东搜索引擎优化_seo搜索引擎优化排名

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) {//顺序表的初始长度为0L.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;//顺序表长度+1L.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 - 1e = L.data[i - 1];//元素前移for (int j = i; j < Length; j++)L.data[j - 1] = L.data[j];//元素删除，顺序表长度-1L.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-