前言
有误的地方还请大家指出来,我会一一改正,也会在评论区置顶更正的记录;如果是因为不同的教材导致的错误,请把教材名、著作者、版次一并提供,供大家一起督促一起学习,本篇参考的教材是《数据结构与算法 (C语言) 严蔚敏》,这也是我大学教材。程序的逻辑大同小异,本篇只是针对参考的教材做出的记录,不具有代表性。保持良好的网络教学环境,请不要随意断章取义、复制粘贴。
线性结构拓展
前言串的存储结构及操作1 串的基本概念2 串的基本操作3 串的顺序存储与实现(三种)4 串的块链存储与实现 数组的存储结构递归广义表广义表的基本操作取表头 GetHead(LS);取表尾 GetTail(LS)。举例 广义表的存储结构表头表尾链存储结构同层结点链存储结构串的存储结构及操作
1 串的基本概念
串: 是由 0 个或多个字符组成的有限序列。记为s =' a1 a2 a3 … ai …an' ( n≥0 )。
空串: 长度为零的串,通常用符号∅
表示。注意:串的逻辑结构和线性表极为相似。区别为串的数据对象约定是字符集
2 串的基本操作
略
3 串的顺序存储与实现(三种)
用一个变量来表示串的长度。在串尾存储一个特殊字符(如:\0
)作为串的终结符。用数组的0号单元存放串的长度。4 串的块链存储与实现
结构定义为:
#define nodesize 16typedef struct node{char data[nodesize];struct node* next;}LString;
数组的存储结构
以行为主序的分配规律。以列为主序分配的规律。递归
递归方法是将复杂问题分解为较为简单的子问题的组合。而这些子问题恰好又是与原问题相同的问题,一般情况量会小一点。递归算法一定要有一个或几个最简单情况的计算(非递归分支)。递归算法是有层次的,低层的解组合成高层的解。各层间一般通过参数传递来交流信息,如使用全局量,则要注意全局量的及时修订。 递归算法一般适用在三个场合: 数据的定义形式是递归的,如 Fibonacci 数列。数据之间的逻辑关系(数据结构),是递归的,如树、图等的定义和操作。某些问题虽然没有明显的递归关系或结构,但问题的解法是不断重复执行一种操作,只是问题规模由大化小,直至某个原操作(基本操作)就结束,如汉诺塔问题。广义表
广义表是线性表的推广,他也是个递归概念。记为:LS=(d1,d2,…,dn)。LS 是表名,di (i=1,2,…,n)是数据元素,数据元素可以是单元素(称为原子),也可以是广义表子表(称为子表);如表A=(a,((b,c),d),(e,(f,g,h)))的数据元素就是由原子和广义表子表构成。空表:长度为 零 的表。深度:广义表中子表最大嵌套层次,也可以说是括弧的重数。表头:非空表的第一个元素。表尾:除表头外,其余元素组成的表。广义表的基本操作
取表头 GetHead(LS);
当广义表LS存在,计算出广义表的表头
取表尾 GetTail(LS)。
当广义表LS存在,计算出广义表的表尾
举例
例:LS=(( ),(e),(a,(b,c,d)))
表长为:3
深度为:3
则: GetHead(LS)=( )
GetTail(LS)= ((e),(a,(b,c,d)))
GetHead(GetTail(LS))= (e)
广义表的存储结构
由于广义表的数据元素可以是单元素和广义表,所以很难用顺序存储结构表示,常采用链式存储结构。
表头表尾链存储结构
表头表尾链存储结构中有两种结点:表结点和单元素结点。
同层结点链存储结构
同层结点链存储结构同样有两种结点:表结点和单元素结点。
结束
Thanks♪(・ω・)ノ 感谢支持!!!