数据结构速成--顺序表

        由于是速成专题，因此内容不会十分全面，只会涵盖考试重点，各学校课程要求不同 ，大家可以按照考纲复习，不全面的内容，可以看一下小编主页数据结构初阶的内容，找到对应专题详细学习一下。 

目录

一、线性表的类型定义

二、顺序表的结构

三、顺序表的实现

1. 数据元素的插入

2. 数据元素的删除

一、线性表的类型定义

        线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。

        除第一个元素外，每个元素有且仅有一个直接前驱。

        除最后一个元素外，每个元素有且仅有一个直接后继。 

         第一部分要求大家了解线性表的基本操作，根据函数名和传递的参数明白该函数实现的具体功能。

二、顺序表的结构

        线性表的顺序存储称为顺序表，它是由一组地址连续的存储单元依次存储线性表中的数据
元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

例：如果一个顺序表中第一个元素的存储地址为1000，每个元素占4个地址单元，那么第6个元素的存储地址应是（      ）。

A. 1020       B.1010      C.1016      D.1024

        本道题选 A。sizeof(数据元素的类型)=4，i=6，因此根据上面的公式，得到1000+4*5=1020。

顺序表的特点：

• 顺序表最主要的特点是随机存取，允许下标的随机访问，因此适合用于随机查找，时间复杂度为O(1)。
• 顺序表的存储密度高，每个结点只存储数据元素。
• 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。 

        第二部分要求大家重点掌握动态顺序表的定义，存储地址的计算以及顺序表的特点。

三、顺序表的实现

1. 数据元素的插入

        假设顺序表长度为n，在顺序表的第i个位置插入新元素e。若i的输入不合法，则返回false，表示插入失败；否则将顺序表的第i个元素及其后的所有元素右移一个位置（即需要挪动n-i+1次元素），腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。 

bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1||i>L.length+1) //判断的范围是否有效
        return false;
    for(int j=L.length;j>=i;j--) //将第i个元素及之后的元素后移
        L.data[j]=L.data[j-1];
    L.data[i-1]=e; //在i位置处放入e
    L.length++; //线性表长度增加1
    return true;
}

2. 数据元素的删除

        删除线性表L中第i个位置的元素，若成功则返回true，并将被删除的元素用引用变量返回，否则返回false。 

bool ListDelete(SqList &L,int i,ElemType &e){
    if(i<1||i>L.length) //判断i的范围是否有效
        return false;
    e=L.data[i-1]; //将被删除的元素赋给e
    for(int j=i;j<L.length;j++) //将第i个位置后的元素后移
        L.data[j-1]=L.data[j];
    L.length--; //线性表长度减1
    return true;
}

         由此可见，插入/删除元素的时间复杂度均为O(n)。

例1：将两个有序顺序表A、B合并为一个新的有序顺序表C，并用函数返回结果顺序表。

//定义动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;//记录顺序表的空间大小
	int size;//有效数据个数
}SL;
//算法思想：A和B进行比较，谁小就先放到C里
void Merge(SL* A, SL* B, SL* C)
{
	//A和B有效数据之和大于C的容量，就无法存储
	if (A->size + B->size > C->capacity)
		return -1;
	int i = 0, j = 0, k = 0;
	//比较A和B各元素大小，谁小就放到C里
	while (i < A->size && j < B->size) {
		if (A->arr[i] <= B->arr[j])
			C->arr[k++] = A->arr[i++];
		else
			C->arr[k++] = B->arr[j++];
	}
	//跳出循环说明A和B其中一个已经遍历完了，但不知道是哪个先结束了
	//分别判断，让没结束的那个顺序表继续遍历
	while (i < A->size)
	{
		C->arr[k++] = A->arr[i++];
	}
	while (j < B->size)
	{
		C->arr[k++] = B->arr[j++];
	}
	//最后C有效数据的个数就是k
	C->size = k;
}

例2：删除顺序表中所有值为x的数据。

//定义动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;//记录顺序表的空间大小
	int size;//有效数据个数
}SL;
//删除指定位置数据
void SLErase(SL* ps, int pos) {
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//pos以后的数据往前挪动一位
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;//有效数据-1
}
//算法思想：找到x在顺序表中的位置，在通过删除指定位置的算法实现
void DeleteX(SL* ps, SLDataType x) {
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			SLErase(ps, i);//删除指定位置的元素，下标为i
			//顺序表现在是4 3 2 1 1
			//i=3时删除一个1，顺序表是4 3 2 1
			//但是i++就使得i=4,就会越界，因此要让i--变回i=3的位置
			i--;
		}
	}
}

例3：设计一个高效的算法逆置顺序表。

void Swap(SLDataType* a, SLDataType* b) {
	SLDataType tmp = *a;
	*a = *b;
	*b = tmp;
}
void Reverse(SL* ps) {
	//思路1：创建一个新的顺序表，逆序遍历原顺序表放到新表里，再用新表覆盖原顺序表（效率低下）
	//思路2：交换下标为i和n-i-1的数据
	int n = ps->size;
	for (int i = 0; i < ps->size; i++)
	{
		if (i <= n - i - 1) {
			Swap(&ps->arr[i], &ps->arr[n - i - 1]);
		}
	}
	return ps;
}

        第三部分是本章最为重要的内容，需要大家熟练掌握插入和删除元素的基本算法思路，一定要注意，在执行操作之前，一定要判断所给的参数是否合法！