[清华PPT2讲义.ppt

第2章 线性表 本章要点：    线性结构的特点。    线性表的逻辑结构和基本概念。    线性表在顺序和链式两种存储结构上操作算法 的实现。    线性表的两种存储结构的运算特点。    线性表的应用。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.1 线性表的逻辑结构 线性表（Liner_List）：有ｎ(ｎ≥0)个类型相同的数据元素a1，a2，…，an组成的有限序列，每个元素都有唯一的前驱和唯一的后继（第一个元素无前驱、最后一个元素无后继）。记作(a1，a2，……，an)。 ，如下图所示。 元素的位置： 线性表（a1，a2，…，an ），数据元素ai 在线性表中的序号i，称为元素a i 的位置。 线性表的长度：线性表中数据元素的个数ｎ为线性表的长度，当ｎ＝0 时称为空表。 图2.1 线性表的逻辑结构 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.1 线性表的逻辑结构（续） 例如：(′A′，′B′，…，′Z′)，可以表示为一个线性表，表中数据元素是英文字母。 前驱、后继、表长、位置 说明： 1.线性表中数据元素的类型可以是整型、字符型等简单数据类型，也可以是结构体、共用体等复杂的数据类型。 2.线性表令相邻数据元素之间存在着序偶关系，即对于非空的线性表(a1，a2，…，ai-1,ai ,ai+1…，an)，a i-1领先于a i ,称a i-1为ai的前驱，a i为a i-1的后继。记做：a i-1,a i称为序偶。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.1 线性表的逻辑结构（续） 线性表的抽象数据类型定义如下： ADT Liner_List{ 数据元素：D＝{a i | a i ∈elemset i=1..n (n≥0)} 数据关系：R＝{＜a i-1，a i＞| a i-1，a i ∈D i=2..n (n≥) } 基本操作：(1) InitList(L) (2) DestroyList(L) (3) ClearList(L) (4) EmptyList(L) (5) LengthList (L) (6) InsertList(L，i，e) (7) Getelem(L，i) (8) DeleteList(L，i，e) (9) Locate(L，e) (10) Priorelem(L,e) (11) Nextelem(L,e) (12) Traverse(L) }ADT Liner_List Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.1 线性表的逻辑结构（续） 【例2.1】假设两个有序线性表La，Lb均为Liner_List类型，他们分别表示二个集合A，B。现要求将A，B合并为一个有序集合C，且C=AUB 。 算法分析：即要求把A与B并集元素加入到C中去，使A成为一个更长的有序线性表。 例如：La=(3,5,8,11)，Lb=(2,6,8,9,11,15,20) 则 Lc=(2,3,5,6,8,8,9,11,11,15,20)。 归并算法如下： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.1 线性表的逻辑结构（续） void Merge_list(Liner_List la,Liner_List lb,Liner_List *lc） { int i=1,j=1,k=0; while（i=LengthList（la）j=LengthLis