数据结构—线性结构—(顺序表和链表的差异)

拼搏现实的明天。 2023-07-21 06:15 96阅读 0赞

### 这里写目录标题 ###

*  存取方式
 *  逻辑结构和物理结构
 *  基本操作
 *   *  插入&删除：
     *  插入操作：
     *  删除操作：
     *  查找操作
 *  内存空间
 *   *  顺序存储：
     *  链式存储：
 *  顺序表和单链表的选择
 *  三个常用操作
 *   *  求最值：
     *  逆置：
     *  归并：

# 存取方式 #

顺序表可以实现顺序存取和随机存取

单链表只能实现顺序存取  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

# 逻辑结构和物理结构 #

顺序表：逻辑相邻物理上也相邻，通过相邻表示逻辑关系

单链表：逻辑相邻物理上不一定相邻，通过指针表示逻辑关系

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

# 基本操作 #

## 插入&删除： ##

单链表为【O(1)（节点指针已知）O(n)（节点指针未知）】，而且操作时只需修改指针

顺序表为O(n)，而且需要移动大量元素

## 插入操作： ##

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

## 删除操作： ##

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

## 查找操作 ##

按值查找中单链表和顺序表（无序）都为O(n)

按序查找中单链表为O(n)，顺序表为O(1)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]

# 内存空间 #

## 顺序存储： ##

无论是静态分配还是非静态分配都需要预先分配合适的内存空间  
静态分配时预分配空间太大会造成浪费，太小会造成溢出  
动态分配时虽不会溢出，但是扩充需要大量移动元素，操作效率低

## 链式存储： ##

在需要时分配节点空间即可，高效方便，但指针需要使用额外的空间

# 顺序表和单链表的选择 #

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

# 三个常用操作 #

## 求最值： ##

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

## 逆置： ##

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

## 归并： ##

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230528/f86eb2fd33734d6e842a18bf7918b0eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20230528/bed2c4c889624743baa8dc546e5aa9a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: /images/20230528/c65a034c1c21412cabe9cb4e0eacd912.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: /images/20230528/7165a115b621449e84478e130c6e5144.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]: /images/20230528/03c6d9a830f248e5a10be484ccdec4c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 5]: /images/20230528/75d25e08cf8b440eb2eb0f3a0a1e0c81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 6]: /images/20230528/38371630d1764f6a80bf93873c98d992.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 7]: /images/20230528/8b7884579f0d4d14a031968729126c68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 8]: /images/20230528/9dc4dde3874648e68993471c320d0d90.png