《数据结构》教案(64课时)

四川城市职业学院教案课程名称数据结构与算法课程性质必修课开课学期2017-2018第1学期学时数64开课系（部）汽车与信息工程学院授课班级16级软件技术2班主讲教师林琳职称副教授二O一七年九月

填写说明1、封面中课程性质是指公共必修课、专业必修课、公共选修课、专业选修课等。2、教案首页中的授课类型是指理论授课、实验课、习题课、课堂讨论、课程设计、实作等。3、教学步骤及主要内容包括教学设计、教学内容、过程、方法。4、备注包括时间安排、媒体应用、对教材的整合等；对教材的整合包括删减的内容、补充、更新的内容等。5、教师每次课都要写一份教案（一次课计2学时），新教师和年轻教师还应准备讲稿或课件。

四川城市职业学院备课环节质量标准及评价方案一、备课环节质量标准（一）基本要求备课是教学过程的起始环节，是教师在课堂讲授之前进行的教学设计准备工作。备课环节主要包括把握大纲、钻研教材、准备教学进度表和讲稿、设计教案、开发课件、准备教具、试验预做、实践教学内容及实施设计、考核等工作。备课环节的基本要求是：（1）改革教学方法和手段，融“教、学、做”为一体。（2）合理安排理论教学与实践教学的内容和比例，备课要体现理论教学必需、够用的原则。（3）教师备课除认真、深入钻研教材外，必须广泛猎取和掌握丰富的相关知识，要特别注意吸收新思想、新信息，掌握本专业领域的新知识、新技术、新方法、新工艺，充实备课内容。教师备课应紧扣教材，又不拘于教材，应参阅本课程其他教材或专著，深入钻研、分析，集众家之所长，择其精华而授之。（4）备课时既要考虑面向全体学生，又要兼顾差异教育，因材施教，克服教学中的片面性和一般化，讲究备课的针对性。要针对大纲、针对教材、针对授课对象，结合课程特点和自己的教学风格，使备课工作具有实效性。（5）教师备课时要掌握教材的内容、特点，弄清主要问题的来龙去脉及领悟关键内容的前因后果，精心构思教学内容的先后次序和重点内容的展开与深入步骤，做到条理分明，层次清楚，注意教学设计的层次性。（6）教师要注重备课的计划性，对每一章节、每一单元的知识点认真进行梳理，对分析判断结果加以整理、归纳，编制学期教学进度计划表，并编写成教案。（二）质量标准教学环节观测点参考权重等级标准备注AC1.备内容1.1钻研教学大纲0.4掌握所授课程在本专业人才培养过程中的地位和作用，理解本门课程与其它课程的相互关系；钻研吃透教学大纲精神，明确本课程的教学目的、任务和“三基”内容与要求，掌握本课程内容的深度、广度及要点、重点、难点、疑点和弱点了解所授课程在本专业人才培养过程中的地位、作用，了解本门课程与其它课程的相互关系；基本明确本课程的教学目的、任务和“三基”内容与要求，基本掌握本课程内容的深度、广度及要点、重点、难点根据学科专业特点和具体实际情况可进行适当调整

教学环节观测点参考权重等级标准备注AC1.2钻研教材0.3清楚与本课程有关的“已学课程”和“后续课程”的内容及相关知识点，钻研透本教材的知识结构，弄清教材的重点章节和各章节的重点、难点，对插图的构思及意义、练习的安排与解答等了如指掌，并有针对性地适度拓展备课内容；能够深入挖掘教材中有利于学生能力培养和思想提高的潜在因素，寓于讲稿之中了解本课程教学内容与已学课程的关系，基本清楚本教材的知识结构，明确教材的重点章节和各章节的重点、难点，对插图的构思及意义、练习的安排与解答等做到心中有数根据学科专业特点和具体实际情况可进行适当调整1.3准备教学资料0.3能够广泛阅读有关教学参考资料，并能结合教材的不足给学生推荐学习参考书，能够针对所授课程的内容，广泛搜集典型案例和工程案例，并融入教学内容之中能够阅读有关教学参考资料，向学生推荐学习参考书，能够针对所授课程的内容，寻找典型案例和工程案例，准备用于教学2.备学生2.1学生知识基础0.3了解所授对象的生源构成，清楚学生的文化基础和已学课程情况，研究学生的知识水平现状基本了解所授对象的文化基础和已学课程情况2.2学生学习能力0.3了解学生的思想情况、品德意志、学习态度和思维方式，了解学生自习情况和学习习惯，掌握学生在学习方面的个体差异基本了解学生的思想情况、学习态度和思维方式，了解学生自习情况和学习习惯2.3学生学习要求0.4针对本课程，收集学生在学习上的疑点、难点和对教学的意见等，能根据所获得的信息后，及时恰当地设计或修订教学方案了解学生的学习要求，并在教学方案设计中有所体现3.备方法3.1讲授次序0.2备课时能够根据学生的认知特点，根据由浅入深、由近及远、从具体到抽象、循序渐进的教学原则来编写教案，对导入新课、讲授、复习巩固、小结等过程设计合理备课中能够根据教学的基本规律研究如何导入新课、讲授、复习巩固、小结等过程3.2讲课重点0.3能够针对课程特点，在备课中注意突出重点，化解难点，抓住关键，处理弱点（易混、易错内容），能够科学合理地安排教学内容能够从本课程要求出发，注意突出重点，化解难点；能够合理地安排教学内容

