顺序表
顺序表的定义
- 线性表的顺序存储又称顺序表
- 它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻
线性表的顺序存储类型描述
- 静态分配
#define MaxSize 50
typedef struct {
ElemType data[MaxSize]; // 顺序表的元素
int length; // 顺序表的实际长度
} SqList; // 顺序表类型的定义
- 动态分配
#define InitSize 100
typedef struct {
ElemType * data;
int MaxSize,length; //最大容量和当前size
} SqList;
// C的初始动态分配语句
L.data = (ElemType *)malloc(sizeof(SqList) * InitSize);
// C++的初始动态分配语句
L.data = new ElemType[InitSize];
顺序表上基本操作实现以及事件复杂度分析
- 插入操作
/**
* 方法名:ListInsert
* 参数1:SqList &L 顺序表
* 参数2:int i 插入位置
* 参数3:ElemType e 插入内容
* 要求在 i (1 <= i <= L.length + 1) 个位置插入新元素e
*/
bool ListInsert(SqList &L, int i, ElemType 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;
}
时间复杂度分析:
最好情况: 表尾插入，没有元素移动时间复杂度为O(1)
最坏情况: 表头插入，所有元素都移动，时间复杂度为O(n)
平均情况: O(n)
分析：
插入到哪个位置就把从那个位置之后所有的值都往后移动一位；
平均移动次数 = 总次数 / 移动情况个数；
移动情况个数: 表的长度为n，由于表头和表尾都可以插入，所以插入的情况有(n + 1)种；
总次数: 在表尾插入移动的次数为0次，在表头插入移动的次数为n次，一共有(n + 1)次种情况可以插入，所以首项为(n + 1)，末项为0，项数为(n + 1)，所以总次数为(n + 1)(n + 0) / 2；
平均移动次数 = ((n + 1)(n + 0) / 2) / (n + 1) = n / 2
- 删除操作
/**
* 方法名:ListDelete
* 参数1:SqList &L 顺序表
* 参数2:int i 删除位置
* 参数3:ElemType &e 被删除内容用引用变量e返回
* 要求删除在 i (1 <= i <= L.length) 个位置元素
*/
bool ListDelete(SqList &L, int i, ElemType &e) {
if (i < 1 || i > L.length) // 判断范围是否有效
return false;
e = L.data[i - 1];
for(int j = i; j < L.length; j++) { // 把所有元素往前移动
L.data[j - 1] = L.data[j];
}
L.length --; // 线性表长减1
return true;
}
时间复杂度分析:
最好情况: 表尾删除，没有元素移动时间复杂度为O(1)
最坏情况: 表头插入，所有元素都移动，时间复杂度为O(n)
平均情况: O(n)
分析:
删除哪个元素就把那个元素后面所有的值往前移一位；
平均移动次数 = 总次数 / 移动情况个数；
移动情况个数: 表的长度为n，可以删除的情况有n种
总次数: 在表尾删除移动的次数为0次，在表头删除移动的次数为n - 1次，一共有n种删除的情况，所以首项为(n - 1)，末项为0，项数为n，所以总次数为(n - 1)n / 2；
平均移动次数 = （(n - 1)n / 2）/ n = (n - 1) / 2
- 查找元素
/**
* 方法名:LocateElem
* 参数1:SqList L 顺序表
* 参数3:ElemType e 需要查找的内容
*/
int LocateElem(SqList L, ElemType e) {
int i = 0;
for(i = 0;i < L.length; i++) {
if(L.data[i] == e)
return i + 1; // 返回位置
}
return 0;
}
时间复杂度分析:
最好情况: 查找表头元素，时间复杂度为O(1)
最坏情况: 查找表尾元素，需要把所有元素都遍历一遍，时间复杂度为O(n)
平均情况: O(n)
分析:
平均查找次数 = 总次数 / 查找的情况个数
移动情况个数: 顺序表长度为n，查找情况一共有n种，
总次数: 如果需要查找的元素在表头需要查找1次，如果需要查找的元素在表尾需要查找n次，所以首项为n，末项为1，一共有n项，总次数为(n + 1)n / 2，
所以平均查找次数 = ((n + 1)n / 2) / n = (n + 1) / 2
