中小学教育资源及组卷应用平台
第二单元
初识数据结构
项目三
探索商品基本信息表的实现
——线性表的应用
第一课时
问题分析
?教材分析
本节的主要内容是问题分析。从问题分析开始，分析商品信息表每一个数据元素之间的逻辑关系，确定数据元素之间存在着一对一的关系，逻辑结构也是线性表。在此过程中培养学生的计算思维能力，学生的数字化学习和创新能力。
?教学目标
1.理解线性的概念和特点；
2.理解线性表顺序存储和链式存储时，数据的插入和删除过程。
?教学重点
1.线性表抽象数据类型的定义。
?教学难点
1.线性的概念和特点。
?教学方法
体验法、讲授法、讨论法、示例法
?教学准备
计算机教室、多媒体设备、多媒体广播软件、教学课件、安装Python编程的相关软件，学生上机练习的程序文件，学生工作单等。
?教学过程
一、新课导入
提出问题：超市销售品种繁多的商品，需要及时添加、修改商品信息，商家需要存储商品的哪些信息？
商品信息表（简化）
序号
商品条形码编码
品名
库存数（件）
零售价（元）
1
6956416200029
1.25L果粒橙
80
8
2
6956416200265
450mL果粒芒果
80
3.5
3
6921311196364
1L冰红茶
80
4
4
6921311196494
1L绿茶
80
4
5
6924862101467
2L百事可乐
100
6.5
6
6900451893036
2L芬达
100
6.5
7
6900451891032
2L可口可乐
100
6.5
二、问题分析
为了实现使用计算机对超市商品进行管理，需要按照商品的不同分类，建立“商品信息表”，然后通过条码扫描器读取商品条码，录人每一种商品的具体数据。
上面的商品信息表中，每一个数据元素有相同的数据项。若将表中的每一个数据元素表示为商品i
（i为原表中的商品序号），可以得到按原序号顺序排列的序列，如图2-8所示。
图2-8顺序排列的数据元素
从表中可以看到，各个数据元素(商品)之间存在着对一的关系，自上而下顺序排列。此表也是线性表。
思考与讨论
1.在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表：A,B,C,D,…Z就是一个线性表。想一想，生活中还有哪些这样的例子？
2.上一个项目中给出的抽象数据类型是否适用于商品信息表？为什么？
参考：
1.例如，一年中的月份：1月~12月；星期：星期一~星期天等。
2.适用，在商品信息表中，对商品信息进行抽象后得到的数据是商品的集合，数据元素之间也是一对一的线性关系，在此数学模型的基础上定义的插入和删除操作，在以后需要插入删除时，直接调用即可。
小贴士
为了便于理解，此处“商品信息表”设定为只包含序号、条形码、品名、库存数、零售价等信息。
线性表的特点是存在唯的一个被称作“第一个”的数据元素；存在唯一的个被称作“最后一个”的数据元素；除第一个外，结构中每个数据元素只有一个前驱；除最后一个外，结构中每个数据元素只有一个后继。
三、线性表
1.线性表概念
线性表是最基本、最简单、也是最常用的一种数据结构。
线性表（linear
list）是数据结构
(?https:?/??/?baike.?/?item?/?%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84?/?1450"
\t
"https:?/??/?baike.?/?item?/?%E7%BA%BF%E6%80%A7%E8%A1%A8?/?_blank?)的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录
(?https:?/??/?baike.?/?item?/?%E8%AE%B0%E5%BD%95?/?14312145"
\t
"https:?/??/?baike.?/?item?/?%E7%BA%BF%E6%80%A7%E8%A1%A8?/?_blank?)（record），含有大量记录的线性表又称文件
(?https:?/??/?baike.?/?item?/?%E6%96%87%E4%BB%B6?/?6270998"
\t
"https:?/??/?baike.?/?item?/?%E7%BA%BF%E6%80%A7%E8%A1%A8?/?_blank?)（file）。
线性表是n(n≥0)个数据特性相同的元素构成的有限序列。记为(a1,a2,…,ai-1,ai,ai+1,…,an)，其中ai-1是ai的直接前驱元素，ai+1是ai直接后继元素，ai无前驱元素，an无后继元素。n称为线性表的长度，当n=0时，称为空表。
2.线性表特征
①集合中必存在唯一的一个“第一元素”。
②集合中必存在唯一的一个
“最后元素”
。
③除最后一个元素之外，均有唯一的后继(后件)。
④除第一个元素之外，均有唯一的前驱(前件)。
3.基本操作
①MakeEmpty(L)
这是一个将L变为空表的方法
②Length（L）
返回表L的长度，即表中元素个数
③Get（L，i）
这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
④Prior（L，i）
取i的前驱元素
⑤Next（L，i）
取i的后继元素
⑥Locate（L，x）
这是一个函数，函数值为元素x在L中的位置
⑦Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
⑧Delete（L，p）
从表L中删除位置p处的元素
⑨IsEmpty(L)
如果表L为空表(长度为0)则返回true，否则返回false
⑩Clear（L）清除所有元素
?Init（L）同第一个，初始化线性表为空
?Traverse（L）遍历输出所有元素
?Find（L，x）查找并返回元素
?Update（L，x）修改元素
?Sort（L）对所有元素重新按给定的条件排序
?strstr(string1,string2)用于字符数组的求string1中出现string2的首地址
例如，商品信息表=(商品1,商品2,商品3,商品4,商品5,商品6…)
线性表的抽象数据类型表示如下:
四、课后活动
1.请尝试写出线性表抽象数据类型的定义。
2.请分析以下生活中的案例，判断哪个是线性表。
①公司的组织结构表：总经理管理数名总监，每个总监管理数名经理，每个经理都有各自的下属和员工。
②学生信息表，如表2-5所示。
学生信息表
学号
姓名
性别
出生年月
家庭地址
1
张一帆
男
2001.03
东街西巷1号203室
2
李小红
女
2001.8
南大北路4弄5号6室
……
……
……
……
……
3.下面哪些事物的相关信息适合用线性表存储和管理，为什么？
①在银行排队等候服务的顾客；
②书架上的一排书籍；
③计算机桌面上的各种图标及其相关信息；
④计算机的文件和文件夹；
⑤个人的电话簿；
⑥一辆汽车的所有部件和零件。
ADT
List
数据对象：D={ai
lai∈
ElemSet,i=1,2,n,n>=0}
数据关系：R={
l
ai-1,ai∈D,i=2,…,n}
基本操作:
def
InitList(self)
#建立一个空的线性表
def
GetElem(self,i)
#返回线性表的第i个元素
def
Length(self)
#求线性表的长度
def
LocateElen(self,x)
#求元素x在线性表中的位置；若不存在x,则返回0
def
Insert(self,i,x)
#在线性表的第i个位置上插入一个新元素x
def
Delete(self,i)
#删除线性表的第i个元素
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://21世纪教育网(www.21cnjy.com)
"
21世纪教育网(www.21cnjy.com)(共27张PPT)
第一课时
问题分析
信息技术沪教版
选择性必修1
第二单元
初识数据结构
项目三
探索商品基本信息表的实现
——线性表的应用
一、新课导入
二、问题分析
四、课后活动
三、线性表
一、新课导入
超市销售品种繁多的商品，需要及时添加、修改商品信息，商家需要存储商品的哪些信息？
商品信息表（简化）
序号
商品条形码编码
品名
库存数（件）
零售价（元）
1
6956416200029
1.25L果粒橙
80
8
2
6956416200265
450mL果粒芒果
80
3.5
3
6921311196364
1L冰红茶
80
4
4
6921311196494
1L绿茶
80
4
5
6924862101467
2L百事可乐
100
6.5
6
6900451893036
2L芬达
100
6.5
7
6900451891032
2L可口可乐
100
6.5
二、问题分析
为了实现使用计算机对超市商品进行管理，需要按照商品的不同分类，建立“商品信息表”，然后通过条码扫描器读取商品条码，录人每一种商品的具体数据。
上面的商品信息表中，每一个数据元素有相同的数据项。若将表中的每一个数据元素表示为商品i
（i为原表中的商品序号），可以得到按原序号顺序排列的序列，如图所示。
从表中可以看到，各个数据元素(商品)之间存在着对一的关系，自上而下顺序排列。此表也是线性表。
思考与讨论
1.在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表：A,B,C,D,…Z就是一个线性表。想一想，生活中还有哪些这样的例子？
思考与讨论
2.上一个项目中给出的抽象数据类型是否适用于商品信息表？为什么？
适用，在商品信息表中，对商品信息进行抽象后得到的数据是商品的集合，数据元素之间也是一对一的线性关系，在此数学模型的基础上定义的插入和删除操作，在以后需要插入删除时，直接调用即可。
为了便于理解，此处“商品信息表”设定为只包含序号、条形码、品名、库存数、零售价等信息。
线性表的特点是存在唯的一个被称作“第一个”的数据元素；存在唯一的个被称作“最后一个”的数据元素；除第一个外，结构中每个数据元素只有一个前驱；除最后一个外，结构中每个数据元素只有一个后继。
三、线性表
1.线性表概念
线性表是最基本、最简单、也是最常用的一种数据结构。
线性表（linear
list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
1.线性表概念
在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。
线性表是n(n≥0)个数据特性相同的元素构成的有限序列。记为(a1,a2,…,ai-1,ai,ai+1,…,an)，其中ai-1是ai的直接前驱元素，ai+1是ai直接后继元素，ai无前驱元素，an无后继元素。n称为线性表的长度，当n=0时，称为空表。
2.线性表特征
①集合中必存在唯一的一个“第一元素”。
②集合中必存在唯一的一个
“最后元素”。
③除最后一个元素之外，均有唯一的后继(后件)。
④除第一个元素之外，均有唯一的前驱(前件)。
3.基本操作
①MakeEmpty(L)
这是一个将L变为空表的方法
②Length（L）
返回表L的长度，即表中元素个数
③Get（L，i）
这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
④Prior（L，i）
取i的前驱元素
⑤Next（L，i）
取i的后继元素
3.基本操作
⑥Locate（L，x）
这是一个函数，函数值为元素x在L中的位置
⑦Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
⑧Delete（L，p）
从表L中删除位置p处的元素
⑨IsEmpty(L)
如果表L为空表(长度为0)则返回true，否则返回false
3.基本操作
⑩Clear（L）清除所有元素
?Init（L）同第一个，初始化线性表为空
?Traverse（L）遍历输出所有元素
?Find（L，x）查找并返回元素
3.基本操作
?Update（L，x）修改元素
?Sort（L）对所有元素重新按给定的条件排序
?strstr(string1,string2)用于字符数组的求string1中出现string2的首地址
例如，商品信息表=(商品1,商品2,商品3,商品4,商品5,商品6…)
线性表的抽象数据类型表示如下:
ADT
List
数据对象：D={ai
lai∈
ElemSet,i=1,2,n,n>=0}
数据关系：R={l
ai-1,ai∈D,i=2,…,n}
基本操作:
def
InitList(self)
#建立一个空的线性表
def
GetElem(self,i)
#返回线性表的第i个元素
def
Length(self)
#求线性表的长度
def
LocateElen(self,x)
#求元素x在线性表中的位置；若不存在x,则返回0
def
Insert(self,i,x)
#在线性表的第i个位置上插入一个新元素x
def
Delete(self,i)
#删除线性表的第i个元素
四、课后活动
1.请尝试写出线性表抽象数据类型的定义。
2.请分析以下生活中的案例，判断哪个是线性表。
①公司的组织结构表：总经理管理数名总监，每个总监管理数名经理，每个经理都有各自的下属和员工。
②学生信息表，如表2-5所示。
学生信息表
学号
姓名
性别
出生年月
家庭地址
1
张一帆
男
2001.03
东街西巷1号203室
2
李小红
女
2001.8
南大北路4弄5号6室
……
……
……
……
……
3.下面哪些事物的相关信息适合用线性表存储和管理，为什么？
①在银行排队等候服务的顾客；
②书架上的一排书籍；
③计算机桌面上的各种图标及其相关信息；
④计算机的文件和文件夹；
⑤个人的电话簿；
⑥一辆汽车的所有部件和零件。
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php