数据结构——C语言描述概论学习教案.pptx

数据结构——C语言描述(miáoshù)概论1.1什么是数据结构
1.1.1数据和数据元素
数据（data）是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储和加工处理。可以说，数据是计算机程序加工的“原料”。目前，象图像、声音、视频等都可以通过编码而由计算机处理，因此它们也属于数据的范畴。
数据元素（dataelement）是数据的基本单位，通常在计算机程序中作为一个(yīɡè)整体进行考虑和处理。数据元素也称为元素、结点或记录。有时，一个(yīɡè)数据元素可以由若干个数据项（也称字段、域），数据项是数据不可分割的最小单位。1.1.2数据(shùjù)对象和数据(shùjù)类型
数据(shùjù)对象（dataobject）是性质相同的数据(shùjù)元素的集合，它是数据(shùjù)的一个子集。例如，整数数据(shùjù)对象是集合N={0，±1，±2，±3，…}；大写字母字符数据(shùjù)对象是集合C={‘A’，‘B’，…，‘Z’}。要注意的是，计算机中的整数数据(shùjù)对象集合N1应该是上述集合N的一个子集，N1={0，±1，±2，…，±maxint}，其中maxint是依赖于所使用的计算机和语言的最大整数。
数据(shùjù)类型（datatype）是计算机程序中的数据(shùjù)对象以及定义在这个数据(shùjù)对象集合上的一组操作的总称。例如，C语言中的整数类型是区间[-maxint，maxint]上的整数，在这个集合上可以进行加、减、乘、整除、求余等操作。
1.1.3数据结构
数据结构（datastructure）是指数据对象以及(yǐjí)该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。
数据元素的组织形式一般包含下列内容：
⑴数据元素之间的逻辑关系，也称为数据的逻辑结构。数据的逻辑结构通常有下列4类（见图1.1）：
①集合：其中的数据元素之间除了“属于同一个集合”的关系以外，别无其他关系。
②线性结构：其中的数据元素之间存在一对一的关系。
③树型结构：其中的数据元素之间存在一对多的关系。
④图状结构（或称网状结构）：其中的数据元素之间存在多对多的关系。数据结构可以理解为：按某种逻辑关系组织起来(qǐlái)的一批数据，应用计算机语言，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。数据结构(shùjùjiéɡòu)的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构(shùjùjiéɡòu)。数据的存储结构可采用以下4种基本的存储方法得到：
⑴顺序存储方法
⑵链接存储方法
⑶索引存储方法
⑷散列存储方法
上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行(jìnxíng)存储映象。同一种逻辑结构，若采用不同的存储方法，则可以得到不同的存储结构。1.2为什么要学习数据结构?
1.2.1学习数据结构的重要性
算法+数据结构=程序
1.2.2数据结构的应用举例
例1.2电话号码的查询(cháxún)问题。
要求编写一个电话号码的查询(cháxún)程序。对于任意给出的一个姓名，如果该人留有电话号码，那么就找出他的电话号码；否则就指出该人没有电话号码。/例1.3n个城市之间铺设光缆的问题。
假设需要在n个城市之间铺设光缆，并且任意两个城市之间都可以铺设。大家知道，在n个城市之间只要铺设n-1条光缆，即能将这n个城市连成网络，只是由于地理位置的不同，所需经费也不同，问题是采用什么样的设计方案能使总投资(tóuzī)最省。
这个问题的数学模型是如图1.3（a）所示的“图”，图中“顶点”表示城市，顶点之间的连线及其上面的数值表示可以铺设的光缆及所需经费。/1.3算法和算法分析
1.3.1什么是算法?
由于数据的运算是通过算法来描述的，因此，讨论算法是数据结构课程的重要内容之一。
算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个(yīɡè)或多个操作；此外，一个(yīɡè)算法还具有下列5个特性：
1、有穷性
2、确定性
3、可行性
4、输入
5、输出程序与算法的异同
在一个算法中，有些指令可能重复执行，因而指令的执行次数可能远远大于算法中的指令条数。由有穷性和可行性得知，对于任何(rènhé)输入，一个算法在执行了有限条指令后一定要终止，而且必须在有限时间内完成。因此，一个程序如果对任何(rènhé)输入都不会产生无限循环，则它就是一个算法。
尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是