数据结构(C语言版)线性表资料.ppt

上堂课要点回顾;数据结构课程的内容;第2章 线性表 ;线性结构的特点： 在数据元素的非空有限集中， 存在唯一的一个被称为“第一个”的数据元素； 存在唯一的一个被称为“最后一个”的数据元素； 除第一个元素之外，集合中的每个元素均只有一个前驱； 除最后一个元素之外，集合中的每个元素均只有一个后继。 ;图2.1 线性表的逻辑结构 ; 线性表(Linear List)是由n(n≥0)个类型相同的数据元素组成的有限序列，记作（a1, a2, …, ai-1, ai, ai+1, …, an）。这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同情况下可以不同，它既可以是原子类型，也可以是结构类型，但同一线性表中的数据元素必须属于同一数据对象。此外，线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a1, a2, …，ai-1, ai, ai+1, …, an），表中ai-1领先于ai，称ai-1是ai的直接前驱，而称ai是ai-1的直接后继。除了第一个元素a1外，每个元素ai有且仅有一个被称为其直接前驱的结点ai-1，除了最后一个元素an外，每个元素ai有且仅有一个被称为其直接后继的结点ai+1。线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。 ;（a1, a2, … ai-1，ai, ai＋1 ，…, an） ;例1 分析26 个英文字母组成的英文表; 线性表的特点可概括如下：  同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。  有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。  有序性：线性表中表中相邻数据元素之间存在着序偶关系ai, ai+1。  由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、 队列等都符合线性条件。 ;2.1.2 线性表的抽象数据类型定义;（2） DestroyList(L) 初始条件： 线性表L已存在。  操作结果： 将L销毁。  （3） ClearList(L) 初始条件： 线性表L已存在 。  操作结果： 将表L置为空表。  （4） ListEmpty（L） 初始条件： 线性表L已存在。  操作结果： 如果L为空表则返回真， 否则返回假。 ; （5） ListLength（L） 初始条件： 线性表L已存在。  操作结果： 如果L为空表则返回0， 否则返回表中的元素个数。 （6） LocateElem(L, e,compare()) 初始条件： 表L已存在， compare()是数据元素判定函数。  操作结果： 返回L中第1个与e满足关系compare() 的数据元素的位序，如果不存在，返回值为0。  （7） GetElem(L, i,e) 初始条件： 表L存在， 且1≤i≤ListLength（L）。 操作结果： 用e返回线性表L中第i个元素的值。 ; （8） ListInsert (L, i, e) 初始条件：表L已存在，1≤i≤ListLength(L)+1。  操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 （9） ListDelete (L, i, e) 初始条件： 表L已存在且非空， 1≤i≤ListLength(L)。 操作结果： 删除L的第i个数据元素， 并用e返回其值， L的长度减1。  } ADT List ;例2-1 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); } } O(Listlength(LA)* Listlength(LB)) ;例2-2 void MergeList(List La,List Lb,List Lc){ InitList(Lc); i=j=1;k=0; La