数据结构学习――第二章线性表.ppt

《数据结构学习――第二章线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第二章线性表（linearlist)2.1线性表的定义及运算1.线性表的定义：是由n(n>=0)个数据元素（结点）a1,a2,a3,……an组成的有限序列。其中：n为数据元素的个数，也称为表的长度。当n=0时，称为空表。非空的线性表(n>0)记作：（a1,a2,a3,……an）12.线性表（a1,a2,a3,……an）的逻辑特征：（1）有且仅有一个开始结点a1(无直接前趋）；（2）有且仅有一个终端结点an(无直接后继）；（3）其余的结点ai都有且仅有一个直接前趋ai-1和一个直接后继ai+1。（4）ai是属于

2、某个数据对象的元素，它可以是一个数字、一个字母或一个记录。23.线性表的特性（1）线性表中的所有数据元素的数据类型是一致的。（2）数据元素在线性表中的位置只取决于它的序号。（3）结点间的逻辑关系是线性的。3例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）4例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790

3、634男17神经衰弱……..……..…….…….…….54.线性表的运算数据的运算是定义在逻辑结构上的，而具体的实现则在存储结构上进行。（1）存取（2）插入（3）删除（4）查找（5）合并（6）分解（7）排序（8）求线性表的长度基本运算6线性表的顺序存储结构（顺序表）1.顺序表的定义：------用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。72.顺序表中数据元素的存储地址若一个数据元素仅占一个存储单元，则其存储方式参见下图。从图中

4、可见，第i个数据元素的地址为：LOC（ai）=loc(a1)+(i-1)8若每个数据元素占用m个存储单元，则第i个数据元素的存储位置为：LOC（ai）=loc(a1)+(i-1)*mloc(a1)称为基地址（第一个数据元素的存储位置）。显然，数据元素在顺序表中位置取决于数据元素在线性表中的位置。顺序表的特点是：逻辑位置相邻，其物理位置也相邻。93.顺序表的描述：可用C语言的一维数组实现：#defineM100intv[M];其中：M是大于线性表长度的一个整数，它可根据实际需要而修改。线性表的各个元素a1,a2,

5、a3,……an可依次存入在向量v的各个分量v[1],v[2],…...,v[n]中。105.顺序表的几种基本运算（1）插入运算---在第i（1<=i<=n)个元素之前插入一个新的数据元素x。使：长度为n的线性表变为长度为n+1的线性表（a1,a2,…,ai-1,ai,…,an）（a1,a2,…,ai-1,x,ai,…,an）11插入算法的思想：若i=n+1,则将x插入到表尾；若表长度n<0或插入位置不适当，则输出错误信息，并返回-1；当1<=i<=n时，则从表尾开始到i个依次向后移动一个位置（共需移动n-i+1个

6、数据元素。最后将x存入v[i]中，表长n增1插入成功，函数返回值为0。12插入算法描述intsxbcr(v,pn,i,x)intv[],x,*pn,i;/*--pn指向表长n的地址。--*/{intj;if(*pn<0){printf(“表长错误");return(-1);}if(i<1

7、

8、i>*pn+1){printf(“插入位置i不适当");return(-1);}for(j=*pn;j>=i;j--)v[j+1]=v[j];v[j]=x;(*pn)++;printf("success");ret

9、urn(0);}算法调用：k=sxbcr(&v,&n,i,x)13插入算法分析：上述算法for循环语句的执行次数为n-i+1;若i=1,需移动全部n个结点（最坏：O(n)）若i=n+1（在表尾插入）,无需用移动结点，直接插入即可。（最好O(1)）移动结点的平均次数：14按等概率考虑：可能的插入位置为i=1,2,……n,n+1共n+1个，则pi=1/(n+1)所以顺序表插入算法平均约需移动一半结点。15（2）删除算法---将线性表的第i（1<=i<=n)个结点删除，使：长度为n的线性表变为长度为n-1的线性表。（a

10、1,a2,…,ai-1,ai,ai+1,…,an）（a1,a2,…,ai-1,ai+1,…,an）16删除算法的思想：若i=n,只需删除终端结点，不用移动结点；若表长度n<=0或删除位置不适当，则输出错误信息，并返回-1；当1<=i