全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构题库 典型题(线性表)【圣才出品】
- 格式：pdf
- 大小：744.72 KB
- 文档页数：21
第2章线性表
2.1 考点归纳
【考纲指定考点】
【题型及考点分析】
本章是考研的重点章节，从历年的考研真题来看，考查的题型主要以选择题和算法设计题为主，考查的重点顺序表以及单链表的基本操作。
一、线性表的定义和操作
1．线性表的定义
线性表（Linear List）是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。
该序列中的所有结点具有相同的数据类型。
其中数据元素的个数n称为线性表的长度。
当n＝0时，称为空表。
当n＞0时，将非空的线性表记作：L＝（a1，a2，…，an），其中a1称为线性表的第一个（首）结点，an称为线性表的最后一个（尾）结点。
a1，a2，…ai－1都是ai（2≤i≤n）的前驱，其中ai－1是ai的直接前驱；ai＋1，ai＋2，…，an都是ai（1≤i≤n－1）的后继，其中ai＋1是ai的直接后继。
2．线性表的基本操作
一个数据结构的基本操作是指其最核心、最基本的操作。
其它较为复杂的操作可以通过调用基本操作来实现。
线性表的主要操作如下：
InitList（&L）初始化线性表：构造一个空的线性表L。
DestroyList（&L）销毁线性表：释放线性表L占用的内存空间。
ListEmpty（L）判断线性表是否为空表：若L是空表，则返回真，否则返回假。
ListLength（L）求线性表长度：返回L中元素的个数。
DispList（L）输出线性表：当线性表L不为空时，顺序显示L的各结点的值域。
GetElem（L，i，&e）求线性表L中指定位置的某个元素：用e返回L中第i（1≤i≤ListLength （L））个元素的值。
LocateElem（L，e）定位查找：返回L中第1个值域与e相等的为序。
不存在则返回0。
ListInsert（&L，i，e）插入数据元素：在L的第i（1≤i≤ListLength（L）＋1）个元素之前插入新的元素e，L的长度增加1。
ListDelete（&L，i，&e）删除数据元素：删除L的第i（1≤i≤ListLength（L））个元素，并用e返回其值，L的长度减少1。
二、线性表的实现
1．顺序存储
（1）线性表的顺序存储结构
线性表的顺序存储结构就是把线性表的结点按逻辑顺序依次存放在一块地址连续的存储单元里。
用这种方法存储的线性表简称顺序表。
顺序存储的线性表的特点：
①线性表的逻辑顺序与物理顺序一致。
②数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。
假设线性表存储的起始位置是LOC（A），元素类型为ElemType，则每个元素所占用存储空间的大小（即字节数）为sizeof（ElemType），整个线性表所占用存储空间的大小为n*sizeof（ElemType），其中，n表示线性表的长度。
线性表的存储如图2-1所示。
图2-1 线性表的顺序存储结构
ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。
在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线性表中的所有元素和定义一个整型变量来存储线性表的长度。
假定数组用data[MaxSize]表示，长度整型变量用length表示，并采用结构体类型表示，则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下：
其中，Elem_array成员存放元素，length成员存放线性表的实际长度。
（2）顺序表的基本操作
由于顺序表的操作比较简单，在这里只给出建立、插入、删除和按值查找的操作的算法。
①建立顺序表
其方法是将给定的含有n个元素数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。
算法如下：
②插入操作
该运算在顺序表L的第i个位置（1≤i≤ListLength（L）＋1）上插入新的元素e。
思路：如果i值不正确，则显示相应错误信息；否则将顺序表原来第i个元素及其后面元素均后移一个位置，腾出一个空位置插入新元素，顺序表长度增1。
在线性表L中的第i个位置插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中的第i个位置插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi＝1/（n＋1），而插入时移动结点的次数为n－i＋1。
总的平均移动次数：
即在顺序表上做插入运算，平均要移动表上一半结点。
当表长n较大时，算法的效率相当
低。
因此算法的平均时间复杂度为O（n）。
③删除操作
删除顺序表L中的第i（1≤i≤ListLength（L））个元素。
思路：如果i值不正确，则显示相应错误信息；否则将线性表第i个元素及其后面元素均向前移动一个位置，这样覆盖了原来的第i个元素，达到删除该元素的目的，最后顺序表长度减1。
删除线性表L中的第i个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。
设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则。
