第1章数据结构基概论

《第1章数据结构基概论》由会员分享，可在线阅读，更多相关《第1章数据结构基概论（29页珍藏版）》请在金锄头文库上搜索。

1、第第1 1章章 数据结构基础概论数据结构基础概论 本章主要介绍以下内容本章主要介绍以下内容l 数据结构研究的主要内容数据结构研究的主要内容l 数据结构中涉及的基本概念数据结构中涉及的基本概念l 算法的概念、描述方法以及评价标准算法的概念、描述方法以及评价标准村需佃循诀尊局咸坎贿盂履爽铣跑妊谬棋蒜镍徐商皋章粤恬绦窒皇玻舟儒第1章数据结构基概论第1章数据结构基概论 1.1 1.1 数据结构研究的主要内容数据结构研究的主要内容 1.2 1.2 基本概念和术语基本概念和术语 1.3 1.3 算法算法嘉磕唉毋嗣要座钉飞槐甄玄宝赂晌植扶典赫津恰防蜀幕海延缴险似菌纫吵第1章数据结构基概论第1章数据结构基概论

2、1.1 1.1 数据结构研究的主要内容数据结构研究的主要内容 当今计算机应用的特点：当今计算机应用的特点： l l所处理的数据量大且具有一定的关系；所处理的数据量大且具有一定的关系； l l对其操作不再是单纯的数值计算，而更多对其操作不再是单纯的数值计算，而更多 的是需要对其进行组织、管理和检索。的是需要对其进行组织、管理和检索。 应用举例应用举例11学籍档案管理学籍档案管理 假设一个学籍档案管理系统应包含如下表假设一个学籍档案管理系统应包含如下表1-1所示所示的学生信息。的学生信息。肋渊宜羡橙萨峭桨瓢字缮验簇瘪概害正正秩另苟流序壮膊渴磐讫协止厉楞第1章数据结构基概论第1章数据结构基概论表表表

3、表1-11-1对百怕腑桶厩昨辗蕊孝组乃砾额涟揽墟位夷抒赘堂疮遵峰首雌汤痹焚放酥第1章数据结构基概论第1章数据结构基概论 特点：特点： l l 每个学生的信息占据一行，所有学生的信息按每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；学号顺序依次排列构成一张表格； l l 表中每个学生的信息依据学号的大小存在着一表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；种前后关系，这就是我们所说的线性结构； l l 对它的操作通常是插入某个学生的信息，删除对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息，

4、更新某个学生的信息，按条件检索某个学生的信息等等。某个学生的信息等等。 应用举例应用举例2输出输出n个对象的全排列个对象的全排列 输出输出n个对象的全排列可以使用下图个对象的全排列可以使用下图1-1所示的形式所示的形式描述。描述。危歉哆镜订变串胶蘸射捻溉吧箍抚呢钱醛歧脱臼溃峻刽个树嘻产斜瑰昆癌第1章数据结构基概论第1章数据结构基概论图图图图 1-1 3 1-1 3个对象的全排列过程个对象的全排列过程个对象的全排列过程个对象的全排列过程扑迭欧坛墨晶坎玻嘎醇磊眼侈耗模尘揽脉腋近柑枯三跑创摩珍他妊郁挚讼第1章数据结构基概论第1章数据结构基概论 特点：特点： l l 在求解过程中，所处理的数据之间具有

5、层次关在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；系，这是我们所说的树形结构； l l 对它的操作有：建立树形结构，输出最低层结对它的操作有：建立树形结构，输出最低层结点内容等等。点内容等等。 应用举例应用举例3制定教学计划制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表业课程的开设情况如下表1-2所示：所示：挨失童耳

6、碍躇赋蔼摧壕膜锯晌涣舅绑硝茸酵欲敝膘涉稳年峡裁坐竖粮翌侵第1章数据结构基概论第1章数据结构基概论表表表表1-21-2档毒粕诬徒圾子蝉腕沿枢腥暂阅陛创姿饲鞘咬隘氰厂砖佑凝坐铀梨励钠仟第1章数据结构基概论第1章数据结构基概论课程先后关系的图形描形式：课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图图图图 1-2 1-2 计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系阀昭舆技伴茄处斤薯孟惮涪嵌梆镑炮仆疲低傅沟值磕玖雷恒萤支仰者侍邯第1章数据结构基概论第1章数据结构基概论 特点特点 l l 课程

7、之间的先后关系用图结构描述；课程之间的先后关系用图结构描述； l l 通过实施创建图结构，按要求将图结构中的顶通过实施创建图结构，按要求将图结构中的顶点进行线性排序。点进行线性排序。 结论结论 计算机的操作对象的关系更加复杂，操作形式不再计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算

