第4章 串2—第5章 数组和广义表

1、1.第4章，字符串，4.1字符串类型的定义，4.2字符串的表示和实现，4.3字符串的模式匹配算法，2.4.1字符串类型的定义一.字符串1的基本概念。字符串是由零个或多个字符组成的有限序列，是一种特殊的线性表，其数据元素是单个字符。3、字符串的逻辑结构和线性表与线性表字符串非常相似，唯一的区别是字符串的数据对象仅限于字符集。字符串的基本操作与线性表有很大不同。在线性表的基本运算中，大多数以“单元素”为运算对象；在字符串的基本运算中，“整个字符串”通常作为运算对象。4，基本操作：Strassign(/Sstring 0)存储字符串的长度，以及字符串的定长序列存储结构的C语言描述。特点：字符串的实际

2、长度可以在这个固定长度范围内任意设置；当实现字符串操作时，基本操作是复制字符序列，9，2，堆分配存储表示，使用一组具有连续地址的存储单元来存储字符串值的字符序列，但是存储空间是在程序执行期间动态分配的。在这种存储结构中，基本操作与定长表示相同，仍然基于“字符序列的拷贝”。在堆存储分配中不需要考虑“截断”。在堆分配的存储表示中，存储空间的管理已经成为算法实现的一个重要关注点，特别是对于新分配空间大小的计算和存储空间的释放。10，typedef struct char * ch/如果是非空字符串，将根据字符串长度分配存储区域。/否则，不分配存储区域，ch为空整数长度；/字符串长度HString字符

3、串的堆分配存储结构用C语言描述。11.通常，用C语言提供的字符串类型是这样实现的。系统使用malloc()和free()函数来动态管理字符串值空间，并为每个新生成的字符串分配一个存储区域，这称为“堆”。在C语言中，字符串以空字符结尾，字符串长度是一个隐式值。这种字符串操作实现的算法是：首先为新生成的字符串分配存储空间，然后复制字符串值。一二三。区块链存储意味着一个字符串由一个链表存储。通常，节点存储的是子串而不是字符。每个节点都分配有固定长度的存储空间(块)，最后一个节点可能没有满，通常用#填充。设置一个头指针和一个尾指针，并给出字符串的长度。这种结构被称为“区块链结构”。13，9/15=3/

4、5，1/2，讨论：方法1的存储密度为：方法2存储密度是：显然，如果有许多数据元素，用法2更好地称为区块链结构。方法1:链表节点(数据字段)的大小为1，方法2:链表节点(数据字段)的大小为n(例如，n=4)，14，#定义CHUNKSIZE 80 /用户可定义的块大小typedef struct Chunk /节点结构char chCUNKSIZE结构块*下一个；组块；c语言描述的区块链存储结构，链表结构的typedef结构/字符串Chunk *头，*尾；/字符串的头指针和尾指针；/字符串LString的当前长度；15、在实际应用中，可以根据问题的需要设置节点的大小。例如，在编辑系统中，整个文本编

5、辑区域可以被视为一个字符串，每一行都是一个子字符串，构成一个节点。也就是说，对同一行中的字符串使用固定长度的结构，并且这些行通过指针连接。区块链结构的缺点：因为字符串的应用需要随机访问字符或子字符串，链表的结构显然不适合这个应用。另外，对于跨多个节点的子串操作，链表的操作不如序列结构的操作灵活。区块链的构造也成为算法设计中的一个棘手问题：节点的合适大小是多少？16，第5章数组和广义表，5.1数组的类型定义，5.3矩阵的压缩存储，5.2数组的顺序表示和实现，5.4广义表的类型定义，5.5广义表的存储结构，17。数组和广义表的特点：特殊线性表元素的值不是原子类型，可以再次分解。elemen，18，

6、5.1数组的定义，1。数组：的基本概念是由一组同名不同下标的变量组成的。注意：本章讨论的数组不同于高级语言中的数组：高级语言中的数组是序列结构；本章中的数组可以是顺序或链式结构，用户可以根据自己的需要进行选择。19，2D阵列的特征：1D阵列的特征：1下标，ai是ai 1，2下标的直接前驱，每个元素ai，j受两个关系(行关系和列关系)的约束，mn的2D阵列可以看作是M行或N列的一维阵列。n维数组的特点是：n个下标，每个元素受n个关系的约束；20.2.数组的抽象数据类型定义了ADT数组数据对象：daj1，J2，jn | ji=0，bi-1，I=1，2，n是数组的维数，bi是数组的第I维。Rn Ri

