《大学计算机基础》第3章-程序设计与数据结构(2014_11_29)【amj】【OK】

1、大学计算机基础大学计算机基础北京航空航天大学计算机学院2课程目录第6章求解显示，交互 （2学时）求解效率，优化和限制 （2学时）第5章求解的工程思维，规范 （2学时）第7章程序设计与数据结构 （6学时）第3章计算机与计算思维 （6学时）第1章第2章问题的抽象与建模 （4学时）问题的求解，算法及实现 （4学时）第4章3第3章 程序设计与数据结构数据与数据结构程序与程序设计语言3.4 程序控制结构3.3 Python的基本构成及操作3.5 函数、模块及文件3.6 Python中类的定义3.7 Python实现典型数据结构4本 章 重 点 n了解如何设计程序：程序结构n掌握数据、数据元素、数据项的概

2、念n了解数据的逻辑结构和存储结构概念上的联系与区别n掌握数据结构的定义及其三个组成部分n掌握使用Python的基础操作，对象、类型、表达式、程序控制结构，如何构建较大规模的程序n掌握如何在Python中定义“类”n掌握典型数据结构的定义，抽象数据类型及实现方法53.1 程序与程序设计语言u3.1.1 引例引例u3.1.2 程序与程序与程序设计语言程序设计语言u3.1.3 Python语言简介语言简介63.1.1 引例 n方法1：积分法 u在平面坐标系中有一个圆心在原点、半径r为1的圆，用矩形法计算第一象限的面积S，4*S就是整个圆的面积u圆面积也可以通过r2来求，因此可得=4*Su尝试不同的小

3、矩形宽度，以得到不同精度的值 【例例3.1】如何计算圆周率？方法2：随机法44正方形面积圆面积22rr正方形的面积倍的圆面积4122 yxu可以通过如下的方式计算的近似值u假设圆的半径为1，产生0到1之间的两个随机实数x和y。则（x,y）这个点是正方形中的一个点u如果 ，则点落在圆内u重复n次上述动作，并记录点落在圆内的次数mu通过 ，可得的近似值 122yxnm4n方法2： 随机法7两种方法的源程序及运行 方法1：源程序及运行方法2： 源程序及运行8什么是软件？n什么是软件？u国标中对软件（Software）的定义：与计算机系统操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据u

4、硬件是计算机系统的物质基础，软件则是计算机系统的灵魂u软件是用户与硬件之间的接口界面。用户主要是通过软件与计算机进行交流u软件是计算机系统设计的重要依据。为了方便用户，为了使计算机系统具有较高的总体效用，在设计计算机系统时，必须全局考虑软件与硬件的结合，以及用户的要求和软件的要求1运行时，能够提供所要求功能和性能的指令或计算机程序集合 2程序能够满意地处理信息的数据结构 3描述程序功能需求以及程序如何操作和使用所要求的文档 9软件=程序+数据+文档3.1.2 程序与程序设计语言n如何让计算机理解我们的意图，自动进行计算？ 我们需要事先编写程序，输入计算机中n什么是程序？u程序（Program）

5、是软件开发人员根据用户需求开发的，用程序设计语言描述的，适合计算机执行的指令（语句）序列 10算法数据结构程序解决问题的方法和步骤数据的组织形式u第一种结构化程序设计语言Pascal的发明者尼克劳斯沃尔斯（Niklaus Wirth）认为算法、语言与计算机程序11算法算法解决问题的方法和步骤程序程序计算机能够理解与执行的解决问题的步骤程序设计语程序设计语言言步骤书写的规范、语法规则、标准的集合是人和计算机都能理解的语言12程序设计语言n程序设计语言u程序设计语言（Programming Language）（或编程语言）是用于书写计算机程序的语言。它是软件的基础和组成u程序设计语言由单词、语句、

6、函数和程序文件等组成机器语言直接用二进制 无需翻译 效率高u使用繁琐汇编语言使用助记符 较易掌握u需要翻译u通用性差高级语言最接近人类语言 容易使用 易于移植u需要翻译u效率较低程序设计语言的鸿沟13计算机自然语言面向对象语言结构化描述语言汇编语言机器语言客观世界（问题域）语言的鸿沟n程序设计语言的鸿沟不同的程序设计阶段的问题计算机自然语言：需求分析结构图：概要设计流程图/PDL：详细设计汇编语言：编码？：测试客观世界（问题域） 分析与设计的鸿沟 设计的鸿沟 设计与实现的鸿沟高级程序设计语言：代码实现？：检验？：验证n不同的程序设计阶段的问题14程序设计方法n程序设计方法分为两大类u面向过程的

7、结构化程序设计方法 u面向对象的程序设计方法 151、面向过程的结构化程序设计方法u1969年，荷兰科学家EWDijkstra提出了结构化程序设计（Structured Programming）的概念强调从程序的结构和风格上来研究程序设计方法提倡利用三种基本结构（顺序结构、选择结构、循环结构）进行规范化程序设计，使程序具有模块化特征从程序要实现的功能出发进行程序设计，目的是使程序具有良好的结构框架1、面向过程的结构化程序设计方法16u1971年，瑞士联邦技术学院的Niklaus Wirth（尼克劳斯沃尔斯）教授推出了Pascal结构化程序设计语言，在计算机软件开发与编程人员中，兴起了学用Pas

