C语言 数据结构与算法之字符串详解

目录
  • 串的定义
  • 串的比较
  • 串的抽象数据类型
  • 串的初始化
    • 相关定义初始化
    • 定长类初始化
    • 串的堆式顺序存储结构（Heap）
  • 初始化堆字符串
    • 赋值操作
    • 比较两个堆字符串的大小

串的定义

零个或多个字符组成的有限序列

串的比较

串的比较实际上是在比较串中字符的编码

存在某个k < min(n,m),使得ai = bi （i = 1,2,3,4..k）

如果 ak < bk  -->  那么srt1 < srt2 （反之也成立）

除去相等的字符，在第一个不相等的字符位置以Ascii码进行比较

串的抽象数据类型

串的顺序存储结构示意图

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列

typedef struct sqString{
    char* ch;  //若串为空，则按串长分配存储区
               //否则ch = NULL
    int length;//串长
}sqString;

串的初始化

相关定义初始化

/** 状态码  **/
#define TRUE 1
#define FALSE 0
#define EQ 0
#define GT 1  //大于
#define LT -1 //小于

定长类初始化

#define MAX_SIZE 1024
typedef struct{
    char ch[MAX_SIZE + 1];
    //定长方式实现了字符串的顺序结构--缺点是浪费空间
    int length;

}SString;

串的堆式顺序存储结构（Heap）

/** 串的堆式顺序存储结构（Heap）**/
typedef struct{
    char * ch;
    //如果是非空串，那么就按照指定长度分配内存，否则ch就指向NULL
    int length;   //串当前长度
}HString;

初始化堆字符串

赋值操作

/** 为串str赋值，值为字符串常量chars **/
void StrAssign_HeapString(HString * str,char * chars){
    int len = strlen(chars);
    if(!len) return ERROR;
    InitString_HeapString(str);
    //动态为字符串分配空间
    str->ch = (char*)malloc(len * sizeof(char));
    if(!str->ch){
        exit(OVERFLOW); //内存溢出，分配失败
    }
    //逐个将字符串输入所分配的空间中
    for(int i = 0;i < len ; i++)
    {
        str->ch[i] = chars[i];
    }
    str->length = len;  //将长度赋值
    return OK;
}

比较两个堆字符串的大小

str1 == str2 返回0 ； str1 < str2 返回-1 ； str1 > str2 返回1

Status Strcmp_HeapString(HString * str1,HString * str2){
    for(int i = 0;i < str->length && i < str2->length; i ++){
        //遇到不同的字符就直接比较Ascii
        if(str->ch[i] != str[2]->ch[i]){
                //大于则返回整数，小于则返回负数
            return str->ch[i] - str[2]->ch[i];
        }
    }
    //字符都相等但是长度不等，就比较长度
    return str1->length - str2->length;
}

