资源描述：
《数据结构线性表PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表2.1线性表的基本概念2.2线性表的顺序存储2.3线性表的链式存储2.4线性表的应用本章小结2.5有序表2.1线性表的基本概念2.1.1线性表的定义2.1.2线性表的运算2.1.1线性表的定义线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n≥0。当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1≤i≤n)。线性表的一般表示为:(a1,a2,…ai,ai+1,…,an)其中a1为第一个元素,又称做表
2、头元素,a2为第二个元素,an为最后一个元素,又称做表尾元素。例如,在线性表(1,4,3,2,8,10)中,1为表头元素,10为表尾元素。2.1.2线性表的运算线性表的基本运算如下:(1)初始化线性表InitList(&L):构造一个空的线性表L。(2)销毁线性表DestroyList(&L):释放线性表L占用的内存空间。(3)判线性表是否为空表ListEmpty(L):若L为空表,则返回真,否则返回假。(4)求线性表的长度ListLength(L):返回L中元素个数。(5)输出线性表DispList(L
3、):当线性表L不为空时,顺序显示L中各结点的值域。(6)求线性表L中指定位置的某个数据元素GetElem(L,i,&e):用e返回L中第i(1≤i≤ListLength(L))个元素的值。(7)定位查找LocateElem(L,e):返回L中第1个值域与e相等的位序。若这样的元素不存在,则返回值为0。(8)插入数据元素ListInsert(&L,i,e):在L的第i(1≤i≤ListLength(L)+1)个元素之前插入新的元素e,L的长度增1。(9)删除数据元素ListDelete(&L,i,&e):删
4、除L的第i(1≤i≤ListLength(L))个元素,并用e返回其值,L的长度减1。例2.1假设有两个集合A和B分别用两个线性表LA和LB表示,即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合C=A∪B,即将两个集合的并集放在线性表LC中。解:本算法思想是:先初始化线性表LC,将LA的所有元素复制到LC中,然后扫描线性表LB,若LB的当前元素不在线性表LA中,则将其插入到LC中。算法如下:voidunionList(ListLA,ListLB,List&LC){intlena,lenc,
5、i;ElemTypee;InitList(LC);for(i=1;i<=ListLength(LA);i++)/*将LA的所有元素插入到Lc中*/{GetElem(LA,i,e);ListInsert(LC,i,e);}lena=ListLength(LA);/*求线性表的长度*/lenB=ListLength(LB);for(i=1;i<=lenb;i++){GetElem(LB,i,e);/*取LB中第i个数据元素赋给e*/if(!LocateElem(LA,e))ListInsert(LC,++le
6、nc,e);/*LA中不存在和e相同者,则插入到LC中*/}}由于LocateElem(LA,e)运算的时间复杂度为O(ListLength(LA)),所以本算法的时间复杂度为:O(ListLength(LA)*ListLength(LB))。2.2线性表的顺序存储2.2.1线性表的顺序存储—顺序表2.2.2顺序表基本运算的实现2.2.1线性表的顺序存储—顺序表线性表的顺序存储结构就是:把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。这样,线性表中第一个
7、元素的存储位置就是指定的存储位置,第i+1个元素(1≤i≤n-1)的存储位置紧接在第i个元素的存储位置的后面。线性表逻辑结构顺序表存储结构假定线性表的元素类型为ElemType,则每个元素所占用存储空间大小(即字节数)为sizeof(ElemType),整个线性表所占用存储空间的大小为:n*sizeof(ElemType)其中,n表示线性表的长度。顺序表示意图在定义一个线性表的顺序存储类型时,需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用data[MaxSiz
8、e]表示,长度整型变量用length表示,并采用结构体类型表示,则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下:typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;/*顺序表类型*/其中,data成员存放元素,length成员存放线性表的实际长度。说明：由于C/C++中数组的下标从0开始，线性表的第i个元素ai存放顺序表的第i-1位置上。为了清