8、cal语言进行结构化编程的高潮n结构化程序设计方法是一种传统的程序设计方法n由结构化分析、结构化设计和结构化编码三部分组成n其本质是功能的分解u将系统按功能分解为若干模块，每个模块是实现系统某一功能的程序单元。每个模块都具有输入、输出和过程等基本特性结构化程序设计方法的特点17u程序层次分明、逻辑清晰、功能独立u降低了开发程序的复杂性，增加了程序的可靠性u便于团队合作，快速而高效地完成项目开发u增强了系统的可维护性，使程序设计更加规范化 n结构化程序设计方法的特点u自顶向下、逐步求精复杂问题逐步分解为简单的子问题u划分功能模块整个程序由相对独立的、分层次的功能模块组成u结构化编程任何程序或算法

9、均以三种基本控制结构或嵌套基本结构实现面向过程的程序设计方法的不足18n面向过程的程序设计方法的不足u基于功能的设计方法难以适应系统需求的变化，功能变化则程序必须重新设计u数据和处理数据的过程分离为相互独立的实体，它只是封装了各个功能模块，而每个功能模块可以随意修改未加封装的数据。使得数据可靠性、安全性难以得到保障，不利于对程序的维护u当数据结构改变时，所有相关的处理过程都要进行相应修改，程序的可重用性差n新时期的新问题，以及软件产业的更高要求，迫使人们寻求更加科学、更加先进的程序设计方法 2、面向对象的程序设计方法 192、面向对象的程序设计方法 u面向对象程序设计（ Object-Orie

10、nted Programming，OOP）方法出现在20世纪80年代中后期 uOOP是建立在结构化程序设计基础上的u但它不再是从功能入手，而是从对象入手u面向对象思想是将现实世界中客观存在的事物即客体（如人、事物、地方等）视作为对象，而对象与对象之间的通信是通过发送消息和接收消息完成的面向对象的程序设计方法的核心概念 20nOOP采用的是一种结构模拟的方法，软件开发过程始终围绕建立问题域的对象模型来进行u用“类”描述具有相同属性特征的一组对象u用“封装”将对象的属性和行为分别用适当的数据结构和方法来描述，并将它们绑定在一起形成一个可供访问的基本逻辑单元u利用“继承”实现类与类之间的数据和方法的

11、共享n面向对象的程序设计方法的核心概念u对象（Object）u类 （Class）u消息（Message）u方法（Method）（1）对象（Object） 21n面向对象程序设计中的对象现实世界中的客体在应用程序中的具体体现，其中封装了客体的属性信息和行为方式，并用数据表示属性，用方法表示行为方式 n对象中的数据记录了客体的属性状态，方法决定了客体所能够实施的操作行为和与其它对象进行通信的接口方式n对象并非孤立存在，消息传递是对象之间相互联系的唯一途径。发送者发送消息，接收者通过调用相应的方法响应消息，这个过程被不断地重复，从而驱动整个程序的运转 对象概念的通俗示例22n现实世界（或者说系统）是

12、由“对象”构成的，对象之间是可相互区分的，每一对象都有唯一的标识（如用名字作为唯一标识）u例如一个个人n对象之间是相互独立的，对象有自己的状态，对象自己执行自身的动作而无需其他对象干预u 例如每个人都可以长高、行动、说话 n对象可为其他对象服务，或接受其他对象服务u例如当有人问其身高时，他可回答身高；问其体重时，他可回答体重；当他想问其他人事情时，他可向其他对象请求服务；. n 对象只有在接收到需服务的请求时，才去服务张三李四王五（2）类（Class） 23n人类在认知客观世界时，将众多的事物归纳、划分成一些类，这是经常采用的思维方法。分类所依据的原则是抽象 n类是具有相同属性和行为方式的一组

13、对象的集合，或者说，类是指对一组具有相同特征（包括属性、操作、方法、关系、行为）的对象的抽象描述。任何对象都是某个类的实例 n对象是系统运行时将类作为生成对象实例的模板，通过分配私有存储空间，然后对相应的属性赋初始值而创建的。这个过程在面向对象程序设计中称为“实例化”n类与对象的关系犹如模具与铸件之间的关系 类与对象概念的通俗示例24n类和对象?u有些对象具有相似的特性描述，组成一个“类”u类是对象的抽象或者称对象的“类型”，对象是类的实例u共性的内容 类（对象）名，类（对象）的唯一标识 类（对象）的属性 类（对象）的功能或者称函数各自独立运行的类的实例：对象同类对象的共性形式或者说对象的类型

