title: "串-string"
date: 2015-05-26 17:14:14
categories: 数据结构
tags: 数据结构
概念：
- 零个或多个字符组成的有限序列，又叫
字符串； - s = "a1a2....an" ( n>=0 )；
- 相邻字符具有前驱和后继的关系；
- 子串是主串的一部分（主串
包含子串）；
串的比较
- 通过字符间的编码进行比较（编码指字符在对应字符集中的
序号）； - 早先计算机常用字符使用标准的ASCII编码（7位二进制数表示一个字符，总共可以表示128个字符）；
- 后来扩展ASCII由8位二进制数标识一个字符，总计可以标识256个字符；
- 后来随着计算机的广泛应用各个国家，各个国家的语言有成百上千种；
- 最后引入Unicode编码，由16位二进制数表示一个字符，总计标识6.5万多个字符；
- Unicode为了和ASCII兼容，Unicode前256个字符与ASCII码完全相同；
- s="happen",t = "happy"; 两个串前4个字符相等，第5个字符 e的ASCII码是101，y的ASCII码是121，e<y; 所以s<t；
常用操作
查找子串 (模式匹配)、串的相似度、截取、反转、最长公共子串、分词、回文、连接等。
顺序存储
- 符合线性表的顺序存储特点；
-
用定长数组定义；
string - 存储空间大小＝串真实长度＋1（"\0"占一个字节空间）
- 串值的存储空间可在程序执行过程中动态分配
- 计算机中的自由存储区
堆，可由C语言的动态分配函数malloc()和free()来管理；
链式存储
- 符合线性表的链式存储特点；
- 为了更大的利用空间，根据实际情况一个结点可以存放一个或多个字符；
-
最后未占满的可以用特殊符号”#“等不全；
string-chain - 除了连接串和串操作外，总体不如顺序存储
灵活，性能不如顺序存储好；
