文档章节

Python中的数据结构和面向对象设计模式的算法

ricardohn
 ricardohn
发布于 2016/02/14 18:18
字数 3051
阅读 23
收藏 0
点赞 1
评论 0

第一章   导论

1.1  关于本书

    本书主要讲述的是基本的数据结构和算法,它们是组成大型和复杂软件产品的基本元素。如果要对数据结构有充分的理解,你需要做三件事情:第一,你必须知道信息在计算机内存中的存在和组织形式;第二,你必须熟悉不同数据结构中的信息的操作算法;第三,你必须理解不同数据结构的性能特性,使你在特定的应用中能够选择合适的数据结构,做出正确的决策。

    本书也阐述了面向对象的设计理念,对普遍常用的面向对象设计模式进行了强化。本书涉及的算法和数据结构都是Python语言的形式呈现的。大多数的数据结构都是基于类层次结构的,这样的设计使后面章节的程序基于前面章节的所出现过的程序。

1.2  面向对象的设计

    传统的软件设计模式基本上面向数据或者面向过程的设计模式。面向数据的设计理念强调的是信息的表现形式和局部及所属整体的关系;另一方面,面向过程的设计理念强调的是软件产品的动作过程,数据处于次要地位。

    现在普遍观点认为,在处理设计大型复杂软件产品的复杂性方面,面向对象的方法论比面向数据和面向过程都更有效率。这是因为数据和过程是同等重要的,对象的使用将数据和对数据的处理过程联系了起来。使用对象的主要优势在于,它提供了抽象和封装的方法。

1.2.1 抽象

    抽象可以看做是一种在抑制不相干的具体细节的同时对相关特性进行强调的机制。抽象的最大的好处是可以使程序员在思考要解决的问题时更加简单容易。

    例如,过程抽象使软件设计者只需思考要执行的动作步骤而不需要担心这些动作具体是怎么实现执行的。同理,数据抽象使软件设计者只需要考虑

程序中的对象以及对象之间的交互,不需要考虑对象是怎么实现的。

    抽象也有不同的级别层次,低层次的抽象会暴露更多的实现细节,而高此次的抽象会将之隐藏起来。

1.2.2  封装

    封装在软件设计中辅助设计者将信息强制隐藏起来。对象是将数据及数据的相应的操作过程进行封装。在某种意义上,对象将具体的实现细节在对象的使用者面前进行隐藏。

    这样做主要有两大好处:概念独立性和物理独立性。

    概念独立性是在对象的使用中将对象的实现隐藏的结果。因此在对象的使用过程中,无法对一个对象做出任何改动,这是由对象的实现过程决定的。这是非常令人满意的,这样的设计使得当对象的实现有改动时不必对使用该对象的代码做出修改。

    物理独立性,对象的行为是由对象本身决定的,不会受到外部实体的影响。因此,在对一个对象进行操作时,不会产生意外的副作用。

1.3  类层次和设计模式

    面向对象的程序设计不仅仅是简单的将一些数据和它们的处理过程封装到对象中。面向对象的方法也对对象的分类和不同类的对象之间的关系进行处理。

    用于表示对象类的关系的主要工具是派生,新的类可以从现有的类派生出来。使派生如此有用的是继承的概念,派生出来的类可以继承父类的特征。另外,继承的函数可以被重写,你也可以再派生类中自定义新的函数。

    本书的一大特点就是文中展现的所有的数据结构都是基于类层次结构的。实际上,类层次结构是对数据结构的一种分类。特定的抽象数据结构的不同的实现都来自于相同的抽象基类。相互关联的基类则是由抽象和封装了它们共同特性的一些类派生而来的。

    除了相关联的类分层设计外,有经验的面向对象设计者对不相关类之间的交互也会小心注意。在经验的帮助下,一个优秀的设计者能发现对象交互过程中的循环(重复)模式,通过使用这些模式,你的面向对象设计将会更加灵活和可重用。

    最近,程序员对这些通用设计模式进行了命名归类,这些设计模式的分类目录已经被编辑发布出来。

 

1.3.1  容器

    容器是一种可以将其他对象放入其中的对象。容器本身有容量,可以是满的或者空的;其他的对象可以插入容器或者从容器中取出。另外,可搜索容器是一种支持效率搜索操作的容器。

1.3.2  迭代器

    迭代器提供了一种对容器中的不同对象同一时间只能访问一个的方法。所有的迭代器都共享一个接口,隐蔽了用户所使用的容器的底层实现。

1.3.3  访客

    访客表示的是一种对容器中所有对象都可以进行的操作。所有的访客都共享同一个接口,并对容器隐藏所要进行的操作。同时,访客的定义是单独于容器的,因此,一个特定的访客可以在任何容器中使用。

1.3.4  指针

    指针表示的是在一个有序容器中某对象的位置。指针给使用者提供给一个方法来指定将要进行的操作位于什么位置,而不必了解该位置代表的什么东西。

1.3.5  适配器

    适配器可以将类的接口形式转换为其使用者所需要的的接口形式。这样使得非兼容接口的类在所需接口不一致的情况下仍然可以使用。

