数据结构与算法第二章教学教案
109页1、第第2章章基本数据结构基本数据结构2.1线性表线性表2.2数组数组2.3字符串字符串22.1线性表线性表ADT线性表线性表线性表(线性表(LinearList)u例例126个大写英文字母组成的字母表个大写英文字母组成的字母表(A,B,C,Z)u例例2某个学生宿舍学生姓名某个学生宿舍学生姓名(“wan”,“li”,“zhao”,“ye”,“hao”,“jia”)u例例3学生信息情况登记表学生信息情况登记表姓姓名名学学号号性性别别年年龄龄班班级级家庭住址家庭住址陈陈燕燕060001女女21计计06内蒙古内蒙古刘刘伟伟060002男男21计计06北京北京王树林王树林060003男男22计计06山东山东32.1线性表线性表ADT线性表线性表定义定义u由由n(n 0)个性质相同的数据元素个性质相同的数据元素a1,a2,an组组成的成的有限序列有限序列u数据元素的个数数据元素的个数n(n 0)定义为表的长度,当定义为表的长度,当n=0时称为空表时称为空表u常常将非空的线性表(常常将非空的线性表(n0)记作:)记作:L=(a1,a2,ai,an)注意:这里的数据元素注意:这里的数据元素ai(1 i
2、n)只是一个抽象只是一个抽象的符号,其具体含义在不同的情况下可以不同。的符号,其具体含义在不同的情况下可以不同。452.1线性表线性表ADT线性表线性表抽象数据类型线性表的定义抽象数据类型线性表的定义ADTListData数据元素表数据元素表size:数据元素的个数:数据元素的个数OperationConstructorProcess:创建空表:创建空表ClearProcess:清空线性表:清空线性表IsEmptyProcess:判断线性表是否为空:判断线性表是否为空Output:若线性表为空,返回:若线性表为空,返回true,否则返回,否则返回false62.1线性表线性表ADT线性表线性表LengthProcess:求线性表中元素个数:求线性表中元素个数Output:返回线性表中元素个数:返回线性表中元素个数GetElemInput:要取出的元素的位置:要取出的元素的位置Process:取出指定位置上的元素:取出指定位置上的元素Output:返回取出的元素值:返回取出的元素值LocateInput:要定位的元素:要定位的元素Process:为指定元素定位:为指定元素定位Output
3、:若线性表中有给定元素,返回元素位置,否则:若线性表中有给定元素,返回元素位置,否则返回返回-172.1线性表线性表ADT线性表线性表InsertInput:被插入元素值及其位置:被插入元素值及其位置Process:将给定元素插入指定位置:将给定元素插入指定位置DeleteInput:被删除元素的位置:被删除元素的位置Process:若线性表中有给定元素,则删除它:若线性表中有给定元素,则删除它PriorInput:要求前驱的元素:要求前驱的元素Process:求给定元素的直接前驱:求给定元素的直接前驱NextInput:要求后继的元素:要求后继的元素Process:求给定元素的直接后继:求给定元素的直接后继/List82.1线性表线性表ADT线性表线性表例例4假设利用线性表假设利用线性表LA和和LB分别表示两个集合分别表示两个集合A和和B(线性表中的数据元素即为集合中的成员),现(线性表中的数据元素即为集合中的成员),现求一个新的集合求一个新的集合AB,并用,并用LA表示结果集合。表示结果集合。voidIntersection(ListLA,ListLB)inti=1;while(i
4、=LA.size)x=LA.GetElem(i);/在在LA中取一元素中取一元素k=LB.Locate(x);/在在LB中搜索它中搜索它if(k=-1)/在在LB中未找到,则在中未找到,则在LA中删除它中删除它LA.Delete(i);LA.size-;elsei+;/Intersection92.1线性表线性表ADT线性表线性表例例5假设利用线性表假设利用线性表LA和和LB分别表示两个集合分别表示两个集合A和和B(线性表中的数据元素即为集合中的成员),现(线性表中的数据元素即为集合中的成员),现求一个新的集合求一个新的集合AB,并用,并用LA表示结果集合。表示结果集合。voidUnion(ListLA,ListLB)intn;for(inti=1;i=LB.size;i+)x=LB.GetElem(i);/在在LB中取一元素中取一元素k=LA.Locate(x);/在在LA中搜索它中搜索它if(k=-1)/在在LA中未找到,则在中未找到,则在LA中插入它中插入它n=LA.size;LA.Insert(n,i);LA.size+;/Intersection102.1线性表线性表线性表的
5、顺序存储线性表的顺序存储顺序表顺序表定义定义u顺序存储的线性表顺序存储的线性表u把线性表的元素按逻辑顺序依次存放在一组地址把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里连续的存储单元里存储要点存储要点用一段地址用一段地址连续连续的存储单元的存储单元依次依次存储线性表中的数据元素存储线性表中的数据元素a1a2ai-1aian112.1线性表线性表线性表的顺序存储线性表的顺序存储例:(例:(34,23,67,82)34236782存储空间的起始存储空间的起始地址地址基地址基地址用什么属性来描述顺序表?用什么属性来描述顺序表?顺序表的容量(最大长度)顺序表的容量(最大长度)顺序表的当前长度顺序表的当前长度4122.1线性表线性表线性表的顺序存储线性表的顺序存储存储结构与逻辑结构的关系存储结构与逻辑结构的关系 存储地址存储地址 内存状态内存状态线性表中线性表中的位序的位序LOC(a1)a11LOC(a1)+ma22LOC(a1)+(i-1) maiiLOC(a1)+(n-1) mann空闲空闲 顺序表存储结构示意图顺序表存储结构示意图LOC(ai)=LOC(a1)+(i-1)m基地
《数据结构与算法第二章教学教案》由会员youn****329分享,可在线阅读,更多相关《数据结构与算法第二章教学教案》请在金锄头文库上搜索。
第九章温毒类温病1讲义教材
10第十章成本费用174101教学材料
第八章重量分析和沉淀滴定法复习课程
风险与内部控制-普华永道-RISKT讲课教案
建筑施工组织设计7知识讲解
最全外汇投资经验教你入门1教学内容
危重病人液体治疗教学教材
团队精神--企业真正的核心竞争力1讲课教案
2012年城市规划管理与法规(北京2)701研究报告
烧伤患者的护理2讲义资料
完善组织架构及优化管理流程1知识课件
小学数学五年级下册《长方体的认识》1讲课教案
数据结构与算法第二章教学教案
学校事故及其法律责任6电子教案
MINITAB活用基础资料讲解
卫生行政执法风险控制2008培训教材
计划周密427说课材料
如何成为一名出色的部门经理9教学幻灯片
第3章汽车常识3说课讲解
十八大宣讲 核心价值2知识课件
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页