首页 » 软件编程 » C语言

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

C语言 2022-01-10

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

串的定义

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

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

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

串的比较 

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

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

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

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

串的抽象数据类型

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

串的顺序存储结构示意图

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

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

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

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

串的初始化

相关定义初始化

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

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

定长类初始化

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

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

串的堆式顺序存储结构(Heap)

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

/** 串的堆式顺序存储结构(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语言 字符串内容请搜索www.580doc.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.580doc.com!


上一篇:C++的缺省参数你了解嘛下一篇:C++链表节点的添加和删除介绍
程序园_程序员的世界 Copyright © 2020- www.580doc.com. Some Rights Reserved.