14、：类王五张三各自独立运行的类的实例：对象对象（3）消息（Message） 25n消息：一个对象要求另一个对象实施某项操作的请求 n在一条消息中，需要包含消息的接收者和要求接收者执行某项操作的请求。但具体的操作过程由接收者自行决定，这样可以很好地保证系统的模块性n消息传递是对象之间相互联系的唯一途径。发送者发送消息，接收者通过调用相应的方法响应消息，这个过程被不断地重复，从而驱动整个程序的运转消息概念的通俗示例26n消息?u消息：消息是对象之间传递的内容，如指示、打听、请求 .。u消息是对象之间交互的唯一的内容u消息是 “对象.函数()”的调用和执行张三王五请问.(消息)您问的解答是(消息)Ca

15、ll 王五.回答身高()Execute 王五.回答身高() and Return “1.80m”（4）方法（Method） 27n面向对象技术中的方法：针对对象的属性的各种操作n方法是能执行特定功能的程序语句块，即过程或函数n方法是响应消息或事件的程序，或者说，是类或对象封装的函数的实现体，即程序段落n在OOP中，通常将一些通用的过程或函数编写好并封装起来，作为方法直接提供给用户调用面向对象程序设计n 面向对象程序设计计算机(OO)自然语言：问题描述OOA：需求模型OOD：设计模型OOP：编码OOT：测试客观世界（问题域）OOV：验证面向对象建模方法28程序设计语言要素n程序设计语言要素u一组

16、编程结构原语 Python原语：文字literal （如数字4.9以及字符串xyz）以及中缀运算符infix operator（如+及/）等u语法 定义哪些字符串以及符号可以组合表示一定的含义 如4.9 + 4.9是正确的语法，4.9 4.9则不是u静态语义 定义哪些语法正确的串具有含义 如序列4.9/xyz符合的语法，但是该序列的静态语义是错误的，因为字符串除数字没有含义u语义 语义是语法正确且无静态语义错误的字符串所关联的含义 编程语言要求每个合法的语句仅有唯一的含义29学习编程易犯的错误n语法错误u严谨的编程语言均会进行语法错误检查，如果含有任何语法错误，用户都无法执行程序n静态语义错误

17、u在允许执行程序前需要进行很多静态语义检查。而C和Python，则仅是做少量的静态语义检查n程序的执行并不是创建者的意图u它可能崩溃，也就是停止运行，给出示意u它可能继续运行，持续运行而不停止u它也可能完成运行，产生不正确的结果，甚至有可能是看似正确的结果30程序设计语言分类n低级语言与高级语言u前者（如机器语言、汇编语言）采用指令以及机器级别的数据对象进行编程，后者（如C、C+、Java、Python）采用语言设计者提供的抽象操作进行编程n通用编程语言与特定领域编程语言u看编程语言的原语操作是广泛可被使用还是面向特定的领域u如Adobe Flash可用于向网页页面添加动画和交互，但是我们不会

18、使用它构建股票投资分析程序n解释型编程语言与编译型编程语言u用解释型编程语言（如BASIC、 Python ）书写的程序由解释程序对源程序逐句翻译、逐句执行。效率相对较低，执行速度慢u用编译型编程语言（如C、C+、Java）编写的程序通过编译程序（一种翻译程序）将源程序整个编译成目标程序，然后通过链接程序将目标程序链接成可执行程序，即可脱离源程序和编译程序，单独执行，故效率高，执行速度快31常用程序设计语言n常用程序设计语言uFORTRAN 科学计算语言，第一个高级编译语言，主要用于科学计算（或称数值计算）uPascal 语言 第一个结构化程序设计语言， 1971年，瑞士联邦技术学院的Nikl

19、aus Wirth（尼克劳斯沃尔斯）教授推出语法非常严谨，类型丰富，层次分明，易读易写适于结构化程序设计教学uC 语言1972年，美国贝尔实验室的Kenneth Lane Thompson（肯汤普逊）和Dennis MacAlistair Ritchie（丹尼斯麦卡利斯泰尔里奇，C语言之父，UNIX之父）（两人于1983年获得图灵奖）开发32常用程序设计语言（Cont.1）优点兼有汇编语言（面向硬件）和高级语言（面向用户）的优点；结构化程序设计语言，适合于自顶向下，易开发，易理解，易维护；适于多种操作系统，如Windows、DOS、UNIX等，也适用于多种机型；小型，关键字少，有很多输入输出功

20、能以及丰富的标准库函数；有先进的数据结构和数据类型；可直接访问内存地址，能进行二进制位的操作；与硬件无关，可移植性强缺点运算符极为灵活，数目多、优先次序复杂，不利于初学者；类型检验较弱、类型转换也较随便，编译时难以发现编程错误；是面向过程的语言，不易代码复用，数据安全性无保障，很难控制大规模程序的复杂性33常用程序设计语言（Cont.2）uC+ 语言1980年，Bjarne Stroustrup（本贾尼斯特劳斯特卢普）博士（1993年获得了ACM Grace Murray Hopper奖）在贝尔实验室开始研究从C到C+的开发， 1985年推出了第一个可以实现的C+ 1.0版本C+支持过程化程序

