数据结构第二章ppt

1、2.1 2.1 线性表概念及基本操作线性表概念及基本操作2.22.2 线性表的顺序存储和实现线性表的顺序存储和实现2.32.3 线性表的链式存储和实现线性表的链式存储和实现 2.3.12.3.1 线性链表线性链表 2.3.22.3.2 循环链表循环链表 2.3.32.3.3 双向链表双向链表2.42.4 一元多项式的表示及相加一元多项式的表示及相加 在本课程介绍的几种数据结构中，线性表是在本课程介绍的几种数据结构中，线性表是最简单的，也是最常用的数据结构，线性表在实最简单的，也是最常用的数据结构，线性表在实际应用中大量使用，并不是一个陌生的概念。际应用中大量使用，并不是一个陌生的概念。 基本内

2、容：基本内容： 1 1 线性表的概念；线性表的概念； 2 2 线性表两类存储结构和它们的类型定义；线性表两类存储结构和它们的类型定义； 3 3 在两类存储结构下，线性表基本操作的算法；在两类存储结构下，线性表基本操作的算法； 学习要点：学习要点： 1 1 了解线性表逻辑结构的特征；了解线性表逻辑结构的特征； 2 2 重点掌握线性表的顺序存储结构和链式存储结构，它重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如何用们如何表达线性表中数据元素之间的结构关系；如何用C C语语言描述它们的类型定义；言描述它们的类型定义； 3 3 掌握在顺序存储结构下，线性表的

3、基本操作的算法；掌握在顺序存储结构下，线性表的基本操作的算法； 4 4 掌握在链式存储结构下，线性表的基本操作的算法；掌握在链式存储结构下，线性表的基本操作的算法； 5 5 能够从时间复杂度的角度，比较线性表两类存储结构能够从时间复杂度的角度，比较线性表两类存储结构的不同特点及适用场合；的不同特点及适用场合； 线性表是线性表是n 个类型相同数据元素的有限序列，个类型相同数据元素的有限序列，通常记作通常记作:（a1, a2, a3, , an ）。）。 姓名姓名 电话号码电话号码 蔡颖蔡颖 63214444 陈红陈红 63217777 刘建平刘建平 63216666 王小林王小林 6321888

4、8 张力张力 63215555 . 2. 1 线性表的概念线性表的概念例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A, B, C, D, E Z ）。例3、某单位的电话号码簿。一、线性表的逻辑结构一、线性表的逻辑结构 电话号码簿是数据元素电话号码簿是数据元素的有限序列，每一数据的有限序列，每一数据元素包括两个数据项，元素包括两个数据项，一个是用户姓名，一个一个是用户姓名，一个是对应的电话号码。是对应的电话号码。说明：说明：设设 A=（a1, a2, . , ai-1, ai , ai+1, , an ）是一线性表）是一线性表1） 线性表的数据元素可以是各种各样的，

5、但同一线性表中的元线性表的数据元素可以是各种各样的，但同一线性表中的元素必须具有相同特性；素必须具有相同特性；2） 在表中在表中 ai-1 领先于领先于ai ，ai 领先于领先于ai+1 ，称，称ai-1 是是ai 的直接前趋的直接前趋，ai+1 是是ai 的直接后继；的直接后继；3） 在线性表中，除第一个元素和最后一个元素之外，其他元素在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构；构特征的数据结构称为线性结构；4） 线性表中元素的个数线性表中元素

6、的个数n称为线性表的长度，称为线性表的长度，n=0时称为空表；时称为空表；5） ai是线性表的第是线性表的第i 个元素，称个元素，称i 为数据元素为数据元素ai 的序号，每一个的序号，每一个元素在线性表中的位置，仅取决于它的序号；元素在线性表中的位置，仅取决于它的序号； 线性表的其他表示方式线性表的其他表示方式 二元组表示二元组表示 L= ，其中，其中D= a1,a2, a3, . an S= R R=, , 图示表示图示表示a ai i+1a a1a ai-i-1a a2 2a ai ia an n顶点：表示数据顶点：表示数据边：表示是数据间的顺序结构关系边：表示是数据间的顺序结构关系设设L

7、=（a1,a2, .ai-1, ai , ai+1, , an ）是一线性表）是一线性表1 初始化操作初始化操作 InitList(&L) 功能：建立空的线性表功能：建立空的线性表L；2 销毁操作销毁操作DestroyList(&L)功能：回收为线性表功能：回收为线性表L动态分配的存储空间；动态分配的存储空间；3 置空操作置空操作ClearList(&L)功能：功能：L中已存在，重新将其置成空表；中已存在，重新将其置成空表；4 判空操作判空操作ListEmpty(L)功能：判断线性表功能：判断线性表L是否为空表，若为空表返回是否为空表，若为空表返回TRUE，否则返回否则

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