教学环节观测点参考权重等级标准备注AC3.备方法3.3教学方法0.3对于学生在学习过程中易混淆、易差错或易疏忽的问题，能采取设问、质疑、比较、讨论等方法搞清楚；能够采用讲授与自学、讨论与交流、指导与研究、理论学习与案例分析、理论学习与实践实习、相结合的教学方法，注意因材施教和个性化教学，强化学生的学习动机能基本克服“满堂灌”的现象，采用某些启发式的教学方法，并注意到因材施教根据学科专业特点和具体实际情况可进行适当调整3.4教学手段0.2有自主开发的教育软件或CAI课件，不断更新教学手段，开发虚拟工厂、虚拟车间、虚拟工艺、虚拟实验部分章节能够采用现代教育技术进行教学，注意教学手段的改进4.备结构4.1教学步骤0.3能够结合讲授内容合理安排教学步骤，对学生预习、导入新课、讲授新课、复习巩固、课末小结等有精心的构思，做到有条不紊、环环相扣、严谨有序有关学生预习、导入新课、讲授新课、复习巩固、课末小结等过程基本完整4.2时间分配0.3能够根据不同内容、不同要求及重要性，科学划分教学时数，同时结合讲授内容合理安排每次课的时间进程，做到内容紧凑，时间分配科学，留有余地各章节教学学时安排合理，每次课教学内容适当4.3教学组织0.2精心设计教学环节，师生双边活动安排适当，计划周密科学，能够联系生产实际、生活实际和社会实际，做到教书育人能有效设计教学环节，教学组织合理4.4板书设计0.2有详细的板书设计，图表交代清楚，投影、幻灯等手段交互应用科学可行，布局合理、富于启发，充分显示重点内容有的板书设计，布局合理，条理比较清楚，重点内容容易得到体现5.备教具5.1教具器材0.4熟悉常用教具器材的功能和使用方法，教案设计中明确上课演示要用到的教具和器材名称备课中列出了各章节教学中要用到的教具和器材5.2案例资料0.3针对专业课程教学需要，对典型案例资料进行梳理，其资料的引用和介绍写入教案，做到安排紧凑，突出实效对典型工程案例资料进行了一般性的梳理，教案中有文字说明5.3实验试做0.3课前对演示性实验应亲自试做，对试做中出现的问题有原因分析和处置方法，精心设计实验程序对不太熟悉的实验进行了试做

教学环节观测点参考权重等级标准备注AC6．备进度6.1教学进度表0.4认真编写教学进度表，表中各项目完整，说明清楚，理论教学、辅副教授学（实验、操作、讨论、习题）等环节安排科学；教学进度表在学期第一周编制完成，经教研室主任和教学单位教学负责人审核后及时上报表中各项目完整，说明比较清楚，理论教学、辅副教授学（实验、操作、讨论、参观、习题课等）等环节安排比较恰当，能按时上交教学进度表根据学科专业特点和具体实际情况可进行适当调整6.2教案0.6课堂教学目标明确，安排教学内容详细，重点突出，各项目填写规范、内涵完整、整体和谐。教案按规定要求分章节编写，在讲课前已全部完成课堂教学目标比较明确，重点突出；各项目填写较规范；教案按规定要求分章节编写，并在讲课前完成二、备课环节质量评价方案1．评价方案以《备课环节质量标准》为依据，以系或教学组为单位，通过审阅任课教师的授课计划、教案和讲稿，按《四川城市职业学院备课质量评价表》中评价要素的内涵和评价方法，对教师的备课质量进行评价。首先对各评价要素定等级，评价等级分为A、B、C、D四档，按《备课环节质量标准》中A、C的标准，低于A高于C为B，低于C为D；然后打出评价基元的得分，得分＝∑评价要素分值*等级系数（等级系数：A∶0.9、B∶0.75、C∶0.6、D∶0.1）。评价总分S等于每项得分之和，评价结果按优秀、良好、合格、不合格四级评定，优秀：87≤S<100；良好74≤S<87；合格：60≤S<74；不合格：S<60。2．有关说明①备课环节质量评价一般由系组织实施，教务处监督检查；②尚未获得主讲教师资格的青年教师必须通过系组织的备课质量评价，并和其他教学环节的评价结果一起作为晋升职称的重要依据；③各系可以采用抽查、教案展评等方式，促进备课质量的提高；④各系要对评价过程中发现存在问题的教师端正态度。对备课态度较认真、但备课质量不高的教师，应该及时配备指导教师，请有经验的教师加以指导，提高备课质量。四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题数据结构概述授课教师林琳职称副教授授课日期授课类型理论学时数8教学目的及要求掌握数据结构课程的基本任务；掌握数据结构相关的基本概念；掌握逻辑结构的分类和各种逻辑结构的基本特点；教学重点数据结构相关的基本概念；逻辑结构的分类；教学难点

