数据结构(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
}

 总结：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/797394.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

YOLOv8-OBB 旋转目标检测训练自己的数据

YOLOv8-OBB 旋转目标检测训练自己的数据

数据集制作 标注工具&#xff1a;X-AnyLabeling https://github.com/CVHub520/X-AnyLabeling 下载链接&#xff1a;https://pan.baidu.com/s/1UsnDucBDed8pU1RtaVZhQw?pwd5kel 数据标注可以参考&#xff1a;https://zhuanlan.zhihu.com/p/665036259 1. 选择导出方式为…
阅读更多...
Ubuntu搭建Android架构so库交叉编译环境

Ubuntu搭建Android架构so库交叉编译环境

目录 前言一、下载NDK并安装二、安装NDK三、配置交叉编译工具链四、编写交叉编译脚本 前言 需要将一些源码编译成Android可用的架构的so库 一、下载NDK并安装 https://developer.android.google.cn/ndk/downloads/ 二、安装NDK 将下载下来的android-ndk-r23b-linux.zip解压…
阅读更多...
[GICv3] 3. 物理中断处理（Physical Interrupt Handling）

[GICv3] 3. 物理中断处理（Physical Interrupt Handling）

中断生命周期 ​​ 外设通过中断信号线生成中断&#xff0c;或者软件生成中断&#xff08;SGI&#xff09;。Distributor 和 ReDistributor 配合按照中断分组和中断优先级仲裁后将最高优先级的中断分发到 CPU interface。cpu interface 向中断发送到 PEPE 读取 IAR 寄存器&am…
阅读更多...
力扣 24两两交换链表中节点

力扣 24两两交换链表中节点

画图 注意有虚拟头结点 注意判断时先判断cur->next ! nullptr,再判断cur->next->next ! nullptr 注意末尾返回dumyhead->next&#xff0c;用新建result指针来接并返回 class Solution { public:ListNode* swapPairs(ListNode* head) {ListNode *dummyhead new …
阅读更多...
高等数学第一讲:函数极限与连续

高等数学第一讲:函数极限与连续

函数极限与连续 文章目录 函数极限与连续1.函数概念与特性1.1 函数定义 1.2 几种重要的基本函数类型1.2.1 反函数1.2.2 复合函数1.2.3 隐函数 1.3 函数的基本特性1.3.1 有界性1.3.2 单调性1.3.3 奇偶性1.3.4 周期性 2. 函数的极限2.1函数的极限的定义2.2 函数的极限的性质2.3 无…
阅读更多...
昇思25天学习打卡营第19天|基于MindNLP+MusicGen生成自己的个性化音乐

昇思25天学习打卡营第19天|基于MindNLP+MusicGen生成自己的个性化音乐

MusicGen是来自Meta AI的Jade Copet等人提出的基于单个语言模型&#xff08;LM&#xff09;的音乐生成模型&#xff0c;能够根据文本描述或音频提示生成高质量的音乐样本&#xff0c;相关研究成果参考论文《Simple and Controllable Music Generation》。 MusicGen模型基于Tra…
阅读更多...
LabVIEW液压数据采集测试系统

LabVIEW液压数据采集测试系统

液压系统是装载机的重要组成部分&#xff0c;通过液压传动和控制实现各项作业功能&#xff0c;如提升、倾斜、转向等。液压系统的性能直接影响装载机的作业效率和稳定性。为了保证装载机液压系统的正常运行和优化设计&#xff0c;需要对其进行数据采集和测试。本文介绍了一套基…
阅读更多...
jQuery代码原封不动的显示在网页中，应该是没有放在script标签中

jQuery代码原封不动的显示在网页中，应该是没有放在script标签中

jQuery代码原封不动的显示在网页中&#xff0c; 应该是没有放在script标签中 <body> <span id"a1">I am a element by id is a1</span>$(#a1).attr({name:spanDom,title:a1Title}); alert($(#a1).attr(id));alert($(#a1).attr(name));alert($(#a1…
阅读更多...
企业网三层架构

企业网三层架构

企业网三层架构&#xff1a;是一种层次化模型设计&#xff0c;旨在将复杂的网络设计分成三个层次&#xff0c;每个层次都着重于某些特定的功能&#xff0c;以提高效率和稳定性。 企业网三层架构层次&#xff1a; 接入层&#xff1a;使终端设备接入到网络中来&#xff0c;提供…
阅读更多...
昇思25天学习打卡营第20天 | 基于MindNLP+MusicGen生成自己的个性化音乐

昇思25天学习打卡营第20天 | 基于MindNLP+MusicGen生成自己的个性化音乐