9、元素，则返回0；8 前驱操作前驱操作 PriorElem(L,cur_e,&pre_e) 功能：若功能：若cur_e是是L的数据元素，且不是第一个，则用的数据元素，且不是第一个，则用pre_e返回它的前驱，返回它的前驱，否则操作失败。否则操作失败。9 后继操作后继操作 NextElem(L,cur_e,&next_e) 功能：若功能：若cur_e是是L的数据元素，且不是最后一个，则用的数据元素，且不是最后一个，则用next_e返回它的后返回它的后继，否则操作失败。继，否则操作失败。10 插入操作插入操作 ListInsert(&L, i, e )功能：在线性表功能：在线

10、性表L的第的第i个元素之前插入一个新元素个元素之前插入一个新元素e;11 删除操作删除操作 ListDelete(&L, i, &e )功能：删除线性表功能：删除线性表L的第的第i个元素，并用个元素，并用e返回；返回；12 遍历操作遍历操作 ListTraverse (&L,visit( ) )功能：依次对线性表功能：依次对线性表L的每一个元素调用函数的每一个元素调用函数visit( )。若。若visit( )失败，失败，则返则返回回ERROR，否则返回，否则返回OK；说明：说明：1 上面列出的操作，只是线性表的一些常用的基本操作；上面列出的操作，只是线性表的一些常用的

11、基本操作；2 不同的应用，基本操作可能是不同的；不同的应用，基本操作可能是不同的； 例如：上面列出的删除操作例如：上面列出的删除操作Delete( &L, i, &e ), 功能是在功能是在线性表线性表L中删除第中删除第i个元素，并用个元素，并用e返回其值。返回其值。 在电话号码查询在电话号码查询系统中，一旦某用户撤掉某部电话，则需在系统的电话号码系统中，一旦某用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，需要簿中删除该用户对应的数据，因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与给定元素提供这样的功能，在电话号码簿中删除

12、与给定元素e值相同的值相同的数据元素；数据元素； 线性表的复杂操作可通过基本操作实现；线性表的复杂操作可通过基本操作实现； 这有点类似于数中情形，例如整数基本操作是这有点类似于数中情形，例如整数基本操作是+，-， ，/ 。如果要求某班同学的平均年龄则可利用如果要求某班同学的平均年龄则可利用+ / 实现：实现： 全班同学的平均年龄全班同学的平均年龄=(age1+age2+age3+)/全班同学人数全班同学人数 关于如何用线性表的基本操作实现复杂操作将在后面讲解。关于如何用线性表的基本操作实现复杂操作将在后面讲解。 现在我们已经知道什么是线性表及线性表的一些基本操作，现在我们已经知道什么是线性表及

13、线性表的一些基本操作，下一步要做什么呢？下一步要做什么呢？ 例如，我们要设计一个电话号码查询系统，显然这个系统至例如，我们要设计一个电话号码查询系统，显然这个系统至少要具备下列功能：少要具备下列功能：查询某人的电话号码；查询某人的电话号码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码； 由上我们知道，电话号码薄可用线性表表示，上面列出的功由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就是对线性表的查找、插入、删除操作。能实际上就是对线性表的查找

14、、插入、删除操作。 显然，首先需要将电话号码薄上的信息存储到计算机中，然显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对这些信息进行加工处理，实现上述功能。后才可能对这些信息进行加工处理，实现上述功能。 本课程不仅要从概念和方法上了解每一种数据结构的本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储数据结构？如何在计算机上实现，即如何在计算机上存储数据结构？如何在计算机上实现对数据结构的各种操作？为此，我们将用计算机语言实现对数据结构的各种操作？为此，我们将用

15、计算机语言来描述数据的存储结构，用计算机语言来描述这些操作的来描述数据的存储结构，用计算机语言来描述这些操作的算法。算法。 本课程用类本课程用类C语言做为描述语言。语言做为描述语言。 2.2 线性表的顺序存储和实现线性表的顺序存储和实现 一、线性表的顺序存储结构一、线性表的顺序存储结构顺序表顺序表 1 1 线性表的顺序存储结构线性表的顺序存储结构 2 2 顺序表的类型定义顺序表的类型定义 二、顺序表的基本操作算法二、顺序表的基本操作算法 三、利用基本操作实现线性表的其他操作三、利用基本操作实现线性表的其他操作为了存储线性表，至少要保存两类信息：为了存储线性表，至少要保存两类信息：1）线性表中的