数据结构相关的基本概念；

教学方法结合实际生活的案例讲授基本理论，

课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注基本内容：

课程简介。5分钟第1节数据结构学科概念及其所研究的主要内容一、用计算机解决实际问题的一般步骤：10分钟1、问题定义。分析问题是什么？明确问题要求是什么？理解问题做什么？2、建立模型。将实际问题中的客观对象的属性及联系，抽形成逻辑数据模型。3、定义数据。降落及数据模型数据化，定义成计算机能存储处理的存储结构。4、寻找算法。根据存储结构，找出求解问题的策略和方法步骤。5、编写程序。将算法用计算机语言表示出来。6、调试运行。将数据和程序输入计算机，查错修改，运行得到结果。7、分析结果。计算结果是否符合要求，若符合则结束，否则，返回监察修改。建立模型和寻找算法是较困难的两个步骤。二、《数据结构》学科概念描述。20分钟计算机应用的特点：处理的数据量大且数据之间存在一定的关系；对数据的操作不单纯是数值计算（仅占计算机数据处理的10%），更多地是需要对其进行非数值计算（占计算机数据处理的90%）。如检索、排序、插入、删除等。数值计算问题在《数值分析》（计算方法）学科中专门研究。非数值计算问题是《数据结构》学科所要讨论的内容。1、数据结构建模举例例1图书管理问题。此例建立的是线性表。类似的学生管理、人事管理、物资管理、商品管理等大量问题都可以抽象出类似的线性数据结构。例2排课问题。此例建立了一种图状数据结构。另有像交通管理、工程管理等大量问题可以抽象出图状数据结构。课程编号 课程编号 课程名称 先修课程 C1 计算机导论 无 C2 数据结构 C1，C4 C3 汇编语言 C1 C4 C程序设计语言C1C5 计算机图形学C2，C3，C4 C6 接口技术 C3 C7 数据库原理 C2，C9 C8 编译原理 C4 C9 操作系统 C2 （a）计算机专业的课程设置C1C2C3C6C4C5C9C7C8（b）表示课程之间优先关系的有向图图1.2教学计划编排问题的数据结构2、《数据结构》学科的概念综上所述可以对《数据结构》作为一门学科给出一种描述性的定义：数据结构是研究计算机非数值计算程序设计问题中的数据、数据之间的联系以及数据操作的专门学科。三、数据结构研究的主要内容5分钟《数据结构》学科概念已经包含了所研究的问题，更具体一点，《数据结构》研究的内容可以说有5个方面：1、数据的逻辑结构。2、数据的存储结构。3、数据的操作算法。4、算法的效率分析。5、数据结构的应用。第2节基本概念和术语一、关于数据的几个概念10分钟1、数据。是对客观事物的符号表示。在计算机科学是指所有能够输入到计算机中并能被计算机程序处理的符号集合。包括数值、文字、图像、图像、音频、视频等形式。2、数据项。所谓数据项就是数据中具有独立含义的、不可再分割的最小数据单位。是客观实体一种特征的数据表示。3、数据元素。是多个相关数据项的集，是一个客观实体多种特征的数据描述，是计算机程序中加工处理的基本单位（数据存储和组织的单位）。数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。如前面例子中的书目信息、棋盘格局和图的顶点等都是数据元素。二、数据结构的几个概念。30分钟1、数据结构，就是相互之间存在一种或多种特定关系的数据元素的集合。可以简单表示为：数据结构=数据+关系，同一数据元素集合，所定义的关系不同，构成不同的数据结构。数据结构包括逻辑结构和存储结构两个方面。2、数据的逻辑结构。是指对数据及其关系的抽象逻辑描述，独立于计算机，与机器实现无关。根据定义的关系不同，数据的基本逻辑结构分为四种：集合结构。数据元素之间未定义任何关系的松散集合。线性结构。数据元素之间定义了次序关系的集合，描述的是1对1关系。树形结构。数据元素之间定义了层次关系的集合，描述的是1对多关系。图状结构。数据元素之间定义了网状关系的集合，描述的是多对多关系。

3.课后习题练习10分钟四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题数据结构概述2授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握存储结构的概念；掌握顺序和链式存储结构的存储方法和特点；掌握算法的概念和特点；掌握算法的评价指标和大O标记法分析时、空间复杂度；教学重点顺序存储结构和链式存储结构的存储方法和特点；算法时、空间复杂度分析方法。教学难点

顺序存储结构和链式存储结构的存储方法和特点；算法时、空间复杂度分析方法。

教学方法结合实际生活的案例讲授基本理论；结合简单算法讲解算法分析的方法。

课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注基本内容：

