数据结构day02

1 线性表的定义和基本操作

1.1 线性表的定义

分析：

1.1.1 问题一：我们为什么探讨线性表的定义和基本操作

在研究数据结构时，需要重点关注三个方面：逻辑结构、物理结构以及数据的运算。在本节内容里，我们首先来介绍线性表的定义与基本操作。实际上，这就是要探究这种数据结构的逻辑结构究竟是怎样的，同时还要探讨针对这种数据结构需要实现哪些基本运算，也就是基本操作。在后续小节中，我们还会深入探讨如何运用不同的存储结构来实现线性表。要知道，当采用不同的存储结构时，数据运算的具体实现方式也会有所不同。这一点，后续我们会通过具体代码，帮助大家加深理解。

分析：

1.1.2 问题2：如何用大白话讲明白线性表的定义？

好了，现在我们先来看看什么是线性表。通俗来讲，线性表指的是各个数据元素之间的逻辑关系，其逻辑结构呈一条线的形态，就如同被串在一起，数据元素之间存在明确的前后顺序。课本中给出了较为严谨的文字定义 ，

1.1.3 问题3：在官方给的线性表定义中，我们需要留意哪些点？

在这个定义中，有几个要点需要我们留意。

第一点：

首先，线性表中的各个数据元素，其数据类型必须相同。例如，如果某个数据元素是int型，那么其他数据元素也都得是int型。当然，你也可以自行定义某种结构类型，比如定义为struct a ，然后将这个自定义的结构类型作为数据元素的数据类型。所有数据元素数据类型相同，这意味着它们所占的存储空间大小是一致的 。 这个特性有助于计算机迅速定位某一具体数据元素。

第二点：

线性表是一个序列，“序”即次序，各个数据元素之间存在明确的前后次序。

第三点

线性表中的数据元素数量是有限的。举个反例，若将所有整数按递增次序排列，这样的数据结构虽满足数据元素类型相同、元素之间有次序这两个特性，但由于整数数量是无限的，所以它并非线性表。

1.1.4 问题4：我们在做题当中，在考察线性表的定义时，还需要注意哪些术语？

（1）线性表的长度 N，我们称之为表长。若表长为 0，这样的线性表就是一个空表。

（2）另外，在描述线性表中的各个数据元素时，角标从 1 开始，A₁表示线性表中的第一个数据元素，A₂是第二个数据元素，Aᵢ 是第 i 个数据元素。我们用“数据元素在线性表中的位序”这一专业术语来描述“第几个”。

（3）线性表中的第一个元素称为表头元素，最后一个元素称为表尾元素。除表头元素外，线性表中的其他所有元素都有一个直接前驱，即排在它们前面的数据元素，这就是前驱的概念 。 除了最后一个元素外，其他每个元素都能直接找到其直接后继，这就是后继的概念。

（4）这里要再次强调位序这个概念，位序是从 1 开始的，但我们在程序中定义数组时，数组下标是从 0 开始的。

分析：

1.1.5 问题5：为什么这样一种线性结构关系要被称作“表”呢？

不知道大家看到“线性表”这个术语时，会联想到什么。对我来说，看到“表”这个字，首先想到的就是类似这样的东西。我刚开始学习的时候就很疑惑，为什么这样一种线性结构关系要被称作“表”呢？其实从线性表的英文术语中就能找到答案。线性表的英文是“linear list”，“linear”意思是“线形的、直线的、线状的”，它由“line”这个单词演变而来，“line”就是“线”的意思，比如大家爱看的《天线宝宝》英文是“Teletubbies” ，其中“skyline”就有“天际线”之意。“list”有“列表”的意思，比如待办事项是“to - do list”，这种列表由一个个元素组成，这就和我们的线性表模样对应上了。所以我觉得它被翻译为“线性表”，可能就是因为“list”本身有“列表”的含义。

换个角度理解，如果一个数据元素包含多个数据项，那么从形式上看，这样的数据结构所保存的内容不就像这样的一张表吗？这就是为什么这种数据结构叫“线性表”，而不是什么“线性串”之类名称的原因。

 1.2 线性表的基本操作

好啦，在认识了线性表的逻辑结构后，咱们来瞧瞧需要对线性表实现哪些基本操作，或者说基本运算。

 分析：

