c - 在数组中找到第一个伪回文

标签 c binary-search palindrome

我有一个字符串数组,我想为每个字符串(如果有的话)找到数组中的第一个伪回文。所以我决定首先对我的数组进行排序,然后反转单词并进行二进制搜索以查找反转的单词。所以这就是我到目前为止所拥有的:

#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/

相关文章:

c - 消息队列多接收者实现

c - 双后增量的结果 - 在 if 语句及其主体中

javascript - 在javascript中实现二分查找

algorithm - 具有重复项的旋转排序数组中的最小值

c++ - 找到下一个回文

c - C语言中的gets()接受参数

c - Doxygen 中的所见即所得

java - 在行大小不固定的 UTF-8 编码文本文件上使用 Java 进行二进制搜索

c - 如何判断一个数是不是回文?

java - 数字回文代码不起作用