资源描述:
《数据结构课件第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=