09年自考《数据结构》各章要点一[9]

顺序串又可按存储分配的不同分为

·静态存储分配直接用定长的字符数组来定义优点是涉及串长的操作速度快但不适合插入链接操作

·动态存储分配是在定义串时不分配存储空间需要使用时按所需串的长度分配存储单元

串的链式存储就是用单链表的方式存储串值串的这种链式存储结构简称为链串链串与单链表的差异只是它的结点数据域为单个字符

为了解决存储密度低的状况可以让一个结点存储多个字符即结点的大小

顺序串上子串定位的运算又称串的模式匹配或串匹配是在主串中查找出子串出现的位置在串匹配中将主串称为目标(串)子串称为模式(串)这是比较容易理解的串匹配问题就是找出给定模式串P在给定目标串T中首次出现的有效位移或者是全部有效位移最坏的情况下时间复杂度是O((nm+)m)假如m与n同阶的话则它是O(n^)链串上的子串定位运算位移是结点地址而不是整数

第五章 多维数组和广义表

数组一般用顺序存储的方式表示存储的方式有

·行优先顺序也就是把数组逐行依次排列PASCALC

·列优先顺序就是把数组逐列依次排列FORTRAN

地址的计算方法

·按行优先顺序排列的数组LOCa(ij)=LOCa()+((i)*n+(j))*d

·按列优先顺序排列的数组LOCa(ij)=LOCa()+((j)*n+(i))*d

[] [] [] [] [] [] [] [] [] [] []