《线性表的定义 顺序表示和实现(精品).ppt》由会员分享，可在线阅读，更多相关《线性表的定义 顺序表示和实现(精品).ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和队列 第第4章章 串串第第6 6章章 树和二叉树树和二叉树 第第7章章 图图第第9章章 查找查找第第10章章 排序排序目目 录录1数据结构课程的起点：数据结构课程的起点：什么是什么是线性结构？线性结构？2 线性结构的线性结构的基本特征基本特征:1 1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2 2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素”3 3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4 4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。线性
2、结构线性结构 是一个数据元素的是一个数据元素的有序（次序）集有序（次序）集特点：一对一特点：一对一3第第2 2章章 线性表线性表2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 应用举例应用举例4（a1,a2,ai-1，ai,ai1，,an）2.1 2.1 线性表的逻辑结构线性表的逻辑结构 线性表的定义：线性表的定义：线性表的定义：线性表的定义：用数据元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直
3、接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。n0n0空表空表线性终点线性终点5 （A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级012003010622012003010622陈建武陈建武男男 19 1920032003级电信级电信03010301班班012003010704012003010704赵玉凤赵玉凤女女 18 1820032003级电信级电信03020302班班012003010813012003010813王王 泽泽男男 19 1920032003级电信级
4、电信03030303班班012003010906012003010906薛薛 荃荃男男 19 1920032003级电信级电信03040304班班012003011018012003011018王王 春春男男 191920032003级电信级电信03050305班班：例例2 2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析分析:数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系元素间关系是线性的。是线性的。例例1 1 分析分析26 26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。6“同同一一数数据据逻逻辑辑结结构构中中的的所所有有数
5、数据据元元素素都都具具有有相相同同的的特特性性”是是指指数数据据元元素素所所包包含含的的数数据据项项的的个个数数都都相相等。等。是指各元素具有相同的数据类型是指各元素具有相同的数据类型是指各元素具有相同的数据类型是指各元素具有相同的数据类型试判断下列叙述的正误：试判断下列叙述的正误：注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性 ！分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系），元素间关系是线性的。是线性的。7抽象数据类型抽象数据类型线性表线性表的定义
6、如下：的定义如下：ADT List 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 基本操作：基本操作：结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT List8 InitList(&L)操作结果：构造一个空的线性表L结构初始化操作结构初始化操作结构销毁操作结构销毁操作DestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表L引用型操作引用型操作:ListEmpty(L)/判空 ListLength(L)/表长PriorElem(L,
7、cur_e,&pre_e)/前驱 NextElem(L,cur_e,&next_e)/后继9 GetElem(L,i,&e)/读取 LocateElem(L,e,compare()/查找ListTraverse(L,visit()/遍历 加工型操作加工型操作 ClearList(&L)/清空PutElem(&L,i,&e)/改写ListInsert(&L,i,e)/插入ListDelete(&L,i,&e)/删除 10例1：假设:有两个集合集合 A A 和和 B B 分别用两个线性表线性表 LA LA 和和 LB LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合现要求一个
8、新的集合A AABAB。即即扩大线性表扩大线性表 LALA，将存在于线性表，将存在于线性表LB LB 中而不存在于中而不存在于线性表线性表 LA LA 中的数据元素插入到线性表中的数据元素插入到线性表 LA LA 中去。中去。操作步骤：操作步骤：1 1从线性表从线性表LBLB中依次察看每个数据元素中依次察看每个数据元素;2 2依值在线性表依值在线性表LALA中进行查访中进行查访;GetElem(LB,i)e LocateElem(LA,e,equal()3 3若不存在，则插入之。若不存在，则插入之。ListInsert(LA,n+1,e)11 GetElem(Lb,i,e);/取取Lb中第中第
9、i个数据元素赋给个数据元素赋给e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union(List&La,List Lb)La_len=ListLength(La);/求线性表的长度求线性表的长度 Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)/union12集合集合 B集合集合 A从集合从集合 B 取出物件放入集合取出物件放入集合 A要求集合要求集合A中不能有同样物件中不能有同样物件因此，因此，算法的策略应
10、该和例算法的策略应该和例1相同相同例例2 2：已知一个非纯集合：已知一个非纯集合 B B，试构造一个纯集合，试构造一个纯集合 A A，使使 A A中只包含中只包含 B B 中所有值各不相同的数据元素。中所有值各不相同的数据元素。13void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);/union GetElem(Lb,i,e);/取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在中不
11、存在 /和和 e 相同的数据元素，则插入之相同的数据元素，则插入之for(i=1;i=i;j-)aj+1=a j;a i=x;n+;/后移一个位置/插入/表长加1注意注意2 2：表是否已满？：表是否已满？如表长超过表尺寸则要增加尺寸。如表长超过表尺寸则要增加尺寸。注意注意1：事先应判断：事先应判断:插入位置插入位置i 是否合法是否合法?应当符合条件：应当符合条件：1in+1 或或 i=1,n+1 使用使用reallocrealloc（*p p，newsizenewsize）：新开一片大小为）：新开一片大小为newsizenewsize的连续空间，并把以的连续空间，并把以*p p为首址的原空间数
12、为首址的原空间数据都拷贝进去，并把该区首址作为函数值。据都拷贝进去，并把该区首址作为函数值。动态数组的核心是动态数组的核心是realloc（void*p，newsize）函数函数 算法见教材 P2426 Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移*q=e;/插入e+
13、L.length;/表长增1return OK;27if(L.length=L.listsize)/当前存储空间已满，增加分配 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败 L.elem=newbase;/新基址 L.listsize+=LISTINCREMENT;/增加存储容量if(i L.length+1)return ERROR;/插入位置不合法28删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素
14、3)3)删除删除删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：12345678912132124262830427712345678121321242830427729算法见教材 P24实现步骤：实现步骤：将第将第i+1i+1 至第至第n n 位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1 1。注意：事先需要判断，注意：事先需要判断，删除位置删除位置i i 是否合法是否合法?应当符合条件：应当符合条件：1in 1in 或或 i=1,ni=1,n核心语句：核心语句：for(j=i+1;j=n;j+)aj-1=aj;n-;/前移一个位置/表长减
15、130Status ListDelete_Sq (SqList&L,int i,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移-L.length;/表长减1return OK;p=&(L.elemi-1);/p 为被删除元素的位置e=*p;/被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置if(i L.length)return ERROR;/删除位置不合法返返 回回312.2.3 2.2.3 顺序表的运算效率分析顺序表的运算效率分析算法时间主要耗费在算法时间主要耗费在移动元素移动元素的
16、操作上，因此的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度）T(n)=OT(n)=O (移动元素次数移动元素次数)而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）若插入在尾结点之后，则根本无需移动（特别快）若插入在首结点之前，则表中元素全部要后移（特别慢）若插入在首结点之前，则表中元素全部要后移（特别慢）应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数才合理。数才合理。讨论讨论1 1：若在长度为
17、若在长度为 n n 的线性表的第的线性表的第 i i 位前位前 插入插入一个一个元素，则向后移动元素的次数元素，则向后移动元素的次数f(n)f(n)为为:f(n)=f(n)=n i+1时间效率时间效率分析分析:32插入时的平均移动次数为插入时的平均移动次数为同理可证：同理可证：顺序表删除一元素的平均移动次数为顺序表删除一元素的平均移动次数为 想一想：想一想：想一想：想一想：顺序表插入、删除算法的顺序表插入、删除算法的平均空间复杂度平均空间复杂度为多少为多少？O(1)O(1)因为没有因为没有占用辅助占用辅助空间！空间！33链式存储结构链式存储结构2.22.2节小结节小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的两个元素在：逻辑关系上相邻的两个元素在物理存储位置上也相邻；物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素，方便快捷；可以随机存取表中任一元素，方便快捷；缺点：缺点：在插入或删除某一元素时，需要移动大量元素。在插入或删除某一元素时，需要移动大量元素。解决问题的思路：解决问题的思路：改用另一种线性存储方式：改用另一种线性存储方式：34