特殊线性表讲义.pptVIP

特殊线性表——串 串的逻辑结构 串的数据对象约束为某个字符集。 微机上常用的字符集是标准ASCII码，由 7 位二进制数表示一个字符，总共可以表示 128 个字符。扩展ASCII码由 8 位二进制数表示一个字符，总共可以表示 256 个字符，足够表示英语和一些特殊符号，但无法满足国际需要。Unicode由 16 位二进制数表示一个字符，总共可以表示 216个字符，即6万5千多个字符，能够表示世界上所有语言的所有字符，包括亚洲国家的表意字符。为了保持兼容性，Unicode字符集中的前256个字符与扩展ASCII码完全相同。 S1=ab12cd S2=ab12 S3=ab13 S4=ab12φ S5= S6=φφφ 特殊线性表——串 串的逻辑结构 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串。 子串的位置：子串的第一个字符在主串中的序号。 串的比较：通过组成串的字符之间的比较来进行的。 给定两个串：X=x1x2…xn和Y=y1y2…ym，则： 1. 当n=m且x1=y1，…，xn=ym时，称X=Y； 2. 当下列条件之一成立时，称X＜Y： ⑴ n＜m且xi=yi（1≤ i≤n）； ⑵存在k≤min(m,n)，使得xi=yi(1≤i≤k-1)且xk＜yk。 特殊线性表——串 串的逻辑结构 例：S1=ab12cd ，S2=ab12，S3=ab13 串的抽象数据类型定义 特殊线性表——串 ADT String Data 串中的数据元素仅由一个字符组成，相邻元素具有前驱和后继关系 Operation StrLength 前置条件：串S已存在 输入：无 功能：求串S的长度 输出：串S中的字符个数 后置条件：串S不变 StrAssign 前置条件：无 输入：串T 功能：串赋值，将T的串值赋值给串S 输出：串S 后置条件：串T不变 StrConcat 前置条件：无 输入：串S，串T 功能：串连接，将串T放在串S的后面连接成一个新串S 输出：串S 后置条件：串T不变 StrSub 前置条件：串S已存在 输入：位置i，长度len 功能：求子串，返回从串S的第i个字符开始长为 len 的子串 输出：S的一个子串 后置条件：串S不变 StrCmp 前置条件：无 输入：串S，串T 功能：串比较 输出：若S=T，返回0；若ST, 返回-1；若ST, 返回1 后置条件：串S和T不变 StrIndex 前置条件：串S已存在 输入：串T 功能：子串定位 输出：子串T在主串S中首次出现的位置 后置条件：串S和T不变 StrInsert 前置条件：串S已存在 输入：串T，位置i 功能：串插入，将串T插入到串S 的第i个位置上 输出：串S 后置条件：串T不变 StrDelete 前置条件：串S已存在 输入：位置i，长度len 功能：串删除，删除串S中从第i个字符开始连续len个字符 输出：串S 后置条件：串S的长度减少了len StrRep 前置条件：串S已存在 输入：串T，串R 功能：串替换，在串S中用串R 替换所有与串T相等的子串 输出：串S 后置条件：串T和R不变 endADT 求子串操作SubStr(s, i, len)示例 a b c d e f g e i = 3, len = 3 i = 7, len = 4 特殊线性表——串 串的抽象数据类型定义 c d e a b c d e f g e g e 空串 串的存储结构 顺序串：用数组来存储串中的字符序列。 特殊线性表——串 a b c d e f g 方案1：用一个变量来表示串的实际长度。 特殊线性表——串 如何表示串的长度？ 串的存储结构 0 1 2 3 4 5 6 … … Max-1 a b c d e f g 9 空 闲 特殊线性表——串 方案1：用一个变量来表示串的实际长度。 串的存储结构 如何表示串的长度？ 0 1 2 3 4 5 6 7