程序一直输出false结果,,

0

运行环境:VS2019(C语言编写)

题目:

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。

示例 1:

输入: "abab"
输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"
输出: False

示例 3:

输入: "abcabcabcabc"
输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/repeated-substring-pattern

/***
判断字符串能否由其子字符串重复构成
***/
#include<stdbool.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct {
    int front;
    int rear;
    char* base;
    int length;
}Squeue;
/**
初始化循环队列
这里申请存储空间的时候需要多申请一个
存储空间作为循环队列判断队列是否已经
满了
**/
Squeue* SqueueInit(int k){
    Squeue* q =(Squeue*)malloc(sizeof(Squeue));
    if (q == NULL) return NULL;
    q->base =(char*)malloc(sizeof(char)*(k+1));
    if (q->base == NULL) return NULL;
    q->front = 0;
    q->rear = 0;
    q->length = k + 1;
    return q;
}
/***
顺序循环队列的入队操作
 判断队列是否已经满了
**/
void Enqueue(Squeue *q,char ch){
    if ((q->rear + 1) % q->length == q->front) return;
    q->base[q->rear] = ch;
    q->rear = (q->rear + 1) % q->length;
}
/**
顺序循环队列的出队操作
  判断队列是否已经为空
***/
char Dequeue(Squeue *q){
    if (q->rear == q->front) return 0;
    char ch = q->base[q->front];
    q->front = (q->front + 1) % q->length;
    return ch;
}
/**
循环队列的销毁
***/
void Destory(Squeue *q){
    free(q->base);
    q->base = NULL;
    free(q);
    q = NULL;
}
/***
判断队列是否已经满了 
 **/
bool QueueIsFull(Squeue *q){
    if ((q->rear + 1) % q->length == q->front) return true;
    return false;
}
/**
判断队列是否为空
***/
bool QueueIsEmpty(Squeue *q){
    return q->front == q->rear ? true : false;
}
/***
实现思路:
    循环顺序队列
    队列刚出队的元素是否与即将入队的元素相同
    相同执行新的一轮判断,不同则直接跳出循环
**/
bool repeatedSubstringPattern(char *s){
    /***
    题目已经说明非空这里不讨论
    **/
    int len = strlen(s);
    for (int i = 1; i < len; i++) {
        Squeue* q = SqueueInit(i);
        int j = 0;
        while (j < len) {
            if (!QueueIsEmpty(q))
            {
                char t = Dequeue(q);
                if (t != s[j]) {
                    break;
                }
            }
            while (!QueueIsFull(q))
            {
                Enqueue(q, s[j]);
                j++;
            }
        }
        if (j == len) {
            return true;
        }
        Destory(q);
    }
    return false;
}
int main() {
    /*s = getchar();
    while (s != '\n') {
        if (s == ' ') {
            putchar(s);
        }
        else 
            putchar(s + 1);
            s = getchar();
    }*/
    printf("输入字符串的大小:\n");
    int L=0;
    scanf_s("%d", &L);
    char* s =(char*)malloc(sizeof(char)*L);
    if (s == NULL) return NULL;
    for (int i = 0; i < L;i++) {
        char ch;
        /**
        这里传入整数1表示每次最多读取一个字符
        **/
        scanf_s("%c", &ch,1);
        s[i] = ch;
    }
    if (repeatedSubstringPattern(s)) {
        printf("这个字符串可以用子串表示!\n");
    }
    else {
        printf("这个字符串不行啊!\n");
    }
    return 0;
}

ava
凤栖梧

2020-11-5

问题已经解决了,问题是主函数传入字符串的方式不对,导致出错了。 -  凤栖梧  2020-11-25
0

只是判断而已,这个题目不需要用队列吧。

ava
慢羊羊

2020-11-5

可以不用队列的,,,我是想练习使用队列 -  凤栖梧  2020-11-7
技术讨论社区