线性表(数据结构ppt)ppt课件.ppt

《线性表(数据结构ppt)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表2.1线性表的基本概念2.2线性表的顺序存储2.3线性表的链式存储2.4线性表的应用本章小结2.5有序表2.1.1线性表的定义线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n≥0。当n=0时，表示线性表是一个空表，即表中不包含任何元素。设序列中第i（i表示逻辑位序）个元素为ai（1≤i≤n）。线性表的一般表示为:(a1,a2,…ai,ai+1,…,an)逻辑结构2.1线性表的基本概念其中a1为第一个元素，又称做表头元素，a2为第二个元素，

2、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):当线性表L不为空

3、时，顺序显示L中各节点的值域。（6）求线性表L中指定位置的某个数据元素GetElem(L,i,&e)：用e返回L中第i（1≤i≤ListLength(L)）个元素的值。（7）定位查找LocateElem(L,e)：返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0。（8）插入数据元素ListInsert(&L,i,e)：在L的第i（1≤i≤ListLength(L)+1）个元素之前插入新的元素e，L的长度增1。（9）删除数据元素ListDelete(&L,i,&e)：删除L的第i

4、（1≤i≤ListLength(L)）个元素，并用e返回其值，L的长度减1。数据基本运算1基本运算n…用户设计的应用程序体现结构化编程的思想。例2.1假设有两个集合A和B分别用两个线性表LA和LB表示，即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合C=A∪B，即将两个集合的并集放在线性表LC中。解题思路:LCLALCLB中不在LA中的元素voidunionList(ListLA,ListLB,List&LC){intlena,i;ElemTypee;InitList(LC);f

5、or(i=1;i<=ListLength(LA);i++)//将LA的所有元素插入到Lc中{GetElem(LA,i,e);ListInsert(LC,i,e);}lena=ListLength(LA);//求线性表LA的长度for(i=1;i<=ListLength(LB);i++){GetElem(LB,i,e);//取LB中第i个数据元素赋给eif(!LocateElem(LA,e))//LA中不存在和e相同者,插入到LC中ListInsert(LC,++lena,e);}}本算法中，由于Lo

6、cateElem(LA,e)运算的时间复杂度为O(ListLength(LA))，所以本算法的时间复杂度为:O(ListLength(LA)*ListLength(LB))。2.2线性表的顺序存储2.2.1线性表的顺序存储—顺序表2.2.2顺序表基本运算的实现2.2.1线性表的顺序存储—顺序表线性表的顺序存储结构：把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。这样,线性表中第一个元素的存储位置就是指定的存储位置，第i+1个元素（1≤i≤n-1）的

7、存储位置紧接在第i个元素的存储位置的后面。线性表逻辑结构顺序表存储结构区别假定线性表的元素类型为ElemType，则每个元素所占用存储空间大小（即字节数）为sizeof(ElemType)，整个线性表所占用存储空间的大小为:n*sizeof(ElemType)其中，n表示线性表的长度。顺序表示意图在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用data[MaxSize]表示，长度整型变量用length表示，并采用结构体类型

8、表示，则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下:typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;//顺序表类型其中data成员存放元素，length成员存放线性表的实际长度。说明：由于C/C++中数组的下标从0开始，线性表的第i个元素ai存放顺序表的第i-1位置上。为了清楚，将ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。对于第1章的逻辑结构City，假定