16、数据元素；）线性表中的数据元素；2）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系； 在计算机内部可以采用不同的方式来存储一个线性在计算机内部可以采用不同的方式来存储一个线性表，其中最简单的方式就是线性表的顺序存储结构表，其中最简单的方式就是线性表的顺序存储结构。 线性表的顺序存储结构，就是用一组线性表的顺序存储结构，就是用一组连连续的续的内存单元内存单元依次依次存放线性表的数据元素。存放线性表的数据元素。用顺序表存储线性表时，数据元素之间的逻辑用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存储顺序反映出来的关系，是通过数据元素的存储顺序反映出来的a a1 1a a2

17、 2a ai-1i-1a ai ia ai+1i+1a an n 线性表（线性表（a1,a2, a3, . an ）的顺序存储结构的顺序存储结构用顺序存储结构存储的线性用顺序存储结构存储的线性表表称为顺序表称为顺序表一、线性表的顺序存储结构一、线性表的顺序存储结构顺序表顺序表1、线性表的顺序存储结构、线性表的顺序存储结构说明：说明： 在顺序存储结构下，线性表元素之间的逻辑关系，可通过在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息的信息 假设线性表中每个数据元素占用假设线性表中每个数

18、据元素占用 k 个存储单元，那么在顺个存储单元，那么在顺序存储结构中，线性表的第序存储结构中，线性表的第i个元素的存储位置与第个元素的存储位置与第1个元素的个元素的存储位置的关系是：存储位置的关系是：Loc(ai ) = Loc( a1 )+ ( i 1) k 这里这里 Loc(ai)是第是第 i 个元素的存储位置，个元素的存储位置， Loc( a1 ) 是第是第1个个元素的存储位置，也称为线性表的起始位置或基地址。元素的存储位置，也称为线性表的起始位置或基地址。怎样在计算机上实现怎样在计算机上实现线性表的顺序存储结构？线性表的顺序存储结构？2、顺序表的类型定义、顺序表的类型定义 以上用自然语

19、言描述了线性表的顺序存储结构，怎样以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？我们知道将这种存储方式在计算机上实现？我们知道C语言一维数组语言一维数组的机内表示也是顺序结构，因此，可借用的机内表示也是顺序结构，因此，可借用C语言的一维数组语言的一维数组实现线性表的顺序存储。实现线性表的顺序存储。顺序表的类型定义顺序表的类型定义#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量线性表存储空间的分配增量typedef structE

20、lemType * elem; /线性表存储空间基址线性表存储空间基址int length; /当前线性表长度当前线性表长度int listsize; /当前分配的线性表存储空间大小当前分配的线性表存储空间大小 /（以（以sizeof(ElemType)为单位）为单位）SqList;说明：说明：SqList 为类型名；为类型名；SqList类型的变量是结构变量，三个域分别是：类型的变量是结构变量，三个域分别是： *elem：存放线性存放线性表元素的一维数组基址，其存储空间在初始化操作时动态分配；表元素的一维数组基址，其存储空间在初始化操作时动态分配；length：存放线性表的表长；存放线性表的

21、表长； listsize：用于存放当前分配（存放线用于存放当前分配（存放线性表元素）的存储空间的大小。性表元素）的存储空间的大小。顺顺序序表表图图示示a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nL.lengthL.lengthL.listsizeL.listsizeL.elemL.elemn nLIST_INIT_SIZELIST_INIT_SIZE存放线性表元素存放线性表元素 的一维数组的一维数组设设 A = （a1,a2 , a3 , . an ）是一线性表，）是一线性表，L是是SqList 类型的结类型的结构变量，用于存放线性表构变量，用于存放线性

22、表A，则，则L在内存中的状态如图所示：在内存中的状态如图所示：二、顺序表的基本操作算法二、顺序表的基本操作算法 现在，我们已为线性表设计好了一种存储结构，下面将看到用这种现在，我们已为线性表设计好了一种存储结构，下面将看到用这种存储方式存储线性表时，线性表的各种基本操作算法。存储方式存储线性表时，线性表的各种基本操作算法。 在介绍基本操作的算法之前，先回顾一下本书算法中常用到的两个在介绍基本操作的算法之前，先回顾一下本书算法中常用到的两个C函数。函数。1) malloc(int size) 功能：功能：在系统内存中分配在系统内存中分配size个存储单元，并返回该空间的基址。个存储单元，并返回该

