《数据结构与算法第2节线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法第2节线性表.ppt（100页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第22章章 数据结构与算法数据结构与算法Section 2 Linear List（线性表）一、基本概念二、顺序表三、链表1学习内容和目标1、学习和掌握线性表的定义（逻辑结构）及其特点；2、学习和理解线性表的顺序存储结构（顺序表）的C+类定义和类模板定义方法；掌握顺序表的基本操作的实现原理和方法；3、学习和理解线性表的链式存储结构（链表）的C+类定义和类模板定义方法；掌握单链表、双向链表和循环链表的结构特点以及基本操作的实现原理和方法。2Subsection 1Basic Concept3Definition of List A list of elements(数据元素)of type T
2、 is a finite sequence(有限序列)of elements of T together with the following operations(操作):1.Construct(构造)the list,leaving it empty.2.Determine(确定)whether the list is empty or not.3.Determine whether the list is full or not.4.Find the size of the list.5.Clear the list to make it empty.46.Insert(插入)an en
3、try(数据元素)at a specified position of the list.7.Remove(删除)an entry from a specified position in the list.8.Retrieve(检索)the entry from a specified position in the list.9.Replace(替换)the entry at a specified position in the list.10.Traverse(遍历)the list,performing(执行)a given operation on each entry.遍历:逐项
4、访问数据元素(每个元素只访问一次)5线性表(Linear List)线性表的定义和特点 定义 n（0）个数据元素的有限序列，记作（a1,a2,an）或（a0,a1,an-1）ai 是表中数据元素，n 是表长度。数据类型的任意性和一致性直接前驱元素和直接后继元素 6线性表的特点n除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。n除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。n相邻数据元素之间存在序偶关系。“序偶”包含两层含义：顺序、配对a1a2a3a4a5a67抽象数据类型线性表的定义如下：ADT List 数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 称 n 为线性表的表长;称 n=0 时的线性表为空表。数据关系：R1|ai-1,aiD,i=2,.,n 设线性表为(a1，a2,.，ai，.，an),称 i 为 ai 在线性表中的位序。8 基本操作：结构初始化操作结构销毁操作 引用型操作 加工型操作 ADT List9