Chapter数据架构演示文稿.pptVIP

第二章　线性表 主讲：王攀 wangpan@126.com 目 录 2.1　线性表的类型定义 2.2　线性表的顺序存储结构 2.3　线性表的链式存储结构 2.1　线性表的类型定义 1. 线性表的定义 线性表是n（n≥0）个数据元素a1, a2, …, an组成的有限序列。其中n 称为数据元素的个数或线性表的长度。当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1，a2，ai，…，an），其中的数据元素ai（1≤i≤n）是一个抽象的符号，其具体含义在不同情况下是不同的。 2.1　线性表的类型定义（续） 2. 线性表示例 例1：26个英文字母组成的字母表：（A，B，C，…，Z），是一个线性表，长度为26，其中的每一个字母就是一个数据元素。 例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：（6，17，28，50，92，188）是一个线性表，长度为6，其中的每一个数值就是一个数据元素。 2.1　线性表的类型定义（续） 例3：学生健康情况登记表 2.1　线性表的类型定义（续） 3. 线性表的特征 从线性表的定义可以看出线性表的特征： a.有且仅有一个开始结点（表头结点），它没有直接前驱，只有一个直接后继； b.有且仅有一个终端结点（表尾结点），它没有直接后继，只有一个直接前驱； c.其它结点都有一个直接前驱和直接后继； d.元素之间为一对一的线性关系。 2.1　线性表的类型定义（续） 2.1　线性表的类型定义（续） 4. 线性表的抽象数据类型描述 线性表的抽象数据类型描述为： ADT List { 数据对象：D={ ai| ai∈ElemSet,i=1,2, …, n, n≥0} 数据关系：R={ai-1，ai| ai-1，ai∈D, i=2, …, n} Elemset为某一数据对象集；n为线性表的长度。 基本操作： 1．InitList(L) 2．DestroyList(L) 3．ClearList(L) 2.1　线性表的类型定义（续） 4． ListEmpty(L) 　 5． ListLength(L) 6． GetElem(L, i, e) 7． LocateElem(L, e, compare()) 8． PriorElem(L, cur_e, pre_e) 9． NextElem(L, cur_e, next_e) 10．ListInsert(L, i, e) 11．ListDelete(L, i, e) 12．ListTraverse(L, visit()) }　ADT List 2.1　线性表的类型定义（续） 2.1　线性表的类型定义（续） 2.1　线性表的类型定义（续） 2.1　线性表的类型定义（续） 　while((i=La _ len)(j=Lb _ len)){ 　　GetElem(La, i, ai);GetElem(Lb, j, bj); 　　if(ai=bj) {ListInsert(Lc, ++k, ai); ++i;} 　　else {ListInsert(Lc，++k，bj);++j;} 　　 //将较小的元素插入到Lc的表尾 　} 　while(i=La_len) 　{Getelem((La,i++,ai); ListInsert(Lc,++k,ai);} 　while(j=Lb_len) 　{GetElem((Lb,j++,bj);ListInsert(Lc,++k,bi);} 　//将另一个线性表中剩余元素依次插入 } 2.2　线性表的顺序存储结构 1. 顺序表结构 线性表的顺序存储结构，也称为顺序表。 其存储方式为：在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。 2.2　线性表的顺序存储结构（续） 2.2　线性表的顺序存储结构（续） 2.2　线性表的顺序存储结构（续） 2.2　线性表的顺序存储结构（续） 2.2　线性表的顺序存储结构（续） 2.2　线性表的顺序存储结构（续） 2.2　线性表的顺序存储结构（续） 2. 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的初始化、第i个元素的访问等。 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则第i个元素是L.elem[i-1] 。 ① 初始化：位顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为“0”。 2.2　线性表的顺序存储结构（续） ② 插入运算：线性表的插入运算