数据结构-C语言版本（八）字符串

时间：2025-04-19 10:09:50

数据结构中的字符串：概念、操作与实战

第一部分 字符串的分类及常见形式

字符串是由零个或多个字符组成的有限序列，是编程中最基础也最重要的数据结构之一。

1. C语言中的字符串表示

字符数组形式
char str1[10] = {'H', 'e', 'l', 'l', 'o', '\0'};
字符串字面量
char str2[] = "Hello World";
动态分配字符串
char *str3 = (char*)malloc(20 * sizeof(char));
strcpy(str3, "Dynamic String");

2. 字符串的存储方式

固定长度存储
#define MAX_LEN 100
char fixedStr[MAX_LEN];
动态长度存储
typedef struct {
    char *data;
    int length;
} DynamicString;

3. 特殊字符串类型

宽字符字符串
#include <wchar.h>
wchar_t wideStr[] = L"宽字符字符串";
多字节字符串
char mbStr[] = "多字节字符串";

第二部分 字符串常见操作

1. 基本操作函数

字符串长度
size_t my_strlen(const char *str) {
    size_t len = 0;
    while (*str++) len++;
    return len;
}
字符串复制
char* my_strcpy(char *dest, const char *src) {
    char *ret = dest;
    while ((*dest++ = *src++));
    return ret;
}
字符串连接
char* my_strcat(char *dest, const char *src) {
    char *ret = dest;
    while (*dest) dest++;
    while ((*dest++ = *src++));
    return ret;
}
字符串比较
int my_strcmp(const char *s1, const char *s2) {
    while (*s1 && (*s1 == *s2)) {
        s1++;
        s2++;
    }
    return *(unsigned char*)s1 - *(unsigned char*)s2;
}

2. 字符串查找与分割

查找字符
char* my_strchr(const char *str, int c) {
    while (*str != (char)c) {
        if (!*str++) return NULL;
    }
    return (char*)str;
}
查找子串
char* my_strstr(const char *haystack, const char *needle) {
    if (!*needle) return (char*)haystack;
    
    for (; *haystack; haystack++) {
        if (*haystack == *needle) {
            const char *h = haystack, *n = needle;
            while (*h && *n && *h == *n) {
                h++;
                n++;
            }
            if (!*n) return (char*)haystack;
        }
    }
    return NULL;
}
字符串分割
char* my_strtok(char *str, const char *delim) {
    static char *last = NULL;
    if (str) last = str;
    if (!last || !*last) return NULL;
    
    char *start = last;
    while (*last && !strchr(delim, *last)) last++;
    
    if (*last) {
        *last = '\0';
        last++;
    } else {
        last = NULL;
    }
    return start;
}

3. 字符串转换与格式化

字符串转数字
int my_atoi(const char *str) {
    int sign = 1, result = 0;
    
    while (*str == ' ') str++;
    
    if (*str == '-' || *str == '+') {
        sign = (*str++ == '-') ? -1 : 1;
    }
    
    while (*str >= '0' && *str <= '9') {
        result = result * 10 + (*str - '0');
        str++;
    }
    
    return sign * result;
}
数字转字符串
void my_itoa(int num, char *str) {
    int i = 0, sign = num;
    
    if (sign < 0) num = -num;
    
    do {
        str[i++] = num % 10 + '0';
    } while ((num /= 10) > 0);
    
    if (sign < 0) str[i++] = '-';
    str[i] = '\0';
    
    // 反转字符串
    int len = i;
    for (int j = 0; j < len/2; j++) {
        char temp = str[j];
        str[j] = str[len-j-1];
        str[len-j-1] = temp;
    }
}
字符串格式化
int my_sprintf(char *str, const char *format, ...) {
    va_list args;
    va_start(args, format);
    int len = vsprintf(str, format, args);
    va_end(args);
    return len;
}

第三部分 字符串编程题例子

1. 反转字符串

