考研专业课之统考计算机蓝宝书(2)

来源：跨考网 2008-11-22 21:09

第一章线性表

【考纲解析与应试指导】

线性表一章在线性结构的学习乃至整个数据结构学科的学习中其作用都是非常重要的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念，所以一定搞透彻了。线性表是线性结构的基础，紧接着的栈、队列和数组等都是线性表在运算或者是存储对象上的扩展，树和图是在线性结构一对一关系的基础上变化成一对多和多对多的关系。

线性表一章一般考题以选择题和小分值的综合应用题居多，建议大家注意线性表的两种存储结构以及两种结构之间的对比，尤其是一些线性表的基本操作在单链表或其变形上的实现步骤，能够用线性表的常用操作解决线性表的应用问题。

【核心考点】

线性关系、线性表的定义，线性表的基本操作。

线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。

线性表的应用

【知识点精讲】

1.1 线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为：
(a1，a2，... ai-1，ai，ai+1，...an)
其中n为表长， n＝0 时称为空表。
表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，...，n 时，有且仅有一个直接前趋 ai-1.，当i=1，2，...，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋，an 是最后一个元素无后继。

订阅收藏考研专业课之统考计算机蓝宝书

1.2 线性表的基本操作

数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，因此下面定义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。
线性表上的基本操作有：

(1). 线性表初始化：Init_List(L)
初始条件：表L不存在
操作结果：构造一个空的线性表

(2). 求线性表的长度：Length_List(L)
初始条件：表L存在

操作结果：返回线性表中的所含元素的个数
(3). 取表元：Get_List(L,i)
初始条件：表L存在且1<=i<=Length_List(L)
操作结果：返回线性表L中的第ｉ个元素的值或地址

(4). 按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。
初始条件：线性表L存在
操作结果：在表L中查找值为ｘ的数据元素，其结果返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。

(5). 插入操作：Insert_List(L,i,x)
初始条件：线性表L存在，插入位置正确 (1<=i<=n+1,ｎ为插入前的表长)。
操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, ... , n 的数据元素的序号变为 i+1,i+2, ... , n+1，插入后表长=原表长+1。

(6). 删除操作：Delete_List(L,i)
初始条件：线性表L存在，1<=i<=n。
操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,..., n 的元素变为序号为 i, i+1,...,n-1，新表长＝原表长-1。

1.3 线性表的顺序存储及运算实现

1.3.1 顺序表

线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单，又自然的。如图 2.1 所示。设 a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：
Loc(ai)=Loc(a1)+(i-1)*d 1<=i<=n

这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。

类型定义：
# define MAXSIZE 100
struct LIST {
elementtype elements[MAXSIZE];
int last;};
位置类型：typedef int position;
线性表 L:LIST L;

专业课精选

专业课复习规划专业课知识库专业课真题专业课大纲

教育学统考

心理学统考

西医综合