当前课程知识点:Data Structures and Algorithm Design Part I >  02.Vector I >  B.extendable_vector >  02B-1

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

02B-1在线视频

下一节:02B-2

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

02B-1课程教案、知识点、字幕

欢迎回到数据结构的课堂

在上一讲中

我们首先介绍了ADT的规范

并且基于这种规范

给出了向量的接口定义

我们也实现了

作为一个数据结构而言

最最基本的构造与析构接口

与所有的数据结构一样

向量也可以认为是

一组数据项的集合

换而言之

它首先必须能够

自适应地在规模上

适应其中所包含的

元素个数的变化

这也就是为什么这一节

要集中讨论它的可扩充性能

向量天生

并不具有这种性能

我们需要采取一些策略

而且需要采取聪明的策略

的确 就目前的设计方案而言

我们的向量并不具备

可扩充的性能

究其原因在于

它采用的 实际上是所谓的

静态空间管理的策略

具体来说

它实际上在内部

只不过是设置了一个

私有的数组

这个数组所占有的

那段连续的地址空间

会被用来存放若干个

对外界而言可见的

或者是有效的元素

而这些元素的总数 或者说它们

所占用的逻辑空间的数

我们用_size来表示

而整个物理空间的大小

是由_capacity来确定的

这里的问题是

_capacity一旦确定

按照目前的方案

它就将一成不变

而这样一种策略

显然存在明显的不足

这种不足

体现在两个方面

第一 是有可能会出现

所谓的上溢overflow

也就是说

随着有效元素(个数)的增加

总有一天有这样的可能

使得整个这个element

所占用的物理空间

已经不足以存放

需要存放的元素组

尽管在这个时候

在系统的其它的部分

仍然有足够多的空间

可以用于存放这些元素

但是

限于_capacity是固定的

我们不能直接做到这一点

另一种情况呢

虽然不是很严重

但是 也是会造成一定的

空间的效率低下

我们称之为下溢

underflow

具体来说 就是

有可能我们开辟了一个

比较大的空间

但是在整个

这个数据结构的生命期内

真正存放于其中的数据

却寥寥无几

从而使得我们有一个指标

叫作装填因子

会非常非常的小

这个装填因子

其实就是 我们的有效元素个数

也就是_size 去除以

可用于存放元素的空间总数

也就是_capacity

我们也可以理解成是

这个空间的利用率

它有可能不到一半

甚至远远地低于一半

那么在这种时候

空间效率非常低下

很遗憾

如果我们坚持采用这样一种

固定容量的策略

我们在实际的一般应用环境中

很难在事先就预测到

我们需要用多少空间

也就是说 这种空间不足

以及空间浪费的情况

都有可能发生 甚至经常发生

那么有没有什么好的办法

可以使得向量

可以自适应地 根据实际需要

来动态地调整自己的容量呢?

而且这种调整的过程

既能保证足够

同时又不致使得

因为开辟的空间过多

而导致空间效率的低下

我们说是可以的

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

02B-1笔记与讨论

也许你还感兴趣的课程:

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