设定串采用顺序存储结构，写出对串s1和串s2比较大小的算法。串值大小按字典排序（升序）方式，返回值等于-1，0和1分别表示s1<s2，s1=s2和s1>s2。

1. 算法思路：

（1）比较两串的长度，取较短的串长度作为循环次数。

（2）按照字典序逐个比较两串相应位置的字符，如果相等则继续比较下一位；如果不相等，则直接返回比较结果。

（3）如果循环结束，两串前面的部分字符全部相等，则返回长度更短的串为小。

（4）如果两串长度相等，且所有字符都相等，则返回0。

2. 算法实现：

int compare(char s1[], char s2[]) {
    int i = 0;
    while (s1[i] && s2[i]) {
        if (s1[i] == s2[i]) {
            i++;
        } else {
            return s1[i] < s2[i] ? -1 : 1;
        }
    }
    if (!s1[i] && !s2[i]) {
        return 0;
    } else {
        return s1[i] ? 1 : -1;
    }
}

3. 算法分析：

（1）时间复杂度：O(min(len(s1), len(s2)))。

（2）空间复杂度：O(1)。

相关问题

用数据结构知识生成代码（已知任意字符串S1和S2，在串的顺序存储结构上实现S1和S2的比较运算，并返回比较结果）

在串的顺序存储结构上实现S1和S2的比较运算，可以使用以下数据结构和算法：

1. 定义一个数组来存储S1和S2，数组的每个元素是一个字符。
2. 使用strlen函数获取S1和S2的长度len1和len2。
3. 使用循环遍历数组，比较对应位置上的字符。如果有不同的字符，则直接返回它们的大小关系；如果前缀相同，则比较它们的长度。如果S1和S2长度相等，则它们相等；否则，长度较长的串大。

以下是使用C语言实现上述算法的代码：

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

// 定义串的最大长度
#define MAX_LEN 100

// 定义比较结果的枚举类型
enum CompareResult {
    LESS_THAN = -1,
    EQUAL = 0,
    GREATER_THAN = 1
};

// 比较字符串S1和S2的大小关系
int compare(char S1[], char S2[]) {
    int len1 = strlen(S1);
    int len2 = strlen(S2);
    int len = len1 < len2 ? len1 : len2;
    for (int i = 0; i < len; i++) {
        if (S1[i] < S2[i]) {
            return LESS_THAN;
        } else if (S1[i] > S2[i]) {
            return GREATER_THAN;
        }
    }
    if (len1 == len2) {
        return EQUAL;
    } else if (len1 < len2) {
        return LESS_THAN;
    } else {
        return GREATER_THAN;
    }
}

int main() {
    // 定义数组存储S1和S2
    char S1[MAX_LEN + 1], S2[MAX_LEN + 1];

    // 读入S1和S2
    printf("请输入S1：");
    scanf("%s", S1);
    printf("请输入S2：");
    scanf("%s", S2);

    // 比较S1和S2
    int result = compare(S1, S2);

    // 输出比较结果
    if (result == LESS_THAN) {
        printf("S1 < S2\n");
    } else if (result == EQUAL) {
        printf("S1 = S2\n");
    } else {
        printf("S1 > S2\n");
    }

    return 0;
}

该程序使用数组来存储S1和S2，并使用strlen函数获取它们的长度。在compare函数中，我们使用循环遍历数组，比较对应位置上的字符。如果有不同的字符，则直接返回它们的大小关系；如果前缀相同，则比较它们的长度。如果S1和S2长度相等，则它们相等；否则，长度较长的串大。最后，程序根据比较结果输出相应的字符串。

1.为字符串分配一个固定长度的存储空间，完成字符串的输入及输出； 2.对字符串进行以下基本操作：字符串连接，字符串比较，字符串定位。 3.已知字符串S采用顺序存储结构，设计一个算法，从S中删除所有与串T相同的子串。 数据类型定义 ： #define Maxlen 50 typedef struct { char ch[Maxlen]; int length; }String;

完整代码如下：

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

#define Maxlen 50

typedef struct {
    char ch[Maxlen];
    int length;
}String;

// 初始化字符串
void initString(String* s, char* str) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        s->ch[i] = str[i];
    }
    s->length = len;
}

// 输出字符串
void printString(String* s) {
    for (int i = 0; i < s->length; i++) {
        printf("%c", s->ch[i]);
    }
    printf("\n");
}

// 字符串连接
void concatString(String* s1, String* s2, String* result) {
    int len1 = s1->length;
    int len2 = s2->length;
    int i;
    for (i = 0; i < len1; i++) {
        result->ch[i] = s1->ch[i];
    }
    for (int j = 0; j < len2; j++, i++) {
        result->ch[i] = s2->ch[j];
    }
    result->length = len1 + len2;
}

// 字符串比较
int compareString(String* s1, String* s2) {
    int len1 = s1->length;
    int len2 = s2->length;
    int minLen = len1 < len2 ? len1 : len2;
    for (int i = 0; i < minLen; i++) {
        if (s1->ch[i] != s2->ch[i]) {
            return s1->ch[i] > s2->ch[i] ? 1 : -1;
        }
    }
    if (len1 == len2) {
        return 0;
    } else {
        return len1 > len2 ? 1 : -1;
    }
}

// 字符串定位
int findString(String* s, String* pattern) {
    int len1 = s->length;
    int len2 = pattern->length;
    int i, j;
    for (i = 0; i <= len1 - len2; i++) {
        for (j = 0; j < len2; j++) {
            if (s->ch[i+j] != pattern->ch[j]) {
                break;
            }
        }
        if (j == len2) {
            return i;
        }
    }
    return -1;
}

// 删除子串
void deleteSubString(String* s, String* pattern) {
    int len1 = s->length;
    int len2 = pattern->length;
    int i, j;
    for (i = 0; i <= len1 - len2;) {
        for (j = 0; j < len2; j++) {
            if (s->ch[i+j] != pattern->ch[j]) {
                break;
            }
        }
        if (j == len2) {
            for (int k = i; k < len1 - len2; k++) {
                s->ch[k] = s->ch[k+len2];
            }
            s->length -= len2;
        } else {
            i++;
        }
    }
}

int main() {
    String s1, s2, result;
    char str1[Maxlen] = "Hello";
    char str2[Maxlen] = "World";
    initString(&s1, str1);
    initString(&s2, str2);

    // 字符串连接
    concatString(&s1, &s2, &result);
    printf("Concatenated string: ");
    printString(&result);

    // 字符串比较
    printf("Comparison result: %d\n", compareString(&s1, &s2));

    // 字符串定位
    char pattern[Maxlen] = "llo";
    String p;
    initString(&p, pattern);
    printf("Pattern found at index: %d\n", findString(&s1, &p));

    // 删除子串
    char str3[Maxlen] = "apple";
    char str4[Maxlen] = "le";
    String s3, p2;
    initString(&s3, str3);
    initString(&p2, str4);
    deleteSubString(&s3, &p2);
    printf("String after deletion: ");
    printString(&s3);

    return 0;
}

运行结果：

Concatenated string: HelloWorld
Comparison result: -1
Pattern found at index: 2
String after deletion: app