数据结构.ppt

第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章排序目录数据结构课程的起点数据结构课程的起点什么是线性结构? 线性结构的定义: 若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为:( a 1 , a 2 , ……, a n) 简言,线性结构反映结点间的逻辑关系是。特点①只有一个首结点和尾结点; 特点②除首尾结点外,其他结点只有一个直接前驱和一个直接后继。线性结构包括: 线性表、堆栈、队列、字符串、数组等,其中最典型、最常用的是------ 线性表线性表一对一(1:1) 第第2 2章章线性表线性表 线性表的逻辑结构线性表的逻辑结构 线性表的顺序表示和实现线性表的顺序表示和实现 线性表的链式表示和实现线性表的链式表示和实现 应用举例应用举例(a 1, a 2, …a i-1 ,a i, a i+1,…, a n) 线性表的逻辑结构线性表的逻辑结构线性表的定义: 线性表的定义: 用数据元素的有限序列表示 n=0 时称为数据元素线性起点 a i的直接前趋 a i的直接后继下标, 是元素的序号,表示元素在表中的位置 n 为元素总个数,即表长。 n n≥≥0 0空表线性终点( ( A, B, C, D, A, B, C, D, ………… , Z , Z ) ): : : : : : : : : : 2003 2003 级电信科级电信科 0305 0305 班班 19 19 男男王王春春 0********** 0********** 2003 2003 级电信科级电信科 0304 0304 班班 19 19 男男薛薛荃荃 0********** 0********** 2003 2003 级电信科级电信科 0303 0303 班班 19 19 男男王王泽泽 0********** 0********** 2003 2003 级电信科级电信科 0302 0302 班班 18 18 女女赵玉凤赵玉凤 0********** 0********** 2003 2003 级电信科级电信科 0301 0301 班班 19 19 男男陈建武陈建武 0********** 0********** 班级班级年龄年龄性别性别姓名姓名学号学号例2 分析学生情况登记表是什么结构。分析: 数据元素都是同类型( 记录),元素间关系是线性的。分析: 数据元素都是同类型( 字母), 元素间关系是线性的。注意:同一线性表中的元素必定具有相同特性注意:同一线性表中的元素必定具有相同特性! ! 例1 分析 26 个英文字母组成的英文表是什么结构。““同一数据逻辑结构中的所有数据元素都具有相同的同一数据逻辑结构中的所有数据元素都具有相同的特性特性””是指数据元素所包含的是指数据元素所包含的数据项的个数数据项的个数都相等。都相等。× 是指各元素具有相同的数据类型是指各元素具有相同的数据类型试判断下列叙述的正误: 线性表的顺序表示和实现线性表的顺序表示和实现 顺序表的表示 顺序表的实现 顺序表的运算效率分析 顺序表的表示顺序表的表示用一组用一组地址连续地址连续的存储单元依次的存储单元依次存储线性表的元素存储线性表的元素。。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义: 顺序存储方法: 特点: 逻辑上相邻的元素,物理上也相邻可以利用数组 V[n] 来实现注意:在 C语言中数组的下标是从 0开始,即: V[n] 的有效范围是从 V[0] ~V[n-1] 1. ,其物理上也相邻; 逻辑上相邻的数据元素,其物理上也相邻; 2. ,则其他元若已知表中首元素在存储器中的位置,则其他元素存放位置亦可求出素存放位置亦可求出( ( 利用数组利用数组 V[n] V[n] 的的下标下标) )。。设首元素 a 1的存放地址为 LOC(a 1)(称为首地址), 设每个元素占用存储空间(地址长度)为 L字节, 则表中任一数据元素的存放地址为: LOC ( a i+1 ) = LOC( a i ) + L LOC ( LOC ( a a i i ) = LOC( ) = LOC( a a 1