文档介绍：数据结构课程的内容
逻辑结构唯一
存储结构不唯一
运算的实现依赖于存储结构
1
近3周 上课 内容
第2章线性表
第3章栈和队列
第4章串
第5章数组和广义表
线性结构
若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。
可表示为:(a1 , a2 , ……, an)
线性结构的定义:
(逻辑、存储和运算)
2
线性结构的特点:
①只有一个首结点和尾结点;
②除首尾结点外,其他结点只有一个直接前驱和一个直接后继。
线性结构表达式:(a1 , a2 , ……, an)
线性结构包括线性表、堆栈、队列、字符串、数组等等,其中,最典型、最常用的是------
线性表
简言之,线性结构反映结点间的逻辑关系是一对一的。
见第2章
3
第2章线性表
线性表的逻辑结构
线性表的顺序表示和实现
线性表的链式表示和实现
应用举例(一元多项式的表示及相加)
作业
4
(a1, a2, … ai-1,ai, ai+1 ,…, an)
线性表的类型定义
1. 线性表的定义:用数据元素的有限序列表示
n=0时称为
数据元素
线性起点
ai的直接前趋
ai的直接后继
下标,是元素的序号,表示元素在表中的位置
n为元素总个数,即表长
空表
线性终点
5
例1 分析26 个英文字母组成的英文表
( A, B, C, D, ……, Z)
学号
姓名
性别
年龄
班级
2001011810205
于春梅
女
18
2001级电信016班
2001011810260
何仕鹏
男
18
2001级电信017班
2001011810284
王爽
女
18
2001级通信011班
2001011810360
王亚武
男
18
2001级通信012班
:
:
:
:
:
例2 分析学生情况登记表
数据元素都是记录; 元素间关系是线性
数据元素都是字母; 元素间关系是线性
同一线性表中的元素必定具有相同特性
6
练:判断下列叙述的正误:
1. 数据的逻辑结构是指数据元素之间的逻辑关系,是用户按使用需要建立的。
2. 线性表的逻辑结构定义是唯一的,不依赖于计算机。
3. 数据结构是指相互之间存在一种或多种关系的数据元素的全体。
4. 线性结构反映结点间的逻辑关系是一对一的。
一维向量是线性表,但二维或N维数组不是。
“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。
√
×
√
√
×
×
7
(详见课本P19)
对线性表的有关操作举例请大家看课本P20例2-1,例2-2
8
线性表的顺序表示和实现
顺序表的表示
顺序表的实现
顺序表的运算效率分析
本节小结
作业
9
顺序表的表示
用一组地址连续的存储单元依次存储线性表的元素,可通过数组V[n]来实现。
把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义:
顺序存储方法:
简言之,逻辑上相邻,物理上也相邻
10