1.2.1 问题6：我们为什么要先了解线性表的初始化和销毁，其次了解插入删除，查找？

首先，要实现的两个基本操作，是初始化一个线性表以及销毁一个线性表。这两个操作实现了线性表从无到有、从有到无的过程，主要工作是分配和释放内存空间，

当然，还得更改一些必要信息。

接下来要实现的基本操作是插入和删除。这里的描述是不是很像函数？这部分是函数名，括号里的是函数参数。这里声明了三个参数，第一个参数 L 代表线性表，第二个参数 i 表示要在线性表的第 i 个位置插入元素，第三个参数 e 则是要插入的元素值。删除操作类似，一个函数名，里面有相应参数。

之后要实现的基本操作是按值查找和按位查找。按值查找，就是给定一个元素 e 的值，在线性表 L 中查找是否有数据元素与传入的参数 e 相同。按位查找呢，就是传入一个参数 i，通过它指明要找的是线性表中的第几个元素。

1.2.2 问题7：我们除了上面的操作方式，还有其他的操作方式吗？

最后，我们还能定义一些其他常用操作。比如定义一个函数 length，传入 L，它会返回线性表 L 的长度；也可以定义一个函数 print_list，传入线性表 L，它会打印输出线性表 L 中所有元素的值。 Emply(L)最后是一个判空操作，传入线性表 L。若线性表为空表，该函数将返回true；若线性表非空，则返回 false。这些基本操作的具体实现，后续会通过具体代码详细讲解，此处我们只需有个大致印象。

1.2.3 问题8：对学习数据结构，有什么好的建议？

这里有几个要点需牢记。

(1)其一，学习任何数据结构时，对其操作基本都逃不开创建、销毁、增删改查，即增加、删除、修改或查询数据元素。学习后续数据结构时，大家也可自行思考，针对特定数据结构，这些操作该如何实现。比如线性表的插入和删除操作，不正是增加和删除数据元素吗？而按值查找和按位查找操作，本质就是查询数据元素。虽说此处未定义修改数据元素值的操作，但修改前必然要先找到目标元素，所以“改”操作的第一步也是“查”。后面这些基本操作是为方便编程实现的，核心还是前面那几个操作。

(2)其二，在 C 语言中定义函数时，需声明函数名，之后还要声明参数列表，包括参数名及其具体类型。 然而，在我们上述描述基本操作的地方，并未明确指出具体的参数类型。因此，此处给出的函数接口实际上具有抽象性。例如，这里的“e”代表数据元素，线性表中存储的数据元素既可以是 int 型变量，也可以是某种 T 类型的变量。所以，我们在阐述这些基本操作时，并未明确参数的具体类型。只有在通过代码实现这些基本操作时，我们才需要真正关注参数的具体类型。

(3)接下来，第三个要点是，在实际开发或做题过程中，大家可根据实际需求定义其他基本操作。倘若你觉得更改某一数据元素的操作十分常用，那么完全可以将其定义为一个基本操作。

(4)最后要提醒大家的是，此处给出的函数名和参数名的命名方式，参考了严蔚敏版的数据结构。由于许多高校指定的考研参考教材都是严蔚敏版的，但大家在自行做题时，不必完全拘泥于这种命名方式，无需过于教条。当然，你所命名的函数和变量，其名称应具备可读性。就像“destroy list”，仅从函数名就能知晓它是用于销毁一个表的。倘若你将销毁操作的函数命名为“A”，谁又能明白这个“A”的用途呢？当然，如果大家在答题时采用此处推荐的命名方式，想必会深受改卷老师的青睐。

(5) 

大家会发现，在某些函数的基本操作中，传入的参数是引用类型，这是 C++ 里的写法。那么，何时需要传入引用型参数呢？先给出结论，稍后再详细解释。如果需要将对参数的修改结果带回来，那就必须传入引用型参数。

下面来看一个具体例子，

1.2.4 问题9：理解什么叫“把修改的结果带回来”。大家可以自己动手编写这段程序。

