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

四川城市职业学院教案课程名称数据结构与算法课程性质必修课开课学期2017-2018第1学期学时数64开课系（部）汽车与信息工程学院授课班级16级软件技术2班主讲教师W职称副教授二O一七年九月填写说明1、封面中课程性质是指公共必修课、专业必修课、公共选修课、专业选修课等。2、教案首页中的授课类型是指理论授课、实验课、习题课、课堂讨论、课程设计、实作等。3、教学步骤及主要内容包括教学设计、教学内容、过程、方法。4、备注包括时间安排、媒体应用、对教材的整合等；对教材的整合包括删减的内容、补充、更新的内容等。5、教师每次课都要写一份教案（一次课计2学时），新教师和年轻教师还应准备讲稿或课件。四川城市职业学院备课环节质量标准及评价方案一、备课环节质量标准(一)基本要求备课是教学过程的起始环节，是教师在课堂讲授之前进行的教学设计准备工作。备课环节主要包括把握大纲、钻研教材、准备教学进度表和讲稿、设计教案、开发课件、准备教具、试验预做、实践教学内容及实施设计、考核等工作。备课环节的基本要求是：(I)改革教学方法和手段，融”教、学、做”为一体。(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；然后打出评价基元的得分，得分=Z评价要素分值*等级系数（等级系数：A:0.9、B：0.75、C：0.6、D：0.1）o评价总分S等于每项得分之和，评价结果按优秀、良好、合格、不合格四级评定，优秀：87S<100;良好74S<87;合格：60<S<74;不合格：SV60。2 .有关说明备课环节质量评价一般由系组织实施，教务处监督检查；尚未获得主讲教师资格的青年教师必须通过系组织的备课质量评价，并和其他教学环节的评价结果一起作为晋升职称的重要依据；3 各系可以采用抽查、教案展评等方式，促进备课质量的提高；各系要对评价过程中发现存在问题的教师端正态度。对备课态度较认真、但备课质量不高的教师，应该及时配备指导教师，请有经验的教师加以指导，提高备课质量。教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题数据结构概述授课教师林琳职称副教授授课日期授课类型理论学时数8教学目的及要求掌握数据结构课程的基本任务；掌握数据结构相关的基本概念；掌握逻辑结构的分类和各种逻辑结构的基本特点；教学重点数据结构相关的基本概念；逻辑结构的分类；教学难点数据结构相关的基本概念；教学方法结合实际生活的案例讲授基本理论，课程作业或思考题审阅意见主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注基本内容：课程简介。5分钟第1节数据结构学科概念及其所研究的主要内容一、用计算机解决实际问题的一般步骤：IO分钟1、问题定义。分析问题是什么？明确问题要求是什么？理解问题做什么？2、建立模型。将实际问题中的客观对象的属性及联系，抽形成逻辑数据模型。3、定义数据。降落及数据模型数据化，定义成计算机能存储处理的存储结构。4、寻找算法。根据存储结构，找出求解问题的策略和方法步骤。5、编写程序。将算法用计算机语言表示出来。6、调试运行。将数据和程序输入计算机，查错修改，运行得到结果。7、分析结果。计算结果是否符合要求，若符合则结束，否则，返回监察修改。建立模型和寻找算法是较困难的两个步骤。二、数据结构学科概念描述。20分钟计算机应用的特点：处理的数据量大且数据之间存在一定的关系；对数据的操作不单纯是数值计算（仅占计算机数据处理的10%）,更多地是需要对其进行非数值计算（占计算机数据处理的90%）o如检索、排序、插入、删除等。数值计算问题在数值分析(计算方法)学科中专门研究。非数值计算问题是数据结构学科所要讨论的内容。1、数据结构建模举例例1图书管理问题。此例建立的是线性表。类似的学生管理、人事管理、物资管理、商品管理等大量问题都可以抽象出类似的线性数据结构。例2排课问题。此例建立了-种图状数据结构。另有像交通管理、工程管理等大量问题可以抽象出图状数据结构。课程编号课程名称计算机导论 数据结构 汇编语言 C程序设计语言 计算机图形学 接口技术 数据库原理 编译原理先修课程 无C1» C4C1C1C2，Cj > C4C3C?，CgC4(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)和数据的物理结构(PhyiCaIStructure)o存储结构与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。常见的存储结构有：顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。 索引存储方式：数据元素通过索引表相连系； 散列存储方式：数据元素通过散列函数相连系；存储地址存储内农指针13457,1141346元素4A1400元素215361536抗素R1346顺序存储存储地址 存储内容顺序存储结构常用于线性数据结构，将逻 辑上相邻的数据元素存储在物理上相邻的 存储单元里。head1345 I链式存储1536彳-Q13462o算法的概念20分钟算法：是对特定问题求解步骤的种描述，使得问题能在有限时间内被机械求解。算法的五个特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果。可行性：算法的每一步都是能够实现的，即可操作的。输入：一个算法具有零个或多个输入，这些输入取自特定的数据对象集合输出：算法执行完毕，必须有一个或若干个输出结果。评价算法：正确性、易读性、健壮性、效率和低存储量。3.算法性能分析与度量30分钟时间复杂度一个程序的时间复杂度(TimeComplexity)是指程序运行从开始到结束所需要的时间。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。许多时候要精确地计算T(n)是困难的，我们引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。定义(大0记号)：如果存在两个正常数C和n,使得对所有的n,nn,有：f(n)eg(n)则有：f(n)=O(g(n)例如，一个程序的实际执行时间为T(n)=2.7n3+3.8n2+5.3则T(n)=O(n3)o通常用O(1)表示常数计算时间。常见的渐进时间复杂度有：0(1)<O(Iog2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)空间复杂度是指程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括以下两部分：固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。4.练习10分钟教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题线性表及其顺序存储结构授课教师林琳职称副教授授课日期授课类型理论学时数2教学目的及要求掌握线性表的基本概念和特点；掌握线性表逻辑结构的表示和各操作的含义；掌握顺序表存储结构和各种操作在顺序表中的实现；进一步理解顺序存储结构的特点。教学重点线性表逻辑结构的表示和各操作的含义；顺序表存储结构和各种操作在顺序表中的实现；教学难点顺序表存储结构和各种操作在顺序表中的实现；教学方法结合实际生活的案例讲授基本理论，结合操作代码讲解各个操作的实现。课程作业或思考题审阅意见主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容(教学设计、教学内容、过程、方法等)备注基本内容：一、线性表的定义及特点15分钟1、线性表的定义。线性表是由n(n0)个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(al,a2,.,ai-l,ai,ai+l,.,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。例ILa=(34,89,765,12,90,-34,22)数据元素类型为int.Ls=(2Hello2,2World2,2China2,2Welcomc2)数据元素类型为string1.b=(book1,book2,.,booklOO)数据元素类型为下列所示的结构类型：structbookinfointNo;图书编号char*namc;图书名称char*auther;作者名称9)2、线性表的特点。有序性：除第一个元素外，每个元素有且仅有唯个直接前驱，第一个元素无直接前驱，除最后一个元素外，每个元素有且仅有唯一一个直接后继，最后一个元素无直接后继。这种次序描述了元素之间的1对1联系。抽象性：数据元素可以是任意类型。同质性：数据元素具有相同的类型。二、线性表的基本操作10分钟(1) 初始化线性表LInitList(L)(2)销毁线性表LDestoryList(L)(3)清空线性表LClearList(L)(4) 求线性表L的长度LiStLength(L)(5) 判断线性表L是否为空IsEmpty(L)(6) 获取线性表L中的某个数据元素内容GetElem(L,i,e)(7) 检索值为e的数据元素LOCateELenI(Le)(8) 返回线性表L中e的直接前驱元素PriorElem(L,e)(9) 返回线性表L中e的直接后继元素NextElem(L,e)(10)在线性表L中插入一个数据元素Listinsert(L,i,e)（三）删除线性表L中第i个数据元素ListDelete(L,i,e)三、线性表的顺序存储结构定义及其特点15分钟1、线性表的顺序存储结构(顺序表)线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图所示：其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式:LOC(ai+l)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：1.OC(ai+l)=LOC(al)+(i-l)*L(其中L是每个元素的长度)2、顺序存储结构的特点(1) 一致性。在顺序表中，利用数据元素的存储位置相邻，表示线性表中数据元素之间的相邻前后关系，逻辑结构与存储结构(物理结构)一致；(2)可随机访问性。在访问顺序表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。(3)经济性。节省空间和时间。(4)不方便性。对插入、删除等操作效率较低，需要移动大量元素。(5)不便于扩充性。要动态增加元素个数较困难。3、顺序存储结构的类型定义数组形式定义：#defineMaxsize100必预留数组的最大容量*/typedefstructdatatypeI)ataMaxsize;intlast;SeqList,*L;最多能存放MaXSiZe个元素Last二最后一个元素数组下标值，<=Maxsize-I.有n个元素时Last=n-1表长为Last+1表长为空时Last=-I线性表的存储空间通过malloc函数获取，格式为：malIoc(sizeof(SeqList)返回值为地址值Data数组元素的引用方式有：L.Datai或L->Datai最后一个数组元素的引用用Last表示时方式有：L.DataL.last或L->DataL->last四、线性表的典型操作算法的实现40分钟(1)初始化线性表LSeqList*initSeqList()(SeqList*L;1.=malloc(sizeof(SeqList);1.->Iast=-I;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<lIli>L->last+2)printf(“位置错");return(0);for(j=L->last;j>=i-1;j)1.->dataj+1=L->dataj;1.->datai-l=x;1.->last=L->last+l;)最坏情况时间复杂性为n,量级为0(n);时间的平均复杂性为：(0+1+2+.+n口n+1-删除第i个元素：delete_seqlist(Seqlist*L,inti)(i11tj;if(i<lIli>L->last+l)printf(,不存在第i个元素");return(0);for(j=i;j<=L->last;j+)1.->dataj-l=L->dataj;1.->last=L->last-l;return(1);最坏情况时间复杂性为n-l,量级为0(n);时间的平均复杂性为：(0+1+.+(n-1)nT分析插入和删除算法可得如下结论：顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。定位操作实现：intLocation_SeqList(SeqList*L,datatypex)(inti=0;while(i<=L.last&&L->dataiJ!=x)i+；if(i>L->last)return-1;elsereturni;*返回的是存储位置字/)最坏情况时间更杂性为n,量级为O(n);时间的平均复杂性为：(1+2+.+n)n+1线性表的应用举例：10分钟例2.1将顺序表(al,a2,.,an)重新排列为以ai为界的两部分：ai前面的值均比ai小,ai后面的值都比ai大voidpart(SeqList*L)Etij；datatypex,y;x=L->data0;/*将基准置入X中*/for(i=1;i<=L->last;i+)if(L->datai<x)/*当前元素小于基准*/y=L->datai;for(j=i-l;j>=0;j-)/*移动*/1.>dataj+l=L->dataj;1.->data0=y;)125。15,如20p2。UMp2肺IOp3。U35*6(P屏35»三划分国教案完成时间：2017年月日课程名称数据结构专业班级16级软件技术2-4班课题线性表及其链式存储结构授课教师林琳职称副教授授课日期授课类型理论学时2数教学目的及要求掌握掌握单链表的相关C语言定义；理解并掌握头结点在链表操作中的作用；掌握链表基本操作的实现；理解链式存储的优点和应用；教学重点链表的C语言定义；链表各个操作的实现。教学难点链表的C语言定义；链表各个操作的实现。教学方法结合实际生活的案例讲授基本理论，结合算法代码讲解各个基本操作的实现。课程作业或思考题审阅意见主讲教师或教学组长签名：林琳系主任签名：教学后记教学步骤及主要内容（教学设计、教学内容、过程、方法等）备注基本内容：一、线性表的链式存储结构30分钟线性表顺序存储结构的缺点是在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。1、线性表的链式存储结构：指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d）,可用下图所示的形式存储：术语其中标JEIImEm的两部分信朝台在rg被称为结点即容解除娜次据域(对3)一表示S接后院素存储地址的部分媾为才时或指针域(ned).单表笥化陋形描述形式，h出d<1a-tI一AbTHCTT一Ud|其中，gd是头指$十，百的单薛表中的第f三,这是单熊趣作的入口品由于最后TS点没有削帽继S点，所以它的擀十域放入3l三的值NULL.NULL值在图示中锦()符号表示,带头结点的单缝表,为了简儡茂诔缄作，人们经常在蓬表的第TS的JIW点瓶为头结点.这样被跆前诔第FS点的特殊处理.如下图所示：，head*-1/>a<bBrcd2、链式存储结构的特点(1)不一致性。线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；(2)只能顺序访问性。在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点,这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。(3)插入、删除操作方便性。不需移动元素，数据个数可动态增长。(4)不连续占用存储空间。但浪费空间较多。链式存储结构适合于数据各是动态变化、插入、删除频繁的场合。线性表的链式存储结构描述：线性表的单链表存储结构可用C语言中的“结构指针”来描述typedefstructNodedatatypedata；structNode*next;LNode,*Linklist,*H：通常指针P是一个动态变量，在需要时由库函数InaIloC(SiZe)产生，如:>P=DlalloC(SiZeOf(LnOde)该函数分配个LnOde数据类型所占的空间长度存放数据元素并返回一个该空间的起始地址给指针P。当该结点不再需要时，可由free(p)释放空间。>p->data表示一个数据元素；>p->next表示下一个元素的起始存放地址的指针。二、链表的典型操作的算法实现50分钟创立单链表(在表头添加)linklistcreat_linklistOlinklistL=null;1.Node*s;intx;scanf("%d”,&x)；while(x!=-1)或另外指定一flag值s=malloc(sizeof(LNode)；s->data=x;s->next=L;1.=s；scanf(%dw,&x)；)returnL;建立单链表(在表尾添加)linklistcreat_linklist()linklistL=null;1.node*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;求单链表的表长(带头结点)intIengthlinklist(linklistL)LNode*p=L;p指向首节点Lj=0;While(P->next!=NULL)当P指向an时，p->next为空，结束p=p->next;第一次循环P为首节点的指针域里的值，即指向节点alj+；表长计算从首节点al开始到an.return(j);按序号查找(找表中第i个结点,返回该节点序号或指针)查找方法:从头指针开始,修改指针p=p->next,使顺链表顺序往下搜索,直到找到为止.查找次数为i次.1.NodeGet_linklist(linklistL,inti)LNode*p=L;j=0;whiIe(p->next!=NULL)&&(j<i)/SP指向an时，p->next为空或P已指向节点i时结束p=p->next;/*第一次循环P指向首节点al*/j+；/*表长计算从首节点al开始到an.*/if(i=j)return(p);elsereturn(Null);)按值查找(找与给定值x相等的第一个结点,返回该节点指针)LNode*Iocatelinklist(linklistL,datatypex)LNode*p=L->next;while(p!=Null)(p->data!=x)p=p->next;if(p->data=x)return(p);elsereturn(0);单链表的插入运算(后插)算法思路：L找到第iT个结点；若存在继续2,否则结束2 .申请、填装新结点；3 .将新结点插入。结束。voidinsert_linklist(linklistL,inti,datatypex)P=L;j=0;whiIe(pfe(j<i-l)p=p->next;+j;if(!pIIj>i-l)returnERROR;s=(Iinklist)malIoc(sizeof(structNode);s->data=x;s->next=p->next;p->next=s;returnOK;在结点P前插入结点S:需要找到*P的前驱结点*q,然后再完成在*q后插入*s结点的操作.q=L;whiIe(q->next!=p)q=q->next;(2)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<il)p=p->next;+j;if(!(p->next)j>i-l)returnERROR;s=p->next;p->next=s->next;free(s);returnOK;应用举例10分钟已知单链表H,写一算法将其倒置。即实现如图的操作。(a)为倒置前，(b)为倒置后。(a)(b)单链表的倒置算法思路：依次取原链表中的每个结点，将其作为第一个结点插到新链表中去，指针P用来指向当前结点，P为空时结束。算法如下：voidreverse(LinklistH)LNode*p,*q;p=H->next;*p指向第一个数据结点*/H->next=NULL;/*将原链表置为空表H*/whi