《线性表1-第2讲》由会员分享，可在线阅读，更多相关《线性表1-第2讲（36页珍藏版）》请在金锄头文库上搜索。
1、第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序目 录线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有一个直接前趋和一个直 接后继。 可表示为：（a1 , a2 , , an） 简言之，线性结构反映结点间的逻辑关系是 的。特点 只有一个首结点和尾结点； 特点 除首尾结点外，其他结点只有一个直接前驱和一个 直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是-线性表线性表一对一 (1:1)第第2 2章章 线性表线性表2.1
2、 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 2.4 应用举例应用举例（a1, a2, ai-1，ai, ai1 ，, an）2.1 线性表的逻辑结构 线性表的定义：线性表的定义：是n个数据元素的有限序列；表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的 序号，表示元素 在表中的位置n为元素总 个数，即表 长。n0n0空表线性终点（ A, B, C, D, , Z）学号姓名性别年龄班级 012003010622陈建武男 192003级电信030
3、1班012003010704赵玉凤女 182003级电信0302班 012003010813王 泽男 192003级电信0303班012003010906薛 荃男 192003级电信0304班012003011018王 春男 192003级电信0305班： ：例2 分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析： 数据元素都是同类型（字母）， 元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性 ！例1 分析26 个英文字母组成的英文表是什么结构。“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数
4、据元素所包含的数据项的个数都相等。是指各元素具有相同的数据类型是指各元素具有相同的数据类型试判断下列叙述的正误：线性表抽象数据类型线性表的定义ADT List 数据对象：D=ai | aiElemSet, i=1,2,n,n0 数据关系：R1= | ai 1, ai D, i=2,n 基本操作： InitList( /建空表，初始化 DestoryList( /撤销表，释放内存 LengthList( L ); /求表中元素个数，即表长 LocateElem (L,ElemType e，compare() ); PriorElem( L, cur_e, /求当前元素e的前驱 NextElem(
5、 L, cur_e, /求当前元素e的后继 ListInsertBefore( /把e插入到第i个元素 之前 ListDelete( /删除第i个元素并“看” 此元素 ListTraverse( L, Visit() ); / “看”表中全部元素（遍 历） ADT List例2-1 两个线性表LA和LB分别表示两个 集合A和B，现要求一个新的集合A=AB算法思想：将存在于LB中而不存在于LA中的依 次取LB中每一个元素,依值在LA中查找，若不 存在则插入。void union(List Lb_len=ListLength(Lb);/求线性表的度 for (i=1;i=i; j- -) aj+1
6、=a j ; a i =x; n+;/ 元素后移一个位置 / 插入x / 表长加1 核 心 语 句 ：2)插入在线性表的第i个位置前插入一个元素的示意图如下：12 13 21 24 28 30 42 7712 13 21 242525 28 30 42 7712345678123456789插入2525实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当有1in 或 i=1, n删除线性表的第i个位置上的元素for ( j=i+1; j L.length+1) return ERROR; / 检验i 值的合法性if ( L.l
7、ength L.listsize ) /若表长超过表尺寸则要增加尺寸 newbase = ( ElemType* ) realloc ( L.elem , (L.listsize + + LISTLISTINCREMENTINCREMENT )* sizeof ( ElemType ) );if (newbase=NULL )exit( OVERFLOW ) ; /分配失败则退出并报错L.elem = newbase ; /重置新基址L.listsize = L.listsize + + LISTINCREMENT LISTINCREMENT ; /增加表尺寸q = / q为插入位置。这是没有
8、头结点的情况for ( p = L.elemL.length-1 ; p=q ; -p ) *(p+1) = *p ;/插入位置及之后的元素统统后移, p为元素位置*q= e ; /插入e+L.length ; /增加1个数据元素，则表长+1return OK ; /ListInsert_Sq动态数组的核心是realloc(void *ptr, newsize)函数！动态顺序表的删除算法动态顺序表的删除算法 Status ListDelete_Sq(SqList / i 值不合法，返回p= / p 是被删除元素的位置e=*p; /被删除元素的值赋给 e q=L.elem+L.length-1;
9、 / q 是表尾的位置for(+p; p=q; p+) *(p-1) = *p; /待删元素后面的统统前移-L.length; /表长 - 1return OK; /ListDelete_Sq查找元素的算法int LocateElem_Sq(SqList L, ElemType e,Status(*compare)(ElemType,ElemType)/在顺序线性表L中查找第1个值与e满足compare()的 元素位序,若找到则返回其在L中的位序,否则返回0i=1; /i的初值为第 1个元素的位序p=L.elem; /p的初值为第1个元素的存储位置while(i=L.lengthif (i=L
10、.length) return i;else return 0; / LocateElem_Sq归并算法void MergeList_Sq(SqList La, SqList Lb, SqList pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(Elemtype);if (!Lc.elem) exit(OVERFLOW); /存储分配 失败pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.lengt
11、h-1; while(pa=pa_lastelse *pc+=*pb+; while(pa=pa_last) *pc+=*pa+; /插入La的剩 余元素 While(pb=pb_last) *pc+= *pb+;/插入Lb的剩 余元素 /MergeList_Sq 时间复杂度为 O(La.length+Lb.length)2.2.3 顺序表的运算效率分析算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度）T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置.思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素
12、全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才 合理。讨论1：若在长度为 n 的线性表的第 i 位前 插入一个元素， 则向后移动元素的次数f(n)为: f(n) = n i + 1时间效率分析:推导：假定在每个元素位置上插入x的可能性都一样（即 概率P相同），则应当这样来计算平均执行时间： 将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移n次； 若在a1后面插入，要后移n-1个元素，后移次数为n-1; 若在an-1后面插入，要后移1个元素； 若在尾结点an之后插入，则后移0个元素；所有可能的元
13、素移动次数合计： 0+1+n = n(n+1)/2故插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n)O(n) 共有多少种插入形式?连头带尾有n+1种!同理可证：顺序表删除一元素的时间效率为: T（n)=(n-1)/2 O(n)O(n) 想一想：想一想： 顺序表插入、删除算法的平均空间复杂度为多少？插入效率：删除效率：教材P25算法2.5也是对执行效率的推导：因为没有 占用辅助 空间！含义：对于顺序表，插入、删除操作平均需要 移动一半元素( n / 2 )O(1)即插入、删除算法的平均 时间复杂度为 O(n)链式存储结构本节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素 在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：