1.存储结构30分钟数据结构包括数据的逻辑结构（LogicalStructure）和数据的物理结构（PhyicalStructure）。存储结构与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。常见的存储结构有：顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。索引存储方式：数据元素通过索引表相连系；散列存储方式：数据元素通过散列函数相连系；1346元素31536…….……..…….1536元素21400…….……..…….∧元素413461400元素1346元素31536…….……..…….1536元素21400…….……..…….∧元素413461400元素11345指针存储内容存储地址链式存储1345∧1536元素21400元素11346元素3元素4head2。算法的概念20分钟算法：是对特定问题求解步骤的一种描述，使得问题能在有限时间内被机械求解。算法的五个特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。可行性：算法的每一步都是能够实现的，即可操作的。输入：一个算法具有零个或多个输入，这些输入取自特定的数据对象集合输出：算法执行完毕，必须有一个或若干个输出结果。评价算法：正确性、易读性、健壮性、效率和低存储量。3.算法性能分析与度量30分钟时间复杂度一个程序的时间复杂度（TimeComplexity）是指程序运行从开始到结束所需要的时间。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。许多时候要精确地计算T(n)是困难的，我们引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。定义（大Ο记号）：如果存在两个正常数c和n0，使得对所有的n，n≥n0，有：f(n)≤cg(n)则有：f(n)＝Ο(g(n))例如，一个程序的实际执行时间为T(n)＝2.7n3+3.8n2+5.3则T(n)＝Ο(n3)。通常用Ο(1)表示常数计算时间。常见的渐进时间复杂度有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)空间复杂度是指程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括以下两部分：固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。4.练习10分钟四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题线性表及其顺序存储结构授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握线性表的基本概念和特点；掌握线性表逻辑结构的表示和各操作的含义；掌握顺序表存储结构和各种操作在顺序表中的实现；进一步理解顺序存储结构的特点。教学重点线性表逻辑结构的表示和各操作的含义；顺序表存储结构和各种操作在顺序表中的实现；教学难点

顺序表存储结构和各种操作在顺序表中的实现；

教学方法结合实际生活的案例讲授基本理论，结合操作代码讲解各个操作的实现。

