【数据结构】串（string）的定义与表示

绝地灬酷狼 2021-12-17 11:39 298阅读 0赞

\#笔记整理

## 串（string）（或字符串） ##

是由零个或多个字符组成的有限序列，一般记为  s = ′ a 1 a 2 … a n ′ s=&\#x27;a\_1a\_2…a\_n&\#x27; s=′a1a2…an′。

#### 串的定长顺序存储表示（定长顺序串） ####

定长顺序串的存储分配是在编译时完成的。与前面所讲的线性表的顺序存储结构类似, 用一组地址连续的存储单元存储串的字符序列。

＃define MAXSTRLEN 255
     typedef   unsigned char SString[MAXSTRLEN+1];

**定长顺序存储特点：**

*  串值后加入一个不计入串长的结束标记字符，C中“\\0”表串值的终结，其ASCⅡ码值为0。
 *  超出予定义长度的串值被舍去，称之为“截断”。
 *  存储长度无法扩展。

#### 堆分配存储表示（堆串） ####

在C语言中，已经有一个称为“堆” 的自由存储空间，并可用 malloc() 和 free() 函数完成动态存储管理。  
（注：  
应用程序用到的内存分配：栈分配和堆分配。  
堆：用户程序动态申请的地址空间。  
栈：保存函数参数和块内局部变量的内存区。）  
![在这里插入图片描述][20190708165449968.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]

#### 串的块链存储表示（链串） ####

用链表存储串值时，存在一个“节点大小“的问题，即每个节点可以存放一个字符，也可以存放多个字符。  
为了便于进行串操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表中的最后一个节点。  
称如此定义的串存储结构为**块链结构**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]  
**在链式存储方式中，节点大小的选择和顺序存储方式的格式选择以用都很重要，它直接影响着串处理的效率。因此处理字符串时需要考虑串的存储密度。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]

**串的链式存储结构对某些串操作，如链接操作等有一定的方便之处，但总的来说不如另外两种存储结构灵活，它占用存储量大且操作复杂。**

内容来源：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳

[20190708165449968.png]: /images/20211213/6098febdab484176bb59ed68e2d351c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211213/4c71226e31df48769180b844d97dd55e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20211213/90c4345674394e9880742f1fe7261bc1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20211213/c324086d62af44a1b46f6d04dea6d7f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20211213/e30e7d0b108347888110f8a67f0ba8e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]: /images/20211213/dad93c5d7ae542ed80971c02aac09e2d.png