下面具体看看这个程序。在 main 函数里，首先定义一个变量 X，并赋值为 1，接着使用 printf 输出 X 的值。随后调用 test 函数，将变量 X 作为参数传入。在 test 函数中，把 X 的值修改为 1024，并打印此时 X 的值。当 test 函数运行结束返回 main 函数后，再次打印 X 的值。运行结果是：调用 test 函数前，X 的值为 1；

在 test 函数内部，X 的值被改为 1024；但当 test 函数执行完毕返回 main 函数时，X 的值又变回了 1。 所以在这个地方，test函数虽然对X的值进行了修改，但修改结果并未带回main函数。这背后的原因是什么呢？ 

在main函数中，我们定义了一个初始值为1的变量X。当调用test函数时，test函数里的X实际上是main函数中X的一个复制品。这两个变量虽然都叫X，但在内存中，它们是两份不同的数据。因此，test函数将X的值改为1024，改的只是它自己那份数据。当test函数运行结束回到main函数后，这里打印出的X值依然是1。请仔细体会这句话：对参数的修改结果没有带回来。

好了，接下来我们把参数改成引用类型，即在参数名前面加一个引用符号。看这边的运行结果

 在test函数中把X的值改成了1024，当返回到main函数时，这里打印出的X值同样是1024。

这意味着，如果将参数改成引用类型，test函数中对参数的修改就能被带回到main函数中。简单理解就是，main函数里定义了变量X，这个变量X作为参数传递给了test函数。由于test函数中定义的参数是引用类型，所以test函数操作的参数与main函数里的X是同一份数据。如此一来，test函数中对X的修改，自然也会影响到main函数里X的值。

通过这两个例子，想必大家已经能体会到什么叫“把对参数的修改结果带回来”了。这里要提醒一下，引用类型是 C++ 里的特性，运行这个程序时，需要选择 C++ 编译器，因为 C 语言并不支持这种引用类型。

好了，咱们再回到刚才提到的基本操作。就拿插入操作来说，传入的线性表 L 加了引用符号。这是因为在这个函数里，我们要修改线性表 L 的具体内容，并且希望把修改效果带回去，所以才加了引用符号。大家不妨暂停一下，好好琢磨琢磨，为什么有些地方需要加引用符号，有些地方却不用。从这个角度深入思考，这可是重点内容，只有理解了，才能写出无误的代码。

1.2.5 问题10：在了解了需要实现哪些基本操作之后，我们来探讨一个问题：为什么要实现对数据结构的基本操作呢？

首先，现在的项目大多是大型项目，需要庞大的团队协作编程。如果你是数据结构的定义者，那么你定义的数据结构，得让队友们用起来得心应手。所以，在定义完数据结构后，还得为队友们提供一些方便易用的函数，将这些基本操作以函数的形式封装起来。 第二，将这些基本操作封装成函数后，能避免重复工作。毕竟这些基本操作十分常用，封装成函数后，日后每次使用时，无需重新编写代码，调用一个函数就能解决问题。

大家学习时，一定要时常进行这类深入思考。很多同学学习时，只关注“怎么做”，却不思考“为什么要这么做”。实际上，想明白“为什么”至关重要。只有清楚做一件事的原因和意义，学习时才会更有动力，更加积极主动。这算是与课程内容本身无关的小建议。

总结：

好啦，在这个小节中，我们学习了线性表这种数据结构。它的逻辑结构理解起来并不难，唯一需要留意的是“位序”这个概念。位序指的是一个数据元素在线性表中的位置序号，即位序从 1 开始，而程序中数组的下标是从 0 开始的。所以，若用数组实现线性表，一定要仔细审题。这一点，我们会在后续小节中有更深刻的体会。

在这个小节里，我们还探讨了需要对线性表实现哪些基本操作。基本运算对所有数据结构而言，都是最为重要和核心的部分。基本操作不外乎创建、销毁，以及增、删、改、查，这可以作为大家的思考方向。我们也着重强调了这一点。 有一个极其关键的要点，那就是我们必须清晰理解参数何时需要使用引用类型。此外，还需格外留意，函数和变量的命名务必具备可读性，要让他人一眼就能明白该函数和变量的用途。好了，以上便是本小节的全部内容。

2 顺序表

从逻辑角度而言，线性表的各个元素构成一个有序序列，各数据元素存在先后顺序。这种逻辑结构是我们从人类视角理解所观察到的特性。那么，在计算机中该如何表示这些数据元素之间的逻辑关系呢？