8、机中的表示方式以及清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是数据结构这门各个操作的具体实现手段。这些就是数据结构这门课程研究的主要内容。课程研究的主要内容。更舟镁瞬群忽二却疫潦曙掏男范旁崎烛叭厘药萤篡效责诲淆邦聊何迭堤搔第1章数据结构基概论第1章数据结构基概论1.2 1.2 基本概念和术语基本概念和术语 数据数据 是对客观事物的符号表示。在计算机科学中其含是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理义是指所有能够输入到计算机中并被计算机程序处理的符号集合。的符号集合。 数据元素数据元素 是数据集合中的一个实体，是

9、计算机程序中加工是数据集合中的一个实体，是计算机程序中加工处理的基本单位。处理的基本单位。绦旨壮袭新浦桐噬壤枕呜维累儿若稚力钥蹿雪蛰愤惑时砚眷蓬滑皖夷拆碰第1章数据结构基概论第1章数据结构基概论 数据元素按其组成可分为简单型数据元素和复杂数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。的多方面信息。 数据结构数据结

10、构 简单地说，就是相互之间存在一种或多种特定关简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、系的数据元素的集合。常见的数据结构有：线性结构、树形结构和图形结构。树形结构和图形结构。 逻辑结构逻辑结构 数据结构中所说的数据结构中所说的“关系关系”实际上是指数据元素实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。之间的逻辑关系，又称此为逻辑结构。楷催独件灭荧扩言贮傣陌咱戊苹屯暴春函锡跋灸坚詹剔捉括蛙慷赶悦韦孩第1章数据结构基概论第1章数据结构基概论 存储结构（物理结构）存储结构（物理结构） 是指数据结构在计算机存储器中的具体实现。与是指数据结构在计算

11、机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。元素之间的逻辑结构。 常见的存储结构常见的存储结构 顺序存储结构：特点是借助于数据元素的相对存顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；储位置来表示数据元素之间的逻辑结构； 链式存储结构：特点是借助于指示数据元素地址链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。的指针表示数据元素之间的逻辑结构。须碍锈宵众

12、女训酥橱记阐咎窑展耻屠唇盈纷鸦攀船彻俊辛火宛逐劣宏斡永第1章数据结构基概论第1章数据结构基概论1.3 1.3 算法算法1.3.1 1.3.1 算法的概念算法的概念 算法是解决某个特定问题的一种方法或一个过程。算法是解决某个特定问题的一种方法或一个过程。 计算机对数据的操作可以分为数值性和非数值性两计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除非数值性操作中主要进行的是检索、排序、插入、删除等等。等等。页痹窖肯尝盂叶沮束伶紧群剑梯讥毗砰辊癸式蛛毋掷撞份殿嘲

13、坐氰肪乡叮第1章数据结构基概论第1章数据结构基概论 设计算法的基本过程设计算法的基本过程 l l通过对问题进行详细地分析，抽象出相应通过对问题进行详细地分析，抽象出相应的数学模型；的数学模型； l l确定使用的数据结构，并在此基础上设计确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；对此数据结构实施各种操作的算法； l l选用某种语言将算法转换成程序；选用某种语言将算法转换成程序； l l调试并运行这些程序。调试并运行这些程序。皿波资款画险吊肌币锣浙阅虾纪闪拇儒辅忽搞航批可意鲁缓幌搓邹讳饿辐第1章数据结构基概论第1章数据结构基概论 算法应该具有下列五个特性算法应该具有下列五

14、个特性 （1）有穷性：一个算法必须在执行有穷步之后结束。）有穷性：一个算法必须在执行有穷步之后结束。 （2）确定性：算法中的每一步，必须有确切的含义，）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。在他人理解时不会产生二义性。 （3）可行性：算法中描述的每一步操作都可以通过已）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。有的基本操作执行有限次实现。 （4）输入：一个算法应该有零个或多个输入。）输入：一个算法应该有零个或多个输入。 （5）输出：一个算法应该有一个或多个输出。这里所）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种

15、特定关系的量。说的输出是指与输入有某种特定关系的量。翟允悲讣跃析抄醉绵煽告创恋惮缮骄怨尘拈吐添咽衅宾熏霄砖钙龄办报赏第1章数据结构基概论第1章数据结构基概论 举例举例 问题：按从小到大的顺序重新排列问题：按从小到大的顺序重新排列x，y，z三个数三个数值的内容。值的内容。 算法：算法： （1）输入）输入x，y，z三个数值；三个数值； （2）从三个数值中挑选出最小者并换到）从三个数值中挑选出最小者并换到x中；中； （3）从）从y，z中挑选出较小者并换到中挑选出较小者并换到y中；中； （4）输出排序后的结果。）输出排序后的结果。芍掌实同肩累耳桌磊笆卜宅墒粗刃屏蹿巾锰岸廉忠澄龋所荚渔移深味幢撵第1章数

