《数据结构与算法(Python语言描述)课件1》由会员分享，可在线阅读，更多相关《数据结构与算法(Python语言描述)课件1（37页珍藏版）》请在金锄头文库上搜索。
1、第 三 章 线 性 表,2016 Fall数据结构,内容提要,线性结构 线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现,线性结构,学生信息表 通讯录 短信、聊天记录 邮件列表 购物清单 账单,何处用到线性结构？,相邻的元素 组成前驱与后继关系,线性表,线性表的逻辑结构,线性表,线性表是n个数据元素的有限序列。 一般形式：(a1,ai-1,ai,ai+1,an) 直接前驱、直接后继 长度：表中元素的个数n (n=0时称为空表) 非空表中，每个元素都有一个确定的位置,结构 + 操作 结构的创建、结构的销毁：构造与析构 引用型（访问型）：get 加工型（改变型）：set,线性表抽象
2、数据类型？,ADT List 数据对象：D ai | ai ElemSet, i = 1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i = 2,.,n 基本操作： InitList( / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量 List;,顺序存储结构的表示,2020/8/9,数学科学学院,21,Status InitList(List ,顺序存储时基本操作的实现,【结构的销毁没有空间了！】 void DestroyList(List ,/ 引用型 void TraverseList(List L, void
3、(*visit)(ElemType) for (i = 0; i L.length; i+) (*visit)(L.elemi); / 加工型map操作！ void TraverseList(List / 注意引用参数的使用！,Status GetElem(List L, int i, ElemType ,int LocateElem(List L, ElemType e, Status (*compare)(ElemType, ElemType) /起步 i = 1; p = L.elem; /在有效范围内查询 while(i = L.length ,int LocateElem(List
4、L, ElemType e, Status (*compare)(ElemType, ElemType) /起步 i = 1; /在有效范围内查询 while(i=L.length ,插入操作：Status InsertList( ) 插入前的线性表：(a1,ai-1,ai,ai+1,an) 插入后的线性表：(a1,ai-1,b,ai,ai+1,an) 时间复杂度：最坏和平均的情况O(n) 逻辑关系发生了变化,Status InsertList(List 【实验时可先假定空间总是够用，先不考虑空间追加，先做好基本的元素移动、和插入，回头再考虑空间的追加与元素的拷贝！】 【问题：实验一下real
5、loc也做了元素的拷贝工作么？】,【数组方式的元素移动、插入】 /从插入位置开始向后的元素，自后向前依次后移 for(j = L.length; j=i; j-) L.elemj = L.elemj-1; /插入e，修改表长 L.elemi-1 = e; +L.length; return OK; ,【指针方式的元素移动、插入，有些难以阅读。】 /从插入位置开始向后的元素，自后向前依次后移 q = ,删除操作： Status DeleteList( ) 删除前的线性表：(a1,ai-1,ai,ai+1,an) 删除后的线性表：(a1,ai-1,ai+1,an) 时间复杂度：最坏和平均的情况O(n) 逻辑关系发生了变化,Status DeleteList(List ,/ 两个表的有序归并 / 此处作为List类型的基本操作直接定义！ void MergeList(List La, List Lb, List ,/有序归并 while (pa = pa_last 时间复杂度：O(La.Length + Lb.Length) 空间复杂度：和空间申请、空间追加策略有关， 至少需要 2(La.Length + Lb.Length)空间,
