数据结构线性表文档资料学习教案.pptx

《数据结构线性表文档资料学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构线性表文档资料学习教案.pptx（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(shjjiu)线性表文档资料线性表文档资料第一页，共103页。第二章第二章 线性表线性表 在本课程介绍的几种在本课程介绍的几种在本课程介绍的几种在本课程介绍的几种(jzhn)(jzhn)数据结构中，数据结构中，数据结构中，数据结构中，线性表是最常简单的，也是最常用的数据结构，线性表是最常简单的，也是最常用的数据结构，线性表是最常简单的，也是最常用的数据结构，线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使用，并不是一个陌生的线性表在实际应用大量使用，并不是一个陌生的线性表在实际应用大量使用，并不是一个陌生的线性表在实际应用大量使用，并不是一个陌生的概念

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

3、描述它们的类型定义；描述它们的类型定义；3 3 掌握在顺序存储结构下，线性表的基本操作的算法；掌握在顺序存储结构下，线性表的基本操作的算法；4 4 掌握在链式存储结构下，线性表的基本操作的算法；掌握在链式存储结构下，线性表的基本操作的算法；5 5 能够从时间复杂度的角度，比较线性表两类存储结构能够从时间复杂度的角度，比较线性表两类存储结构 的不同特点及适用场合；的不同特点及适用场合；第二章第二章第二章第二章 线性表线性表线性表线性表第2页/共103页第三页，共103页。线性表是线性表是线性表是线性表是n n n n 个类型相同个类型相同个类型相同个类型相同(xin tn)(xin tn)(xi

4、n tn)(xin tn)数据元素的有限序数据元素的有限序数据元素的有限序数据元素的有限序列，通常记作列，通常记作列，通常记作列，通常记作(a1,a2,a3,an)(a1,a2,a3,an)(a1,a2,a3,an)(a1,a2,a3,an)2.1 2.1 2.1 2.1 线性表的概念线性表的概念线性表的概念线性表的概念(ginin)(ginin)(ginin)(ginin)例例例例1 1 1 1、数学中的数列、数学中的数列、数学中的数列、数学中的数列(shli)(shli)(shli)(shli)（11111111，13131313，15151515，17171717，19191919，21

5、212121）例例例例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、某单位的电话号码簿。、某单位的电话号码簿。、某单位的电话号码簿。、某单位的电话号码簿。一、线性表的逻辑结构一、线性表的逻辑结构电话号码簿是数据元素电话号码簿是数据元素电话号码簿是数据元素电话号码簿是数据元素的有限序列，每一数据的有限序列，每一数据的有限序列，每一数据的有限序列，每一数据元素包括两个数据项，元素包括两个数据项，元素包括两个数据项，元素包括两个数据项，一个是用户姓名

6、，一个一个是用户姓名，一个一个是用户姓名，一个一个是用户姓名，一个是对应的电话号码。是对应的电话号码。是对应的电话号码。是对应的电话号码。姓名姓名姓名姓名 电话号码电话号码电话号码电话号码 蔡颖蔡颖蔡颖蔡颖 63214444 63214444 63214444 63214444 陈红陈红陈红陈红 63217777 63217777 63217777 63217777 刘建平刘建平刘建平刘建平 63216666 63216666 63216666 63216666 王小林王小林王小林王小林 63218888 63218888 63218888 63218888 张力张力张力张力 63215555

7、 63215555 63215555 63215555.第3页/共103页第四页，共103页。2.1 2.1 2.1 2.1 线性表的概念线性表的概念线性表的概念线性表的概念(ginin)(ginin)(ginin)(ginin)说明：设说明：设说明：设说明：设 A=(a1,a2,.,ai-1,ai,ai+1,an)A=(a1,a2,.,ai-1,ai,ai+1,an)A=(a1,a2,.,ai-1,ai,ai+1,an)A=(a1,a2,.,ai-1,ai,ai+1,an)是一线性表是一线性表是一线性表是一线性表1 1 1 1）线性表的数据元素可以是各种各样的，但同一线性表中）线性表的数据元

