字符串和字符串的常见存储结构

继续接去年的常见数据结构和算法总结 系列随笔记录

一、计算机里进行非数值处理的对象基本上是字符串数据,比处理浮点和整数都要复杂

string串定义:由 0 个或多个 字符 组成的 有限的 序列,通常记为:s =“a1 a2 a3 … ai …an”  ( n≥0 ,且n是有限的)。其中的引号不属于串,只是一个标记作用!

n就是串的长度,且字符串里的字符 ai 的值由 字母、数字或其他字符 组成的。

二、字符串为什么要用双引号标记

作用:避免字符串与变量名或数的常量混淆。  

    char *str = "*str";
    int x = 1111111;
    char *str1 = "1111111";

三、几个概念

空串:不含任何字符的串,长度 = 0,用符号 f  表示。也就是说空串也是字符串!

空格串:仅由一个或多个空格组成的串。 区分空串和空格串!

子串:由串中任意个连续的字符组成的子序列。空串是任意串的子串,任意串是其自身的子串。 

主串:包含子串的串。

字符的位置:字符在序列中的序号。

子串在主串中的位置:子串的首字符在主串中的位置。

    char *str = "";//空串
    char *str1 = "    ";//空格串
    char *strMain = "abcdefg";//主串
    char *strSub = "cde";//strMain的子串,子串在主串的位置是 3
    char *strSub1 = "";//空串同样是strMain的子串
    char *strSub2 = "abcdefg";//也可以看成是strMain的子串,字符串本身也是自己的子串,在主串的位置是 1

串相等:当两个串的长度相等且各个对应位置的字符都相等时才相等。

    char *s1 = "12345";
    char *s2 = "12345";
    //s1和s2相等
    char *s3 = "1 2345";
    //s1,s2和s3不等

四、串的逻辑存储结构

还是那句话,线性表是数据结构和算法的基础!很多地方都以线性表为基础去扩展!同样,串的逻辑结构和线性表很相似!

串和线性表的区别:串的数据对象,我们约定是字符集,也就是说,字符串是数据受限的!而线性表的数据对象,不一定是字符集!可以存储整数,浮点数等,都没问题。

五、串的基本操作

和线性表差别较大。 因为,线性表的基本操作大多以“单个元素”作为操作对象,比如删除一个元素,初始化一个结点,插入一个结点等,而串的基本操作通常以“串这个整体”作为操作对象。比如在串中查找某个子串、在串的某个位置上插入一个子串、删除一个子串,子串的模式匹配……

六、字符串的三种存储结构

串也是一类特殊的线性表,故其存储结构与线性表的存储结构类似,只不过组成串的结点是单个字符而已。

 

定长顺序存储

也称为静态存储分配的顺序串。即用一组地址连续的存储单元依次存放串中的字符序列。“定长”、“静态”的意思可简单地理解为一个确定的存储空间,它的长度是不变的。 

串长的表示方法:

1)在串的存贮区首地址显式地记录串的长度。 方便使用,一目了然,比如Pascal语言。

2)在串之后加结束标志,隐式记录串的长度,不直观,如C/C++ 使用 “\0”。这里使用的是1)中的显式方式记录串长度。


字符串This is a dog.  的存储形式对比,要知道,串的静态存储结构(简单一维数组表示),大小不可变。

注意:

1)串的实际长度可在这个预定义长度的范围内随意设定,超过预定义长度的串值则被舍去,称之为“截断”。

2)字符类型存储的是对应字符在 ASCII 里的值,10进制表示!

#define len 255
typedef unsigned char string[len + 1];//0单元存储穿的长度

定长顺序存储表示时串操作的缺点 :

需事先预定义串的最大长度,这在实际的程序运行前是很难估计的。 

由于定义了串的最大长度,使得串的某些操作受限(截尾),如串的联接、插入、置换等运算。

克服办法:不限定最大长度——动态分配串值的存储空间。 

 

