一、顺序表（顺序存储）

（一）、定义（如何用代码实现）

• 线性表是具有相同数据类型的n（n >= 0）个数据元素的有限序列。
• 顺序表：用顺序存储的方式实现线性表顺序存储。
• 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
  
• C语言 sizeof(ElemType)：知道一个数据元素大小。ElemType 就是你的顺序表中存放的数据元素类型.

typedef struct {
int num; //号数
int people; //人数
} Customer;

sizeof(int) = 4B
sizeof(Customer) = 8B

（二）、基本操作的实现

1. 顺序表的实现——静态分配

#define MaxSize 10				//定义最大长度
typedef struct{
	ElemType data[MaxSize];		//用静态的“数组”存放数据元素
	int length;					//顺序表的当前长度
}SqList;						//顺序表的类型定义（静态分配方式）

• 初始化一个顺序表，将所有数据元素设置为默认初始值以及将顺序表初始长度为0.
  
• 不初始化数据元素，内存就会存在“脏数据”。
  

2. 顺序表的实现——动态分配

#define InitSize 10		//顺序表的初始长度
typedef struct{			
	ElemType *data;		//指示动态分配数组的指针
	int MaxSize;		//顺序表的最大容量
	int length;			//顺序表的当前长度
}SeqList;               //顺序表的类型定义（动态分配方式）

3. 顺序表的实现

• 顺序表的特点：
  ①、随机访问，既可以在O(1)时间内找到第i个元素。
  ②、存储密度高，每个节点只存储数据元素。
  ③、扩展容量不方便（即便采用动态分配的方式实现，扩展长度的时间复杂度也比较高）。
  ④、插入、删除操作不方便，需要移动大量元素。
  
  

（三）、顺序表的插入和删除

1. 顺序表的基本操作——插入

• ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
• 用存储位置的相邻来体现数据元素之间的逻辑关系。
  

#include<stdio.h>
#define MaxSize 10  //定义最大的长度
typedef struct {
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int length;     //顺序表的当前长度
}SqList;

void InitList(SqList &L){
    for(int i=0; i<MaxSize; i++)
        L.data[i] = 0;
    L.length = 0;
}

bool ListInsert(SqList &L, int i,int e){//在L的位序i处插入元素e
	if(i<1 || i>L.length+1) //判断i的范围是否有效
		return false;
	if(L.length >= MaxSize)//当前存储空间已满，不能插入
		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;
}


int main(){
    SqList L; //声明一个顺序表
    InitList(L); // 初始化顺序表
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,4);
    ListInsert(L,4,5);
    ListInsert(L,5,6);
    ListInsert(L,3,3);
    
    for(int i=0;i<L.length;i++)
        printf("data[%d]=%d\n",i,L.data[i]);
    
    return 0;
}

• 运行结果:

data[0]=1
data[1]=2
data[2]=3
data[3]=4
data[4]=5
data[5]=6

（1）插入操作的时间复杂度

• 最好情况：新元素插入到表尾，不需要移动元素，i = n+1，循环0次；最好时间复杂度 = O(1)
• 最坏情况：新元素插入到表头，需要将原有的 n 个元素全都向后移动，i = 1，循环 n 次；最坏时间复杂度 = O(n);
  

2. 顺序表的基本操作——删除

• ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
  

#include<stdio.h>
#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int length;
}SqList;

void InitList(SqList &L){
    for(int i=0; i<MaxSize; i++)
        L.data[i] = 0;
    L.length = 0;
}

bool ListInsert(SqList &L, int i,int e){//在L的位序i处插入元素e
	if(i<1 || i>L.length+1) //判断i的范围是否有效
		return false;
	if(L.length >= MaxSize)//当前存储空间已满，不能插入
		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;
}

bool ListDelete(SqList &L, int i, int &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;
} 

int main(){
    SqList L;//声明一个顺序表
    InitList(L);//初始化顺序表
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,4);
    ListInsert(L,4,5);
    ListInsert(L,5,6);
    
    int e=-1;//用变量e把删除的元素“带回来”
    if(ListDelete(L, 3, e))
        printf("已删除第3个元素，删除的元素为%d\n",e);
    else
        printf("位序i不合法，删除失败\n");
    return 0;
}

• 运行结果：

已删除第3个元素，删除的元素为4

• 如果参数没有加引用符号，会怎样？
  ①、变量e是引用变量，加上了引用符号。因为ListDelete方法中e加上变量符号，所以ListDelete方法中处理的e和main函数中处理的变量e是同一个数据。
  ②、但是如果，e不是引用类型的，即把e的引用符号去掉。那么ListDelete方法处理的变量e是main函数中e的复制品，虽然两个变量都是e，但是在内容中对应不同的两份数据。

（2）删除操作的时间复杂度

• 最好情况：删除表尾元素，不需要移动其他元素，i = n，循环 0 次；最好时间复杂度 = O(1)
• 最坏情况：删除表头元素，需要将后续的 n-1 个元素全都向前移动，i = 1，循环 n-1 次；最坏时间复杂度 = O(n);
  
  

（四）、顺序表查找

1. 顺序表的按位查找

• GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

（1）静态分配实现

#define MaxSize 10 //定义最大长度
typedef struct {
    ElemType data[MaxSize];//用静态的“数组”存放数据元素
    int length;//顺序表的当前长度
}SqList;//顺序表的类型定义（静态分配方式）

ElemType GetElem(SqList L, int i){
	return L.data[i-1];
}

（2）动态分配实现

#define InitSize 10//顺序表的初始长度
typedef struct{
	ElemType *data;//指示动态分配数组的指针
	int MaxSize;//顺序表的最大容量
	int length;//顺序表的当前长度
}SeqList;//顺序表的类型定义（动态分配方式）

ElemType GetElem(SeqList L,int i){//i和访问普通数组的方法一样
	return L.data[i-1];
}

（3）按位查找的时间复杂度

• 时间复杂度为：O(1)
• 由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第 i 个元素——“随机存取”特性

2. 顺序表的按值查找

• LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

#define InitSize 10//顺序表的初始长度
typedef struct{
	int *data;//指示动态分配数组的指针
	int MaxSize;//顺序表的最大容量
	int length;//顺序表的当前长度
}SeqList;//顺序表的类型定义（动态分配方式）

//在顺序表L中查找第一个元素值等于e的元素并返回其位置
int LocateElem(SqeList l, int e){
	for(int i=0; i<L.length; i++)
		if(L.data[i]==e)
			return i+1;//数组下标为i的元素值等于e,返回其位序i+1
	return 0;//退出循环，说明查找失败
}

3. 结构类型的比较

4. 按值查找的时间复杂度

• 最好情况：目标元素在表头，循环1次；最好时间复杂度 = O(1)
• 最坏情况：目标元素在表尾，循环 n 次；最坏时间复杂度 = O(n);