计算机考研408-数据结构笔记本之——第二章 线性表
2.2 线性表的顺序表示（顺序表的定义和基本操作：初始化/插入/删除/查找）
2.2.1 顺序表的定义
1.定义
顺序表是线性表的顺序存储。
所谓顺序存储，就是把逻辑上相邻的元素存储在物理位置上相邻的存储单元中，元素间的关系由存储单元的邻接关系来体现。
2.实现
顺序表中的任意一个数据元素都可以随机存取。通常用数组来描述线性表的顺序存储结构。数组可以是静态分配的，也可以是动态分配的.
注意：线性表中元素位序从1开始，而数组中元素下标从0开始。
假定线性表的元素类型为ElemType
1）静态分配（存储数组空间和内存固定）
静态分配的顺序表存储结构描述为：
2）动态分配（存储数组分配空间大小在运行时动态决定）
3.特点
2.2.2 顺序表的初始化
静态分配：
静态分配在声明一个顺序表时，就已经为其分配了数组空间，因此初始化时只需将顺序表的当前长度设为0。
//静态分配初始化//SqList L； //声明一个顺序表 void InitSize(SeqList &L){ L.length = 0; //顺序表初始长度为0 } 动态分配：
动态分配的初始化为顺序表分配一个预定义大小的数组空间，并将顺序表的当前长度设为0.MaxSize指顺序表当前分配的存储空间大小,一旦因为插入元素而空间不足,就再进行分配.
//动态分配初始化//SqList L； //声明一个顺序表 void InitSize(SeqList &L){L.data = (ElemType *)malloc(sizeof(ElemType)*Initsize); //分配存储空间 L.length = 0; //顺序表初始长度为0L.MaxSzie = InitSize; //初始存储容量 } 2.2.2 顺序表的插入(O(n))
在顺序表L的第i个位置插入新元素e: ListInsert(&L,i,e);
若i不合法(不在1 <= i <= L.length + 1范围内),返回False,插入失败;
若i合法,将第i个元素及其后的元素均往后移动一位,腾出的空位置插入新元素e,顺序表长度+1,插入成功,返回True.
bool ListInsert(SqList &L, int i, int e)
{if(i < 1 || i > L.length+1) return false; //判断i的范围是否有效 if(L.length >= MaxSzie) return false; //存储空间若满了不能插入 for(int j = L.length; j >= i; j--)L.data[j] = L.data[j-1]; //将第i个及其之后元素均后移一位 L.data[i-1] = e; //插入元素e L.length++; //表长度+1 return true;
} 时间复杂度分析: 
2.2.2 顺序表的删除(O(n))
删除顺序表L中第i个位置的元素,用引用变量e返回被删除元素的值: ListDelete(&L,i,e);
若i不合法(不在1 <= i <= L.length 范围内),返回False;
若i合法,将第i个元素(要删除的元素)的值赋给e,并将第i+1个元素及其后的元素均往前移动一位,表长减1,返回True.
bool ListDelte(SqList &L, int i, int &e) //注意e要加引用符
{if(i < 1 || i > L.length) return false; //判断i的范围是否有效 e = L.data[i-1]; //将被删除元素的值赋给e for(int j = i; j < L.length; j++)L.data[j-1] = L.data[j]; //将第i个元素后面的元素均前移一位 L.length--; //表长度-1 return true;
}时间复杂度分析
2.2.2 顺序表的查找(O(n)或O(1))
分按位查找和按值查找(顺序查找)两种.
按位查找(O(1)):直接根据数组下标访问元素,获取表L中第i个位置的元素的值.GetElem(L,i);
ElemType GetElem(SqList L, int i)
{return L.data[i-1];
}按值查找(顺序查找)(O(n)):在顺序表L中查找第一个元素值 = e的元素,并返回其位序: LocateElem(&L,e);
时间复杂度分析
代码汇总
