软考知识点-01

àì夳堔傛蜴生んèń 2021-09-07 06:14 372阅读 0赞

### 软考知识点-01 ###

*   *  栈
     *  队列
     *  稀疏矩阵
     *  字符串

## 栈 ##

定义：栈是一种特殊的线性表，只允许从一端删除和插入。允许插入和删除的一端为栈顶，另一端为栈底；

分类：顺序存储和链接存储栈  
顺序存储：可以用顺序存储线性表来表示栈，为了指明当前执行插入和删除的栈顶位置，需要一个地址变量top指出栈顶结点在数组中的下标。  
链接存储栈：栈也可以用链表实现，用链表实现的栈称为链接栈。链接的第一个结点为顶结点，链表的首结点就是栈顶指针top，top为NULL的链表时空栈

## 队列 ##

定义：队列是一种特殊的线性表，只允许一端插入，另一端进行删除运算，允许删除操作的那一端称为队首，允许插入运算的一端称为队尾。称队列的结点插入为进队，结点删除为出队，因为最先进队的结点将最先出队所以队列具有先进先出的特征。

分类：顺序存储和链接存储

## 稀疏矩阵 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70_pic_center]

## 字符串 ##

定义：字符串是由某字符集上的字符组成的任何有限字符集序列。当一个字符串不包含任何字符时，称他为空字符串。一个字符所包含的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。  
解释：字符串通常存于足够大的字符数组中，每个字符串的最后一个有效字符之后有一个字符串结束标志，记为"/0"。通常由系统提供的库函数形成的字符串的末尾会自动添加"/0"，但当由用户的应用程序来形容字符串时，必须由程序自行负责在最后一个有效字符串之后添加"/0",以形成字符串。

对字符串的操作通常有：

1.  统计字符串中的有效字符个数
2.  把一个字符串的内容复制到另一个字符串中
3.  把一个字符串的内容链接到一个足够大的字符串的末尾
4.  在一个字符串中查找另一个字符串或字符
5.  按字典顺序比较两个字符串大小

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70_pic_center]: /images/20210901/3105d2ed582546ddaf1ee9d441b1b92f.png