文档介绍：数据结构
Data Structure
中南大学
中南大学信息院计科系
主讲人:王国军,郑瑾
{csgjwang,zhengjin}***@csu.
./
电话:0731-88877711
手机:**********
办公室:校本部计算机楼406-B
本PPT根据《数据结构》教材(清华大学)制作,仅供中南大学计算机科学与技术专业及相关专业11级本科生和任课老师使用。
第二章线性表
提纲
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
线性链表
循环链表
双向链表
一元多项式的表示及相加
线性表的类型定义
“第一个元素”;
“最后一个元素”;
,均有唯一的后继;
,均有唯一的前驱。
线性结构是一个数据元素的有序集。对非空有限集:
线性结构的基本特征:
线性表的定义
线性表是由n(n≥0)个类型相同的数据元素组成的有限序列。通常表示成下列形式:
L=(a1, a2,...,ai-1,ai,ai+1,...,an)
其中:
L为线性表的名称;
ai为组成该线性表的数据元素,i为数据元素ai在线性表中的位序;
n为线性表中数据元素的个数,称为线性表的长度。当n=0时,线性表为空,又称为空线性表。
抽象数据类型线性表的定义
ADT List {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系:
R1={ <ai-1, ai >|ai-1, ai∈D, i=2,...,n }
基本操作:
InitList( &L )
操作结果:
构造一个空的线性表L。
初始化操作
结构销毁操作
DestroyList( &L )
初始条件:
操作结果:
线性表 L 已存在。
销毁线性表 L。
ListEmpty( L )
初始条件:
操作结果:
线性表 L 已存在。
若 L 为空表,则返回
TRUE,否则FALSE。
线性表判空操作
ListLength( L )
初始条件:
操作结果:
线性表 L 已存在。
返回 L 中数据元素的个数。
求线性表的长度
PriorElem( L, cur_e, &pre_e )
初始条件:
操作结果:
线性表 L 已存在。
若 cur_e 是 L 的元素,则用pre_e 返回它的前驱,否则操作失败,pre_e无定义。
求数据元素的前驱
NextElem( L, cur_e, &next_e )
初始条件:
操作结果:
线性表 L 已存在。
若 cur_e 是 L 的元素,则用next_e 返回它的后继,否则操作失败,next_e无定义。
求数据元素的后继
GetElem( L, i, &e )
初始条件:
操作结果:
线性表 L 已存在,
用 e 返回 L 中第 i 个数据元素的值。
求线性表中某个数据元素
并且 1≤i≤ListLength(L) 。
LocateElem( L, e, compare( ) )
初始条件:
操作结果:
线性表 L 已存在,e 为给定值,
compare( ) 是元素判定函数。
返回 L 中第 1 个与 e pare( ) 的元素的位序。
若这样的元素不存在,则返回值为 0。
定位函数