顺序表

顺序表的定义

顺序表：用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系体系

顺序表——静态分配

//不初始化数据元素，内存不刷0 #include <stdio.h> #define MaxSize 10 // 定义最大长度 using namespace std; 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; //顺序表初始值长度为0 } int main() { SqList L; // 声明一个顺序表 InitList(L); // 初始化顺序表 // 尝试“违规”打印整个data数组 for(int i = 0; i < MaxSize; i++) { printf("data[%d] = %d\n", i, L.data[i]); } return 0; } data[0] = 0 data[1] = 0 data[2] = 0 data[3] = 0 data[4] = 0 data[5] = 0 data[6] = 0 data[7] = 0 data[8] = -272632568 data[9] = 32766

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

#include <stdlib.h> #define InitSize 10 // 默认的最大长度 using namespace std; typedef struct { int *data; // 指示动态分配数组的指针 int MaxSize; // 顺序表的最大容量 int length; // 顺序表的当前长度 }SqList; // 顺序表的类型定义 //基本操作——初始化一个顺序表 void InitList(SqList &L) { // 用 malloc 函数申请一片连续的存储空间 L.data = (int *)malloc(InitSize *sizeof(int)); L.length = 0; //顺序表初始值长度为0 L.MaxSize = InitSize; } void IncreaseSize(SqList &L, int len) { int *p = L.data; L.data = (int *)malloc((L.MaxSize + len) * sizeof(int)); for(int i = 0; i < L.length; i++) { L.data[i] = p[i]; // 将数据复制到新区域 } L.MaxSize = L.MaxSize + len; // 顺序表最大长度增加len free(p); // 释放原来的内存空间 } int main() { SqList L; // 声明一个顺序表 InitList(L); // 初始化顺序表 // 往顺序表中随便插入几个元素 IncreaseSize(L, 5); return 0; }

顺序表的特点

随机访问，可以在O(1)时间内找到第i个元素存储密度高，每个节点只存储数据元素拓展容量不方便插入、删除操作不方便，需要移动大量元素

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

在表L中的第i个位置上插入指定元素e

#include <stdlib.h> #define MaxSize 10 // 定义最大长度 using namespace std; typedef struct { int data[MaxSize]; // 用静态的“数组”存放数据元素 int length; // 顺序表的当前长度 }SqList; // 顺序表的类型定义 bool ListInsert(SqList &L, int i, int 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, 3, 3); return 0; }

最好情况：新元素插入到表尾，不需要移动元素，i=n+1，循环0次，最好时间复杂度 = O(1)

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

平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,2,3…,length+1的概率都是p=1/(n+1)，i=1，循环n次，i=2时，循环n-1次，i=3，循环n-2次…i=n+1时，循环0次，平均循环次数 = np+(n-1)p+(n-2)p+…+p=n(n+1)/2 * 1/(n+1) = n/2，平均复杂度O(n)

顺序表基本操作——删除

删除表L中第i个位置的元素，并用e返回删除元素的值

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); // 初始化顺序表 int e = -1; if(ListDelete(L, 3, e)) { printf("已删除第3个元素，删除元素值为=%d\n", e); } else { printf("位序i不合法，删除失败\n"); } return 0; }

最好情况：删除表尾元素，不需要移动其他元素，i=n，循环0次，最好时间复杂度 = O(1)

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

平均情况：假设删除任何一个元素的概率相同，即i=1,2,3,…,length的概率都是p=1/n1，i=1，循环n-1次，i=2时，循环n-2次，i=3，循环n-3次…i=n时，循环0次，平均循环次数 = (n-1)p+(n-2)p+…+p=n(n-1)/2 * 1/n=(n-1)/2；平均时间复杂度 = O(n)

顺序表按位查找

获取表L中第i个位置的元素的值

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

时间复杂度：O(1)，随机存取特性

顺序表按值查找

在表L中查找具有给定关键字值的元素

// 在顺序表L中查找第一个元素值等于e的元素，并返回其位序 int LocateElem(SeqList 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; // 退出循环，说明查找失败 }

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

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

平均情况：假设目标元素出现在任何一个位置的概率相同，都是1/n，目标元素在第1次，循环1次，在第2次，循环2次，…，在第n次，循环n次，平均循环次数 = 1/n + 2/n + 3/n + … + n/n = n(n+1)/2 * 1/n = (n+1)/2，平均时间复杂度 = O(n)