从本节课起，我们将分别介绍如何运用顺序存储和链式存储这两种存储结构来实现线性表。在本小节，我们要学习的顺序表，实际上就是采用顺序存储方式实现的线性表。本小节我们将学习顺序表的定义，了解顺序表的特性，以及掌握如何用代码实现顺序表。下一小节，我们还会探讨基于顺序存储结构，怎样用代码具体实现之前所定义的一些基本操作。

2.1 顺序表的定义

2.1.1问题11：顺序表的定义是什么？如何理解顺序存储？

顺序表是通过顺序存储方式实现的线性表，而顺序存储是指将逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中。这一点在绪论中曾提及，结合这张图，很容易直观理解，数据元素之间的前后关系通过物理内存的连接关系得以体现。

2.1.2问题12.我们如果知道了顺序表中的一个元素的物理存储地址，那下一个元素的存储地址是什么？

我们在之前强调过，线性表中的各个数据元素数据类型相同，即每个数据元素所占内存空间大小一致。所以，若顺序表的第一个数据元素存放地址为某一地址，由于顺序表中各数据元素在物理内存中连续存放，且每个数据元素所占空间大小相等 。 因此，顺序表中第二个数据元素的存放位置，应为顺序表的起始地址加上数据元素的大小；第三个数据元素的存放位置，则是起始地址加上2倍的数据元素大小。

2.1.3问题13：如何得知一个数据元素的大小呢？

C语言提供了一个便捷的关键字“sizeof”，使用时在其后加上小括号，在括号内传入顺序表中存放的数据元素的数据类型即可。

例如，若顺序表中存放的是整数，在“sizeof”括号内填入“int”，就能得到一个int型整数在该系统中所占的内存空间大小。在C语言里，多数情况下，一个int型变量占4个字节。

      2.1.3.1问题13.1 顺序表还能存放更复杂的数据吗？

当然，顺序表还能存放更复杂的数据，比如自定义的结构类型数据。这里定义了一个名为“customer”的结构，其中包含两个整数“nu”和“people”。由于每个整数占4个字节，所以“customer”这种数据类型所占的内存空间大小为8个字节。实际上，无需关心这8个字节是如何计算得出的，只需使用C语言提供的“sizeof”关键字就能轻松获取数据类型的大小。

   2.2 静态分配

接下来，我们看看顺序表的第一种实现方式——静态分配

2.2.1问题14：什么是静态分配？

所谓静态分配，就是采用大家最为熟悉的数组定义方式来实现顺序表。

2.2.1.1 问题14.1 静态数组的特性？

静态数组，其长度一旦确定便不可更改，这是静态数组的特性。

2.2.2 问题15：解释一下上面如图片中顺序表定义的代码？

我们用这样的数据类型来表示顺序表，其中定义了一个长度为“MaxSize”的静态数组，“MaxSize”是通过宏定义的常量。此外，还定义了一个名为“length”的变量，用于表示当前顺序表的实际长度。“MaxSize”的值决定了顺序表最多能存放的数据元素数量，而“length”的值则体现了当前顺序表中已存入的元素个数。

2.2.2.1问题15.1：如何从内存的角度来理解代码？

从内存角度看，当声明一个数组时，实际上是在内存中开辟了一整片连续空间。在我们的代码中，这片连续空间总共可存放10个数据元素。这里数据元素的类型用“element_type”表示，它其实是“element（元素）”的缩写。数据元素的类型可以是“int”型，也可以是用户自定义的更复杂类型，具体取决于顺序表的存储需求。我们用“element_type”表示，是为了让代码更具通用性。 如果大家自行写代码实现，只需将数据元素的具体类型替换“type”即可。我们将顺序表命名为“SqList”，其中“Sq”是“sequence”的缩写。

    

2.2.3问题16：上面的代码是如何给顺序表进行初始化的？

接下来看具体代码。这里定义了一个用于存放整数的顺序表，即数据元素的数据类型为“int”。我们定义了一个名为“data”的静态数组，最多可存放10个数据元素。

