零基础学数据结构-第3章-线性表培训讲学.ppt

《零基础学数据结构-第3章-线性表培训讲学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、零基础学数据结构-第3章-线性表3.1线性表的定义及抽象数据类型我们学过的英文单词就是简单的线性表，例如，“China”、“Science”、“Structure”。其中每一个英文字母就是一个数据元素，每个数据元素之间存在着唯一的顺序关系。如“China”中字母’C’后面是字母’h’，字母’h’后面是字母’i’。在较为复杂的线性表中，一个数据元素可以由若干个数据项组成，在表3.1所示的一个学校的教职工情况表中，数据元素也称为记录。表3.1教职工情况表3.1线性表的定义及抽象数据类型3.1.2线性表的抽象数据类型线性表的抽象数据类型包括数据对象集合和基本操作集合。1．数据对象集合线性表的数据

2、对象集合为{a1，a2，…，an}，元素类型为DataType。数据元素之间的关系是一对一的关系。除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。3.1线性表的定义及抽象数据类型2．基本操作集合（1）InitList(&L)：初始化操作，建立一个空的线性表L。（2）ListEmpty(L)：若线性表L为空，返回1，否则返回0。（3）GetElem(L,i,&e)：返回线性表L的第i个位置元素值给e。（4）LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功返回该元素在表中的序号表示成功，否则

3、，返回0表示失败。（5）InsertList(&L,i,e)：在线性表L中的第i个位置插入新元素e。（6）DeleteList(&L,i,&e)：删除线性表L中的第i个位置元素，并用e返回其值。（7）ListLength(L)：返回线性表L的元素个数。（8）ClearList(&L)：将线性表L清空。3.2线性表的顺序表示与实现线性表的存储结构主要有两种：顺序存储结构和链式存储结构。3.2.1线性表的顺序存储结构线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。线性表中第i+1个元素的存储位置LOC(ai+1)和第i个元素的存储位置LOC(ai)之间满足以下关系

4、：LOC(ai+1)=LOC(ai)+m第i个元素的存储位置与第一个元素a1的存储位置满足以下关系：LOC(ai)=LOC(a1)+(i-1)*m其中，第一个元素的位置LOC(a1)称为起始地址或基地址。3.2线性表的顺序表示与实现线性表的这种机内表示称为线性表的顺序存储结构或顺序映像，将这种方法存储的线性表称为顺序表。顺序表具有以下特征：逻辑上相邻的元素，在物理上也是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数（见图3.2）。只要确定了第一个元素的起始位置，线性表中的任一元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存

5、储结构。3.2线性表的顺序表示与实现顺序表的存储结构描述如下。#defineListSize100typedefstruct{DataTypelist[ListSize];intlength;}SeqList;其中，DataType表示数据元素类型，list用于存储线性表中的数据元素，length用来表示线性表中数据元素的个数，SeqList是结构体类型名。3.2线性表的顺序表示与实现3.2.2顺序表的基本运算（1）初始化线性表。voidInitList(SeqList*L)/*初始化线性表*/{L->length=0;/*把线性表的长度置为0*/}（2）判断线性表是否为空。intList

6、Empty(SeqListL)/*判断线性表是否为空，线性表为空返回1，否则返回0*/{if(L.length==0)/*线性表的长度若为0*/return1;/*返回1*/else/*否则*/return0;/*返回0*/}3.2线性表的顺序表示与实现（3）按序号查找。先判断序号是否合法，如果合法，把对应位置的元素赋给e，并返回1表示查找成功；否则，返回-1表示查找失败。按序号查找的算法实现如下。intGetElem(SeqListL,inti,DataType*e)/*查找线性表中第i个元素。查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败。*/{if(i<1

7、

8、i>L.

9、length)/*判断该序号是否合法*/return-1;*e=L.list[i-1];/*将第i个元素的值赋值给e*/return1;}3.2线性表的顺序表示与实现（4）按内容查找。从线性表中的第一个元素开始，依次与e比较，如果相等，返回该序号表示成功；否则，返回0表示查找失败。intLocateElem(SeqListL,DataTypee)/*查找线性表中元素值为e的元素*/{inti;for(i=0;i