数据结构--线性表.pptx
《数据结构--线性表.pptx》由会员分享,可在线阅读,更多相关《数据结构--线性表.pptx(103页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二章第二章 线性表线性表在本课程介绍的几种数据结构中,在本课程介绍的几种数据结构中,线性表是最常简单的,也是最常用的线性表是最常简单的,也是最常用的数据结构,线性表在实际应用大量使数据结构,线性表在实际应用大量使用,并不是一个陌生的概念。用,并不是一个陌生的概念。第1页/共103页 基本内容基本内容基本内容基本内容 1 1 1 1 线性表的概念;线性表的概念;线性表的概念;线性表的概念;2 2 2 2 线性表两类存储结构和它们的类型定义;线性表两类存储结构和它们的类型定义;线性表两类存储结构和它们的类型定义;线性表两类存储结构和它们的类型定义;3 3 3 3 在这些存储结构下,线性表的基本操
2、作的算法;在这些存储结构下,线性表的基本操作的算法;在这些存储结构下,线性表的基本操作的算法;在这些存储结构下,线性表的基本操作的算法;学习要点:学习要点:学习要点:学习要点:1 1 1 1 了解线性表逻辑结构的特征了解线性表逻辑结构的特征了解线性表逻辑结构的特征了解线性表逻辑结构的特征;2 2 2 2 重点掌握线性表的顺序存储结构和链式存储结构,它重点掌握线性表的顺序存储结构和链式存储结构,它重点掌握线性表的顺序存储结构和链式存储结构,它重点掌握线性表的顺序存储结构和链式存储结构,它们如们如们如们如 何表达线性表中数据元素之间的结构关系;如何用何表达线性表中数据元素之间的结构关系;如何用何表
3、达线性表中数据元素之间的结构关系;如何用何表达线性表中数据元素之间的结构关系;如何用C C C C语语语语言言言言 描述它们的类型定义;描述它们的类型定义;描述它们的类型定义;描述它们的类型定义;3 3 3 3 掌握在顺序存储结构下,线性表的基本操作的算法;掌握在顺序存储结构下,线性表的基本操作的算法;掌握在顺序存储结构下,线性表的基本操作的算法;掌握在顺序存储结构下,线性表的基本操作的算法;4 4 4 4 掌握在链式存储结构下,线性表的基本操作的算法;掌握在链式存储结构下,线性表的基本操作的算法;掌握在链式存储结构下,线性表的基本操作的算法;掌握在链式存储结构下,线性表的基本操作的算法;5
4、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
5、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、某单位的电话号码簿。、某单位的电话号码簿。、某单位的电话号码簿。、某单位的电话号码簿。一、线性表的逻辑结一、线性表的逻辑
6、结构构电话号码簿是数据元素电话号码簿是数据元素电话号码簿是数据元素电话号码簿是数据元素的有限序列,每一数据的有限序列,每一数据的有限序列,每一数据的有限序列,每一数据元素包括两个数据项,元素包括两个数据项,元素包括两个数据项,元素包括两个数据项,一个是用户姓名,一个一个是用户姓名,一个一个是用户姓名,一个一个是用户姓名,一个是对应的电话号码。是对应的电话号码。是对应的电话号码。是对应的电话号码。姓名姓名姓名姓名 电话号码电话号码电话号码电话号码 蔡颖蔡颖蔡颖蔡颖 63214444 63214444 63214444 63214444 陈红陈红陈红陈红 63217777 63217777 632
7、17777 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
8、+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+1
9、i+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)在线性表中,除第一个元素和最后一个元素之外,其他元素)在线性表中,除第一个元素和最后一个元素之外,其他元素)在线性表中,除第一个元素和最后一个元素之外,其他元素)在线性表中,除第一个元素和最后一个元素之外,其他元素都有且仅有一个直接前趋,有且仅有一个直接后继,具有这种结都有且仅有一个直接前趋,有且仅有一个直接后继,具
10、有这种结都有且仅有一个直接前趋,有且仅有一个直接后继,具有这种结都有且仅有一个直接前趋,有且仅有一个直接后继,具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构;构特征的数据结构称为线性结构。线性表是一种线性数据结构;构特征的数据结构称为线性结构。线性表是一种线性数据结构;构特征的数据结构称为线性结构。线性表是一种线性数据结构;4 4 4 4)线性表中元素的个数)线性表中元素的个数)线性表中元素的个数)线性表中元素的个数n n n n称为线性表的长度,称为线性表的长度,称为线性表的长度,称为线性表的长度,n=0n=0n=0n=0时称为空表;时称为空表;时称为空表;时称为空表;5
11、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.a
12、i-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)功能:回收为线性表功能:
13、回收为线性表功能:回收为线性表功能:回收为线性表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)功能:判断线
14、性表功能:判断线性表功能:判断线性表功能:判断线性表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 取元素操作取元素操作取
15、元素操作取元素操作: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()功能:在线性表功能:在线性表功能:在线性表功能:在
16、线性表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)List
17、Insert(&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的第的第
18、的第的第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()vi
19、sit()visit()visit()失失失失 败,则返回败,则返回败,则返回败,则返回ERRORERRORERRORERROR,否则返回否则返回否则返回否则返回OKOKOKOK;说明说明说明说明1 1 1 1 上面列出的操作,只是线性表的一些常用的基本操作;上面列出的操作,只是线性表的一些常用的基本操作;上面列出的操作,只是线性表的一些常用的基本操作;上面列出的操作,只是线性表的一些常用的基本操作;2 2 2 2 不同的应用,基本操作可能是不同的;不同的应用,基本操作可能是不同的;不同的应用,基本操作可能是不同的;不同的应用,基本操作可能是不同的;例如:上面列出的删除操作例如:上面列出的删除
20、操作例如:上面列出的删除操作例如:上面列出的删除操作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返回其值。返回其值。返回其值。返回其值。在电话号码查询系统中,一旦某在电话号码查询系统中,一旦某在电话号码查询系统中,一旦某在电话号码查询系统中,一旦某用户撤掉某部电话,则需在系统的电话号码簿中删除该用户对应的数据,用户撤掉某部电话,则需在系
21、统的电话号码簿中删除该用户对应的数据,用户撤掉某部电话,则需在系统的电话号码簿中删除该用户对应的数据,用户撤掉某部电话,则需在系统的电话号码簿中删除该用户对应的数据,因此电话号码查询系统,需要提供这样的功能,在电话号码簿中删除与因此电话号码查询系统,需要提供这样的功能,在电话号码簿中删除与因此电话号码查询系统,需要提供这样的功能,在电话号码簿中删除与因此电话号码查询系统,需要提供这样的功能,在电话号码簿中删除与给定元素给定元素给定元素给定元素e e e e值相同的数据元素;值相同的数据元素;值相同的数据元素;值相同的数据元素;3 3 3 3 线性表的复杂操作可通过基本操作实现;线性表的复杂操作
22、可通过基本操作实现;线性表的复杂操作可通过基本操作实现;线性表的复杂操作可通过基本操作实现;这有点类似于数中的情形,例如整数的基本操作是这有点类似于数中的情形,例如整数的基本操作是这有点类似于数中的情形,例如整数的基本操作是这有点类似于数中的情形,例如整数的基本操作是+,-,+,-,+,-,+,-,/。如果要。如果要。如果要。如果要求某班同学的平均年龄则可利用求某班同学的平均年龄则可利用求某班同学的平均年龄则可利用求某班同学的平均年龄则可利用+/+/+/+/实现,全班同学的平均年龄实现,全班同学的平均年龄实现,全班同学的平均年龄实现,全班同学的平均年龄 =(=(=(=(age1+age2+ag
23、e3+age1+age2+age3+age1+age2+age3+age1+age2+age3+)/)/)/)/全班同学的全班同学的全班同学的全班同学的人数人数人数人数 例如,我们要在设计一个电话号码询系统,显然这个系统至少例如,我们要在设计一个电话号码询系统,显然这个系统至少例如,我们要在设计一个电话号码询系统,显然这个系统至少例如,我们要在设计一个电话号码询系统,显然这个系统至少要具备下列功能:要具备下列功能:要具备下列功能:要具备下列功能:查询某人的电话号码;查询某人的电话号码;查询某人的电话号码;查询某人的电话号码;在电话号码薄中,插入一新用户姓名及电话号码;在电话号码薄中,插入一新用
24、户姓名及电话号码;在电话号码薄中,插入一新用户姓名及电话号码;在电话号码薄中,插入一新用户姓名及电话号码;在电话号码薄中,删除已撤销的用户姓名及电话号码;在电话号码薄中,删除已撤销的用户姓名及电话号码;在电话号码薄中,删除已撤销的用户姓名及电话号码;在电话号码薄中,删除已撤销的用户姓名及电话号码;由上我们知道,电话号码薄可用线性表表示,上面列出的功由上我们知道,电话号码薄可用线性表表示,上面列出的功由上我们知道,电话号码薄可用线性表表示,上面列出的功由上我们知道,电话号码薄可用线性表表示,上面列出的功能实际上就是对线性表的查找、插入、删除操作,为了在计算能实际上就是对线性表的查找、插入、删除操
25、作,为了在计算能实际上就是对线性表的查找、插入、删除操作,为了在计算能实际上就是对线性表的查找、插入、删除操作,为了在计算机上实现上述功能,我们应该做什么呢?机上实现上述功能,我们应该做什么呢?机上实现上述功能,我们应该做什么呢?机上实现上述功能,我们应该做什么呢?显然,首先需要将电话号码薄上的信息存储到计算机中,然显然,首先需要将电话号码薄上的信息存储到计算机中,然显然,首先需要将电话号码薄上的信息存储到计算机中,然显然,首先需要将电话号码薄上的信息存储到计算机中,然后才可能对这些信息进行加工处理,实现上述功能。后才可能对这些信息进行加工处理,实现上述功能。后才可能对这些信息进行加工处理,实
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 线性
限制150内