PS:C没有字符串类型,C的字符串类型实际上是字符数组。而常说的C风格字符串,实际是末尾元素为零的字符数组。其他字符串风格取决于该语言设计思想,如Pascall语言为了强化类型管理与简化实现,字符串类型不要求字符串尾部有特殊字符表示字符串结束,而采用一种数据结构来管理字符串,在字符串头部分别有两个字段表示了该字符串的长度和引用计数。这样,简单的指针赋值直接复制地址并增加引用计数即可。而且字符串长度也不用每次都要重新计算。后来的C++、Java等语言都借鉴了这样的设计思想。

 

堆分配存储(很重要,经常用)

堆存储结构的特点:

仍以一组空间足够大的、地址连续的存储单元依次存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配的,C 语言中提供的串类型就是以这种存储方式实现的。

由动态分配函数 malloc() 分配一块实际串长所需要的存储空间(“堆”),如果分配成功,则返回此空间的起始地址,作为串的基址,由 free( ) 释放串不再需要的空间。 

typedef struct {
    char *chr;//存放穿的手地址,其实编写程序,只要思路清晰,基础知识点明白,那么一定能写出来
    int len;
} strHeap;

这样分配的字符串,对分配的,可以动态改变长度,进行串的复制,插入,连接,置换算法等

堆存储结构的优点:

堆存储结构既有顺序存储结构的特点,处理(随机取子串)方便,操作中对串长又没有任何限制,更显灵活,因此在串处理的应用程序中常被采用。 

 

块链存储

刚刚的堆分配,其实还是顺序表的动态分配的演化。那么自然有链表的演化,串值也可用单链表存储,简称为链串。 链串与单链表的差异只是它的结点数据域为单个字符。 

   

优点:便于插入和删除    缺点:空间利用率低 ,这里知道一个公式:

为了提高空间利用率,可使每个结点存放多个字符(这是顺序串和链串的综合 (折衷) ),称为块链结构。 实际应用时,可以根据问题所需来设置结点的大小。例如:在编辑系统中,整个文本编辑区可以看成是一个串,每一行是一个子串,构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。 

为了便于进行串的操作(连接等),当以块链存储串值时,除头指针外还可附设一个尾指针指示链表中的最后一个结点,并给出当前串的长度。

先表示块链的结点的结构(这也是这类问题的惯常做法,链式的,可以考虑定义单个的结点,然后定义整体的组织,从小到大,由内而外!)

typedef struct string{
   char chr[100];//数据=块
    struct string *next;//链
} string;

串的链表结构

typedef struct {
    string *head;//
    string *tail;
    int len;
} String;

 

辛苦的劳动,转载请注明出处,谢谢……

http://www.cnblogs.com/kubixuesheng/p/4116378.html

时间: 2024-09-15 01:42:13

字符串和字符串的常见存储结构的相关文章

Python 字符串的编码转换、存储及乱码总结

Python2的字符串包含str.unicode两种类型,str的字符串编码方式由源码文件的编码方式决定,目前使用的基本都是UTF-8的编码格式,所以要在py文件的头部指定编码格式: # -*- coding: utf-8 -*- 在Python程序内部,通常使用的字符串为unicode编码,这样的字符串字符是一种内存编码格式,如果将这些数据存储到文件或是记录日志的时候,就需要将unicode编码的字符串转换为特定字符集的存储编码格式,比如:UTF-8.GBK等等,很多时候Python程序员都会

队列的存储结构和常见操作(c 语言实现)

一.队列(queue) 队列和栈一样,在实际程序的算法设计和计算机一些其他分支里,都有很多重要的应用,比如计算机操作系统对进程 or 作业的优先级调度算法,对离散事件的模拟算法,还有计算机主机和外部设备运行速度不匹配的问题解决等,很多很多.其实队列的本质还是线性表!只不过是一种特殊的或者说是受限的线性表,是这样的: 1).限定在表的一端插入.另一端删除. 插入的那头就是队尾,删除的那头就是队头.也就是说只能在线性表的表头删除元素,在表尾插入元素.形象的说就是水龙头和水管,流水的水嘴是队头,进水的

线性链表其他种类(静态,双向,循环)的存储结构和常见操作

