Chap2-m.ppt

线性表Linear List 要 点 一、了解线性表的逻辑结构定义 二、熟练掌握线性表的两种存储结构 顺序存储和链式存储 三、了解在存储结构上如何实现基本运算 查找、插入、删除等 四、了解顺序表和链表的不同特点及其适用场合 本章学习的线索 主要线索 重点 顺序存储表示 链式存储表示 难点 链式存储表示及实现 一元多项式的表示和运算 Contents ADT of Linear list Sequential list Linked list Applications Representation and operations of polynomials Conclusion 线性表的逻辑结构定义 线性表的逻辑结构定义 线性表是n（n≥0）个数据元素组成的有限序列 线性表的逻辑特征 对于非空的线性表，有且仅有一个开始结点，它没有直接前趋；有且仅有一个终端结点，它没有直接后继；其余的内容结点都有且仅有一个直接前趋和一个直接后继。 Characteristics of Linear structure 在数据元素的非空有限集中， （1）存在唯一的一个被称为“第一个”的数据元素 （2）存在唯一的一个被称为“最后一个”的数据元素 （3）除第一个之外，集合中的每个数据元素均只有一个前驱 （4）除最后一个之外，集合中的每个数据元素均只有一个后继 2.1 Linear List Linear List is also called list, which contains zero or n elements denoted as k0,, k1, …, kn-1 n≥1 . The number of element is the length of the list. If the number is zero, the list is called as “Empty list”. “线性表”简称为表，是零个或多个元素的有穷序列，通常可以表示成k0，k1,　…，kn-1　（n≥1）。表中所含元素的个数称为表的“长度”。长度为零的表称为“空表”。表中的元素又称“表目”。 线性表中的数据元素在不同的情况下可以有不同的具体含义，它可以是一个数、一个符号，也可是其它更复杂的信息。 Basic functions for SeqList 1. Initialization 创建空线性表 ; 2. Element insertion 在线性表中插入一个元素 ; 3. Element removal 在线性表中删除某个元素 ; 4. Find out the specific element 在线性表中查找某个特定元素 ; 5. Find out the successor of the specific element 在线性表中查找某个元素的后继元素 ; 6. Find out the predecessor of the specific element 在线性表中查找某个元素的前驱元素 ; 7. Judge the list is empty or not 判别一个线性表是否为空表 …… ADT of Linear List 线性表的顺序存储结构 定义 把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表称为顺序表。 随机存储特性 Loc a1 Loc a1 + i-1 *c Logical Physical forms Logical form: linear list Physical form Sequential List Array or Vector Linked List 2.2 Sequential List The sequential list is stored in the contiguous storage, also called as Vector. It is a simple implementation of the linear list. The relationship of the addresses of the two neighbors is : Locate ki+1 Locate ki + sizeof DataType As a result, the address of the i-th element is: Locate ki Locate k0 + sizeof DataType * i Sketch map of SeqList in memory Definition of SeqList 在C语言中可以用以下方式定义一个顺序表： DataType e