3种字符串存储结构详解

串也是一类特殊的线性表，故其存储结构与线性表的存储结构类似，只不过组成串的结点是单个字符而已。本文我们就结合线性表的存储结构和大家一起来探讨一下3种字符串存储结构。

1.定长顺序存储

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

串长的表示方法：

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单元存储穿的长度

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

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

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

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

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

2.堆分配存储(很重要，经常用)

堆存储结构的特点：

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

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

typedef struct {

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

int len;

} strHeap;

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

堆存储结构的优点：

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

3.块链存储

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

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

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

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

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

typedef struct string{

char chr[100];//数据=块

struct string *next;//链

} string;

串的链表结构

typedef struct {

string *head;//

string *tail;

int len;

} String;

以上就是3种字符串存储结构的详细情况，我们可以根据字符串的特性来判断字符串存储结构。这些基本的Java知识在本站的Java基础教程中都有很完美的讲解，需要的小伙伴可以随时观看学习。