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