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++ - binary_search 与 std::pair 使用自定义运算符

C++在while循环中更改变量

algorithm - 使用最少的插入将字符串转换为回文字符串

c++ - 禁用 USB 内存棒的存储功能并自动启动程序

c - 匹配什么样的括号括住字符串并将其删除

c - 为什么我的 C 程序在使用 floor 和 ceil 以及舍入函数时意外终止?

java - 二进制搜索 O(log n) 算法在顺序列表中查找重复项?

java - 练习使用二进制搜索将数据插入数组,问题很少

javascript - 用javascript匹配回文中的单个字符?

c - 变量意外更改值