百科知识网

数据抽象类型的两个重要特征

发布时间：2025-10-11 | 来源：互联网转载和整理

1、数据结构：是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在某种特定关系的数据元素的***。

2、结构体类型是由一组被称为结构体成员的数据项组成，每个结构体成员都有自己的标识符，也称为数据域。

3、抽象数据类型的两个特征：数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。

数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

4、算法时间复杂度：也称渐进时间复杂度，表示随问题规模的n的增大，算法执行时间的增长率和f(n)的增长率相同。

算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的度量。

5、顺序栈：

栈空的条件：s->top=-1

栈满的条件：s->top=MaxSize-1(data数组的最大下标）

元素e的进栈操作：先将栈顶指针top增1，然后将e元素放在栈顶指针处

出栈操作：先将栈顶指针top处元素取出放在e中，然后将栈顶指针减1

6、循环队列：

队空：front=rear

队满：（rear+1）%MaxSize=front

入队：rear=（rear+1）%MaxSize

出队：front=（front+1）%MaxSize

7、串的模式匹配原理：从主串的指定的起始位置字符开始和模式第一个字符比较，如果相等，则继续比较下一个字符，如果不等，则从主串的下一个字符开始和模式的第一个字符开始比较，以此类推，直到模式串所有字符都匹配完成，则匹配成功，否则，匹配不成功。

8、串的KMP算法原理：

模式串从右向左进行匹配。对于每个文本搜索窗口（其实就是主串中一个和模式串长度相等的子串，我们称之位一个文本搜索窗口），将窗口内的最后一个字符与模式串的最后一个字符进行比较。如果相等则继续从后向前验证其他字符，直到完全相等或者某个字符不匹配。然后无论匹配与否，都将根据在模式串的下一个出现位置将窗口向右移动。模式串与文本串口匹配时，模式串的整体挪动，是从左往右，但是，每次挪动后，从模式串的最后一个字符从右往左进行匹配。