数据结构与算法(二) 线性表一

线性表：

定义：由零个或多个数据元素组成的有限序列。

• 首先他是一个序列，也就是说元素之间是有先来后到
• 若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继
• 另外，线性表强调是有限的。

数学语言的定义：

若将线性表记为(a1，...，ai-1，ai，ai+1，...an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。

所以线性表元素的个数n定义线性表的长度，当n=0是，则称为空表

例如：公司的组织架构是否属于线性关系?  否

抽象数据类型：

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

例如很多编程语言的整型，浮点型，字符型这些指的就是数据类型。

例如在C语言中，按照取值的不同，数据类型可以分为两类：

原子类型：不可以在分解的基本类型，例如整型、浮点型、字符型等。

结构类型：由若干个类型组合而成的，是可以在分解的，例如整型是由若干个整型数据组成的

抽象：是指抽取的事务具有普遍性的本质。他要求抽出问题的特征而忽略非本质的细节，是对具体事物的一个概括，抽象是一种思考问题的方式，它隐藏了繁杂的细节。

我们对已有的数据类型进行抽象，就有了抽象数据类型。

抽象数据类型是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

例如：1+1=2，在不同CPU的处理上可能不一样，但由于其定义的数学特性相同，所以在计算机编程者来看，他们都是相同的。

 "抽象"的意义在于数据类型的数学抽象特性。

而且，抽象数据类型不仅仅是指那些已经定义并实现的数据类型，还可以是计算机编程者在设计软件程序时自己定义的数据类型。

 抽象数据类型的标准格式：

ADT 抽象数据类型名

Data

　　数据元素之间逻辑关系的定义

Operation

　　操作

endADT 

 线性表的抽象数据类型

线性表的抽象数据类型定义：

ADT 线性表（List）

Data

线性表的数据对象集合为{a1,a2,...,an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个

元素有且只有一个直接前驱元素，除了最后一个元素an之外，每一个元素有且只有一个直接后继元素。

数据元素之间的关系是一对一的关系

 Operation

 InitList(*L):初始化操作，建立一个空的线性表L。

ListEmpty(L):判断线性表是否为空表，若线性表为空，返回true，否则返回false。

ClearList(*L):将线性表清空。

GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e。

LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查考成功，返回该元素在表中序号表示成功；否则，返回0表示失败。

ListInsert（*L,i,e):在线性表L中第i个位置插入新元素e。

ListDelete(*L,i,*e):删除线性表L中第i个位置元素，并用e返回其值。

ListLength(L):返回线性表L的元素个数。

endADT‘

对于不同的应用，线性表的基本操作是不同的，上述操作时最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现

 例如集合A{A,C,D}，集合B{A,C,W}，

 其实仔细思考一下，我们只需要循环遍历集合B中的每个元素，判断当前元素是否在A中，若不存在，则插入A中即可。

需要的基本操作组合：ListLength(L);GetElem(L,i,*e);LocateElem(L,e);ListInsert(*L,i,e);

//La表示A集合，Lb表示B集合

void unionL(List *La,list Lb)

{

　　int La_len,Lb_len,i;

　　ElemType e;

　　La_len=ListLength(*La);

　　Lb_len=ListLength(Lb);

　　for(i=1;i<Lb_len;i++)
　　{
　　　　GetElem(Lb,i,&e);
　　　　if(！LocateElem(*La,e))
　　　　{
　　　　　　ListInsert(La,++La_len,e);
　　　　}
　　}
}

我们可以想象，线性表有两种物理存储结构：顺序存储结构和链式存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

线性表（a1,a2,...,an）的顺序存储如下：

线性表顺序存储结构代码：

#define MAXSIZE 20

typedef int ElemType;

typedef struct

{

　　ElemType data[MAXSIZE];

　　int length;//线性表当前的长度

} SqList;

这里我们封装了一个结构，事实上就是对数组进行封装，增加当前长度的变量。

 总结：顺序存储结构封装需要三个属性：

• 存储空间的起始位置，数组data，它的存储位置就是线性表存储空间的存储位置。
• 线性表的最大存储容量：数组长度MAXSIZE.
• 线性表的当前长度：length.

注意：数组的长度与线性表的当前长度需要区分：数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会发生变化的。

地址计算方法：

数组是从0开始计算，而线性表是从1开始

 假设ElemType占用的是c个存储单元（字节），那么线性表中第i+1个数据元素和第i个数据元素的存储关系是（LOC表示获得存储位置的函数）：LOC(ai+1)=LOC(ai)+c

 所以对于第i个数据元素ai的存储位置可以由a1推算得出：LOC(ai)=LOC(a1)+(i-1)*c

 根据这个公式，我们可以计算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间，那么它的存储时间性能当然就为O(1)，我们通常称为随机存储结构。

例如：实现GetElem的具体操作，即将线性表L中的第i个位置元素值返回，注意返回类型Status是一个整型

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedef int Status;

//Status是函数的类型，其值是函数结果的状态代码，如OK等。

//初始条件：顺序线性标L已经存在，1<=i<=ListLength(L)

//操作结果：用e返回L中第i个数据元素的值。

Status GetElem(SqList L,int i,ElemType *e)

{

　　if(L.length==0||i<1||i>L.length)

　　{

　　　　return ERROR;

　　}

　　*e=L.data[i-1];

return OK;

}

 插入操作：

线性表的顺序存储结构具有随机存储结构的特点，时间复杂度为O(1)。

如果要实现ListInsert(*L,i,e)，既在线性表L中的第i个位置插入新元素e，代码如何实现。

 实现插入操作的思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表的长度大于等于数组长度则抛出异常或动态增加数组容量；
• 从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置；
• 将要插入的元素填入第i个位置；
• 线性表长度+1；

/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L),*/

/*操作结果：在L中第i个位置之前插入新的数据元素e，L长度+1*/

Status ListInsert (SqList *L,int i,ElemType e)

{

　　int l;

　　if(L->length==MAXSIZE)//顺序线性表已满

　　{

　　return ERROR;

　　}

　　if(i<1||i>L->length+1)//当i不在范围内时

　　{

　　return ERROR;

　　}

　　if(i<=L-<length)//若插入数据位置不在表尾

　　{

//若要插入数据，则向后移动一位

　　　　for(k=L->length-1;k>=i-1;k--)
　　　　{

　　　　 L->data[k+1]=L->data[k];

　　　　}
　　}

L->data[i-1]=e;

L->length++;

return OK;

}

上海华颂商旅汽车租赁服务有限公司