求助实现generateString函数：生成严格介于par1与par2间的字符串

Great question—generating a string that falls strictly between two arbitrary strings (with your given constraints) does have some tricky edge cases to work through, but let's break this down step by step with a practical, robust implementation.

First: Validate Input & Check Feasibility #

Before we start generating strings, we need to confirm a valid result can exist:

• If strcmp(par1, par2) >= 0, there’s no way to have a string strictly greater than par1 and strictly less than par2—return NULL immediately in this case.
• Even when par1 < par2, some edge cases leave no room for an intermediate string (e.g., par1 = "z" where SUP='z', par2 = "za"). We’ll handle these scenarios with fallback logic to avoid infinite loops.

Key Rules to Remember (strcmp Behavior) #

To generate valid strings, keep these strcmp rules top of mind:

• Strings are compared character-by-character until a mismatch is found. The string with the higher ASCII value at the first mismatch is larger.
• If one string is a prefix of the other, the shorter string is smaller. For example: "ab" < "abc" and "abd" > "abc".

Generation Strategy #

We’ll use a hybrid approach:

1. Random Candidate First: Generate random strings of random lengths (0 to MAX) and check if they fit the criteria. This is fast for most cases.
2. Deterministic Fallback: If random generation fails after a reasonable number of tries, construct a valid string manually to avoid infinite loops.

Example Implementation #

First, define your constants (adjust these to match your actual MAX, INF, and SUP values):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_LENGTH 100
#define INF_CHAR 'a'   // Replace with your actual INF value
#define SUP_CHAR 'z'   // Replace with your actual SUP value
#define MAX_RETRIES 1000  // Number of random attempts before fallback

Helper Functions #

These functions handle deterministic string construction for edge cases:

// Generate a random character within [INF_CHAR, SUP_CHAR]
char get_random_char() {
    return INF_CHAR + (rand() % (SUP_CHAR - INF_CHAR + 1));
}

// Build a string of length `len` that's strictly greater than `par`
char* make_greater_than(const char* par, int len) {
    int par_len = strlen(par);
    char* res = malloc(len + 1);
    if (!res) return NULL;

    // Copy characters from par until we can increment one without exceeding SUP_CHAR
    int i;
    for (i = 0; i < len && i < par_len; i++) {
        res[i] = par[i];
        if (res[i] < SUP_CHAR) {
            res[i]++;
            // Fill the rest with random valid characters
            for (int j = i + 1; j < len; j++) {
                res[j] = get_random_char();
            }
            res[len] = '\0';
            return res;
        }
    }

    // If we need a longer string than par, extend with INF_CHAR (smallest valid)
    if (len > par_len) {
        strncpy(res, par, par_len);
        for (int j = par_len; j < len; j++) {
            res[j] = INF_CHAR;
        }
        res[len] = '\0';
        return res;
    }

    // No valid string of this length exists
    free(res);
    return NULL;
}

// Build a string of length `len` that's strictly less than `par`
char* make_less_than(const char* par, int len) {
    int par_len = strlen(par);
    char* res = malloc(len + 1);
    if (!res) return NULL;

    // Copy characters from par until we can decrement one without dropping below INF_CHAR
    int i;
    for (i = 0; i < len && i < par_len; i++) {
        res[i] = par[i];
        if (res[i] > INF_CHAR) {
            res[i]--;
            // Fill the rest with random valid characters
            for (int j = i + 1; j < len; j++) {
                res[j] = get_random_char();
            }
            res[len] = '\0';
            return res;
        }
    }

    // A shorter prefix of par is automatically smaller
    if (len < par_len) {
        strncpy(res, par, len);
        res[len] = '\0';
        return res;
    }

    // No valid string of this length exists
    free(res);
    return NULL;
}

Main Function #

char *generateString(char *par1, char *par2) {
    // Initialize random seed once (move this to your program's startup if called multiple times)
    static int seed_initialized = 0;
    if (!seed_initialized) {
        srand(time(NULL));
        seed_initialized = 1;
    }

    // Quick check: if par1 is not smaller than par2, return NULL
    if (strcmp(par1, par2) >= 0) {
        return NULL;
    }

    // First try random candidates
    for (int retry = 0; retry < MAX_RETRIES; retry++) {
        int len = rand() % (MAX_LENGTH + 1);
        char* candidate = malloc(len + 1);
        if (!candidate) continue;

        // Fill candidate with random valid characters
        for (int i = 0; i < len; i++) {
            candidate[i] = get_random_char();
        }
        candidate[len] = '\0';

        // Check if candidate fits the criteria
        if (strcmp(par1, candidate) < 0 && strcmp(candidate, par2) < 0) {
            return candidate;
        }

        free(candidate);
    }

    // Fallback to deterministic construction if random fails
    for (int len = 0; len <= MAX_LENGTH; len++) {
        // Try to make a string greater than par1 and less than par2
        char* candidate = make_greater_than(par1, len);
        if (candidate && strcmp(candidate, par2) < 0) {
            return candidate;
        }
        free(candidate);

        // Try to make a string less than par2 and greater than par1
        candidate = make_less_than(par2, len);
        if (candidate && strcmp(par1, candidate) < 0) {
            return candidate;
        }
        free(candidate);
    }

    // No valid string exists
    return NULL;
}

Important Notes #

• Memory Management: The returned string is allocated with malloc—the caller must free it to avoid memory leaks.
• Empty Strings: The function correctly handles empty input strings (length 0) and cases where no valid intermediate string exists (returns NULL).
• Random Seed: The seed is initialized once inside the function. If you call this function multiple times, move the seed initialization to your program’s startup code to avoid repeated seeding.

内容的提问来源于stack exchange，提问作者Diablo3000