1.3.6  单例模式

    单例模式是一个类只能有一个实例。这样的类保证了只能有一个实例被创建,并提供了访问该实例的方法。


1.4    你需要知道的Python特性

    本书不是对编程基础的教学。本书的读者应该已经有一定的编程基础,并学过如何使用Python编写程序。那就表示,你已经清楚了Python的语法规则,知道如何编写Python语句来初步解决程序设计问题。接下来的内容将更充分的简述你所应该熟悉的Python程序设计的各个要点。


1.4.1  对象,值和类型

    你应该对对象是数据的抽象形式这样的概念感到舒心,一个对象有他的属性,例如:标示(一致性),类型和值。

1.4.2  命名和捆绑

    你应该理解对象名和对象本身之间的不同。具体就是,赋值语句将对象名和一个对象捆绑起来,而该赋值语句不会对对象本身的值做任何修改。

1.4.3  参数传递

    Python中的参数传递是引用传递。重要的是,当一个函数被调用时,函数定义中给定的形参名和函数调用中的实际参数指定的对象绑定。

1.4.4   类

    Python中的类封装了一组值和一组操作。类的值和操作以类的属性来表示。Python中的类定义了一个新的类型。类的实例被称为对象。

1.4.5   继承

    在Python中 ,类可以派生出其他类。派生类继承了父类的所有属性。另外,在派生类中可以对继承的属性进行重写,也可以自定义新的属性。你应该了解Python虚拟机是如何决定代码执行时调用特定的方法。

1.4.6   新型类 

    Python提供了两种风格的类:经典类和新型类。在这本书中,我们仅使用Python的新型类。新型类支持属性特性,并提供了满足局部优先排序和单调性约束的方法解析顺序。

1.4.7   其他特性

    本书也使用了Python的其他特性,如异常处理和生成器。你可以通过本书学到这些内容。

 


1.5   本书的章节组织



1.5.1   模型和渐进分析

    要分析一个算法的性能,我们必须了解计算机的模型。第2章主要展示了3种计算机模型,按展示顺序,精确程度递减,但是使用也更加简单。这些模型都比较相似,使用时要注意对算法的执行注意小心。

    接下来第3章主要讲的是渐进分析,这是非常有用的一项数学方法,因为它极大的简便了对算法的分析。渐进分析使我们不必对算法的具体执行特别关注,同时能得出普遍(大体)的结论。


1.5.2   基础数据结构

    当我们要实现一种数据结构时,我们首先要决定是否使用数组或链表作为底层的组织结构。因此,数组和链表有被称为基础数据结构。第4章也包含了多维数组和矩阵的内容。


1.5.3   抽象数据类型和类层次结构

    第5章介绍了抽象数据类型的概念。本书中讨论的所有的数据结构都是以各种抽象数据类型的实例的形式展现的。第5章也介绍了类层次结构,同时对相关的迭代器和访客的概念进行了阐述。

    

1.5.4   数据结构

    第6章介绍了堆栈,队列,双端队列的内容。第7章介绍了有序列表和排序列表。第8章介绍了散列法的概念,覆盖了许多不同的对象类型的哈希函数的设计,最后介绍了哈希表和散射表。

    树和搜索树的内容分别位于第9章和第10章。树是最重要的非线性数据结构之一。第10章包含多种树的遍历,包括深度优先遍历和广度优先遍历。第1

1章讲述了优选队列,第12章讲述了集合,多重集和划分。

    Python运行时间系统的必要组成部分是动态分配的存储池。第13章提出了许多用于实现垃圾回收的不同方法,在这个过程中,说明与动态存储分配相关联的实际开销。


1.5.5   算法

    相比于数据结构,最后三章更多关注于算法方面。第14章是不同算法模式的综述,通过引入一个抽象的问题求解的概念,我们展示了其相关的模式。第15章通过相似的方法引出了各种分类算法。我们通过一个抽象的分类器,展示了其相关的分类算法。

    最后,第16章简单介绍了图的概念和图的算法,本章结合前面章节讨论过的类层次结构和14章各种算法综合运用。


© 著作权归作者所有

共有 人打赏支持
ricardohn
粉丝 1
博文 76
码字总数 30236
作品 0
成都
《 Head First 》学习笔记:策略模式 (python实现)

学习<head first>,书中是用java 来实现,我用python比较多,所以在这里记下 用python实现的方法 。 书中策略模式的定义 : 策略模式 : 策略模式定义了算法族,分别封装起来,让它们之间可以...

Jbryan
2013/06/13
0
0
《大话设计模式》Python版代码实现

 上一周把《大话设计模式》看完了,对面向对象技术有了新的理解,对于一个在C下写代码比较多、偶尔会用到一些脚本语言写脚本的人来说,很是开阔眼界。《大话设计模式》的代码使用C#写成的,...

若虚道人
2014/08/14
0
2
python 与设计模式 ——工厂与单例