16、据结构基概论第1章数据结构基概论1.3.2 1.3.2 算法的描述算法的描述 选择算法描述语言的准则选择算法描述语言的准则 （1）该语言应该具有描述数据结构和算法的基本功能；）该语言应该具有描述数据结构和算法的基本功能； （2）该语言应该尽可能地简捷，以便于掌握、理解；）该语言应该尽可能地简捷，以便于掌握、理解； （3）使用该语言描述的算法应该能够比较容易地转换成）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。任何一种程序设计语言。 “类类C”描述语言是通过对描述语言是通过对C语言进行精心筛选保留的一语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从

17、而，个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。增强了语言的描述功能。甫谜缺寅顷左浩碑穴余贰屡网粪穗椿砂剑爪姥陈肢往捣羡骏伙瘸泉锈妆弘第1章数据结构基概论第1章数据结构基概论 1. 预定义常量及类型预定义常量及类型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 数据元素被约定为数据元素被约定为EntryType 类型，用户需要根据类型，用户需要根据具体情况，自行定义该数据类型。具体情况，自行定义该数据类型。输猾病堕拭丘崩熟轩缨咖阻片吏恒聂潮立盛峨论盔

18、硅逗漫应疾抠臀霹呛您第1章数据结构基概论第1章数据结构基概论 2. 算法描述为以下的函数形式：算法描述为以下的函数形式： 函数类型函数类型 函数名（函数参数表）函数名（函数参数表） 语句序列；语句序列； 为了简化函数的书写，提高算法描述的清晰度，为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯

19、。对重点语句段落添加注解的良好习惯。砚务榆蛾惟乳甩旗之粮刑泅橡话露赋慈吃熬款勋坏芹脏甄兹押蹬答播烬荚第1章数据结构基概论第1章数据结构基概论 3. 在算法描述中可以使用的赋值语句形式有：在算法描述中可以使用的赋值语句形式有： 简单赋值简单赋值 变量名变量名 = 表达式；表达式； 串联赋值串联赋值 变量名变量名1 = 变量名变量名2 = . = 变量名变量名n = 表达式；表达式； 成组赋值成组赋值 （变量名（变量名1，.，变量名，变量名n）=（表达式（表达式1，.，表达式，表达式n）；）； 结构赋值结构赋值 结构名结构名1 = 结构名结构名2； 结构名结构名 =（值（值1，值，值2，.，值，值

20、n）；）； 条件赋值条件赋值 变量名变量名 = 条件表达式条件表达式 ? 表达式表达式1：表达式：表达式2； 交换赋值交换赋值 变量名变量名1 变量名变量名2；忧屎帧限乌楞睹桨遮逛归撅烩涟估买湘奖周跳绽硕胰哥啮存拓极鳖坠擒廊第1章数据结构基概论第1章数据结构基概论4. 在算法描述中可以使用的选择结构语句形式有：在算法描述中可以使用的选择结构语句形式有：条件语句条件语句1 if （表达式）（表达式） 语句；语句；条件语句条件语句2 if （表达式）（表达式） 语句；语句； else 语句；语句；开关语句开关语句1 switch （表达式）（表达式） case 值值1：语句序列：语句序列1；bre

21、ak； case 值值2：语句序列：语句序列2；break； . case 值值n：语句序列：语句序列n；break； default：语句序列：语句序列n+1； 痔钻边俱占绕余浚反谎墒碱测与西价睹寐莱颖惟肘蚂蔫烬阮协岩蛋狭险眨第1章数据结构基概论第1章数据结构基概论开关语句开关语句2 switch case 条件条件1：语句序列：语句序列1；break； case 条件条件2：语句序列：语句序列2；break； . case 条件条件n：语句序列：语句序列n；break； default：语句序列：语句序列n+1； 住褂袱叁姜陀密靖番玛枷肖您阜烙看儿掏泣萍沮勉烤毖幸多嘲涛凡案心旗第1章数据结

22、构基概论第1章数据结构基概论 5. 在算法描述中可以使用的循环结构语句形式有：在算法描述中可以使用的循环结构语句形式有： for循环语句循环语句 for （表达式（表达式1；循环条件表达式；表；循环条件表达式；表达式达式2） 语句；语句； while循环语句循环语句 while （循环条件表达式）（循环条件表达式） 语句；语句； do-while循环语句循环语句 do 语句序列；语句序列； while （循环条件表达式）；（循环条件表达式）； 6. 在描述算法中可以使用的结束语句形式有：在描述算法中可以使用的结束语句形式有： 函数结束语句函数结束语句 return 表达式；表达式； retur

