《线性表的定义 顺序表示和实现》由会员分享，可在线阅读，更多相关《线性表的定义 顺序表示和实现（34页珍藏版）》请在金锄头文库上搜索。
1、第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序目 录1数据结构课程的起点：什么是 线性结构？2线性结构的基本特征:1集合中必存在唯一的一个“第一元素”；2集合中必存在唯一的一个 “最后元素”3除最后元素在外，均有 唯一的后继；4除第一元素之外，均有 唯一的前驱。线性结构 是一个数据元素的有序（次序）集特点：一对一3第2章 线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序表示和线性表的顺序表示和实现实现2.3 2.3 线性表的链式表示和线性表的链式表示和实现实现2.4 2.4 应用举例应
2、用举例4（a1, a2, ai-1，ai, ai1 ，, an）2.1 线性表的逻辑结构 线性表的定义：线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的 序号，表示元素 在表中的位置n为元素总 个数，即表 长。n0n0空表线性终点5（ A, B, C, D, , Z）学号姓名性别别年龄龄班级级012003010622陈陈建武男 192003级电级电 信0301班012003010704赵赵玉凤凤女 182003级电级电 信0302班 012003010813王 泽泽男 192003级电级电 信0303班012003010906薛 荃男
3、 192003级电级电 信0304班012003011018王 春男 192003级电级电 信0305班 ： ：例2 分析学生情况登记表是什么结构。分析:数据元素都是同类型（字母）， 元素间关系 是线性的。例1 分析26 个英文字母组成的英文表是什么结构。6“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。是指各元素具有相同的数据类型是指各元素具有相同的数据类型试判断下列叙述的正误：注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性 ！分析：数据元素都是同类型（记录），元素间关系 是线性的。7抽象数据类型线性表的定义如下：
4、 ADT List 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 |ai-1 ,aiD, i=2,.,n 基本操作：结构初始化操作结构销毁操作引用型操作加工型操作 ADT List8InitList( 2依值在线性表LA中进行查访; GetElem(LB, i)eLocateElem(LA, e, equal( ) 3若不存在，则插入之。ListInsert(LA, n+1, e)11GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给eif (!LocateElem(La, e, equal( ) ) ListInsert(L
5、a, +La_len, e);/ La中不存在和 e 相同的数据元素，则插入之void union(List / 求线性表的长度Lb_len = ListLength(Lb); for (i = 1; i =i; j- -)aj+1=a j ; a i =x; n+;/后移一个位置 /插入 /表长加1注意2：表是否已满？如表长超过表尺寸则要增加尺寸。注意1：事先应判断: 插入位置i 是否合法? 应当符合条件： 1in+1 或 i=1, n+1使用realloc（*p，newsize）：新开一 片大小为newsize的连续空间，并把以*p为首址的 原空间数据都拷贝进去，并把该区首址作为函数值 。
6、动态数组的核心是realloc（void*p，newsize）函数 算法见教材 P2426Status ListInsert_Sq(SqList / q 指示插入位置 for (p = p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK;27if (L.length = L.listsize) / 当前存储空间已满，增加分配newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)
7、;if (!newbase) exit(OVERFLOW); / 存储分配失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量 if (i L.length+1) return ERROR; / 插入位置不合法28删除线性表的第i个位置上的元素3)删除删除顺序表中某个指定的元素的示意图如下： 12345678912 13 21 24 26 28 30 42 771234567812 13 21 24 2830 42 7729算法见教材 P24实现步骤： 将第i+1 至第n 位的元素向前移动一个 位置； 表长减1。注意：事先
8、需要判断，删除位置i 是否 合法? 应当符合条件：1in 或 i=1, n核心语句：for ( j=i+1; j L.length) return ERROR; / 删除位置不合法返 回312.2.3 顺序表的运算效率分析算法时间主要耗费在移动元素的操作上 ，因此 计算时间复杂度的基本操作（最深层语 句频度）T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元 素的位置.思考：若插入在尾结点之后，则根本无需移动（特别快）若插入在首结点之前，则表中元素全部要后移（特别慢）应当考虑在各种位置插入（共n+1种可能）的平均移动次 数才合理。讨论1：若在长度为 n 的线性表的第 i 位前 插入一 个元素，则向后移动元素的次数f(n)为: f(n) = n i + 1时间效率分析:32插入时的平均移动次数为同理可证：顺序表删除一元素的平均移动次数为想一想：想一想： 顺序表插入、删除算法的平均空间复杂度为多少？O(1)因为没有 占用辅助 空间！33链式存储结构2.2节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在 物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：34