23、空间的基址。 使用方法：使用方法： . int m = 100； float *p; p = (float *) malloc(m*sizeof(float ); 执行语句执行语句p = (float *) malloc(m*sizeof(float)，计算机将按，计算机将按float 类型类型变量所占空间的大小（一般为变量所占空间的大小（一般为32bit）分配）分配m* sizeof(float)个存储单元个存储单元,并并将其基址赋值给指针变量将其基址赋值给指针变量p;0 0 1 1 2 2 9999p p执行执行 p = (float *) malloc(m*sizeof(float) 图

24、示 调用free ( p ) 0 0 1 1 2 2 9999p p 调用调用free ( p ) 图示图示2) free ( p ) 功能：功能：将指针变量将指针变量p所指示的存储空间，回收到系统内存空间中去。所指示的存储空间，回收到系统内存空间中去。使用方法：使用方法： . int m = 100; float *p; p = (float*) malloc(m*sizeof(float); / 一旦一旦p所指示的内存空间不再使用，所指示的内存空间不再使用， /调用调用free( ) 回收之回收之 free(p);如何在顺序表如何在顺序表上实现线性表的基本操作？上实现线性表的基本操作？如何

25、建空表？如何求表长？如何建空表？如何求表长？如何插入？删除？如何插入？删除？ 设线性表用设线性表用顺序表顺序表L存储，下面我们介绍用顺序表存储存储，下面我们介绍用顺序表存储线性表时，各种基本操作的算法。当线性表用顺序表存储线性表时，各种基本操作的算法。当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存中的时，对线性表各种基本操作实际上就是对存储在内存中的顺序表进行操作。顺序表进行操作。1）初始化操作）初始化操作 InitList_Sq( SqList &L)参数参数：L是存放线性表的结构变量（称是存放线性表的结构变量（称L为顺序表为顺序表）, 因为因为插入操作对顺序表插

26、入操作对顺序表L进行了修改，所以用了引用参数进行了修改，所以用了引用参数&L功能：功能：建立空的顺序表建立空的顺序表L主要步骤：主要步骤：调用调用malloc ( )为顺序表分配一预定大小为顺序表分配一预定大小(LIST_INIT_SIZE）的空间，并将其基址赋值给）的空间，并将其基址赋值给L.elem 顺序表初始化0 01 1LIST_INIT_SIZE-1LIST_INIT_SIZE-1L.lengthL.lengthL.listsizeL.listsizeL.elemL.elem 0 0LIST_INIT_SIZELIST_INIT_SIZE初始化操作算法：初始化操作算法：Sta

27、tus InitList_Sq(SqList &L) /构造一个空的顺序表构造一个空的顺序表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (! L.elem) exit(OVERFLOW); /存储分配失败存储分配失败L. length=0; /空表长度为空表长度为0L.listsize=LIST_INIT_SIZE; /初始存储容量初始存储容量Return OK;/InitList_Sq 算法算法2.3 销毁顺序表销毁顺序表L.lengthL.lengthL.listsizeL.listsizeL.elemL

28、.elem0 01 1LIST_INIT_SIZE-1LIST_INIT_SIZE-1a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n n nLIST_INIT_SIZELIST_INIT_SIZE0 00 0=null=null2）销毁操作）销毁操作 DestroyList ( SqList &L) 功能：功能：回收为顺序表动态分配的存储空间回收为顺序表动态分配的存储空间主要步骤：主要步骤：调用调用free( ) 回收为顺序表动态分配的存储空间回收为顺序表动态分配的存储空间销毁操作算法：销毁操作算法：Status DestroyList_Sq (

29、SqList &L) if (!L.elem) return ERROR; / 若表若表L不存在不存在 free (L.elem); / 若表若表L已存在，回收动态分配的存储空间已存在，回收动态分配的存储空间 L.elem = null; L.length = 0; L.Listsize = 0; return OK;/ DestroyList_Sq3）置空操作）置空操作ClearList_Sq ( SqList &L) 功能：功能：若若L已存在，重新将其置成空表已存在，重新将其置成空表算法：算法： Status ClearList_Sq ( SqList &L) if

30、 (!L.elem) return ERROR; / 若表若表L不存在不存在 L.length = 0; /若表若表L已存在，将已存在，将L置空置空 return OK;/ ClearList_SqL.lengthL.lengthL.listsizeL.listsizeL.elemL.elem0 01 1 99 99a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an n n nLIST_INIT_SIZELIST_INIT_SIZE 0 0 置空操作图示置空操作图示置空置空4）取元素操作）取元素操作 GetElem_Sq ( SqList L, int i, El

31、emType &e )功能：功能：将顺序表中第将顺序表中第i 个元素赋值给个元素赋值给 e算法：算法：Status GetElem_Sq ( SqList &L, int i, ElemType &e ) if (i L.length ) return ERROR; / i 非法非法 e = L.elem i-1 ; /将顺序表中第将顺序表中第i 个元素赋值给个元素赋值给 e return OK;/ GetElem_Sq 由于由于C语言的一维数组下标从语言的一维数组下标从0开始开始, 故线性表的第一个元故线性表的第一个元素放在素放在L.elem0，第，第i个元素放个元素

32、放L.elemi-1中，最后一个元素放中，最后一个元素放在在 L.elemL.length-1中。中。 取元素操作取元素操作e ea ai iL.lengthL.lengthL.listsizeL.listsizeL.elemL.elem0 01 1LIST_INIT_SIZE-1LIST_INIT_SIZE-1a a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nn n LIST_INIT_SIZE LIST_INIT_SIZE5）插入操作）插入操作 ListInsert_Sq ( &L, i, e ) 参数：参数：L ：顺序表：顺序表 ， i 插入位置

33、，插入位置， e 被插入元素；被插入元素； 因为插因为插入操作对顺序表进行修改，所以用了引用参数入操作对顺序表进行修改，所以用了引用参数&L； 功能：功能：在顺序表在顺序表L的第的第i个元素之前插入一个新元素个元素之前插入一个新元素e 0 a11 a2i-2 ai-1i-1 aii ai+1n-1 an插插 入入 前前0 a11 a2i-2 ai-1i-1 ei aii+1 ai+1n-1 an插插 入入 后后插入操作示意图插入操作示意图 为初学者易于理解插入算法主要步骤，这里简化了书为初学者易于理解插入算法主要步骤，这里简化了书上的插入算法上的插入算法2.42.4，对插入算法中表空间

34、已满的情况，只，对插入算法中表空间已满的情况，只简单的返回出错（简单的返回出错（ERRORERROR），），在在2.22.2节的最后部分给出完整节的最后部分给出完整的插入算法。当然，应用中对各种情况如何处理，要根据的插入算法。当然，应用中对各种情况如何处理，要根据实际问题的需要来决定。实际问题的需要来决定。注意注意插入操作主要步骤：插入操作主要步骤：1）i 是否合法，若合法转是否合法，若合法转2），否则算法结束，并返回），否则算法结束，并返回ERROR；2）L是否已满，若未满转是否已满，若未满转3），否则算法结束，并返回），否则算法结束，并返回ERROR；3）将顺序表）将顺序表ai 及之后的所

35、有元素后移一个位置；及之后的所有元素后移一个位置；4) 将新元素写入空出的位置；将新元素写入空出的位置；5）表长）表长+1 。 Status ListInsert_Sq(SqList &L, int i , ElemType e) /在顺序表在顺序表L中第中第i个位置之前插入新的元素个位置之前插入新的元素e, / i的合法值为的合法值为1iL.lL.length+1,当当i =L.lL.length+1时时e插在表尾插在表尾 if (iL.length+1) return ERROR; / i值不合法值不合法 if (L.length=L.listsize) return ERROR;

36、 /顺序表已满顺序表已满 for ( j=L.length-1 ; j= i-1; -j) L.elemj+1= L.elem j; /插入位置及其之后的元素后移一个位置插入位置及其之后的元素后移一个位置 L.elemi-1 =e; /插入插入e +L.length; /表长增表长增1 return OK;/ListInsert_Sq 算法算法2.4 a 插入操作算法插入操作算法为初学者易于理解插入算为初学者易于理解插入算法，这里通过下标引用法，这里通过下标引用L L.elem.elem中的元素。中的元素。Status ListInsert_Sq(SqList &L, int i, E

37、lemType e) /在顺序表在顺序表L中第中第i个位置之前插入新的元素个位置之前插入新的元素e, /i的合法值为的合法值为1iL.lL.length+1 if (iL.length+1) return ERROR; /i值不合法值不合法 if (L.length=L.listsize) return ERROR; /顺序表已满顺序表已满 q=&(L.elem i-1); /q为插入位置为插入位置 for (p=&(L. elemL.length-1) ; p=q; -p) *(p+1)=*p; /插入位置及之后的元素后移一个位置插入位置及之后的元素后移一个位置 *q=e;

38、/插入插入e +L.length; /表长加表长加1 return OK;/ListInsert_Sq 算法算法2.4 b算法算法2.4b2.4b与算法与算法2.4a 2.4a 唯唯一的不同是一的不同是通过指针通过指针p p引引用用L L.elem.elem中的元素。中的元素。Status ListInsert_Sq(SqList &L, int i, ElemType e) /在顺序线性表在顺序线性表L中第中第i个位置之前插入新的元素个位置之前插入新的元素e, / i的合法值为的合法值为1iListLength_Sq(L)+1 if (iL.length+1) return ERRO

39、R; /i值不合法值不合法 if (L.length=L.listsize) /当前存储空间已满，重新分配空间当前存储空间已满，重新分配空间 newbase=(ElemType*) realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) exit(OVERFLOW); /存储分配失败存储分配失败 L. elem=newbase; /新基址新基址 L.listsize+=LISTINCREMENT; /增加存储容量增加存储容量 q=&(L.elemi-1); /q为插入位置为插入位置 for

40、(p=&(L. elemL.length-1); p=q ; -p)*(p+1) = *p; /插入位置及之后的元素右移插入位置及之后的元素右移 *q=e; /插入插入e +L.length; /表长增表长增1 return OK;/ListInsert_Sq 算法算法2.4表空间已表空间已满情况的满情况的处理处理现在给出完整的插入操作算法！现在给出完整的插入操作算法！在插入数据前查看表空间是否已满在插入数据前查看表空间是否已满L.listsizena a1 1a a2 2a ai-1i-1a ai ia ai+1i+1a an nL.elem01n01n+10a a1 1a a2 2

41、a ai-1i-1a ai ia ai+1i+1a an nn+10将新空间长度赋给将新空间长度赋给L.listsize若满，若满，调用调用realloc()分配一个更大的分配一个更大的存储空间存储空间将数据复制到将数据复制到新的空间中新的空间中L.lengthn顺序表插入对表空间已满情况的处理顺序表插入对表空间已满情况的处理 插入位置插入位置 移动元素个数移动元素个数 1 n 2 n-1 i n-i+1 n 1 n+1 0插入算法时间复杂度分析插入算法时间复杂度分析 顺序表的插入算法顺序表的插入算法2.4a或或2.4b中，基本操作是移动元素中，基本操作是移动元素，算法时间复杂度取决于移动元素

42、的个数算法时间复杂度取决于移动元素的个数，即算法时间复杂，即算法时间复杂度取决于算法中循环体执行的次数。移动元素的个数不仅与度取决于算法中循环体执行的次数。移动元素的个数不仅与表长有关，而且与插入位置有关。表长有关，而且与插入位置有关。由此可见：由此可见：在顺序表中插入一个元素在顺序表中插入一个元素 ，平均要移动表中一半元素。，平均要移动表中一半元素。表长为表长为n的顺序表，插入算法的时间复杂度为的顺序表，插入算法的时间复杂度为 O（n）。）。假设在线性表的任何位置插入元素的概率相同，即假设在线性表的任何位置插入元素的概率相同，即pi= 1/(n+1)，则则：若用若用pi表示在顺序表的第表示在

43、顺序表的第i个元素之前插入元素的概率，在长个元素之前插入元素的概率，在长度为度为n的顺序表中插入一个元素，所需移动元素个数的数学期的顺序表中插入一个元素，所需移动元素个数的数学期望值为：望值为： 11(1)nisiiEpni111(1)12nisinEnin6）删除操作）删除操作 ListDelete_sq ( SqList &L, int i, ElemType &e ) 功能：功能：删除顺序表删除顺序表L中第中第i个元素，并用个元素，并用e返回返回0 a11 a2i - 2 ai - 1i - 1 aii ai + 1n - 1 an删删 除除 前前0 a11 a2i -

44、2 ai - 1i - 1 ai + 1i ai + 2i + 1 ai + 3n - 1 an删删 除除 后后aie删除操作图示删除操作图示 删除操作主要步骤删除操作主要步骤 ：1）i 不合法或表空，算法结束，并返回不合法或表空，算法结束，并返回ERROR；否则转否则转2）2）将）将ai赋值给赋值给e; 3）将顺序表中）将顺序表中ai后面的元素依次向前移动一个位置后面的元素依次向前移动一个位置;4）表长）表长-1。删除操作算法删除操作算法Status ListDelete_Sq(SqList &L, int i, ElemType &e) /在顺序表在顺序表L中删除第中删除第

45、 i个元素，并用个元素，并用e返回其值返回其值 /i的合法值为的合法值为1iL.lL.length，表空，表空L.length=0 则则i L.lL.length if (iL.length) return ERROR; / i值不合法或表空值不合法或表空 e = L.elemi-1; /被删除元素的值赋给被删除元素的值赋给e for ( j= i; j L.length if(iL.Length) return ERROR; / i值不合法或表空值不合法或表空 p=&(L.elemi-1); /p为被删除元素的位置为被删除元素的位置 e=*p; / 被删除元素的值赋给被删除元素的值赋

46、给e q=L.elemL.length-1; / 表尾元素的位置表尾元素的位置 for (+p; p=q;+p)*(p-1)=*p; /被删除元素之后的元素前移被删除元素之后的元素前移 -L.length; /表长减表长减1 return OK;/ListDelete_Sq 算法算法2.5 b算法算法2.5b2.5b与算法与算法2.5a 2.5a 唯唯一的不同是一的不同是通过指针通过指针p p引引用用L L.elem.elem中的元素。中的元素。删除操作算法删除操作算法例：将两个有序线性表归并成一个有序线性表。例：将两个有序线性表归并成一个有序线性表。设线性表设线性表A、B分别用分别用La 、

47、 Lb 的两个顺序表存储，两顺序表中的两个顺序表存储，两顺序表中元素元素按非递减按非递减顺序排列，编写算法：将顺序排列，编写算法：将La 、 Lb归并得到顺序归并得到顺序表表Lc, Lc中的元素也按值非递减顺序排列。中的元素也按值非递减顺序排列。实现上述功能的算法有很多，如：实现上述功能的算法有很多，如： 1）将）将Lb并入并入La;2）将）将La并入并入Lb;3）将）将La,Lb并入并入Lc (顺序表顺序表Lc中的空间是新分配的存储空间）中的空间是新分配的存储空间） ;此处采用第三种，其基本思想：同时对此处采用第三种，其基本思想：同时对La.elem, Lb.elem 进行扫进行扫描，在扫描

48、过程中按照两表描，在扫描过程中按照两表当前元素当前元素的大小，依次将其插入到的大小，依次将其插入到Lc的表尾。的表尾。三、利用基本操作实现线性表的其他操作三、利用基本操作实现线性表的其他操作 现在来回答现在来回答2.1中提到的问题中提到的问题, 如何利用已有基本操作实现线性表如何利用已有基本操作实现线性表的其他操作。的其他操作。Void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) /已知顺序表已知顺序表La和和Lb中的数据元素按值非递减排列，中的数据元素按值非递减排列， /归并归并La和和Lb得到新的顺序表得到新的顺序表Lc，Lc的数据

49、元素也按值非递减排列。的数据元素也按值非递减排列。 InitList_Sq(Lc)； i=j=1;k=0; La_len=Listength_Sq(La); Lb_len=ListLength_Sq(Lb); While(i=La_len)&(j=Lb_len) /La和和Lb均非空均非空GetElem_Sq(La, i, ai); GetElem_Sq(Lb, j, bj);if(ai=bj) ListInsert_Sq(Lc, +k, ai); +.i;else ListInsert_Sq(Lc, +k, bj); +j; while(i=La_len) GetElem_Sq(La

50、, .i+, ai); ListInsert_Sq(Lc, +k, ai); while(j=Lb_len) GetElem_Sq(Lb, .j+, bj); ListInsert_Sq (Lc, +k,bj); /MergeList_Sq 算法算法2.7 aLc.elemLc.lengthLc.listsize顺序表的归并图示顺序表的归并图示（算法算法2.7a)0199La.elem358La.length3 100 100La.listsize0199Lb.elem2689Lb.length4 100 100Lb.listsize01992356889 100 100建空表建空表LcLc0

51、La,LbLa,Lb归并归并7void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) /已知顺序表已知顺序表La和和Lb的元素按值非递减排列的元素按值非递减排列 /归并归并La和和Lb得到新的顺序表得到新的顺序表Lc,Lc的元素也按值非递减排列的元素也按值非递减排列 pa=La.elem; pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem)