21、设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格C+ 是C语言的超集，很好地支持OOP思想uJava 语言Java是Sun Microsystems公司在1995年推出的一种编程语言Java是一种简单、面向对象、平台无关（能运行于不同的计算机或不同的操作系统）、分布式、解释型、安全可靠、性能优异、多线程、动态的高级程序设计语言，特别适合在网络环境下的编程使用34常用程序设计语言（Cont.3）uC# 语言 C#（读作C sharp）是一种为生成在.NET Framework上运行的多种应用程序而设计的面向对象的编程语言简单、功能强大、类型安全语法表现力强，不到90个关键字，简单

22、易学。语法方面简化了C+的诸多复杂性，同时提供了很多强大的功能支持泛型方法和类型，从而提供了更出色的类型安全和性能u标记式语言HTMLHTML（Hypertext Markup Language ）即超文本标记语言是WWW（World Wide Web ）的描述语言。由Tim Berners-lee提出HTML是由HTML命令组成的描述性文本，HTML命令可以说明文字、图形、动画、声音、表格、链接等353.1.3 Python语言简介n通用的编程语言，可有效构建绝大多数程序，而无需对计算机硬件进行直接的访问n较弱的静态语义检查功能，对于高可靠性限制要求的程序、由较多人员长期维护和构建的程序而言

23、，它并不是最佳的选择n解释型语言，对于编程新生而言，Python提供的实时反馈非常有帮助，同时Python提供大量库以及扩展功能，便于使用36 什么是Python？37nPython是一种解释型的、面向对象的、带有动态语义的高级程序设计语言uPython程序，通常称为脚本script，是定义以及命令行的序列u尽管可能Python不像C或C+编译型语言一样快，但它简单易学，编写的程序清晰易懂，特别适于入门者学习nPython简单但功能强大u广泛用于系统管理工作（是许多Linux发行版的重要组成部分）uNASA在它的几个系统中既用Python开发，又将其作为脚本语言uYahoo!使用它管理讨论组u

24、Google用它实现Web爬虫和搜索引擎中的许多组件uPython也正应用于计算机游戏和生物信息等多个领域1、Python面世n 1989年，由Guido van Rossum（吉多范罗苏姆）在阿姆斯特丹完成，第一个公开版发行于1991年n Guido为了打发圣诞节的无趣，决心开发一个新的脚本解释程序，作为ABC语言的一种继承u使用Python作为语言的名字，因为Guido是英国幽默剧团Monty Python飞行马戏团的fansuABC是由Guido参加设计的一种教学语言，非常优美和强大，是专门为非专业程序员设计的Guido van Rossum38n目前，Guido在Google，主要从事

25、GAE/Python3.x方面的研究Python的版本nPython 2.0于2000年10月16日发布，主要是实现了完整的垃圾回收，并且支持UnicodenPython 3.0于2008年12月3日发布，此版不完全兼容之前的Python源代码n目前使用最广泛的版本是Python 2.7n最新的版本是Python 3.3.5（2014.3.13） 39Python哲学翻译与解释n翻译与解释uPython之禅 by Tim Petersu优美胜于丑陋（Python 以编写优美的代码为目标）u明了胜于晦涩（优美的代码应当是明了的，命名规范，风格相似）u简洁胜于复杂（优美的代码应当是简洁的，不要有复

26、杂的内部实现）u复杂胜于凌乱（如果复杂不可避免，那代码间也不能有难懂的关系，要保持接口简洁）u扁平胜于嵌套（优美的代码应当是扁平的，不能有太多的嵌套）u间隔胜于紧凑（优美的代码有适当的间隔，不要奢望一行代码解决问题）u可读性很重要（优美的代码是可读的）u即便假借特例的实用性之名，也不可违背这些规则（这些规则至高无上）41翻译与解释（Cont.）u不要包容所有错误，除非你确定需要这样做（精准地捕获异常，不写 except:pass 风格的代码）u当存在多种可能，不要尝试去猜测u而是尽量找一种，最好是唯一一种明显的解决方案（如果不确定，就用穷举法）u虽然这并不容易，因为你不是 Python 之父（

27、这里的 Dutch 是指 Guido ）u做也许好过不做，但不假思索就动手还不如不做（动手之前要细思量）u如果你无法向人描述你的方案，那肯定不是一个好方案；反之亦然（方案测评标准）u命名空间是一种绝妙的理念，我们应当多加利用（倡导与号召）422、Python的特色n容易上手u提供交互式环境u语法简洁 高级数据结构简洁地表达复杂的操作 语句组织依赖于缩进 参数或变量不需要声明n火力强大u易学但不简单，从桌面程序，到网络互联、图形处理、科学计算、实时控制，到处都有Python的身影u跨平台（Windows, Linux，Unix, Macintosh）u面向对象43Python的特色（Cont.1

28、）n快速开发uPython内建的高层次数据结构，以及动态类型和动态绑定，非常适合于快速应用开发uPython语法强调可读性，降低了程序的维护费用uPython支持模块和包，并鼓励程序模块化和代码重用n高效运行uPython可以编译执行，其运行效率接近C语言的运行速度，相同功能的代码运行速度约为C的90%，而同时Java的运行速度却只能达到C的50%44Python的特色（Cont.2）n丰富的库uPython 标准库已经很庞大。可帮你处理各种工作：正则表达式、文档生成、单元测试、线程、数据库、网页浏览器、CGI、 FTP、电子邮件、XML、XML-RPC、HTML、WAV文件、密码系统、GUI

