数据结构与算法—赵玉兰 第2章 基本数据结构.ppt

文档介绍：本章介绍有关线性表和数组的内容,它们和第三章中的栈、队列都属于线性结构。
线性结构的特点:
具有唯一的第一个数据元素(无前驱);
具有唯一的最后一个数据元素(无后继) ;
其他数据元素都有且仅有一个前驱和一个后继。
第二章基本数据结构
线性表
ADT线性表
线性表的顺序存储
线性表的链式存储
数组
数组的定义
数组的存储
特殊矩阵
稀疏矩阵
第二章基本数据结构
线性表(Linear List)
线性表的定义和特点
定义由n(  0)个性质相同的数据元素组成的有限序列,记作:
L=(a1, a2, …, an)
其中:ai是表中的第i个数据元素,n是表长度。
注意:
数据元素的个数n被定义为表的长度。当n=0时,称为空表。
这里的数据元素ai(1in)只是一个抽象的符号,其具体含义在不同的情况下可以不同。
例1、26个大写英文字母组成的字母表:

(A,B, C,…, Z)
例2、某个学生宿舍的学生姓名表:
( wan,li,zhao,ye,hao,jia)
例3、学生信息情况登记表如下:
姓名
学号
性别
年龄
民族
系
专业
入学时间
王小林
060631
男
18
汉族
计算机
计算机科学
2006,9
陈红
060632
女
20
蒙族
计算机
计算机应用
2006,9
刘建平
060633
男
19
回族
计算机
电子商务
2006,9
……..
……..
…….
…….
……
……
…….
非空线性表的逻辑特征:
1)有且仅有一个开始结点a1,它没有(直接)前趋,而仅有一个(直接)后继a2;
2)有且仅有一个终端结点an,它没有(直接)后继,而仅有一个(直接)前趋an-1;
3)其余的内部结点ai(2in-1)都有且仅有一个(直接)前趋ai-1和一个(直接)后继ai+1。
线性表的逻辑结构是一种典型的线性结构。
线性表
ADT线性表
线性表的顺序存储
线性表的链式存储
数组
数组的定义
数组的存储
特殊矩阵
稀疏矩阵
第二章基本数据结构
9
抽象数据类型(ADT)线性表的定义如下:
ADT List {
Data 数据元素表:是n(n  0)个数据元素的一个有限
序列,其中每个数据元素的数据类型为DataType
size: 数据元素的个数
Operation
Constructor
Process: 创建空表
Clear
Process: 清空线性表
IsEmpty
Process: 判断线性表是否为空
Output: 若线性表为空, 返回true, 否则返回false
ADT线性表