数据结构与算法--顺序表

约定不等于承诺〃 2022-12-20 02:19 73阅读 0赞

### 目录 ###

*  1、内存、类型本质、连续储存recv
 *  2、基本顺序表与元素外围顺序表
 *  3、顺序表的一体式结构与分离式结构
 *   *  顺序表的结构
     *  顺序表的实现方式
     *  元素存储区替换
     *  元素存储区扩充

# 1、内存、类型本质、连续储存recv #

**内存**：计算机的内存是真正用来存放数据，并且直接和CPU打交道的。  
CPU读取内存。存储单元  
是内存的基本单位是以一个字节作为索引单位的。一个字节是8位。  
告诉cpu到哪个位置取数。  
**内存是什么样的模型呢？**  
内存是一个连续的存储空间。对连续的存储的空间中，它是由基本的单元存储到一块的，基本的单位代表的就是一个字节，它把一个字节作为一个标识，一个字节的8位整体会有一个地址的标识。如果你告诉计算机去0XO1去找的时候，计算机能找到这个计算机所标识的0X01的存储空间，一下子能读出8位来。  
换言之，计算机去标识的时候，是按照一个存储单元去标识的。在存储数据的时候，就需要多个存储单元存放到一起，如果这个时候，有一个基本类型是整形，那整形要占多少位呢？占多大呢？现在有类型的概念了吧。类型到底是什么概念呢？它的本质是什么呢？它决定了，比如说，有一个整形数据的话，我在内存中到底要申请多少个存储单元来把这个数给存起来（也就是整形要占据多少个存储单元），这是我需要解决的问题。对于32位机器来说，普通的整形是需要存储四个字节的，也就是说它要占据4个单元。比如说 int a=1，要把这个存储起来，首先转为二进制0000 0001，现在是两个字节，要将它变成四个字节（0000 0000 0000 0001）存储到计算机内存中。如下图所示：每一个小格代表一位，八位代表一个字节，对应一个地址标识。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 1]

char（ 在python中没有）可以理解为字符串中的一个字符，（字符串是一堆字符组合到一起的，实际上，字符串已经是一个集合了，在往下分，就是一个一个的字符了），一个char就占据一个字节，也就是一个存储单元。int和char类型不同，就意味着在存储空间所占据的大小是不一样的。  
**类型第一个本质：它决定了在计算机内存当中占据多少个内存单元。**  
**第二点**，从取得角度考虑，这个时候，假如说还是上图得四个单位，也就是有四个地址（），我一次把这四个地址的所有数据取出来了，对于计算机来说，它一次性取出来了32位的二进制数据，那它如何对待这个数据呢？你是把它当作整数来对待还是一个字符来对待呢？这也是类型要来决定的。如果存储的告诉你是int，那么取出来四个存储单元的数据当一个整体来处理，如果是char，就当四个char来对待。这也是类型要告诉计算机内存的。**计算机在拿到二进制数据的时候，如何对待它的问题**。  
变量类型的概念。  
所有的高级的数据结构。都是由这些基本类型组成的，这些基本类型就会涉及到这里面的内存到底怎么存。

# 2、基本顺序表与元素外围顺序表 #

int = 1, 2, ,3 这是一个集合，那么如何存储它呢？  
如果只是 1， 2， 3 这三个是没有关联的，那么存储就没有太大关联，但现在这个时候，这三个数是一组数据，有关联的，那有木有一种方式把它存储起来呢？最直观的，就是连续的存储起来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 3]  
如果我需要取出第三个数字，第一个位置存储的7，它的地址是0X01,第一个元素的起始位置，加上2\*4，就是第三个元素的位置。换言之，第一个元素起始位置加上偏移就是需要寻找的地址。

顺序表：它存储的是，有一个类型，它的基本类型是相同的。  
比如说Li = \[200， 390， 78， 121112\]，四个整型，（32位的操作系统，一个整型就占据4个字节，也就是三个存储单元），我就想操作系统申请16个字节（存储空间），操作系统一次返回的，这个空间是连续的，不是分散的，返回的是第一个元素的起始地址（最小标识单位是一个字节，也就是8位）。Li代表的就是起始地址。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 5]  
上面是基本形式。下面来引入其他形式–>元素外置。  
基本数据类型不一样时候，就不能用上面的方式了。  
比如 li =\[12, ‘ab’\]，12需要4个字节，‘ab’需要2个字节。  
存储单元都有一个编号，就是地址，地址本身也是一个数据，对于32位的机器，会用4个字节来存储一个地址，无论是存储12还是“ab”，都会有一个地址来对应，存储占据的存储空间是。

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

# 3、顺序表的一体式结构与分离式结构 #

## 顺序表的结构 ##

一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 7]

## 顺序表的实现方式 ##

顺序表的两种基本实现方式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 8]  
图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。  
一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。  
图b为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 11]

## 元素存储区替换 ##

一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。

分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

## 元素存储区扩充 ##

采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

**扩充的两种策略**

*  每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。  
    特点：节省空间，但是扩充操作频繁，操作次数多。
 *  每次扩充容量加倍，如每次扩充增加一倍存储空间。（**用空间换时间**）  
    特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e602ab24203245239fd2d7eb84696ac1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/9667b77c4baa47fbb7d899b7da3b53d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201110084755217.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/2020111008484639.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201110090348524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/2020111009053477.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201110093852959.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20201110094746894.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/20201110095023532.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/20201110095536588.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20201110100605588.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20201110100620903.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NNRjA1MDQ=,size_16,color_FFFFFF,t_70#pic_center