大学《数据结构》第二章：线性表-第二节-线性表的顺序存储和基本运算的实现

1、第二节线性表的顺序存储和基本运算的实现一、线性表的顺序存储1、顺序表的概念线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存 入一组地址连续的存储单元里，用这种方法存储的线性表称为顺序 表。当顺序表中每个结点占用d(dl)个存储单元，而且起始结 点ai的存储地址是Loc(ai),那么可以通过以下公式求得任一结点ai 的存储地址Loc ( ai):Loc ( ai) = Loc ( al) + (i-1) *d线性表的这种机内表示称为线性表的顺序存储结构。它的特点是， 元素在表中的相邻关系，在计算机内也存在着相邻的关系。2、顺序表数据类型的定义#define ListSize 100 表

2、的大小根据实际需要定义，这里假设为 100typedef int DataType ; /DataType的数据类型根据实际情况而 定，这里定义为inttypedef struct DataType dataListSize; 数组 data 用来存放表结点 int length ; 线性表的当前长度(实际元素的个数) SeqList ；顺序表的数据类型名3、顺序表在内存中的表示SeqList L ; 定义变量L为顺序表类型的变量存储地址存储地址顺序表存储地址顺序表b b+d b+(i4)db+(n4)db+(ListSize-l)d存储地址顺序表b b+d b+(i4)db+(n4)db+(

3、ListSize-l)dL.dataO L.datalL.datai-1L.datan-1L.dataListSize-l1、插入运算线性表的插入运算是指在线性表的第i-1个元素和第i个元素之间 插入一个新元素X。算法的基本步骤是：将结点ai，an各后移一 位以便腾出第i个位置；将x置入该空位；表长加10此外，必须在上述各步之前判断参数i即插入位置是否合法。初始状态ala2 ai.1at+1 an 移动元素alQ aiai+1 an 插入元素ala2 ailXaiatl 2B 表下标 01i-2i-1 in-1 nListSize-1算法描述：void InsertList(SeqLlst *

4、L , int i , DataType x)在顺序表L中第i个位置之前插入一个新元素xintj ;if(i L- length +1) 判断 i 值是否合法？当 i length + 1时,i值不合法。 printf(position error);return ;if(L-length = ListSize) 判断 L 是否已满？当 L- length = ListSize 时，表示 L 已满。printf(overflow);return ;for(j=L-length-l;j = i-l;j)L-dataj + l = L-dataj ”/从最后一个元素开始逐一后移L-datai-l=

5、x; 插入新元素 xL-length+ ; /实际表长力口 1)算法分析：(设表的长度为n)合法的插入位置共n + 1个，即第1个位置到到第n+1个位置。最坏情况是插入到第1个位置，共需要移动n个元素。故插入 算法的最坏情况时间复杂性是O(n)o最好情况是插入到第n + 1个位置，不需要移动元素。在插入位置等概率情况下，平均移动元素的个数为：(n + ( n -1) + ( n -2 ) + .+ 2 + 1+0 ) / ( n+1)= n / 2。故插入算法平均 时间复杂性是。(n )。真题选解（例题单项选择题）1、在长度为n的顺序表的第iQwEn + 1）个位置上 插入一个元素，元素的移动

6、次数为（）。A . n-i+1B . n-iC . iD . i-1显示答案2、删除运算线性表的删除运算是指将表的第i个结点删去，使其长度为变成n-lo算法的基本步骤是：从ai+i，an依次向前移一个位置；表 长减lo表下标 01i-2i-1 in-1 nListSize-1初始状态ala2 ai-1*ai+1 an-1an移动元素al12 ai-1ai+1ai+2 an算法描述：void DeleteList(SeqLlst *L , int i)删除顺序表L中第i个元素int j ; DataType xif(iL-length) 判断 i 值是否合法？当 i datai 保存被册!)除的

7、元素 for(j = i;jlength-l;j+)L-dataO-l = L-dataj; 元素前移L-length-; 实际表长减1return x ; 返回被删除的元素算法分析：(设表的长度为n)合法的删除位置共n个，即第1个位置到第n个位置。最坏情况是删除第1个位置上的元素，共需要移动n-1个元 素。故插入算法的最坏情况时间复杂性是O(n)o最好情况是删除第n个位置上的元素，不需要移动元素。在删除元素的位置等概率情况下，平均移动元素的个数为：(n-l) + (n-2)+ . + 2 + l+0)/n=(n-l)/2o 故删除算 法平均时间复杂性是0(n )。3、顺序表上的其他运算举例例

8、：一长度为n顺序存储的线性表，试写一算法将该线性表逆 置。分析：线性表为(ai, a2, . , an),逆置之后为(an, an-i，ai),实现其算法的基本思想是：先以表长的一半为循环控制次数，将表中最后一个元素同顺数第一个元素交换，将倒数第二个元素同顺数第二 个元素交换，依此类推，直至交换完为止。算法描述：SeqList ConVerts(SeqList L) DataType x ;int i , k ;k=L.length/2 ;for(i=O; ik; i+) 元素相互交换x=L.datai;L.datai = L.dataL.length-i-l;L.dataL.length-i

9、-l=x ;)return L :)算法分析：该算法的时间复杂度为0(n)当前讲授例：试写一算法，实现在顺序表中找出最大值和最小值的元素及其 所在位置。分析：扫描一次顺序表找出最大和最小值的元素。算法中要求带回 求得的最大值和最小值元素及其所在位置，可用4个指针变量参数间 接得到。算法描述：void MaxMin(SeqList L , DataType *max, DataType *min,int*k,int *j)int i;*max=L.dataO;*min = LdataO;*k=*j=l; 先假设第一个元素既是最大值，也是最小值for(i=l ; i* max) 发现更大的*max=L.datai ; *k=i ; else if(L.datai*min) 发现更小的*min=L.datai ; *j=