基于MindNLPMusicGen生成个性化音乐 实验简介 MusicGen是Meta AI提出的音乐生成模型&#xff0c;能够根据文本描述或音频提示生成高质量音乐。该模型基于Transformer结构&#xff0c;分为三个阶段&#xff1a;文本编码、音频token预测和音频解码。此实验将演示如何使用MindSpo…
阅读更多...
【JavaEE】AOP实现原理

【JavaEE】AOP实现原理

概述 Spring AOP 是基于动态代理来实现AOP的, 此处主要介绍代理模式和Spring AOP的源码剖析 一.代理模式 代理模式是一种常用的设计模式&#xff0c;它允许为其他对象提供代理&#xff0c;以控制对这个对象的访问。这种结构在不改变原始类的基础上&#xff0c;通过引入代理类…
阅读更多...
CentOS 7：停止更新后如何下载软件？

CentOS 7：停止更新后如何下载软件？

引言 CentOS 7 是一个广受欢迎的 Linux 发行版&#xff0c;它为企业和开发者提供了一个稳定、安全、且免费的操作系统环境。然而&#xff0c;随着时间的推移&#xff0c;CentOS 7 的官方支持已经进入了维护阶段&#xff0c;这意味着它将不再收到常规的更新和新功能&#xff0c;…
阅读更多...
「网络通信」HTTP 协议

「网络通信」HTTP 协议

HTTP &#x1f349;简介&#x1f349;抓包工具&#x1f349;报文结构&#x1f34c;请求&#x1f34c;响应&#x1f34c;URL&#x1f95d;URL encode &#x1f34c;方法&#x1f34c;报文字段&#x1f95d;Host&#x1f95d;Content-Length & Content-Type&#x1f95d;User…
阅读更多...
千帆模型申请方法

千帆模型申请方法

第一步&#xff1a;注册千帆云账号 百度智能云-云智一体深入产业 第二步&#xff1a;申请实名认证 第三步&#xff1a;开通服务 第四步&#xff1a;配置到网方Ai的设置里去&#xff0c;网方Ai的下载地址见下面链接。 网方Ai的软件下载地址见论坛地址&#xff1a; 网创有方官…
阅读更多...
Spark调度底层执行原理详解（第35天）

Spark调度底层执行原理详解（第35天）

系列文章目录 一、Spark应用程序启动与资源申请 二、DAG&#xff08;有向无环图&#xff09;的构建与划分 三、Task的生成与调度 四、Task的执行与结果返回 五、监控与容错 六、优化策略 文章目录 系列文章目录前言一、Spark应用程序启动与资源申请1. SparkContext的创建2. 资…
阅读更多...
TS真的比JS更好吗？

TS真的比JS更好吗？

前言 在讨论TypeScript&#xff08;TS&#xff09;是否比JavaScript&#xff08;JS&#xff09;更好时&#xff0c;我们需要明确“更好”这一概念的上下文和衡量标准。TypeScript和JavaScript在多个方面有着明显的区别&#xff0c;但它们并不是简单的“好”与“不好”的关系&a…
阅读更多...
接口安全配置

接口安全配置

问题点&#xff1a; 有员工在工位在某个接口下链接一个集线器&#xff0c;从而扩展上网接口&#xff0c;这种行为在某些公司是被禁止的&#xff0c;那么网络管理员如何控制呢&#xff1f;可以配置接口安全来限制链接的数量&#xff0c;切被加入安全的mac地址不会老化&#xff…
阅读更多...
宜春旅游集散中心展厅OLED透明屏方案设计

宜春旅游集散中心展厅OLED透明屏方案设计

一、项目概述 为提升宜春旅游集散中心展厅的现代化展示水平&#xff0c;增强游客的参观体验&#xff0c;我们计划在展厅的核心区域引入OLED透明屏技术。该方案旨在通过高科技的视觉呈现方式&#xff0c;将展品信息以虚拟与现实相结合的方式展现&#xff0c;打造出一个既具科技感…
阅读更多...
IDEA 2024 maven 配置

IDEA 2024 maven 配置

1 查看IDEA默认的maven版本 2 下载对应的maven maven 官网&#xff1a;Maven – Welcome to Apache Maven 找到对应的版本(可以选择更高一点的版本&#xff0c;但是不能差太大&#xff0c;可能会有不兼容的情况 复制下载连接&#xff0c;并打开新标签&#xff0c;只保留链接…
阅读更多...
STL 提供的容器可以有多快？（下）「榨干最后一滴」

STL 提供的容器可以有多快？（下）「榨干最后一滴」

以下内容为本人的烂笔头&#xff0c;如需要转载&#xff0c;请声明原文链接 微信公众号「ENG八戒」https://mp.weixin.qq.com/s/QWgA97TDMGBnwR4hKA7BwA 查表的消耗 某些场景下需要用到大量的 (string, X) 键值对来存储数据&#xff0c;标准库提供了关联容器 std::map 来解决键…
阅读更多...
最新文章

Copyright @ 2022~2023