资源描述：
《数据结构ppt教学课件第2章线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、２.1线性表的定义及其运算２.2线性表的顺序存储结构（向量）２.3线性表的链表存储结构２.４循环链表和双向链表２.5多项式相加问题２.6线性表的算法实现举例第2章线性表返回主目录２.１.２各种运算简介对线性表要经常进行的基本运算主要有以下几种:（1）求线性表的表长Length(L);（2）取线性表中的第ｉ个元素Get(L,i);（3）修改线性表中的第ｉ个元素Modify(L,i);（4）删除线性表中的第ｉ个元素Delete(L,i);（5）在线性表中第ｉ个元素之后（或之前）插入一个新元素Insert(L,i,x);第2章线性表2.1线性表的定义及其运用２
2、.２线性表的顺序存储结构（向量）２.２.１顺序存储结构（向量）在计算机内,可以用不同的方法来存储数据信息,最常用的方法是顺序存储。顺序存储结构也称为向量存储。向量是内存中一批地址连续的存储单元。由于线性表的所有数据元素属于同一类型,所以每个元素在存储器中占用的空间大小相同。假设向量的第一个元素存放的地址为LOC(a1),每个元素占用的空间大小为L个字节,则元素ai的存放地址为LOC(ai)＝LOC(a1)＋L*(i－1)线性表的这种机内表示称做线性表的顺序存储结构或顺序映象(sequentialmapping),只要确定了存储线性表的起始位置,线性表中任一数据元
3、素都可随机存取,所以线性表的顺序存储结构是一种随机存取结构。在高级语言环境中常用一维数组来表示向量。为更好体现信息隐蔽原则以及数据抽象原则,在这里把数组和线性表的长度封装在一个结构体中:Structsequnce{ELEMTPelem;/*数组域*/intlen;/*表长域*/}２.２.２向量中基本运算的实现1.插入向量的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素x,使长度为ｎ的线性表（ａ1,…,ａi-1,ａi,…,ａｎ）变成长度为ｎ＋１的线性表（ａ1,…,ａi-1,x,ai,…,ａｎ）。插入操作应先把元素ai,…,ａ
4、ｎ向后各自移动一个位置,然后将x插在第i个位置上。C语言的数组下标从零开始,为了与前文概念的描述相一致,v.elem［0］闲置不用,将ａ1存放于v.elem［1］之中。插入过程可用如下算法来实现：算法2.1”SS]voidinsert(structsequnce*p,inti,ELEMTPx){structsequncev;v=*p;if((i<1)
5、
6、(i>v.len+1))printf("Error！");/*插入位置出错*/else{for(j=v.len;j>=i;j--)v.elem［j+1］=v.elem［j］;v.elem［j］=x;v.l
7、en=v.len+1;}*p=v;}在算法2.1基础上可以进一步分析线性表长度v.len的大小,如果v.len的值已经等于MAXSIZE-1,则不允许进行任何插入操作。由于C语言函数的一般参数仅能向被调函数传值,这个值在返回时也不会改变,因此在上面的算法中,采用指针变量p做参数,虽然从被调函数返回时p值不变,但是p中地址所代表的结构体的内容发生了变化。structsequncev;v=*p;这两个语句是为了使程序书写简明易懂,用v来表示结构体。这样,操作是在局部变量v结构体上进行,因此最后还要用*p=v;将改变后的内容赋值给*p,由指针变量p将结构带回主调函数。
8、在下面的删除算法中也是同样处理,目的是使算法主体部分简明扼要。处理此类函数的参数传递问题,上述方法多用了一个局部变量,并不理想。在本节最后的源程序例题中,使用的是另一种方法,也不理想。在此,问题显得如此麻烦,主要因为C语言参数传递的限制。如果换为C++语言,通过让&v做参数就可以解决问题。2.删除要删除线性表中的第i个元素ai,操作和插入操作类似。把元素ai+1,…,ａｎ分别向前移动一个位置,使长度为ｎ的线性表（ａ1,…,ａi-1,ai,…,ａｎ）,变成长度为ｎ－１的线性表（ａ1,…,ａi-1,ai+1,…,ａｎ）。在下面的算法中,仍假设ａ1存放在v.elem［1］
9、之中。删除算法见算法2.2。算法2.2算法2.2voiddelete(structsequnce*p,inti){v=*p;if((i<1)
10、
11、(i>v.len))printf("Notexist");else{for(j=i;j<=v.len-1;j++)v.elem［j］=v.elem［j+1］;v.len--;}*q=v;}关于两种运算的时间复杂度分析。从上述两个算法来看,当在顺序存储结构的线性表中某个位置上插入或删除一个向量时,其时间主要耗费在数据元素的移动上,而移动元素的次数取决于插入或删除元素的位
