题目
设A= (an,a2, ..,. am)和B= (b, b2, .. b,)均为顺序表,A'和 B'分别是除去最大公共前缀后的子表。例如,A=(b, e, i, j,i, n, g),B=(b,e, i, f, a, n, g),则两者的最大公共前缀为b、e、i,在两个顺序表中除去最大公共前缀后的子表分别为A'= (j, i, n, g), B'=(f,a, n, g)。若A'=B'=空表,则A=B.若A'=空表且B'≠空表,或两者均不为空且A'的第一个元素值小于B'的第一个元素值,则A<B,否则A>B.试编写一个函数,根据上述方法比较A和B的大小。
分析
代码
核心代码:
/* 比较两个去掉最大公共前缀后的顺序表的大小 */
/* A[]指的是A顺序表;An指的是A顺序表的长度; B[]指的是B顺序表;Bn指的是B顺序表的长度 */
int compare(float A[],int An,float B[],int Bn){
/* 过滤掉公共前缀 */
int i=0;
while(i<An&&i<Bn){
if(A[i]==B[i]){
i++;
}else{
break;
}
}
if(i>=An&&i>=Bn){// A和B都空(思路就是下标i大于等于数组中的元素个数)
return 0;
}else if((i>=An&&i<Bn)||A[i]<B[i]){// 如果A空B不空或者除去前缀的A首元素小于B元素
return -1;
}else {// 剩余的情况
return 1;
}
}
完整代码:
#include<stdio.h>
/* 打印顺序表 */
void print(float L[],int m) {
printf("\n");
for(int i=0; i<m; i++) {
printf("%1.f\t",L[i]);
}
printf("\n");
}
/* 比较两个去掉最大公共前缀后的顺序表的大小 */
/* A[]指的是A顺序表;An指的是A顺序表的长度; B[]指的是B顺序表;Bn指的是B顺序表的长度 */
int compare(float A[],int An,float B[],int Bn){
/* 过滤掉公共前缀 */
int i=0;
while(i<An&&i<Bn){
if(A[i]==B[i]){
i++;
}else{
break;
}
}
if(i>=An&&i>=Bn){// A和B都空(思路就是下标i大于等于数组中的元素个数)
return 0;
}else if((i>=An&&i<Bn)||A[i]<B[i]){// 如果A空B不空或者除去前缀的A首元素小于B元素
return -1;
}else {// 剩余的情况
return 1;
}
}
int main() {
float L1[]= {4,3,5,8,2,1,9};
float L2[]= {4,3,6,1,2,3,4};
int l1=7,l2=7;
print(L1,l1);// 打印顺序表
print(L2,l2);// 打印顺序表
int r=compare(L1,l1,L2,l2);
printf("%d",r);
return 0;
}
运行结果如下: