文档介绍：第二章
线性表
7/7/2018
第1页
【课前思考】
1. 抽象数据类型的定义由哪几部分组成?
数据对象、数据关系和基本操作三部分。
2. 按数据元素之间的逻辑关系不同,数据结构有哪几类?
线性结构、树型结构、图状结构和集合四类。
3. 你能举出几个你熟悉的"序列"的例子来吗?
如:"0,1,2,…,9","A,B,C,…,Z"。
7/7/2018
第2页
【学****目标】
1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表,用后者表示的线性表简称为链表。 2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 4. 结合线性表类型的定义增强对抽象数据类型的理解。
7/7/2018
第3页
【重点和难点】
链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求,分清链表中指针 p 和结点*p 之间的对应关系,区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。
【知识点】
线性表、顺序表、链表、有序表
7/7/2018
第4页
【学****指南】
正如课程概况中所提,学****数据结构的目标是为了编出质量更高的程序,因此重在“实践”。本章讨论的线性表是学****的第一种也是最简单的一种数据结构,是整个课程的基础,特别是熟练掌握链表的操作对以后各章的学****将有很大帮助。本章要求必须完成的算法设计题为:,,,,,,, , 。其中 , 要求书面作业完成。
7/7/2018
第5页
线性结构的基本特征为:
“第一元素”;
“最后元素”;
,均有唯一的后继;
,均有唯一的前驱。
线性结构是
一个数据元素的有序(次序)集
线性表是一种最简单的线性结构
7/7/2018
第6页
线性表的类型定义
线性表类型的实现
链式映象
一元多项式的表示
线性表类型的实现
顺序映象
7/7/2018
第7页
线性表的类型定义
7/7/2018
第8页
抽象数据类型线性表的定义如下:
ADT List {
数据对象:
D={ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
{称 n 为线性表的表长;
称 n=0 时的线性表为空表。}
数据关系:
R1={ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n }
{设线性表为(a1,a2, . . . ,ai,. . . ,an),
称 i 为 ai 在线性表中的位序。}
7/7/2018
第9页
基本操作:
结构初始化操作
结构销毁操作
引用型操作
加工型操作
} ADT List
7/7/2018
第10页