2线性表.pptVIP

2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 2、线性表 * * 物料管理 LILST * * * 数据结构与程序设计考研复习提纲—SJTU 1、线性结构的定义： 空或者只有一个结点。或者 1、存在唯一的一个被称之为”第一个“ 的结点。 2、存在唯一的一个被称之为”最后一个“ 的结点。 3、除第一个结点之外，每个结点均只有一个前驱结点。 4、除最后一个结点之外，每个结点均只有一个后继结点。 分为以下几大类： ·线性表：进通过它们之间的相对位置，确定它们之间的相互关系的线性结构。 e.g: 序列：a1、 a2、 a3…………………an-1、 an ·分类表 ·时间有序表 ·频率有序表 ·序列 2、基本操作：插入、删除、查找 …… e.g:已知线性表 LA 和线性表 LB 中的结点为递增序。将 LA 和 LB 进行合并至 另一线性表 LC， 并仍为递增序。 LA ＝ （3，5，8，11） LB ＝ （2，6，8，9，11，15，20） LC ＝ （2，3，5，6，8，8，9，11，11，15，20） Void Mergelist(List La,list Lb, list Lc) { InitiList( Lc ); i=j=1; k=0; La.len = ListLength(La); Lb.len = ListLength(Lb); while ( ( i = La.len ) ( j = Lb.len ) ) { GetElem(La,i,ai); GetElem(Lb,j,bj); if (ai = bj ) { Listinsert(Lc, ++k, ai ) ; ++i; } else { Listinsert(Lc, ++k, bj ) ; ++j; } } while (i = La.len) { GetElem(La,i,ai); Listinsert(Lc, ++k, ai ) ; ++i; }; while (j = Lb.len) { GetElem(Lb,j,bj); Listinsert(Lc, ++k, bj ) ; ++j; }; } // Mergelist La Lb 时间复杂性: O( m + n ) 3、物理存储位置的计算： ·顺序表示：在物理位置上紧靠在一起。如用数组表示线性表。 ·设第一个结点的存储地址为 LOC(a1), 余类推。设每个结点占用 L 个单元。则： an ai-1 a2 a1 ai LOC(ai) = LOC(ai-1) + L = LOC(ai-2) + 2L = LOC(ai-(i-1)) + (i-1)L = LOC(a1) + (i-1)L 4、插入的时间复杂性分析： 在一般情况下，插在第 i 个结点之前，移动 n-(i-1) 次 插在第 1 个结点之前，移动 n 次 插在第 2 个结点之前，移动 n-1 次 插在第 i 个结点之前，移动 n-(i-1) 次 插在第 n 个结点之前，移动 1 次。 插在第 n 个结点之后，移动 0 次。 总共 n+1 种情况 ·在长度为 n 的顺序表示的线性表中插入一个结点的平均次数为： ∑(n-i+1)/(n+1) = n/2 时间复杂性为 O(n)。 i =1 n 5、删除的时间复杂性分析： 在一般情况下，删除第 i 个结点，移动 n-i 次 删除第 1 个结点，移动 n-1 次 删除第 2 个结点，移动 n-2 次 删除第 i 个结点，移动 n-i 次 删除第 n 个结点，移动 0 次。 总共 n 种情况 ·在长度为 n 的顺序表示的线性表中删除一个结点的平均次数为： ∑(n-i)/n = (n-1)/2 时间复杂性为 O(n)。 i =1 n ·另外，通过 KEY 查找结点，代价 O(n)。 查找第 i 个结点，代价O(1)。 6、线性链表(单链接表)： · 结点的表示：参照下图所示的情况： data next typedef struct Lnode { ElemType