52、exit(OVERFLOW);/存储分配失败存储分配失败 pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last &pb=pb_last) /归并归并 if(*pa=*pb)*pc+=*pa+; else *pc+=*pb+; while (pa=pa_last)*pc+=*pa+; /插入插入La的剩余元素的剩余元素 while (pbnext = null; return OK;/ InitList_L 1、初始化操作、初始化操作InitList_L (LinkList &L) 功

53、能：功能： 建空线性链表建空线性链表L参数：参数： L为线性链表的头指针为线性链表的头指针主要步骤：主要步骤：调用调用malloc ( )分配一结点的空间分配一结点的空间,并将其地址并将其地址赋值给赋值给L2、取元素操作、取元素操作 GetElem_L ( LinkList L, int i, ElemType &e )功能：功能：将线性链表中第将线性链表中第i 个元素赋值给个元素赋值给 e取元素操作主要步骤：取元素操作主要步骤：1）查找链表中第）查找链表中第 i个元素结点；个元素结点；2）将第）将第i个元素结点中的数据元素赋值给个元素结点中的数据元素赋值给e;e eaiai-1aia

54、2a1ai+1nanL L 取元素元素操作图示取元素元素操作图示取元素操作算法：取元素操作算法：Status GetElem_L(LinkList L, int i, ElemType &e) /L为带头结点单链表的头指针，当第为带头结点单链表的头指针，当第i个元素存在时，个元素存在时， /其值赋给其值赋给e并返回并返回OK，否则返回，否则返回ERROR p=L-next; j=1; /初始化，初始化，p指向第一个结点，指向第一个结点，j为计数器为计数器 while(p& jnext; +j; if (!p | ji) return ERROR; /第第i个元素不存在个元素不存

55、在 e=p-data; /取第取第i个元素个元素 return OK;/GetElem_L 算法算法 2.83、插入操作、插入操作 ListInsert_L(LinkList &L, int i, ElemType e)功能：功能：在线性链表在线性链表L的第的第i个元素结点之前插入一个新元素结点个元素结点之前插入一个新元素结点插入前插入前ai-1aia2a1ai+1nanL L插入后插入后 ai-1aia2a1ai+1naneL L插入操作图示：插入操作图示：插入操作算法：插入操作算法：Status ListInsert_L(LinkList &L, int i, ElemTy

56、pe e) /在带头结点的线性链表在带头结点的线性链表L中第中第i个结点之前插入元素个结点之前插入元素e p=L; j=0; while (p & jnext; +j; /寻找第寻找第i-1个结点个结点 if(!p | jj-1) return ERROR; / i小于小于1或者大于表长或者大于表长 s=(LinkList) malloc(sizeof(LNode); / 分配新结点分配新结点 s-data=e; s-next=p-next; p-next=s; /插入新结点插入新结点 return OK;/LinstInsert_L 算法算法 2.9插入操作主要步骤：插入操作主要步骤

57、：1）查找链表）查找链表L的第的第 i-1个元素结点；个元素结点；2）为新元素建立结点；）为新元素建立结点；3）修改新元素结点指针和第）修改新元素结点指针和第 i-1个元素结点的指针完成插入个元素结点的指针完成插入；4、删除操作、删除操作 ListDelete_L(LinkList &L, int i, ElemType &e) 功能：功能：在线性链表在线性链表L中删除第中删除第i个元素，并且用个元素，并且用e 返回其值返回其值删除前删除前ai-1aia2a1ai+1nanL L删除后删除后ai-1aia2a1ai+1nanL L 删除操作图示：删除操作图示：删除操作主要步骤：

58、删除操作主要步骤：1）查找线性链表）查找线性链表L的第的第 i-1个元素结点；个元素结点；2）修改第）修改第 i-1个元素结点的指针，删除第个元素结点的指针，删除第i个元素结点；个元素结点；3) 将第将第i个元素结点中的数据元素赋值给个元素结点中的数据元素赋值给e;4）回收被删除结点空间；）回收被删除结点空间；删除操作算法：删除操作算法：Status ListDelete_L(LinkList &L, int i, ElemType &e) /在带头结点的单链线性表在带头结点的单链线性表L中，删除第中，删除第i个元素并由个元素并由e返回其值返回其值 p=L; j=0; whil

59、e (p-next&jnext; +j; if (!(p-next) | ji-1) return ERROR; /表中无第表中无第i个结点个结点 q=p-next; p-next=q-next; /删除结点删除结点 e =q-data; free(q); /回收（回收（释放）结点空间释放）结点空间 return OK;/LinstDelete_L 算法算法 2.10三、静态链表三、静态链表1、静态链表的概念、静态链表的概念 用一维数组表示的线性链表，称为静态链表。用一维数组表示的线性链表，称为静态链表。SLinkList：数组的类型名；数组的类型名；SLinkList类型的数组变量是

60、结构数组，每一数组分量包括类型的数组变量是结构数组，每一数组分量包括两个域：两个域：data：用于存储线性表元素用于存储线性表元素cur： 用于存储直接后继元素在数组中的位置（下标）用于存储直接后继元素在数组中的位置（下标）2、静态链表的类型定义、静态链表的类型定义#define MAXSIZE 1000 /链链表的最大长度表的最大长度typedef structElemType data; int cur; component, SLinkListMAXSIZE;静态链表图示静态链表图示0123456789107a40a32a19a24a a4 4a a3 3a a1 1a a2 2 nullnull101010101024102410141014101010121014101610181020102210241026线性链表图示线性链表图示数组数组下标下标地址地址静态链表与静态链表与线性链表线性链表的区别？的区别？3、静态链表图示、静态链表图示0123456789101ZHAO2QIAN3SUN4LI9ZHOU6WU7ZHENG8WANG0SHI50123456789101ZHAO2QIAN3SUN