数据结构课件第2章.ppt

《数据结构课件第2章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性表线性表的基本概念线性表：是由一组数据元素组成，线性表或者是一个空表，或者可以写成{a1,a2,…ai,…,an}，其中ai是取自某个集合S的元素。当1

2、个后继。Partition(L,L1,L2)：将L拆分成L1和L2。Search(L,b):查找满足条件b的数据元素。Sort(L)：将L中所有数据元素进行排序（降序或者升序）。Prior(L,elm)：求元素elm的前驱。Next(L,elm)：求元素elm的后继。Empty(L)：判空表函数。Clear(L)：表置空操作。线性表可以进行如下运算：Initiate(L)：初始化操作，设定一个线性表。Length(L)：长度的函数，返回元素的个数。Access(L,i)：访问第i个数据元素。Insert(L,i,b)：在第i个元素之前，插入元素b。Delete(L,i)：删除第i个元

3、素。Merge(L1,L2)：合并L1和L2，合并结果保存在L1中。线性表的存储结构在计算机中有不同的方法来表示线性表，最普通、最简单的方法是顺序映像或顺序分配，即采用一组连续的存储单元依次存储线性表中各数据元素。顺序分配的存储结构采用向量结构：设线性表的长度为N，建立一向量V，用V[i]表示第i个分量，第i个分量是线性表第i个元素ai在计算机存储中的映像，即V[i]=ai。顺序存储结构一、顺序存储结构的定义存储地址内存状态元素序号空闲aaaa12in:::::::bb+Lb+(i-1)Lb+(n-1)Lb+(maxlen-1)L12in线性表的顺序存储结构示意图若线性表中的第一个存

4、储元素的地址为LOC[a1]，每个元素占用L个存储单元，则表的第i个元素的存储地址为：LOC[ai]=LOC[a1]+(i-1)LLOC[ai]=LOC[ai-1]+L若每个元素仅占用1个存储单元，则表的第i个元素的存储地址为：LOC[ai]=LOC[a1]+(i-1)存储密度d：d=数据元素的值所需的存储量/该数据元素所需的存储总量在顺序分配的存储结构中，所有的存储单元空间全部被数据元素有效占用，因此，顺序分配结构的存储密度d=1。二、顺序存储结构的插入和删除运算1删除运算例：设有长为n的线性表a1,a2,…,an,删除ai，并把它送入某单元Y。Yaia1a2a3ai-1aian:

5、:123i-1in-1i+1n::a1a2a3ai-1an::123i-1in-1i+1n::ai+1顺序存储结构的删除操作顺序存储结构的删除操作算法：1、如果1=

6、pedefstructL_stru{intn;/表长度为n/inta[m];/数据元素向量为整型/}；voiddelete(L,i,y)/删除数据元素函数/structL_struL；/定义参数类型/inti,y;{intj;if((i<1)(i>L.n))/判断删除数据元素的位置/printf(“Thedeletepositionisnotcorrect!”);else{y=L.a[i-1];/a的下标从0开始，不是从1开始/for(j=i;j<=L.n-1;j++)/j<=L.n-1即j<=n-1/L.a[j-1]=L.a[j];L.n=L.n-1;}}删除操作算法的程序段：

7、2插入运算例：设有长为n的线性表a1,a2,…,an,在第i位置插入新数据元素x。顺序存储结构的插入操作xa1a2a3ai-1aian::123i-1ini+1::a1a2a3ai-1an-1::123i-1ini+1n+1::aixan顺序存储结构的插入操作算法：1、如果1=