数据结构与算法接触——第02周-小节

发表于 2022-01-07 分类于开发， N-数据与算法，数据结构与算法基础阅读时长 ≈ 1 分钟

一概述

顺序表(线性表的顺序存储结构)的特点
顺序表的基本操作
顺序表的操作算法分析
顺序表优缺点

二顺序表(线性表的顺序存储结构)的特点

利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系。即线性表的逻辑结构与存储结构一致
在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等
这种存取元素的方法被称为随机存取法

三顺序表的基本操作

InitList(&L);     //初始化操作，建立一个空的线性表L
DestroyList(&L);    //销毁已存在的线性表L
ClearList(&L);     //将线性表清空
ListInsert(&L,i,e);  //在线性表L中第i个位置插入新元素e
ListDelete(&L,i,&e);  //删除线性表L中第i个位置元素，用e返回
IsEmpty(L);      //若线性表为空，返回true，否则false
ListLength(L);     //返回线性表L的元素个数
LocateElem(L,e);    //L中查找与给定值e相等的元素，若成功返回该元素在表中的序号，否则返回0
GetElem(L,i,&e);    //将线性表L中第i个位置元素返回给e

四顺序表的操作算法分析

4.1 时间复杂度

查找、插入、删除算法的平均时间复杂度为O(n)

4.2 空间复杂度

显然，顺序表操作算法的空间复杂度S(n)=O(1)。即没有占用辅助空间

五顺序表优缺点

5.1 优点

存储密度大(结点本身所占存储量/结点结构所占存储量)
可以随机存取表中任一元素

5.2 缺点

在插入、删除某一元素时，需要移动大量元素
浪费存储空间
属于静态存储形式，数据元素的个数不能自由扩充

5.3 补充

为了克服这一缺点，使用链表

0%