29、（图形用户界面）、Tk和其他与系统有关的操作uPython开源、免费，在“百花齐放”式发展中，已经产生大量的高质量库，如wxPython、Twisted 、Pygame、 matplotlib 、scipy等45Python的特色（Cont.3）n可扩展、可嵌入u如果你需要你的一段关键代码运行得更快或者希望某些算法不公开，你可以把你的部分程序用C或C+编写，然后在你的Python程序中使用它们u可以把Python程序嵌入你的C/C+程序中，从而向你的程序用户提供脚本功能n解释性 uPython程序不需要编译成二进制代码，可以直接从源代码运行程序。使得Python程序更加易于移植46Python

30、解释器nPython是一门跨平台的脚本语言，Python规定了一个Python语法规则，实现Python语法的解释程序称为Python解释器 uCPython（ClassicPython，最原始Python的实现，需要区别于其他实现的时候才以CPython称呼；或用C语言实现的的Python）uJython （Java语言实现的Python ）uIronpython (面向.NET和ECMA CLI的Python实现 )uPyPy (使用Python语言写的Python )uZhpy（支持繁/简中文语句编写程序的Python语言） 473、谁在用Python？典型几个国外公司48谁在用Pyth

31、on？（Cont.1）典型几个国内公司49谁在用Python？（Cont.2）n豆瓣n新浪SAE （Sina App Engine）u开始支持Python了n搜狐邮箱u基于web.pyn游戏公司504、开发环境nIDLEuPython内置IDE（Integrated Development Enviroment），随Python安装包提供 nPyCharmu由著名的JetBrains公司开发，带有一整套可以帮助用户在使用Python语言开发时提高其效率的工 具，比如调试、语法高亮、Project管理、代码跳转、智能提示、自动完成、单元测试、版本控制。此外，该IDE提供了一些高级功能，以用于支持

32、Django框架下的专业Web开发，推荐！nUlipadu功能较全的自由软件，基于wxPython；作者是中国Python高手limodou，推荐！开发环境（Cont.）nEclipse+pydev u 收费的nEricu基于PyQt的自由软件，功能强大。全名是：The Eric Python IDE nPyScripteru使用Delphi开发的轻量级的开源Python IDE n其它编辑器uUltraEdit ，notepad+，editplus525、Python安装n官网/下载核心upython-2.7.6.msi 推荐！upython-3.3.

33、5.msin常用第三方库下载uPython package index (pypi): /pypiunumpy、 scipy 科学计算umatplotlib 二维、三维画图upygame 游戏开发uwxpython 图形用户界面开发udjango web开发uscikit-learn 数据挖掘 53 6、Python程序及结构n一般来讲，一个Python程序包括了多个模块文件。程序是作为一个主体的、顶层的文件来构造，配合有多个支持的文件n在Python中，顶层文件包含了程序的主要控制流程，是启动应用的文件n模块文件就是工具的库，这些工具用来收集顶层文

34、件使用的组件。顶层文件使用了模块文件中定义的工具，而模块又使用了其他模块所定义的工具n模块文件通常在运行时不需直接做任何事情，然后，它们定义的工具会在其他文件中使用。在Python中，一个文件通过导入一个模块来获得这个模块定义的工具的访问权，这些工具被认作是模块的属性54 Python程序及结构（Cont.）55n一个程序是一个模块的系统，它有一个顶层脚本文件a.py（启动后可运行的程序）以及多个模块文件b.py、c.py（用来导入工具库）n顶层脚本和模块都包含了自己编写的Python语句。Python标准库提供了一系列的预先编写好的模块563.2 数据与数据结构u3.2.1 数据类型及其本质

35、数据类型及其本质u3.2.2 数据结构数据结构u3.2.3 抽象数据类型抽象数据类型用计算机求解问题的过程57n编写解决实际问题的程序的一般过程u 如何用数据形式描述问题?即由问题抽象出一个适当的数学模型；u 问题所涉及的数据量大小及数据之间的关系；u 如何在计算机中存储数据及体现数据之间的关系? u 处理问题时需要对数据作何种运算?u 所编写的程序的性能是否良好?n上面所列举的问题基本上由数据结构这门课程来回答3.2.1 数据类型及其本质n什么是数据？u在计算机世界中，数据是所有能被输入到计算机中，且能被计算机处理的符号（数值、字符等）的集合u是计算机操作的对象的总称u是计算机处理的信息的某

36、种特定的符号表示形式n计算机中的数据是来自于客观世界的各种各样的信息，不仅包含整型、实型等数值型数据，还包括字符、图形、图像、声音、视频等非数值型数据n这些数据，都是以二进制数的形式存储在计算机中的n计算机是怎样对这些性质、形式各异的数据进行计算或处理的呢？58 数据类型n计算机计算或处理的数据，来源于我们在对客观世界各个领域里客观事物的一种认知基础上的观察和抽象n因此，人们将分类的思想引入编程语言，便产生了“数据类型（Data Type）”的概念u数据类型是一个值的集合以及定义在此集合上的一组操作的总称u基本思想：把某种语言所处理的对象按其属性的不同，分为不同的子集，对不同的子集规定不同的运

