欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    数据结构zmz2顺序表.ppt

    • 资源ID:6578862       资源大小:790KB        全文页数:25页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    数据结构zmz2顺序表.ppt

    数据结构,主讲:郑梦泽,信息工程学院,大家好,第二章2.2 顺序表,一、线性表的定义,一、线性表的定义,书目文件,各条书目信息之间存在一个对一个的线性关系数据对象、数据元素(记录)、数据项(属性)数据操作:查找,插入,删除,修改等,在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外,集合中的每个数据元素均只有一个前驱除最后一个外,集合中的每个数据元素均只有一个后继,一、线性表的定义(特点),定义:一个线性表是n个数据元素的有限序列,例 打字游戏(B,H,Y,U.T),特征:有限、序列、同构元素个数n表长度,n=0空表1in时ai-1是ai的直接前驱,a1无直接前驱ai+1是ai的直接后继,an无直接后继,运算:存取 插入 删除 查找 合并 分解 排序 求长度,数据元素,一、线性表的定义(逻辑结构),ADT List 数据对象:D=ai|aiElemSet,i=1,2,n,n0,n表长,n=0,空表 数据关系:R=|ai-1,aiD,i=2,n,i为线性表中位置 基本操作:结构初始化操作 结构销毁操作 引用型操作(只读操作)加工型操作(修改操作)ADT List,二、线性表的抽象数据类型定义,初始化操作:InitList(&L)操作结果:构造一个空线性表L结构销毁操作:DestroyList(&L)初始条件:线性表L已存在 操作结果:销毁线性表L,二、线性表的抽象数据类型定义,引用型操作:ListEmpty(L)/线性表判空 初始条件:线性表L已存在 操作结果:若L为空表,返回TRUE;否则返回FALSE ListLength(L)/求线性表的表长 初始条件:线性表L已存在 操作结果:返回L中数据元素个数 GetElem(L,i,&e)/求线性表的第i个元素 初始条件:线性表L已存在,且1i ListLength(L)操作结果:用e返回L中第i个数据元素的值 LocateElem(L,e)/定位函数 初始条件:线性表L已存在 操作结果:返回L中第1个与e相同的元素的位序i,二、线性表的抽象数据类型定义,引用型操作:PriorElem(L,e,&pre_e)/求数据元素的前驱 初始条件:线性表L已存在 操作结果:若e是L中元素,且不是第一个,则用pre_e返回其前驱 NextElem(L,e,&next_e)/求数据元素的后继 初始条件:线性表L已存在 操作结果:若e是L中元素,且不是最后一个,则用next_e返回其后继 ListTraverse(L,visit()/线性表遍历 初始条件:线性表L已存在,visit()为某个访问函数 操作结果:依次对L中每个元素调用函数visit()。,二、线性表的抽象数据类型定义,加工型操作:ClearList(&L)/线性表置空 初始条件:线性表L已存在 操作结果:将L重置为空表 ListInsert(&L,i,e)/插入数据元素 初始条件:线性表L已存在,且1i ListLength(L)+1 操作结果:在L中第第i个位置之前插入元素e,L的长度加1 ListDelete(&L,i,&e)/删除数据元素 初始条件:线性表L已存在且非空,1i ListLength(L)操作结果:删除L的第i个元素,并用e返回其值,L的长度减1,二、线性表的抽象数据类型定义,三、线性表的顺序存储结构,LOC(a2)=LOC(a1)+L其中:L一个元素占用的存储单元个数LOC(ai)线性表第i个元素的地址LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L,顺序表定义:用一组地址连续的存储单元存放一个线性表叫元素地址计算方法:,三、线性表的顺序存储结构,特点:实现逻辑上相邻 物理地址相邻实现随机存取用什么数据类型来实现?一维数组!,顺序表,#define M 100int aM;int n;/*元素个数n=M*/,例 typedef struct int num;char name20;char author10;char publisher30;float price;BookCard;BookCard aM;,三、线性表的顺序存储结构,数据元素不是简单类型时,可定义结构体数组,缺点:elem 与n 是孤立的,没有反映出elem与n 的内在联系,没有指出n是顺序表List的属性,方案一,内存,数组下标,1,2,n,元素序号,#define ListSize 100typedef struct int length;int elemListSize;SqList;,SqList s;SqList*p=,length,elem,表长,三、线性表的顺序存储结构,方案二,缺点:表容量难以扩充,L.elem=(int*)malloc(M*sizeof(int);,free(L.elem);,L.elem=(int*)realloc(L.elem,(L.listsize+20)*sizeof(int);,SqList L;,int elemM;=int*elem;动态申请和释放内存int*elem=(ElemType*)malloc(M*sizeof(int);elem=(int*)realloc(elem,M*2*sizeof(int);free(elem);,L.listsize=100;,三、线性表的顺序存储结构,方案三,/*定义动态顺序表*/#define M 100/线性表初始大小typedef struct int*elem;/存储空间基址 int length;/当前表长 int listsize;/当前分配的存储容量SqList;,void InitList_Sq(SqList/*假设数据元素为整型变量*/,四、顺序表的C语言实现,Status ListEmpty_Sq(SqList L)if(L.length=0)return True;elsereturn False;,初始化(静态表),判空,void DestroyList_Sq(SqList,Status GetElem_Sq(SqList L,int i,int,int ListLength_Sq(SqList L)return L.length;,求表长,销毁表,取数据元素值,四、顺序表的C语言实现,int LocateElem_Sq(SqList L,int e),顺序表查找:(返回元素的序列号),算法时间复杂度:,O(n),找64,查找成功,L.elem,L.length,L.listsize,while(i=L.length,if(i=L.length)return i;return 0;,int i=1;/*elem0不用,使i和数组下标统一*/,四、顺序表的C语言实现,顺序表在i的位置插入元素xelem0不用,四、顺序表的C语言实现,an,ai+1,ai,x,1.从表尾开始后移,2.插入元素L.elemi=x,3.什么时候不能插入,4.长度+1 L.length+,Status ListInsert_Sq(SqList,顺序表插入算法:,四、顺序表的C语言实现,判断i值合法性,判断是否溢出,元素后移,插入,算法时间复杂度:,O(n),顺序表删除第i位置上的元素elem0不用,四、顺序表的C语言实现,1.从第i+1个位置开始前移,2.什么时候不能删除,3.长度-1 L.length-,ai+1,ai+2,an,Status ListDelete_Sq(SqList,顺序表删除算法:,四、顺序表的C语言实现,算法时间复杂度:,O(n),例:LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)则:LC=(2,3,5,6,8,8,9,11,11,15,20),11,2,3,5,6,8,8,9,11,11,15,20,MergeList_Sq(SqList La,SqList Lb,SqList&Lc),讨论:两个有序顺序表的合并,讨论:两个有序顺序表的合并,void MergeList_Sq(SqList La,SqList Lb,SqList,顺序表特点总结分析,优点编程简单查找元素方便缺点插入、删除效率低数组长度受限空间浪费很大解决方法“链式存储”链表,

    注意事项

    本文(数据结构zmz2顺序表.ppt)为本站会员(牧羊曲112)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开