定义好这样的数据结构后，在“main”函数里，首先声明一个“SqList”，即声明一个顺序表。执行此代码时，计算机将在内存中为该顺序表分配所需空间。首先是用于存放“data”数组的一整片连续空间，这片空间大小为10乘以每个数据元素的大小。由于这里的数据元素是“int”型，每个数据元素大小为4个字节。除“data”外，还需分配一个用于存放变量“lenth”的空间，其大小同样为4个字节，因为它也是“int”型。

接下来，在代码中实现了一个名为“InitList”的函数，用于对该顺序表进行初始化。 其实这个函数，正是我们上一小节提到的基本运算中的第一个。既然“main”函数调用了“InitList”，接下来就会执行该函数里的代码。

         首先是一个“for”循环，它的作用是将“data”数组中所有数据元素的值设为零，也就是给数据元素设置默认初始值。当然，这一步是可以省略的，稍后再作解释。

        除此之外，还需将“list”的值设为零，因为刚开始顺序表中没有存入任何数据元素，此时顺序表的当前长度应为零。这便是对顺序表的初始化工作。

       

2.2.3.1问题16.1：如果不给“data”数组设置默认初始值，会出现什么情况呢？

我们把这部分代码去掉，即在初始化顺序表时，只设置其内部变量的值。然后在“main”函数里添加一个“for”循环，将“data”数组全部打印出来。打印结果如下：可以看到，“data”数组前面的数据元素都是零，这很正常。但最后两个数据元素却是很奇怪的值。如果大家在自己电脑上运行这段代码，打印出的“data”数组中各元素的值，可能与我的不一样。

出现这种奇怪现象的原因是内存中存在遗留的脏数据。也就是说，当我们声明这个顺序表时，尽管系统在背后为我们分配了一大片内存空间，但这片内存空间之前存储的数据，我们并不清楚。所以，如果不给这些数据元素设置默认值，就可能因之前遗留的脏数据，导致我们的数据中出现一些奇怪的值 。

2.2.3.2问题16.2：如何理解脏数据？

这里重点让大家理解脏数据的概念。由于内存中可能存在脏数据，声明 lengths 变量时，将其初始值设为零这一步绝不能省略，因为无法预知这片内存区域之前存放的数据是什么。有些同学可能会说，C 语言会自动为 int 型变量设置默认初始值为零。但需注意，默认初始值的设置由编译器决定，换一个 C 语言编译器，可能就不会进行这种初始化工作。所以，声明顺序表时，将其初始值设为零是必不可少的。

2.2.3.3问题16.3：数据元素设置默认值这一步其实可以省略，为什么？

不过，刚才提到给数据元素设置默认值这一步其实可以省略。这是因为在内核数里打印顺序表中的内容，这种操作实际上是违规的，我们本就不该以这种方式访问顺序表。要知道，顺序表中定义了一个变量“lenth”，它表示顺序表当前的长度。因此，当我们访问顺序表中的数据元素时，不应从第一个元素一直访问到最后一个元素，而应访问到顺序表中当前实际存储的最后一个元素。由于刚开始“L”的值为零，所以若采用更正规一些的写法，那么“for”循环中的语句将不会被执行。这就是为什么说可以省略给各个数据元素设置默认值这一步，因为按正常的访问方式，我们实际上不应该访问大于顺序表实际长度的那些数据元素。当然，其实更好的做法应该是。 使用基本操作来访问数据元素是最佳方式。回顾上一小节，我们应实现一个名为 GET0 的基本操作，该操作能从线性表 L 中取出第二个元素。

通过刚才的代码，相信大家对顺序表的静态分配实现方式有了更深入的理解。这种实现方式的关键在于定义一个静态数组来存储数据元素。

2.2.3.4问题16.4：接下来思考，如果刚开始声明的数组长度不够，存满了该怎么办？

遇到这种情况，建议直接放弃，因为静态数组一旦声明，其容量就无法改变。 也就是说，为顺序表分配的存储空间是固定不变的，属于静态分配。或许有同学会问：“既然如此，一开始就申请一大片连续的存储空间，把数组长度设置得大一些，不就可以了吗？”然而，这种做法存在明显弊端——太过浪费内存。设想一下，若将数组长度设为 10000，可最终实际仅使用了 10 个元素，这无疑是对内存资源的极大浪费，并非明智之举。

