数据结构 第2章数据结构.ppt

线性结构的定义:
若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。→可表示为:(a1 , a2 , ……, an)
简言之,线性结构反映结点间的逻辑关系是的。
特点①只有一个首结点和尾结点;
特点②除首尾结点外,其他结点只有一个直接前驱和一个直接后继。
线性结构包括:线性表、堆栈、队列、字符串、数组等,其中最典型、最常用的是------
线性表
一对一(1:1)
1
第2章线性表
线性表的基本概念
线性表的顺序存储结构及其算法
线性表的链式存储结构及其算法
算法应用举例
数组
2
线性表的基本概念
1、线性表
它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的,由n(n≥0)个相同类型数据元素a0, a1, …, an-1组成的线性结构。
3
(a0, a1, … ai-1,ai, ai+1 ,…, an-1)
线性表的逻辑结构:
n=0时称为
数据元素
线性起点
ai的直接前趋
ai的直接后继
下标,是元素的序号,表示元素在表中的位置
n为元素总个数,即表长。n≥0
空表
线性终点
4
( A, B, C, D, ……, Z)
学号
姓名
性别
成绩
年龄
001
张东
女
70
23
002
赵玉凤
女
80
20
003
王泽
男
90
19
004
薛荃
男
81
21
005
王春
男
88
22
:
:
:
:
:
例2 分析学生档案表是什么结构。
分析:数据元素都是同类型(记录),元素间关系是线性的。
分析: 数据元素都是同类型(字母), 元素间关系是线性的。
注意:同一线性表中的元素必定具有相同特性!
例1 分析26 个英文字母组成的英文表是什么结构。
5
2、线性表抽象数据类型
它包括两个方面:
数据集合:{ a0, a1, …, an-1 } ai的数据类型为DataType
操作集合:
(1) InitList(List) 初始化线性表,建一空线性表List
(2) ListLength(L) 求当前数据元素个数
(3) GetElement(List,i) 取线性表中第 i个元素(1,n)
(4) ListInsert(L,i,x) 插入数据元素
(5)ListDelete(L,i,x) 删除数据元素
(6)ListGet(L,i,x) 取数据元素等
6
3、线性表的存储结构
(1)顺序存储结构:它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法。
特点:(任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻)逻辑上相邻的元素,物理上也相邻。
(2)链式存储结构:它是把数据元素和指针定义成一个存储体,使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。
特点:任意两个在逻辑上相邻的数据元素在物理上不一定相邻,数据元素的逻辑次序是通过链中的指针链接实现的。
7
线性表的顺序存储结构及其算法
一、顺序表的存储结构
二、顺序表的实现
三、顺序表的运算效率分析
8
一、顺序表的存储结构表示
1、顺序表:用一组地址连续的存储单元依次存储线性表的各个数据元素。即采用顺序存储结构的线性表。它通常采用静态数组实现数据元素的存储。
可以利用数组V[n]来实现
注意:在C语言中数组的下标是从0开始,即:
V[n]的有效范围是从 V[0]~V[n-1]
9
(1) 逻辑上相邻的数据元素,其物理上也相邻;
(2) 若已知表中首元素在存储器中的位置,则其他元素存放位置亦可求出(利用数组V[n]的下标)。
设首元素a0的存放地址为LOC(a0)(称为首地址),
设每个元素占用存储空间(地址长度)为L字节,
则表中任一数据元素的存放地址为:
LOC ( ai+1 ) = LOC( ai ) + L
LOC ( ai ) = LOC( a0 ) + L *i
对上述公式的解释如图所示
2、线性表顺序存储特点:
10