当前课程知识点：数据结构（Data Structures） > 2. List > 2.2 Array based List > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
大家好
接下来这节课中
我们将给大家讲解一下
List的一种具体实现方法数组
我们先来看一看
在实现List过程中
我们需要关注的问题
实现List关键是要寻找合适的方式
去存储List中的数据元素
第一种常见的存储方法
是建立一个数组
那么List中的数据元素
在内存中将一个接着一个的
顺序存放在这个数组中
这种基于数组的方法
实施起来比较简单
而且访问也比较高效
但是这种方法需要预先去给它分配内存
如果预先分配的空间太大
就会造成空间的浪费
相反如果分配的空间太小
则无法容纳新的数据
所以我们看到数组在空间的使用上
它是不够灵活的
那么有没有一种方法
可以灵活地根据当前我们实际的需要
来去分配内存空间呢
常用的一种方法叫做链表
链表并不要求数据是连续存放的
数据元素之间它们先后的逻辑关系
是通过指针把它们连接在一起的
链表消耗的空间大小
是随着元素个数的变化
而进行动态调整的
在这里我们首先来讲一下
基于数组的List实现方法
基于数组的List
它的核心就是要建立一个
用来存放元素的数组
围绕这个数组我们可以去构建一个C++类
AList用来去实现这个List
AList继承了List抽象类
并且实现了List上面的所有操作
这个类有一个模板参数Elem
它对应的是数据元素的类型
我们先来看一下AList它的属性成员
必不可少的
首先当然就是要有一个数组
这里定义了一个名字为listArray的数组
那么在对象初始化的时候
我们需要给这个数组来分配空间
接下来的整数maxsize
是用来去记录数组的大小
listsize记录的是列表中元素的个数
此外还有一个很重要的fence成员属性
用来去记录当前栅栏的位置
如图所示fence的值
它定义为栅栏后面的这个元素
在数组中的位置
AList它的构造函数是比较简单的
主要的工作是要给数组listArray分配空间
同时需要去初始化maxsize listsize
以及栅栏的位置fence
并且把fence设置为0
让栅栏处于列表的最前端的位置
而AList它的析构函数
则是简单地去销毁整个数组就可以了
下面我们再来看一下List的
一些其他基本的操作
首先我们看到的是setPos函数
fence函数用来去设置栅栏的位置
setPos指明了要去设置的位置
这个函数的核心其实是比较简单的
就是直接地将栅栏的位置fence
做相应的设置就可以了
但是需要注意的是
在设置位置的时候
要确保这个位置Pos
它是不是一个合理的取值
我们知道栅栏在列表中最左边的位置
是0号位置
而最右边的位置是在listsize这个位置
所以fence它的取值范围
应该是从0到listsize
因此在这里面我们在写Pos函数的时候
要注意去检查
只有当Pos的值属于这个合理的范围
我们才去设置fence
否则应该返回false
下面我们再来看一下getValue函数的实现
这个函数用来去获取
栅栏后面元素的值
并且把它记录在引用参数it中
在访问数组之前
我们首先要去判断一下
栅栏的后面是否存在元素
如果后面没有元素
那么getValue应该返回false
这个是可以通过去检查
栅栏是否出于列表的最后端来去实现的
也就是去判断fence是否和listsize重叠
在其他的一般情况下
我们可以非常简单地去访问数组
listArray在fence位置的数值
来去获得栅栏后面的元素
我们把这个值记录在参数it中
然后进行返回
这里我们可以看到
我们所实现的setPos函数
以及getValue函数
并没有涉及到复杂的循环语句
它们的时间复杂度都是Θ(1)
可见在数组这种实现方式里面
它可以非常高效地完成
读取任意位置上的元素
我们这节课就先讲到这里
下节课再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
