顺序表的定义
顺序表:用顺序存储的方式来实现线性表
顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。
如何知道一个数据元素的大小?
- C语言:sizeof(ElemType)
sizeof(int) = 4B
顺序表的实现方式
静态分配
#define MaxSize 10 // 定义最大长度
typedef struct{
ElemType data[MaxSize];// 用静态的“数组”存放数据元素
int length;// 顺序表的当前长度
}SqList;// 顺序表的类型定义(静态分配的方式)
当定义了数组的长度就无法改变
Q:如果“数组”中数据存满了怎么办?
A:可以放弃治疗,顺序表的表长刚开始确定后就无法更改(存储空间是静态的)
Q:如果刚开始就声明一个很大的内存空间呢?
A:会存在很浪费的问题
#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; // 顺序表的初始长度为0
}
int main(){
SqList L; // 声明一个顺序表
InitList(L);// 初始化顺序表
// ... 未完待续,后续操作
return 0;
}
动态分配
#define InitSize 10 //顺序表的初始长度
typedef struct{ //指示动态分配数组的指针
ELemType *data; //顺序表的最大容量
int MaxSize; // 顺序表的当前长度
int length; // 顺序表的类型定义(动态分配的方式)
} SqList;
- C语言中 分别使用 --
malloc
和free
函数。malloc函数返回一个指针需要强制转型为你定义的数据元素的类型指针
L.data = (ElemType *) malloc (sizeof(ElemType*) * InitSize);
ElemType *
表示你要申请的内存的数据类型sizeof(ElemType*) * InitSize
表示的是申请的内存空间大小
- C++中使用
new
和delete
关键字
#include <stdlib.h>
#define InitSize 10 //默认的最大长度
typedef struct{
int *data; // 指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的当前长度
}SeqList;
void InitList(SeqList &L){
// 用malloc函数申请一片连续的存储空间
L.data=(int *) malloc(InitSize * sizeof(int));
L.length =0;
L.MaxSize =InitSize;
}
// 增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
int *p=L.data;
L.data=(int *)malloc ((L.MaxSize+len)*sizeof(int));
// 上面的malloc返回一个指针,需要强制转换
for(int i=0;i<L.length;i++){
L.data[i]=p[i]; // 复制到新的空间
}
L.MaxSize=L.MaxSize+len;
free(p); // 释放空间
}
int main(){
SeqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
// ……往顺序表中随便插入几个元素
IncreaseSize(L,5);
return 0;
}
顺序表的特点
- 随机访问:即可以在O(1)时间内找到第i个元素。
- 存储密度高:每个节点只存储数据元素
- 拓展容量不方便(即采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
- 插入、删除操作不方便,需要移动大量的元素
顺序表的插入
ListInsert(&L,e)
:插入操作。在表L中第i个位置上插入指定元素e。
以下代码是基于静态分配实现的顺序表,在动态分配实现上也雷同
#define MaxSize 10 // 定义最大长度
typedef struct{
int data[MaxSize]; // 用静态的“数组”存放数据元素
int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义
void ListInsert(SqList &L,int i,int e){
for(int j=L.length;j>i;i--){
L.data[j]=L.data[j-1];
}
L.data[i-1]=e;// 在位置i处放入e 注意位序、数组下标的关系,并从后面的元素依次移动
// 这里的i为数组的位序,是从1开始的
L.length++; // 长度加1
}
int main(){
SqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
ListInsert(L,2,3);
return 0;
}
当调用以上的代码是,避免调用者的不规范时使用,比如:i 的范围应该在【1~length+1】,所以我们可以如下的完善相关的代码逻辑,重新编写插入函数如下:
bool ListInsert(SqList &L,int i,int e){
if(int < 1 || i > L.length + 1){
return false; // 判断i的范围是否有误
}
if(L.length >= MaxSize){
return false; // 当前的存储空间已满,不能插入
}
for(int j=L.length;j>i;j--){
L.data[j]=L.data[j-1]; // 将第i个元素及以后的元素后移
}
L.data[i-1] =e; // 将第i个元素及之后的元素后移
L.length ++; // 长度加1
return true;
好的算法,应该具有“健壮性”,能够很好的处理异常情况,并给使用者反馈!
插入操作的时间复杂度:
问题规模:n = length(表长)
- 最好情况:新元素插入到表尾,不需要移动元素
i = n + 1,循环0次;最好时间复杂度 = O(1)
- 最坏情况:新元素插入到表头,需要将原有的n个元素全都向后移动
i = 1,循环n次;最坏时间复杂度 = O(n)
- 平均情况:假设新元素插入到任何一个位置的概率相同,即$ i =1,2,3...,length+1$的概率是$$p=\frac {1} {n+1}$$
i = 1,循环n次;
i = 2,循环n-次;
...
i = n+1,循环0次
平均循环次数 = $$np + (n+1)p +(n-2)p +...+1·p = \frac {n(n+1)}{2}\frac {1}{n+1}=\frac {n}{2}$$ ⇨平均时间复杂度 = O(n)
顺序表的删除
ListDelete(&L,i,&e)
:删除操作。删除表L中的第i个位置的元素,并用e返回删除元素的值。
bool ListDelete(SqList &L,int i,int &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];
}
L.length--; // 顺序表的长度减1
return true;
}
int main(){
SqList L; //声明一个顺序表
InitList(L); //初始化一个顺序表
// ...此处省略一些代码,插入几个元素
int e = -1; //用变量e把删除的元素“带回来”
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,… 的概率都是$$p = \frac {1} {n}$$
i = 1,循环n-1次;
i = 2,循环n-2次;
i = 3,循环n-3次;
……
i = n,循环0次
平均循环次数 = $$(n-1)p + (n-2)p + ... +1·p = \frac {n(n+1)}{2}\frac {1}{n} =\frac{n-1}{2}$$⇨平均时间复杂度 = O(n)
顺序表的查找
按位查找
GetElem(L,i)
:按位查找操作。获取表中第i个位置的元素的值。
- 静态分配实现:
#define MaxSize 10 // 定义最大的长度
typedef struct {
ElemType data[MaxSize]; // 用静态的“数组”存放数据元素
int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义(静态分配的方式)
ElemType GetElem(SqList L,int i){
return L.data[i-1]; // 因为这里传入的是查找的位序,所以是i-1
}
- 动态分配实现:
#define InitSize 10 // 顺序表的初始长度
typedef struct{
ElemType *data; // 指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的长度
}SeqList; // 顺序表的类型定义(动态分配方式)
ElemType GetElem(SeqList L,int i){
return L.data[i-1];
}
时间复杂度:O(1)
由于顺序表的各个元素在内存中连续存放,因此可以根据起始位置和数据元素大小立即找到第i个元素 -- “随机存取”特性
按值查找
LocateElem(L,e)
:按值查找操作。在表L中查找具有给定关键字值得元素。
#define InitSize 10 // 顺序表的初始长度
typedef struct{
ElemType *data; // 指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的长度
}SeqList; // 顺序表的类型定义(动态分配方式)
// 在顺序表L中查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SeqList L,ELemType e){
for(int i = 0; i<L.length;i++){
if(L.data[i]==e){
return i+1; // 数组下标为i的元素值等于e,返回其位序i+1
}
}
return 0; // 退出循环,说明查找失败!
}
当查找的元素为`结构体类型
或复杂类型不能使用==
来比较!
Tips:
《数据结构》考研初试中,手写代码可以直接使用 “==”,无论ElemType是基本数据类型还是结构类型!
时间复杂度:
问题规模:n = L.length(表长)
- 最好情况:目标元素在表头
循环1次;最好时间复杂度 = O(1)
- 最坏情况:目标元素在表尾
循环n次;最坏情况复杂度 = O(n)
- 平均情况:假设目标元素出现在任何一个位置的概率相同,都是$$\frac{1}{n}$$
目标元素在第1位,循环1次
目标元素在第2位,循环2次
……
目标元素在第n位,循环n次
平均循环次数 = $$1·\frac{1}{n} + 2·\frac{1}{n} +……+n·\frac{1}{n} =\frac{n(n+1)}{2}\frac{1}{n} = \frac{n+1}{2}$$ ⇨平均时间复杂度 = O(n)
版权声明:文章转载请注明来源,如有侵权请联系删除!