第二章(顺序表).ppt

1、第二章 线性表,内容:1、线性表的类型定义 2、线性表顺序表示和实现 3、线性表的链表表示和实现 重点：顺序表和单链表的描述方法，遍历、插入和删除算法。同时还要掌握其他基本操作的实现。,线性结构的基本特征为:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素” ；,3除最后元素在外，均有 唯一的直接后继；,4除第一元素之外，均有 唯一的直接前驱。,线性结构是一个数据元素的有序(次序)集,线性表是一种最简单的线性结构,2.1 线性表的类型定义,2.3 线性表类型的实现 链式映象,2.4 一元多项式的表示,2.2 线性表类型的实现 顺序映象,2.1 线性表的类型定义,线

2、性表：是若干个数据元素的有限序列。 记为：（a1,a2,ai-1,ai,ai+1,an) 注：线性表中数据元素可以是多种多样的，但同一线性表中数据元素必须具有相同特性；相邻数据元素之间存在序偶关系。ai-1是ai的直接前驱，ai+1是ai的直接后继。,抽象数据类型线性表的定义如下：,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。,数据关系：,R1 |ai-1 ,aiD, i=2,.,n ,设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中

3、的位序。,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作, ADT List,InitList( ,2依值在线性表LA中进行查访;,3若不存在，则插入之。,GetElem(LB, i)e,LocateElem(LA, e, equal( ),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 ,f

4、or (i = 1; i = Lb_len; i+) , / union,例2-2,已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据仍按值非递减有序排列。,分析： LC先设为空表，然后将LA或LB中的元素逐个插入到LC中。可设两个整型变量i、j，分别指向LA和LB，比较i、j所指元素的大小，决定哪个元素插入LC。插入后，在LA 或LB 中顺序后移。,void MergeList(List La, List Lb, List / 构造空的线性表 Lc i = j = 1; k = 0; La_len = ListLength(La);

5、 Lb_len = ListLength(Lb);,while (i=La_len) / 若 La 不空 while (j=Lb_len) / 若 Lb 不空,GetElem(La , i ,ai);/取出La中的元素 GetElem(Lb , i ,bj); /取出Lb中的元素 if(ai =bj ) /向Lc中插入元素ai ListInsert(Lc, +k , ai); + i; else /向Lc中插入元素bj ListInsert(Lc, +k , bj); + j; ,while (i = La_len) / 当La不空时 GetElem(La, i+, ai); ListInse

6、rt(Lc, +k, ai); / 插入 La 表中剩余元素,while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素,2.2 线性表类型 的实现-顺序映象,最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻。,顺序映象, 以 x 的存储位置和 y 的存储位置之间的某种关系表示逻辑关系。,用一组地址连续的存储单元 依次存放线性表中的数据元素。 采用这种存储结构的线性表叫做顺序表。,a1 a2 ai-1 ai an,线性表的起始地址 称作线性表的基地址,1、线

7、性表的顺序存储结构,以“存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址,2、特点：,数据元素在“逻辑关系上的相邻”用“物理地址相邻”来表示。顺序表中任一元素都可“随机存取”。,3、顺序映像的 C 语言描述,typedef struct SqList; / 俗称 顺序表,#define MAXSIZE 100 / 线性表存储空间的分配量，即数组长度,ElemType elemMAXSIZE;,int length; / 当前

8、长度,4、线性表的基本操作在顺序表中的实现,InitList( return OK;,例如：顺序表,e =,38,i,1,2,3,4,1,8,50,可见，基本操作是： 将顺序表中的元素 逐个和给定值 e 相比较。,int Locate (SqList L, ElemType x) / 在顺序表中查询第一个等于x的数据元素， / 若存在，则返回它的位序，否则返回 0 / Locate,O( L.length ),算法的时间复杂度为：,i = 1; / i 的初值为第 1 元素的位序,while ( L.elemi-1 !=x,if (i = L.length) return i; else re

9、turn 0;,线性表操作 ListInsert( j=i ; j - - ) L.elemj=L.elemj-1; / 插入位置及之后的元素右移 L.elemi-1 = e ; / 插入e +L.length; / 表长增1 return OK;,if (i L.length+1) return ERROR; / 插入位置不合法,插入算法时间复杂度分析： 考虑移动元素的平均情况,插入位置,需要移动的结点次数,1,n,2,n-1,n,1,n+1,0,平均次数:,(1+2+n-1+n)/(n+1) =n/2,T(n)=O(n),例如：ListInsert_Sq(L, 5, 66),L.lengt

10、h-1,0,87,56,42,66,线性表操作 ListDelete(&L, i, &e)的实现：,首先分析：,删除元素时， 线性表的逻辑结构发生什么变化？,(a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an),ai+1,an, ,表的长度减少,Status ListDelete_Sq (SqList / ListDelete_Sq,算法时间复杂度为:,O( L.length),L.length-1,0,87,56,例如：ListDelete_Sq(L, 5, e),删除算法时间复杂度分析： 考虑移动元素的平均情况,删除位置,需要移动的结点次数,1,n-1,2,n-2,n,0,平均次数:,(0+1+n-11)/n =(n-1)/2,T(n)=O(n),取元素（取第i个元素,Status GetElem(SqList L,