7、 | 0 jk bk -1，1 k n和k i，0 ji bi -2，i=2，n ADT Array，基本运算：21，二维数组的定义：数据对象： D=aij | 0ib1-1，0 jb2-1数据关系：r=Colrow=| 0ib1-1，0jb2-2col=| 0ib1-2，0jb2-1，22，基本运算：初始化数组(chararray 210=h，e，l，l，0；char array310=“你好”；int a15=1，2，3，4，5；int a2=1，2，3，4，5；24，5.2数组的顺序表示和实现，数据一般不插入或删除。因此，顺序存储更合适。数组是多维结构，而存储空间是一维结构。在选择存储结

8、构时，应该对维度进行排列，即元素应该按照哪个维度的下标先存储。例如，二维数组有两种存储方法：1)基于列顺序的存储方法；FORTRAN语言采用列优先；2)基于行顺序的存储模式。在c语言和PASCAL语言中，一般采用行优先顺序。25，例如：称为基址或基址。以“行顺序为主要顺序”的存储器映射，二维阵列Amn中任何元素ai、J的存储器位置是loc (I，j)=loc (0，0) (inj)，A0，1，A0，0，A0，2，A1，0，A1，1，A1，2，A0，A0，以“列顺序为主要顺序”的存储器映射，二维阵列Amn中任何元素ai、J的存储器位置是LOC (I，J)=LOC (0，0) (JMI)，A0，2

9、88，回答：体积=m * n * l=(6-11)*(7-01)* 6=48 * 6=288，28，5.3矩阵的压缩存储(自学)，讨论：1。什么是压缩存储？如果多个数据元素的值相同，则只分配一个元素值的存储空间，零元素不占用存储空间。2.所有二维数组(矩阵)都可以压缩吗？不一定，这取决于矩阵是否有压缩条件。3.什么样的矩阵有压缩条件？一些特殊的矩阵，如对称矩阵、对角矩阵、三角矩阵、稀疏矩阵等。29，数组和广义表的特征：特殊线性表的所有数据元素仍然属于相同的数据类型。元素的值不是原子类型，可以再次分解。表中的元素也是线性表(即广义线性表)。30，5.4通用表的定义，1。广义表抽象数据类型的定义：

10、ADT GList数据对象：dei | I=1，2，n；n0。是一个数据对象的数据关系：LR| ei-1，eiD，2在ADT表中，基本操作：31，结构创建和破坏表(表，基本操作，状态函数表(表)；GListDepth(L)；GListEmpty(左)；GetHead(左)；GetTail(L)；插入和删除操作插入第一个_总帐(，遍历第一个_总帐(左)，访问()；32，2，基本概念1。定义：广义表是递归定义的线性结构，是线性表的推广。它也称为列表，标记为：LS=(1，2，n)，广义表的首和尾，n是表的长度，33，原子用小写字母表示。第一个元素是头，由其他元素组成的表称为表尾。讨论：广义表和线性表

11、的区别和联系？通用表中的元素可以是原子类型，也可以是列表。当每个元素都是原子的并且是同一类型时，它就是一个线性表。广义表是多级线性结构，例如，D=(E，F)，其中：e=(a，(B，c) f=(d，(E)，D，E，F，A，()，D，()，B，2)广义表的长度被定义为包含在最外层中的元素的数量；3)广义表的深度被定义为括号的最大多重性；注意：“原子”的深度是0；“空表”的深度为1。4)通用表可以共享；5)广义表可以是递归表；递归表的深度是无限的，长度是有限的。6)任何非空的广义表LS=(1，2，n)都可以分解为两部分：表头LS=1和表尾LS=(2，n)。特别注意：对于任何非空的表，标题可以是一个原

12、子或一个列表；但是页脚必须是一个列表。36，E=(a，E)=(a，(a，E)=(a，(a，(a，)，E是递归表，1)a=(2)b=(E)3)c=(a，(b，c)，n=0，因为a是一个空表n=1，表中的元素E是一个原子n=2，a是一个原子，(b，c，D)是一个子表n=3，所有三个元素都是子表n=2，a是一个原子，E是一个子表，d=(a，b，c)=()，()，37，情况23:D=(E， F)=(a，(b，c)，F)，头部(d)=(尾部(d)=，头部(e)=(尾部(e)=，头部(b，c) )=(c)=(尾部(b，c) )=，头部(c)=(尾部(c)=，E，(F)，a，(b，c)，(b，c)，(b，c)，(c)，38，1。 GetTail (b，k，p，h)；2.GetHead (a，b)、(c，d)；3.GetTail (a，b)、(c，d)；4.Get