内蒙古大学《算法与数据结构》课件第2章基本数据结构
119页1、1 第第2章章 基本数据结构基本数据结构2.1 线性表线性表 2.1.1 ADT线性表线性表 2.1.2 静态线性表静态线性表 2.1.3 动态线性表动态线性表2.2 数组数组 2.2.1 数组的定义数组的定义 2.2.2 数组的存储数组的存储 2.2.3 特殊矩阵特殊矩阵 2.2.4 稀疏矩阵稀疏矩阵2.3 字符串字符串 2.3.1 串的表示与实现串的表示与实现 2.3.2 串的模式匹配算法串的模式匹配算法2 线性表线性表(Linear List) :v由由n(n 0)个数据元素个数据元素a1,a2,an组成的组成的有限序列。有限序列。v数据元素的个数数据元素的个数n定义为表的长度。当定义为表的长度。当n=0时称为空表时称为空表v常常将非空的线性表常常将非空的线性表(n0)记作:记作: L(a1,a2,ai,an)注意:注意:这里的数据元素这里的数据元素ai(1 i n)只是一个抽象的符号,只是一个抽象的符号, 其具体含义在不同的情况下可以不同。其具体含义在不同的情况下可以不同。 2.1 线性表线性表3l例例1 1、2626个大写英文字母组成的字母表个大写英文字母组成的字母表( (
2、A A , , B B , C C , , , Z Z )l例例2、某个学生宿舍学生姓名、某个学生宿舍学生姓名 ( wan , li , zhao , ye , hao , jia )2.1.1 ADT线性表线性表4 例例3 3、学生信息情况登记表如下:学生信息情况登记表如下:2.1.1 ADT线性表线性表姓姓 名名学学 号号性性 别别年龄年龄民族民族系系专业专业入学时间入学时间.5非空线性表的逻辑特征:非空线性表的逻辑特征:v1)有且仅有一个开始结点有且仅有一个开始结点a1,它没有它没有(直接直接)前趋,而仅有一前趋,而仅有一个个(直接直接)后继后继a2;v2)有且仅有一个终端结点有且仅有一个终端结点an,它没有它没有(直接直接)后继,而仅有一后继,而仅有一个个(直接直接)前趋前趋an-1;v3)其余的内部结点其余的内部结点ai(2 i n-1)都有且仅有一个都有且仅有一个(直接直接)前趋前趋ai-1和一个和一个(直接直接)后继后继ai+1。线性表的逻辑结构是一种典型的线性结构。线性表的逻辑结构是一种典型的线性结构。2.1.1 ADT线性表线性表6抽象数据类型线性表的定义如下:抽象数
3、据类型线性表的定义如下:ADT List Data 数据元素表数据元素表.即由即由n(n 0)个数据元素的一个有限个数据元素的一个有限 序列,其中每个数据元素的数据类型为序列,其中每个数据元素的数据类型为DataType size: 数据元素的个数数据元素的个数 Operation Constructor Process: 创建空表创建空表 Clear Process: 清空线性表清空线性表IsEmpty Process: 判断线性表是否为空判断线性表是否为空Output: 若线性表为空,返回若线性表为空,返回true,否则返回否则返回false 7Length Process: 求线性表中元素个数求线性表中元素个数 Output: 返回线性表中元素个数返回线性表中元素个数GetElem Input: 要取出的元素的位置要取出的元素的位置 Process: 取出指定位置上的元素取出指定位置上的元素 Output: 返回取出的元素值返回取出的元素值Locate Input: 要定位的元素要定位的元素 Process: 为指定元素定位为指定元素定位 Output: 若线性表中有给定元素,返
4、回元素位置,否则若线性表中有给定元素,返回元素位置,否则 返回返回-1抽象数据类型线性表的定义如下:抽象数据类型线性表的定义如下:8Insert Input: 被插入元素值及其位置被插入元素值及其位置 Process: 将给定元素插入指定位置将给定元素插入指定位置Delete Input: 被删除元素的位置被删除元素的位置 Process: 若线性表中有给定元素,则删除它若线性表中有给定元素,则删除它Prior Input: 要求前驱的元素要求前驱的元素 Process: 求给定元素的直接前驱求给定元素的直接前驱Next Input: 要求后继的元素要求后继的元素 Process: 求给定元素的直接后继求给定元素的直接后继 / List 抽象数据类型线性表的定义如下:抽象数据类型线性表的定义如下:9例例2.1 假设利用线性表假设利用线性表LA和和LB分别表示两个集合分别表示两个集合A和和B(线性(线性表中的数据元素即为集合中的成员),现求一个新的集合表中的数据元素即为集合中的成员),现求一个新的集合AB,并用,并用LA表示结果集合。表示结果集合。void Intersection (
5、List LA,List LB ) int i=0; while ( i LA.size ) x = LA.GetElem(i); /在在LA中取一元素中取一元素 k = LB.Locate (x); /在在LB中搜索它中搜索它 if ( k = -1 ) /在在LA中未找到,则删除它中未找到,则删除它 LA.Delete (i); LA.size -; else i+; / Intersection时间复杂度为时间复杂度为O (LA.size) 。 2.1.1 ADT线性表线性表练习:写一个求练习:写一个求AB的算法。的算法。101、顺序表、顺序表把线性表的元素按逻辑顺序依次存放在一组地址连续的存把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称储单元里。用这种方法存储的线性表简称顺序表顺序表。 a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的称作线性表的基地址基地址(a1,a2,ai,an)2.1.2 线性表的顺序存储线性表的顺序存储11一个数据元素所一个数据元素所占存储量占存储量以以“存储位置相邻存储位置相邻”表示有
《内蒙古大学《算法与数据结构》课件第2章基本数据结构》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》课件第2章基本数据结构》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页