鱼C论坛

 找回密码
 立即注册
查看: 1160|回复: 1

哪位大佬可以帮忙改改这代码的问题呢?

[复制链接]
发表于 2023-11-2 19:42:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>


#define VOLUME 255

typedef struct HString
{
        char* ch;   //指向字符串所在空间地址
        int   length; //记录字符串长度
}HString;

//初始化字符结构
void InitString(HString* S)
{
        S->ch = NULL;
        S->length = 0;
}

//赋值:将字符串str赋给字符结构T
void StrAssign(HString* T, char* str) {
        int i, j, len;
        char* c;
        if (str != NULL) {
                if (T->ch)
                {
                        free(T->ch);  //释放T原有的空间
                }

                for (len = 0; str[len] != '\0'; len++)
                {
                        continue;
                }

                if (!len) {
                        T->ch = NULL;
                        T->length = 0;
                }
                else {
                        T->ch = (char*)malloc((len + 1) * sizeof(char)); // 为null终止符分配空间
                        if (T->ch == NULL) {
                                exit(-1);
                        }
                }

                for (j = 0; j < len; j++) {
                        T->ch[j] = str[j];//分配成功后,将str中的字符逐个赋给T
                }
                T->length = len;//记录此时T的长度
        }
}

//获取next数组
void get_next(HString* T, int* next)
{
        int j = 0;
        int i = 1;
        next[1] = 0;

        while (i < T->length)
        {
                if (0 == j || T->ch[i] == T->ch[j])
                {
                        i++;
                        j++;
                        if (T->ch[i] != T->ch[j])
                        {
                                next[i] = j;
                        }
                        else
                        {
                                next[i] = next[j];
                        }
                }
                else
                {
                        j = next[j];
                }
        }
}

// 返回子串T在主串S第pos个字符之后的位置
// 若不存在,则返回-1
int Index_KMP(HString* S, HString* T, int pos)
{
        int i = pos;
        int j = 1;
        int *next;

        next = (int*)malloc(sizeof(int) * VOLUME);  //动态分配next数组
        get_next(T, next);

        while (i <= S->length && j <= T->length)
        {
                if (i <= S->length && (0 == j || S->ch[i] == T->ch[j]))
                {
                        i++;
                        j++;
                        if (T->ch[i] != T->ch[j])
                        {
                                next[i] = j;
                        }
                        else
                        {
                                next[i] = next[j];
                        }
                }
                else
                {
                        j = next[j];
                }
        }
        
        if (j > T->length)
        {
                return i - T->length + 1;
        }
        else
        {
                return -1;
        }
        free(next);
}

int StrCompare(HString *S, HString *T) {
        int i;
        for (i = 0; i < S->length && i < T->length; i++) 
        {
                if (S->ch[i] != T->ch[i])
                {
                        return S->ch[i] - T->ch[i];
                }
        }
        return  S->length - T->length;
}

int ClearString(HString* S) {
        if (S->ch)
        {
                free(S->ch);
                S->ch = NULL;
        }
        S->length = 0;
        return 0;
}

int main(int argc, char* argv[])
{
        HString input, keyword;
        InitString(&input);
        InitString(&keyword);
        
        if (argc != 3)
        {
                printf("ERROR_01");
                exit(-1);
        }

        StrAssign(&input, argv[1]);
        StrAssign(&keyword, argv[2]);

        printf("%d",Index_KMP(&input, &keyword, 0));
        ClearString(&input);
        ClearString(&keyword);
        
        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-11-2 19:43:29 | 显示全部楼层
这段代码存在以下问题:

1. 在函数 get_next 中,没有对 next 数组进行初始化。应该在函数开始时将 next[0] 初始化为-1。

2. 在函数 Index_KMP 中,动态分配的 next 数组没有在函数结束时释放。应该将 free(next) 放在 return 语句之前。

3. 在函数 StrCompare 中,当字符串长度不相等时,返回的是 S->length - T->length ,这可能导致溢出。应该返回 S->length - T->length 的符号。

4. 在函数 ClearString 中,没有释放 S->ch 指向的内存空间。应该在释放之后将 S->ch 指向 NULL 。

下面是修改后的代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define VOLUME 255

typedef struct HString
{
    char* ch;   //指向字符串所在空间地址
    int   length; //记录字符串长度
}HString;

//初始化字符结构
void InitString(HString* S)
{
    S->ch = NULL;
    S->length = 0;
}

//赋值:将字符串str赋给字符结构T
void StrAssign(HString* T, char* str) {
    int i, j, len;
    char* c;
    if (str != NULL) {
        if (T->ch)
        {
            free(T->ch);  //释放T原有的空间
        }

        for (len = 0; str[len] != '\0'; len++)
        {
            continue;
        }

        if (!len) {
            T->ch = NULL;
            T->length = 0;
        }
        else {
            T->ch = (char*)malloc((len + 1) * sizeof(char)); // 为null终止符分配空间
            if (T->ch == NULL) {
                exit(-1);
            }
        }

        for (j = 0; j < len; j++) {
            T->ch[j] = str[j];//分配成功后,将str中的字符逐个赋给T
        }
        T->ch[j] = '\0'; // 添加字符串结束符
        T->length = len;//记录此时T的长度
    }
}

//获取next数组
void get_next(HString* T, int* next)
{
    int j = 0;
    int i = 1;
    next[0] = -1; // 初始化next数组

    while (i < T->length)
    {
        if (j == -1 || T->ch[ i] == T->ch[j])
        {
            i++;
            j++;
            if (T->ch[ i] != T->ch[j])
            {
                next[ i] = j;
            }
            else
            {
                next[ i] = next[j];
            }
        }
        else
        {
            j = next[j];
        }
    }
}

// 返回子串T在主串S第pos个字符之后的位置
// 若不存在,则返回-1
int Index_KMP(HString* S, HString* T, int pos)
{
    int i = pos;
    int j = 0;
    int* next;

    next = (int*)malloc(sizeof(int) * VOLUME);  //动态分配next数组
    get_next(T, next);

    while (i < S->length && j < T->length)
    {
        if (j == -1 || S->ch[ i] == T->ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }

    free(next);

    if (j >= T->length)
    {
        return i - T->length;
    }
    else
    {
        return -1;
    }
}

int StrCompare(HString* S, HString* T) {
    int i;
    for (i = 0; i < S->length && i < T->length; i++)
    {
        if (S->ch[ i] != T->ch[ i])
        {
            return (S->ch[ i] > T->ch[ i]) ? 1 : -1;
        }
    }
    return (S->length > T->length) ? 1 : ((S->length < T->length) ? -1 : 0);
}

int ClearString(HString* S) {
    if (S->ch)
    {
        free(S->ch);
        S->ch = NULL;
    }
    S->length = 0;
    return 0;
}

int main(int argc, char* argv[])
{
    HString input, keyword;
    InitString(&input);
    InitString(&keyword);

    if (argc != 3)
    {
        printf("ERROR_01");
        exit(-1);
    }

    StrAssign(&input, argv[1]);
    StrAssign(&keyword, argv[2]);

    printf("%d", Index_KMP(&input, &keyword, 0));
    ClearString(&input);
    ClearString(&keyword);

    return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 08:08

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表