数据结构宋红

1、122.1 线性表的基本概念线性表的基本概念线性表特点：在数据元素的非空有限集中线性表特点：在数据元素的非空有限集中存在唯一的一个被称作存在唯一的一个被称作“第一个第一个”的数据元素的数据元素存在唯一的一个被称作存在唯一的一个被称作“最后一个最后一个”的数据元素的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后除最后一个外，集合中的每个数据元素均只有一个后继继线性表是类型相同的元素有限序列，记作：线性表是类型相同的元素有限序列，记作：（a1, ., ai-1, ai, ai+1, , an）32.

2、1 线性表的基本概念线性表的基本概念设设 A=（a1, a2, . , ai-1, ai , ai+1, , an）是一线性表）是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；素必须是同一类型的；2）在表中）在表中 ai-1 领先于领先于 ai ，ai 领先于领先于 ai+1，称，称 ai-1 是是 ai 的直的直接前趋，接前趋， ai+1 是是ai 的直接后继；的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前

3、趋，有且仅有一个直接后继。线性表都有且仅有一个直接前趋，有且仅有一个直接后继。线性表是一种线性数据结构；是一种线性数据结构；4）元素的个数）元素的个数 n 称为表的长度，称为表的长度，n=0时称为空表；时称为空表；5）ai 是表的第是表的第 i 个元素，称个元素，称 i 为数据元素为数据元素 ai 的序号，每个元素的序号，每个元素在线性表中的位置，仅取决于它的序号。在线性表中的位置，仅取决于它的序号。6）可在表的任意位置进行插入和删除操作。）可在表的任意位置进行插入和删除操作。42.1 线性表的基本概念线性表的基本概念 对线性表的对线性表的ADT描述描述 ADT List 数据对象：数据对象：

4、D = ai | ai ElemSet, i=1,n，n0 数据关系：数据关系：R1 = | ai-1,ai D, i=2, ,n 基本操作：基本操作： InitList (&L) 操作结果：构造一个空的线性表操作结果：构造一个空的线性表L。DetroyList (&L) 初始条件：线性表初始条件：线性表L已经存在。已经存在。 操作结果：销毁线性表操作结果：销毁线性表L。. ADTList52.1 线性表的基本概念线性表的基本概念 对线性表的基本操作对线性表的基本操作 1 初始化操作初始化操作 InitList (&L) 功能：建立空的线性表功能：建立空的线性表L； 2 销毁操作销毁操作 De

5、troyList (&L) 功能：回收为线性表功能：回收为线性表L动态分配的存动态分配的存储空间；储空间； 3 置空操作置空操作 ClearList (&L) 功能：功能：L中已存在，重新将其置成空中已存在，重新将其置成空表；表； 4 判空操作判空操作 ListEmpty (L) 功能：判断线性表功能：判断线性表L是否为空表，若是否为空表，若为空表返回为空表返回TRUE，否则返回，否则返回FALSE； 5 求表长操作求表长操作 ListLength (L) 功能：返回线性表功能：返回线性表L的表长；的表长；62.1 线性表的基本概念线性表的基本概念6 6 取元素操作：取元素操作：GetElem

6、 ( L, i, &e)GetElem ( L, i, &e) 功能：将线性表功能：将线性表L L中第中第 i i 个元素赋值给个元素赋值给 e e；7 7 查找操作查找操作 LocateElem ( L, e, compare() ) LocateElem ( L, e, compare() ) 功能：在线性表功能：在线性表 L L 中查找与元素中查找与元素e e 满足满足compare()compare()的第的第 1 1 个元素，返回该元素在表中的序号（或位个元素，返回该元素在表中的序号（或位置），若表中不存在这样的元素，则返回置），若表中不存在这样的元素，则返回 0 0；8 8 查找前

7、驱查找前驱 PriorElem ( &L, cur_e, &pre_e ) PriorElem ( &L, cur_e, &pre_e ) 功能：若功能：若 cur_e cur_e 是是 L L 中的数据元素且不是第一个，中的数据元素且不是第一个，则用则用 pre_e pre_e 返回它的前驱，否则失败，返回它的前驱，否则失败，pre_epre_e无定无定义。义。72.1 线性表的基本概念线性表的基本概念9 9 查找后继查找后继 NextElem ( &L, cur_e, &next_e ) NextElem ( &L, cur_e, &next_e ) 功能：若功能：若 cur_e cur_

8、e 是是L L中的数据元素且不是最后一个，中的数据元素且不是最后一个，则用则用next_enext_e返回它的后继，否则失败，返回它的后继，否则失败，next_enext_e无定义。无定义。10 10 插入操作插入操作 ListInsert ( &L, i, e ) ListInsert ( &L, i, e ) 功能：在线性表功能：在线性表L L的第的第i i个元素之前插入个元素之前插入1 1个新元素个新元素e e；11 11 删除操作删除操作 ListDelete ( &L, i, &e ) ListDelete ( &L, i, &e ) 功能：删除线性表功能：删除线性表L L的第的第i

