高中信息技术沪教版（2019）选修1 数据与数据结构2.设计算法一等奖课件ppt

第二单元 初识数据结构

项目三 探索商品基本信息表的实现

——线性表的应用

第二课时 设计算法

❑教材分析

本节的主要内容是设计算法。根据前面所学的线性表的存储结构，详细阐述线性表采用顺序存储(即顺序表)时，用数组表示商品信息的插入和删除过程，以及采用链式存储(即链表)时，商品信息的插入和删除过程。对比两种存储结构在数据插入和删除时的别，比较数组和链表的不同。在对教材上的活动以及生活中其他问题情境进行抽象时，帮助学生感悟抽象数据类型在数据处理时的重要性；学会用数据结构来表达数据的逻辑关系，提高信息意识和计算思维能力。

❑教学目标

1.理解线性表顺序存储和链式存储时，数据的插入和删除过程；

2.比较组和链表的区别，明确上述两种数据结构在存储不同类型数据中的应用。

❑教学重点

1.线性表顺序存储数据的插入和删除过程。

2.线性表链式存储数据的插入和删除过程。

❑教学难点

1.数据的插入和删除过程。

❑教学方法

体验法、讲授法、讨论法、示例法

❑教学准备

　　计算机教室、多媒体设备、多媒体广播软件、安装Python编程的相关软件、教学课件、学生上机练习的程序文件，学生工作单等。

❑教学过程

一、新课导入

复习上节课学习的内容线性表的概念和特点。

如下表：

“商品信息表”——线性表不能被计算机直接处理，需要为它选择合适的存储结构，然后设计算法编程实现相关功能，如插入一条商品信息或者删除一条商品信息等。

二、设计算法

线性表既可以采用顺序存储结构存储，也可以采用链式存储结构存储。

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所示。

小贴士

当一个序列中只含有指向它的后继结点的链接时，就称该链表为单链表。

思考与讨论

1数组和链表有何区别？

2.你觉得本例中，链表插入操作方便还是数组方便？为什么？如果编程实现，哪个执行操作的次数可能多些？

参考：

1.数组的数据在内存中连续存放，无须为表示表中元素之间的逻辑关系而增加额外的存储空间，但是插入和删除需要移动大量的元素。

2.链表中的结点在内存中不是连续存放，需要增加空间来存放下一个结点的地址，但是插入和删除操作非常方便。链表的插入操作方便，只需要修改指针即可，不需要移动元素。数组执行的次数要多一些。

三、线性表的存储

线性表可以使用顺序存储结构存储（此时称为顺序表），也可以使用链式存储结构存储

（此时称为链表）。

1.线性表的顺序存储

大多数高级程序语言的数组在计算机内的表示是顺结构。为此可以用数组来表示顺

序表。

数组( array)是由数据类型相同的数据元素构成的有序集合。它被用来存放大量数据

类型相同的数据。

数组与变量一样，每个数组都要有一个唯一的名称，即数组名，命名规则和变量相同。

数组元素是组成数组的基本单元，每一个存储单元对应于一个数组元素。数组元素用数组的名字和它自己在数组中的顺序位置来表示。例如，d[0]表示名字为d的数组中的第一个元素，d[1]代表数组d中的第二个元素，以此类推，如图2-16所示。

图2-16数组d

①插入操作

如果要实现在线性表L中的第i个位置插入新元素e,插入算法的思想为：

②删除操作

删除算法的思想为：

数组的优点是具有随机访问的特性，可以快速地存取任意位置的元素。缺点是为了保持存储的连续性，插入和删除操作可能会移动大量元。因此，数组适合查找和存取数据的操作，而不适合插入和删除的操作。

2.线性表的链式存储

链式存储是将数据元素存储在地址任意的存储空间中，用指针来指出元素间的逻辑关系，所以每个结点空间由数据域和指针域两部分组成，数据域用来存放数据元素，指针域用来存放指向后继的指针。链式存储是一种动态存储结构，即每当要存储元素时就去申请一个存储空间，存放数据元素及指针。

链表中的结点形式用以下方式表示：

①单链表的插入

假设存储元素e的结点为s，若要实现将e插入到ai和ai+1之间，如图所示，该如何做呢？

图2-17将要插入结点s

只须让s.next和 p. next的指针做一点改变即可实现插入。即：

s.next=p. next；

p. next=s；

通过图2-18可以理解以上两句代码。

图2-18插入结点s

那么，这两句代码的顺序是否可以交换位置？

即先p.next=s,再s.next=p.next。

如果先执行 P.next=s的话，p.next会被s覆盖，s.next=p.next就等于s.next=s了，所

以这两句代码是不能颠倒次序的。

在单链表第i个位置上插入结点e的算法思想为;

②单链表的删除

单链表的删除操作如图2-19所示。

图2-19单链表的删除

假设元素a2的结点为q，要实现删除结点q的操作，其实就是将它的前驱结点的指针指向后继结点即可。

可以是：p.next=p.next.next也可以是：q=p.next;  p.next=q.next;

删除单链表第i个结点的算法思想为:

无论是单链表插入还是删除算法，它们其实都是由两部分组成：第一部分是从第一个元素开始逐个查找第i个元素，第二部分是实现插入和删除元素。

链表的优点是插入和删除的速度快，链表长度不固定，拓展灵活。缺点是不能随机查找，必须从第一个开始逐个查找，效率很低。因此，链表比较适合插入或删除数据频繁的操作，而不适合查找操作。

总之，线性表的顺序存储结构和链式存储结构各有其优缺点，不能简单地认为哪个好哪个不好，需要根据实际情况，来综合判断采用哪种存储结构更能满足需求。

四、课后活动

1.现需要删除商品3数据元素，请在图2-15的基础上，用图示方式呈现全过程（数组和单链表两种方式）。

图2-15数组和单链表

2.完成在商品3后插入商品5的算法步骤设计。