【零基础学数据结构】第3章 线性表---机械工业,陈锐 著...

《【零基础学数据结构】第3章 线性表---机械工业,陈锐 著...》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章线性表线性表是一种最简单的线性结构。线性结构的特点是：在非空的有限集合，只有唯一的第一个元素和唯一的最后一个元素。第一个元素没有直接前驱元素，最后一个元素没有直接后继元素。其它元素都有唯一的前驱元素和唯一的后继元素。线性表可以用顺序存储结构和链式存储结构存储，可以在线性表的任意位置进行插入和删除操作.3.1线性表的概念及运算线性表是一种最简单且最常用的一种线性结构。本节主要介绍线性表的逻辑结构及在线性表上的运算。3.1.1线性表的逻辑结构一个线性表由有限个类型相同的数据元素组成。在这有限个数据元素中，数据元素构成一个有序的序列，除了第一个元素和最后一个元素外，其它元素有唯一的前驱

2、元素和唯一的后继元素。在简单的线性表中，可以把每一英文单词看成是一个线性表。表中的每一英文字母就是一个数据元素，每个数据元素之间存在着唯一的顺序关系。3.1.1线性表的逻辑结构在较复杂的线性表中，一个数据元素可以由若干个数据项组成，如图3.2所示的一个学校的教职工情况表中，一个数据元素由姓名、性别、出生年月、籍贯、学历、职称及任职时间七个数据项组成。这时，数据元素也称为记录。3.1.2线性表的抽象数据类型1．数据对象集合2．基本操作集合3.2线性表的顺序表示与实现要在计算机上实现线性表的操作，必须将其逻辑结构转化为计算机可以识别的存储结构形式。线性表的存储结构主要有两种：顺序存储结构和

3、链式存储结构。本节的主要学习内容包括线性表的顺序存储结构及顺序存储结构下的操作实现。3.2.1线性表的顺序存储结构线性表的顺序存储指的是将线性表中的元素存放在一组连续的存储单元中。这样的存储方式使得线性表逻辑上相邻的元素，其在物理存储单元也是相邻的。采用顺序存储结构的线性表称为顺序表。假设线性表有n个元素，每个元素占用m个存储单元，如果第一个元素的存储位置记为LOC(a1)，第i个元素的存储位置记为LOC(ai)，第i+1个元素的存储位置记为LOC(ai+1)。3.2.1线性表的顺序存储结构线性表的顺序存储结构描述如下。#defineListSize100typedefstruct{D

4、ataTypelist[ListSize];intlength;}SeqList;3.2.2顺序表的基本运算在顺序存储结构中，线性表的基本运算如下。以下算法的实现保存在文件“SeqList.h”中。3.2.2顺序表的基本运算（1）线性表的初始化操作。线性表的初始化就是将线性表初始化为空表，只需要将线性表的长度置为0即可。线性表的初始化实现代码如下。voidInitList(SeqList*L){L->length=0;/*把线性表的长度置为0*/}3.2.2顺序表的基本运算（2）判断线性表是否为空。线性表为空的标志就是线性表的长度length为0。判断线性表是否为空的实现代码如下。in

5、tListEmpty(SeqListL){if(L.length==0)/*判断线性表的长度是否为0*/return1;/*当线性表为空时，返回1；否则返回0*/elsereturn0;}3.2.2顺序表的基本运算（3）按序号查找操作。intGetElem(SeqListL,inti,DataType*e){/*在查找第i个元素之前，判断该序号是否合法*/if(i<1

6、

7、i>L.length)return-1;*e=L.list[i-1];/*将第i个元素的值赋值给e*/return1;}3.2.2顺序表的基本运算（4）按内容查找操作。intLocateElem(SeqListL,Da

8、taTypee){inti;for(i=0;ilength=0;}3.2.3顺序表的实现算法分析在以上顺序表的实现算法中，除了按内容查找运算、插入和

9、删除操作外，其它算法的时间复杂度都为O（1）。在按内容查找算法中，如果要查找的元素在第一个位置，则需要比较一次；如果要查找的元素在最后一个位置，则需要比较n次，n为线性表的长度。3.2.3顺序表的实现算法分析在顺序表的插入算法中，时间的耗费主要集中在移动元素上。如果要插入的元素在第一个位置，则需要移动元素的次数为n次；如果要插入的元素在最后一个位置，则需要移动元素次数为1次；如果插入位置在最后一个元素之后，即第n+1个位置，则需要移动次数为0次