数据结构 第一章

数据结构第一章1第一页，共三十四页，编辑于2023年，星期三本次课堂教学内容课程简介教学环节组成教材和教学参考书教学要求任课教师简介第一章概述2第二页，共三十四页，编辑于2023年，星期三课程简介“数据结构”是计算机科学类专业重要的专业技术基础课程，是提高软件设计水平以及学习后续课程所必需的基础。课程中介绍软件设计中常用的基本技术，包括：常见的数据结构及其在计算机中的存储结构和各种操作的实现：线性表、串、栈、队列、数组、树和二叉树、图、文件等软件设计中常用的排序和查找方法及其性能。基本算法设计技术通过对这些内容的学习，熟练地掌握各种常用结构的特性，各种运算的实现方法及其性能，并能在实际应用中根据具体问题的要求设计出合理的数据结构和运算。然而，由于该课程中的内容多，而且许多内容较抽象，特别是其中大量的算法以及所用到的递归技术，以及缺乏有效的实验条件，使学习数据结构课程的难度较大。3第三页，共三十四页，编辑于2023年，星期三教学环节组成整个课程的教学包括：课堂教学、实验教学和课程设计。共有6.5个学分课堂教学：64课时1-16周，周学时4，保留一周备用系统学习相关的知识体系和应用方法----基础理论实验教学：16学时由多个实验单元组成，以上机调试算法和程序的形式，分别围绕各部分的知识及其应用方法，验证、综合运用所学知识，提高解决实际问题的能力。课程设计：集中1周半时间对具有更大规模的，以数据结构方法和技术为主要手段，通过综合性设计方式，实现问题求解。在此基础上，撰写设计报告，描述求解的相关方法。4第四页，共三十四页，编辑于2023年，星期三教材和参考书教材：数据结构与程序设计，C++语言描述（英文版），RobertL.Kruse,AlexanderJ.Ryba，高等教育出版社)。

教材和参考书照片\高教社外文版教材.JPG《计算机科学与技术专业软件系列课程实践教程》，胡学钢，王浩主编，合肥工业大学出版社，2005。

教材和参考书照片\实践教程.JPG说明：每本教材都有其优点和适用条件，但也存在不足。不能仅限于一本教材，需多方面参考，应多读几本，互为补充。5第五页，共三十四页，编辑于2023年，星期三教材和参考书（2）教学参考书：数据结构（C语言版），严蔚敏，吴伟民编著，清华大学出版社，1999。《数据结构算法设计指导》，胡学钢著，清华大学出版社，1999。《数据结构(C语言版)》，胡学钢主编，高等教育出版社，2008。1。

教材和参考书照片\胡学钢教材.JPG6第六页，共三十四页，编辑于2023年，星期三学习要求和建议

教学的每个方面都是围绕总体目标来开展的，有自身的教学目标和规律，不仅需要投入精力，而且还要注意学习方法。为此，提出如下的学习要求和建议。课堂教学是构建完整知识体系的关键关于知识体系：包括多个方面（知识点）----显现的静态性知识各知识点间具有一定的联系----隐含的动态性知识，例如，关于某项知识的背景，解决问题的方法和技术，可能存在的问题，求解方法的性能及其选择方法，应用价值等。对知识体系的教学任课教师在教学过程中，会以多种方式，结合自己的教学、研究积累来介绍，引导建立知识体系。学习中，不仅要理解和掌握各知识点，同时还要注意知识点之间的联系，学会用发展的观点来理解知识，掌握能力。各教学环节，包括课堂教学、作业、复习、实验和课程设计，都是围绕此目的来开展的。7第七页，共三十四页，编辑于2023年，星期三学习要求和建议（续1）课堂教学的要求：不旷课、迟到、早退------保持听课和知识的完整性。事先作必要的预习------有备而来，主动学习，而不是被动学习认真听课，记笔记------便于后续的复习和回忆，因为单纯的听课达不到“完全录音”的效果。认真完成作业：帮助复习、深化，乃至综合理解和运用知识提交作业，作业本，电子信箱，网站平时成绩的计算方法，考试的门槛总结和复习：学习需要不断升华，提升对知识的理解深度。

--------从厚到薄，从薄到厚

--------实践，认识，再实践，再认识