9、 i个元素，并用个元素，并用 e e 返回；返回；12 12 遍历操作遍历操作 ListTraverse ( &L,visit( ) ) ListTraverse ( &L,visit( ) ) 功能：依次对线性表功能：依次对线性表L L的每个元素调用函数的每个元素调用函数visit()visit()。若若visit()visit()失败，则返回失败，则返回 ERROR ERROR，否则返回，否则返回 OK OK；82.1 线性表的基本概念线性表的基本概念 说明说明1 1、基本操作是一种数据结构中最常、基本操作是一种数据结构中最常见的操作，它具有明确的逻辑意义。见的操作，它具有明确的逻辑意义。

10、2 2、可以将基本操作看成一个整体，、可以将基本操作看成一个整体，使用基本操作来解决新的问题，设计新的算使用基本操作来解决新的问题，设计新的算法。使我们可以在更高的层次上进行抽象，法。使我们可以在更高的层次上进行抽象，在更高的基础上进行设计。在更高的基础上进行设计。3 3、在算法的程序实现的过程中，基、在算法的程序实现的过程中，基本操作需要通过编制公共函数进行具体实现。本操作需要通过编制公共函数进行具体实现。可以为基本操作建立公共函数库。可以为基本操作建立公共函数库。92.1 线性表的基本概念线性表的基本概念 利用基本操作进行算法设计利用基本操作进行算法设计例例1 1：若有两个集合：若有两个集

11、合 A A 和和 B B 分别用分别用两个线性表两个线性表 LA LA 和和 LB LB 表示，即：线表示，即：线性表中的数据元素即为集合中的成员。性表中的数据元素即为集合中的成员。现要求一个新的集合：现要求一个新的集合：A AABAB。 问题分析问题分析上述问题可以演绎为：扩大线性表上述问题可以演绎为：扩大线性表 LALA，将存在于线性表，将存在于线性表LB LB 中而不存在于中而不存在于线性表线性表 LA LA 中的数据元素插入到线性中的数据元素插入到线性表表 LA LA 中去。中去。102.1 线性表的基本概念线性表的基本概念 利用基本操作进行算法设计利用基本操作进行算法设计1从线性表从

12、线性表LB中依次察看每个数据元素；中依次察看每个数据元素；2依值在线性表依值在线性表LA中进行查访；中进行查访； 3若不存在，则插入之。若不存在，则插入之。GetElem ( LB, i ) e LocateElem ( LA, e, equal( ) ) ListInsert ( LA, n+1, e ) ListInsert ( LA, n+1, e )112.1 线性表的基本概念线性表的基本概念 利用基本操作进行算法设计利用基本操作进行算法设计 GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if ( ! LocateElem ( La, e,

13、 equal( ) ) ) ListInsert ( La, +La_len, e ); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union ( List &La, List Lb ) La_len = ListLength (La); / 求线性表的长度求线性表的长度 Lb_len = ListLength (Lb); for ( i = 1; i = Lb_len; i+ ) / union12集合集合 B2.1 线性表的基本概念线性表的基本概念 例例2-1：已知一个非纯集合：已知一个非纯集合B，试构造一个纯集合，试构造一个纯集合 A，使

14、使 A中只包含中只包含 B 中所有值各不相同的数据元素。中所有值各不相同的数据元素。 问题分析：采用线性表表示集合问题分析：采用线性表表示集合集合集合 A算法策略：从集合算法策略：从集合 B 取出物件放入集合取出物件放入集合 A。 要求集合要求集合 A 中同样的物件不能有两件以上。中同样的物件不能有两件以上。132.1 线性表的基本概念线性表的基本概念 利用基本操作进行算法设计利用基本操作进行算法设计 GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if ( ! LocateElem ( La, e, equal( ) ) ) ListInsert

15、( La, +La_len, e ); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之void union ( List &La, List Lb ) La_len=ListLength (La); Lb_len=ListLength (Lb); for ( i = 1; i = Lb_len; i+ ) / unionInitList (La); / 构造构造(空的空的)线性表线性表LA142.1 线性表的基本概念线性表的基本概念 例例2-2：已知一个非纯集合：已知一个非纯集合B，试构造一个纯集合，试构造一个纯集合 A，使使 A中只包含中只包含 B 中所有

16、值各不相同的数据元素。中所有值各不相同的数据元素。 问题分析：采用有序表表示集合问题分析：采用有序表表示集合有序表：有序表： 若线性表中的数据元素相互之间可以比较若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非，并且数据元素在线性表中依值非递减或非递增有序排列，即：递增有序排列，即：aiai-1 或或 aiai-1 (i=2,3,n)则称该线性表为有序表则称该线性表为有序表(Ordered List)。152.1 线性表的基本概念线性表的基本概念例如：例如： （2 2，3 3，3 3，5 5，6 6，6 6，6 6，8 8，1212）对集合对集合 B 而言，而言， 值

