第三章线性表

1、第三章 线 性 表西南林学院计算机与信息科学系董跃宇内容提要n线性结构的特点n抽象数据类型的表示与实现n三种主要存储结构线性结构的特点n存在唯一的“第一个”数据元素n存在唯一的“最后一个”数据元素n除了第一个元素外，每个元素均只有一个前驱n除最后一个之外，每个数据元素均只有一个后继线性表的类型定义n线性表是最常见最简单的一种数据结构，是 n 个数据元素的有限序列n线性表中的数据元素可以是各种各样的n线性表中数据元素的个数叫做线性表的长度，长度为零称为空表n可对线性表的元素进行访问，还可以进行插入和删除等线性表的类型定义nADT List数据对象：D=ai | ai 属于ElemSet , i=

2、1,2,n,n=0数据关系：R1= | ai-1,ai属于D,i=2,n基本操作：InitList(L)DestroyList(L)ClearList(L)ListEmpty(L)ListLength(L)GetElem(L,i, e)LocateElem(L,e,compare()PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,&e)ListDelete(&L,i,&e)ListTraverse(L,visit()ADT List数据对象数据关系一组数据结构数据结构程序算法结构?操作线性表的顺序表示和实现ab

3、cdefgabcdefg何谓顺序结构？n顺序映射逻辑结构中相邻的元素，在物理结构中亦相邻n物理结构的组织方式是顺序的C语言虚拟机上顺序结构的实现n静态顺序结构q简单讲，即采用数组作为物理存储结构n动态顺序结构q借助内存分配函数获得连续的存储空间作为物理存储结构静态顺序存储7abcdefg动态顺序存储abcdefgelem79顺序存储结构上的操作实现n操作定义源自数据结构本身，操作的实现细节则受制于数据结构的物理结构n以PriorElem(),NextElem(),ListInsert(),ListDelete()为例PriorElem()的实现abcdefgabcdefgCur_elem:ar

4、ray4array4 不是第一个元素pri_elem:array4-1NextElem()的实现abcdefgabcdefgCur_elem:array4array4 不是最后一个元素next_elem:array4-1ListInsert()的实现abcdefgabcdefgzListDelete()的实现abcdefgabcdefg链式存储结构abcdefgnullheadabcdefg0001010000110031014100801102链式存储结构与顺序存储结构的简单比较abcdefgnullheadabcdefg0001010000110031014100801102abcdefg

5、0009001300170021002500290033链式存储结构上的操作实现n操作定义源自数据结构本身，操作的实现细节则受制于数据结构的物理结构n以PriorElem(),NextElem(),ListInsert(),ListDelete()为例NextElem()abcdefgnullheadabcdefgcur_elemcur_elemnextPriorElem()abcdefgnullheadabcdefgcur_elem第四个第三个pri_elemListInsert()abcdefgnullheadabcdefgzzListDelete()abcdefgnullheadabcdefg一个一般性结论n顺序结构简单清晰，易于实现随机访问但在插入删除时需进行大量的数据移动，效率不佳n链