数据结构第2章线性表

《数据结构第2章线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表1.1线性表的定义和基本操作1.1.2考点精讲1.线性表的定义线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。其中n为表长，当n=0时该线性表是一个空表。若用L命名线性表，则其一般表示如下：L(a,a,,a,a,,a)12ii1n其中，a1是唯一的“第一个”数据元素，又称为表头元素；an是唯一的“最后一个”数据元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。这种线性有序的逻辑结构正是线性表名字的由来。由此，我们得出线性表的特点

2、是：表中元素的个数有限。表中元素具有逻辑上的顺序性，在序列中各元素有其先后次序。表中元素都是数据元素。就是说，每一个表元素都是不可再分的原子数据。表中元素的数据类型都相同。这意味着每一个表元素占有相同数量的存储空间。表中元素具有抽象性。就是说，仅讨论表元素之间的逻辑关系，不考虑元素究竟表示什么内容。注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。2.线性表的基本操作一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可以通过

3、调用其基本操作来实现。线性表的主要操作有：（‘&’表示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)

4、：删除操作。删除表L中第i个位置的元素。PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。Empty(L)：判空操作。若L为空表，则返回true，否则返回false。DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。注意：基本操作的实现取决于采用哪一种存储结构，存储结构不同，实现的算法也不同。1.1.2例题精讲单项选择题1.1.线性表是具有n个（）的有限序列。A.数据表B.字符C.数据元素D.数据项【C】线性表是由数据元素组成的，数据元素是由数据项组成的。2.以下__

5、_____是一个线性表。A．由n个实数组成的集合B．由100个字符组成的序列C．所有整数组成的序列D．邻接表【B】线性表的定义中要求为有限序列，而C中序列中元素个数是无穷多个，因此C错误；而A中指定的是集合（集合中各元素没有前后驱关系），因此A也错误；D是属于存储结构，线性表是一种逻辑结构，不要把二者混淆起来。只有B满足线性表定义的条件。3.在线性表中，除了开始元素外，每个元素_________。A．只有唯一的前趋元素B．只有唯一的后继元素C．有多个前趋元素D．有多个后继元素【A】见考点精讲。1.2线性表的顺序表示1.2.1

6、考点精讲1．顺序表的定义线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。假设线性表L存储的起始位置为LOC(A)，sizeof(ElemType)是每个数据元素所占用存储空间的大小，则表L所对应的顺序存储如图2-1所示。数组下标顺序表内存地址图2-1线性表的顺序存储结构注意，线性表中元素的位序是从

7、1开始，而数组中元素的下标是从0开始的。假定线性表的元素类型为ElemType，线性表的顺序存储类型描述为：#defineMaxSize50//定义线性表的最大长度typedefstruct{ElemTypedata[MaxSize];//顺序表的元素intlength;//顺序表的长度}SqList;//顺序表的类型定义一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将产生溢出，就会导致程序崩溃。而动态分配时，存储数组的空间是在程序执行过程中通过动态

8、存储分配语句分配的，一旦数据空间占满，可以另外再开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的。#defineInitSize100//表长度的初始定义typedefstruct{ElemType*data;//指示动态分配数组的指针intMaxSize,l