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

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

02A-3在线视频

下一节:02A-4

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

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

为获得向量ADT操作的

具体感受

不妨来看 这样一个具体的实例

最开始向量与

任何一个数据结构一样

初始化的时候

都是不包含

任何实质的内容的

我们称它是一个空的向量

那么接下来呢

如果我们调用

插入操作insert

然后这个意思是说

在rank为0的这个位置上

插入一个元素9

所以我们就会看到

向量的组成

将由空变成包含一个元素

也就是这个9

接下来我们继续

调用insert接口

在0号这个位置上

rank为0的这个位置上

插入一个元素4

所以4会插入在这

而原来的元素呢

比如说这个地方只有9呢

原来的元素呢 将会后移一位

同样地 我们也可以

调用插入接口

在rank为1的位置上插入5

这就是为什么

在这个位置上出现了5

而它的后继统一地

向后后移了一位

我们也可以调用put接口

这个接口的意思是修改

它会把当前

rank为1的那个位置上的元素

数值 由原来的5修改为2

我们也可以通过get这个接口

获取秩为某一特定值的元素

比如说 秩为2的那个元素

实际上就是

0 1 2这个位置上的9

我们看到这是第一次

我们有了一个

output 有一个输出

当然还包括其它的

比如说insert insert

包括remove

这是我们需要重点看一下的

我们说remove

这个接口的参数是2

这说明 它希望在原来这个向量中

将rank为0 1 2的这个元素

恰好它的数值也是2

把它剔除掉

所以剔除之后

会把这个被剔除的元素

作为输出 返回回来

同时它的所有的后继

与插入时候的操作的现象相反

会向前平移一个单元

包括其它的insert insert

当这个时候我们调用

size的时候

因为这里所包含的元素总共是6个

所以它返回6就不奇怪了

我们可以看到在整个

这个操作的过程中

向量都确实具有这么样一个特点

就是它在逻辑上

甚至在物理上

必然是彼此紧邻的排列的

所有的元素之间

没有任何的缝隙

接下来我们可以通过

disordered()这个接口

来检测这个向量的有序性

或者更准确地讲 它的无序性

我们在此前介绍bubble sort

算法的原理的时候

曾经指出

包括向量在内的序列

是否有序

当且仅当其中

是否存在紧邻的逆序对

那么这里总共有6个元素

共定义了5组紧邻对

其中有3组

也就是4和3

7和4、和9和6是逆序的

所以这就是为什么

它返回的是3

只要这个数值不是0

就说明它尚未构成有序的序列

好 对于这样的一个无序的向量

我们已经可以通过find接口

来查找其中特定的某个元素

比如说9

你可以看到9号元素

是位于rank为

0 1 2 3 4的位置

所以这就是为什么

我们这里需要返回是4

同样地 也可以查找

下一个比如说5

我们一眼扫去就会发现

5并不存在

这个时候

我们统一地约定

返回一个数值 是-1

这个-1肯定不是

一个合法的rank

表示查找失败

好 再接下来

我们可以通过sort这个接口

对整个向量排序

大家注意 无论是此前

所介绍的这些接口

还是后面我们要所介绍的接口

就目前而言

我们并不关心它的具体实现方法

我们关心的只是它的操作语义

这就犹如刚才所说地

这些规范其实就相当于

一个冰箱的使用说明

或者一辆汽车的驾驶规范

我们并不需要

现在就了解它的实现细节

我们只需要了解它的功能

所以从功能上讲

这个排序确实可以做到这一点

接下来再调用

disordered()这个接口

它已经没有任何逆序的紧邻对了

所以返回0

对于有序向量

我们可以通过另一套接口

也就是search来进行查找

比如说 可以首先通过search

然后引用9来查找

数值为9的元素

这个元素的rank为

0 1 2 3 4 5

所以这就是为什么

这里返回的是5

那么如果查找8会怎么样呢?

一眼望去 这里并没有8

当然我们简便的方法

是直接返回-1

但是我们后面会讲到

这种方法并不好

实际上 这里我们采用了另一种约定

比如说 对这个例子来讲

我们返回的是4

为什么是4呢?

因为我们这里约定

如果没有找到这个元素

我们要找的是不超过这个元素的

最大的那个元素的值

对这个例子而言

不超过8的最大的元素

实际上就是7

而这个7的秩是多少呢?

就是0 1 2 3 4

所以这是为什么返回的是4

同样 我们如果要去查找10的话

会返回不超过10的

最大的那个元素

也就是9的秩 也就是5

另一种特殊情况

就是我们查找一个全局都没有

而且小于全局的最小的

那个元素的数

比如说1 后面我们会讲到

我们会假设在这个-1的

rank这个位置上

有一个假想的哨兵

它的数值是负无穷

所以这里返回的

应该是在整体这些元素中

不大于1的

其实就只有那个

负无穷 那个元素的rank

也就是-1

这样一套约定

可以使得我们在语义上

更加的明确

使得我们在后续的操作过程中

可以便利地来搭建不同的算法

当然 还有一点

在有些时候

我们要查找的元素尽管有

但是它反过来却有很多次出现

比如说这个4 出现了两次

那这个时候我应该返回谁呢?

同样跟我们这里的语义

所定义吻合的是

我们要返回其中不超过4

这个目标元素的

最后边那个元素

所以如果有两个甚至多个的话

我们会取其中rank最大的那个元素

并且把它的rank给返回回来

对这个例子而言 也就是

0 1 2 2号元素

那么这种语义为什么要这么定义

需要在后边讲到相应的算法的时候

再去细细体会

最后 看一下这个uniquify()

对于一个有序的向量

我们在其中

把所有的重复的元素

比如说4都剔出掉

只保留一个拷贝

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-3笔记与讨论

也许你还感兴趣的课程:

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