--------温故而知新考勤的要求：必要的督促，作为平时成绩的组成部分。必须学会按照规则办事。8第八页，共三十四页，编辑于2023年，星期三学习要求和建议（续2）实验教学作为教学的重要组成部分关于实践：实践是认识的源泉。实践是检验知识的唯一标准。实践是培养能力的基础。实践是创新的保证。用人单位，尤其是企业需要有实践经历的毕业生。实践教学是实现教学目标的重要组成部分是检验和深化理论知识的重要手段实际解决问题的能力培养创新意识和能力的培养良好治学态度的培养9第九页，共三十四页，编辑于2023年，星期三学习要求和建议（续3）实验教学的要求每项实验任务都是需要完成的。实验前，要认真准备：理解教学要求，编写实验程序，组织好实验数据，并估计可能出现的问题。提交实验预习报告。（上网）实验过程中：认真观察过程，记录数据和结果，并分析有关的原因，及时调整。实验后：在系统分析试验数据和结果的基础上，对相关的原理进行总结。提交实验报告，培养良好的治学态度，掌握描述规范。平时成绩的计算方法，考试的门槛10第十页，共三十四页，编辑于2023年，星期三学习要求和建议（续4）课程设计：综合型、提高性的设计训练课程设计的要求：选题：能达到充分的锻炼----量力而行，认真设计：问题建模，数据结构设计，算法设计，性能指标要求，求解性能分析撰写设计报告：作为一种基本的能力叙述设计，并作必要的分析和描述培养严谨的治学态度未来工作中的基本能力：业务报告，学术论文，毕业论文，著作，工作报告等。成绩评定的依据11第十一页，共三十四页，编辑于2023年，星期三全课程的内容第一章概述第二章顺序栈第三章顺序队列第四章链栈和链队列第五章线性表第六章递归技术第七章树和二叉树第八章图结构第九章查找第十章排序第十一章数组和广义表12第十二页，共三十四页，编辑于2023年，星期三任课教师简介胡学钢1983年7月任教至今，先后主讲十多门本科和研究生课程。愿望：希望自己的学生都能成才，并为此而不断地探索和努力。希望成为学生的知心朋友！现在的基本情况如下：合肥工业大学计算机与信息学院副院长，分管本科教学合肥工业大学人工智能与数据挖掘研究室教授研究团队有教师、博士、硕士研究生数十人针对急剧增长的各类数据，开展从数据中发现知识的课题研究。目前的主要研究方向：算法设计，数据挖掘，知识工程本科教学：以数据结构为主，目前是安徽省级精品课程另外还主讲：计算机科学技术导论，数据挖掘13第十三页，共三十四页，编辑于2023年，星期三任课教师简介其他的工作兼职：教育部计算机科学与技术专业指导委员会委员安徽省高校计算机教育研究会副理事长安徽省教学名师安徽省精品课程“数据结构”建设项目主持人学校“程序设计技术”教学团队负责人安徽省水平考试专家组组长联络方式Email:jsjxhuxg@办公室电编：230009，传晶：非常认真和敬业，教学效果优异，热心为人是学生的好朋友14第十四页，共三十四页，编辑于2023年，星期三第一章概述

主要内容

1.1

研究内容

1.2术语

1.3算法及其描述

1.4算法分析

15第十五页，共三十四页，编辑于2023年，星期三1.1研究内容数据结构课程的研究内容：软件设计中常用的基本技术包括哪些基本技术？下面从采用计算机来解决实际问题的过程中所涉及到的各步骤中的相关技术来对此作一分析：在用计算机解决实际问题时，一般要经过以下几个步骤：首先，对具体问题抽象出数学模型，然后针对数学模型设计出求解算法，选择或设计合适的数据结构存储相关数据，最后编出程序上机调试，直至得到最终的解答。下面简述各环节的有关内容。16第十六页，共三十四页，编辑于2023年，星期三1.1研究内容问题求解之一：问题建模：一般情况下，实际应用问题可能会各式各样，例如我们所熟悉的工资表的处理问题，学生成绩管理问题，电话号码查询，数据加密、压缩问题等。这些问题无论是所涉及到的数据还是其操作要求都可能存在一定的差异。尽管如此，许多应用问题之间还是具有一定的相似之处的。例如，虽然工资表和学生成绩表的具体信息（栏目）不同，但如果将两个表中的每个人的工资信息和成绩信息分别看作一个整体，则这两个表结构之间就有了某些共性。从操作方面来看，虽然对这两种表的操作存在差异，但也存在一些相同或相似的基本操作。例如，查询一个人的工资信息和成绩信息，修改有关信息等。17第十七页，共三十四页，编辑于2023年，星期三1.1研究内容正因为许多不同的问题之间存在着的某些共性，可以将一个具体问题用这些共性的形式描述出来-----建立模型。建立问题的模型通常包括：所描述问题中的数据对象，对象间关系的描述，问题求解的要求及方法等方面。建立问题模型的好处：通过建立模型，就可以将一个具体的问题转换为所熟悉的模型，然后借助于这一模型来实现。数据结构、离散数学及许多数学课程中就介绍了许多模型。例如，要描述一个群体中个体之间的关系时，可以采用”数据结构”和”离散数学”中所介绍的图结构。要描述一个工程内的关系或进展情况时，我们可以采用”数据结构”中所介绍的AOV网或AOE网等。即使所建立的模型没有现成的求解方法，借助于已有的模型的适当组合也相对易于构造求解方法。18第十八页，共三十四页，编辑于2023年，星期三1.1研究内容问题求解之二：构造求解算法在构建问题模型之后，使一个具体的问题就转变成了一个用模型所描述的抽象的问题。借助于这一模型以及已有的知识（例如数据结构中有关图结构的基本知识），我们可以相对容易地描述出原问题的求解方法，即算法。从某种意义上说，该算法不仅能实现原问题的求解，而且还可能实现许多类似的具体问题的求解，尽管这些具体问题的背景及其描述形式可能存在较大的差异。19第十九页，共三十四页，编辑于2023年，星期三1.1研究内容问题求解之三：选择或设计存储结构在构造出求解算法之后，需要考虑在计算机上实现求解了。为此，需要做两方面的工作：选择或设计合适的存储结构，以便将问题所涉及到的数据（包括数据中的基本对象及对象之间的关系）存储到计算机中。不同的存储形式对问题的求解实现有较大的影响，所占用的存储空间也可能有较大的差异。编写程序，实现问题求解。存储形式和问题要求决定了编写程序的方法。问题求解之四：测试在编写出完整的程序之后，需要经过测试才能交付使用。20第二十页，共三十四页，编辑于2023年，星期三1.1研究内容问题求解的过程框架：实际问题求解算法测试程序设计数据结构组织数据结构课程中的内容数学模型抽象

