数据结构（c语言版上）清华大学出版社ppt

《数据结构（c语言版上）清华大学出版社ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构——C语言版清华大学出版社2009年9月第1章概论什么是数据结构为什么要学习数据结构算法和算法分析1.1.1数据和数据元素数据（data）是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储和加工处理。1.1什么是数据结构数据——在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。如图像、数、字符、声音、视频等都可以通过编码而由计算机处理，因此它们也属于数据的范畴。是数据的基本单位。通常在计算机程序中作为一个整体进行考虑和处理。数据元素也称为元素、结点或记录。一个数据元素可以由若干个数据项（也称字段、域

2、）组成，数据项是数据不可分割的最小单位。数据元素（dataelement）：数据对象（dataobject）：是性质相同的数据元素的集合，它是数据的一个子集。例如，所有的“数”构成了数据集合，而正整数集合N={1，2，3，…}是“数”的数据对象；所有的字符是数据，大写字母集合C={‘A’，‘B’，…，‘Z’}是该数据的数据对象。1.1.2数据对象和数据类型要注意的是：计算机中的正整数数据对象集合N1应该是上述集合N的一个子集，N1={1，2，…，maxint}，其中maxint是依赖于所使用的计算机和语言的最大整数。数据类型（datat

3、ype）是计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。可以看作是数据结构的实现。例如，C语言中的整数类型是区间[-maxint，maxint]上的整数，在这个集合上可以进行加、减、乘、整除、求余等操作。数据结构（datastructure）是指数据对象（集合）以及该数据对象集合中的数据元素之间的相互关系的集合（即数据元素的组织形式）。一组数据元素和一组运算（关系）两个集合组成的集合1.1.3数据结构根据数据元素之间关系的不同，数据结构分为两大类：线性结构非线性结构①集合：数据元素之间除了“属于同一个集合”的关系以

4、外，别无其他关系。②线性结构：数据元素之间存在一对一的关系。③树型结构：数据元素之间存在一对多的关系。④图状结构（或称网状结构）：数据元素之间存在多对多的关系。⑴数据元素之间的逻辑关系，也称为数据的逻辑结构。是数据元素之间抽象化的相互关系。是用户所看到的数据结构，是面向问题的，它不考虑数据的存储。数据的逻辑结构通常有下列4类：⑶数据元素之间的运算（关系）：对数据元素施加的操作，有时也直接称为数据的运算或操作。⑵数据的物理结构：又称存储结构。是数据的逻辑结构在计算机存储器内的表示（又称映象）。它属于具体实现的视图，是面向计算机的。例1.1

5、学生成绩表（表1.1）是一个数据结构。表1.1学生成绩表(每行是一个数据元素)学号姓名计算机导论高等数学普通物理平均成绩04081101陈小洁8090858504081102马丽丽7568787404081103林春英8278667504081104王澄娟90859389┆┆┆┆┆┆04081150张吉祥70887578数据结构可以理解为：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。数据结构主要研究什么？（或者说数据结构的研究对象是什么？）数据结

6、构的内容可归纳为三个部分：按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。逻辑结构存储结构运算集合上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映象。同一种逻辑结构，若采用不同的存储方法，则可以得到不同的存储结构。数据的存储结构（4种基本的存储）⑴顺序存储方法⑵链接存储方法⑶索引存储方法⑷散列存储方法算法+数据结构=程序1.2为什么要学习数据结构?1.2.1学习数据结构的重要性数据结构是计算机专业的专业基础课。它主要讨论在软件开发

7、中如何进行数据的组织、数据的表示和数据的处理。它不仅为操作系统、编译原理、数据库系统、计算机网络等后续课提供必要的知识，而且也为学习者提供必要的技能训练。例1.2电话号码的查询问题。要求编写一个电话号码的查询程序。对于任意给出的一个姓名，如果该人留有电话号码，那么就找出他的电话号码；否则就指出该人没有电话号码。1.2.2数据结构的应用举例例1.3n个城市之间铺设光缆的问题。假设需要在n个城市之间铺设光缆，并且任意两个城市之间都可以铺设。大家知道，在n个城市之间只要铺设n-1条光缆，即能将这n个城市连成网络，只是由于地理位置的不同，所需经

8、费也不同，问题是采用什么样的设计方案能使总投资最省。这个问题的数学模型如下页所示的“图”，图中“顶点”表示城市，顶点之间的连线及其上面的数值表示可以铺设的光缆及所需经费。1.3算法和算法分析1.3.1什么是