第二节 - 线性表的顺序存储和基本运算的实现
发布时间：2020-09-20 10:28来源：未知
第二节 线性表的顺序存储和基本运算的实现
一、线性表的顺序存储
1、顺序表的概念
线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。
当顺序表中每个结点占用d（d≥1）个存储单元，而且已知起始结点al的存储地址是Loc（a1），则可以通过下列公式求得任一结点ai的存储地址Loc（ai）：
Loc（ai）= Loc（a1）+（i-1）*d
线性表的这种机内表示称为线性表的顺序存储结构。它的特点是，元素在表中的相邻关系，在计算机内也存在着相邻的关系。
2、顺序表数据类型的定义
#define ListSize 100 //表的大小根据实际需要定义，这里假设为100
typedef int DataType； //DataType的数据类型根据实际情况而定，这里定义为int
typedef struct
｛DataType data[ListSize]；//数组data用来存放表结点
int length； //线性表的当前长度（实际元素的个数）
｝SeqList；//顺序表的数据类型名
3、顺序表在内存中的表示
SeqList L；//定义变量L为顺序表类型的变量
二、顺序表上基本运算的实现
1、插入运算
线性表的插入运算是指在线性表的第i-1个元素和第i个元素之间插入一个新元素x。算法的基本步骤是：①将结点ai，…，an各后移一位以便腾出第i个位置；②将x置入该空位；③表长加1。此外，必须在上述各步之前判断参数i即插入位置是否合法。
算法描述：
void InsertList(SeqLlst *L，int i，DataType x)
{ //在顺序表L中第i个位置之前插入一个新元素x
int j；
if(i<1||i>L->length+1) //判断i值是否合法？当i <l或i> length+1时，i值不合法。
{ printf("position error")；
return；
}
if(L->length>=ListSize) //判断L是否已满？当L->length>=ListSize 时，表示L已满。
{printf("overflow")；
return；
}
for(j=L->length-1;j>=i-l;j--)
L->data[j+1]=L->data[j]；//从最后一个元素开始逐一后移
L->data[i-1]=x； //插入新元素x
L->length++； //实际表长加1
}
算法分析：（设表的长度为n）
① 合法的插入位置共n+1个，即第1个位置到到第n+1个位置。
② 最坏情况是插入到第1个位置，共需要移动n个元素。故插入算法的最坏情况时间复杂性是O（n）。
③ 最好情况是插入到第n+1个位置，不需要移动元素。
④ 在插入位置等概率情况下，平均移动元素的个数为：（n +（n - 1）+（n -2）+ …+ 2 + 1+0）/（n+1）= n / 2。故插入算法平均时间复杂性是O（n）。
真题选解
（例题·单选题）1、在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( )。
A．n-i+1
B．n-i
C．i
D．i-1
2、删除运算
线性表的删除运算是指将表的第i个结点删去，使其长度为变成n-1。
算法的基本步骤是：①从ai+1，…，an依次向前移一个位置；②表长减1。
算法描述：
void DeleteList(SeqLlst *L，int i)
{ //删除顺序表L中第i个元素
int j；DataType x
if(i<1||i>L->length) //判断i值是否合法？当i <l或i>length时，i值不合法。
{ printf("position error")；
exit(0)；//不合法退出
}
DataType x= L->data[i] //保存被删除的元素
for(j=i;j<= L->length-1;j++)
L->data[j-1]=L->data[j]；//元素前移
L->length--； //实际表长减1
return x；//返回被删除的元素
}
算法分析：（设表的长度为n）
① 合法的删除位置共n个，即第1个位置到第n个位置。
② 最坏情况是删除第1个位置上的元素，共需要移动n-1个元素。故插入算法的最坏情况时间复杂性是O（n）。
③ 最好情况是删除第n个位置上的元素，不需要移动元素。
④ 在删除元素的位置等概率情况下，平均移动元素的个数为：（（n-1）+（n -2）+ … + 2 + 1+0）/ n=（n - 1）/ 2。故删除算法平均时间复杂性是O（n）。
3、顺序表上的其他运算举例
例：已知一长度为n顺序存储的线性表，试写一算法将该线性表逆置。
分析：线性表为(a1，a2，…，an)，逆置之后为(an，an-1，…，a1)，实现其算法的基本思想是：先以表长的一半为循环控制次数，将表中最后一个元素同顺数第一个元素交换，将倒数第二个元素同顺数第二个元素交换，…，依此类推，直至交换完为止。
算法描述：
SeqList ConVerts(SeqList L)
｛DataType x；
int i，k；
k=L.1ength/2；
for(i=O; i<k; i++) //元素相互交换
{ x=L.data[i]；
L.data[i]=L.data[L.1ength-i-1]；
L.data[L.1ength-i-1]=x；
}
return L：
}
算法分析：该算法的时间复杂度为O(n)
例：试写一算法，实现在顺序表中找出最大值和最小值的元素及其所在位置。
分析：扫描一次顺序表找出最大和最小值的元素。算法中要求带回求得的最大值和最小值元素及其所在位置，可用4个指针变量参数间接得到。
算法描述：
void MaxMin(SeqList L，DataType *max, DataType *min,int *k,int *j)
{ int i;
*max=L.data[0];*min=L.data[0]；
*k=*j=1；//先假设第一个元素既是最大值，也是最小值
for(i=l；i<L.1ength;i++) //扫描除第一个外的其他元素
if(L.data[i]>* max) //发现更大的
{ *max=L.data[i]；*k=i；}
else if(L.data[i]<*min) //发现更小的
{*min=L.data[i]；*j=i;}
}
算法分析：
①最坏情况：线性表元素递减有序排列，每次都和*max及*min比较，共比较2（n-1）次。
②最好情况：线性表元素递增有序排列，每次只和*max比较，共比较（n-1）次。
③该算法的平均比较次数为：(2(n-1)+(n-1))／2=3(n-1)／2。该算法的时间复杂度为O(n)。
