第2章线性表线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。
本章主要介绍线性表的定义、表示和基本运算的实现。
重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。
重点提示：●线性表的逻辑结构特征●线性表的顺序存储和链式存储两种存储结构的特点●在两种存储结构下基本操作的实现2-1 重点难点指导2-1-1 相关术语1．线性表线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,a n)，其中n为表长，n=0时称为空表。
要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。
2．顺序表顺序存储的线性表。
要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。
3．链表用链表存储的线性表。
要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。
4．单链表每个结点除了数据域外还有一个指向其后继的指针域。
要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。
5．头指针要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。
如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。
通常用头指针来惟一标识一个链表。
6．头结点要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。
当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。
7．头结点的作用要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。
2-1-2 线性表的顺序存储1．顺序表顺序存储的线性表称为顺序表。
其特点是：用一组地址连续的存储单元来依次存放线性表的数据元素，因此数据元素的逻辑顺序和物理次序一致（这是顺序存储的核心所在）。
数据结构线性表一、引言数据结构是计算机存储、组织数据的方式，它决定了数据访问的效率和灵活性。
在数据结构中，线性表是一种最基本、最常用的数据结构。
线性表是由零个或多个数据元素组成的有限序列，其中数据元素之间的关系是一对一的关系。
本文将对线性表的概念、分类、基本操作及其应用进行详细阐述。
二、线性表的概念1.数据元素之间具有一对一的关系，即除了第一个和一个数据元素外，其他数据元素都是首尾相连的。
2.线性表具有唯一的第一个元素和一个元素，分别称为表头和表尾。
3.线性表的长度是指表中数据元素的个数，长度为零的线性表称为空表。
三、线性表的分类根据线性表的存储方式，可以将线性表分为顺序存储结构和链式存储结构两大类。
1.顺序存储结构：顺序存储结构是将线性表中的数据元素按照逻辑顺序依次存放在一组地质连续的存储单元中。
顺序存储结构具有随机访问的特点，可以通过下标快速访问表中的任意一个元素。
顺序存储结构的线性表又可以分为静态顺序表和动态顺序表两种。
2.链式存储结构：链式存储结构是通过指针将线性表中的数据元素连接起来，形成一个链表。
链表中的每个节点包含一个数据元素和一个或多个指针，指向下一个或前一个节点。
链式存储结构具有动态性，可以根据需要动态地分配和释放节点空间。
链式存储结构的线性表又可以分为单向链表、双向链表和循环链表等。
四、线性表的基本操作线性表作为一种数据结构，具有一系列基本操作，包括：1.初始化：创建一个空的线性表。
2.插入：在线性表的指定位置插入一个数据元素。
3.删除：删除线性表中指定位置的数据元素。
4.查找：在线性表中查找具有给定关键字的数据元素。
5.更新：更新线性表中指定位置的数据元素。
6.销毁：释放线性表所占用的空间。
7.遍历：遍历线性表中的所有数据元素，进行相应的操作。
8.排序：对线性表中的数据元素进行排序。
9.合并：将两个线性表合并为一个线性表。
五、线性表的应用1.程序语言中的数组：数组是一种典型的顺序存储结构的线性表，常用于存储具有相同类型的数据元素。
第1章概论1.数据、数据元素、数据结构、数据类型的含义分别是什么？数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。
数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。
数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。
数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。
数据类型包含取值范围和基本运算等概念。
2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。
数据的逻辑结构包含下面两个方面的信息：①数据元素的信息；②各数据元素之间的关系。
物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。
数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。
采用不同的存储结构，其数据处理的效率是不同的。
因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。
3.数据结构的主要操作包括哪些？对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有：●创建：建立一个数据结构；●清除：清除一个数据结构；●插入：在数据结构中增加新的结点；●删除：把指定的结点从数据结构中删除；●访问：对数据结构中的结点进行访问；●更新：改变指定结点的值或改变指定的某些结点之间的关系；●查找：在数据结构中查找满足一定条件的结点；●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。
4.什么是抽象数据类型？如何定义抽象数据类型？抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
