王道考研系列：2013年数据结构联考复习指导(chater2).pdf

第2 章 线性表 【大纲考点】 （一）线性表的定义和基本操作 （二）线性表的实现 顺序存储；链式存储；线性表的应用 【考题分析】 年份 单选题/分 综合题/分 考查内容 2009 年 0 1 题×15 查找链表中倒数第k 个结点 20 10 年 0 1 题×13 将数组中的序列循环左移 2011 年 0 1 题×15 求两个有序顺序表的中位数 2012 年 0 1 题×13 求两个单链表的公共结点 线性表是考研命题的重中之重，近4 年的算法设计题都是基于线性表的（顺序表或单链 表），这类算法题往往要求具有最优的性能（时间复杂度和空间复杂度），才能获满分。因此， 应牢固掌握线性表的各种基本操作（基于两种存储结构），读者在平时的学习中应多注重积累 和培养动手能力。另外，需要提醒的是，算法最重要的是思想，在考场上的时间有限，在试 卷上答题不一定要求结果具有实际的可执行性，因此不应过于拘泥每一个细节。 2.1 线性表的定义和基本操作 2.1 线性表的定义和基本操作 2.1.1 考点精析 1．线性表的定义 线性表是具有相同数据类型的n （n ≥0 ）个数据元素的有限序列。其中n 为表长，当n=0 时该线性表是一个空表。若用L 命名线性表，则其一般表示如下： L=(a ，a ， ，a ，a ， ，a ) 1 2  i i+1  n 其中，a1 是唯一的 “第一个”数据元素，又称为表头元素；an 是唯一的 “最后一个”数据元 素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素 外，每个元素有且仅有一个直接后继。这种线性有序的逻辑结构正是线性表名字的由来。 由此，我们得出线性表的特点如下：  表中元素的个数有限。  表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后次序。  表中元素都是数据元素。就是说，每一个表元素都是不可再分的原子数据。  第2 章 线性表  表中元素的数据类型都相同。这意味着每一个表元素占有相同数量的存储空间。  表中元素具有抽象性。就是说，仅讨论表元素之间的逻辑关系，不考虑元素究竟表 示什么内容。 注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存 储结构，两者属于不同层面的概念，因此不要将其混淆。 2 ．线性表的基本操作 一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可以通过调 用其基本操作来实现。线性表的主要操作如下 （‘’表示C++中的引用，为方便理解，可以 认为加是为了在操作中达到修改L 的目的）： InitList(L) ：初始化表。构造一个空的线性表。 Length(L) ：求表长度。返回线性表L 的长度，即L 中数据元素的个数。 LocateElem(L, e) ：按值查找操作。在表L 中查找具有给定关键字值的元素。 GetElem(L, i) ：按位查找操作。获取表L 中第i 个位置的元素的值。 ListInsert(L, i, e) ：插入操作。在表L 中第i 个位置上插入指定元素。 ListDelete(L, i) ：删除操作。删除表L 中第i 个位置的元素。 PrintList(L) ：输出操作。按前后顺序输出线性表L 的所有元素值。 Empty(L) ：判空操作。若L 为空表，则返回true ，否则返回false 。 DestroyList(L) ：销毁操作。销毁线性表，并释放线性表L 所占用的内存空间。 注意：基本操作的实现取决于采用哪一种存储结构，存储结构不同，实现的算法也不同。 2.1.2 试题精选 一、单项选择题 1．线性表