第2章线性表ppt课件.ppt

《第2章线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法信息管理学院李季课前导学2.1线性表的类型定义2.2线性表的顺序表示与实现2.3线性表的链式表示与实现2.4线性表应用：一元多项式的表示及相加2.5顺序表与链表的对比2.6总结与提高第二章线性表【学习目标】了解线性表的逻辑结构特性是数据元素之间存在着线性关系，和计算机中表示线性表可用的存储结构顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。熟练掌握这两类存储结构的描述方法以及线性表基本操作在这两种存储结构上的实现。能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。结合线性

2、表类型的定义增强对抽象数据类型的理解。【重点和难点】链表是本章的重点和难点扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求分清链表中指针p和结点*p之间的对应关系区分链表中的头结点、头指针和首元结点掌握循环链表、双向链表的特点【知识点】线性表、顺序表、链表、单链表、循环链表【学习指南】学习数据结构的目标是为了编出质量更高的程序，因此重在“实践”。本章讨论的线性表是学习的第一种也是最简单的一种数据结构，是整个课程的基础，特别是熟练掌握链表的操作对以后各章的学习将有很大帮助。本章要求完成以下《数据结构C语言版题集》中的算法设计题：2.11，2.12

3、，2.19，2.22，2.24，2.27，2.28，2.38。其中2.11和2.12可以在学完顺序表之后练习其余建议在学完全章的内容之后进行。第1章回顾DataStructure=(D,S)D:数据对象S:元素之间的关系数据类型=(D,P)D:所有性质相同的值的集合P:允许进行的操作ADT=（D，S，P)数据对象数据关系基本操作定义表示实现线性结构数据元素之间存在着一个对一个的关系bindevetclibuser线性结构的特点线性结构的特点在数据元素的非空有限集中，存在唯一一个被称做“第一个”的数据元素；存在唯一一个被称做“最后一个”的数据元素；除第一个

4、数据元素之外，每个元素都只有一个前驱；除最后一个数据元素之外，每个元素都只有一个后继。2.1线性表的类型定义(LinearList)定义一个线性表是n个数据元素的有限序列(a1,a2,…,ai,…,an)例：英文字母表（A,B,C,…..Z)是一个线性表例：学号姓名年龄001张三18002李四19………数据元素2.线性表的特征元素个数n==表长度当n=0时称为空表i为ai在线性表中的位序（1≤i≤n），当1

5、t{数据对象：D＝{ai

6、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{

7、ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：（1）结构初始化InitList(&L)操作结果：构造一个空的线性表L。（2）销毁结构DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。（3）引用型操作ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表

8、，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤Leng

9、thList(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit())//线性表遍历初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（4）加工型操作ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,

10、&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：L中