我有一个字符串数组,我想为每个字符串(如果有的话)找到数组中的第一个伪回文。所以我决定首先对我的数组进行排序,然后反转单词并进行二进制搜索以查找反转的单词。所以这就是我到目前为止所拥有的:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char len(char *x){
char len = 0;
while (*x != '\0'){
x++;
len++;
}
return len;
}
char compare(char *x, char *y){
char x0 = &x;
char y0 = &y;
while (*x != '\0'){
if (tolower(*x) < tolower(*y)) return -1;
if (tolower(*x) > tolower(*y)) return 1;
x++;
y++;
}
// if we are here it means that strings are equal (case insensitive)
x = &x0;
y = &y0;
while (*x != '\0'){
if (*x > *y) return -1;
if (*x < *y) return 1;
x++;
y++;
}
// strings are equal (case sensitive)
return 0;
}
char *reverse(char *x){
int i, j;
char temp, *rev = NULL;
rev = malloc(sizeof(char)*(len(x)+1));
rev = strcpy(rev,x);
i = 0;
j = len(x) - 1;
while (i < j){
temp = rev[i];
rev[i] = x[j];
rev[j] = temp;
i++;
j--;
}
return rev;
}
int binsearch(char *x, char *A, int len){
int l, r, m, index;
l = 0;
r = len - 1;
index = -1;
while (l <= r){
m = (l + r) / 2;
if (compare(x, A[m]) == 0){
index = m;
r = m - 1;
}
else if (compare(x, A[m]) == -1) r = m - 1;
else l = m + 1;
}
return index;
}
int main()
{
int n, i, j, k, fnd;
char T[10000][101], temp[101];
scanf("%d", &n);
for (i = 0; i < n; i++){
scanf("%s", &T[i]);
}
for (i = 1; i < n; i++){
strcpy(temp, T[i]);
j = i - 1;
while (j >= 0 && compare(T[j], temp) == 1){
strcpy(T[j+1], T[j]);
j--;
}
strcpy(T[j+1], temp);
}
for (i = 0; i < n; i++){
fnd = binsearch(reverse(T[i]), T, n);
printf("%d", fnd);
}
return 0;
}
该程序停止执行。问题可能出在二进制搜索上,因为每个函数 before 都执行得很好。但是这个二分查找有什么问题呢?或者还有什么可以破解密码?
最佳答案
是否是导致问题的返回类型.. 对于二分查找,未提及返回类型
编辑 1. 但是你没有在声明中提到函数的返回类型
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
char len(char *x){
char len = 0;
while (*x != '\0'){
x++;
len++;
}
return len;
}
char compare(char *x, char *y){
char* x0 = x;
char* y0 = y;
while (*x != '\0'){
int a0 = tolower(*x);
int b0 = tolower(*y);
if ( a0 < b0)
return -1;
if ( a0 > b0)
return 1;
x++;
y++;
}
// if we are here it means that strings are equal (case insensitive)
x = x0;
y = y0;
while (*x != '\0'){
if (*x > *y) return -1;
if (*x < *y) return 1;
x++;
y++;
}
// strings are equal (case sensitive)
return 0;
}
char *reverse(char *x){
int i, j;
char temp, *rev = NULL;
rev = malloc(sizeof(char)*(len(x)+1));
rev = strcpy(rev,x);
i = 0;
j = len(x) - 1;
while (i < j){
temp = rev[i];
rev[i] = x[j];
rev[j] = temp;
i++;
j--;
}
return rev;
}
int binarysearch(char *x,char A[][101], int len){
int l, r, m, index;
l = 0;
r = len - 1;
index = -1;
while (l <= r){
m = (l + r) / 2;
if (compare(x, A[m]) == 0){
index = m;
r = m - 1;
}
else if (compare(x, A[m]) == -1) r = m - 1;
else l = m + 1;
}
return index;
}
int main()
{
int n, i, j, k, fnd;
char T[10000][101], temp[101];
scanf("%d", &n);
for (i = 0; i < n; i++){
scanf("%s", &T[i]);
}
for (i = 1; i < n; i++){
strcpy(temp, T[i]);
j = i - 1;
while (j >= 0 && compare(T[j], temp) == 1){
strcpy(T[j+1], T[j]);
j--;
}
strcpy(T[j+1], temp);
}
for (i = 0; i < n; i++){
fnd = binarysearch(reverse(T[i]), T, n);
printf("%d", fnd);
}
return 0;
}
关于c - 在数组中找到第一个伪回文,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47247220/