一、顺序表定义线性表顺序存储
typedef struct {
int data[MaxSize];
int length;
}SqList;
二、顺序表题目及代码
1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
bool search_min(SqList &L,int &e){
if(L.length==0)
return false;
int min,k=0;
min=L.data[0];
for (int i = 1; i
if(min>L.data[i]){
min=L.data[i];
k++;
}
}
e=min;
L.data[k]=L.data[L.length-1];
return true;
}
2.设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为 O(1)。
void Reverse(SqList &L){
int temp,mid=L.length/2;
for (int i = 0; i <=mid; ++i) {
temp=L.data[L.length-1-i];
L.data[L.length-1-i]=L.data[i];
L.data[i]=temp;
}
}
3.对长度为n 的顺序表 L，编写一个时间复杂度为 O(n)、空间复杂度为 O(1)的算法，该算法删除线性表中所有值为x的数据元素。
void Delete_x(SqList &L,int x){
int k=0;
for (int i = 0; i < L.length; ++i) {
if(L.data[i]!=x)
L.data[k++]=L.data[i];
}
L.length=k;
}
4.从有序顺序表中删除其值在给定值 s与 t之间（要求 s/ * 算法思想：新增一个空数组，顺序表中的每个数与新数组的最后一个数作比较，若不相等赋值到新的空数组中，直到遍历到最后一个数
* 再把新的数组的值复制到顺序表中
*/
void Delete_Re(SqList &L){
int b[MaxSize];
int k=0;
b[0]=L.data[0];
for (int i = 1; i < L.length; ++i) {
if(b[k]!=L.data[i]){
b[++k]=L.data[i];
}
}
for (int j = 0; j <=k; ++j) {
L.data[j]=b[j];
}
L.length=k+1;
}
6.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
SqList merge0(SqList M,SqList N){
SqList a;
int i=0,j=0,k=0;
while (i
if (M.data[i]>=N.data[j]){
a.data[k++]=N.data[j++];
} else{
a.data[k++]=M.data[i++];
}
}
while (i
a.data[k++]=M.data[i++];
}
while (j
a.data[k++]=N.data[j++];
}
a.length=k;
return a;
}
7.已知在一维数组 A[m + n]中依次存放两个线性表(a1,a2, …,am)和(b1, b2, b3,…, bn)。编写一个函数，将数组中两个顺序表的位置互换，即将(b1, b2, b3,…, bn)放在(a1,a2, …,am)的前面。
void reverse1(SqList &L,int left,int right){
int mid=(left+right)/2+1;
int temp;
for (int i = left; i < mid; ++i) {
temp=L.data[right+left-i];
L.data[right+left-i]=L.data[i];
L.data[i]=temp;
}
}
void reverse2(SqList &L,int m,int n){
reverse1(L,0,m-1);
reverse1(L,m,m+n-1);
reverse1(L,0,m+n-1);
}
8.线性表(a1,a2, a3,…,an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。
void findx(SqList &L,int x){
int low=0,high=L.length-1,mid;
while (low
mid=(low+high)/2;
if(L.data[mid]==x){
int temp;
temp=L.data[mid+1];
L.data[mid+1]=L.data[mid];
L.data[mid]=temp;
break;
}else if(L.data[mid]>x){
high=mid-1;
} else{
low=mid+1;
}
}
if (low>=high){
L.length++;
int i;
for ( i = L.length; i >low; --i) {
L.data[i]=L.data[i-1];
}
L.data[low]=x;
}
}
9.一个长度为 L(L≥ 1)的升序序列 S，处在第[L/2]个位置的数称为 S的中位数。例如，若序列 S1=(11,13,15,17,19)。则S的中位数是 15，两个序列的中位数是含它们所有元素的升度序列的中位数。例如，若S2=（2,4,6,8,20)，则 S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A和B的中位数。【2011统考真题】
int find_mid(SqList M,SqList N){
int i=0,j=0,k=0,value;
while (k!=M.length){
k++;
if(M.data[i]
value=M.data[i];
i++;
} else{
value=N.data[j];
j++;
}
}
return value;
}
11.已知一个整数序列A=(a1,a2,…,an-1)，其中 0≤ai
int find_int(SqList L){
int max=L.data[0];
for (int i = 0; i < L.length; ++i) {
if (max < L.data[i]) {
max=L.data[i];
}
}
printf("max is %dn",max);
int *count=(int *) malloc(sizeof (int)*(max+2));
for (int i = 0; i < max+2; ++i) {
count[i]=0;
}
for (int i = 0; i < max+2; ++i) {
if(L.data[i]>0){
count[L.data[i]]=1;
}
}
int i;
for (i=1; i < max+2; ++i) {
if (count[i]==0){
return i;
}
}
return 0;
}
13.定义三元组(a,b,c)(a、b、c均为正数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2和S3按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)(aES1，bES2，cES3)中的最小距离。例如S={-1,0,9}，S2{-25,-10,10,11}，S={2,9,17,30,41}，则最小距离为2，相应的三元组为(9,10,9)。【2020统考真题】
int abs(int a){
if(a<0){
a=-a;
}
return a;
}
int distance_min(SqList L,SqList J,SqList I){
int a=0,b=0,c=0;
for (int i = 0; i < L.length; ++i) {
if (L.data[i] > 0) {
a++;
}
}
for (int j = 0; j
if(J.data[j]>0){
b++;
}
}
for (int f = 0; f
if(I.data[f]>0){
c++;
}
}
int d=a*b*c;
SqList ax;
int p=0;
ax.length=d;
for (int i = 0; i < ax.length; ++i) {
ax.data[i]=0;
}
for (int i = 0; i < L.length; ++i) {
if(L.data[i]>0){
for (int j = 0; j < J.length; ++j) {
if (J.data[j]>0){
for (int k = 0; k < I.length; ++k) {
ax.data[p++]= abs(L.data[i]-J.data[j])+ abs(L.data[i]-I.data[k])+ abs(J.data[j]-I.data[k]);
}
}
}
}
}
int min=ax.data[0];
for (int i = 0; i < ax.length; ++i) {
if(min>ax.data[i]){
min=ax.data[i];
}
}
return min;
}
三、递归
1、递归逆向输出顺序表
void f2(SqList L,int n){
if (n
f2(L,n+1);
}
printf("%d",L.data[n]);
return;
}
2、递归正向输出顺序表
int f3(SqList L,int n){
if (n==L.length){
return -1;
}
printf("%d",L.data[n]);
return f3(L,n=n+1);
}
3、递归二分查找法
int DG_two(SqList L,int x,int low,int high){
int mid=(low+high)/2;
if (L.data[mid]==x || low>high){
return mid;
}
if (x
high=mid;
} else low=mid;
return DG_two(L,x,low,high);
}
总结
以上就是今天的所有内容