构造求解算法

数据结构设计

程序实现

数据结构：计算机类专业核心课程之一21第二十一页，共三十四页，编辑于2023年，星期三1.2术语下面介绍课程中所涉及到的一些术语数据（data）——能够输入到计算机中，并能被计算机处理的符号的集合。例如，工资表，学生成绩，电话号码簿，电子字典，一个家族关系的表示形式、表示一个群体中个体之间关系的图形描述等。如图图1-1.doc所示。编号姓名基本工资奖金……工资表示例AA2A1A11A3A12A311A21A32A31A121家族关系示例22第二十二页，共三十四页，编辑于2023年，星期三1.2术语

A1A2A3A5A4A6A8A7群体之间的认识关系图23第二十三页，共三十四页，编辑于2023年，星期三1.2术语虽然数据的形式及运算存在较大的差异，但存在共性：由若干具有独立意义的个体所组成，个体间存在着某些关系。对这些数据的运算也有某些相似之处。例如，在家族关系数据中，组成数据的基本个体是个人信息，其中各人之间存在着多种关系，如父子关系、兄弟关系、祖先－后代关系等。其中有些关系是直接表示出来的，还有一些关系则是隐含的。对家族关系数据，通常要涉及到查询特定个体间的关系、插入和删除个体等。24第二十四页，共三十四页，编辑于2023年，星期三1.2术语数据可以分解为元素的集合数据元素（dataelement）——构成数据的基本单位（具有完整的独立意义）。

例如工资表中的个人工资信息，成绩表中的学生成绩信息，家族关系中的个人等。在有些场合下，也称之为元素、记录、结点、顶点等。数据项（字段）——元素的具体描述信息。图1-1.doc25第二十五页，共三十四页，编辑于2023年，星期三1.2术语数据结构（datastructure）——构成数据的元素之间的结构关系。数据元素之间存在以下几类内在的关系：线性结构：元素之间具有次序关系树形结构（树型结构）图结构（网状结构）集合逻辑结构26第二十六页，共三十四页，编辑于2023年，星期三1.2术语逻辑结构——元素之间的内在结构关系（逻辑关系）线性、树形（树型）、图（网状）、集合存储结构——数据结构在内存中的实现形式运算------对数据所施加的运算。有关数据结构几个方面的联系图逻辑结构分析

运算实现（算法）

运算定义

存储结构抽象数据类型（ADT）

数据结构的组成27第二十七页，共三十四页，编辑于2023年，星期三1.3算法及其描述算法——特定问题的求解方法。较为粗略。另一种定义：指令的有限序列满足：

(1)输入0～n个

(2)输出1～n个

(3)确定性（无二义性）：指令的描述是确定的，使得对相同的输入能产生相同的输出结果。

(4)有限性：指令的执行次数有限。

(5)可行性：算法中的每条指令可用计算机指令的有限次执行来实现。28第二十八页，共三十四页，编辑于2023年，星期三1.3算法及其描述算法描述语言

易懂，灵活

自然语言不准确

准确，严格

计算机语言死板

伪语言（类语言）：类pascal、类C、类C++

算法举例：

1.求最大公因子（辗转相除法）

2.韩信点兵问题

3.幻方问题（纵横图）29第二十九页，共三十四页，编辑于2023年，星期三1.4算法分析算法的衡量指标：在正确性的前提下，重点关注以下指标:

（1）时间性能——运行算法所需的时间开销。（2）空间性能——运行算法所需的辅助空间的规模。（3）其它性能——如可读性/可移植性等。时间性能（时间复杂度）的描述方法讨论：

(1)以运行算法d的机器时间开销来度量问题是：与具体机器相关，难以比较

（2）以算法中语句的执行次数来衡量问题是：计算麻烦，可以简化为（3）以算法中语句的执行次数的数量级来替代。

30第三十页，共三十四页，编辑于2023年，星期三1.4算法分析数量级：如果变量n的函数f(n)和g(n)满足：

limf(n)/g(n)=常数k(k≠∞,0)，则称f(n)和g(n)是同一数量级的，