课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注基本内容：一、线性表的定义及特点15分钟1、线性表的定义。线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,...,ai-1,ai,ai+1,...,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。例1La=（34，89，765，12，90，-34，22）数据元素类型为int。Ls=(2Hello2,2World2,2China2,2Welcome2)数据元素类型为string。Lb=(book1,book2,...,book100)数据元素类型为下列所示的结构类型：structbookinfo{intNo;//图书编号char*name;//图书名称char*auther;//作者名称...;}2、线性表的特点。有序性：除第一个元素外，每个元素有且仅有唯一一个直接前驱，第一个元素无直接前驱，除最后一个元素外，每个元素有且仅有唯一一个直接后继，最后一个元素无直接后继。这种次序描述了元素之间的1对1联系。抽象性：数据元素可以是任意类型。同质性：数据元素具有相同的类型。二、线性表的基本操作10分钟初始化线性表LInitList(L)销毁线性表LDestoryList(L)清空线性表LClearList(L)求线性表L的长度ListLength(L)判断线性表L是否为空IsEmpty(L)获取线性表L中的某个数据元素内容GetElem(L,i,e)检索值为e的数据元素LocateELem(L,e)返回线性表L中e的直接前驱元素PriorElem(L,e)返回线性表L中e的直接后继元素NextElem(L,e)在线性表L中插入一个数据元素ListInsert(L,i,e)删除线性表L中第i个数据元素ListDelete(L,i,e)三、线性表的顺序存储结构定义及其特点15分钟1、线性表的顺序存储结构（顺序表）线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图所示：其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式:LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L

(其中L是每个元素的长度)2、顺序存储结构的特点（1）一致性。在顺序表中，利用数据元素的存储位置相邻，表示线性表中数据元素之间的相邻前后关系，逻辑结构与存储结构（物理结构）一致；（2）可随机访问性。在访问顺序表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。（3）经济性。节省空间和时间。（4）不方便性。对插入、删除等操作效率较低，需要移动大量元素。

（5）不便于扩充性。要动态增加元素个数较困难。3、顺序存储结构的类型定义数组形式定义：#defineMaxsize100/*预留数组的最大容量*/typedefstruct{datatypeData[Maxsize];intlast;}SeqList,*L;最多能存放Maxsize个元素Last=最后一个元素数组下标值，<=Maxsize-1.有n个元素时Last=n-1表长为Last+1表长为空时Last=-1线性表的存储空间通过malloc函数获取，格式为：malloc(sizeof(SeqList))返回值为地址值Data数组元素的引用方式有：L.Data[i]或L->Data[i]最后一个数组元素的引用用Last表示时方式有：L.Data[L.last]或L->Data[L->last]四、线性表的典型操作算法的实现40分钟（1）初始化线性表LSeqList*init_SeqList(){SeqList*L;L=malloc(sizeof(SeqList));L->last=-1;returnL;}主函数的调用main()SeqList*Q;Q=init_SeqList();....在第i位置插入运算：insert_seqlist（Seqlist*L，inti,datatypex）{intj;if(L->last>=maxsize-1){printf(＂表满＂);return(-1);}if（i<1‖i>L->last+2）{printf(＂位置错＂);return(0);}for(j=L->last;j>=i-1;j--)L->data[j+1]=L->data[j];L->data[i-1]=x;L->last=L->last+1;}最坏情况时间复杂性为n,量级为O(n);时间的平均复杂性为：n+1n+1(0+1+2+...+n)=2n删除第i个元素：delete_seqlist（Seqlist*L，inti）{intj;if（i<1‖i>L->last+1）{printf(＂不存在第i个元素＂);return(0);}for(j=i;j<=L->last;j++)L->data[j-1]=L->data[j];L->last=L->last-1;return(1);}最坏情况时间复杂性为n-1,量级为O(n);时间的平均复杂性为：==n(0+1+...+(n-1))2n-1分析插入和删除算法可得如下结论:顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。定位操作实现：intLocation_SeqList(SeqList*L,datatypex){inti=0;while(i<=L.last&&L->data[i]!=x)i++;if(i>L->last)return-1;elsereturni;/*返回的是存储位置*/}最坏情况时间复杂性为n,量级为O(n);时间的平均复杂性为：==n(1+2+...+n)2n+1线性表的应用举例：10分钟例2.1将顺序表(a1，a2，...，an)重新排列为以ai为界的两部分：ai前面的值均比ai小，ai后面的值都比ai大voidpart(SeqList*L){inti,j;datatypex,y;x=L->data[0];/*将基准置入x中*/for(i=1;i<=L->last;i++)if(L->data[i]<x)/*当前元素小于基准*/{y=L->data[i];for(j=i-1;j>=0;j--)/*移动*/L－>data[j+1]=L->data[j];L->data[0]=y;}}四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题线性表及其链式存储结构授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握掌握单链表的相关C语言定义；理解并掌握头结点在链表操作中的作用；掌握链表基本操作的实现；理解链式存储的优点和应用；教学重点链表的C语言定义；链表各个操作的实现。教学难点链表的C语言定义；链表各个操作的实现。教学方法结合实际生活的案例讲授基本理论，结合算法代码讲解各个基本操作的实现。

课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注基本内容：一、线性表的链式存储结构30分钟线性表顺序存储结构的缺点是在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。1、线性表的链式存储结构：指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图所示的形式存储：2、链式存储结构的特点（1）不一致性。线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）只能顺序访问性。在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。（3）插入、删除操作方便性。不需移动元素，数据个数可动态增长。（4）不连续占用存储空间。但浪费空间较多。链式存储结构适合于数据各是动态变化、插入、删除频繁的场合。线性表的链式存储结构描述：线性表的单链表存储结构可用C语言中的“结构指针”来描述typedefstructNode{datatypedata；structNode*next；}LNode，*Linklist,*H；通常指针P是一个动态变量，在需要时由库函数malloc(size)产生，如:p=malloc(sizeof(Lnode))该函数分配一个Lnode数据类型所占的空间长度存放数据元素并返回一个该空间的起始地址给指针P。当该结点不再需要时，可由free(p)释放空间。p->data表示一个数据元素；p->next表示下一个元素的起始存放地址的指针。二、链表的典型操作的算法实现50分钟

创立单链表(在表头添加)linklistcreat_linklist(){linklistL=null;LNode*s;intx;scanf(“%d”,&x)；while(x!=-1)//或另外指定一flag值{s=malloc(sizeof(LNode))；s->data=x;s->next=L;L=s；scanf(%d”,&x)；}returnL;}建立单链表（在表尾添加）linklistcreat_linklist(){linklistL=null;Lnode*s,*r=null;intx;scanf(“%d”,&x)；while(x!=-1){s=malloc(sizeof(LNode))；s->data=x;if(L==null)L=s；elser->next=s；r=s；scanf(%d”,&x)；}if(r!=nullr->next=null)；returnL;}求单链表的表长(带头结点)intlength_linklist(linklistL){LNode*p=L;//p指向首节点Lj=0;while(p->next!=NULL)//当P指向an时,p->next为空,结束{p=p->next;//第一次循环P为首节点的指针域里的值,即指向节点a1j++;}//表长计算从首节点a1开始到an.return(j);}按序号查找(找表中第i个结点,返回该节点序号或指针)查找方法:从头指针开始,修改指针p=p->next,使顺链表顺序往下搜索,直到找到为止.查找次数为i次.LNodeGet_linklist(linklistL,inti){LNode*p=L;j=0;while((p->next!=NULL)&&(j<i))//当P指向an时,p->next为空或P已指向节点i时结束{p=p->next;/*第一次循环P指向首节点a1*/j++;}/*表长计算从首节点a1开始到an.*/if(i==j)return(p);elsereturn(Null);}按值查找(找与给定值x相等的第一个结点,返回该节点指针)LNode*locate_linklist(linklistL,datatypex){LNode*p=L->next;while((p!=Null)&&(p->data!=x)){p=p->next;}if(p->data==x)return(p);elsereturn(0);}单链表的插入运算(后插)算法思路：1.找到第i-1个结点；若存在继续2，否则结束2.申请、填装新结点；3.将新结点插入。结束。voidinsert_linklist(linklistL,inti,datatypex){p=L;j=0;while(p&&(j<i-1)){p=p->next;++j;}if(!p½½j>i-1)returnERROR;s=(linklist)malloc(sizeof(structNode));s->data=x;s->next=p->next;p->next=s;returnOK;}在结点P前插入结点S:需要找到*P的前驱结点*q,然后再完成在*q后插入*s结点的操作.q=L;①while(q->next!=p)q=q->next;②s->next=q->next;③q->next=s;单链表的删除运算：1).要删除P所指结点,首先要找到P的前驱结点q，再完成下列操作：q->next=p->next;free(p);单链表的删除运算(删除第i个节点的元素ai)voidDel_Linklist(linklistL,inti){LinkListp=L;s=L;j=0;while(p->next!=null&&j<i-1){p=p->next;++j;}if(!(p->next)½½j>i-1)returnERROR;s=p->next;p->next=s->next;free(s);returnOK;}应用举例10分钟已知单链表H，写一算法将其倒置。即实现如图的操作。(a)为倒置前，(b)为倒置后。单链表的倒置单链表的倒置25∧45187629H29∧76184525H(a)(b)算法思路：依次取原链表中的每个结点，将其作为第一个结点插到新链表中去，指针p用来指向当前结点，p为空时结束。算法如下：voidreverse(LinklistH){LNode*p,*q;p=H->next;/*p指向第一个数据结点*/H->next=NULL;/*将原链表置为空表H*/while(p){q=p;p=p->next;q->next=H->next;/*将当前结点插到头结点的后面*/H->next=q;}}四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题队列及其应用授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握队列的逻辑结构、特点和操作定义；掌握队列存储结构及其算法；能计算各算法的时间复杂度。教学重点队列的逻辑结构、特点和操作定义；队列存储结构及其算法；教学难点队列存储结构及其算法；教学方法课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注一、队列的逻辑结构及特点1、概念队:是一种限定在一端进行插入而在另一端进行删除的线性表,遵循先进先出（FirstInFirstOut，LIFO）的原则。进队：从队尾插入一个新的队尾元素。出队：将一个队中的队头元素删除。存储结构：有顺序存储和链接存储两种结构，链接存储的队叫链队。2.队列的抽象数据类型的定义ADTQueue{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}约定其中a1端为队列头，an端为队列尾。基本操作：InitQueue(&Q)操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。操作结果：队列Q被销毁，不再存在。ClearQueue(&Q)初始条件：队列Q已存在。操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。QueueLength(Q)初始条件：队列Q已存在。操作结果：返回Q的元素个数，即队列的长度。GetHead(Q,&e)初始条件：Q为非空队列。操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。操作结果：插入元素e为Q的新的队尾元素。DeQueue(&Q,&e)初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADTQueue二、顺序队列算法及实现1、详见课件2、算法时间复杂度分析三、链队列和循环队列1、存储结构和算法2、时间复杂度分析。四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题串的模式匹配授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握基本串的模式匹配算法及实现；理解KMP算法；掌握next函数值的计算方法。教学重点基本串的模式匹配算法及实现；KMP算法；教学难点next函数值的计算方法。教学方法课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注一、基本模式匹配算法1、特别要理解其执行过程中主串和模式串的指针的变化，在指针回退时两个指针应该回退的位置；2、要理解算法中循环控制条件的意义，明确循环结束的两种不同的条件及其代表的意义，以及在循环终止后，如何得到判定结论。二、KMP算法在理解一般匹配算法指针回退意义的基础上再来看KMP算法相对就比较容易了。KMP算法的改进主要体现在不匹配时指针的回退距离减小了：主串可以不动，而模式串也只须退到NEXT[]位置。三、求解NEXT[]数组值过程是一个自身的模式匹配的过程。其顺序要自前往后来实现。注意NEXT[]数组和NEXTVAL[]数组的区别。四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题数组及其应用授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特殊矩阵进行压缩存储时的下标变换公式。教学重点数组的两种存储表示方法教学难点数组的两种存储表示方法教学方法课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注一、数组的定义和基本运算1、数组的定义。数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。2、二维数组结构的基本操作：（1）给定一组下标，修改该位置元素的内容Assign(A,elem,index1,index2)（2）给定一组下标，返回该位置的元素内容Value(A,elem,index1,index2)二、数组的存储结构及其算法1、数组的存储结构定义从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。LOC(i,j)=LOC(0,0)+(n*i+j)*L数组结构的类型定义：#defineMAX_ROW_INDEX10#defineMAX_COL_INDEX10typedefstruct{Elemtypeelem[MAX_ROW_INDEX][MAX_COL_INDEX];}ARRAY;2、数组基本操作算法（1）给数组元素赋值voidAssign(ARRAY*A,Elemtypeelem,intindex1,intindex2){if(index1<0||index1>=MAX_ROW_INDEX||index2<0||index2>=MAX_COL_INDEX)exit(ERROR);elseA->elem[index1][index2]=elem;}（2）返回给定位置的元素内容intValue(ARRAYA,Elemtype*elem,intindex1,intindex2){if(index1<0||index1>=MAX_ROW_INDEX||index2<0||index2>=MAX_COL_INDEX)returnFALSE;else{*elem=A.elem[index1][index2];returnOK;}}三、矩阵的压缩存储结构及其操作算法1、矩阵的压缩存储结构对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。三种特殊矩阵的压缩方法：。（1）对称矩阵。对称矩阵的特点是aij=aji。一个n×n的方阵，共有n2个元素，而实际上在对称矩阵中有n(n-1)/2个元素可以通过其他元素获得。压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。举例：假设定义一个数组型变量：intA[10];k是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。操作算法的实现：intValue(intA[],Elemtype*elem,inti,intj){if(i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDEX)returnFALSE;else{if(i>=j)k=i*(i-1)/2+j-1;elsek=j*(j-1)/2+i-1;*elem=A[k];returnTRUE;}}（2）下（上）三角矩阵下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。例如：操作算法的实现：intValue(intA[],Elemtype*elem,inti,intj){if(i<1||i>MAX_ROW_INDEX||j<1||j>MAX_COL_INDEX)returnFALSE;else{if(i>=j)k=i*(i-1)/2+j;elsek=0;*elem=A[k];returnTRUE;}}四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题广义表及其应用授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握广义表的ADT定义，逻辑结构特点与表示。掌握广义表基本操作的算法及Java程序实现。教学重点广义表的ADT定义，逻辑结构特点与表示。广义表基本操作的算法及Java程序实现。教学难点广义表基本操作的算法及Java程序实现。教学方法课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注一、广义表的类型定义广义表是一种递归的结构------这是其非常重要的属性。因为任何广义表都可以拆分成表头、表尾两个部分或者拆分成N个子表，所以广义表就可以用表头表尾分析法或子表分析法来表示，并且对于一个广义表的操作都可以转换成对其表头、表尾的递归操作或对N个子表的递归操作。要通过对广义表的学习来认真的品位一下递归算法的设计特点和设计思路。ADTGlist{数据对象：D＝{ei|i=1,2,..,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet为某个数据对象}数据关系：LR＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}}ADTGlist广义表是递归定义的线性结构。广义表是一个多层次的线性结构。二、广义表的结构特点1)广义表中的数据元素有相对次序;2)广义表的长度定义为最外层包含元素个数;3)广义表的深度定义为所含括弧的重数;注意:“原子”的深度为0;“空表”的深度为1。4)广义表可以共享;5)广义表可以是一个递归的表;递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表LS=(a1,a2,…,an)均可分解为表头Head(LS)=a1和表尾Tail(LS)=(a2,…,an)两部分三、广义表操作的递归函数1、递归函数的概念和特点；2、如何设计递归函数；3、广义表的递归算法：求广义表的深度、复制广义表和创建广义表的存储结构。四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题树和二叉树授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握树的ADT定义、逻辑结构特点；掌握二叉树的定义及特点；掌握二叉树的存储结构和基本操作。教学重点二叉树的存储结构和基本操作。教学难点二叉树的存储结构和基本操作。教学方法课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注一、树的定义和基本运算

1、树的定义

树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归的。

树的其他术语结点：数据元素的内容及其指向其子树根的分支统称为结点。结点的度：结点的分支数。终端结点：（叶子）度为0的结点。非终端结点：度不为0的结点。结点的层次：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度：树中所有结点度的最大值。树的深度：树中所有结点层次的最大值。有序树和无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为

有序树，否则称为无序树。森林：是m（m≥0）棵互不相交的树的集合。

在树结构中，结点之间的关系又可以用家族关系描述，定义如下：

孩子与双亲。结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。

子孙。以某结点为根的子树中的所有结点都被称为是该结点的子孙。

祖先。从根结点到该结点路径上的所有结点。

兄弟。同一个双亲的孩子之间互为兄弟。

堂兄弟。双亲在同一层的结点互为堂兄弟。

2、树的基本运算常用操作：（1）构造一个树CreateTree(T)（2）清空以T为根的树ClearTree(T)（3）判断树是否为空TreeEmpty(T)（4）获取给定结点的第i个孩子Child(T,linklist,i)（5）获取给定结点的双亲Parent(T,linklist)（6）遍历树Traverse(T)

对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依

二、树的存储结构1、双亲表示法2、孩子表示法

这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。3、孩子兄弟表示法

孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系。三、二叉树的定义和结构特点

1、定义：二叉树是另一种树形结构。它与树形结构的区别是：

（1）每个结点最多有两棵子树；

（2）子树有左右之分。

二叉树也可以用递归的形式定义：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。

二叉树的5种形态

2、二叉树的基本运算(略见教材)（1）构造一棵二叉树CreateBTree(BT)（2）清空以BT为根的二叉树ClearBTree(BT)（3）判断二叉树是否为空BTreeEmpty(BT)（4）获取给定结点的左孩子和右孩子LeftChild(BT,linklist)，RightChild(BT,linklist)（5）获取给定结点的双亲Parent(BT,linklist)（6）遍历二叉树Traverse(BT)二、二叉树的性质二叉树具有下列5个重要的性质。性质1、在二叉树的第i层上最多有2i-1个结点（i≥1）。

证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。

因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：

n=n0+n1+n2

（1）

再看分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。

又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。

将此式代入上式，得：

n=n1+2n2+1

（2）

用（1）式减去（2）式，并经过调整后得到：n0=n2+1。

满二叉树：

如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。

完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。性质4、具有n个结点的完全二叉树的深度为?log2n?+1。其中，?log2n?的结果是不大于log2n的最大整数。

证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：

2K-1-1<n≤2K-1

将不等式两端加1得到：

2K-1≤n<2K

将不等式中的三项同取以2为底的对数，并经过化简后得到：

K-1≤log2n<K

由此可以得到：?log2n?=K-1。整理后得到：K=?log2n?+1。性质5、对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n），都有：（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为i/2。（2）如果2i>n，则结点i没有左孩子；否则其左孩子结点的编号为2i。（3）如果2i+1>n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。利用数学归纳法证明。首先证明（2）和（3）。

当i=1时，若n≥3，则根的左、右孩子的编号分别是2，3；若n<3，则根没有右孩子；

若n<2，则根将没有左、右孩子；以上对于（2）和（3）均成立。

假设：对于所有的1≤j≤i结论成立。即：结点j的左孩子编号为2j；右孩子编号为

2j+1。

由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。

可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编号为2(i+1)；右孩子编号为2(i+1)+1。

又因为二叉树由n个结点组成，所以，当2(i+1)+1>n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)>n，结点i+1既没有左孩子也没有右孩子。

以上证明得到（2）和（3）成立。

利用上面的结论证明（1）。

对于任意一个结点i，若2i≤n，则左孩子的编号为2i，反过来结点2i的双亲就是i，而2i/2=i；若2i+1≤n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而

(2i+1)/2=i，由此可以得出（1）成立。三、二叉树的存储结构

二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。

1、顺序存储结构

这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构

2、链式存储结构

在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。

常见的二叉树结点结构如下所下所示：

其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，elem是数据元素的内容。下面是一棵二叉树及相应的链式存储结构

这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。教学重点：树的ADT定义、逻辑结构特点；二叉树的定义及特点；二叉树的存储结构和基本操作。教学难点：二叉树的性质和存储结构。四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题遍历二叉树和线索二叉树授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握遍历二叉树的三种算法；掌握三种遍历二叉树的递归算法的实现；掌握线索二叉树的概念的二叉树的线索化方法。教学重点三种遍历二叉树的递归算法的实现；教学难点三种遍历二叉树的递归算法的实现；教学方法课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注一、遍历二叉树二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。

二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。

1、按根、左子树和右子树三部分进行遍历遍历二叉树的顺序存在下面6种可能：

TLR（根左右）,TRL（根右左）

LTR（左根右）,RTL（右根左）

LRT（左右根）,RLT（右左根）

其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列

（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。二、遍历算法的实现（1）先序遍历递归算法

voidPreOrder(BTreeBT){

if(BT){Visit(BT);

PreOrder(BT->Lchild);

PreOrder(BT->Rchild);

}（2）中序遍历递归算法

voidInOrder(BTreeBT){

if(BT){

InOrder(BT->Lchild);

Visit(BT);

InOrder(BT->Rchild);

}

}（3）后序遍历递归算法

voidPostOrder(BTreeBT){

if(BT){

PostOrder(BT->Lchild);

PostOrder(BT->Rchild);

Visit(BT);

}

}三、线索二叉树及二叉树的线索化1、指向该线性序列中的“前驱”和“后继”的指针，称作“线索”，与其相应的二叉树，称作“线索二叉树”。2、在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索Thread”若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索Thread”。如此定义的二叉树的存储结构称作“线索链表”3、二叉树的线索化在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题树和森林授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求了解树的存储结构掌握森林与二叉树的转换了解树和森林的遍历教学重点森林与二叉树的转换教学难点森林与二叉树的转换教学方法课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注一、 树的存储结构1、 双亲表示法2、孩子链表表示法3、树的二叉链表(孩子-兄弟）存储表示法二、 森林与二叉树的转换1、由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ;否则，由ROOT(T1)对应得到Node(root);由(t11,t12,…,t1m)对应得到LBT;由(T2,T3,…,Tn)对应得到RBT。2、二叉树转换为森林的规则：若B=Φ,则F=Φ;由Node(root)对应得到ROOT(T1);由LBT对应得到(t11,t12,…，t1m);由RBT对应得到(T2,T3,…,Tn)。三、 树和森林的遍历1、 熟的遍历2、 森林的遍历3、 树的遍历的应用四川城市职业学院课程教案教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题哈夫曼树及其应用授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握哈夫曼树算法及实现教学重点哈夫曼树算法及实现教学难点哈夫曼树算法及实现教学方法课程作业或思考题审阅意见

主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注1、哈夫曼树的定义及特点这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是：没有度为1的结点。

2、构造哈夫曼树的过程：（1）将给定的n个权值{w