数据结构(4.1)——串的存储结构

串的顺序存储

串（String）的顺序存储是指使用一段连续的存储单元来存储字符串中的字符。

计算串的长度

静态存储(定长顺序存储)

#define MAXLEN 255//预定义最大串为255

typedef struct {
	char ch[MAXLEN];//每个分量存储一个字符
	int length;//串的实际长度
}SString;

动态存储(堆分配存储)

typedef struct {
	char* ch;//按串长分配存储区，ch指向串的基地址
	int length;//串的长度
}HString;
void main() {
	HString S;
	S.ch = (char*)malloc(MAXLEN * sizeof(char));
	S.length = 0;
}

注意调用完malloc函数后需要手动用free函数回收内存空间

代码示例

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

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

typedef struct {
    char ch[MAXLEN];      // 按串长分配存储区
    int length;    // 串的长度
} HString;

// 函数：initString
// 功能：初始化一个HString串
// 参数：str - 指向HString结构的指针
void initString(HString *str) {
    str->length = 0;
}

// 函数：assignString
// 功能：为HString串赋值
// 参数：str - 指向HString结构的指针
//       chars - 要赋值的字符数组
void assignString(HString *str, char *chars) {
    int i = 0;
    while (chars[i] != '\0' && i < MAXLEN) {
        str->ch[i] = chars[i];
        i++;
    }
    str->length = i;
}

// 函数：concatString
// 功能：连接两个HString串
// 参数：str1 - 第一个HString串
//       str2 - 第二个HString串
// 返回值：连接后的HString串
HString concatString(HString str1, HString str2) {
    HString result;
    initString(&result);
    int i, j;
    for (i = 0; i < str1.length; i++) {
        result.ch[i] = str1.ch[i];
    }
    for (j = 0; j < str2.length && i + j < MAXLEN; j++) {
        result.ch[i + j] = str2.ch[j];
    }
    result.length = i + j;
    return result;
}

// 函数：printString
// 功能：打印一个HString串
// 参数：str - 要打印的HString串
void printString(HString str) {
    for (int i = 0; i < str.length; i++) {
        printf("%c", str.ch[i]);
    }
    printf("\n");
}

int main() {
    HString S, T, R;

    // 初始化串
    initString(&S);
    initString(&T);

    // 赋值
    assignString(&S, "Hello");
    assignString(&T, " World");

    // 打印原始串
    printString(S);
    printString(T);

    // 连接两个串
    R = concatString(S, T);
    printString(R);

    return 0;
}

串的链式存储

串的链式存储结构是指使用链表来存储字符串中的字符。

typedef struct {
	char ch;//每个结点存1个字符
	struct StringNode* next;
}StringNode, * String;

但这样子的操作会造成内存存储密度过低

所以我们可以优化一下代码，在每个结点多存一些字符

typedef struct {
	char ch[4];//每个结点存多个字符
	struct StringNode* next;
}StringNode, * String;

代码示例

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

typedef struct Node {
    char data;          // 存储字符数据
    struct Node* next;  // 指向下一个节点的指针
} Node;

typedef struct {
    Node* head;         // 指向链表头节点的指针
    int length;         // 串的长度
} LString;

// 函数：initLString
// 功能：初始化一个LString串
// 参数：str - 指向LString结构的指针
void initLString(LString *str) {
    str->head = NULL;
    str->length = 0;
}

// 函数：appendLString
// 功能：向LString串追加一个字符
// 参数：str - 指向LString结构的指针
//       ch - 要追加的字符
void appendLString(LString *str, char ch) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = ch;
    newNode->next = NULL;

    if (str->head == NULL) {
        // 如果链表为空，新节点作为头节点
        str->head = newNode;
    } else {
        // 否则，找到链表的最后一个节点，并追加新节点
        Node* current = str->head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
    str->length++;
}

// 函数：printLString
// 功能：打印一个LString串
// 参数：str - 要打印的LString串
void printLString(LString str) {
    Node* current = str.head;
    while (current != NULL) {
        printf("%c", current->data);
        current = current->next;
    }
    printf("\n");
}

// 函数：freeLString
// 功能：释放LString串的内存
// 参数：str - 指向LString结构的指针
void freeLString(LString *str) {
    Node* current = str->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    str->head = NULL;
    str->length = 0;
}

int main() {
    LString S;

    // 初始化串
    initLString(&S);

    // 追加字符
    appendLString(&S, 'H');
    appendLString(&S, 'e');
    appendLString(&S, 'l');
    appendLString(&S, 'l');
    appendLString(&S, 'o');

    // 打印串
    printLString(S);

    // 释放内存
    freeLString(&S);

    return 0;
}

基本操作的实现

求子串

SubString(&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串

// 函数SubString：从字符串S中提取从pos位置开始的长度为len的子串
bool SubString(SString *Sub, SString S, int pos, int len) {
    if (pos + len - 1 > S.length || pos < 1) // 检查子串范围是否越界
        return false; // 如果越界，返回false
    for (int i = pos; i < pos + len; i++) // 循环，将子串复制到Sub中
        //将源字符串S中从pos开始的第i个字符复制到目标子串Sub的相应位置
        Sub->ch[i - pos + 1] = S.ch[i];
    Sub->ch[len] = '\0'; // 在子串末尾添加空字符，标记字符串结束
    Sub->length = len;   // 设置子串的长度
    return true;         // 如果操作成功，返回true
}

比较操作

StrCompare(S,T):比较操作。若S>T，则返回值>0:若S=T，则返回值<0;

//比较操作。若S>T，则返回值>0:若S=T，则返回值<0;
int StrCompare(SString S, SString T) {
    for (int i = 1; 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;
}

定位操作

Index(S,T):定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0

// 函数Index：在主串S中查找子串T的位置
// 返回值：如果找到子串，返回子串在主串中的位置（从1开始计数）
//         如果没有找到，返回0
int Index(SString S, SString T) {
    int i = 1, n = StrLength(S), m = StrLength(T);
    SString sub; // 定义一个SString变量，用于暂存从主串S中提取的子串

    // 循环，直到i超过可能存在子串的最后一个位置
    while (i <= n - m + 1) {
        SubString(&sub, S, i, m); // 从S中提取从位置i开始的长度为m的子串
        if (StrCompare(sub, T) != 0) // 如果提取的子串与T不相等
            ++i; // 移动到下一个位置
        else
            return i; // 如果找到相等的子串，返回其在主串中的位置
    }
    return 0; // 如果循环结束还没有找到子串，返回0
}