到此这篇关于C语言 数据结构与算法之字符串详解的文章就介绍到这了,更多相关C语言 字符串内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • c语言 数据结构实现之字符串

    c语言 数据结构实现之字符串

    c语言 数据结构实现之字符串 串采用定长顺序存储结构(由c4-1.h定义)的基本操作(13个),包括算法4.2,4.3,4.5   实现效果图: #include <stdio.h> #include <string.h> #include <malloc.h> // SString是数组,故不需引用类型 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define INFEASIBLE -1 #

  • C语言数据结构实现字符串分割的实例

    C语言数据结构实现字符串分割的实例

    C语言数据结构实现字符串分割的实例 以下为"字符串分割"的简单示例: 1. 用c语言实现的版本 #include<stdio.h> /* 根据空格分隔字符串 */ int partition(char *src, char *par, int pos) { int i,j; i = pos; //取到第一个非空格字符 while(src[i] == ' ') { ++i; } if(src[i] != '\0') { j = 0; while((src[i] != '\0'

  • C语言数据结构之模式匹配字符串定位问题

    C语言数据结构之模式匹配字符串定位问题 主要实现了三种字符串的模式匹配,主要包括字符串子操作的集合,字符串指针回溯,和KMP算法 头文件  #ifndef INDEXHEAD_H_INCLUDED #define INDEXHEAD_H_INCLUDED #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXLEN 255 typedef char Sstring[MAXLEN + 1

  • C语言 数据结构与算法之字符串详解

    C语言 数据结构与算法之字符串详解

    目录 串的定义 串的比较 串的抽象数据类型 串的初始化 相关定义初始化 定长类初始化 串的堆式顺序存储结构(Heap) 初始化堆字符串 赋值操作 比较两个堆字符串的大小 串的定义 零个或多个字符组成的有限序列 串的比较 串的比较实际上是在比较串中字符的编码 存在某个k < min(n,m),使得ai = bi (i = 1,2,3,4..k) 如果 ak < bk  -->  那么srt1 < srt2 (反之也成立) 除去相等的字符,在第一个不相等的字符位置以Ascii码进行比较

  • Python数据结构与算法之算法分析详解

    Python数据结构与算法之算法分析详解

    目录 0. 学习目标 1. 算法的设计要求 1.1 算法评价的标准 1.2 算法选择的原则 2. 算法效率分析 2.1 大O表示法 2.2 常见算法复杂度 2.3 复杂度对比 3. 算法的存储空间需求分析 4. Python内置数据结构性能分析 4.1 列表性能分析 4.2 字典性能分析 0. 学习目标 我们已经知道算法是具有有限步骤的过程,其最终的目的是为了解决问题,而根据我们的经验,同一个问题的解决方法通常并非唯一.这就产生一个有趣的问题:如何对比用于解决同一问题的不同算法?为了以合理的方式

  • Go语言数据结构之希尔排序示例详解

    Go语言数据结构之希尔排序示例详解

    目录 希尔排序 算法思想 图解算法 Go 代码实现: 总结 希尔排序 在插入排序中,在待排序序列的记录个数比较少,而且基本有序,则排序的效率较高. 1959 年,Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进,提出了希尔排序算法. 希尔排序又称为“缩小增量排序”.即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序): 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1,整个序列基本有序,再对

  • Go语言数据结构之选择排序示例详解

    Go语言数据结构之选择排序示例详解

    目录 选择排序 动画演示 Go 代码实现 总结 选择排序 选择排序(selection sort)是一种原地(in-place)排序算法,适用于数据量较少的情况.由于选择操作是基于键值的且交换操作只在需要时才执行,所以选择排序长用于数值较大和键值较小的文件. 思想: 对一个数组进行排序,从未排序的部分反复找到最小的元素,并将其放在开头. 给定长度为 nnn 的序列和位置索引i=0 的数组,选择排序将: 遍历一遍序列,寻找序列中的最小值.在 [i...n−1] 范围内找出最小值 minValue

  • c语言数据结构之栈和队列详解(Stack&Queue)

    c语言数据结构之栈和队列详解(Stack&Queue)

    目录 简介 栈 一.栈的基本概念 1.栈的定义 2.栈的常见基本操作 二.栈的顺序存储结构 1.栈的顺序存储 2.顺序栈的基本算法 3.共享栈(两栈共享空间) 三.栈的链式存储结构 1.链栈 2.链栈的基本算法 3.性能分析 四.栈的应用——递归 1.递归的定义 2.斐波那契数列 五.栈的应用——四则运算表达式求值 1.后缀表达式计算结果 2.中缀表达式转后缀表达式 队列 一.队列的基本概念 1.队列的定义 2.队列的常见基本操作 二.队列的顺序存储结构 1.顺序队列 2.循环队列 3.循环队列

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • C语言实现冒泡排序算法的示例详解

    C语言实现冒泡排序算法的示例详解

    目录 1. 问题描述 2. 问题分析 3. 算法设计 动图演示 4. 程序设计 设计一 设计二 结论 5. 流程框架 6. 代码实现 7. 问题拓展 1. 问题描述 对N个整数(数据由键盘输入)进行升序排列. 2. 问题分析 对于N个数因其类型相同,我们可利用 数组 进行存储. 冒泡排序是在 两个相邻元素之间进行比较交换的过程将一个无序表变成有序表. 冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小. 若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,

  • C语言数据结构之单链表存储详解

    C语言数据结构之单链表存储详解

    目录 1.定义一个链表结点 2.初始化单链表 3.输出链表数据 4.完整代码 如果说,顺序表的所占用的内存空间是连续的,那么链表则是随机分配的不连续的,那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系,指针则起到了关键性作用. 单链表的基本结构: 头指针:永远指向链表第一个节点的位置. 头结点:不存任何数据的空节点,通常作为链表的第一个节点.对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题. 首元结点:首个带有元素的结点. 其他结点:链表中其他的节点. 1.定义一

  • C语言数据结构之单链表操作详解

    C语言数据结构之单链表操作详解

    目录 1.插入操作 2.删除操作 3.查找操作 4.修改操作 5.完整代码 1.插入操作 (1)创建一个新的要插入的结点 (2)将新结点的 next 指针指向插入位置后的结点 (3)将插入位置前的节点指针 next 指向新的结点 注意:步骤(2)(3)的顺序不能颠倒,否则会导致插入位置后的部分链表丢失. 插入位置一共分三种,分别是头部插入.中间插入和尾部插入. 如图: 代码: link* insertElem(link* p,int elem,int pos){ link* temp = p;/

  • Java数据结构与算法入门实例详解

    Java数据结构与算法入门实例详解

    第一部分:Java数据结构 要理解Java数据结构,必须能清楚何为数据结构? 数据结构: Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构. 而一个数据结构的设计过程分成抽象层.数据结构层和实现层. 数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构. 一.Java数据结构之:线性数据结构 线性数据结构:常见的

随机推荐