数据结构与算法第一章.pptx

数据结构与算法生命学院范军

课程教材及参考书 教学用书：数据结构（C语言版）徐孝凯，贺桂英编清华大学出版社，2004年参考书：1．数据结构，许卓群，张乃孝，杨冬青，唐世渭，高等教育出版社，1987年2.数据结构–C++与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，1998年3．数据结构(C语言版），严蔚敏、吴伟民，清华大学出版社，1997年4.数据结构与算法，王若梅等著，中山大学出版社，2000年5.C语言程序设计谭浩强清华大学出版社

第一章概论1.1《数据结构》课程研究的内容1.2《数据结构》课程的发展历史1.3基本概念和术语1.4数据类型的表示与实现1.5算法和算法分析

如今．计算机已深入到人类社会的各个领域。计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。（数值计算？）与此相应．计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据。而随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂，这就给程序设计带来一些新的问题。为了编写出一个“好”的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。这就是“数据结构”这门学科形成和发展的背景。1231.1《数据结构》课程研究的内容

什么是程序、软件？N.沃思（NiklausWirth)教授提出：程序=算法+数据结构以上公式说明了如下两个问题：12345算法的选择依赖于作为基础的数据结构（数据结构→算法）。软件=程序+文档（软件工程的观点）数据上的算法决定如何构造和组织数据（算法→数据结构）。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其关系和操作的学科。它是一门主要研究怎样合理地组织数据，建立合适的数据结构来提高计算机执行程序所用的时间效率和空间效率的科学。它的主要研究内容为：数据的逻辑结构--数据关系之间的逻辑关系数据的存储结构--数据的逻辑结构在计算机中的表示操作算法--插入、删除、修改、查询、排序等

数据结构的应用示例例1电话号码簿查询系统研究目的：构造一个可以多种方式查询的电话号码查询系统。研究内容：如何建立一个可通过姓名，拼音，号码，分组进行多角度查询的电话号码查询系统如何兼顾多种查询的查询表的存储结构以及相关的关联操作

采用姓氏索引表的存储结构：查找过程是先在索引表中查对姓氏，然后根据索引表中的地址到电话号码登记表中核查姓名，这样查找登记表时就无需查找其它姓氏的名字了。因此，在这种新的结构上产生的查找算法就更为有效。

21在图书馆内每本书都有多种信息条目所组成的书目信息卡。在书目自动检索系统中的主要操作便是按照某个特定要求(如给定书名、作者、分类号等)对书目文件进行快速、准确地查询。每一本书都有惟一的一个登录号，但不同的书目之间可能有近似甚至相同的书名，或者有相同的作者名，或者有相同的分类号。3例2图书馆的书目检索系统自动化

研究目的：书目自动检索系统中的主要操作便是按照某个特定要求(如给定书名、作者、分类号等)对书目文件进行快速、准确地查询。研究的内容：如何构建一个检索效率高的书目信息数据库？（顺序存储？链接存储？顺序存储？索引存储？）如何对这个数据库进行高效率的检索、维护和管理操作？（索引查询、分组查询、模糊查询、关联查询、关键词查询）

如将这些信息卡片按特定的分类编排，：如按书名编排的、有按作者编排的、还有按分类编排的，等等。这样计算机按作者的要求查找起来就更加迅速。

图书馆的书目自动检索系统设计：建立所处理的基本数据（数据元素）并选择合适的数据元素类型：每本书由（登录号，书名，作者，出版社,分类号)组成；设计并建立数据元素间的关系（逻辑结构）：建立一个按登录号顺序排列的书目表和按书名、作者和分类号顺序排列的索引表；设计所需的操作：一组作用在这些表上的运算（查询、插入、修改等）；设计数据的存储（存储结构）：怎样存储这些数据及其关系使得上述操作容易实现。

例3人机对弈问题(博弈树）No.1计算机之所以能和人对奕是因为有人将对奕的策略事先己存入计算机。并且以某种格式存储在计算机中。因此，在对奕问题中，实际上是计算机根据对奕过程中可能出现的棋盘状态在存储的对策中检索出最佳的“步骤”。No.2若将从对奕开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到—‘棵倒长的“树”。“树根”是对奕开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对奕的过程就是从树根沿树枝到某个叶子的过程。

研究目的：设计一个能应对各