#第三部分 线性部分之串(第7章).ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 湖北工业大学计算机学院 沈华 * 算法7.1 void Concat_sq(SqString *T, SqString S1, SqString S2) { int i; int temp; for(i = 0; i = S1.length - 1; i++) (*T).data[i] = S1.data[i]; if(S1.length + S2.length = MAX) temp = S2.length; else temp = MAX - S1.length; for(i = 0; i = temp - 1; i++) (*T).data[i] = S2.data[i]; (*T).length = S1.length + temp; } 湖北工业大学计算机学院 沈华 * 串的堆结构 这种存储方式仍然以一组地址连续的存储单元来存放串值字符序列。 它有两个特点： 串变量的存储空间是在程序执行过程中动态分配的； 程序中出现的所有串变量可用的存储空间就是一个称之为“堆”的共享空间。 湖北工业大学计算机学院 沈华 * 串的堆结构示意图 b 串名sn length 堆 … … 自由空间 已分配 空间 addrstart free 湖北工业大学计算机学院 沈华 * 采用堆结构的串类型定义 #define MAXSIZE 200 char store[MAXSIZE]; //定义堆空间 int free; //指向堆中自由空间的起始位置 typedef struct { int length; //串的长度 int addrstart; //串在堆中的存储首地址 }HString; 湖北工业大学计算机学院 沈华 * 在串的堆结构如何实现存储空间的分配？ b 堆 … … 自由空间 已分配 空间 free 新串sn’ length addrstart ① sn’.addrstart = free; ① ② for(i=0; i=sn’.length-1; i++) store[sn’.addrstart+i]=ch[i]; sn’.length free ② ③ free = free + sn’.length; 湖北工业大学计算机学院 沈华 * 基于堆结构的基本操作的实现 串复制运算StrCopy_sq 串的堆结构（Cont.） 湖北工业大学计算机学院 沈华 * 算法7.2 int StrCopy_hs(HString *hs, HString sn) { int i; if(free + sn.length MAXSIZE - 1) return -1; (*hs).addrstart = free; (*hs).length = sn.length; for(i = 0; i = sn.length; i++) store[(*hs).addrstart+i] = store[sn.addrstart+i]; free = free + (*hs).length; return 0; } 湖北工业大学计算机学院 沈华 * 串的链式存储结构——块链结构 由于串也是一种线性表，因此可以采用链式存储结构，由于串的特殊性（每个数据元素是一个字符），在具体实现时，每个结点内可以存放1个或多个字符，每个结点可容纳字符的个数称为块大小。 湖北工业大学计算机学院 沈华 * 串的块链结构示意图 H o w ＿ a r e ＿ y # # # ^ 9 head tail len next ch 如果串长不是块大小的整数倍，那么最后一个结点需要用一个特殊的字符来补满。 湖北工业大学计算机学院 沈华 * 串的块链结构示意图 H o w ＿ a r e ＿ y # # # ^ 9 head tail len next ch 设置尾指针是为了便于实现串的联接操作，但要注意的是联接时需要处理串尾的特殊(无效)字符#。 湖北工业大学计算机学院 沈华 * 串的块链结构描述如下 #define CHUNKSIZE 4 //块大小 typedef struct ChNode //块链中的结点结构 { char ch[CHUNKSIZE]; struct ChNode *next; }ChNode; typedef struct //块链结构 { ChNo