8、素可以是各种各样的，但同一线性表中）线性表的数据元素可以是各种各样的，但同一线性表中）线性表的数据元素可以是各种各样的，但同一线性表中的元素须是同一类型的；的元素须是同一类型的；的元素须是同一类型的；的元素须是同一类型的；2 2 2 2）在表中）在表中）在表中）在表中ai-1ai-1ai-1ai-1领先领先领先领先(ln xin)(ln xin)(ln xin)(ln xin)于于于于aiaiaiai，aiaiaiai领先领先领先领先(ln xin)(ln xin)(ln xin)(ln xin)于于于于ai+1ai+1ai+1ai+1，称，称，称，称ai-1ai-1ai-1ai-1是是是是a

9、iaiaiai的直接前趋，的直接前趋，的直接前趋，的直接前趋，ai+1ai+1ai+1ai+1是是是是aiaiaiai的直接后继；的直接后继；的直接后继；的直接后继；3 3 3 3）在线性表中，除第一个元素和最后一个元素之外，其他）在线性表中，除第一个元素和最后一个元素之外，其他）在线性表中，除第一个元素和最后一个元素之外，其他）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具元素都有且仅有一个直接前趋，有且仅有一个直接后继，具元素都有且仅有一个直接前趋，有且仅有一个直接后继，具元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结有这

10、种结有这种结有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构特征的数据结构称为线性结构。线性表是一种线性数据结构特征的数据结构称为线性结构。线性表是一种线性数据结构特征的数据结构称为线性结构。线性表是一种线性数据结构；构；构；构；4 4 4 4）线性表中元素的个数）线性表中元素的个数）线性表中元素的个数）线性表中元素的个数n n n n称为线性表的长度，称为线性表的长度，称为线性表的长度，称为线性表的长度，n=0n=0n=0n=0时称为空时称为空时称为空时称为空表；表；表；表；5 5 5 5）aiaiaiai是线性表的第是线性表的第是线性表的第是线性表的第i i i i个元素，称

11、个元素，称个元素，称个元素，称i i i i为数据元素为数据元素为数据元素为数据元素aiaiaiai的序号，每的序号，每的序号，每的序号，每一个元素在线性表中的位置，仅取决于它的序号；一个元素在线性表中的位置，仅取决于它的序号；一个元素在线性表中的位置，仅取决于它的序号；一个元素在线性表中的位置，仅取决于它的序号；第4页/共103页第五页，共103页。2.1 2.1 2.1 2.1 线性表的概念线性表的概念线性表的概念线性表的概念(ginin)(ginin)(ginin)(ginin)设设设设L=L=L=L=（a1,a2,.ai-1,ai,ai+1,ana1,a2,.ai-1,ai,ai+1,

12、ana1,a2,.ai-1,ai,ai+1,ana1,a2,.ai-1,ai,ai+1,an）是一线性表）是一线性表）是一线性表）是一线性表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)功能：回收为线性表功能：回收为线性表功能：回收为线

13、性表功能：回收为线性表L L L L动态分配的存储空间；动态分配的存储空间；动态分配的存储空间；动态分配的存储空间；3 3 3 3 置空操作置空操作置空操作置空操作ClearList(&L)ClearList(&L)ClearList(&L)ClearList(&L)功能：功能：功能：功能：L L L L中已存在，重新中已存在，重新中已存在，重新中已存在，重新(chngxn)(chngxn)(chngxn)(chngxn)将其置成空表；将其置成空表；将其置成空表；将其置成空表；4 4 4 4 判空操作判空操作判空操作判空操作ListEmpty(L)ListEmpty(L)ListEmpty(L

14、)ListEmpty(L)功能：判断线性表功能：判断线性表功能：判断线性表功能：判断线性表L L L L是否为空表，若为空表返回是否为空表，若为空表返回是否为空表，若为空表返回是否为空表，若为空表返回TRUETRUETRUETRUE，否则返回，否则返回，否则返回，否则返回FALSEFALSEFALSEFALSE；5 5 5 5 求表长操作求表长操作求表长操作求表长操作 ListLength(L)ListLength(L)ListLength(L)ListLength(L)功能：返回线性表功能：返回线性表功能：返回线性表功能：返回线性表L L L L的表长；的表长；的表长；的表长；二、线性表的基

