川大数据结构与算法分析第二章线性表.ppt

Chapter 2Linear List;第二章 线性表 本章主要讲述线性表的逻辑结构和存储结构以及典型算法。重点：理解线性表的逻辑结构，掌握线性表 的两种存储结构及在这两种存储结构上的典型算法插入算法和删除算法。难点：能够分析算法的时间复杂度；了解循环链表和双向链表；掌握集合的两种存储结构下的运算。;Section 1Basic Concept;List Definition A list of elements of type T is a finite sequence of elements of T together with the following operations: ; 1. Construct the list, leaving it empty. 2. Determine whether the list is empty or not. 3. Determine whether the list is full or not ; 4. Find the size of the list. 5. Clear the list to make it empty. 6. Insert an entry at a specified position of the list. 7. Remove an entry from a specified position in the list. ; 8. Retrieve the entry from a specified position in the list. 9. Replace the entry at a specified position in the list. 10. Traverse the list, performing a given operation on each entry.;线性表 (Linear List);1．集合中必存在唯一的一个“第一元素”；;线性表的特点;抽象数据类型线性表的定义如下：; 基本操作：; InitList( L ) ; 结构销毁操作;Empty( L );Empty( L ) ;Length( L ); Prior( L, x, pre ) ;Next( L, x, next );Get( L, i );Locate( L, x );加工型操作 ;Clear( L );PutElem( L, i, x ); Insert( L, i, x );Delete(L, i ); 假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合A＝A∪B。; 要求对线性表作如下操作： 扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。; 1．从线性表LB中依次察看每个数据元素;; x=Get(Lb, i); if (!Locate(La, x) ) Insert(La, ++La_len, x);; Section 2 Sequential List;顺序表 (Sequential List);顺序表(SeqList)类的定义; int Locate ( Type x ) const; //定位 int Insert ( int i, Type x ); //插入 int Delete ( int i ); //删除 int Next ( Type x, Type next ) ; //后继 int Prior ( Type x, Type pre ) ; //前驱 int Empty ( ) { return last ==-1; } int Full ( ) { return last == MaxSize-1; } Type Get ( int i ) { //提取 return i 0 || i last？NULL : data[i];