第二章 线性表

• • 2.1 线性表相关概念及操作
    • 2.1.1 线性表相关概念
    • 2.1.2 线性表的基本操作
  • 2.2 线性表的顺序表示
    • 2.2.1 顺序表的定义
    • 2.2.2 顺序表上基本操作的实现

• 线性表的定义和基本操作
• 线性表的实现
  • 顺序存储
  • 链式存储
  • 线性表的应用

知识框架

重点

• 考研命题重点
• 代码量少,但是性能要求极高(时间,空间复杂度)
• 基于两种存储结构的各种基本操作
• 可执行性不强求(那肯定语法正确更好),但须尽量表达出算法的思想和步骤

2.1 线性表相关概念及操作

2.1.1 线性表相关概念

1. 线性结构的特点,在数据元素的非空有限集中:
   • 存在惟一的一个被称做“第一个”的数据元素
   • 存在惟一的一个被称做“最后一个”的数据元素
   • 除第一个之外，集合中的每个数据元素均只有一个前驱
   • 除最后一个之外，集合中每个数据元素均只有一个后继。
2. 线性表的定义
   线性表是具有相同数据类型的n(n≥0)个数据元素的__有限序列__，其中__n为表长，当n=0时线性表是一个空表__。若用L命名线性表，则其一般表示为:L=(a₁,a₂,...,a_i+1,...,a_n)式中:
   • a₁是唯一的“第一个”数据元素，又称表头元素；
   • a_n是唯一的“最后一个”数据元素，又称表尾元素。
   • 除第一个元素外，每个元素有且仅有一个直接前驱。
   • 除最后一个元素外，每个元素有且仅有一个直接后继。
     以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。
3. 线性表的特点:
   • 表中元素的__个数有限__。
   • 表中元素具有逻辑上的__顺序性__，表中元素有其先后次序。
   • 表中元素都是数据元素，每个元素都是单个元素。
   • 表中元素的数据类型都相同，这意味着__每个元素占有相同大小的存储空间__。
   • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
4. 注意点
   • 线性表是一种逻辑结构，表示元素之间一对一的相邻关系。
   • 顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

2.1.2 线性表的基本操作

1. 一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。线性表的主要操作如下:

InitList(&L):初始化表。构造一个空的线性表。
Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L，e):按值查找操作。在表L中查找具有给定关键字值的元素。返回i,无返回0(咱-1)
GetElem(L，i):按位查找操作。获取表工中第i个位置的元素的值。
ListInsert(&L，i，e):插入操作。在表L中的第i个位置上插入指定元素e。
Listpelete(&L，i，&e):删除操作。删除表工中第i个位置的元素，并用e返回删除元素的值。
PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L):判空操作。若L为空表，则返回true，否则返回false。
DestroyList(&L):销毁操作。销毁线性表，并释放线性表工所占用的内存空间。

2. 注意:

• 基本操作的__实现取决于采用哪种存储结构__，存储结构不同，算法的实现也不同。
• "&"表示C++中的引用调用。若传入的变量是指针型变量，且在函数体内要对传入的指针进行改变，则会用到指针变量的引用型。在C中采用指针的指针也可达到同样的效果。

2.2 线性表的顺序表示

2.2.1 顺序表的定义

1. 线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表中数据元素,使得逻辑上相邻的两个元素在物理位置上也相邻.
   • 线性表的顺序存储又称__顺序表__
   • 第1个元素存储在线性表的起始位置,也叫__基地址__
   • 第i个元素的存储位置后面紧接着存储的是第i+1个元素，称i为元素a_i在线性表中的位序。假设线性表L存储的起始位置为LOC(A)，sizeof(ElemType)是每个数据元素所占用存储空间的大小，则表L所对应的顺序存储如图;
     
   • 线性表的这种机内表示称作__线性表的顺序存储结构或顺序映像__
   • 顺序表的特点是表中元素的逻辑顺序与其物理顺序相同
   • 线性表中元素的位序是从1开始的,而数组中的元素的下标是从0开始的
2. 顺序表的描述

• 假定线性表的元素类型为ElemType，则线性表的顺序存储类型描述为(静态)

#define MaxSize50//定义线性表的最大长度
typedef struct{
    ElemType data[MaxSize]；//顺序表的元素
    int length；/顺序表的当前长度
}SqList;

• 一维数组可以是静态分配的，也可以是动态分配的。
  • 在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。

#define InitSize 100//表长度的初始定义
typedef struct{
    Elemrype*data；//指示动态分配数组的指针
    int MaxSize，length；//数组的最大容量和当前个数
}SeqList；/动态分配数组顺序表的类型定义

    * C的初始动态分配语句:
    L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
    * C++的初始动态分配语句
    L.data=newElemType(InitSize);

• 由于高级程序语言中的数组类型也有随机存取的特性,因此通常用数组来描述数据结构中的顺序存储结构
• 注意：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时决定。

1. 总结

• 顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。
• 顺序表的存储密度高，每个结点只存储数据元素。
• 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

2.2.2 顺序表上基本操作的实现