一.静态单链表 在不支持动态空间分配的环境中,要使用链表存储数据,那么可采用静态链表的方法:即在一块预分配的存贮空间中,用下标作为指针链来构成链式结构. //既然是静态链表,那么可以使用一维数组实现存储,java没有指针,那么就用这来使用链表结构 //在不支持动态空间分配的环境中,要使用链式结构技术,可采用静态链表的方法:即在一块预分配的存贮空间中,用下标作为指针. //存储结构:在数组中增加一个"指针"域,存放下一元素在数组中的下标.且0为代表空指针   //设S为SLinkList

一个字节造成的巨大性能差异——SQL Server存储结构

今天同事问了我一个SQL的问题,关于SQL Server内部存储结构的,我觉得挺有意思,所以写下这篇博客讨论并归纳了一下.问题是这样的: 首先我们创建两张表,一张表的列长度是4039字节,另一张表的长度是4040字节,他们就只有一个字节的差距,比如以下创建表的SQL: CREATE TABLE tb4039(c1 INT IDENTITY,c2 char(4035) not null)CREATE TABLE tb4040(c1 INT IDENTITY,c2 char(4036) not nu

MySQL的InnoDB逻辑存储结构

InnoDB存储引擎中的表非常像Oracle中的索引组织表,每张表必须得有主键,如果表在创建时没有显示定 义主键,则根据以下原则自动创建主键: 1)如果有非空的唯一索引,则该索引所在的列为主键: 2)如果不符合上述条件,自动创建一个6个字节的指针为主键. InnoDB存储引擎的逻辑存储 结构和Oracle几乎一样,从大到小分别为:表空间.段.区.页,它们的关系如下图所示: 表空间 在上一篇<MySQL InnoDB文件介绍>中,我们知道InnoDB有一个默认的表空间,如果我们启用了参数 inn

《Effective Ruby:改善Ruby程序的48条建议》一第10条:推荐使用Struct而非Hash存储结构化数据

第10条:推荐使用Struct而非Hash存储结构化数据 哈希表是Ruby程序员经常使用的一种有用的.通用的数据结构.Hash类提供了使用哈希表的简单的接口,与数组一样,它是Ruby的重要部分之一,该类有自己专用的语法来创建新的实例.当需要使用键值对时,Hash类绝对是首选.事实上,Ruby程序员在任何时候都会使用哈希,甚至方法的参数关键字也是使用Hash类语法糖来实现的.哈希如此通用,因此能被用来对类型进行模拟,比如数组.集合,甚至基本对象.在OOP语言中,当用到结构化数据时,我们往往有比哈希

密封舱-MFC用fscanf去读取字符串,字符串中间不能有空格么?

问题描述 MFC用fscanf去读取字符串,字符串中间不能有空格么? MFC用fscanf去读取字符串,字符串中间不能有空格么?如果有空格,用%s怎么才能正确读取呢? 解决方案 看你的格式限定符怎么写的,你可以自定义分割字符

Oracle数据库结构之物理存储结构

oracle|数据|数据库|数据库结构 1.物理存储结构1.1数据文件数据文件用于存放所有的数据库数据.将数据放在多个数据文件中,再将数据文件分放在不同的硬盘中,可以提高存取速度.1.2记录文件记录文件也称为重做日志(事务)文件.重做日志在日志文件中以循环的方式工作.有归档日志模式和非归档日志模式.1.3参数文件每一个Oracle数据库和实例都有它自己唯一的init.ora文件.Init.ora文件中的值决定着数据库和实例的特性.1.4控制文件每个数据库中至少要有一个控制文件,但是建议用户使用两

大话数据结构二十一:图的存储结构之邻接多重表

1.引言: 若要删除左边的(V0,V2)这条边,需要对图下表的阴影两个结点进行删除操作. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 2.邻接多重表的存储结构: iVex和jVex:是与某条边依附的两个顶点在顶点表中的下标. iLink:指向依附顶点iVex的下一条边. jLink:指向依附顶点jVex的下一条边. 3.邻接多重表示意图绘制: 作者:csdn博客 zdp072