15、本操作二、线性表的基本操作6 6 6 6 取元素取元素取元素取元素(yun s)(yun s)(yun s)(yun s)操作：操作：操作：操作：GetElem(L,i,&e)GetElem(L,i,&e)GetElem(L,i,&e)GetElem(L,i,&e)功能：将线性表功能：将线性表功能：将线性表功能：将线性表L L L L中第中第中第中第i i i i 个元素个元素个元素个元素(yun s)(yun s)(yun s)(yun s)赋值给赋值给赋值给赋值给 e e e e；7 7 7 7 查找操作查找操作查找操作查找操作 LocateElem(L,e,compare()Locate

16、Elem(L,e,compare()LocateElem(L,e,compare()LocateElem(L,e,compare()功能：在线性表功能：在线性表功能：在线性表功能：在线性表L L L L中查找与元素中查找与元素中查找与元素中查找与元素(yun s)e(yun s)e(yun s)e(yun s)e满足满足满足满足compare()compare()compare()compare()的第的第的第的第1 1 1 1个元素个元素个元素个元素(yun s)(yun s)(yun s)(yun s)，返回该，返回该，返回该，返回该 元素元素元素元素(yun s)(yun s)(yun

17、s)(yun s)在表中的序号（或位置），若表中不存在这样的元素在表中的序号（或位置），若表中不存在这样的元素在表中的序号（或位置），若表中不存在这样的元素在表中的序号（或位置），若表中不存在这样的元素(yun s)(yun s)(yun s)(yun s)，则返回，则返回，则返回，则返回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

18、个元素个元素个元素个元素(yun s)(yun s)(yun s)(yun s)之前插入一个新元素之前插入一个新元素之前插入一个新元素之前插入一个新元素(yun(yun(yun(yun s)e;s)e;s)e;s)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个元素个元素个元素个元素(yun s)(yun s)(yun s)(yu

19、n s)，并用，并用，并用，并用e e e e返回；返回；返回；返回；10 10 10 10 遍历操作遍历操作遍历操作遍历操作 ListTraverse(&L,visit()ListTraverse(&L,visit()ListTraverse(&L,visit()ListTraverse(&L,visit()功能：依次对线性表功能：依次对线性表功能：依次对线性表功能：依次对线性表L L L L的每一个元素的每一个元素的每一个元素的每一个元素(yun s)(yun s)(yun s)(yun s)调用函数调用函数调用函数调用函数visit()visit()visit()visit()。若。若。

20、若。若visitvisitvisitvisit()()()()失失失失 败，则返回败，则返回败，则返回败，则返回ERRORERRORERRORERROR，否则返回，否则返回，否则返回，否则返回OKOKOKOK；说明说明说明说明1 1 1 1 上面列出的操作，只是线性表的一些常用的基本操作；上面列出的操作，只是线性表的一些常用的基本操作；上面列出的操作，只是线性表的一些常用的基本操作；上面列出的操作，只是线性表的一些常用的基本操作；2 2 2 2 不同的应用，基本操作可能是不同的；不同的应用，基本操作可能是不同的；不同的应用，基本操作可能是不同的；不同的应用，基本操作可能是不同的；例如：上面列出

21、的删除操作例如：上面列出的删除操作例如：上面列出的删除操作例如：上面列出的删除操作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返回其值。返回其值。返回其值。返回其值。在电话号码查询系统中，一旦某用户撤掉某部电在电话号码查询系统中，一旦某用户撤掉某部电在电话号码查询系统中，一旦某用户撤掉某部电在电话号码查询系统中，一旦某用户撤掉某部电话，

22、则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与给定元素需要提供这样的功能，在电话号码簿中删除与给定元素需要提供这样的功能，在电话号码簿中删除与给定元素需要提供这样的功能，在电话号码簿中删除与给定元素e e e e值相同的数据元素；值相同的数据元素；值相同的数据元素；值相同的数据元素；3 3 3 3 线性表的复杂操作可通过

23、基本操作实现；线性表的复杂操作可通过基本操作实现；线性表的复杂操作可通过基本操作实现；线性表的复杂操作可通过基本操作实现；这有点类似于数中的情形，例如整数的基本操作是这有点类似于数中的情形，例如整数的基本操作是这有点类似于数中的情形，例如整数的基本操作是这有点类似于数中的情形，例如整数的基本操作是+,-,+,-,+,-,+,-,/。如果要求某班。如果要求某班。如果要求某班。如果要求某班同学的平均年龄则可利用同学的平均年龄则可利用同学的平均年龄则可利用同学的平均年龄则可利用+/+/+/+/实现，全班同学的平均年龄实现，全班同学的平均年龄实现，全班同学的平均年龄实现，全班同学的平均年龄 =(=(=

24、(=(age1+age2+age3+age1+age2+age3+age1+age2+age3+age1+age2+age3+)/)/)/)/全班同学的人全班同学的人全班同学的人全班同学的人数数数数 例如，我们要在设计一个电话号码询系统，显然这个系统至少要具备例如，我们要在设计一个电话号码询系统，显然这个系统至少要具备例如，我们要在设计一个电话号码询系统，显然这个系统至少要具备例如，我们要在设计一个电话号码询系统，显然这个系统至少要具备下列功能：下列功能：下列功能：下列功能：查询某人的电话号码；查询某人的电话号码；查询某人的电话号码；查询某人的电话号码；在电话号码薄中，插入一新用户姓名及电话号

25、码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，插入一新用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；在电话号码薄中，删除已撤销的用户姓名及电话号码；由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就是对线性表的查找、插入、

26、删除操作，为了在计算机上实现上述功能，我是对线性表的查找、插入、删除操作，为了在计算机上实现上述功能，我是对线性表的查找、插入、删除操作，为了在计算机上实现上述功能，我是对线性表的查找、插入、删除操作，为了在计算机上实现上述功能，我们应该做什么呢？们应该做什么呢？们应该做什么呢？们应该做什么呢？显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对这些信息进行加工处理，实现上述功能。这些信息进行加工处理

27、，实现上述功能。这些信息进行加工处理，实现上述功能。这些信息进行加工处理，实现上述功能。第5页/共103页第六页，共103页。2.2 2.2 线性表的顺序存储和实线性表的顺序存储和实现现 一、线性表的顺序存储结构一、线性表的顺序存储结构顺序表顺序表 1.1.线性表的顺序存储结构线性表的顺序存储结构 2.2.顺序表的类型定义顺序表的类型定义二、顺序表的基本操作算法二、顺序表的基本操作算法三、利用三、利用(lyng)(lyng)基本操作实基本操作实现线性表的其他操作现线性表的其他操作第6页/共103页第七页，共103页。为了存储线性表，至少要保存两类信息为了存储线性表，至少要保存两类信息为了存储线

28、性表，至少要保存两类信息为了存储线性表，至少要保存两类信息(xnx)(xnx)(xnx)(xnx)：1 1 1 1）线性表中的数据元素；）线性表中的数据元素；）线性表中的数据元素；）线性表中的数据元素；2 2 2 2）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系；2.2 2.2 线性表的顺序存线性表的顺序存储和实现储和实现(shxin)(shxin)在计算机内部可以采用不同的方式来存储一个在计算机内部可以采用不同的方式来存储一个在计算机内部可以采用不同的方式来存储一个在计算机内部可以采用不同的方式来存储一个(y(y)线性表

29、，其中最简单的方式就是本节要讲的线性表线性表，其中最简单的方式就是本节要讲的线性表线性表，其中最简单的方式就是本节要讲的线性表线性表，其中最简单的方式就是本节要讲的线性表的顺序存储结构。的顺序存储结构。的顺序存储结构。的顺序存储结构。第7页/共103页第八页，共103页。线性表的顺序存储结构，就是用一组连续线性表的顺序存储结构，就是用一组连续线性表的顺序存储结构，就是用一组连续线性表的顺序存储结构，就是用一组连续的内存单元依次的内存单元依次的内存单元依次的内存单元依次(yc)(yc)存放线性表的数据存放线性表的数据存放线性表的数据存放线性表的数据元素。元素。元素。元素。用顺序表存储线性表时，数

30、据元素之间的逻用顺序表存储线性表时，数据元素之间的逻用顺序表存储线性表时，数据元素之间的逻用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存储顺序反映辑关系，是通过数据元素的存储顺序反映辑关系，是通过数据元素的存储顺序反映辑关系，是通过数据元素的存储顺序反映(fnyng)(fnyng)出来的出来的出来的出来的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 n线性表线性表线性表线性表(a1,a2a3,.an)(a1,a2a3,.an)的顺序存储结

31、构的顺序存储结构的顺序存储结构的顺序存储结构(jigu)(jigu)用顺序存储结构存储的线性表用顺序存储结构存储的线性表用顺序存储结构存储的线性表用顺序存储结构存储的线性表:称为顺序表称为顺序表称为顺序表称为顺序表2.2 2.2 线性表的顺序存储和线性表的顺序存储和实现实现一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构:顺序表顺序表顺序表顺序表1 1 1 1.线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构第8页/共103页第九页，共103页。2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现(shxi

32、n)(shxin)说明：说明：说明：说明：在顺序存储结构下，线性表元素之间的逻辑关系，可通过在顺序存储结构下，线性表元素之间的逻辑关系，可通过在顺序存储结构下，线性表元素之间的逻辑关系，可通过在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素元素的存储顺序反映（表示）出来，所以只需存储数据元素元素的存储顺序反映（表示）出来，所以只需存储数据元素元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息；的信息；的信息；的信息；假没线性表中每个数据元素占用假没线性表中每个数据元素占用假没线性表中每个数据元素占用假没线性表中每个数据元素占用kk个

33、存储单元个存储单元个存储单元个存储单元(cnch(cnchdnyun)dnyun)，那么，在顺序存储结构中，线性表的第，那么，在顺序存储结构中，线性表的第，那么，在顺序存储结构中，线性表的第，那么，在顺序存储结构中，线性表的第i i个元素的个元素的个元素的个元素的存储位置与第存储位置与第存储位置与第存储位置与第1 1个元素的存储位置的关系是：个元素的存储位置的关系是：个元素的存储位置的关系是：个元素的存储位置的关系是：Loc(ai)=Loc(a1)+Loc(ai)=Loc(a1)+(i1)(i1)k k这里这里这里这里Loc(ai)Loc(ai)是第是第是第是第ii个元素的存储位置个元素的存储

34、位置个元素的存储位置个元素的存储位置,Loc(a1),Loc(a1)是第是第是第是第1 1个个个个元素的存储位置，也称为线性表的基址；元素的存储位置，也称为线性表的基址；元素的存储位置，也称为线性表的基址；元素的存储位置，也称为线性表的基址；第9页/共103页第十页，共103页。2.2 2.2 线性表的顺序存储线性表的顺序存储和实现和实现(shxin)(shxin)怎样在计算机上实现怎样在计算机上实现怎样在计算机上实现怎样在计算机上实现线性表的顺序存储结构？线性表的顺序存储结构？线性表的顺序存储结构？线性表的顺序存储结构？2 2 2 2、顺序表的类型定义、顺序表的类型定义、顺序表的类型定义、顺

35、序表的类型定义 以上用自然语言描述了线性表的顺序存储结构，怎样将这种以上用自然语言描述了线性表的顺序存储结构，怎样将这种以上用自然语言描述了线性表的顺序存储结构，怎样将这种以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？为此，我们用存储方式在计算机上实现？为此，我们用存储方式在计算机上实现？为此，我们用存储方式在计算机上实现？为此，我们用C C C C语言对这种存储方式语言对这种存储方式语言对这种存储方式语言对这种存储方式进行进行进行进行(jnxng)(jnxng)(jnxng)(jnxng)描述，我们知道描述，我们知道描述，我们知道描述，我们知道C C C C语言

36、一维数组的机内表示也是顺语言一维数组的机内表示也是顺语言一维数组的机内表示也是顺语言一维数组的机内表示也是顺序结构，因此，可借用序结构，因此，可借用序结构，因此，可借用序结构，因此，可借用C C C C语言的一维数组实现线性表的顺序存储。语言的一维数组实现线性表的顺序存储。语言的一维数组实现线性表的顺序存储。语言的一维数组实现线性表的顺序存储。第10页/共103页第十一页，共103页。2.2 2.2 线性表的顺序存储和实现线性表的顺序存储和实现(shxin)(shxin)顺序表的类型定义顺序表的类型定义#defineLIST_INIT_SIZE100/线性表存储空间的初始分配量线性表存储空间的

37、初始分配量#defineLISTINCREMENT10/线性表存储空间的分配增量线性表存储空间的分配增量typedefstructElemType*elem;/线性表存储空间基址线性表存储空间基址intlength;/当前线性表长度当前线性表长度(chngd)intlistsize;/当前分配的线性表存储空间大小当前分配的线性表存储空间大小(以以sizeof(ElemType)为为单位单位)SqList;SqList SqList：类型名，：类型名，SqListSqList类型的变量是结构变量，它的三个域分别是：类型的变量是结构变量，它的三个域分别是：*elem *elem：存放线性表元素的一

38、维数组基址；存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配其存储空间在初始化操作（建空表）时动态分配(fnpi)(fnpi)；length length：存放线性表的表长；存放线性表的表长；listsize listsize：用于存放当前分配：用于存放当前分配(fnpi)(fnpi)（存放线性表元素）的存储（存放线性表元素）的存储空间的大小。空间的大小。第11页/共103页第十二页，共103页。2.2 2.2 线性表的顺序存储线性表的顺序存储和实现和实现(shxin)(shxin)顺序顺序顺序顺序(shnx)(shnx)(shnx)(shnx)表表表表图示图示图示图示

39、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存放存放存放存放(cnfng)(cnfng)(cnfng)(cnfng)线性表元素线性表元素

40、线性表元素线性表元素 的一维数组的一维数组的一维数组的一维数组设设 A=A=（a a1 1,a,a2 2,a,a3 3,.a,.an n ）是一线性表，是一线性表，L L是是SqList SqList 类型的结构类型的结构变量，用于存放线性表变量，用于存放线性表A A，则则L L在内存中的状态如图所示：在内存中的状态如图所示：第12页/共103页第十三页，共103页。2.2 2.2 线性表的顺序存线性表的顺序存储和实现储和实现(shxin)(shxin)二、顺序表的基本操作算法二、顺序表的基本操作算法二、顺序表的基本操作算法二、顺序表的基本操作算法回顾本书算法中常用到的两个回顾本书算法中常用到

41、的两个回顾本书算法中常用到的两个回顾本书算法中常用到的两个C C函数。函数。函数。函数。1)Malloc(intsize)1)Malloc(intsize)功能：系统内存分配功能：系统内存分配功能：系统内存分配功能：系统内存分配sizesize个的存储单元，并返回该空间的基址。个的存储单元，并返回该空间的基址。个的存储单元，并返回该空间的基址。个的存储单元，并返回该空间的基址。使用使用使用使用(shyng)(shyng)方法：方法：方法：方法：.intm=100,intm=100,float*p;float*p;p=(float*)malloc(m*sizeof(float);p=(float

42、*)malloc(m*sizeof(float);执行语句执行语句执行语句执行语句p=(float*)malloc(m*sizeof(float)p=(float*)malloc(m*sizeof(float)，计算机将按，计算机将按，计算机将按，计算机将按floatfloat类型变量所占空间的大小类型变量所占空间的大小类型变量所占空间的大小类型变量所占空间的大小(一般为一般为一般为一般为32bit)32bit)分配分配分配分配m*sizeof(float)m*sizeof(float)个的个的个的个的存储单元存储单元存储单元存储单元,并将其基址赋值给指针变量并将其基址赋值给指针变量并将其基址

43、赋值给指针变量并将其基址赋值给指针变量p;p;第13页/共103页第十四页，共103页。0 0 0 0 1 1 1 1 2 2 2 2 99999999p p p pp=(float*)malloc(m*sizeof(float)p=(float*)malloc(m*sizeof(float)图图图图示示示示2.2 2.2 线性表的顺序存储线性表的顺序存储和实现和实现(shxin)(shxin)第14页/共103页第十五页，共103页。调用调用调用调用(dioyng)fr(dioyng)free(p)ee(p)0 0 0 0 1 1 1 1 2 2 2 2 99999999p p p p 调用

44、调用调用调用(dioyng)free(p)(dioyng)free(p)图图图图示示示示2)free(p)2)free(p)功能：将指针功能：将指针功能：将指针功能：将指针(zhzhn)(zhzhn)变量变量变量变量p p所指示的存储空间，回所指示的存储空间，回所指示的存储空间，回所指示的存储空间，回收到系统内存空间中去；收到系统内存空间中去；收到系统内存空间中去；收到系统内存空间中去；使用方法：使用方法：使用方法：使用方法：.intm=100;intm=100;float*p;float*p;p=(float*)malloc(m*sizeof(float);p=(float*)malloc(

45、m*sizeof(float);/一旦一旦一旦一旦p p所指示的内存空间不再使用，所指示的内存空间不再使用，所指示的内存空间不再使用，所指示的内存空间不再使用，/调用调用调用调用free()free()回收之回收之回收之回收之 free(p);free(p);2.2 2.2 线性表的顺序存储线性表的顺序存储和实现和实现第15页/共103页第十六页，共103页。如何如何如何如何(rh)(rh)在顺序表在顺序表在顺序表在顺序表上实现线性表的基本操作？上实现线性表的基本操作？上实现线性表的基本操作？上实现线性表的基本操作？如何如何如何如何(rh)(rh)建空表？如何建空表？如何建空表？如何建空表？如

46、何(rh)(rh)求表长？求表长？求表长？求表长？如何如何如何如何(rh)(rh)插入？删除？插入？删除？插入？删除？插入？删除？设线性表用顺序表设线性表用顺序表L L存储，下面我们介绍用顺序表存储线性表时，各种基本操作的算法。存储，下面我们介绍用顺序表存储线性表时，各种基本操作的算法。当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存(nicn)(nicn)中的顺序中的顺序表进行操作。表进行操作。2.2 2.2 线性表的顺序存储线性表的顺序存储和实现和实现(shxin)(shxin)第16页/共103页第十七页

47、，共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是存放是存放是存放是存放(cnfng)(cnfng)(cnfng)(cnfng)线性表的结构变量（称线性表的结构变量（称线性表的结构变量（称线性表的结构变量（称L L L L为顺序表）为顺序表）为顺序表）为顺序表）,因为因为因为因为插入操作对顺序表插入操作对顺序表插入操作对顺序表插入操作对顺序表L L L L进行了

48、修改进行了修改进行了修改进行了修改,所以用了引用参数所以用了引用参数所以用了引用参数所以用了引用参数&L;&L;&L;&L;功能：建立空的顺序表功能：建立空的顺序表功能：建立空的顺序表功能：建立空的顺序表L L L L主要步骤：调用主要步骤：调用主要步骤：调用主要步骤：调用malloc()malloc()malloc()malloc()为顺序表分配一预定大小为顺序表分配一预定大小为顺序表分配一预定大小为顺序表分配一预定大小(LIST_INIT_SIZE(LIST_INIT_SIZE(LIST_INIT_SIZE(LIST_INIT_SIZE）的空间）的空间）的空间）的空间,并将其基址赋值给并将

49、其基址赋值给并将其基址赋值给并将其基址赋值给L.elem;L.elem;L.elem;L.elem;初始化操作初始化操作初始化操作初始化操作(cozu)(cozu)演示演示演示演示2.2 2.2 线性表的顺序存储线性表的顺序存储和实现和实现(shxin)(shxin)第17页/共103页第十八页，共103页。顺序顺序顺序顺序(shnx)(shnx)表初始表初始表初始表初始化化化化0 01 1LIST_INIT_SLIST_INIT_SLIST_INIT_SLIST_INIT_SIZE-1IZE-1IZE-1IZE-1L.lengthL.lengthL.listsizeL.listsizeL.e

50、lemL.elem00LIST_INIT_SIZELIST_INIT_SIZELIST_INIT_SIZELIST_INIT_SIZE再演示再演示再演示再演示(ynsh)(ynsh)一次一次一次一次2.2线性表的顺序存储和实现(shxin)第18页/共103页第十九页，共103页。初始化操作算法：初始化操作算法：初始化操作算法：初始化操作算法：StatusInitList_Sq(SqList&L)StatusInitList_Sq(SqList&L)/构造一个空的顺序表构造一个空的顺序表构造一个空的顺序表构造一个空的顺序表L LL.elem=(ElemType*)malloc(LIST_INI