37、算操作59n人类在认识客观世界的过程中，采用了分类的方法u如：将世界分为生物和非生物两大类，生物又细分为动物、植物、微生物n分类是科学研究的基本方法和途径，是我们认识世界和改造世界的锐利武器60C语言的数据类型C语言的数据类型数值类型基本类型指针类型（pointer）字符类型（char）结构（struct）整型实型联合（union）文件（file）数组（array）枚举类型（enum）短整型（short）整型（int）长整型（long）单精度（float）双精度（double）空类型（void）构造类型 数据类型的本质（1）数据类型确定了值的范围u不同的数据类型有不同的取值范围u如整型（16

38、bit）的取值范围是-215（215-1），即-32768+32767；字符型的取值范围是：-128+128u数据若超出指定范围，计算就会出问题（溢出）61（2）数据类型确定了值的操作，不同类型有不同的操作u如：整型有取余运算，实型则没有u即使是同一种操作，对不同的类型可能内涵不同。如：1+2就是对应的二进制数相加；1+2.0先进行类型转换，然后才进行对阶、尾数相加、规格化 数据类型的本质（Cont.）（3）数据类型确定了值存储空间的大小u不同数据类型的数据占据的存储空间大小不同u如整型数据通常占据2Byte；字符型数据占据1Byte；单精度实型数据占据4Byte；双精度实型数据占据8Byte

39、u数据若超出指定范围，计算就会出问题（溢出）62（4）数据类型确定了值的存储方式u不同数据类型的数据在内存里的存储方式不同u如整型与实型值的存储方式截然不同u如十进制数12 整型数据：0000 0000 0000 1100（2个Byte） 实型数据：0100 0001 0100 0000 0000 0000 0000 0000（4个Byte） 在编程语言中为什么引入数据类型？（1）有助于程序设计的简明性和数据的可靠性u引入数据类型，明确了变量的取值范围和其上允许的基本操作，可以防止许多错误的发生u编译系统通过静态类型检查，可以发现程序中与数据类型有关的错误u也有利于程序员编写程序，理解和调试程

40、序63（2）有助于数据的存储管理u不同数据类型的数据占据的存储空间大小不同u对数据根据需要事先定义数据类型，则可以节约宝贵的存储资源（3）有利于提高程序运行效率u程序在编译时对数据的类型信息和操作进行检查，可有效避免程序在运行时操作越界和类型错误，提高了程序运行的整体效率3.2.2 数据结构64n计算机要处理的数据并不是杂乱无章的，它们一定存在内在的联系n只有弄清楚数据之间的本质的联系，才能使用计算机对大量的数据进行有效的处理【例例3.2】某电信公司的市话用户信息表。序号用户名电话号码用户住址街道名门牌号00001万方林3800235北京西路165900002吴金平3800667北京西路209

41、900003王 冬5700123瑶湖大道198700004王三5700567瑶湖大道200800005江 凡8800129学府大道5035【例3.2】必须弄清楚的3个问题65n使用计算机处理用户信息表中的数据时，必须弄清楚下面3个问题u这些数据之间有什么样的内在联系？数据的逻辑结构u数据在计算机中怎样存储？数据的存储结构 u对数据进行处理时需要对数据作何种运算? 数据的运算集合n对于待处理的数据，只有分析清楚这3个问题，才能进行有效的处理！ 1、什么是数据结构？1、什么是数据结构？u有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称之为一个数据结构u数据结构就是指

42、按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合u数据结构是相互之间存在着一种或多种关系的数据元素的集合u数据结构课程讨论计算机系统中数据的组织形式及其相互关系66数据结构概览67数据结构中的术语n数据结构中的术语u数据项（Data Item ）: 是数据的具有独立含义的不可分割的最小标识单位，数据项是对客观事物某一方面特性的数据描述 如【例3.2】表中的序号、用户名、电话号码等u数据元素（Data Element ）：是数据的基本单位，通常作为一个整体考虑和进行处理（又称结点、记录）。一个数据元素由若干数据项组成 如【例3.2】表中的

43、包含序号、用户名、电话号码等具体数值的每一行数据u 数据对象（Data Object）：是性质相同的数据元素的集合，是数据的一个子集。如【例3.2】表中的所有数据元素68【例3.2】中的数据项和数据元素69序号用户名电话号码用户住址街道名门牌号00001万方林3800235北京西路165900002吴金平3800667北京西路209900003王 冬5700123瑶湖大道198700004王三5700567瑶湖大道200800005江 凡8800129学府大道5035u这里序号、用户名、电话号码等项称为基本项，它是有独立意义的最小标识单位，而用户住址称为组合项，组合项是由一个或多个基本项或组合

