《《数据结构概论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构概论》PPT课件.ppt（38页珍藏版）》请在金锄头文库上搜索。
1、数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院第第 1 章章 数据结构概论数据结构概论1.1 1.1 数据结构的概念数据结构的概念1.2 1.2 数据结构的抽象形式数据结构的抽象形式 1.3 1.3 作为作为ADTADT的的C+C+类（自学）类（自学）1.4 1.4 算法定义算法定义1.5 1.5 算法性能分析与度量算法性能分析与度量本章的基本内容是：本章的基本内容是：数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院学习要求理解基本概念并能进行区分比较理解基本概念并能进行区分比较理解算法的定义与算法的五个特性理解算法的定义与
2、算法的五个特性掌握简单的时间复杂度估计和空间复杂度掌握简单的时间复杂度估计和空间复杂度估计方法估计方法掌握用掌握用C+语言编写程序的基本技术语言编写程序的基本技术数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院1938年出生，年出生，25岁毕业于加州理工岁毕业于加州理工学院数学系，博士毕业后留校任教，学院数学系，博士毕业后留校任教，28岁任副教授。岁任副教授。30岁时，加盟斯坦岁时，加盟斯坦福大学计算机系，任教授。从福大学计算机系，任教授。从31岁岁起，开始出版他的历史性经典巨著：起，开始出版他的历史性经典巨著：The Art of Computer Prog
3、ramming他计划共写他计划共写7卷，然而出版三卷之后，卷，然而出版三卷之后，已震惊世界，使他获得计算机科学已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年界的最高荣誉图灵奖，此时，他年仅仅36岁。岁。数据结构的创始人数据结构的创始人数据结构的创始人数据结构的创始人克努思克努思克努思克努思数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院1.1 数据结构的概念数据结构的概念1.1.1 数据结构举例数据结构举例计算机求解问题计算机求解问题: 问题问题抽象出问题的模型抽象出问题的模型求模型的解求模型的解问题问题数值问题、非数值问题数值问题、非数值问题
4、数数 值值 问问 题题数学方程数学方程 非数值问题非数值问题数据结构数据结构数据结构是研究数据结构是研究非数值问题非数值问题中计算机的中计算机的操操作对象作对象以及它们之间的以及它们之间的关系和操作关系和操作的学科。的学科。数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院例例1 选课问题选课问题表结构表结构完成什么功能完成什么功能?各表项之间是什么关系？各表项之间是什么关系？1.1 数据结构的概念数据结构的概念学生表学生表课程表课程表数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院例例2 选课问题选课问题图结构图结构如何表示学
5、生选课的情况？如何表示学生选课的情况？1.1 数据结构的概念数据结构的概念学生学生( (学号学号, ,姓名姓名, ,性别性别, ,籍贯籍贯) )课程课程( (课程编号课程编号, ,课程名课程名, ,学分，课时学分，课时) )选课选课( (学号学号, ,课程号课程号, ,成绩成绩) ) “ “选课单选课单” ”包含如下信息：包含如下信息： 学号学号学号学号 课程编号课程编号课程编号课程编号 成绩成绩成绩成绩 时间时间时间时间m n1 1学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系数据结构（数据结构（C版）版）南京
6、中医药大学南京中医药大学信息技术学院信息技术学院例例3 UNIX文件系统的系统结构文件系统的系统结构树结构树结构各目录之间是什么关系？各目录之间是什么关系？/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp1.1 数据结构的概念数据结构的概念数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院1.1 数据结构的概念数据结构的概念数据数据：信息的载体，是描述客观事物的数、字符以及：信息的载体，是描述客观事物的数、字符以及所有能所有能输入输入到计算机中并能被计算机程序到计算机中并能被计算机程
7、序识别和处理识别和处理的符号集合。的符号集合。 数值数据：整数、实数等数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等非数值数据：图形、图象、声音、文字等 数据元素数据元素：数据的：数据的基本基本单位，在计算机程序中通常作单位，在计算机程序中通常作为一个为一个整体整体进行考虑和处理。进行考虑和处理。数据项数据项：构成数据元素的最小单位，分为：构成数据元素的最小单位，分为初等项初等项和和组组合项合项两种。两种。数据结构数据结构：由某一数据元素的集合和该集合中数据元：由某一数据元素的集合和该集合中数据元素之间的关系组成。素之间的关系组成。 1.1.2 数据与数据结构数据与数据结构数据结
8、构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院数据、数据元素、数据项之间的关系数据、数据元素、数据项之间的关系包含关系：数据是由数据元素组成，数据元包含关系：数据是由数据元素组成，数据元素是由数据项组成。素是由数据项组成。数据元素数据元素是讨论数据结构时涉及的最小数据是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。单位，其中的数据项一般不予考虑。1.1 数据结构的概念数据结构的概念数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院依据数据元素之间的关系，数据结构可分为两大类：依据数据元素之间的关系，数据结构可分为两大类
9、： 线性结构：所有数据元素按某种次序排列在一个序列中。线性结构：所有数据元素按某种次序排列在一个序列中。 非线性结构：各个数据元素不再保持在一个线性序列中，每非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或多个其他数据元素发生联系。又可分个数据元素可能与零个或多个其他数据元素发生联系。又可分为为层次结构层次结构和和群结构群结构。1.1 数据结构的概念数据结构的概念1.1.3 数据结构的分类数据结构的分类bindevetclibuser141312112345678910112543611331814665161921125643数据结构（数据结构（C版）版）南京中医药
10、大学南京中医药大学信息技术学院信息技术学院 “数据结构数据结构”课程是研究系统开发过程中有关课程是研究系统开发过程中有关设计设计（包括数（包括数据设计、体系结构设计、接口设计和过程设计）的若干据设计、体系结构设计、接口设计和过程设计）的若干基本问基本问题题的学科。的学科。 选择数据结构的几个步骤：选择数据结构的几个步骤：分析问题，确定算法遇到的资源限制（内外存空间和执行时间）分析问题，确定算法遇到的资源限制（内外存空间和执行时间）确定必须支持的基本运算，度量每个运算所受到的资源限制。确定必须支持的基本运算，度量每个运算所受到的资源限制。选择最接近这些资源开销的数据结构。选择最接近这些资源开销的
11、数据结构。 数据结构的内容包括数据结构的内容包括3个层次的个层次的5个个“要素要素”。1.1 数据结构的概念数据结构的概念1.1.4 数据结构课程的内容数据结构课程的内容 方面方面层次层次数据表示数据表示数据处理数据处理抽象抽象逻辑结构逻辑结构基本运算基本运算实现实现存储结构存储结构算法算法评价评价不同数据结构的比较及算法分析不同数据结构的比较及算法分析数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 数据结构的核心技术是数据结构的核心技术是分解分解与与抽象抽象。通过分解得到数据的层次：数据通过分解得到数据的层次：数据-数据元素数据元素-数据项数据项 通过抽象
12、得到数据的逻辑结构通过抽象得到数据的逻辑结构通过分解将处理要求划分成各种功能通过分解将处理要求划分成各种功能 通过抽象得到运算的定义通过抽象得到运算的定义上述两个方面的结合将问题变换为上述两个方面的结合将问题变换为数据结构数据结构。1.1 数据结构的概念数据结构的概念1.1.4 数据结构课程的内容数据结构课程的内容抽象（逻辑结构）抽象（逻辑结构）具体（具体问题）具体（具体问题）抽象（逻辑结构）抽象（逻辑结构）具体（存储结构具体（存储结构和实现运算）和实现运算）数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 数据的数据的逻辑结构逻辑结构：简称数据结构，指从解决
13、问题的：简称数据结构，指从解决问题的需要出发，为实现必要的功能所建立的数据结构，属需要出发，为实现必要的功能所建立的数据结构，属于用户的视图，面向问题的。于用户的视图，面向问题的。数据的数据的物理结构物理结构：指数据应该如何在计算机中存放，：指数据应该如何在计算机中存放，是数据逻辑结构的物理存储方式，属于具体实现的视是数据逻辑结构的物理存储方式，属于具体实现的视图，面向计算机的。图，面向计算机的。数据结构的存储结构可以用以下数据结构的存储结构可以用以下4种存储方法得到：种存储方法得到：顺序顺序存储方法：逻辑关系由存储单元的邻接位置关系来体现。存储方法：逻辑关系由存储单元的邻接位置关系来体现。链
14、接链接存储方法：逻辑关系由附加的指针指示。存储方法：逻辑关系由附加的指针指示。索引索引存储方法：通过索引项中的地址来指示一个结点或一组相邻结点存储方法：通过索引项中的地址来指示一个结点或一组相邻结点的物理位置的物理位置散列散列存储方法：根据结点的关键码通过一个函数计算直接得到该结点存储方法：根据结点的关键码通过一个函数计算直接得到该结点的存储地址。的存储地址。1.1 数据结构的概念数据结构的概念1.1.4 数据结构课程的内容数据结构课程的内容数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院1.2.1 数据类型数据类型 数据类型数据类型（Data Type）：一
15、组）：一组值值的集合以及定义于的集合以及定义于这个值集上的一组这个值集上的一组操作操作的总称。的总称。 例如：例如：C+中的整型、字符型等基本类型与数组、构造型中的整型、字符型等基本类型与数组、构造型等构造组合类型。等构造组合类型。注意注意：数据类型的逻辑概念与其在计算机程序中的实现有很：数据类型的逻辑概念与其在计算机程序中的实现有很重要的区别！重要的区别！ 1.2 数据结构的抽象形式数据结构的抽象形式数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院1.2.2 数据抽象与抽象数据类型数据抽象与抽象数据类型1. 抽象抽象（Abstract）:抽出问题本质的特征而
16、忽略非本抽出问题本质的特征而忽略非本质的细节。质的细节。例：例：1.2 数据结构的抽象形式数据结构的抽象形式2. 抽象数据类型抽象数据类型（Abstract Data Type，ADT）:一个一个数据结构数据结构以及定义在该结构上的以及定义在该结构上的一组操作一组操作的总称。的总称。 计算机中数据的存储与运算计算机中数据的存储与运算二进制形式二进制形式(101010111)自然表示自然表示(15.5,1.3E10,10)汇编语言中汇编语言中更高一级的抽象更高一级的抽象(整型、实型等整型、实型等)高级语言中高级语言中数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学
17、院ADT是对数据类型的进一步抽象是对数据类型的进一步抽象 ADT逻逻 辑辑 结结构构操作集合操作集合数据结构数据结构存储结构存储结构算法设计算法设计类类成员变量成员变量成员函数成员函数(a)使用视图使用视图 (b) 设计视图设计视图 (c) 实现视图实现视图ADT的定义的定义 ADT的设计的设计 ADT的实现的实现ADT的不同视图的不同视图1.2 数据结构的抽象形式数据结构的抽象形式数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院ADT 抽象数据类型名抽象数据类型名Data 数据元素之间逻辑关系的定义数据元素之间逻辑关系的定义Operation 操作操作1 前
18、置条件前置条件：执行此操作前数据所必须的状态：执行此操作前数据所必须的状态 输输 入入：执行此操作所需要的输入：执行此操作所需要的输入 功功 能能：该操作将完成的功能：该操作将完成的功能 输输 出出：执行该操作后产生的输出：执行该操作后产生的输出 后置条件后置条件：执行该操作后数据的状态：执行该操作后数据的状态 操作操作2 操作操作n endADT ADT的定义形式的定义形式1.2 数据结构的抽象形式数据结构的抽象形式见P8例数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院算法的定义算法的定义1.算算法法（Algorithm）:，是是对对特特定定问问题题求求解
19、解步步骤骤的的一种描述，是一种描述，是指令指令的的有限序列有限序列。2. 算法的五大特性：算法的五大特性： 输入输入：一个算法有零个或多个输入。：一个算法有零个或多个输入。 输出输出：一个算法有一个或多个输出。：一个算法有一个或多个输出。 有穷性有穷性：一个算法必须总是在执行有穷步之后结束，且：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。每一步都在有穷时间内完成。 确定性确定性：算法中的每一条指令必须有确切的含义，对于：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。相同的输入只能得到相同的输出。 可行性可行性：算法描述的操作可以通过已经实现的基本操
20、作：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。执行有限次来实现。1.4 算法定义算法定义数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院算法的定义算法的定义3.算法和程序不同，程序可以不满足算法和程序不同，程序可以不满足有穷性有穷性。4.算算法法的的描描述述：语语言言方方式式、图图形形方方式式、表表格格方方式式。教教材材中中使使用用C+语语言言，有有时时与与自自然然语语言言结结合合来来描描述算法。述算法。1.4 算法定义算法定义数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院算法的设计算法的设计方法：自顶向下、
21、逐步求精的结构化程序设计方法。方法：自顶向下、逐步求精的结构化程序设计方法。1.4 算法定义算法定义例：例：选择排序选择排序：把存放在一个整数数组中的：把存放在一个整数数组中的n个个乱七八糟的数据按自小到大的顺序排列起来。乱七八糟的数据按自小到大的顺序排列起来。2,33,45,98,100100,2,45,33,98数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院算法思想算法思想：从：从a0到到an-1中选择一个最小中选择一个最小的，把它交换到的，把它交换到a0中；然后从剩下的中；然后从剩下的a1到到an-1中选择一个最小的，把它交换到中选择一个最小的，把它交
22、换到a1中；依次类推直到第中；依次类推直到第n-1个数据交换到个数据交换到an-2中。中。1.4 算法定义算法定义数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院算法框架算法框架：for(int i=0;in-1;i+) 从从ai检查到检查到an-1，寻找最小的整数，其位置记为寻找最小的整数，其位置记为k； 若若ik，则交换则交换ai与与ak；1.4 算法定义算法定义数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院进一步细化得到下面的进一步细化得到下面的算法算法：void selectSort(int a ,const int
23、 n) int temp,i,j,k; for(int i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(ajak) k=j; if(i!=k) temp=ai; ai =ak;ak=temp; 1.4 算法定义算法定义数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院1.5.1 算法的性能标准算法的性能标准判断一个算法的优劣，主要有以下几个标准：判断一个算法的优劣，主要有以下几个标准： 正确性正确性：要求算法能够正确地执行预定的功能和性能要求。：要求算法能够正确地执行预定的功能和性能要求。 可使用性可使用性：要求算法能够很方便地使用。
24、：要求算法能够很方便地使用。 可读性可读性：算法应是可读的。：算法应是可读的。 效效率率：算算法法的的效效率率主主要要指指算算法法执执行行时时计计算算机机资资源源的的消消耗耗，包包括括存储（存储（空间代价空间代价）和运行时间（）和运行时间（时间代价时间代价）的开销。）的开销。 健壮性健壮性：自动检错、报错并通过与用户对话来纠错的功能。：自动检错、报错并通过与用户对话来纠错的功能。 简单性简单性：指一个算法所采用的数据结构和方法的简单程度。：指一个算法所采用的数据结构和方法的简单程度。1.5 算法性能分析与度量算法性能分析与度量数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学
25、院信息技术学院1.5.2 算法的后期测试算法的后期测试度量算法效率的方法：度量算法效率的方法： 后后期期测测试试：主主要要通通过过在在算算法法中中的的某某些些部部位位插插装装时时间间函函数数（如如time()来来测测定定算算法法完完成成某某一一规规定定功功能能所所需需的的时间。时间。 缺点：缺点： 编写程序实现算法将花费较多的时间和精力；编写程序实现算法将花费较多的时间和精力； 算算法法的的运运行行时时间间依依赖赖于于所所用用的的计计算算机机系系统统、编编译译器器、可用存储空间大小等因素。可用存储空间大小等因素。 事前估计事前估计：对算法所消耗资源的一种估算方法。：对算法所消耗资源的一种估算方
26、法。1.5 算法性能分析与度量算法性能分析与度量见P27例数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院1.5.3 算法的事前估计算法的事前估计即即算算法法复复杂杂性性的的度度量量，可可分分为为空空间间复复杂杂度度度度量量和和时时间间复杂度复杂度度量。度量。1、空间复杂度空间复杂度度量度量1）固固定定部部分分：包包括括存存放放程程序序指指令令代代码码的的空空间间，常常数数、简简单单变变量量、定定长长成成分分变变量量所所占占的的空空间间等等，属属于于静静态态空空间。间。2）可可变变部部分分：包包括括与与问问题题规规模模有有关关的的变变量量所所占占空空间间、递递
27、归归工工作作栈栈所所用用空空间间，以以及及在在算算法法运运行行过过程程中中通通过过new和和delete命令动态使用的空间。命令动态使用的空间。1.5 算法性能分析与度量算法性能分析与度量数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院算算法法的的时时间间复复杂杂度度分分析析：主主要要从从程程序序结结构构着着手手，统统计计算算法的程序步数。法的程序步数。程程序序步步：指指在在语语法法上上或或语语义义上上有有意意义义的的一一段段指指令令序序列列，而且这段指令序列的执行时间与实例特性无关。而且这段指令序列的执行时间与实例特性无关。各种语句的程序步数的计算详见书中各
28、种语句的程序步数的计算详见书中P29P29。确定程序步数的确定程序步数的方法方法：1 1、在程序中插入一个计数变量、在程序中插入一个计数变量countcount，见见P30-31P30-312 2、建建立立一一个个表表，列列出出程程序序内内各各个个语语句句的的程程序序步步数数，见见P32P32。1.5 算法性能分析与度量算法性能分析与度量1.5.3 算法的事前估计算法的事前估计数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院例例例例 以迭代方式求累加和的函数以迭代方式求累加和的函数以迭代方式求累加和的函数以迭代方式求累加和的函数float sum ( floa
29、t a , const int n ) float s = 0.0; count+;/count 统计执行语句条数 for ( int i = 0; i n; i+ ) count+=2;/针对 for 语句 s += ai; count+; /针对 赋值语句 count+=2;/针对 for 语句的最后一次 return s; count+;/针对 return 语句执行结束得执行结束得 程序步数程序步数 count = 3*n+4 数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院计算程序步数的简化形式计算程序步数的简化形式 void sum ( float
30、 a , int n ) for ( int i = 0; i n; i+ ) count += 3; count += 4; 数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院注意注意： 一个语句本身的程序步数可能不等一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。于该语句一次执行所具有的程序步数。 例如：赋值语句例如：赋值语句 x = sum (R, n) 本身的程序步数为本身的程序步数为 1； 一次执行对函数一次执行对函数 sum (R, n) 的调用的调用需要的程序步数为需要的程序步数为 3*n+4； 一次执行的程序步数为一次执行的程序步
31、数为 1+3*n+4 = 3*n+5数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院迭代求和迭代求和程序中程序中程序步数程序步数计算工作表格计算工作表格数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院定义定义 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有都有T( (n)cf( (n) )，则称，则称T( (n) )=O( (f( (n)n0问题规模问题规模n执执行行次次数数n0之之前前的的情情况况无无关关紧要紧要T( (n) )cf( (n) )v当问题规模充分大时在渐近意义下的阶当问题规模充
32、分大时在渐近意义下的阶1.5.4 1.5.4 算法的渐进分析算法的渐进分析算法的渐进分析算法的渐进分析大大O渐进表示渐进表示1.5 算法性能分析与度量算法性能分析与度量数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院定定理理：若若A(n)=amnm+am-1nm-1+a1n+a0是是一一个个m次多项式，则次多项式，则A(n)=O(nm)。说明：在计算算法时间复杂度时，可以忽略说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。所有低次幂和最高次幂的系数。1.5 算法性能分析与度量算法性能分析与度量1.5.4 1.5.4 算法的渐进分析算法的渐进分
33、析算法的渐进分析算法的渐进分析大大O渐进表示渐进表示数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院例例1-5 +x; 例例1-6 for ( (i=1; i=n; +i) ) +x; 例例1-7 for (i=1; i=n; +i) for (j=1; j=n; +j) +x; 例例1-8 for (i=1; i=n; +i) for (j=1; j=i-1; +j) +x;1.5 算法性能分析与度量算法性能分析与度量1.5.4 1.5.4 算法的渐进分析算法的渐进分析算法的渐进分析算法的渐进分析大大O渐进表示渐进表示数据结构（数据结构（C版）版）南京中医药
34、大学南京中医药大学信息技术学院信息技术学院例例1-9 for (i=1; i=n; +i) for (j=1; j=n; +j) cij=0; for (k=1; k=n; +k) cij+=aik*bkj; 例例1-10 for (i=1; i=n; i=2*i) +x;(1)(log2n)(n)(nlog2n)(n2)(n3) (2n)(n!) 1.5 算法性能分析与度量算法性能分析与度量1.5.4 1.5.4 算法的渐进分析算法的渐进分析算法的渐进分析算法的渐进分析大大O渐进表示渐进表示数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院 数据结构的概念（小
35、结）数据结构的概念（小结）数据的操作：插入、删除、修改、检索、排序等数据的操作：插入、删除、修改、检索、排序等 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 顺序存储顺序存储链式存储链式存储集合集合线性结构线性结构树结构树结构图结构图结构 非数值问题非数值问题 数数据据表表示示数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院本章小结本章小结知识结构图知识结构图概论概论概论概论数据结构数据结构数据结构数据结构算算算算 法法法法基基本本概概念念逻逻辑辑结结构构存存储储结结构构数据数据数据元素数据元素数据对象数据对象ADT逻辑结构逻辑结构数据结构数据结
36、构的分类的分类存储结构存储结构常用存储常用存储方法方法基基本本概概念念算算法法分分析析算法算法算法特性算法特性评价算法评价算法描述算法描述算法问题规模问题规模基本语句基本语句时间复杂度时间复杂度大大O记号记号关关 系系数据结构（数据结构（C版）版）南京中医药大学南京中医药大学信息技术学院信息技术学院作业：作业：公元公元5世纪末，我国古代数学家张丘建在它所撰写的世纪末，我国古代数学家张丘建在它所撰写的算经中，提出这样一个问题：算经中，提出这样一个问题：“鸡翁一，值钱五；鸡翁一，值钱五；鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何？鸡翁、母、雏各几何？”意思是说公鸡每只意思是说公鸡每只5元，母鸡元，母鸡每只每只3元，小鸡元，小鸡3只只1元，用元，用100元钱买元钱买100只鸡，求公鸡、只鸡，求公鸡、母鸡、小鸡的只数。试设计算法求解该问题，并分析母鸡、小鸡的只数。试设计算法求解该问题，并分析你所设计的算法的时间复杂度。（要求：算法分别用你所设计的算法的时间复杂度。（要求：算法分别用伪代码和伪代码和C描述）描述）