由此可见，静态分配这种实现方式存在一定局限性，主要体现在顺序表的大小和容量无法调整更改

2.2.3.5 问题16.5：若想让顺序表的大小可变，该如何操作呢？

答案是采用动态分配的实现方式。

2.3 动态分配

2.3.1 问题17：若采用动态分配来实现顺序表，我们应该如何操作？

若采用动态分配来实现顺序表，我们需要定义一个指针，使其指向顺序表中的首个数据元素。由于在动态分配方式下，顺序表的容量大小能够改变，因此需要新增一个变量“max_size”，用以表示顺序表的最大容量。除了最大容量，还需使用“next”变量来记录顺序表的当前长度，即顺序表中实际已存放的数据元素个数。

2.3.1.1 问题17.1：malloc 函数的原理是什么？

malloc 函数的作用是申请一整片连续的内存空间。这片内存空间必然有一个起始的内存地址。因此，当 malloc 函数执行完毕后，它会返回一个指向这片存储空间起始地址的指针。

由于这片存储空间是用来存放一个个数据元素的，所以在这里，我们需要将 malloc 函数返回的指针，强制转换为所定义的数据元素数据类型对应的指针。例如，如果顺序表是用来存放整数的，即数据元素为 int 类型，那么在使用 malloc 函数时，就需要将类型指定为 int。

malloc 函数返回的这个内存起始地址的指针，要赋值给顺序表中的 data 指针变量，也就是说，data 指针指向了这片存储空间的起始地址。

另外一个需要注意的点是，既然 malloc 函数是申请一整片连续的存储空间，那么究竟要申请多大的空间呢？这是由 malloc 函数的参数来确定的。看一下左边的 sizeof(element_type)，之前我们讲过，这个式子得出的结果就是一个数据元素所占的存储空间大小。 如果数据元素是 int 类型，其所占空间大小应为四个字节。式子的第二部分是乘以 init_size，init_size 指的是顺序表的初始长度，这里我们将其定义为 10。所以整个式子计算得出的结果，就是存放 10 个 int 型变量所需的存储空间大小。这就是 malloc 函数。

学过 C++ 的同学，可用 new 和 delete 这两个关键字实现类似于 malloc 和 free 的功能。不过，new 和 delete 涉及面向对象相关知识点。为照顾更多跨考同学，后续学习中我们会更多使用 malloc 和 free 这类函数。

接下来，通过一段具体代码看看顺序表动态分配背后的原理

2.3.2问题18：顺序表动态分配背后的原理是什么？

接下来，通过一段具体代码看看顺序表动态分配背后的原理。这里定义了一个顺序表，其数据元素类型为 int 型，data 指针指向顺序表中的第一个数据元素。我们实现了一个 init 函数，用于以动态分配方式初始化顺序表，还实现了一个函数用于动态增加顺序表的长度。在 main 函数里调用这些相关操作。稍后我们来分析其背后的原理。需要注意的是，List 这里使用到了 malloc 函数来增加顺序表的长度 。 这个函数中又用到了 malloc 和 free 这两个函数。malloc 和 free 包含在相应头文件中，所以如果大家自己写代码需要使用这两个函数，得引入这个文件。

接下来分析一下这段代码的运行过程。首先在函数内部声明一个顺序表，执行完这句代码后，计算机将在内存中开辟一小片空间，这片空间用于存放顺序表中的几个变量。其中，size 表示顺序表的最大容量，n 表示当前顺序表中的数据元素个数，而 data 是一个指针变量。

接下来，开始执行定义的基本操作——初始化顺序表。在该函数的第一句，会调用 malloc 函数，此函数将申请一整片连续的存储空间，其大小要能容纳 10 个 int 类型的数据。之后，malloc 函数会返回一个指针，我们将这个指针的类型转换为与此处统一的指针类型，再把 malloc 返回的指针值赋给 data。前面提到过，malloc 返回的是这一整片连续存储空间的起始地址，所以执行完这段代码后，data 指针应指向该位置。 再次强调，需要将 malloc 返回的指针转换为与我们在此处定义的相同类型的指针。

除了 data 指针外，我们还需将顺序表的当前长度 n 设置为零，并将顺序表的最大容量设置为与初始值一致。

