《数据结构与算法(Python语言描述)课件1剖析》由会员分享，可在线阅读，更多相关《数据结构与算法(Python语言描述)课件1剖析（37页珍藏版）》请在金锄头文库上搜索。
1、第 三 章 线 性 表 2016 Fall数据结构 内容提要 线性结构 线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现 线性结构 学生信息表 通讯录 短信、聊天记录 邮件列表 购物清单 账单 何处用到线性结构？ 首元素 相邻的元素 组成前驱与后继关系 线性表 线性表的逻辑结构 尾元素 线性表 线性表是n个数据元素的有限序列。 一般形式：(a1,ai-1,ai,ai+1,an) 直接前驱、直接后继 长度：表中元素的个数n (n=0时称为空表) 非空表中，每个元素都有一个确定的位置 结构 + 操作 结构的创建、结构的销毁：构造与析构 引用型（访问型）：get 加工型（改变型）：s
2、et 线性表抽象数据类型？ ADT List 数据对象：D ai | ai ElemSet, i = 1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i = 2,.,n 基本操作： InitList( Lb_len = ListLength(Lb); for(i = 1; i = L.listsize) newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem = newbase; L.lists
3、ize += LISTINCREMENT; 【实验时可先假定空间总是够用，先不考虑空间追加，先做好基本的元素移动、和插 入，回头再考虑空间的追加与元素的拷贝！】 【问题：实验一下realloc也做了元素的拷贝工作么？】 【数组方式的元素移动、插入】 /从插入位置开始向后的元素，自后向前依次后移 for(j = L.length; j=i; j-) L.elemj = L.elemj-1; /插入e，修改表长 L.elemi-1 = e; +L.length; return OK; 【指针方式的元素移动、插入，有些难以阅读。】 /从插入位置开始向后的元素，自后向前依次后移 q = for (p
4、= p = q; -p) *(p+1) = *p; /插入e，修改表长 *q = e; +L.length; return OK; 删除操作： Status DeleteList( ) 删除前的线性表：(a1,ai-1,ai,ai+1,an) 删除后的线性表：(a1,ai-1,ai+1,an) 时间复杂度：最坏和平均的情况O(n) 逻辑关系发生了变化 Status DeleteList(List /取出元素带回 p = e = *p; /自前向后前移元素 q = L.elem + L.length - 1; for(+p; p = q; +p) *(p-1) = *p; /修改表长 -L.le
5、ngth; return OK; / 两个表的有序归并 / 此处作为List类型的基本操作直接定义！ void MergeList(List La, List Lb, List Lc.elem = (Elemtype *)malloc(Lc.listsize * sizeof(Elemtype); if (!Lc.elem) exit(OVERFLOW); / 起步准备 pc = Lc.elem pa = La.elem; pb = Lb.elem; pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length 1; /有序归并 while (pa = pa_last else *pc+ = *pb+; / 可能有一个表还有剩余 while (pa = pa_last) *pc+ = *pa+; while (pb = pb_last) *pc+ = *pb+; / 修改表长 Lc.length = La.length + Lb.length; 时间复杂度：O(La.Length + Lb.Length) 空间复杂度：和空间申请、空间追加策略有关， 至少需要 2(La.Length + Lb.Length)空间
