数据结构 [data structure] (02)

《数据结构 [data structure] (02)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(2)——线性表主讲：骆昊E-mail：help.my.student@gmail.com线性结构线性结构是数据结构中最常见的一类结构线性结构具有以下特点：存在唯一一个被称为“第一个”的数据元素存在唯一一个被称为“最后一个”的数据元素除第一个元素之外，集合中的每个元素均有且仅有一个前驱除最后一个元素之外，集合中的每个元素均有且仅有一个后继线性结构有多种类型：线性表、栈、队列、数组、串线性表的类型定义一个线性表是n个数据元素的有限序列每个数据元素的具体含义在不同的情况下各不相同，可以是一个数字、一个字符，也可以是一个对象在

2、稍复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下，通常把数据元素称为记录(record)，含有大量记录的线性表又称为文件(file)虽然线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同的属性，即属于同一数据对象，相邻元素之间存在着序偶关系线性表的类型定义线性表抽象数据类型ADTList{数据对象：D={ai

3、ai∈Elemset,i=1,2,…,n,n≧0}数据关系：R={

4、ai-1,ai∈D,i=2,…,n}基本操作：Init(&L)操作结果：构造一个空的线性表LDestroy(&L)初始

5、条件：线性表L已经存在操作结果：销毁线性表LClear(&L)初始条件：线性表L已经存在操作结果：将L重置为空表Empty(L)初始条件：线性表L已经存在操作结果：若L为空表，则返回TRUE，否则返回FALSE…………}线性表的类型定义线性表抽象数据类型ADTList{…………Length(L)初始条件：线性表L已经存在操作结果：返回L中数据元素个数Get(L,i,&e)初始条件：线性表L已经存在，i∈[1,Length(L)]操作结果：通过e返回L中第i个数据元素的值Locate(L,e,compare())初始条件：线性表L已经存在，compa

6、re()是数据元素判定函数操作结果：返回L中第一个与e满足关系compare()的数据元素的位置Prior(L,cur_e,&pre_e)初始条件：线性表L已经存在操作结果：若cur_e是L的数据元素，且不是第一个，通过pre_e返回它的前驱，否则操作失败，pre_e无定义…………}线性表的类型定义线性表抽象数据类型ADTList{…………Next(L,cur_e,&next_e)初始条件：线性表L已经存在操作结果：若cur_e是L的数据元素，且不是最后一个，通过next_e返回它的后继，否则操作失败，next_e无定义Insert(&L,i,e)

7、初始条件：线性表L已经存在，i∈[1,Length(L)]操作结果：在L中第i个位置之前插入数据元素e，L的长度加1Delete(&L,i,&e)初始条件：线性表L已经存在，i∈[1,Length(L)]操作结果：删除L的第i个数据元素并通过e返回，L的长度减1Traverse(L,visit())初始条件：线性表L已经存在操作结果：依次对L的每个元素调用函数visit()，如果visit()失败，则操作失败}线性表的类型定义线性表抽象数据类型对于线性表还可以进行一些更复杂的操作，例如：将两个或多个线性表合并成一个线性表；把一个线性表拆分成两个或

8、多个线性表；复制一个线性表等例子：假设利用两个线性表LA和LB表示两个集合A和B，求A和B的并集。可以通过下面的算法实现voidUnion(List&La,ListLb){La_len=Length(La);Lb_len=Length(Lb);for(i=1;i<=Lb_len;i++){Get(Lb,i,e);if(!Locate(La,e,equal)){ListInsert(La,++La_len,e);}}}线性表的类型定义线性表抽象数据类型例子：已知线性表LA和LB中的数据元素按值非递减有序排列，要求将LA和LB归并为一个新的线性表L

9、C，且LC中的数据元素仍然按非递减有序排列。算法如下所示：voidMerge(ListLa,ListLb,List&Lc){Init(Lc);i=j=1;k=0;La_len=Length(La);Lb_len=Length(Lb);while((i<=La_len)&&(j<=Lb_len)){Get(La,i,ai);Get(Lb,j,bj);if(ai<=bj){Insert(Lc,++k,ai);i++;}else{Insert(Lc,++k,bj);j++;}}while(i<=La_len){Get(La,i++,ai);Insert(L

10、c,++k,ai);}while(j<=Lb_len){Get(Lb,j++,bj);Insert(Lc,+