数据结构---串(赋值,求子串,比较,定位)

简介: 数据结构---串(赋值,求子串,比较,定位)

一.初始化

顺序表中串的存储

#define MaxLen 255
typedef struct{
    char ch[MaxLen];//静态数组,系统自动回收
    int length;
}SString;
typedef struct{
    char *ch;
    int length;
}HString;
HString S;
S.ch=(char*)malloc(MaxLen*sizeof(char));//在堆区分配存储空间,所以需要free手动回收
S.length=0;


串的链式存储

typedef struct StringNode{
    char ch;//一个字符占一个字节
    struct StringNode *next;//占4个字节/8个字节
}StringNode,*String;
//以上定义的结构体类型存储密度低,可以采用以下方案定义结构体
typedef struct StringNode{
    char *ch;//或一个结点存放更多字符
    struct StringNode *next;
}StringNode,*String;

二.赋值操作:将str赋值给S

链式表

void StrAssign(const StringNode* str, char** S) {
    int len = 0;
    const StringNode* currentNode = str;
   
    // 计算字符串长度
    while (currentNode != NULL && currentNode->ch != '\0') {
        len++;
        currentNode = currentNode->next;
    }
   
    *S = (char*)malloc((len + 1) * sizeof(char)); // 分配空间,要考虑'\0'所以长度加1
   
    int i = 0;
//将 currentNode 指向 str,我们可以从链表的头部开始逐个访问节点,并依次处理每个节点的字符
    currentNode = str;
    // 复制字符到新的字符串里
    while (currentNode != NULL && currentNode->ch != '\0') {
        (*S)[i] = currentNode->ch;
        i++;
        currentNode = currentNode->next;
    }
   
    (*S)[i] = '\0'; // 在新的字符串末尾添加'\0'表示结束
}


顺序表

void StrAssign(SString S, SString& sub) {
    int length = 0;
    while (S.ch[length] != '\0') {
        sub.ch[length] = S.ch[length];
        length++;
    }
    sub.ch[length] = '\0';
}

三.复制操作:将chars复制到str中

链式表

void StrCopy(StringNode* str, const char* chars) {
    int len = strlen(chars);
    int i;
    for (i = 0; i < len; i++) {
        str->ch = chars[i];
        if (i < len - 1) {
            str->next = (StringNode*)malloc(sizeof(StringNode));
            // 若字符串还没有复制完毕则手动扩展空间
            str->next->ch = '\0'; // 将下一个节点的 ch 字段设置为空字符
            str = str->next;
        }
    }
    str->next = NULL;
}


顺序表

和赋值操作相同

void StrCopy(SString S, SString& sub) {
    int length = 0;
    while (S.ch[length] != '\0') {
        sub.ch[length] = S.ch[length];
        length++;
    }
    sub.ch[length] = '\0';
}

四.判空操作

链式表
bool StrEmpty(String str)
{
    if(str->ch[0]=='\0')
        return true;
    else
        return false;
}
顺序表
bool StrEmpty(SString S) {
    if (S.ch[0] == '\0')
        return true;
    else
        return false;
}

五.清空操作

void StrClear(StringNode* str)
{
    while(str!=NULL){
        free(str);
        str=str->next;
    }
}

六.串联结

链式表

void Concat(StringNode* str, char* s1, char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    // 创建一个新的结点用于存储连接后的字符串
    StringNode* newNode = (StringNode*)malloc(sizeof(StringNode));
    newNode->ch = (char*)malloc((len1 + len2 + 1) * sizeof(char)); // 加1是为了存放字符串结束符 '\0'
    newNode->next = NULL;
    // 连接字符串并保存到新结点的ch字段
    strcpy(newNode->ch, s1);
    strcat(newNode->ch, s2);
    // 找到链表末尾并将新结点连接到其后
    while (str->next != NULL) {
        str = str->next;
    }
    str->next = newNode;
}


顺序表

void Concat(SString& sub, SString S, SString T) {
    int i = 0;
    // 复制字符串 S 到 sub
    while (S.ch[i] != '\0') {
        sub.ch[i] = S.ch[i];
        i++;
    }
    // 复制字符串 T 到 sub
    int j = 0;
    while (T.ch[j] != '\0') {
        sub.ch[i] = T.ch[j];
        i++;
        j++;
    }
    sub.ch[i] = '\0'; // 添加字符串结束符
}


七.求子串

链式表

void Insert(StringNode** str, char ch) {
    StringNode* newNode = (StringNode*)malloc(sizeof(StringNode));
    newNode->ch = ch;
    newNode->next = NULL;
    if (*str == NULL) {
        *str = newNode;
        return;
    }
    StringNode* currentNode = *str;
    while (currentNode != NULL) {
        currentNode = currentNode->next;
    }
    currentNode->next = newNode;
}
StringNode* SubString(StringNode* str, int pos, int len) {
    StringNode* subStr = NULL;
    StringNode* currentNode = str;
    int currentPos = 0;
    while (currentNode != NULL && currentPos < pos + len) {
        if (currentPos >= pos) {
            Insert(&subStr, currentNode->ch);
        }
        currentNode = currentNode->next;
        currentPos++;
    }
    return subStr;
}


顺序表

