三.顺序表的插入和删除
1.插入
Listlnsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。 位序
#define Maxsize 10 //定义最大长度
typedefstruct{
intdata[MaxSize]; //用静态的"数组"存放数据元素
intlength; //顺序表的当前长度
}SqList; //顺序表的类型定义
voidListInsert(SqList&L,inti,inte){
for(intj=L.length;j>=i;j--) //将第i个元素及之后的元素后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //在位置i处放入e
L.length++; //长度加1
}
intmain(){
SqListL; //声明一个顺序表
InitList(L); //初始化顺序表
//..,此处省略一些代码，插入几个元素
ListInsert(L,3,3);
return0;
}
前提是数组里已经插入了5个元素,length = 5
ListInsert(L,9,3)；
此时,插入的不合法,插入方法改进
boolListInsert(SqList&L,inti,inte){
if(i<1||i>L.length+1) //判断i的范围是否有效
returnfalse;
if(L.length>=MaxSize) //当前存储空间已满，不能插入
returnfalse;
for(intj=L.length;j>=i;j--) //将第i个元素及之后的元素后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; //在位置i处放入e
L.length++; //长度加1
return true;
}
好的算法，应该具有“健壮性”。能处理异常情况，并给使用者反馈
1.1插入操作的时间复杂度
L.data[j]=L.data[j-1];
关注最深层循环语句的执行次数与问题规模n的关系
问题规模n=L.length(表长)
最好情况：新元素插入到表尾，不需要移动元素i=n+1,循环0次；最好时间复杂度=O(1)
最坏情况：新元素插入到表头，需要将原有的个元素全都向后移动i=1,循环n次；最坏时间复杂度=On;
平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,23,,enth+1的概率都是p=1/(n+1)i=1,循环n次；i=2时，循环n-1次；i3,循环n-2次…i=n+1时，循环0次
2.删除
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
boolListDelete(SqList&L,inti,int&e){
if(i<1||i>L.length //判断的范围是否有效
returnfalse;
e=L.data[i-1]; //将被删除的元素赋值给e
for(intj=i;j<L.length;j++) //将第i个位置后的元素前移
L.data[j-1]=L.data[j];
L.length--; //线性表长度减1
return true;
}
intmain(){
SqListL; //声明一个顺序表
InitList(L); //初始化顺序表
//.·,此处省略一些代码，插入几个元素
inte=-1; //用变量e把删除的元素"带回来"
if (ListDelete(L,3,e))
printf("已删除第3个元素，删除元素值为=%d\n",e);
else
printf("位序i不合法，删除失败\n");
return0;
}
2.1 删除操作的时间复杂度
L.data[j-1]=L.data[j];
关注最深层循环语句的执行次数与问题规模n的关系
问题规模n=L.length(表长)
最好情况：删除表尾元素，不需要移动其他元素i=n，循环0次；最好时间复杂度=O(1)
最坏情况：删除表头元素，需要将后续的-1个元素全都向前移动i=1,循环n-1次；最坏时间复杂度=O(n);
平均情况：假设删除任何一个元素的概率相同，即i=12,3,...,length的概率都是p=1/ni=1,循环n-1次；i=2时，循环n-2次；i=3,循环n-3次i=n时，循环0次
Summary:
习题:
选择
1.下述(A)是顺序存储结构的优点。A.存储密度大B.插入运算方便C.删除运算方便D.方便地运用于各种逻辑结构的存储表示
顺序表不像链表那样要在结点中存放指针域，因此存储密度较大，A正确。B和C是链表的优点。D是错误的，比如对于树形结构，顺序表显然不如链表表示起来方便。
2.线性表的顺序存储结构是一种(A).A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.散列存取的存储结构
本题易误选B。注意，存取方式是指读写方式。顺序表是一种支持随机存取的存储结构，根据起始地址加上元素的序号，可以很方便地访问任意一个元素，这就是随机存取的概念。
3.一个顺序表所占用的存储空间大小与（B)无关。A.表的长度B.元素的存放顺序C.元素的类型D.元素中各字段的类型
顺序表所占的存储空间=表长×sizeof（元素的类型)，元素的类型显然会影响存储空间的大小。对于同一元素类型的顺序表，表越长，所占存储空间就越大。
4.若线性表最常用的操作是存取第个元素及其前驱和后继元素的值，为了提高效率，应采用（D)的存储方式。A.单链表B.双向链表C.单循环链表D.顺序表
题干实际要求能最快存取第i一1、i和i+1个元素值。A、B、C都只能从头结点依次顺序查找，时间复杂度为O(n):只有顺序表可以按序号随机存取，时间复杂度为O(1)。
5.一个线性表最常用的操作是存取任一指定序号的元素并在最后进行插入、删除操作，则利用（A)存储方式可以节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表
只有顺序表可以按序号随机存取，且在最后进行插入和删除操作时不需要移动任何元素。
6.在n个元素的线性表的数组表示中，时间复杂度为O(1)的操作是(C)I.访问第i（1≤i≤n)个结，点和求第i（2≤i≤n)个结点的直接前驱II.在最后一个结，点后插入一个新的结点III.删除第1个结点IV.在第i(1≤i≤n)个结点后插入一个结点A.IB.II、IIIC.I、IID.I、II、III
I解析略;II中，在最后位置插入新结点不需要移动元素，时间复杂度为O(1)；III中，被删结点后的结点需依次前移，时间复杂度为O(n):IV中，需要后移n一i个结点，时间复杂度为O(n)。
7.设线性表有”个元素，严格说来，以下操作中，(C)在顺序表上实现要比在链表上实现的效率高。I.揄出第i(1≤i≤n)个元素值II.交换第3个元素与第4个元素的值III.顺序输出这n个元素的值A.IB.I、IIIC.I、IID.II、III
对于Ⅱ，顺序表仅需3次交换操作；链表则需要分别找到两个结点前驱，第4个结点断链后再插入到第2个结点后，效率较低。对于III，需依次顺序访问每个元素，时间复杂度相同。
8.在一个长度为n的顺序表中删除第i(1≤i≤n)个元素时，需向前移动(C)个元素.A.nB.i-1C.n-iD.n-i+i
需要将a_I+1~a_n元素前移一位，共移动n一(i+1)+1=n-i个元素。
9.对于顺序表，访问第个位置的元素和在第1个位置插入一个元素的时问复杂度为（C)。A.O(n),O(n)B.O(n),O(1)C.O(1),0(n)D.O(1),O(1)
在第i个位置插入一个元素，需要移动n一i+1个元素，时间复杂度为O(n)。
10.若长度为的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，则i的合法值应该是（B)A.l≤i≤nB.1≤i≤n+1C.0≤i≤n-lD.0≤i≤n
线性表元素的序号是从1开始，而在第n+1个位置插入相当于在表尾追加。
11.顺序表的插入算法中，当n个空间已满时，可再中请增加分配m个空间，若中请失败，则说明系统没有(D）可分配的存储空间。A.m个B.m个连续C.n+m个D.n+m个连续
顺序存储需要连续的存储空间，在申请时需申请n+m个连续的存储空间，然后将线性表原来的n个元素复制到新申请的n+m个连续的存储空间的前n个单元。
简答
1.从顺序表中删除具有最小值的元素（假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
算法思想：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。
boolDel_Min(sqList&L,ElemType&value){
//删除顺序表L中最小值元素结点，并通过引用型参数value返回其值
//若删除成功，则返回true:否则返回false
if(L.length==0)
returnfalse; //表空，中止操作返回
value=L.data[0];
intpos=0; //假定0号元素的值最小
for(inti=1;i<L.length;i++)
//循环，寻找具有最小值的元素
if(L.data[i]<value){
//让value记忆当前具有最小值的元素
value=L.data[i];
pos=i;
}
L.data(pos]=L.data[L.length-1];
//空出的位置由最后一个元素填补
L.length--;
returntrue; //此时，va1ue即为最小值
}
注意：本题也可用函数返回值返回，两者的区别是：函数返回值只能返回一个值，而参数返回（引用传参)可以返回多个值。
2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。
算法思想：扫描顺序表L的前半部分元素，对于元素L.datai,将其与后半部分的对应元素L.data[L.length-i-1]进行交换。
voidReverse(Sqlist&L){
Elemtypetemp; //辅助变量
for(i=0;i<L.length/2;i++){
temp=L.data [i]; //交换L.data[i]与L.data[L.length-i-1]
L.data[i]=L.data[L.length-i-1];
L.data[L.length-i-1]=temp;
}
}
3.对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
解法一：
用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数），边扫描L边统计k,并将不等于x的元素向前移动k个位置，最后修改L的长度。
voiddel_x_1(Sqlist&L,Elemtypex){
//本算法实现删除顺序表工中所有值为×的数据元素
intk=0; //记录值不等于×的元素个数
for(i=0;i<L.length;i++)
if(L.data.[i]！=x)f
L.data[k]=L.data[i];
k++; //不等于×的元素增1
}
L.length=k; //顺序表工的长度等于k
}
解法二：
用k记录顺序表L中等于x的元素个数，边扫描L边统计k,并将不等于x的元素前移k个位置，最后修改L的长度。
voiddel_x_2(Sqlist&L,Elemtypex)(
intk=0,i=0; //k记录值等于×的元素个数
while(i<L.1ength){
if(L.data[i]==x)
k++;
else
L.data[i-k]=L.data[i];//当前元素前移k个位置
i++;
}
L.length=L.length-k; //颗序表L的长度递减
}
此外，本题还可以考虑设头、尾两个指针(i=1,j=n),从两端向中间移动，在遇到最左端值x的元素时，直接将最右端值非x的元素左移至值为x的数据元素位置，直到两指针相遇。但这种方法会改变原表中元素的相对位置。
4.从有序顺序表中删除其值在给定值s与t之间（要求s<t)的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
注意：本题与上一题存在区别。因为是有序表，所以删除的元素必然是相连的整体。 算法思想：先寻找值大于等于5的第一个元素（第一个删除的元素），然后寻找值大于1的第一个元素（最后一个删除的元素的下一个元素），要将这段元素删除，只需直接将后面的元素前移。
boolDel_s_t2(SqList&L,ElemType.s,ElemTypet){
//删除有序顺序表L中值在给定值s与飞之间的所有元素
inti,j;
if (s>=t||L.length==0)
returnfalse;
for(i=0:i<L.length&&L.data[i]<s;i++); //寻找值大于等于s的第一个元素
if(i>=L.length)
returnfalse; //所有元素值均小于s,返回
for(j=i;j<L.length&&L.data[j]<=t;j++); //寻找值大于t的第一个元素
for (;j<L.length;i++,j++)
L.data[i]=L.data[j]; //前移，填补被删元素位置
L.length=i;
returntrue;
}
5.从顺序表中删除其值在给定值s与1之间（包含s和t,要求s<t)的所有元素，若S或t不合理或顺序表为空，则显示出错信息并退出运行。
算法思想：从前向后扫描顺序表L,用k记录下元素值在s到t之间元素的个数（初始时k=0)。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置：否则执行k++。由于这样每个不在s到t之间的元素仅移动一次，因此算法效率高。
boolDel_s_t(SqList&L,ElemTypes,ElemTypet){
//删除顺序表L中值在给定值s与七（要求s<t)之间的所有元素
inti,k=0;
if(L.length==0||s>=t)
returnfalse; //线性表为空或s、七不合法，返回
for(i=0;i<L.length;i++)(
if(L.data〔i]>=s&&L.data[i]<=t)
k++;
else
L.data[i-k]=L.data[i]; //当前元紫前移k个位置
}//for
L.length-=k; //长度减小
returntrue;
}
注意：本题也可从后向前扫描顺序表，.每遇到一个值在s到t之间的元素，则删除该元素，其后的所有元素全部前移。但移动次数远大于前者，效率不够高。
6.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
算法思想：注意是有序顺序表，值相同的元一定在连续的位置上，用类似于直接插入排序的思想，初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，若相同，则继续向后判断，若不同，则插入前面的非重复有序表的最后，直至判断到表尾为止。
boolDelete_Same(SeqList&L){
if(L,length==0）
returnfalse;
inti,j; //i存储第-一个不相同的元素，方为工作指针
for(i=0,j=1;<L.length;j++)
if(L.data[i]!=L.data(j]) //查找下一个与上个元素值不同的元紫
L.data[++i]Ldata[j]; //找到后，将元紫前移
L.length=i+1;
returntrue;
}
对于本题的算法，请读者用序列1,2,2,2,2,3,3,3,4,4,5来手动模拟算法的执行过程，在模拟过程中要标注i和j所指示的元素。
7.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
算法思想：首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。
boolMerge(SeqListA,SeqListB,SeqList&C){
//将有序顺序表A与B合并为一个新的有序顺序表C
if(A.length+B.length>C.maxsize)//大于顺序表的最大长度
returnfalse;
inti=0,j=0,k=0:
while(i<A.length&&j<B.length){ //循环，两两比较，小者存入结果表
if(A.data[i]<=B.data[j])
C.data[k++]=A.data [i++];
else
C.data[k++]=B.data[j++];
}
while(i<A.length) //还剩一个没有比较完的顺序表
C.data[k++]=A.data[i++];
while(j<B.length)
C.data[k++]=B.data[j++];
C.length=k;
returntrue;
}
注意：本算法的方法非常典型，需牢固掌握。
网络异常，图片无法展示|
网络异常，图片无法展示|
typedefintDataType;
voidReverse(DataTypeA[],intleft,intright,intarraysize){
//逆转(a1eft,aleft+1,aleft+2…,aright)为(aright,aright-1,…,a1eft)
if(left>=right||right>=arraySize)
return;
intmid=(left+right)/2;
for(inti=0;i<=mid-left;i++)(
Datatypetemp=A[left+i];
A[left+i]=A[right-i];
A[right-i]=temp;;
voidExchange(DataTypeA[],intm,intn,intarraysize)[
/*数组A[m+n]中，从0到m-1存放顺序表(al,a2,a3,....,am),从m到m+n-1存放顺序表
(b1,b2,b3,...,bn),算法将这两个表的位置互换*/
Reverse(A,0,m+n-1,arraySize);
Reverse(A,0,n-1,arraySize);
Reverse(A,n,m+n-1,arraySize);
}
网络异常，图片无法展示|算法思想：顺序存储的线性表递增有序，可以顺序查找，也可以折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找法。
voidSearchExchangeInsert (ElemTypeA[],ElemTypex)(
intlow=0,high=n-1,mid; //1ow和high指向顺序表下界和上界的下标
while(low<=high){
mid=(low+high)/2; //找中间位置
if(A[mid]==x) break; //找到x,退出whi1e循环
elseif(A[mid]<x) 1ow=mid+1;//到中点mid的右半部去查
elsehigh=mid-1; //到中点mid的左半部去查
} //下面两个iE语句只会执行一个
if (A[mid]==x&&mid!=n-1){//若最后一个元素与×相等，则不存在与其后继交换的操作
t=A[mid];A[mid]=A(mid+1];A[mid+1]=t;
}
if(1ow>high){ //查找失败，插入数据元素×
for(i=n-1;i>high;i--) A[i+1]=A[i]; //后移元素
A[i+1]=x; //插入x
} //结束插入
}
本题的算法也可写成三个函数：查找函数、交换后继函数与插入函数。写成三个函数的优点是逻辑清晰、易读。
网络异常，图片无法展示|
网络异常，图片无法展示|
网络异常，图片无法展示|
网络异常，图片无法展示|另解，借助辅助数组来实现。算法思想：创建大小为p的辅助数组S,将R中p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为O(),空间复杂度为Op)。
四.顺序表的基本操作
1.按位查找
GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
#define MaxSize 10 //定义最大长度
typedefstruct{
ElemTypedata[MaxSize]; //用静态的“数组”存放数据元素
intlength; //顺序表的当前长度
}SeqList; //顺序表的类型定义（静态分配方式）
ElemTypeGetElem(SqListL,inti){
returnL.data[i-1];
}
#define InitSize 10 //顺序表的初始长度
typedefstruct{
ElemType*data; //指示动态分配数组的指针
intMaxSize; //顺序表的最大容量
intlength; //顺序表的当前长度
}SeqList; //顺序表的类型定义（动态分配方式）
ElemTypeGetElem(SqListL,inti){
returnL.data[i-1];
}
1.1时间复杂度
O(1)
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第ⅰ个元素一一“随机存取”特性
2.按值查找
LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。
#define InitSize 10 //顺序表的初始长度
typedefstruct{
ElemType*data; //指示动态分配数组的指针
intMaxSize; //顺序表的最大容量
intlength; //顺序表的当前长度
}SeqList; //顺序表的类型定义（动态分配方式）
//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
intLocateElem(SeqListL,ElemTypee){
for(inti=0;i<L.length;i++)
if(L.data [i]==e)
returni+1; //数组下标为i的元素值等于e,返回其位序i+1
return 0; //退出循环，说明查找失败
}
2.1结构类型的比较
typedefstruct{
intnum;
intpeople;
}Customer;
voidtest (){
Customera;
a.num1;
a.people1;
Customerb;
b.num1;
b.people1;
if(a≡=b){ //Invalid operands to binary expression ('Customer'and 'Customer')
printf("相等")；
}else{
printf("不相等")；
}
}
if (a.num==b.num&a.people=b.people){
printf("相等")；
}else{
printf("不相等")；
}
//需要依次对比各个分量来
//判断两个结构体是否相等
2.2时间复杂度
if(L.data [i]==e)
关注最深层循环语句的执行次数与问题规模n的关系
问题规模n=L.length(表长)
最好情况：目标元素在表头循环1次；最好时间复杂度=0(1)最坏情况：目标元素在表尾循环n次；最坏时间复杂度=O(0:
平均情况：假设目标元素出现在任何一个位置的概率相同，都是1/n目标元素在第1位，循环1次：在第2位，循环2次；…；在第n位循环n次
Summary:
