数据库软考笔记（七）线性表

Myth丶恋晨 2022-10-20 13:54 134阅读 0赞

**目录**

线性结构（考6分）

1，线性表的定义

2，线性表的顺序存储（顺序表）

2.1链表的类别（单链表、循环链表、双链表）

3，栈

4，链栈：用链表存储栈中的元素

5，队列（顺序队列与循环队列、链式存储）

6，串（作为一个整体处理）

--------------------

# **线性结构（考6分）** #

## **1，线性表的定义** ##

一个线性表是n个元素的有限序列（n>=0），通常表示为（a1，a2，a3,......，an）

![20210518114731971.png][]

## **2，线性表的顺序存储（顺序表）** ##

用一组地址连续的存储单元存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

优点：可以随机存取表中的元素，按序号查找元素的速度很快。

缺点：插入和删除操作需要移动元素。

3，线性表的链式存储（链表）

是指用节点来存储数据元素，元素的节点地址可以连续，也可以不连续。节点的空间只有在需要时才申请，无需事先分配。

优点：插入和删除操作不需要移动元素。

缺点：只能按顺序访问元素，不能进行随机存取。

![20210518114739185.png][]

## **2.1链表的类别（单链表、循环链表、双链表）** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NDExODc0_size_16_color_FFFFFF_t_70][]

## **3，栈** ##

栈和队列都是一种特殊的线性表，栈是按“后进先出”的规则进行操作的。

1.  顺序栈：用一组地址连续的存储单元一次存储自栈顶到栈底的数据元素。

存储空间是预先定义或申请的，因此可能会出现栈满的情况。

每一个元素入栈时都要判断栈是否已满。（top==head指针）

需要设置一个头指针指到栈顶。

需要附设指针top指示栈顶元素的位置。

![20210518114754110.png][]

## **4，链栈：用链表存储栈中的元素** ##

栈中元素的插入和删除仅在栈顶进行，因此不必设置头节点，链表的头指针就是栈顶指针。

![20210518114759840.png][]

## **5，队列（顺序队列与循环队列、链式存储）** ##

队列是一种“先进先出”的线性表，队尾入队头出。

队列的顺序存储（空间是事先分配好的）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NDExODc0_size_16_color_FFFFFF_t_70 1][]

队列的循环队列：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NDExODc0_size_16_color_FFFFFF_t_70 2][]

队列的链式存储（链队列）

为了便于操作，可以给链式队列添加一个头节点，并令头指针指向头节点。

队列为空的判定条件就是头指针和为指针的值相同，并且均指向头节点。

![20210518114829583.png][]

## **6，串（作为一个整体处理）** ##

字符串是一串文字及符号的简称，是一种特殊的线性表。

字符串的基本数据元素是字符，常常把一个串作为一个整体来处理。

串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为S=‘a1 a2 ... an’，其中S是串名，单引号括起来的字符序列是串值。

串长：即串的长度，指字符串中的字符个数。

空串：长度为0的空串，空串不包含任何字符。

空格串：由一个或多个空格组成的串。

子串：由串中任意长度的连续字符构成的序列称为子串。

串相等：指两个串长度相等且对应位置上的字符也相同。

串比较：两个串比较大小时以字符的ASCII码值作为依据。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NDExODc0_size_16_color_FFFFFF_t_70 3][]

[20210518114731971.png]: /images/20221020/ea1d67536bfc4540bd8ead483b282dc4.png
[20210518114739185.png]: /images/20221020/60e278cf648c4738b2f8b285d7502941.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NDExODc0_size_16_color_FFFFFF_t_70]: /images/20221020/f6ab697ca7a741bdaa3ec52b7aa9bee1.png
[20210518114754110.png]: /images/20221020/0ad193e0ec494aa694a2fb4e5fb5ee89.png
[20210518114759840.png]: /images/20221020/aeaf466b13084fd58c9072dffd3accf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NDExODc0_size_16_color_FFFFFF_t_70 1]: /images/20221020/8c3040df8c7448f1a52e947674eaa3f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NDExODc0_size_16_color_FFFFFF_t_70 2]: /images/20221020/d237d381f1274c6b9dd27058c4e8e61a.png
[20210518114829583.png]: /images/20221020/c2c76b6098d045d9bf1b92b06eb9da3b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NDExODc0_size_16_color_FFFFFF_t_70 3]: /images/20221020/b93e6e48821d47efab0c18ac387e4491.png