C++ 实现数据结构中的线性表

浅浅的花香味﹌ 2023-07-17 02:39 7阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70]  
**建议用上面这张图，把关于线性表的知识联系起来进行学习**

# 1.什么是线性表？ #

## 答：零个或多个元素组成的，有序的、有限的序列，称为线性表。 ##

### 注意：这里的有序是指：第一个元素前面没有元素（无前驱），最后一个元素后面没有元素（无后继），中间的元素有且只有一个前驱和后继，是一种承前启后的关系 ###

如一个数组\[1,2,3,4\]是一个线性表，因为他是有序的，元素个数为4的一个序列

如班上的成绩表是一个线性表，因为他是按学号（分数高低），或者任意排列，只要满足第一个元素无前驱，最后一个元素无后继，中间元素承前启后，而且是有限个数的，就是一个线性表  
——————————————————分界线————————————————

# 2.线性表的相关操作 #

**①初始化一个空的线性表(在类中交给构造函数完成)  
②销毁整个线性表（在类中交给析构函数完成）  
③判断表是否为空  
④判断表是否已满  
⑤在表中的第i个位置插入元素  
⑥删除表中的第i个元素  
⑦查找表中与某个元素相等的元素，并返回该元素的位置  
⑧返回表中的元素个数**  
——————————————————分界线————————————————

# 3.什么是线性表的顺序存储？ #

## 答：用一段地址连续的存储单元存储线性表的数据元素 ##

地址连续的存储单元：数组，包括静态数组和动态数组，二者区别请看  
[C++实现 栈的顺序存储（通过静态数组）][C_]  
[C++实现 栈的顺序存储（通过动态数组）][C_ 1]

## 线性表的顺序存储的结构代码 ##

typedef int ElementType;
    #define Maxsize 10
    struct Sequence
    {
        
    ElementType data[Maxsize];//存储数据的数组
    int  length;//线性表当前的长度
    };

**注意，当中的Maxsize（数组长度）和length（线性表长度）的区别：  
数组的长度是线性表所在存储空间的长度，通常分配后这个量是不变的；  
线性表长度是指表中的元素总共有多少个，这个量是随着插入和删除操作变化的，但必须小于等于数组长度**

## 线性表顺序存储的具体方法实现 ##

### 请看 [C++ 实现线性表的顺序存储（顺序表）][C_ 2] ###

——————————————————分界线————————————————

# 4.什么是线性表的链式存储？ #

## 答：由多个节点（Node ）串联而成，每一个节点不仅有数据信息（数据域），最重要的还存储了后继节点的地址（指针域），所以只要知道某一个节点的位置，就能遍历后续节点，结构如下图 ##

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

## 线性表的链式存储的结构代码 ##

typedef int ElementType;
    struct Node
    {
        
    ElementType data;
    Node *next;
    };

## 线性表链式存储的具体方法实现 ##

### 请看 [C++实现 线性表的链式存储（单链表）][C_ 3] ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70]: /images/20230528/324cfc9dc9ed4599863ec6bb9a3c88e8.png
[C_]: https://blog.csdn.net/weixin_43335392/article/details/104932343
[C_ 1]: https://blog.csdn.net/weixin_43335392/article/details/104935311
[C_ 2]: https://blog.csdn.net/weixin_43335392/article/details/105012498
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzMzNTM5Mg_size_16_color_FFFFFF_t_70 1]: /images/20230528/53530062dc974e2c9f6979fc176abf29.png
[C_ 3]: https://blog.csdn.net/weixin_43335392/article/details/104544383