资源描述：
《数据结构第2章线性表.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表2012年7月18日冯鲁涛第一节 线性表的类型定义第二节 线性表的顺序存储表示和实现第三节 线性表的链式存储表示和实现第四节 循环链表、双向链表、有序表、集合操作目录第一节 线性表的类型定义线性表是一种最简单的线性结构线我是性结构线性结构是一个数据元素的有次序的集合。它有4个基本特征：1．集合中必存在唯一的"第一元素"；2．集合中必存在唯一的"最后元素"；3．除最后元素之外，其它数据元素均有唯一的"后继"；4．除第一元素之外，其它数据元素均有唯一的"前驱"。第一节 线性表的类型定义线性表的抽象数据类型的定义：ADTList{数据对象：D={ai
2、ai∈ElemSet,i=1,2,
3、…,n,n≥0}数据关系:R1={
4、ai-1,ai∈D,i=2,…,n}第一节 线性表的类型定义基本操作：{结构初始化}InitList(&L)操作结果:构造一个空线性表L{销毁结构}DestroyList(&L)初始条件:线性表L已存在操作结果:销毁线性表L第一节 线性表的类型定义{引用型操作}ListEmpty(L)初始条件:线性表L已存在操作结果:L为空,则返回TRUE,否则返回FALSEListLength(L)初始条件:线性表L已存在操作结果:返回L中的元素个数第一节 线性表的类型定义PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在操作结
5、果：若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已存在，1≤i≤ListLength(L)操作结果：用e返回L中第i个元素的值LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数操作结果：返回L中第1个与e满足关系compare()的元素的位序,若这
6、样的元素不存在，则返回值为0第一节 线性表的类型定义ListTraverse(L,visit())初始条件：线性表L已存在，visit()为元素的访问函数操作结果：依次对L的每个元素调用函数visit(),一旦visit()失败，则操作失败第一节 线性表的类型定义{加工型操作}ClearList(&L)初始条件：线性表L已存在操作结果：将L重置为空表PutElem(&L,i,&e)初始条件：线性表L已存在，1≤i≤ListLength(L)操作结果：L中第i个元素赋值同e的值第一节 线性表的类型定义ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤ListLength(L
7、)+1操作结果：在L的第i个元素之前插入新的元素e,L的长度增1ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤ListLength(L)操作结果：删除L的第i个元素，并用e返回其值,L的长度减1}第二节 线性表的顺序存储表示和实现顺序表是线性表的顺序存储表示的简称用一组地址连续的存储单元依次存放线性表中的数据元素前驱和后继的关系↔有序对↔存储位置相邻线性表的基地址:线性表的起始地址(表中第一个元素的存储位置)顺序表第三节 线性表的链式存储表示和实现链表是线性表的链式存储表示的简称特点:用一组任意的存储单元存储线性表的数据元素前驱和后继的关系↔
8、有序对↔指针域next关键词:头指针,头节点,单向链表链表数据域data指针域next谢谢！
