中小学教育资源及组卷应用平台 第二单元 初识数据结构 项目三 探索商品基本信息表的实现 ———线性表的应用 第二课时 设计算法 ?教材分析 本节的主要内容是设计算法。根据前面所学的线性表的存储结构，详细阐述线性表采用顺序存储(即顺序表)时，用数组表示商品信息的插入和删除过程，以及采用链式存储(即链表)时，商品信息的插入和删除过程。对比两种存储结构在数据插入和删除时的别，比较数组和链表的不同。在对教材上的活动以及生活中其他问题情境进行抽象时，帮助学生感悟抽象数据类型在数据处理时的重要性；学会用数据结构来表达数据的逻辑关系，提高信息意识和计算思维能力。 ?教学目标 1.理解线性表顺序存储和链式存储时，数据的插入和删除过程； 2.比较组和链表的区别，明确上述两种数据结构在存储不同类型数据中的应用。 ?教学重点 1.线性表顺序存储数据的插入和删除过程。 2.线性表链式存储数据的插入和删除过程。 ?教学难点 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 “商品信息表”———线性表不能被计算机直接处理，需要为它选择合适的存储结构，然后设计算法编程实现相关功能，如插入一条商品信息或者删除一条商品信息等。 二、设计算法 线性表既可以采用顺序存储结构存储，也可以采用链式存储结构存储。 1.采用顺序存储结构 线性表采用顺序结构存储时，称之为顺序表。很多高级程序设计语言的数组( ( array)在计算机内的表示也是顺序结构，为此，可以用数组来表示顺序表。假设用数组s来存放商品信息表的数据元素，则每个数据元素都可以采用s[0]、s[1]、[2]、s[3]表示，其中s为数组名，0,1,2,3……为数组下标，用来标识数据元素的位置和顺序。如图2-9所示(为方便说明，假设目前只有4条商品数据)。 若要在商品1后插入( insert)商品5,则插入位置后的每个数据元素都要向后移动空出插入位置然后插入商品5,具体过程如图2-10所示。 而删除( delete)操作恰好是插入操作的逆过程。若需将插入的商品5删除，则须将该数据元素后的所有数据元素依次向前移动，使后一数据元素覆盖前一数据元素。最终，依旧保证了数据元素存储的连续性，如图2-11所示。 小贴士 一个元素覆盖前一个元素后，该元素本身依旧存在于原先的位置上，要等到后一个元素将其覆盖。最后一个元素覆盖前一个元素后，最后一个位置须去掉。 思考与讨论 1.使用数组存储插入和删除移动数据元素的次数与什么相关？ 2.使用数组存储，确定插入和删除元素的位置是否方便？ 参考： 1.与数据的规模以及插入的位置有关。 2.方便，因为数组就是按照顺序来存储数据的。 2.采用链式存储结构 线性表采用链式存储结构存储时，称为链表。链表中数据可以是不连续存储的。链表不要求逻辑上相邻的数据素在物理位置上也相邻，数据元素之间通过指针链接，如2-12所示。 若要在商品1后插入商品5,先要切断插入位置前后的数据链，然后将断开的链连接到插入元素，具体过程如图2-13所示。 若要删除一个商品，只要将须删除数据元素的前一个数据元素的指针指向下一个数据元素即可，如图2-14所示。 小贴士 当一个序列中只含 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