44、项组成，是有独立意义的标识单位u每一行称为一个结点（或记录）记录），每一个组合项称为一个字段1个数据项1个数据元素5个数据元素4个数据项【例3.2】的数据结构70n数据的逻辑结构u除最前和最后的两个结点之外，表中所有其它的结点都有且仅有一个与它相邻、位于它之前的一个结点，也有且仅有一个与它相邻、位于它之后的一个结点u这些就是用户信息表的逻辑结构n数据的存储结构 u将用户信息表中的所有结点存入计算机时，若使用C语言设计程序，常用一个结构数组来存储整个用户信息表，每一个数组元素是一个结构，它对应于用户信息表中的一个结点u数据在计算机中的存储方式称为存储结构【例3.2】的数据结构（Cont. )71

45、n数据的运算集合u用户信息表可以有删除一个用户、增加一个用户和查找某个用户等操作。应该明确指明这些操作的含义。比如删除操作，是删除序号为5的用户还是删除用户名为王三的用户是应该明确定义的，如果需要可以定义两个不同的删除操作u为一批数据定义的所有运算（或称操作）构成一个运算（操作）集合 数据结构的例子线性表结构72【例例3.3】电话号码查询系统。u设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，(an, bn)，其中ai, bi(i=1，2n) 分别表示某人的名字和电话号码u本问题是一种典型的线性表问题。数据与数据成简单的一对一

46、的线性关系姓名电话号码陈四线性表结构数据结构的例子树形结构73【例例3.4】磁盘目录文件系统。u磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推u本问题是一种典型的树形结构问题，数据与数据成一对多的关系，是一种典型的非线性关系结构树形结构计算机中的目录结构74HBCDEFGAHGFECDBA树形结构特点结点间具有分层次的连接关系数据结构的例子网状结构75【例例3.5】交通网络图。u 从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构（图状结构）问题，数据与数据成多对多

47、的关系，是一种非线性关系结构佛山惠州广州中山东莞深圳珠海网状结构数据的逻辑结构和存储结构76n数据结构包括“逻辑结构” 和“存储结构”两个方面（层次）u 数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的 “关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构u逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示（形式定义）u存储结构是数据元素在计算机系统中的存储方式，是逻辑结构在计算机中的表示和实现体现了数据元素的物理空间关系，故又称为物理结构 2、数据的逻辑结构77 2、数

48、据的逻辑结构n从关系或结构分，数据的逻辑结构可归结为以下4种基本类型线性结构树形结构网状结构（图状结构）集合结构结构中的数据元素之间存在一对一的关系结构中的数据元素之间存在一对多的关系结构中的数据元素之间存在多对多的关系结构中的数据元素除了同属于一种类型外，别无其它关系数据的逻辑结构示例78学号姓名语文数学C语言14011001张三85549214011002李四92846414011003王五877473. 逻辑结构的形式定义79n数据逻辑结构是数据元素之间逻辑关系的描述n有两种表示方法：描述法和图示法（1）描述法u数据结构的形式定义是一个二元组： Data-Structure=(D，S)

49、其中：D是数据元素的有限集，S是D上关系的有限集u数据元素之间的关系：一般抽象为前驱与后继关系 即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁 （2）图示法80（2）图示法u图形要素：结点和有向线段结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作是一个结点有向线段：表示元素之间的关系 K iK hK jKi的前驱Ki的后继箭尾指向的结点是前驱箭头指向的结点是后继【例3.6】逻辑结构的表示方法81【例例3.6】逻辑结构的两种表示方法。u设某数据逻辑结构B=（K，R） K=k1, k2, , k9 R= ， u 画出该逻辑结构的图示，并确定哪些是起点，哪些是终点。

50、它是什么类型的逻辑结构？【例3.6】逻辑结构的图示法82K1K3K4K7K5K6K2K8K9网状结构833、数据的存储结构n数据的逻辑结构只是描述了数据元素之间的逻辑关系，是独立于计算机的，它与数据在计算机中的存储方式无关n如果将数据在计算机中无规律地存储，则数据元素在内存中难以迅速找到，将影响数据处理的结果和速度！n试想一下，如果一本英汉字典中的单词是随意编排的，这本字典谁会用！n对于一个数据结构B=（K，R），必须建立从结点集合到计算机某个存储区域M的一个映象，这个映象要直接或间接地表达结点之间的关系Rn数据元素在计算机中的存储方式称为数据的存储结构了解即可3、数据的存储结构84数据存储结

51、构n数据结构在计算机内存中的存储包括数据元素的存储和数据元素之间的关系的表示n元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和非顺序存储结构（链接存储、索引存储、散列存储）n一种数据结构可以根据需要采用多种不同的存储结构n数据的存储结构不同，解决问题的方法就有所不同，数据处理的效率也是不同的n存储器的特点：由地址连续的单元构成线性关系85（1）顺序存储结构n顺序存储结构：将逻辑上相邻的元素存储在物理位置相邻的存储单元中。通常借助于数组来实现n通常用于存储具有线性结构的数据。则数据元素在存储器中的相对位置正好反映了数据元素之间的逻辑结

