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

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

02A-4在线视频

下一节:02A-5

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

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

在明确了向量结构的

上述接口规范之后

我们就可以遵照这种规范来看一下

如何具体地 在C++语言的平台上

实现这样一种向量模板类Vector结构

那么这里我们讲一下

在大家可以下载到的讲稿中

你都可以去关注一下

这些对应结构和算法的链接

比如说这个链接

只要你的电脑是在线的

你就可以通过一次点击

直接从我们的课程服务器中打开

并且阅读对应的源代码

就这个例子而言

这里给出了Vector这种模板类的

详细的实现

课堂上 不可能把所有的细节

都展示出来

所以我们把它的主体框架给出来

我们来看一下

首先这里约定用int

来定义这里所说的秩这种概念

接下来 因为我们会首先采用

一种基本的扩容方式

它的初始容量需要设定

这里不妨取它的DEFAULT_CAPACITY

取作3 当然

这只是为了测试和演示

我们取非常小的一个数

在实际应用中呢

你完全可以取更大的一个数

那么下面是C++语言中

基本的一个模式

如果大家以前学过 固然很好

如果没有学过的话

我们也可以简单地来看一下

也就是 我们通过template这种方式

再给一个模板参数T

它的意思可以认为是

我们定义了一个Vector这样的模板类

其中的元素类型是什么呢?

可以是将来指定的任何名字

现在叫作T的类型

所以与其说它写的是一个类

不如说这个模板类

给的是一系列的类

你可以根据实际需要

直接地生成相应的Vector类

好 那么在这里头呢

我们有一些私有的

也就是封装和隐藏起来的变量

比如说 它内部会记忆

它到底有多少个元素

我们有一个_size 在内部

我们在前面加一个下划线来表示

以及它目前的容量

也就是加了下划线以后的_capacity

还有呢

包括真正存放元素的一个空间

我们可以看到这确实是

地址连续的一段空间

那么其它的内部函数

以及公开的接口函数

我们会在后边陆续介绍

我们来看一下它的原理

正像我们原来所说的

整个Vector结构是被封装起来

那么能供来自各种应用的用户

使用的操作接口有哪些呢?

是这些

这些就相当于

Vector结构的使用说明书

它告诉你这里提供了

哪些操作渠道 途径以及可能

用户呢 如果他感兴趣

固然可以把这个结构打开

去了解它是怎么实现的

如果不感兴趣

他完全可以按照说明书

通过这种接口规范直接使用

所以这里我们也可以看得出来

经过了这样地一个剥离之后

确实使得我们的应用和我们的实现

相互之间可以很好的分工

又同时很好的协作

那么具体内部怎么实现的呢?

我们这里可以看得出来

其实是开辟了一个

名字叫作_elem的数据区

它的容量至少要足以容纳

所存放的有效数据

对外而言的每一个元素

都通过某种形式转译为

内部这段数据区中的

实际上是这个有效的数据区中的

某一个元素

由此实现了

对内部数据项的封装

作为一种数据结构

与所有的类一样

Vector也首先需要解决

构造和析构的问题

我们来看一下

向量的默认的构造

实际上只需指明

初始的容量就可以了

如果没有指定

会按照默认的容量

指定一个数值

那么在内部的操作呢

其实就是通过new

申请一个长度为c

基本类型就是模板参数T的

一段连续的数据空间

在创建了这样一个空间之后

我们把这个空间的首地址

交给内部的_elem记下来

当然 这个时候虽然它有一定的空间

但是其中有效的数据

其实是没有的

所以这就是为什么

_size初始化是0

当然我们还有其它的一些构造的方法

比如说 如果已经有一组

以数组的形式存放的数据

我们也可以将其中

从lo到hi的这段区间

中的元素取出来

作为初始向量

我们可以看到

它是通过调用一个叫作

copyFrom()的内部接口实现的

同样地 它还重载了其它的一些形式

比如说 我们被复制的元素

可能不见得是来自于一个数组

而是来自于一个本身已经被封装了的向量

这也不要紧 我们可以从这个向量的

_elem区域中去读取出来

并且同样调用copyFrom()来做这件事

所以这里有区间的复制

也可以有对整个向量的一个克隆

那么析构呢

当然也是反过来的逆过程

只需要把这个曾经动态分配

获得的数据区域释放掉

归还给操作系统

所以我们这里的关键问题在于

copyFrom()这个接口如何地来实现

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

也许你还感兴趣的课程:

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