python 与设计模式 源码地址:[http://git.oschina.net/duoduo3_69/python_design_pattern][1] git checkout v001(这个版本与此篇博客相符) zarkpy里面运用了很多设计模式,以前一直很费解p...

duoduo3_69
2013/11/27
0
0
Python新式类 new init 单例模式与作用域(四)

1 新式类与旧式类 新式类拥有经典类的全部特性之外,还有一些新的特性,比如 发生变化,新增了静态方法,python3目前都采用新式类,新式类是广度优先,旧式类是深度优先 (2)类的方法 静态方法 类方...

善良小郎君
06/18
0
0
大数据分析技术:Python面试之理解__new__和__init__的区别

很多同学都以为Python中的init是构造方法,但其实不然,Python中真正的构造方法是new。init和new有什么区别?本文就来探讨一下。 我们先来看一下init的用法 上面的代码会输出如下的结果 那么...

加米谷大数据
07/12
0
0
23种设计模式(12):策略模式

定义:定义一组算法,将每个算法都封装起来,并且使他们之间可以互换。 类型:行为类模式 类图: 策略模式是对算法的封装,把一系列的算法分别封装到对应的类中,并且这些类实现相同的接口,...

LCZ777
2014/07/09
0
0
Android 网络编程 目录

Android 网络编程 目录 Android 网络编程1 Http协议 to be continued... Android 架构师之路 目录 Android 架构师之路1 UML图之用例图 Android 架构师之路2 UML图之类图 Android 架构师之路3...

香沙小熊
06/21
0
0
设计模式-Strategy Pattern

一、 策略(Strategy)模式 策略模式的用意是针对一组算法,将每一个算法封装到具有共同接口的独立的类中,从而使得它们可以相互替换。策略模式使得算法可以在不影响到客户端的情况下发生变化...

Start-up
2012/05/17
0
0
python 与设计模式 ——工厂与装饰者

python 与设计模式第二篇 添加了test.py,里面的单元测试有使用的方法。 源码地址:[http://git.oschina.net/duoduo3_69/python_design_pattern][1] git checkout v002(这个版本与此篇博客相符...

duoduo3_69
2013/11/27
0
1
JavaScript 中常见设计模式整理

开发中,我们或多或少地接触了设计模式,但是很多时候不知道自己使用了哪种设计模式或者说该使用何种设计模式。本文意在梳理常见设计模式的特点,从而对它们有比较清晰的认知。 JavaScript 中...

牧云云
05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

DUBBO 详细介绍

摘要: 主要核心部件: Remoting: 网络通信框架,实现了 sync-over-async 和 request-response 消息机制. RPC: 一个远程过程调用的抽象,支持负载均衡、容灾和集群功能 Registry: 服务目录框架...

明理萝
9分钟前
0
1
4 个快速的 Python 编译器 for 2018

简评:Python 和其他的解释型语言一样经常被吐槽性能不行,所以开发人员为了提升性能创建了不少编译器,本文则选取其中的四个做了基准测试。 Python 其实是一种相当快的语言,但它并不像编译...

极光推送
12分钟前
0
0
spring boot注册多个MQ服务器的问题

关于注册到多个MQ源的文章已经有很多了,这里记录一下声明queue的坑; 如果使用注册bean的方式声明queue,会导致声明的queue同时被注册到所有的MQ源上; //如果使用下面的声明方式,que...

placeholder
13分钟前
0
0
Java面试基础篇——第九篇:BIO,NIO,AIO的区别

现在IO模型主要分三类:BIO(同步阻塞IO),NIO(同步非阻塞IO),AIO()。 先来看看BIO。 1. BIO 服务端接受到请求后,要指派或新建一个线程去处理客户端的IO请求,直到收到断开连接的指令。这么做...

developlee的潇洒人生
18分钟前
0
0
@RequestMapping @ResponseBody 和 @RequestBody 用法与区别

1.@RequestMapping 国际惯例先介绍什么是@RequestMapping,@RequestMapping 是一个用来处理请求地址映射的注解,可用于类或方法上。用于类上,表示类中的所有响应请求的方法都是以该地址作为...

特拉仔
20分钟前
1
0
基于 HTML5 结合互联网+ 的 3D 隧道

前言 目前,物资采购和人力成本是隧道业发展的两大瓶颈。比如依靠民间借贷,融资成本很高;采购价格不透明,没有增值税发票;还有项目管控和供应链管理的问题。成本在不断上升,利润在不断下...

xhload3d
22分钟前
0
0
济南小程序热度分析

原文链接:http://www.jnqianle.cn/company/2072.html

tianma3798
23分钟前
1
0
大数据软件

beats 采集 kafka spark hive es grafana zeppelin

ArlenXu
25分钟前
0
0
Mac item2常用快捷键

标签 新建标签:command + t 关闭标签:command + w 切换标签:command + 数字 command + 左右方向键 切换全屏:command + enter 查找:command + f 分屏 水平分屏:command + d 垂直分屏:c...

说回答
28分钟前
0
0
mac常用软件

1.excel for mac http://www.pc6.com/mac/114205.html

小黑202
29分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部