52、构（关系）数据逻辑结构与物理结构完全统一n连续存放的数据元素在内存中容易找到K1K2K3K4逻辑结构030003010302030303040305030603070308K1K2K3K4物理结构物理结构（1）顺序存储结构86（2）链式存储结构n链式存储结构：对逻辑上相邻的元素不要求其物理地址相邻，元素之间的逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现（pointer）n元素在内存中不一定连续存放元素指针 结点元素指针（2）链式存储结构87链式存储结构的特点指针域：存放下一个结点的地址存储单元的地址即物理地址n链式存储结构特点u每个结点由两部分组成：一部分存放数据，另一部分存储指向

53、前件或后件结点的指针域u逻辑上相邻的结点物理上不必相邻u数据运算（插入和删除等）灵活88（3）索引存储结构n索引存储结构：给存储在内存中的数据元素建立一个索引表，表中存储一串指针，每个指针指向存放在内存中的一个元素（3）索引存储结构030003010302030303040305030603070308K1K2K3K41234索引表索引号 指针n通过查找索引表找到数据元素在内存中的位置n元素可以离散存放89（4）散列存储结构n散列存储结构：根据数据元素的“特点（关键字）”，按照特定的计算公式（哈希函数），计算出对应的值，然后把数据元素存放在以该值（哈希结果）为存储地址的存储单元中n查找时根据其

54、“特点”就可以计算出存储地址n例如欲将十进制数34和52存放在内存中，选取哈希函数为所存数据元素mod 10 取余数作为存储地址。34 mod 10余4，52 mod 10余2，则34和52分别存入存储单元4和2中散列存储结构示意图（4）散列存储结构联想：通过书的名字就能确定书的位置 数据结构的三个组成部分90n逻辑结构： 数据元素之间逻辑关系的描述 D_S=（D，S）n存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构n数据操作： 对数据要进行的运算逻辑结构与所采用的存储结构线性结构树形结构图状结构顺序存储结构链式存储结构复合存储结构逻辑结构存储结构 数据逻辑

55、结构的分类91n数据的逻辑结构分为线性结构和非线性结构两大类数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列数据逻辑结构层次关系图 逻辑结构与存储结构的比较92n数据逻辑结构与存储结构的比较1、存储结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题u存储结构着眼于结点在内存中的定位2、简单的逻辑结构可能与存储结构一致u例：线性逻辑结构与顺序存储结构3、利用存储结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定4、逻辑结构与存储结构是一个问题密不可分的两个方面u任何一个算法的设

56、计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构 4、数据结构的运算934、数据结构的运算u建立（Create）一个数据结构u消除（Destroy）一个数据结构u访问（Access）一个数据结构u插入（Insert）：在一个数据结构中增加一个新的结点u删除（Delete）：从一个数据结构中删除一个结点u查找（Search）（检索）：在一个数据结构中查找满足条件的结点u修改（Modify）：对一个数据结构（中的数据元素）进行修改u排序（Sort）：将一个数据结构中所有结点按某种顺序重新排列u输出（Output）：将一个结构中所有结点的值打印、输出3.2.3 抽象数据类型n利用计算机解

57、决实际问题的重要过程之一便是“抽象”u在程序设计中，数据和运算是两个不可缺少的因素。所有的程序设计活动都是围绕着数据和其上的相关运算而进行的u从机器指令、汇编语言中的数据没有类型的概念，到现在的面向对象程序设计语言中抽象数据类型概念的出现，程序设计中的数据经历了一次次抽象，数据的抽象经历了三个发展阶段94 从无类型的二进制数到基本数据类型的产生 从基本数据类型到用户自定义类型的产生 从用户自定义类型到抽象数据类型的出现 什么是抽象数据类型？n抽象数据类型（ Abstract Data Type ，ADT ）u抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算uADT的

58、定义仅是一组逻辑特性描述， 与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用u对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质u为什么要有抽象数据类型？一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型95抽象数据类型的形式化定义n抽象数据类型的形式化定义uADT的形式化定义是三元组：ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是对D的基本操作集96n抽象数据类型是数据类型的扩展和抽象u数据结构（数据对象D及其关

59、系S）u定义在数据结构上的基本操作和算法（P）n抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现抽象数据类型的一般定义n抽象数据类型的一般定义形式97ADT 数据对象： 数据关系： 基本操作： ADT u其中数据对象和数据关系的定义用伪代码描述u基本操作的定义是：()初始条件： 操作结果： 抽象数据类型的两个重要特征98n抽象数据类型的两个重要特征u数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征，其所能完成的功能以及它与外部用户的接口（即外界使用它的方法）u数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。如复数定义【例3.

60、7】定义抽象数据类型“复数”99ADT Complex 数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复数的实数部分, | e2 是复数的虚数部分 【例例3.7】定义抽象数据类型“复数”。基本操作：AssignComplex( &Z, v1, v2 )操作结果：构造复数 Z，其实部和虚部分别被赋以参数 v1 和 v2 的值。【例3.7】（Cont.）100DestroyComplex( &Z)操作结果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag( Z, &Imag