串
2021-04-14 19:43:00 3 举报AI智能生成
数据结构 串 笔记
作者其他创作
大纲/内容
定义
线性表上的操作对单个元素进行，串上的操作针对串的整体或串的一部分子串进行
基本操作
赋值StrAsign(S,chars)
复制StrCopy(S,T)
求串长StrLength(S)
连接StrCat(S,T)
求子串StrString(Sub,S,pos,len)
Sub返回串S的第pos个字符起长度为len的子串
定位/模式匹配StrIndex(S,pos,T)
若S中存在T子串，pos返回串S中T子串第一个字符第一次出现的位置，否则返回-1
插入StrInsert(S,pos,T)
在串的第pos个位置插入T
删除StrDelete(S,pos,len)
删除在串的第pos个位置起长度为len的子串
替换StrReplace（S,T,V)
串S中的T全部用V替代
判断串空StrEmpty(S)
比较StrCompare(S,T)
S>T 返回值>0;S=T 返回值=0 ;S<T返回值<0
清空StrClear(S)
输出DispStr(S)
存储
定长顺序存储
类型
存储方式
按字节为单位编址，一个存储单元放一个字符，相邻字符顺序的存放在地址相邻的存储单元中
按字为单位编址，一个存储单元可以由四个字节组成
非紧凑存储
-一个地址存一个字符，运算处理简单，存储空间过分浪费
紧凑存储
空间利用率高，对串中字符处理的效率低
链式存储
类型
堆分配存储结构
索引存储，动态存储结构
分配存储结构
1.开辟一块地址连续的存储空间，称为**堆**
2.另建立一个索引表，存储串的名字、长度、串在堆中存储的起始地址
3.每产生一个串，就从堆中分配一块与串大小相同的连续空间，存储串、在索引表中登记
考虑到字符串插入删除，长度变动。在索引表中加上串在堆中实际拥有的存储单元的数量，
若字符串长度等于实际拥有存储单元数量，则不许插入
若字符串长度等于实际拥有存储单元数量，则不许插入
C语言中用malloc函数和free函数管理堆
广义表
定义
存储
广义表中数据元素可以具有不同的结构
所以通常采用链式数据结构
表结点：标志域、表头指针域、表尾指针域
原子结点：标志域、值域
所以通常采用链式数据结构
表结点：标志域、表头指针域、表尾指针域
原子结点：标志域、值域
头尾表示法
孩子兄弟表示法
0 条评论
下一页
