当前课程知识点:Data Structures and Algorithm Design Part I >  02.Vector I >  A.Interface+Implementation >  02A-2

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

02A-2在线视频

下一节:02A-3

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

02A-2课程教案、知识点、字幕

所谓的向量

实际上是C++

等高级编程语言中

数组这种数据组织形式的

一个推广和泛化

我们都知道 实际上

在这些高级程序设计语言中

所谓的数组

实际上就是一段

连续的内存空间

它被均匀地划分为若干个单元

而每一个单元

都与0到n之间的

某一个整数编号

相互彼此对应

我们可以说

第0号单元或者元素

或者第1号元素、第2号元素

以及到最后的实质

第n-1个元素

这里我们也同样延用

我们此前已经约定的习惯

虽然最后这个第n个元素

实际上未必存在

我们还是把它虚拟地放在这儿

作为哨兵

以帮助我们对很多问题的思考

并且使得我们很多算法的实现

能够得以简化

既然每一个这样的元素

都与这些编号是一一对应的

所以反过来

我们通过合法区间内的编号

都可以唯一地来指代

并且访问对应的那个元素

确实如此

我们一旦知道

这个元素的下标i

就可以从A

也就是这段存储区域的

首地址出发

再向后

以s作为间隔 去数出i步

就可以得到某一个特定的单元

正因为所有这些元素的物理地址

可以按照这样一个

线性的方程来确定

所以我们也称之为

linear array

线性数组

那么向量呢

我们可以认为是

数组的抽象与泛化

它同样是由一组抽象的元素

按照刚才的线性次序封装而成的

具体来说 其中的每一个元素

依然与0到n之间的

一个合法的整数

是一一对应的

只不过在这里

我们更倾向于

把这种整数称作是

秩rank

所以原来通过下标i

进行访问的方式在这里

就可以被推广而成

是通过秩来访问

这种方式叫作

call-by-rank

也叫循秩访问

另外在向量中

元素的类型

已经得到了拓展

不限于是某一种

特定的基本类型

也因为如此

它的所有操作、管理

包括维护都更加的简化

可以通过统一的接口来完成

相应地 也会更加安全

避免一些非法和歧义的操作

同时呢 也正因为它本身

已经做了很好的封装

也可以便捷地

参与更加复杂的

一些数据结构的定制以及实现

按照抽象数据类型的规范

向量结构必须提供

一系列的操作接口

可以通过这些操作接口

对向量做各种操作

同时也只能通过这些操作接口

对向量进行操作

这里的接口功能非常的丰富

我们在后续分别介绍

它们的实现的时候

自然会介绍它们的具体含义

比如说 与其它的数据结构一样

向量也可以看作是

一组元素的集合

所以这个size

实际上返回的是

其中元素的总数

我们称之为

这个数据结构的规模

我们也可以从中取特定的元素

也可以修改其中特定的元素

甚至插入或者是删除某个元素

我们也可以判定一下

其中的元素

是否已经有序排列

如果没有有序排列

可以调用相应的接口

使之有序排列

我们也可以在它

尚未有序排列的时候

按某种算法

找到其中特定的元素

也可以在已经有序的前提下

按照某种方式

来找到其中的元素

当然为了展示一些算法的实现

我们也附加了一些其它的功能

比如说能够在

无序和有序的情况下

分别剔除

这个数据集中的重复元素

最后也是非常重要的一个接口

就是如何对这个数据集中的元素

逐一地进行枚举

并且访问一遍

我们称之为遍历

Data Structures and Algorithm Design Part I课程列表:

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--(a)计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-(xd):LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

02A-2笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。