数据结构--线性表.pptx

第二章第二章 线性表线性表在本课程介绍的几种数据结构中，在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使数据结构，线性表在实际应用大量使用，并不是一个陌生的概念。用，并不是一个陌生的概念。第1页/共103页 基本内容基本内容基本内容基本内容 1 1 1 1 线性表的概念；线性表的概念；线性表的概念；线性表的概念；2 2 2 2 线性表两类存储结构和它们的类型定义；线性表两类存储结构和它们的类型定义；线性表两类存储结构和它们的类型定义；线性表两类存储结构和它们的类型定义；3 3 3 3 在这些存储结构下，线性表的基本操作的算法；在这些存储结构下，线性表的基本操作的算法；在这些存储结构下，线性表的基本操作的算法；在这些存储结构下，线性表的基本操作的算法；学习要点：学习要点：学习要点：学习要点：1 1 1 1 了解线性表逻辑结构的特征了解线性表逻辑结构的特征了解线性表逻辑结构的特征了解线性表逻辑结构的特征;2 2 2 2 重点掌握线性表的顺序存储结构和链式存储结构，它重点掌握线性表的顺序存储结构和链式存储结构，它重点掌握线性表的顺序存储结构和链式存储结构，它重点掌握线性表的顺序存储结构和链式存储结构，它们如们如们如们如 何表达线性表中数据元素之间的结构关系；如何用何表达线性表中数据元素之间的结构关系；如何用何表达线性表中数据元素之间的结构关系；如何用何表达线性表中数据元素之间的结构关系；如何用C C C C语语语语言言言言 描述它们的类型定义；描述它们的类型定义；描述它们的类型定义；描述它们的类型定义；3 3 3 3 掌握在顺序存储结构下，线性表的基本操作的算法；掌握在顺序存储结构下，线性表的基本操作的算法；掌握在顺序存储结构下，线性表的基本操作的算法；掌握在顺序存储结构下，线性表的基本操作的算法；4 4 4 4 掌握在链式存储结构下，线性表的基本操作的算法；掌握在链式存储结构下，线性表的基本操作的算法；掌握在链式存储结构下，线性表的基本操作的算法；掌握在链式存储结构下，线性表的基本操作的算法；5 5 5 5 能够从时间复杂度的角度，比较线性表两类存储结构能够从时间复杂度的角度，比较线性表两类存储结构能够从时间复杂度的角度，比较线性表两类存储结构能够从时间复杂度的角度，比较线性表两类存储结构 的不同特点及适用场合；的不同特点及适用场合；的不同特点及适用场合；的不同特点及适用场合；第二章第二章 线性线性表表第2页/共103页线性表是线性表是线性表是线性表是n n n n 个类型相同数据元素的有限序列，通常个类型相同数据元素的有限序列，通常个类型相同数据元素的有限序列，通常个类型相同数据元素的有限序列，通常记作记作记作记作(a(a(a(a1 1 1 1,a,a,a,a2 2 2 2,a a a a3 3 3 3,a,a,a,an n n n)2.1 2.1 线性表的概念线性表的概念例例例例1 1 1 1、数学中的数列（、数学中的数列（、数学中的数列（、数学中的数列（11111111，13131313，15151515，17171717，19191919，21212121）例例例例2 2 2 2、英文字母表（、英文字母表（、英文字母表（、英文字母表（A,B,C,D,EA,B,C,D,EA,B,C,D,EA,B,C,D,E Z Z Z Z）。例例例例3 3 3 3、某单位的电话号码簿。、某单位的电话号码簿。、某单位的电话号码簿。、某单位的电话号码簿。一、线性表的逻辑结一、线性表的逻辑结构构电话号码簿是数据元素电话号码簿是数据元素电话号码簿是数据元素电话号码簿是数据元素的有限序列，每一数据的有限序列，每一数据的有限序列，每一数据的有限序列，每一数据元素包括两个数据项，元素包括两个数据项，元素包括两个数据项，元素包括两个数据项，一个是用户姓名，一个一个是用户姓名，一个一个是用户姓名，一个一个是用户姓名，一个是对应的电话号码。是对应的电话号码。是对应的电话号码。是对应的电话号码。姓名姓名姓名姓名 电话号码电话号码电话号码电话号码 蔡颖蔡颖蔡颖蔡颖 63214444 63214444 63214444 63214444 陈红陈红陈红陈红 63217777 63217777 63217777 63217777 刘建平刘建平刘建平刘建平 63216666 63216666 63216666 63216666 王小林王小林王小林王小林 63218888 63218888 63218888 63218888 张力张力张力张力 63215555 63215555 63215555 63215555.第3页/共103页2.1 2.1 线性表的概念线性表的概念说明：说明：说明：说明：设设设设 A=(aA=(aA=(aA=(a1 1 1 1,a,a,a,a2 2 2 2,.,a,.,a,.,a,.,ai-1i-1i-1i-1,a,a,a,ai i i i,a,a,a,ai+1i+1i+1i+1,a,a,a,an n n n)是一线性表是一线性表是一线性表是一线性表1 1 1 1）线性表的数据元素可以是各种各样的，但同一线性表中的元）线性表的数据元素可以是各种各样的，但同一线性表中的元）线性表的数据元素可以是各种各样的，但同一线性表中的元）线性表的数据元素可以是各种各样的，但同一线性表中的元素须是同一类型的；素须是同一类型的；素须是同一类型的；素须是同一类型的；2 2 2 2）在表中）在表中）在表中）在表中a a a ai-1i-1i-1i-1领先于领先于领先于领先于a a a ai i i i，a a a ai i i i领先于领先于领先于领先于a a a ai+1i+1i+1i+1，称称称称a a a ai-1i-1i-1i-1是是是是a a a ai i i i的直接前趋，的直接前趋，的直接前趋，的直接前趋，a a a ai+1i+1i+1i+1是是是是a a a ai i i i的直接后继；的直接后继；的直接后继；的直接后继；3 3 3 3）在线性表中，除第一个元素和最后一个元素之外，其他元素）在线性表中，除第一个元素和最后一个元素之外，其他元素）在线性表中，除第一个元素和最后一个元素之外，其他元素）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；构特征的数据结构称为线性结构。线性表是一种线性数据结构；构特征的数据结构称为线性结构。线性表是一种线性数据结构；构特征的数据结构称为线性结构。线性表是一种线性数据结构；4 4 4 4）线性表中元素的个数）线性表中元素的个数）线性表中元素的个数）线性表中元素的个数n n n n称为线性表的长度，称为线性表的长度，称为线性表的长度，称为线性表的长度，n=0n=0n=0n=0时称为空表；时称为空表；时称为空表；时称为空表；5 5 5 5）a a a ai i i i是线性表的第是线性表的第是线性表的第是线性表的第i i i i个元素，称个元素，称个元素，称个元素，称i i i i为数据元素为数据元素为数据元素为数据元素a a a ai i i i的序号，每一个元的序号，每一个元的序号，每一个元的序号，每一个元素在线性表中的位置，仅取决于它的序号；素在线性表中的位置，仅取决于它的序号；素在线性表中的位置，仅取决于它的序号；素在线性表中的位置，仅取决于它的序号；第4页/共103页2.1 2.1 线性表的概念线性表的概念设设设设L=L=L=L=（a a a a1 1 1 1,a,a,a,a2,2,2,2,.a.a.a.ai-1i-1i-1i-1,a a a ai i i i,a a a ai+1i+1i+1i+1,a,a,a,an n n n）是一线性表是一线性表是一线性表是一线性表1 1 1 1 初始化操作初始化操作初始化操作初始化操作 InitList(&L)InitList(&L)InitList(&L)InitList(&L)功能：建立空的线性表功能：建立空的线性表功能：建立空的线性表功能：建立空的线性表L L L L；2 2 2 2 销毁操作销毁操作销毁操作销毁操作DetroyList(&L)DetroyList(&L)DetroyList(&L)DetroyList(&L)功能：回收为线性表功能：回收为线性表功能：回收为线性表功能：回收为线性表L L L L动态分配的存储空间；动态分配的存储空间；动态分配的存储空间；动态分配的存储空间；3 3 3 3 置空操作置空操作置空操作置空操作ClearList(&L)ClearList(&L)ClearList(&L)ClearList(&L)功能：功能：功能：功能：L L L L中已存在，重新将其置成空表；中已存在，重新将其置成空表；中已存在，重新将其置成空表；中已存在，重新将其置成空表；4 4 4 4 判空操作判空操作判空操作判空操作ListEmpty(L)ListEmpty(L)ListEmpty(L)ListEmpty(L)功能：判断线性表功能：判断线性表功能：判断线性表功能：判断线性表L L L L是否为空表，若为空表返回是否为空表，若为空表返回是否为空表，若为空表返回是否为空表，若为空表返回TRUETRUETRUETRUE，否则返回否则返回否则返回否则返回FALSEFALSEFALSEFALSE；5 5 5 5 求表长操作求表长操作求表长操作求表长操作 ListLength(L)ListLength(L)ListLength(L)ListLength(L)功能：返回线性表功能：返回线性表功能：返回线性表功能：返回线性表L L L L的表长；的表长；的表长；的表长；二、线性表的基本操作6 6 6 6 取元素操作取元素操作取元素操作取元素操作：GetElem(L,i,&e)GetElem(L,i,&e)GetElem(L,i,&e)GetElem(L,i,&e)功能：将线性表功能：将线性表功能：将线性表功能：将线性表L L L L中第中第中第中第i i i i 个元素赋值给个元素赋值给个元素赋值给个元素赋值给 e e e e；7 7 7 7 查找操作查找操作查找操作查找操作 LocateElem(L,e,compare()LocateElem(L,e,compare()LocateElem(L,e,compare()LocateElem(L,e,compare()功能：在线性表功能：在线性表功能：在线性表功能：在线性表L L L L中查找与元素中查找与元素中查找与元素中查找与元素e e e e满足满足满足满足compare()compare()compare()compare()的第的第的第的第1 1 1 1个元素，返回个元素，返回个元素，返回个元素，返回该该该该 元素在表中的序号（或位置），若表中不存在这样的元素，则返回元素在表中的序号（或位置），若表中不存在这样的元素，则返回元素在表中的序号（或位置），若表中不存在这样的元素，则返回元素在表中的序号（或位置），若表中不存在这样的元素，则返回0 0 0 0；8 8 8 8 插入操作插入操作插入操作插入操作 ListInsert(&L,i,e)ListInsert(&L,i,e)ListInsert(&L,i,e)ListInsert(&L,i,e)功能：在线性表功能：在线性表功能：在线性表功能：在线性表L L L L的第的第的第的第i i i i个元素之前插入一个新元素个元素之前插入一个新元素个元素之前插入一个新元素个元素之前插入一个新元素e;e;e;e;9 9 9 9 删除操作删除操作删除操作删除操作 ListDelete(&L,i,&e)ListDelete(&L,i,&e)ListDelete(&L,i,&e)ListDelete(&L,i,&e)功能：删除线性表功能：删除线性表功能：删除线性表功能：删除线性表L L L L的第的第的第的第i i i i个元素，并用个元素，并用个元素，并用个元素，并用e e e e返回；返回；返回；返回；10 10 10 10 遍历操作遍历操作遍历操作遍历操作 ListTraverse(&L,visit()ListTraverse(&L,visit()ListTraverse(&L,visit()ListTraverse(&L,visit()功能：依次对线性表功能：依次对线性表功能：依次对线性表功能：依次对线性表L L L L的每一个元素调用函数的每一个元素调用函数的每一个元素调用函数的每一个元素调用函数visit()visit()visit()visit()。若若若若visit()visit()visit()visit()失失失失 败，则返回败，则返回败，则返回败，则返回ERRORERRORERRORERROR，否则返回否则返回否则返回否则返回OKOKOKOK；说明说明说明说明1 1 1 1 上面列出的操作，只是线性表的一些常用的基本操作；上面列出的操作，只是线性表的一些常用的基本操作；上面列出的操作，只是线性表的一些常用的基本操作；上面列出的操作，只是线性表的一些常用的基本操作；2 2 2 2 不同的应用，基本操作可能是不同的；不同的应用，基本操作可能是不同的；不同的应用，基本操作可能是不同的；不同的应用，基本操作可能是不同的；例如：上面列出的删除操作例如：上面列出的删除操作例如：上面列出的删除操作例如：上面列出的删除操作Delete(&L,i,&e),Delete(&L,i,&e),Delete(&L,i,&e),Delete(&L,i,&e),功能是在线性表功能是在线性表功能是在线性表功能是在线性表L L L L中删除第中删除第中删除第中删除第i i i i个元素，并用个元素，并用个元素，并用个元素，并用e e e e返回其值。返回其值。返回其值。返回其值。在电话号码查询系统中，一旦某在电话号码查询系统中，一旦某在电话号码查询系统中，一旦某在电话号码查询系统中，一旦某用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与给定元素给定元素给定元素给定元素e e e e值相同的数据元素；值相同的数据元素；值相同的数据元素；值相同的数据元素；3 3 3 3 线性表的复杂操作可通过基本操作实现；线性表的复杂操作可通过基本操作实现；线性表的复杂操作可通过基本操作实现；线性表的复杂操作可通过基本操作实现；这有点类似于数中的情形，例如整数的基本操作是这有点类似于数中的情形，例如整数的基本操作是这有点类似于数中的情形，例如整数的基本操作是这有点类似于数中的情形，例如整数的基本操作是+,-,+,-,+,-,+,-,/。如果要。如果要。如果要。如果要求某班同学的平均年龄则可利用求某班同学的平均年龄则可利用求某班同学的平均年龄则可利用求某班同学的平均年龄则可利用+/+/+/+/实现，全班同学的平均年龄实现，全班同学的平均年龄实现，全班同学的平均年龄实现，全班同学的平均年龄 =(=(=(=(age1+age2+age3+age1+age2+age3+age1+age2+age3+age1+age2+age3+)/)/)/)/全班同学的全班同学的全班同学的全班同学的人数人数人数人数 例如，我们要在设计一个电话号码询系统，显然这个系统至少例如，我们要在设计一个电话号码询系统，显然这个系统至少例如，我们要在设计一个电话号码询系统，显然这个系统至少例如，我们要在设计一个电话号码询系统，显然这个系统至少要具备下列功能：要具备下列功能：要具备下列功能：要具备下列功能：查询某人的电话号码；查询某人的电话号码；查询某人的电话号码；查询某人的电话号码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；由上我们知道，电话号码薄可用线性表表示，上面列出的功由上我们知道，电话号码薄可用线性表表示，上面列出的功由上我们知道，电话号码薄可用线性表表示，上面列出的功由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就是对线性表的查找、插入、删除操作，为了在计算能实际上就是对线性表的查找、插入、删除操作，为了在计算能实际上就是对线性表的查找、插入、删除操作，为了在计算能实际上就是对线性表的查找、插入、删除操作，为了在计算机上实现上述功能，我们应该做什么呢？机上实现上述功能，我们应该做什么呢？机上实现上述功能，我们应该做什么呢？机上实现上述功能，我们应该做什么呢？显然，首先需要将电话号码薄上的信息存储到计算机中，然显然，首先需要将电话号码薄上的信息存储到计算机中，然显然，首先需要将电话号码薄上的信息存储到计算机中，然显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对这些信息进行加工处理，实现上述功能。后才可能对这些信息进行加工处理，实现上述功能。后才可能对这些信息进行加工处理，实现上述功能。后才可能对这些信息进行加工处理，实现上述功能。第5页/共103页 2.2.2 2线性表的线性表的顺序存储顺序存储和实现和实现 一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构顺序表顺序表顺序表顺序表 1 1 1 1.线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构 2 2 2 2.顺序表的类型定义顺序表的类型定义顺序表的类型定义顺序表的类型定义二、顺序表的基本操作算法二、顺序表的基本操作算法二、顺序表的基本操作算法二、顺序表的基本操作算法三、利用基本操作实现线性表的其他操三、利用基本操作实现线性表的其他操三、利用基本操作实现线性表的其他操三、利用基本操作实现线性表的其他操作作作作第6页/共103页为了存储线性表，至少要保存两类信息：为了存储线性表，至少要保存两类信息：1 1）线性表中的数据元素；）线性表中的数据元素；2 2）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系；2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现在计算机内部可以采用不同的方式来存在计算机内部可以采用不同的方式来存储一个线性表，其中最简单的方式就是本储一个线性表，其中最简单的方式就是本节要讲的线性表的顺序存储结构。节要讲的线性表的顺序存储结构。第7页/共103页线性表的线性表的线性表的线性表的顺序顺序顺序顺序存储结构，就是用一组存储结构，就是用一组存储结构，就是用一组存储结构，就是用一组连连连连续续续续的内存单元的内存单元的内存单元的内存单元依次依次依次依次存放线性表的数据元存放线性表的数据元存放线性表的数据元存放线性表的数据元素。素。素。素。用顺序表存储线性表时，数据元素之用顺序表存储线性表时，数据元素之用顺序表存储线性表时，数据元素之用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存间的逻辑关系，是通过数据元素的存间的逻辑关系，是通过数据元素的存间的逻辑关系，是通过数据元素的存储顺序反映出来的储顺序反映出来的储顺序反映出来的储顺序反映出来的a a1 1 1 1a a2 2 2 2a ai-1i-1i-1i-1a ai i i ia ai+1i+1i+1i+1a an n n n线性表线性表线性表线性表(a(a1 1,a,a2 2a a3,3,.a.an n)的顺序存储结构的顺序存储结构的顺序存储结构的顺序存储结构用顺序存储结构存储的线性表用顺序存储结构存储的线性表用顺序存储结构存储的线性表用顺序存储结构存储的线性表:称为顺序表称为顺序表称为顺序表称为顺序表2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构:顺序表顺序表顺序表顺序表1 1 1 1.线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构第8页/共103页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现说明：说明：说明：说明：在顺序存储结构下，线性表元素之间的逻辑关系，可通过在顺序存储结构下，线性表元素之间的逻辑关系，可通过在顺序存储结构下，线性表元素之间的逻辑关系，可通过在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素的元素的存储顺序反映（表示）出来，所以只需存储数据元素的元素的存储顺序反映（表示）出来，所以只需存储数据元素的元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息；信息；信息；信息；假没线性表中每个数据元素占用假没线性表中每个数据元素占用假没线性表中每个数据元素占用假没线性表中每个数据元素占用 kk个存储单元，那么，在个存储单元，那么，在个存储单元，那么，在个存储单元，那么，在顺序存储结构中，线性表的第顺序存储结构中，线性表的第顺序存储结构中，线性表的第顺序存储结构中，线性表的第i i个元素的存储位置与第个元素的存储位置与第个元素的存储位置与第个元素的存储位置与第1 1个元素个元素个元素个元素的存储位置的关系是：的存储位置的关系是：的存储位置的关系是：的存储位置的关系是：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i1)+(i1)k k这里这里这里这里 Loc(aLoc(ai i)是第是第是第是第 i i个元素的存储位置个元素的存储位置个元素的存储位置个元素的存储位置,Loc(aLoc(a1 1)是第是第是第是第1 1个元个元个元个元素的存储位置，也称为线性表的基址；素的存储位置，也称为线性表的基址；素的存储位置，也称为线性表的基址；素的存储位置，也称为线性表的基址；第9页/共103页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现怎样在计算机上实现怎样在计算机上实现怎样在计算机上实现怎样在计算机上实现线性表的顺序存储结构？线性表的顺序存储结构？线性表的顺序存储结构？线性表的顺序存储结构？2 2 2 2、顺序表的类型定义、顺序表的类型定义、顺序表的类型定义、顺序表的类型定义 以上用自然语言描述了线性表的顺序存储结构，怎样将这以上用自然语言描述了线性表的顺序存储结构，怎样将这以上用自然语言描述了线性表的顺序存储结构，怎样将这以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？为此，我们用种存储方式在计算机上实现？为此，我们用种存储方式在计算机上实现？为此，我们用种存储方式在计算机上实现？为此，我们用C C C C语言对这种存储语言对这种存储语言对这种存储语言对这种存储方式进行描述，我们知道方式进行描述，我们知道方式进行描述，我们知道方式进行描述，我们知道C C C C语言一维数组的机内表示也是顺序语言一维数组的机内表示也是顺序语言一维数组的机内表示也是顺序语言一维数组的机内表示也是顺序结构，因此，可借用结构，因此，可借用结构，因此，可借用结构，因此，可借用C C C C语言的一维数组实现线性表的顺序存储。语言的一维数组实现线性表的顺序存储。语言的一维数组实现线性表的顺序存储。语言的一维数组实现线性表的顺序存储。第10页/共103页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现顺序表的类型定义顺序表的类型定义#defineLIST_INIT_SIZE100/线性表存储空间的初始分配量线性表存储空间的初始分配量#defineLISTINCREMENT10/线性表存储空间的分配增量线性表存储空间的分配增量typedefstructElemType*elem;/线性表存储空间基址线性表存储空间基址intlength;/当前线性表长度当前线性表长度intlistsize;/当前分配的线性表存储空间大小当前分配的线性表存储空间大小(以以sizeof(ElemType)为为单位单位)SqList;SqList SqList：类型名，类型名，SqListSqList类型的变量是结构变量，它的三个域分别是：类型的变量是结构变量，它的三个域分别是：*elemelem：存放线性表元素的一维数组基址；存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配；其存储空间在初始化操作（建空表）时动态分配；lengthlength：存放线性表的表长；存放线性表的表长；listsizelistsize：用于存放当前分配（存放线性表元素）的存储空间的大用于存放当前分配（存放线性表元素）的存储空间的大小。小。第11页/共103页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现顺序表图示顺序表图示顺序表图示顺序表图示a a a a1 1 1 1a a a a2 2 2 2a a a ai-1i-1i-1i-1a a a ai i i ia a a ai+1i+1i+1i+1a a a an n n nL.lengthL.lengthL.lengthL.length L.listsizeL.listsizeL.listsizeL.listsizeL.elemL.elemL.elemL.elemn n n nLIST_INIT_SIZELIST_INIT_SIZELIST_INIT_SIZELIST_INIT_SIZE存放线性表元素存放线性表元素存放线性表元素存放线性表元素 的一维数组的一维数组的一维数组的一维数组设设 A=A=（a a1 1,a,a2 2,a,a3 3,.a,.an n ）是一线性表，是一线性表，L L是是SqList SqList 类型类型的结构变量，用于存放线性表的结构变量，用于存放线性表A A，则则L L在内存中的状态如图所示：在内存中的状态如图所示：第12页/共103页2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现二、顺序表的基本操作算法二、顺序表的基本操作算法二、顺序表的基本操作算法二、顺序表的基本操作算法回顾本书算法中常用到的两个回顾本书算法中常用到的两个回顾本书算法中常用到的两个回顾本书算法中常用到的两个C C函数。函数。函数。函数。1)1)Malloc(intsize)Malloc(intsize)功能：功能：功能：功能：系统内存分配系统内存分配系统内存分配系统内存分配sizesize个的存储单元，并返回该空间的基址。个的存储单元，并返回该空间的基址。个的存储单元，并返回该空间的基址。个的存储单元，并返回该空间的基址。使用方法：使用方法：使用方法：使用方法：.intm=100,intm=100,float*p;float*p;p=(float*)malloc(m*sizeof(float);p=(float*)malloc(m*sizeof(float);执行语句执行语句执行语句执行语句p=(float*)malloc(m*sizeof(float)p=(float*)malloc(m*sizeof(float)，计算机将按计算机将按计算机将按计算机将按floatfloat类型变量所占空间的大小类型变量所占空间的大小类型变量所占空间的大小类型变量所占空间的大小(一般为一般为一般为一般为3232bit)bit)分配分配分配分配m*sizeof(float)m*sizeof(float)个的存个的存个的存个的存储单元储单元储单元储单元,并将其基址赋值给指针变量并将其基址赋值给指针变量并将其基址赋值给指针变量并将其基址赋值给指针变量p;p;第13页/共103页 0 0 0 0 1 1 1 1 2 2 2 2 99999999p pp=(float*)malloc(m*sizeof(float)p=(float*)malloc(m*sizeof(float)图图图图示示示示2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现第14页/共103页 调用调用调用调用free(p)free(p)0 0 0 0 1 1 1 1 2 2 2 2 99999999p p 调用调用调用调用free(p)free(p)free(p)free(p)图示图示图示图示2)2)free(p)free(p)功能：将指针变量功能：将指针变量功能：将指针变量功能：将指针变量p p所指示的存储空间，回收到系统内存空间所指示的存储空间，回收到系统内存空间所指示的存储空间，回收到系统内存空间所指示的存储空间，回收到系统内存空间中去；中去；中去；中去；使用方法：使用方法：使用方法：使用方法：.intm=100;intm=100;float*p;float*p;p=(float*)malloc(m*sizeof(float);p=(float*)malloc(m*sizeof(float);/一旦一旦一旦一旦p p所指示的内存空间不再使用，所指示的内存空间不再使用，所指示的内存空间不再使用，所指示的内存空间不再使用，/调用调用调用调用free()free()回收之回收之回收之回收之 free(p);free(p);2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现第15页/共103页如何在顺序表如何在顺序表如何在顺序表如何在顺序表上实现线性表的基本操作？上实现线性表的基本操作？上实现线性表的基本操作？上实现线性表的基本操作？如何建空表？如何求表长？如何建空表？如何求表长？如何建空表？如何求表长？如何建空表？如何求表长？如何插入？删除？如何插入？删除？如何插入？删除？如何插入？删除？设线性表用设线性表用设线性表用设线性表用顺序表顺序表顺序表顺序表L L L L存储，下面我们介绍用顺序表存储线性存储，下面我们介绍用顺序表存储线性存储，下面我们介绍用顺序表存储线性存储，下面我们介绍用顺序表存储线性表时，各种基本操作的算法。当线性表用顺序表存储时，对线表时，各种基本操作的算法。当线性表用顺序表存储时，对线表时，各种基本操作的算法。当线性表用顺序表存储时，对线表时，各种基本操作的算法。当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存中的顺序表进行操性表各种基本操作实际上就是对存储在内存中的顺序表进行操性表各种基本操作实际上就是对存储在内存中的顺序表进行操性表各种基本操作实际上就是对存储在内存中的顺序表进行操作。作。作。作。2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现第16页/共103页1 1 1 1）初始化操作）初始化操作）初始化操作）初始化操作 InitList_Sq(SqList&L)InitList_Sq(SqList&L)InitList_Sq(SqList&L)InitList_Sq(SqList&L)参数参数参数参数：L L L L是存放线性表的结构变量（称是存放线性表的结构变量（称是存放线性表的结构变量（称是存放线性表的结构变量（称L L L L为顺序表）为顺序表）为顺序表）为顺序表）,因为插因为插因为插因为插入操作对顺序表入操作对顺序表入操作对顺序表入操作对顺序表L L L L进行了修改进行了修改进行了修改进行了修改,所以用了引用参数所以用了引用参数所以用了引用参数所以用了引用参数&L;L;L;L;功能：功能：功能：功能：建立空的顺序表建立空的顺序表建立空的顺序表建立空的顺序表L L L L主要步骤：主要步骤：主要步骤：主要步骤：调用调用调用调用malloc()malloc()malloc()malloc()为顺序表分配一预定大小为顺序表分配一预定大小为顺序表分配一预定大小为顺序表分配一预定大小(LIST_INIT_SIZELIST_INIT_SIZELIST_INIT_SIZELIST_INIT_SIZE）的空间的空间的空间的空间,并将其基址赋值给并将其基址赋值给并将其基址赋值给并将其基址赋值给L.elem;L.elem;L.elem;L.elem;初始化操作演示初始化操作演示初始化操作演示初始化操作演示2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现第17页/共103页 顺序表初始化顺序表初始化顺序表初始化顺序表初始化0 01 1LIST_INIT_SLIST_INIT_SLIST_INIT_SLIST_INIT_SIZE-1IZE-1IZE-1IZE-1L.lengthL.lengthL.listsizeL.listsizeL.elemL.elem00LIST_INIT_SIZELIST_INIT_SIZELIST_INIT_SIZELIST_INIT_SIZE再演示一次再演示一次再演示一次再演示一次2.2线性表的顺序存储和实现第18页/共103页初始化操作初始化操作初始化操作初始化操作算法：算法：算法：算法：StatusInitList_Sq(SqList&L)StatusInitList_Sq(SqList&L)/构造一个空的顺序表构造一个空的顺序表构造一个空的顺序表构造一个空的顺序表L LL.elem=(ElemType*)malloc(LIST_INIT_SIZEL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/if(!L.elem)exit(OVERFLOW);/存储分配失存储分配失存储分配失存储分配失败败败败L.length=0;/L.length=0;/空表长度为空表长度为空表长度为空表长度为0 0L.listsize=LIST_INIT_SIZE;/L.listsize=LIST_INIT_SIZE;/初始存储容量初始存储容量初始存储容量初始存储容量ReturnOK;ReturnOK;/InitList_Sq/InitList_Sq 算法算法算法算法2.32.32.32.32.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现第19页/共103页销毁操作图示销毁操作图示销毁操作图示销毁操作图示2 2 2 2 销毁操作销毁操作销毁操作销毁操作 DetroyList(SqList&L)DetroyList(SqList&L)DetroyList(SqList&L)DetroyList(SqList&L)功能：功能：功能：功能：回收为顺序表动态分配的存储空间回收为顺序表动态分配的存储空间回收为顺序表动态分配的存储空间回收为顺序表动态分配的存储空间主要步骤：主要步骤：主要步骤：主要步骤：调用调用调用调用free()free()free()free()回收为顺序表动态回收为顺序表动态回收为顺序表动态回收为顺序表动态分配的存储空间分配的存储空间分配的存储空间分配的存储空间2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现第20页/共103页 销毁顺序表销毁顺序表销毁顺序表销毁顺序表L.lengthL.lengthL.listsizeL.listsizeL.elemL.elem0 01 1LIST_INIT_SLIST_INIT_SLIST_INIT_SLIST_INIT_SIZE-1IZE-1IZE-1IZE-1a a1 1a a2