17、相同的数据元素必定相邻；值相同的数据元素必定相邻；对集合对集合 A 而言，而言， 数据元素依值从小至大的顺序插入。数据元素依值从小至大的顺序插入。因此，数据结构改变了，因此，数据结构改变了， 解决问题的策略也要相应进行改变。解决问题的策略也要相应进行改变。162.1 线性表的基本概念线性表的基本概念 利用基本操作进行算法设计利用基本操作进行算法设计void purge ( List &La, List Lb ) InitList ( La ); La_len = ListLength ( La ); Lb_len = ListLength ( Lb ); / 求线性表的长度求线性表的长度 fo

18、r ( i = 1; i = Lb_len; i+ ) / purge GetElem ( Lb, i, e ); / 取取Lb中第中第i个数据元素赋给个数据元素赋给 eif ( ListEmpty(La) | ! equal (en, e) ) ListInsert ( La, +La_len, e ); en = e; / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之172.2 线性表的顺序表示与实现 线性结构的顺序表示是指使用一组地址连续线性结构的顺序表示是指使用一组地址连续的存储单元依次存储线性表的数据元素。的存储单元依次存储线性表的数据元素。线性表的

19、起始地址，线性表的起始地址，称作线性表的基地址称作线性表的基地址 a1 a2 ai-1 ai an线性表元素之间的逻辑关线性表元素之间的逻辑关系，通过元素的存储顺序系，通过元素的存储顺序反映（表示）出来；反映（表示）出来； 假设：线性表中每个数据元素占用假设：线性表中每个数据元素占用 k k 个存储单个存储单元，那么，在顺序存储结构中，线性表的第元，那么，在顺序存储结构中，线性表的第 i i 个元个元素的存储位置与第素的存储位置与第 1 1 个元素的存储位置的关系：个元素的存储位置的关系：Loc ( ai ) = Loc ( a1 ) + (i 1) Loc ( ai ) = Loc ( a1

20、 ) + (i 1) k k182.2 线性表的顺序表示与实现 线性表的顺序表示线性表的顺序表示内存状态内存状态a1a1a2a2aiaiananb bb+kb+kb+(i-1)kb+(i-1)k存储地址存储地址b+(n-1)kb+(n-1)kb+(maxlen-1)kb+(maxlen-1)k1 12 2i i元素位序元素位序n n空闲空闲顺序表的特点顺序表的特点用连续的存储单元存用连续的存储单元存放线性表的元素。放线性表的元素。元素存储顺序与元素元素存储顺序与元素的逻辑顺序一致。的逻辑顺序一致。192.2 线性表的顺序表示与实现 顺序表的类型定义顺序表的类型定义#define LIST_IN

21、IT_SIZE 100#define LIST_INIT_SIZE 100 / / 线性表存储空间的初始分配量线性表存储空间的初始分配量 #define LISTINCREMENT 10 #define LISTINCREMENT 10 / / 线性表存储空间的分配增量线性表存储空间的分配增量 typedef struct typedef struct ElemType ElemType * * elem; / elem; /线性表存储空间基址线性表存储空间基址 int length; / int length; /当前线性表长度当前线性表长度 int listsize; / int list

22、size; /当前分配的表空间大小当前分配的表空间大小 / /（以（以sizeof(ElemType)sizeof(ElemType)为单位）为单位）SqList;SqList;202.2 线性表的顺序表示与实现 设设 A = A =（a1a1，a2a2， a3 a3，.，anan）是一线性表，）是一线性表，L L是是 SqList SqList 类型的结构变量，用于存放线性表类型的结构变量，用于存放线性表 A A，则，则 L L 在内存中的状态：在内存中的状态：存放线性表存放线性表元素的一维元素的一维数组数组 a1 a1 a2 a2ai-1ai-1 ai aiai+1ai+1 an an0

23、01 1i-2i-2i-1i-1i in-1n-19999L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen n100100212.2 线性表的顺序表示与实现顺序表基本操作的算法顺序表基本操作的算法初始化操作初始化操作 InitList_Sq ( SqList &L)功能：建立空的顺序表功能：建立空的顺序表L参数：参数：L: 顺序表顺序表0 01 1.i i.9999L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsize0 0100100O(1)算法时间复杂度：222.2 线性表的顺序表示与实现两个两个C

24、函数之一：函数之一：malloc ( int size )功能：在内存中分配长度为功能：在内存中分配长度为size个字节的存储单元，个字节的存储单元，并返回该空间的基址。并返回该空间的基址。使用方法：使用方法： int m = 100, float *p; p = (float *) malloc ( m*sizeof(float ) );0 01 1.i i.9999p p232.2 线性表的顺序表示与实现0 01 1.i i.9999p p调用调用free ( p )两个两个C函数之二：函数之二：free ( p )功能：回收指针功能：回收指针 p 所指向的内存空间。所指向的内存空间。使用

