第二章线性表
线性表的类型定义
线性表的顺序表示和实现
教学内容
线性表的顺序表示和实现
学****目的:1. 了解线性表的逻辑结构特性,了解线性表的ADT定义。2. 掌握线性表顺序存储结构。3. 顺序表:掌握C描述方法,熟练掌握查找、插入、删除算法;掌握构造一个空的顺序线性表的算法,并掌握在此空表的基础上进行其他基本操作(取元素、求前驱元素、求后继元素等)算法的实现。
重点难点:顺序表的插入、删除算法及性能分析。
线性结构的特点为:
“第一元素”;
“最后元素”;
,均有唯一的后继;
,均有唯一的前驱。
线性结构是一个数据元素的有序(次序)集
线性表是一种最简单的线性结构。
导入:什么是线性表?
ai必须具有相同特性,即属于同一数据对象;
相邻数据元素有序偶关系,ai-1是ai的直接前驱元素,
ai+1是ai的直接后继元素。
数据元素ai在线性表中有确定的位置i,i称为位序。
线性表中数据元素的个数n称为线性表的长度,
n=0时,线性表称为空表。
线性表的类型定义
定义: n个具有相同特性的数据元素组成的有限序列;表示:{a1,…,ai-1,ai,ai+1,…,an}
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 在线性表中的位序)
基本操作:-------P19
} ADT List
例1 假设利用两个线性表LA和LB分别表示两个集合A和B,要求一个新的集合A=A∪B。
void union(List &La, List &Lb){//
La_len=ListLength(La);
Lb_len=ListLength(Lb);
for( i=1; i<=Lb_len; i++){
GetElem (Lb, i, e) );
if(!LocateElem(La, e, equal))
ListInsert(La, ++La_len,e);
}
}//union
例 2—P20
时间复杂度为 O(ListLength(LA) × ListLength(LB))
逻辑结构是本质
通过上面的例子可以看出:
逻辑结构是数据组织的某种“本质性”的东西:
(1)逻辑结构与数据元素本身的形式、内容无关。
(2)逻辑结构与数据元素的相对位置无关。
(3)逻辑结构与所含数据元素的个数无关。
算法的设计取决于选定的逻辑结构,而算法的实现依赖于采用的存储结构。
1. 顺序映像
——以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系<x,y>。
线性表的顺序表示和实现
线性表的顺序表示指用一组地址连续的存储单元依次存放线性表中的数据元素。以物理位置的相邻表示逻辑关系的相邻,这种机内表示称为线性表的顺序存储结构(顺序映像),称这种存储结构的线性表为顺序表。
a1 a2 … ai-1 ai … an
线性表的起始地址
称作线性表的基地址
3线性表的顺序表示和实现 来自淘豆网www.taodocs.com转载请标明出处.