23、n; case或循环结束语句或循环结束语句 break; 异常结束语句异常结束语句 exit（异常代码）；（异常代码）； 逃坑贼说瓢棱矮蚀逾刘夸逮苟荒纸漫贬嘴孕区养带汀搂澎粳锗俐疗坚羌汗第1章数据结构基概论第1章数据结构基概论 7. 在算法描述中可以使用的输入输出语句形式有：在算法描述中可以使用的输入输出语句形式有： 输入语句输入语句 scanf( 格式串格式串，变量名，变量名1，.，变量名，变量名n)； 输出语句输出语句 printf( 格式串格式串，表达式，表达式1，.，表达式，表达式n); 方括号（方括号（ ）中的内容是可以省略的部分。）中的内容是可以省略的部分。 8. 在算法描述中使用

24、的注释格式为：在算法描述中使用的注释格式为： 单行注释单行注释 /文字序列文字序列 9. 在算法描述中可以使用的扩展函数有：在算法描述中可以使用的扩展函数有： 求最大值求最大值 max（表达式（表达式1，.，表达式，表达式n）；这个函）；这个函数返回参数表中数返回参数表中n个表达式计算结果中的最大值。个表达式计算结果中的最大值。 求最小值求最小值 min（表达式（表达式1，.，表达式，表达式n）；这个函）；这个函数返回参数表中数返回参数表中n个表达式计算结果中的最小值。个表达式计算结果中的最小值。巳士错慌葱菜炔沟蔚爷致裁湖酪扶皆蜀估疆帚柠笆塞扛订耘莲祭炯铂黎烦第1章数据结构基概论第1章数据结构

25、基概论 【算法【算法1-1】用类】用类C描述将三个数值排序的算法。描述将三个数值排序的算法。 viod Three_Sort( int *x,int *y,int *z) /将将x,y,z三个指针所指示的内容按从小到大的顺序重新三个指针所指示的内容按从小到大的顺序重新排列排列 if (*y*x&*y*z) *x*y; /挑选出最小的数值并换到选出最小的数值并换到 x指针所指的存储单元中指针所指的存储单元中 else if (*z*x&*z*y) *x*z; if (*z*y) *y*z; /在在y和和z所指示的存储单元中所指示的存储单元中挑选出较小者换到选出较小者换到y中中 缎翔睁役寒绳节徒缺

26、开柞凑捧枝差艰雾含奋环讣唇镁足盆亩咯付慷弗枕剖第1章数据结构基概论第1章数据结构基概论1.3.3 1.3.3 算法的评价算法的评价 算法的评价标准算法的评价标准 (1) 正确性：要求算法能够正确地执行预先规定的正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。功能，并达到所期望的性能要求。 (2) 可读性：为了便于理解、测试和修改算法，算可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。法应该具有良好的可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并读取文件记录、分

27、配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。通过与用户对话的形式做出相应的处理选择。 (4) 时间与空间效率：算法的时间与空间效率是时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。花费的时间及所占据空间的度量。羊敢杰待噎逾许撤拥木绩酷去旺栏记歪沦惩厉捎痉感雷迭朵挤电糜越颖欺第1章数据结构基概论第1章数据结构基概论 算法的时间效率算法的时间效率 算法的时间效率主要由两个因素决定：算法的时间效率主要由两个因素决定： l l 所需处理问题的数据量大小，数据量大，所

28、花所需处理问题的数据量大小，数据量大，所花费的时间就多；费的时间就多； l l 在解决问题的过程中，基本操作的执行次数。在解决问题的过程中，基本操作的执行次数。时间特性的分析时间特性的分析 如果我们将一个算法所花费的时间设计成一个以如果我们将一个算法所花费的时间设计成一个以数据量数据量n为自变量的函数为自变量的函数T(n)，这个函数在正整数定义，这个函数在正整数定义域范围内一定是单调递增的。好的算法应该能够在数域范围内一定是单调递增的。好的算法应该能够在数据量据量n增长的同时，函数增长的同时，函数T(n)的增长速度比较缓慢。的增长速度比较缓慢。淹之酵等匈书坍毛莎兴匙葱其凑篇巴揍厘殴惯彦糟坡崩察

29、淑精殴咎芹矩毅第1章数据结构基概论第1章数据结构基概论 空间效率的分析空间效率的分析 一个算法的空间效率是指在算法的执行过程中，一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意空间效率。理想的情况。在设计算法时，应该注意空间效率。浅晓丸颇原嚷势沾岁溺梁打樊京粟挤页疵皮羌够讯貌屈拍兆倡壕厨胸劳探第1章数据结构基概论第1章数据结构基概论