25、方法：使用方法： int m = 100, float *p; p = (float *) malloc (m*sizeof(float) ); /一旦不再需要一旦不再需要p所指向的内存空间所指向的内存空间 /调用调用 free( ) 回收之回收之 free(p);242.2 线性表的顺序表示与实现 初始化操作初始化操作InitList_Sq( SqList &L)InitList_Sq( SqList &L) Status InitList_Sq ( SqList &L )Status InitList_Sq ( SqList &L ) / /构造一个空的顺序表构造一个空的顺序表L L L.

26、elem = ( ElemType L.elem = ( ElemType * * ) ) malloc(LIST_INIT_SIZE malloc(LIST_INIT_SIZE * *sizeof(ElemType);sizeof(ElemType); if ( !L.elem ) if ( !L.elem ) exit ( OVERFLOW ); exit ( OVERFLOW ); L.length = 0; / L.length = 0; /空表长度为空表长度为0 0 L.listsize = LIST_INIT_SIZE; L.listsize = LIST_INIT_SIZE; r

27、eturn OK; return OK; /InitList_Sq /InitList_Sq252.2 线性表的顺序表示与实现顺序表基本操作的算法顺序表基本操作的算法销毁操作销毁操作 DetroyList_Sq ( SqList &L )功能：销毁顺序表功能：销毁顺序表L0 01 1.i i.9999L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsize0 0100100NULLNULL0 00 0262.2 线性表的顺序表示与实现 销毁操作销毁操作 DetroyList_Sq ( SqList &L) Status DetroyList_Sq ( S

28、qList &L) free (L.elem); L.elem = NULL; L.length = 0; L.Listsize = 0; return OK; / DetroyList_Sq272.2 线性表的顺序表示与实现 插入操作插入操作 定义：线性表的插入是指在第定义：线性表的插入是指在第 i（1i n+1）个元素之前插入一个新的数据元素个元素之前插入一个新的数据元素 x，使长度为，使长度为 n 的线性表：的线性表： A =（a1, a2, . , ai-1, ai , ai+1, , an）变成长度为变成长度为n+1的线性表：的线性表： A =（a1, a2, . , ai-1, x

29、, ai , ai+1, , an） 需将第需将第 i 至第至第 n 共（共（n-i+1）个元素后移。）个元素后移。282.2 线性表的顺序表示与实现 插入操作：插入操作：ListInsert_Sq(SqList &L, int i, ElemType e)L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen n100100a10a21.ai-1i-299nann-1.ai+1iaii-1L.elemL.elemL.lenghtL.lenghtL.listsizeL.listsizen+1n+1100100a10a21.ai-1i-299ann.n

30、-1.aii+1ei算法的时间算法的时间复杂度为：复杂度为：O( ListLength(L) )292.2 线性表的顺序表示与实现内存内存a1a2aiai+1an01i-1数组下标数组下标n-1in12i元素序号元素序号i+1nn+1e内存内存a1a2aiai+1an01i-1数组下标数组下标n-1in12i元素序号元素序号i+1nn+1an-1302.2 线性表的顺序表示与实现插入操作：基本算法插入操作：基本算法Status ListInsert_Sq (SqList &L, int i, ElemType e) /在顺序线性表在顺序线性表L中第中第 i 个位置之前插入新的个位置之前插入新的

31、元素元素e, if ( iL.length+1 ) return ERROR; / i 超出表长则不超出表长则不合法合法q = & ( L.elemi-1 ); / q 指向插入位指向插入位置置 for ( p=&(L.elemL.length-1); p=q; -p ) / 初始化时初始化时p指向最后一个数据元素指向最后一个数据元素*(p+1) = *p; *q = e; / 插入插入e +L.length; / 表长增表长增1 return OK; / ListInsert_Sq312.2 线性表的顺序表示与实现Status ListInsert_Sq(SqList &L, int i,

32、ElemType e) /在顺序线性表在顺序线性表L中第中第 i 个位置之前插入新的元素个位置之前插入新的元素e, if ( iL.length+1 ) return ERROR; /i不合法不合法 if ( L.length = L.listsize ) /空间已满，重新分配空间空间已满，重新分配空间 newbase = (ElemType*) realloc (L.elem, (L.listsize+L.incresize) * sizeof(ElemType) ); if ( !newbase ) exit(OVERFLOW); /存储分配失败存储分配失败 L.elem = newbase; /新基址新基址 L.listsize+= L.incresize; /增加存储容量增加存储容量 q = & ( L.elemi-1 ); / q为插入位置为插入位置 fo