顺序存储结构分析
优点：缺点： 1、静态顺序存储线性表
优点：缺点：静态顺序存储线性表的基本实现：
1、定义和初始化2、增
时间复杂度分析 2、删
时间复杂度分析 3、查（改类似）(1)按位查找(2)按值查找4、测试 2、动态顺序存储线性表
优点：缺点：动态顺序存储线性表的基本实现：
1、增2、其余操作参考静态
线性表的顺序存储结构又称为顺序表，它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
优点：- 因为逻辑顺序和物理顺序相同，所以顺序表中的任意数据元素都可以随机存取。–这个就叫随机访问。顺序表的存储密度高，每个结点只存储数据元素。
由于顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除就需要移动大量的元素
顺序表分为静态顺序存储和动态顺序存储。
1、静态顺序存储线性表在静态分配时，由于数组的大小和空间已经实现固定。所以一旦占满再加入新的数据就会产生溢出，从而导致程序崩溃。
优点：- 简单快捷针对无指针的语言，无malloc、free操作（这俩运算不简单）
如果数组满了就没办法了。
静态顺序存储线性表的基本实现： 1、定义和初始化#include2、增#include // 静态链表 #define MaxSize 10 //定义 typedef struct { int data[MaxSize]; int length; }SqList; //初始化： void InitList(SqList& L) { L.length = 0; }
//插入---在下标为i的位置插入e
bool InsertList(SqList& L, int i, int e) {
//检查
if (i<0 || i>L.length + 1)
{
//非法插入
printf("非法插入");
return false;
}
if (L.length == MaxSize)
{
//判满
printf("满了");
return false;
}
//没问题了开始插入
for (int j = L.length; j != i; j--)
{
L.data[j] = L.data[j - 1];
//一个个向后挪出位置------时间开销
}
L.data[i] = e;
L.length++;
return true;
}
时间复杂度分析
设L.length = n
最好：插入到表尾不需要移动任何元素此时i = n,循环0次。
最坏：插入到表头，需要将原来的n个元素都往后移动，此时i = 0,循环n次。
平均情况：假设新元素插到任何位置概率相同，即为1/n+1,所以平均循环次数EX = (1/n+1) * (n*(n+1)/2) = n/2;
平均时间复杂度：O(n)
2、删
//删除---按下标删除
bool DeletNode(SqList& L, int i) {
//检查
if (i < 0 || i >= L.length) {
printf("非法删除！");
return false;
}
if (L.length == 0) {
printf("空了");
return false;
}
//没问题了就删除,采用从i处开始每个节点都向前移一位覆盖
for (int j = i; j < L.length-1; j++) {
L.data[j] = L.data[j + 1];
}
L.length--;
return true;
}
时间复杂度分析
设L.length = n
最好：删除的元素是最后一个此时i = n-1,循环0次
最坏的情况：删除的元素是第一个元素此时i = 0,循环n-1次
平均情况：假设删除每个元素概率都相同均为1/n，所以平均循环次数 = EX = (1/n) * (n*(n—1)/2) = n-1/2
平均时间复杂度：O(n)
3、查（改类似） (1)按位查找return L.data[i];
时间复杂度O(1)
(2)按值查找//查到了返回ture,没查到返回false.下标放在local上。
bool GetNode(SqList L, int value,int& local) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == value) {
local = i;
return true;
}
}
return false;
}
最好：目标在表头，循环1次
最坏：目标在尾巴，循环n次
平均情况：假设查找每个元素概率都相同均为1/n，所以平均循环次数 = EX = (1/n) * (n*(n+1)/2) = n+1/2
平均时间复杂度：O(n)
4、测试int main() {
SqList S;
InitList(S);
for (int i = 0; i < MaxSize; i++) {
InsertList(S, i, i * i);
}
for (int i = 0; i < S.length; i++) {
printf("S.data[%d] = %dn", i, S.data[i]);
}
//改：
S.data[2] = 999;
//按下标查:
printf("%dn", S.data[2]);
//按value查找
int n;
if (GetNode(S,36,n)){
printf("36在下标为：%d的地方",n);
}
else {
printf("没找到");
}
}
2、动态顺序存储线性表
优点：
可以动态的更改线性表的长度，即使满了也没有关系。
缺点：存储密度没有静态顺序存储线性表高
动态顺序存储线性表的基本实现：#include#include //malloc和free在stdlib.h中 #define InitSize 10 typedef struct { int* data;//指向动态分配的数组首地址的指针 int MaxSize;//顺序表最大容量 int length;//顺序表当前长度 }SeqList; //初始化 void InitList(SeqList& L) { L.data = (int*)malloc(InitSize * sizeof(int)); L.length = 0; L.MaxSize = InitSize; }
这一步有些跨考的同学不好理解，所以我加了一张我当时考研时的笔记图片：
1、增//增加长度
void IncreaseSize(SeqList& L, int len) {
int* p = L.data;//step1、先把顺序表的首地址指针保存一下
L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));//step2、malloc一片新的空间
//step3、将之前的数据都搬过来
for (int i = 0; i < L.length; i++) {
L.data[i] = p[i];//这一步的时间开销较大
}
L.MaxSize = L.MaxSize + len;
free(p);//释放原来的L.data指向的空间
}
//增加结点：
void IncreaseNode(SeqList& L, int i, int e) {
if (L.length == L.MaxSize) {
//增加一个长度
IncreaseSize(L, 1);
}
//没问题了开始插入
for (int j = L.length; j != i; j--)
{
L.data[j] = L.data[j - 1];
//一个个向后挪出位置
}
L.data[i] = e;
L.length++;
}
或者使用realloc开辟新空间：
//增加长度
void IncreaseSize(SeqList& L, int len) {
int* p;
p = (int*)realloc(L.data, (L.MaxSize + len) * sizeof(int));
L.data = p;
L.MaxSize = L.MaxSize + len;
}
时间复杂度分析：静态动态的都一样。
2、其余操作参考静态