接下来，省略一些代码。假设我们往顺序表中插入数据直至填满，此时 n 的值应为 10，size 的值也应为 10。倘若还想存入更多数据，顺序表的大小显然不够了。因此，我们在此实现了一个函数，用于动态增加数组（即顺序表）的长度。

这里有一个参数，它表示需要拓展的长度。我们传入 5，意味着希望顺序表能够再多存储 5 个数据元素。

首先，定义一个指针 p，将顺序表的 data 指针的值赋给 p，即 p 指针与 data 指向同一位置。接下来调用 malloc 函数，该函数的作用是申请一整片内存空间，这片空间的大小要能容纳当前所有数据元素，并且还能再多存储 5 个新的数据元素。当然，这需要乘以每个数据元素的大小 sizeof(element type)，即要使用 sizeof 这个操作符 。 这意味着开辟了一片新空间，这片空间能存储 15 个元素，此前只能存 10 个，现在可多存 5 个。由于 malloc 申请的是另一片内存空间，且这片空间此时尚未存储任何数据。接下来，让 data 指针指向这片新空间，再通过一个循环，将原来内存空间中的数据逐一迁移过来。因为顺序表的最大容量增加了，所以我们要将size的值加5，使其变为15。最后，调用free函数，它会释放T指针所指向的整片存储内存空间，将其归还给系统。

于P变量是函数的局部变量，当函数执行结束后，存储P变量的内存空间会被系统自动回收。这样，通过malloc就实现了动态数据扩展，也就是顺序表的扩展。 由于我们需要将数据复制到新区域，虽然动态分配能让顺序表的大小灵活改变。熟悉 C 语言的同学可能知道一个名为 realloc 的函数，它确实也能实现我们刚才提到的一系列操作和功能。然而，在调用 realloc 函数的过程中，可能会遇到一些意想不到的“坑”。所以，我建议大家最好还是使用 malloc 和 free 这一对函数，因为使用它们能让我们更清晰地理解动态分配背后的运行过程。

好了，我们已经介绍了顺序表的两种实现方式，一是静态分配，二是动态分配。无论采用哪种方式，顺序表都具备以下特性：

2.3.3 问题19：顺序表都具备哪些特性？

其一，随机访问。这意味着在常数级时间复杂度内就能找到指定元素。这是因为顺序表中的数据元素是连续存放的，只要知道第一个数据元素的存储地址，后续数据元素的地址就能迅速算出，所以能在常数时间内找到目标元素。在代码实现中，我们使用数组，通过数组下标就能直接定位到目标元素。当然，系统在背后还进行了计算地址等一系列操作。 其二，存储密度高。顺序表的每个存储节点仅存储数据元素本身。而若采用链式存储，除了存储数据元素，还需耗费一定的存储空间来存放指针等信息，这就是存储密度高的含义。 第三个特点是拓展容量不便。静态分配方式完全无法拓展容量，动态分配方式虽可拓展，但因要将数据复制到新区域，时间复杂度较高。

第四个特点是插入和删除操作不便，需移动大量元素。在下一小节，我们会结合具体代码，让大家对此有更直观的感受。

总结：

好了，本小节介绍了顺序表的定义。顺序表是采用顺序存储方式实现的线性表，这种存储结构决定了逻辑上相邻的数据元素在物理上也相邻。

我们还介绍了顺序表的两种实现方式：静态分配和动态分配。静态分配代码简单，定义一个常见的数组即可。动态分配则需用到 malloc 和 free 这两个函数。malloc 函数可申请一整片内存空间，若当前顺序表容量不足，可用它申请更大的存储空间，将数据元素复制到新区域，再用 free 函数释放原内存区域，归还系统。这两个函数在考研中至关重要，大家务必亲自编写代码，熟悉其用法。

最后，我们介绍了顺序表的几个特点，其中随机访问这一特点尤为重要，它能在 O(1) 的时间复杂度内找到指定元素。 这一美好的特性源于数据元素在内存中连续存放。在下一小节，我们将介绍如何实现顺序表的插入和删除这两个基本操作。届时，大家会更直观地体会到插入和删除数据的不便之处。

好啦，以上就是本小节的全部内容。