数据结构课件第2章 线性表(教案).doc_第1页
数据结构课件第2章 线性表(教案).doc_第2页
数据结构课件第2章 线性表(教案).doc_第3页
数据结构课件第2章 线性表(教案).doc_第4页
数据结构课件第2章 线性表(教案).doc_第5页
免费预览已结束,剩余36页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构(C+版)教师用书 教案教学专题线性表的逻辑结构授课学时0.5学时(25分钟)教学章节2.1授课对象计算机专业本科生教学课型理论课授课形式课堂讲授教学重点线性表的定义;线性表的逻辑特征。教学难点线性表的抽象数据类型定义教学内容和教学目标知识点学习要求了解理解掌握熟练掌握线性表的定义线性表的逻辑特征线性表的抽象数据类型定义线性表的基本操作教学过程教学过程设计1. 通过几个二维表的实例引出线性表的定义。2. 给出线性表的定义,注意强调要点,总结线性表的特性。3. 复习ADT的三个视图定义视图、设计视图、实现视图。4. 给出线性表的抽象数据类型定义。5. 提出问题:如何使用ADT的定义视图?为什么要定义基本操作?为什么要定义基本操作的接口?为线性表的实现做铺垫。时间分配3分钟7分钟3分钟5分钟7分钟教学提示本讲内容比较简单,学生容易掌握,但要透彻理解并不容易。把线性表的定义讲透,通过线性表定义的讲授方法,向学生渗透一种理解基本概念的方法问题分解、抓住要点、引申。通过线性表抽象数据类型进一步理解抽象数据类型的三个视图,理解其模块化思想,掌握其使用方法,并为后续内容做铺垫。媒体使用多媒体课件:使用超链接实现前后知识的串接;用动画辅助解释基本概念。教学网站:相关教学资源课后导读关于线性表的定义,在数据结构(严蔚敏编著.清华大学出版社)中是用二元组的形式化定义,此外,还有三元组定义、五元组定义,请参阅相关资料。教学后记教学感想、意外发现、点滴收获、个别疏漏及补救:40教 学 内 容 教学设计数据结构(C+版)教师用书 讲稿2.1 线性表的逻辑结构提示:通过两个二维表的实例引出线性表的定义。2.1.1 线性表的定义以下给出两个二维表的实例。学号姓 名离散数学英语高数抽象图2.2 学生成绩登记表及其数据模型0101丁一7896870102李二9087提出问题:各表项之间是什么关系?为什么内容不同的二维表其表项之间具有相同的逻辑关系?具有共同的数据模型线性表。780103张三8667860104孙红816996职工号姓 名基本工资岗位津贴奖金抽象图2.3 职工工资登记表及其数据模型0123李红梅2786002000256张长胜1903001001005王冬梅1863001001012孙佳亮218500200强调:ai为一个抽象符号,表示数据元素;下角标i表示该元素在线性表中的位置或序号。线性表(简称表):零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度。长度等于零时称为空表,通常记为:L( );非空表通常记为:L(a1,a2,an)。理解线性表的定义有以下要点:提出问题:什么是序列?在离散数学中是如何定义序列的? 序列顺序性:元素具有线性顺序,第一个元素无前驱,最后一个元素无后继,其他每个元素有且仅有一个前驱和一个后继。 有限有限性:元素个数有限,在计算机中处理的对象都是有限的。提出问题:线性表的数据类型确定吗?为什么? 相同类型相同性:元素取自于同一个数据对象,这意味着每个元素占用相同数量的存储单元。 元素类型不确定抽象性:数据元素的类型是抽象的、不具体的,需要根据具体问题确定。总结线性表的逻辑特征:元素之间具有前驱后继关系,如图2.4所示。a1a3a4ana2图2.4 线性表的逻辑结构图复习:ADT的定义形式和操作接口。2.1.2 线性表的抽象数据类型定义ADT ListData 线性表中的数据元素具有相同类型,相邻元素具有前驱和后继关系建议:不要将所有基本操作都讲一遍。将整个ADT的框架交代清楚后,解释12个操作。Operation Length 前置条件:线性表已存在 输入:无 功能:求线性表的长度 输出: 线性表中数据元素的个数 后置条件:线性表不变Get 前置条件:线性表已存在提出问题:1.如何使用ADT的定义视图?2.为什么要定义基本操作以及基本操作的接口?复习ADT的三个视图定义视图、设计视图、实现视图。 输入:元素的序号i 功能:在线性表中取序号为i的数据元素 输出:如果序号合法,返回序号为i的元素值,否则抛出异常 后置条件:线性表不变 Insert 前置条件:线性表已存在 输入:插入位置i;待插元素x 功能:在线性表的第i个位置处插入一个新元素x 输出:若插入不成功,抛出异常 后置条件:若插入成功,表中增加了一个新元素 Delete 前置条件:线性表已存在 输入:删除位置i 功能:删除线性表中的第i个元素 输出:若删除成功,返回被删元素,否则抛出异常 后置条件:若删除成功,表中减少了一个元素 (其他基本操作略,请参见主教材)endADT说明:提出问题:1.这些基本操作是确定不变的吗?2.操作的接口是确定不变的吗? 对于不同的应用,线性表的基本操作是不同的; 上述操作是最基本的,对于实际问题中涉及的关于表的更复杂的操作,可以用这些基本操作的组合来实现; 对于不同的应用,上述操作的接口可能不同。42数据结构(C+版)教师用书 教案教学专题线性表的顺序存储结构及实现授课学时1.5学时(75分钟)教学章节2.2授课对象计算机专业本科生教学课型理论课授课形式课堂讲授教学重点顺序表的存储特点;顺序表的插入、删除和查找算法及时间性能。教学难点用伪代码描述顺序表的插入和删除算法教学内容和教学目标知识点学习要求了解理解掌握熟练掌握顺序表的存储要点及存储特点顺序表的随机存取特性顺序表类的声明顺序表类的构造函数顺序表插入、删除、查找操作的实现顺序表插入、删除操作的时间性能顺序表的优缺点教学过程教学过程设计1. 给出顺序表的存储示意图,强调存储要点,总结存储特点。2. 复习存储地址的有关内容,给出顺序表的随机存取特性。3. 复习ADT的三个视图,给出顺序表类的声明。4. 简要复习C+语言的类以及模板类的有关知识。5. 复习构造函数,给出顺序表类构造函数的执行过程,再写出构造函数算法。6. 复习析构函数,写出顺序表类的析构函数。7. 给出插入操作的执行过程,写出伪代码,再写出C+描述。8. 分析插入算法的时间性能,总结算法分析的一般步骤。9. 对于顺序表的删除操作,要求学生仿照插入操作自行给出。10.对于顺序表的查找操作,给出执行过程,再写出算法。11. 总结顺序表的优缺点。时间分配10分钟8分钟2分钟5分钟15分钟3分钟15分钟5分钟3分钟5分钟4分钟教学提示在授课过程中复习C+语言的相关知识,复习遵循的原则是“实用至上”,从应用的角度复习,注意凝练,切忌“多而杂”。对于顺序表的算法(插入、删除),要讲过程讲思路讲方法,注意培养抽象思维能力和逻辑思维能力,这是本课程技能方面的教学目的。媒体使用多媒体课件:用动画模拟顺序表类的基本操作的执行过程教学网站:相关教学资源课后导读数据结构与算法(齐德岦编著.清华大学出版社)中顺序表的实现与本书不同,请参阅相关内容。教学后记教学感想、意外发现、点滴收获、个别疏漏及补救:43教 学 内 容 教学设计数据结构(C+版)教师用书 讲稿2.2 线性表的顺序存储结构及实现2.2.1 线性表的顺序存储结构顺序表强调存储要点:1.连续单元;2.依次存储。顺序表用一段地址连续的存储单元依次存储线性表的数据元素。线性表(a1,a2,an)的顺序存储示意图如图2.5所示。图2.5 用一段连续空间存储线性表a1 a2 ai-1 ai an提出问题:如何实现顺序表的内存分配?复习数组有关内容由于线性表中每个数据元素的类型相同,可以用C+语言中的一维数组来实现顺序表,也就是把线性表中相邻的元素存储在数组中相邻的位置,如图2.6所示。下标: 0 1 i-2 i-1 n-1总结存储特点:数据元素之间的逻辑关系由数据元素在数组中的存储位置表示。a1 a2 ai-1 ai an图2.6 用一维数组来实现线性表由图2.6可以看出,线性表第i个元素存储在数组下标为i-1的位置,即数据元素的序号和存放它的数组下标之间存在对应关系。用数组存储顺序表意味着要分配固定长度的数组空间,由于线性表中可以进行插入操作,因此分配的数组空间要大于当前线性表的长度。顺序表的存储示意图如图2.7所示。data下标: 0 1 i-2 i-1 n-1 MaxSize-1a1 a2 ai-1 ai an 空 闲 表的长度length图2.7 顺序表的存储示意图提出问题:用什么属性来描述这种存储结构?由图2.7可以看出,描述顺序表存储结构需要三个属性: 存储空间的起始位置:数组名data;提示:“数组的长度”和“线性表的长度”是一对容易混淆的概念,解释清楚。 顺序表的存储容量:数组长度MaxSize; 线性表的当前长度:length。数组的长度和线性表的长度是两个不同的概念,如图2.8所示。数组的长度是存放线性表的存储空间长度,存储分配后这个量是确定不变的。线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。在任意时刻,线性表的长度应该小于或等于数组的长度。引申:要善于用图示帮助理解问题。线性表的长度length数组的长度MaxSize下标: 0 1 i-2 i-1 n-1 MaxSize-1a1 a2 ai-1 ai an 空 闲 表的长度图2.8 数组的长度和线性表的长度的不同含义提出问题:如何读取任意数据元素?首先复习存储地址的有关内容。复习存储地址的有关内容:地址:存储器中的每个存储单元都有自己的编号,这个编号称为地址。相对地址(偏移地址):选定一个参考单元作为基准单元(称为基地址,一般将基地址视为0),任一存储单元到基地址之间的单元数,称为该存储单元相对于基地址的相对地址。绝对地址:任一存储单元的偏移地址,加上它的基准单元的绝对地址,即为该单元的绝对地址。进一步提出问题:在顺序表中,如何求得任意元素的相对地址?如何求绝对地址?在顺序表中,任意元素的相对地址就是该元素在数组中的下标,任意元素的绝对地址如图2.9所示。Loc(a1)Loc(ai)(i1)c下标: 0 1 i-2 i-1 n-1 MaxSize-1a1 a2 ai-1 ai an 空 闲 表的长度图2.9 顺序表中任意元素的绝对地址设顺序表的每个元素占用c个存储单元,则第i个元素的存储地址(即绝对地址)为:LOC(ai)= LOC(a1)(i1)c (式1)提出问题:式1说明了什么?式1表明在顺序表中,计算任意元素的存储地址的时间是相等的,具有这一特点的存储结构称为随机存取结构。提示:这里有一对容易混淆的概念存储结构和存取结构,解释清楚。存储结构和存取结构是两个不同的概念:存储结构是数据及其逻辑结构在计算机中的表示;存取结构是在某种数据结构上对查找操作时间性能的描述。“顺序表是一种随机存取的存储结构”的含义为:在顺序表这种存储结构上进行查找操作,其时间性能为O(1)。提出问题:顺序表类的声明是根据什么?2.2.2 顺序表的实现const int MaxSize=100; /100只是示例性的数据template /定义模板类SeqListclass SeqListpublic: SeqList( ) /无参构造函数 SeqList(T a , int n); /有参构造函数 SeqList( ) /析构函数为空强调:操作接口是在ADT的定义视图中定义的,在设计和实现时要遵循这个定义,这也是算法设计的出发点。 int Length( ) /求线性表的长度 T Get(int i); /按位查找,取线性表的第i个元素 int Locate(T x ); /按值查找,求线性表中值为x的元素序号 void Insert(int i, T x); /在线性表中第i个位置插入值为x的元素 T Delete(int i); /删除线性表的第i个元素 void PrintList( ); /遍历线性表,按序号依次输出各元素private: T dataMaxSize; /存放数据元素的数组 int length; /线性表的长度提示:根据学生情况复习模板的有关知识。更多内容参见主教材0.4节。;模板是C+语言提供的参数多态化的工具,用于增强类和函数的可重用性。使用模板可以为函数或类声明一个一般模式,使得函数的参数、返回值或类中的某些成员取得任意类型。 提示:以下给出构造函数的相关内容,需根据学生情况进行取舍。更多内容参见主教材0.4节。1构造函数构造函数的作用是初始化一个对象的成员变量,其特点是:构造函数必须与类名相同;必须声明为类的公有成员函数;不可以有返回值也不得指明返回类型;构造函数可以重载,使得在创建实例时,对象处于不同状态。提出问题:1.构造函数的作用是什么(What)?2. 什么时候调用(When)?3.谁调用(Who)?理解构造函数的要点是三个W:What:构造函数为成员变量分配存储空间。When:在声明一个对象变量是该类的一个实例时调用。Who:由系统根据实参自动调用相应的构造函数。可以重载构造函数, 顺序表类提供了两个构造函数: 无参构造函数操作接口SeqList( ):创建一个空的顺序表。无参构造函数只是简单地将顺序表的长度初始化为0,操作过程如图2.10所示。提示:顺序表类的构造函数的作用是为成员变量data和length分配存储空间并赋初值。 空 闲 0顺序表图2.10 无参构造函数的操作示意图SeqList:SeqList( ) length=0; 提示:简单复习函数重载的有关内容。 有参构造函数操作接口SeqList(T a , int n):创建一个长度为n的顺序表。有参构造函数需要将给定的数组元素作为线性表的数据元素传入顺序表中,并将传入的元素个数作为顺序表的长度。操作过程如图2.11所示。 10 12 15 25 8 16 20 10 12 15 25 8 16 20 空 闲 7数组a顺序表图2.11 有参构造函数的操作示意图用动画演示构造函数的执行过程。请参见课件。提示:首先理解构造函数的执行过程。算法较简单,可以不用伪代码过渡,直接给出C+描述。template SeqList: SeqList(T a , int n) if (nMaxSize) throw 参数非法; for (i=0; i=MaxSize;2.合理的插入位置?1, length+1;3.如果不能插入怎么办?抛出异常;4.最后一个元素的序号?length;5.如何实现元素的移动?通过下标。template void SeqList:Insert(int i, T x) if (length=MaxSize) throw 上溢;if (ilength+1) throw 位置; for (j=length; j=i; j-) /注意j指的是元素序号dataj=dataj-1; /注意第j个元素存储在数组下标为j-1处datai-1=x;length+; 插入算法时间性能分析:提出问题:基本语句是什么?基本语句的执行次数取决于什么?分析最好、最坏、平均情况。问题规模是表的长度length(设为n),基本语句是for循环中元素后移语句。最好情况:i=n+1(在表尾插入),不需要移动元素,时间复杂度为O(1);最坏情况:i=1(在表头插入),需要移动全部元素,后移语句执行n次,时间复杂度为O(n);提出问题:操作接口中的参数i指的是逻辑上的序号,为什么?基本操作定义于逻辑结构,实现于存储结构。平均情况:令Ein (n)表示元素移动次数的平均值,设pi表示插入第i(1in+1)个位置的概率,假设p1=p2=pn=1/(n+1),由于在第i个位置上插入元素后移语句的执行次数为n-i+1,故: Ein (n)= O (n) 也就是说,在顺序表上实现插入操作,等概率情况下,平均要移动表中一半的元素,算法的平均时间复杂度为O(n)。引申:归纳出算法分析的一般步骤。(非递归)算法分析的一般步骤是: 决定用哪个(或哪些)参数作为算法问题规模的度量 在大多数情况下,问题规模可以直接从问题的描述中得到。 找出算法中的基本语句 基本语句通常是最内层循环的循环体。总结:算法分析的关键是建立一个代表算法运行时间的求和表达式,然后用渐进符号表示这个求和表达式。 检查基本语句的执行次数是否只依赖于问题规模如果基本语句的执行次数还依赖于其他一些特性(如数据的初始分布),则需要分析最好情况、最坏情况和平均情况的效率。 建立基本语句执行次数的求和表达式 计算基本语句的执行次数,建立求和表达式。 用渐进符号表示这个求和表达式计算基本语句执行次数的数量级,并用大O记号表示。建议:删除操作要求学生仿照插入操作自行设计。4删除操作接口T Delete(int i):将线性表中的第i(1in)个元素删除,并返回被删除元素的值。提示:通过删除前后状态的对比入手,注意:删除后元素ai-1和ai+1之间的逻辑关系发生了变化,存储位置要反映这个变化。删除前:(a1,ai-1,ai,ai+1,an),删除后:(a1,ai-1,ai+1,an),顺序表删除前后状态的对比如图2.13所示。删除后a1 10a2 12a3 8a4 16a5 20 空 闲 6a6 45删除a1 10a2 12a3 25a4 8a5 16a6 20 空 闲 7数组下标: 0 1 2 3 4 5 6 MaxSize-1删除前a7 45图2.13 顺序表删除前后的状态对比 提出问题:为什么移动元素?向什么方向移动?从哪个元素开始移动?到哪个元素为止? 删除操作要点:元素移动的方向前移一个单元;从第i+1个元素开始移动,直至最后一个元素;在移动元素之前要取出被删元素。进一步提出问题:什么情况下不能插入?注意边界条件。分析边界情况:如果表空,则发生下溢异常;如果元素的删除位置不合理,则引发删除位置异常。1. 如果表空,则抛出下溢异常;2. 如果删除位置不合理,则抛出删除位置异常;3. 取出被删元素;4. 将第i+1个元素直至最后一个元素分别向前移动一个位置;5. 表长减1,返回被删元素值;注意:这里的位置i指的是逻辑上的序号。template T SeqList:Delete(int i) if (length=0) throw 下溢; if (ilength) throw 位置; x=datai-1; for (j=i+1; j=length; j+) for (j=i; jlength; j+)dataj-2=dataj-1; dataj-1=dataj; length-; return x;分析在伪代码中没有考虑的问题:1.表空的条件?length=0;2.合理的删除位置?1, length;3.如果不能删除怎么办?抛出异常;4.最后一个元素的序号?length;5.如何实现元素前移?用下标控制。引申:算法(程序)设计原则:清晰第一。建议:删除算法的时间复杂度的分析可以参照插入算法的时间复杂度分析,由学生自行完成。问题规模是表的长度length(设为n),基本语句是for循环中元素前移语句。最好情况:删除表尾元素(即i=n),无需移动元素,时间复杂度为O(1)。最坏情况:删除表头元素(即i=1),需移动除第一个元素以外的所有元素,时间复杂度为O(n)。平均情况:令Ede(n)表示元素移动次数的平均值,设pi表示删除第i(1in)个元素的概率,假设p1=p2=pn=1/n,由于删除第 i 个元素需要移动n-i个元素,故 Ede(n)=O(n)也就是说,在顺序表上实现删除操作,等概率情况下,平均要移动表中一半的元素,算法的平均时间复杂度为O(n)。5. 查找提示:注意顺序表中序号和下标的关系。 按位查找操作接口T Get(int i):查找第i个元素并返回其值。顺序表中第i个元素存储在数组中下标为i-1的位置,所以,容易实现按位查找。template T SeqList:Get(int i) if (ilength) throw 查找位置非法; else return datai-1;显然,按位查找算法的时间复杂度为O(1)。提出问题:为什么顺序表类提供两种查找操作?取决于具体应用。 按值查找操作接口int Locate(T x):查找值为x的元素并返回其序号。按值查找需要对顺序表中的元素依次进行比较,如果查找成功,返回元素的序号,如果查找不成功,返回查找失败的标志“0”。template int SeqList:Locate(T x) for (i=1; ilength; i+) if (datai-1=x) return i; /下标i-1处存储的元素序号为i return 0; /退出循环,说明查找失败提示:按值查找在第1章已经讲过,此处略讲。引申:使顺序表具有这样优缺点的根本原因:利用数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系。总结顺序表的优缺点。优点: 无需为表示表中元素之间的逻辑关系而增加额外的存储空间; 可以快速地存取表中任一位置的元素(即随机存取)。缺点: 插入和删除操作需移动大量元素; 当线性表的长度变化较大时,难以确定存储空间的容量; 造成存储空间的“碎片”。52数据结构(C+版)教师用书 教案教学专题线性表的链接存储结构及实现授课学时2学时(100分钟)教学章节2.32.4授课对象计算机专业本科生教学课型理论课授课形式课堂讲授教学重点单链表的存储特点;单链表查找、插入、删除算法及时间性能。教学难点单链表查找、插入、删除算法教学内容和教学目标知识点学习要求了解理解掌握熟练掌握单链表的存储要点及存储特点单链表类的声明单链表的顺序存取特性单链表的插入、删除操作单链表插入、删除操作的时间性能单链表类的构造函数和析构函数顺序表和单链表的比较教学过程教学过程设计1. 由顺序表的缺点引出链接存储结构。2. 根据一个实例给出线性表链接存储的实际内存状态,复习C+语言中指针的有关知识,抽象出单链表的存储示意图。3. 区分指针变量和结点变量,说明头指针、尾标志和头结点。4. 给出单链表类的声明,引申单链表类与顺序表类的关系。5. 给出单链表查找的算法,总结单链表算法的设计模式。6. 设计单链表的插入算法,分析时间性能。7. 比较带头结点和不带头结点的单链表上的插入操作。8. 给出单链表的删除算法,注意分析边界情况。9. 对单链表类的构造函数,给出头插法和尾插法的算法。10.对单链表类的析构函数,简单分析后要求学生自行设计。11.将顺序表和单链表进行比较,总结比较存储结构的方法。时间分配5分钟20分钟10分钟5分钟10分钟15分钟10分钟5分钟12分钟3分钟5分钟教学提示熟练使用指针是学好单链表的基本前提,首先需要复习指针的有关内容。在精讲单链表查找算法的基础上,总结单链表算法的设计模式。单链表算法设计的关键是多练,安排一节习题课是非常必要的,如果学时较紧,至少要留作业,然后课堂讲评。媒体使用多媒体课件:用动画模拟单链表各种操作的动态执行过程教学网站:相关教学资源课后导读数据结构与算法(齐德岦编著.清华大学出版社)中单链表的实现与本书不同,请参阅相关内容。教学后记教学感想、意外发现、点滴收获、个别疏漏及补救:53教 学 内 容 教学设计数据结构(C+版)教师用书 讲稿2.3 线性表的链接存储结构及实现提示:由顺序表的缺点引出链接存储结构。复习顺序表的缺点: 当线性表的长度变化较大时,难以确定存储空间的容量; 插入和删除操作需移动大量元素。提出问题:为什么顺序表需要预分配存储空间?缺点的原因:顺序表属于静态存储分配,需要预分配存储空间。缺点的解决:改变存储分配方式,采用动态存储分配。所谓静态存储分配是指在编译时为变量分配内存,并且一经分配就始终占有固定的存储单元,直到该变量退出其作用域。所谓动态存储分配是指在程序运行期间根据实际需要随时申请内存,并在不需要时释放。C+中的动态存储分配是通过指针实现的。进一步提出问题:为什么线性表的插入和删除操作需要移动元素?缺点的原因:在顺序表中,由于存储位置具有邻接关系,在插入和删除操作中要保证具有邻接关系的元素存储在数组中相邻位置。缺点的解决:放宽这个限制,不限定存储位置具有邻接关系。2.3.1 线性表的链接存储结构单链表强调存储要点:一组任意的存储单元可以连续也可以不连续,甚至可以零散分布在内存中的任意位置。单链表用一组任意的存储单元存放线性表的元素。在单链表中,元素的逻辑次序和物理次序不一定相同。为了能正确表示元素之间的逻辑关系,每个存储单元在存储数据元素的同时,还必须存储其后继元素所在的地址信息,这个地址信息称为指针。例如,线性表(a1, a2, a3)的链接存储示意图如图2.14所示。图2.14 线性表(a1, a2, a3)的链接存储示意图 a2 0325 a1 0200 a3 020002080300数据元素指针地址头指针总结存储特点:数据元素之间的逻辑关系是用指针来表示的。存储数据元素的数据域和存储后继元素所在地址的指针域组成了数据元素的存储映象,称为结点,如图2.15所示。引申:再次用到了抽象这个思维方式。本课程的一个教学目标就是培养学生的抽象思维能力。data next a1 0200数据元素指针地址抽象图2.15 单链表的结点存储示意图结点单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起,由于每个结点只有一个指针域,故称为单链表。提示:简单复习结构类型的有关内容。强调结构是一个整体。更多内容请参见0.4节。在C+语言中,可以用结构类型来描述单链表的结点。由于结点的元素类型不确定,所以采用C+的模板。template struct Node T data; Node *next; /此处也可以省略强调:单链表的基本思想就是用指针表示结点间的逻辑关系,首先要正确区分指针变量、指针、指针所指结点和结点的值这四个密切相关的不同概念。;Nodepp-datap-nextdatanext图2.16 指针变量和结点变量的含义*p如图2.16所示,设p是一个指针变量,则p的值是一个指针(即某个存储单元的地址)。有时为了叙述方便,将“指针变量”简称为“指针”。 语句p=new Node 实现向内存申请一个Node类型的结点,则指针p指向该结点,*p为结点变量,表示指针p所指结点。有时为了叙述方便,将“指针p所指结点”简称为“结点p”。在图2.16中,结点p由两个域组成:存放数据元素的数据域和存放后继结点地址的指针域,分别用p-data(或*p.data)和p-next(或*p.next)来标识,且他们各自有自己的值:p-data的值是一个数据元素,p-next的值是一个指针。提示:再次用到了抽象这个思维方式。用内存的实际存储状态表示一个单链表非常不方便,而且在使用单链表时,关心的只是它所表示的线性表中的数据元素以及数据元素之间的逻辑关系,而不是每个数据元素在存储器中的实际位置。单链表的存储示意图如图2.17所示。图2.17 非空单链表的存储示意图a1a2an firstL 提示:用锁链来形象地说明单链表的头指针和尾标志。头指针:在单链表中,每个结点的存储地址存放在其前驱结点的next域中,而第一个元素无前驱,所以设头指针指向第一个元素所在结点(称为开始结点)。整个单链表的存取必须从头指针开始进行,因而头指针具有标识一个单链表的作用。尾标志:终端结点的指针域为空。尾标志标识一个单链表的结束。进一步提出问题:空表和非空表在存储结构上统一吗?不统一的缺点?如何将空表与非空表统一?在空单链表中,头指针为空;在非空链表中,头指针指向开始结点,设计算法时需特殊处理单链表为空的特例而增加程序的复杂性和出现bug的机会(更详细的解释参见单链表插入算法)。头结点:在单链表的开始结点之前附设一个类型相同的结点,称为头结点,保证了空表和非空表的统一。带头结点的单链表的存储示意图如图2.18所示。(a) 空链表firstL(b) 非空链表图2.18 带头结点的单链表存储示意图a1a2an firstL启示?时空权衡:用空间(头结点)换取时间(算法简单)。2.3.2 单链表的实现提出问题:成员函数从何而来?成员变量表示什么?再次复习ADT的三个视图。强化如下观点:ADT为数据结构和算法的研究提供了一种分层模型。template class LinkListpublic:LinkList( ) /建立只有头结点的空链表 LinkList(T a , int n); /建立有n个元素的单链表LinkList( ); /析构函数int Length( ); /求单链表的长度T Get(int i); /取单链表中第i个结点的元素值int Locate(T x); /求单链表中值为x的元素序号void Insert(int i, T x); /在第i个位置插入值为x的结点T Delete(int i); /删除第i个结点void PrintList( ); /遍历单链表,按序号依次输出各元素private:Node *first; /单链表的头指针;提出问题:将单链表类的声明与顺序表类的声明比较,二者之间有什么关系?顺序表和单链表是线性表的不同存储方法,在逻辑上,二者应向外界提供一致的访问接口。更专业化的表示方法是:将线性表设计为一个抽象类,顺序表类和单链表类都是线性表抽象类的继承类。这涉及到抽象类、虚函数、函数多态等面向对象的概念,请有能力的同学课后将这个方法实现。1. 按位查找操作接口T Get(int i):查找第i个元素并返回其值。提出问题:单链表能随机存取吗?顺序表为什么能随机存取?在单链表中,因为元素序号和该元素的存储位置之间没有对应关系,因此,不能像顺序表那样直接按序号访问。单链表的查找只能从头指针出发,设置一个工作指针p,顺next域逐个结点往下搜索。当p指向某结点时判断是否为第i个结点,若是,则查找成功;否则,将工作指针p后移。对每个结点依次执行上述操作,直到p为NULL时查找失败。其查找过程如图2.19所示。提示:设计动画模拟查找过程。请参见课件。a1aian firstp=NULLpppj=1j=i图2.19 单链表的查找过程提示:注意抽象分级。1. 工作指针p初始化; 累加器j初始化;2. 执行下列操作,直到p为空或p指向第i个结点 2.1 工作指针p后移; 2.2 累加器j加1;3. 若p为空,则第i个元素不存在,抛出位置异常;否则查找成功,返回结点p的数据元素;分析在伪代码中没有考虑的问题:1.如何实现工作指针初始化?指向开始结点:p=first-next。2.如何实现累加器初始化? j=1。3.如何判断p指向第i个结点?累加器j与i相等。4.如何实现工作指针后移?p=p-next。 template T LinkList:Get(int i) p=first-next; j=1; /或p=first; j=0; 指向头结点 while (p & jnext; /工作指针p后移 j+; if (!p) throw 位置;

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论