线性表A解析ppt课件.ppt

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

1、第1章序论要点回顾数据结构课程——数据结构＋算法＝程序，涉及数学、计算机硬件和软件。数据结构定义——指互相有关联的数据元素的集合，用二元组D_S=(D,S)或S=(D,R)表示。数据结构内容——数据的逻辑结构、存储结构和基本运算抽象数据类型——由用户定义，用三元组ADT=（D，S，P）表示（基本数据类型＋操作）。算法效率指标——时间效率和空间效率1数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构2例：给出自然数(NaturalNumber)的抽象数据类型定义。ADTNatural_Number{objects:一个整数的有序子集合，它开始于0，结束于机器能表示

2、的最大整数(MAXINT)functions:对于所有的x,yNatural_Number；TRUE,FALSEBoolean；+,-,<,==,=，等等，都是可用的服务。Zero()：NaturalNumber返回0IsZero(x)：Booleanif(x==0)返回TRUEelse返回FALSEAdd(x,y)：NaturalNumberif(x+y<=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):NaturalNumberif(x

3、LSESuccessor(x):NaturalNumberif(x==MAXINT)返回xelse返回x+1}Natural_Number3时间复杂度T(n)或空间复杂度S(n)按数量级递增顺序为：复杂度高复杂度低200log2n4例：分析以下程序段的时间复杂度。i=1;while(i<=n)i=i*2;该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。解：分析：显然，语句①的频度是1。即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)算法的时间复杂度是由嵌套最深层语句的频度

4、决定的。设语句2的频度是f(n)，则有：①②5数据结构课程的起点：什么是线性结构？6线性结构的定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为：（a1,a2,……,an）简言之，线性结构反映结点间的逻辑关系是的。特点①只有一个首结点和尾结点；特点②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是------线性表见第2章一对一(1:1)7第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2

5、.4应用举例第2章作业8（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构1.线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点9例1分析26个英文字母组成的英文表是什么结构。（A,B,C,D,……,Z）学号姓名性别年龄班级012002009524刘禹圻男182002级通信0201班012002009613武锐男182002级通信0202班012002009710彭隽男172002级通信0203班012002009801郭芳女182002级

6、通信0204班012002009904张珍珍女182002级通信0205班：：：：：例2分析学生情况登记表是什么结构。分析：数据元素都是同类型（记录），元素间关系是线性的。分析：数据元素都是同类型（字母），元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性！10练：判断下列叙述的正误：1.数据结构是指相互之间存在一种或多种关系的数据元素的全体。2.一维向量是线性表，但二维或N维数组不是。3.“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×××112.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.

7、3顺序表的运算效率分析本节小结作业122.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之：逻辑上相邻的元素，物理上也相邻可以利用数组V[n]来实现。注意：在C语言中数组的下标是从0开始，即：V[n]的有效范围是从V[0]～V[n-1]13线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存