《数据结构》线性表的定义顺序表示和实现.ppt

第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序,目 录,数据结构课程的起点：,什么是 线性结构？,线性结构的基本特征:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素”,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,线性结构 是一个数据元素的有序（次序）集,特点：一对一,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 线性表的逻辑结构,线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,（ A, B, C, D, , Z）,例2 分析学生情况登记表是什么结构。,分析:数据元素都是同类型（字母）， 元素间关系是线性的。,例1 分析26 个英文字母组成的英文表是什么结构。,“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。,是指各元素具有相同的数据类型,试判断下列叙述的正误：,注意：同一线性表中的元素必定具有相同特性 ！,分析：数据元素都是同类型（记录），元素间关系是线性的。,抽象数据类型线性表的定义如下：,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,.,n, n0 ,数据关系：,R1 |ai-1 ,aiD, i=2,.,n ,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作, ADT List,InitList( &L ),操作结果：构造一个空的线性表L,结构初始化操作,结构销毁操作,DestroyList( &L ),初始条件：线性表L已存在 操作结果：销毁线性表L,引用型操作:,ListEmpty( L ) /判空 ListLength(L) /表长,PriorElem( L, cur_e, &pre_e ) /前驱 NextElem(L,cur_e,&next_e) /后继,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) /删除,例1：假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合AAB。,即扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,操作步骤：,1从线性表LB中依次察看每个数据元素;,2依值在线性表LA中进行查访;,GetElem(LB, i)e,LocateElem(LA, e, equal( ),3若不存在，则插入之。,ListInsert(LA, n+1, e),GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则插入之,void union(List ,for (i = 1; i = Lb_len; i+) , / union,集合 B,集合 A,从集合 B 取出物件放入集合 A 要求集合A中不能有同样物件,因此，算法的策略应该和例1相同,例2：已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相同的数据元素。,void union(List / union,GetElem(Lb, i, e); / 取Lb中第 i 个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在 /和 e 相同的数据元素，则插入之,for (i = 1; i = Lb_len; i+) ,InitList(La); / 构造(空的)线性表LA,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为有序表(Ordered List)。,试改变结构，以有序表表示集合。,例如：（2，3，3，5，6，6，6，8，12）,对集合 B 而言, 值相同的数据元素必定相邻,对集合 A 而言, 数据元素依值从小至大的顺序插入,因此，数据结构改变了， 解决问题的策略也相应要改变。,则,例3：归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表 LC 也具有同样特性。,设 La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n) 且已由(a1, , ai-1)和(b1, ,bj-1)归并得 (c1, , ck-1),k = 1, 2, , m+n,1初始化 LC 为空表；,基本操作：,2分别从 LA和LB中取得当前元素 ai 和 bj；,3若 aibj，则将 ai 插入到 LC 中，否则将bj 插入到 LC 中；,4重复 2 和 3 两步，直至 LA 或 LB 中元素被取完为止；,5将 LA 表或 LB 表中剩余元素复制插入到LC 表中。,算法见教材 P21,返 回,2.2 线性表的顺序表示和实现,2.2.1 顺序表的表示 2.2.2 顺序表的实现 2.2.3 顺序表的运算效率分析,2.2.1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物 理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现,注意：在C语言中数组的下标是从0开始，即： Vn的有效范围是从 V0Vn-1,地址求解公式：若已知表中首元素在存储器中的位 置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a1 ) + L *（i -1）,对上述公式的解释如图所示,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,LOC ( ai ) = LOC( a1 ) + L *（i -1）,线性表的顺序存储结构示意图,下标起点是1,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是98，则的第一个字节的地址是多少？,答案：113,但此题要注意下标起点是从0开始： LOC( M3 ) = 98 + 5 (4-1) =113,解：已知地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-1）,例,顺序映像的 C 语言描述,typedef struct SqList; / 俗称 顺序表,#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量,ElemType *elem; / 存储空间基址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),返 回,sizeof(x)算符的意思是：计算变量x的长度(字节数),malloc (m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。,Status InitList_Sq( SqList /InitList_Sq,2.2.2 顺序表的实现（或操作）,1）初始化 动态创建一个空顺序表,在线性表的第i个位置前插入一个元素,2)插入,在线性表的第i个位置前插入一个元素的示意图如下：,插入26,实现步骤： 将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。,核心语句：,for (j=n; j=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为首址的原空间数据都拷贝进去，并把该区首址作为函数值。,动态数组的核心是realloc（void*p，newsize）函数,算法见教材 P24,Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / ListInsert_Sq,q = ,if (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; / 插入位置不合法,删除线性表的第i个位置上的元素,3)删除,删除顺序表中某个指定的元素的示意图如下：,算法见教材 P24,实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当符合条件：1in 或 i=1, n,核心语句：,for ( j=i+1; j=n; j+ ) aj-1=aj; n-;,/前移一个位置 /表长减1,Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sq,for (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK;,p = / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,返 回,2.2.3 顺序表的运算效率分析,算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置.,思考：若插入在尾结点之后，则根本无需移动（特别快） 若插入在首结点之前，则表中元素全部要后移（特别慢） 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。,讨论1：若在长度为 n