void reverseString(char* s, int sSize) {
    int left = 0, right = sSize - 1;
    while (left < right) {
        char temp = s[left];
        s[left++] = s[right];
        s[right--] = temp;
    }
}

2. 验证回文字符串

bool isPalindrome(char* s) {
    int left = 0, right = strlen(s) - 1;
    
    while (left < right) {
        while (left < right && !isalnum(s[left])) left++;
        while (left < right && !isalnum(s[right])) right--;
        
        if (tolower(s[left++]) != tolower(s[right--])) {
            return false;
        }
    }
    return true;
}

3. 字符串转换整数 (atoi)

int myAtoi(char* str) {
    long result = 0;
    int sign = 1;
    
    while (*str == ' ') str++;
    
    if (*str == '-' || *str == '+') {
        sign = (*str++ == '-') ? -1 : 1;
    }
    
    while (*str >= '0' && *str <= '9') {
        result = result * 10 + (*str - '0');
        if (sign == 1 && result > INT_MAX) return INT_MAX;
        if (sign == -1 && -result < INT_MIN) return INT_MIN;
        str++;
    }
    
    return (int)(sign * result);
}

4. 最长公共前缀

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    
    for (int i = 0; ; i++) {
        char c = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != c || strs[j][i] == '\0') {
                char *result = malloc(i + 1);
                strncpy(result, strs[0], i);
                result[i] = '\0';
                return result;
            }
        }
        if (c == '\0') break;
    }
    return strdup(strs[0]);
}

5. 字符串的排列组合

bool checkInclusion(char* s1, char* s2) {
    int len1 = strlen(s1), len2 = strlen(s2);
    if (len1 > len2) return false;
    
    int count1[26] = {0}, count2[26] = {0};
    
    for (int i = 0; i < len1; i++) {
        count1[s1[i] - 'a']++;
        count2[s2[i] - 'a']++;
    }
    
    int matches = 0;
    for (int i = 0; i < 26; i++) {
        if (count1[i] == count2[i]) matches++;
    }
    
    for (int i = len1; i < len2; i++) {
        if (matches == 26) return true;
        
        int left = s2[i - len1] - 'a';
        count2[left]--;
        if (count2[left] == count1[left]) {
            matches++;
        } else if (count2[left] == count1[left] - 1) {
            matches--;
        }
        
        int right = s2[i] - 'a';
        count2[right]++;
        if (count2[right] == count1[right]) {
            matches++;
        } else if (count2[right] == count1[right] + 1) {
            matches--;
        }
    }
    
    return matches == 26;
}

6. 字符串相乘

char* multiply(char* num1, char* num2) {
    int len1 = strlen(num1), len2 = strlen(num2);
    int len = len1 + len2;
    int *result = calloc(len, sizeof(int));
    char *final = malloc(len + 1);
    
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int product = (num1[i] - '0') * (num2[j] - '0');
            int sum = product + result[i + j + 1];
            result[i + j] += sum / 10;
            result[i + j + 1] = sum % 10;
        }
    }
    
    int index = 0;
    while (index < len && result[index] == 0) index++;
    
    if (index == len) {
        final[0] = '0';
        final[1] = '\0';
        return final;
    }
    
    int pos = 0;
    while (index < len) {
        final[pos++] = result[index++] + '0';
    }
    final[pos] = '\0';
    
    free(result);
    return final;
}

7. 正则表达式匹配

bool isMatch(char* s, char* p) {
    if (*p == '\0') return *s == '\0';
    
    bool first_match = (*s != '\0') && (*p == *s || *p == '.');
    
    if (*(p + 1) == '*') {
        return isMatch(s, p + 2) || (first_match && isMatch(s + 1, p));
    } else {
        return first_match && isMatch(s + 1, p + 1);
    }
}

字符串处理是编程中最常见的任务之一，几乎所有的应用程序都会涉及到字符串操作。掌握字符串的基本操作和常见算法，对于解决实际问题至关重要。通过练习这些典型题目，可以深入理解字符串的特性和处理技巧，提高编程能力和算法思维。

相关文章