bool SubString(SString &Sub,SString S,int pos,int len)
{
    if((pos+len-1)>S.length)
        return false;
    for(int i=pos;i<pos+len;i++)
    {
        Sub.ch[i-pos+1]=S.ch[i];
    }
    Sub.length=len;
    return true;
}


八. 比较串的大小

链式表

int getListLength(StringNode* head) {
    int length = 0;
    ListNode* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }
    return length;
}
int compareLinkedListLength(StringNode* list1, StringNode* list2) {
    int length1 = getListLength(list1);
    int length2 = getListLength(list2);
    if (length1 > length2) {
        return 1;
    } else if (length1 < length2) {
        return -1;
    } else {
        return 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;
}

九.定位操作

链式表

ListNode* locateNode(StringNode* head, int position) {
    if (position <= 0 || head == nullptr) {
        return nullptr;
    }
    ListNode* current = head;
    int count = 1;
    while (current != nullptr && count < position) {
        current = current->next;
        count++;
    }
    return current;
}

顺序表

若主串S中存在与串T值相同的子串,则返回它在主串S中第一次出现的位置,否则函数值为0


#define MaxLen 255
typedef struct {
    char ch[MaxLen]; // 静态数组,系统自动回收
    int length;
} SString;
void SubString(SString& sub, SString S, int start, int length) {
    int i;
    for (i = 0; i < length; ++i) {
        sub.ch[i] = S.ch[start + i];
    }
    sub.ch[length] = '\0'; // 添加字符串结束符
    sub.length = length;
}
int StrCompare(SString S, SString T) {
    int i = 0;
    while (S.ch[i] != '\0' && T.ch[i] != '\0') {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i] - T.ch[i];
        }
        i++;
    }
    return S.length - T.length;
}
int Index(SString S, SString T) {
    int i = 1, n = S.length, m = T.length; // n, m 分别为字符串 S 和 T 的长度
    SString sub;
    while (i <= n - m + 1) {//确保了字符串 T 在字符串 S 中进行匹配时不会越界
//假设 n = 10,m = 3,那么 n - m + 1 = 8
//在循环中,当 i = 9 或 i = 10 时,剩余的字符串 S 的长度已经小于 T 的长度,无法再进行匹配
        SubString(sub, S, i, m);
        if (StrCompare(sub, T) != 0)
            ++i;
        else
            return i;
    }
    return 0;
}



目录
相关文章
|
5月前
|
设计模式 算法 Java
【数据结构和算法】定长子串中元音的最大数目
这是力扣的 1456 题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。又是一道滑动窗口的典型例题,可以帮助我们巩固滑动窗口算法。给你字符串s和整数k。 请返回字符串s中长度为k的单个子字符串中可能包含的最大元音字母数。 英文中的元音字母为(a,e,i,o,u)。
76 1
|
11月前
|
JavaScript
jQuery数据结构渲染(4):复选框checkbox赋值
jQuery数据结构渲染(4):复选框checkbox赋值
55 1
|
11月前
|
JSON JavaScript 数据格式
jQuery数据结构渲染(3):文本和input/textarea框赋值
jQuery数据结构渲染(3):文本和input/textarea框赋值
51 1
|
5月前
|
存储 Java
数据结构:图文详解顺序表的各种操作(新增元素,查找元素,删除元素,给指定位置元素赋值)
数据结构:图文详解顺序表的各种操作(新增元素,查找元素,删除元素,给指定位置元素赋值)
186 0
|
算法
数据结构—串的概述与算法【求子串、比较、删除、插入、扩容、模式匹配】(二)
数据结构—串的概述与算法【求子串、比较、删除、插入、扩容、模式匹配】
315 0
数据结构—串的概述与算法【求子串、比较、删除、插入、扩容、模式匹配】(二)
|
存储 算法 索引
数据结构—串的概述与算法【求子串、比较、删除、插入、扩容、模式匹配】(一)
数据结构—串的概述与算法【求子串、比较、删除、插入、扩容、模式匹配】
543 0
数据结构—串的概述与算法【求子串、比较、删除、插入、扩容、模式匹配】(一)
|
存储 C++
数据结构(C++语言版)实现顺序栈的创建,初始化,赋值随机数,入栈,出栈,获取栈顶元素,输出
数据结构(C++语言版)实现顺序栈的创建,初始化,赋值随机数,入栈,出栈,获取栈顶元素,输出
384 1
数据结构(C++语言版)实现顺序栈的创建,初始化,赋值随机数,入栈,出栈,获取栈顶元素,输出
|
存储
数据结构(C语言版)实现链栈的创建,赋值随机数,进栈,出栈,取栈顶元素,输出
数据结构(C语言版)实现链栈的创建,赋值随机数,进栈,出栈,取栈顶元素,输出
408 0
数据结构(C语言版)实现链栈的创建,赋值随机数,进栈,出栈,取栈顶元素,输出
|
存储
数据结构(C语言版)实现单链表的创建,赋值随机数,插入,删除,取值,输出
数据结构(C语言版)实现单链表的创建,赋值随机数,插入,删除,取值,输出
565 0
数据结构(C语言版)实现单链表的创建,赋值随机数,插入,删除,取值,输出
下一篇
无影云桌面