当前课程知识点：数据结构（Data Structures） > 2. List > 2.1 Introduction of List > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
大家好
接下来我们将开始学习一个
基础的数据结构 List
也称为列表或者叫线性表
我们将会首先给大家介绍一下
List它的定义
然后给大家讲解一下
关于List它的具体描述方法
那么什么是List呢
我们先来看一个例子
在这个例子中
我们给出的是一个书目信息的列表
在列表中它的数据都具有相同的结构
都包含有序号 名称 作者 出版社等等
这些具有相同结构的数据排成一列
就构成了一个线性的列表
我们还可以列举出更多的现实应用中的
列表的例子
比如说学生列表 航班列表
歌曲列表 数字列表 单词列表等等
具体来说一个列表是由有限个数据项
排列而成的一个序列
在列表中每个数据项
我们称为它的一个元素
列表通常可以
形式化地定义为以下这个形式
就是有一对圆括号
然后里面包含有一组元素的序列
关于列表有一些约定俗成的术语
我们这里来学习一下
比如如果一个列表中
不包含有任何的元素我们就称为空列表
另外一个列表的长度
我们定义为列表中的元素的个数
此外 列表的开始位置通常称为列表的头
也就是head
而它的末尾位置通常称为它的尾
也就是tail
那我们看到List这样一个数据结构的时候
我们比较关注的是
可以在上面支持哪些操作
在实际的应用中
我们往往需要在列表的某个特定位置上面
进行插入或者删除
或者我们需要在这个列表中查找某个元素
也有可能我们需要查找
当前位置的下一个元素
或者是查找当前位置的上一个元素等等
那我们可以看出
在列表中访问的当前位置
是一个很重要的概念
因为它决定了我们在列表中
哪一个位置来进行操作
在这里我们用栅栏
来去形象地描述这个位置
比如在下面这个例子中
我们用一个短竖线去表示一个栅栏
栅栏所处在的位置
就是我们进行数据操作的位置
栅栏可以是位于任何的两个相邻元素之间
它也可以处于两端的位置
我们通过一些例子来给大家展示一下
栅栏是如何发挥作用的
在这个例子中List它有三个元素
栅栏处于第一个元素和第二个元素之间
当我们要在当前位置插入元素99的时候
会变成下面这个样子
99将添加到栅栏后面的位置
当我们要在当前位置删除一个元素的时候
会删除栅栏后面的元素
当我们获取当前位置的元素的值的时候
将会返回栅栏后面的32
最后我们来看一下
如何通过程序去描述List这样一个数据结构
我们可以定义一个List抽象类
这个类里面有一个模板参数Elem
它用来去描述列表中元素的数据类型
我们为每个需要实现的操作
将会定义一个抽象函数
首先是setPos函数
这个函数用来去设置栅栏的位置
其中参数Pos指定了栅栏的具体位置
然后是insert函数
用来在栅栏后面插入一个元素
参数e是表示要插入的元素
还有就是remove函数
用来删除栅栏后面的元素
并且把这个元素的值记录在参数e中
最后是getValue函数
它用来去获取栅栏后面的元素的值
并且把它记录参数e中
通过以上这一组操作
我们就可以实现对列表中
任意位置的元素的插入 删除以及访问
好的 这节课我们就介绍到这里
下节课我们再见
-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
