教科版 高二选择性必修1信息技术第2单元第1课《线性表结构及其实现》课件+教案

1.3认识数据抽象高中信息技术/教科版/选择性必修1目录1问题导入2.新课讲授3.实践操作4.课堂小结1.问题导入知识回顾——线性结构数据元素之间的排列次序存在一种明确的先后关系，这样的数据组织方式称为线性结构。在线性结构中，除了最后一个元素，每个元素都有一个唯一的后继元素，所有元素都排成一个线性序列。2.新课讲授线性表的概念线性表(linear list)按线性结构组织数据元素。在线性表中，数据元素之间存在前后的顺序关系。每个数据元素都有一个顺序号，顺序号是连续的整数。通过顺序号可以访问数据元素。线性表中的数据元素可以是一个数或一个字符，也可以是一个对象。 任务一 手工整理图书 活动1 认识线性排列（2）第3本书的书名是 ，紧挨着它的后一本是 ，紧挨着它的前一本是 。（3）第8本书的书名是 ，紧挨着它的前一本是 。《数据与计算》《信息系统与社会》《数据与数据结构》《人工智能初步》《信息系统与社会》《算法初步》《开源硬件项目合计》 任务一 手工整理图书 活动2 整理图书（1）添加图书。图书馆新采购了图书《移动应用设计》，放在书架最右边，请在图左图中相应的书脊上写上书名。（2）借阅图书。有同学借阅了图书《人工智能初步》，请在右图中相应的书脊上写上书名。移动应用设计三维设计与创意开源硬件项目设计算法初步设计 任务一 手工整理图书 活动2 整理图书（3）归还图书。有同学归还了图书《网络基础》，需将该书放置在图书《数据管理与分析》左面，请在图中相应的书脊上写上书名。（4）查询图书。经过以上操作后，图书列表中共有本图书，第8本书的书名是 。 网络基础 三维设计与创意开源硬件项目设计9算法初步线性表的特征在线性表中插入或删除数据元素，该元素之后的数据元素顺序号都将改变。从以上活动可以看出，线性表的基本操作主要包括追加、删除、插入、查询等操作。为了便于在程序中使用线性表解决问题，需要定义线性表抽象数据类型(ADT LinearList)，接口如下：线性表抽象数据类型ADT LinearList:LinearList( ):创建空线性表。appendItem(item):将数据元素item追加到线性表removeItem(pos):从线性表中删除pos位置的数据元素getItem(pos):取得pos位置的数据元素。setItem(pos,item):设置线性表pos位置的数据为item。size( ):获得线性表中数据元素的个数。isEmpt( ):判断线性表是否为空insertItem(item,pos):将item插入表中pos位置。 任务一 手工整理图书 活动3 用线性表实现图书整理借助抽象数据类型LinearList，可以方便地用线性表实现任务。请补全下面的代码或注释。01. books=LinearList( ) #创建一个空线性表02.books.appendItem("数据与计算") #追加“数据与计算”03.books.appendItem("信息系统与社会”) #追加“信息系统与社会“04.books.appendItem("数据与数据结构”) # 05.books.appendItem("数据管理与分析”)# 06.books.appendItem("人工智能初步") # 07.books.appendItem("三维设计与创意”)# 08.books.appendItem("开源硬件项目设计”) # 追加“数据与数据结构“追加“数据管理分析“追加“人工智能初步“追加“三维设计与创意“追加“开源硬件项目设计“ #追加“算法初步” #追加“移动应用设计”11. books.removeItem(4) #在位置4删除图书12.books.insertItem("网络基础”,3) #在位置3插人“网络基础”13.print(books.getItem(7)) #显示位置7的图书名称14.print(books.size( )) #显示图书数量books.appendItem("算法初步”)books.appendItem("移动应用设计”) 任务一 手工整理图书 活动3 用线性表实现图书整理 任务二 编程整理图书 活动1 用顺序存储实现线性表Python的列表采用了顺序存储的方式，可以保存多个数据，并提供了一些好用的方法。利用列表可以方便地实现线性表。列表的第一个存储位置的顺序号为0。以下用列表items来保存线性表中的数据元素(1)创建空列表由构造方法__init__（）完成，它的功能是生成一个空的列表items。01. class LinearList:02.def __init__(self):03.self.items=[ ] #空列表 任务二 编程整理图书 活动1 用顺序存储实现线性表(2)追加数据元素在列表最后添加数据元素，可以使用列表的方法append。04.def appendItem(self,item):05.self.items.append(item) #在列表最后增加一个元素(3)删除数据元素删除线性表指定位置的数据元素，可以使用列表的pop方法。06.def removeItem(self,pos):07.self.items.pop(pos) #删除表中pos位置的元素 任务二 编程整理图书 活动1 用顺序存储实现线性表(4)插入数据元素在线性表中把一个元素插入到指定位置，这个位置及之后的数据元素会向后移动，顺序号发生变化。08.def insertItem(self,item,pos): #把item插人表中pos位置09.self.items.insert(pos,item) 任务二 编程整理图书 活动1 用顺序存储实现线性表(5)其他操作def getItem(self,pos): #获得位置pos的数据元素return self.items[pos] def setItem(self,pos,item): #设置位置pos的值为itemself.items[pos]=itemdef size(self): #获取线性表的数据元素个数return len(self.items)def isEmpty(self): #判断线性表是否为空return self.size()==0 任务二 编程整理图书 活动1 用顺序存储实现线性表顺序表和数组线性表的顺序存储用一组连续的存储单元依次存储线性表的数据元素。利用这种存储方式实现的线性表叫作顺序表。如果顺序表中各数据元素占用的存储空间大小相同 (比如是同一种类型的数据)，这样的顺序表叫数组。各个数据元素叫数组元素，数据元素的序号叫数组下标。如果知道数组的起始存储位置及单个数组元素占用空间大小，各个数组元素的存储位置可以通过计算得到，因而数组具有随机访问的特点，存取数组元素的效率很高。 任务二 编程整理图书 活动2 用链式存储实现线性表用链式存储实现的线性表是一个节点序列。节点中不仅保存数据，还保存下一个节点的存储位置。用链式存储实现的线性表也叫作链表。首先定义链式存储所需要的节点类。01. class Node:02.def __init__(self,item):self.data=item #数据区04.#链接区，指向下一个节点，初始化时为空05.self.next=None 任务二 编程整理图书 活动2 用链式存储实现线性表(1)创建空线性表创建空线性表由构造方法__init__（）完成。链表需要有一个头节点引用变量head指向第一个节点。新创建的链表还没有节点，所以将head指向空。06.#链式存储实现的线性表07.class LinearList:08.def __init__(self):09.self.head= #让头节点引用指向空None 任务二 编程整理图书 活动2 用链式存储实现线性表(2)追加数据元素在链表的末端添加节点，首先生成新节点，再找到链表尾节点，最后让尾节点指向新节点。10.#在链表末端添加数据元素11.def appendItem(self,item):12.temp=Node(item) #用item生成节点类对象temp#如果链表为空13.if self.head==None:14.self.head=temp15.return 任务二 编程整理图书 活动2 用链式存储实现线性表(2)追加数据元素16.tail= #tai1先指向头节点17.while tail.next!=None: #tail还没有指向最后节点18.tail=tail.next #向后移动19.tail.next= #链接新节点self.headtemp 任务二 编程整理图书 活动2 用链式存储实现线性表(3)删除数据元素删除链表中的数据元素，需要先从第一个节点开始向后移，直到指定位置。假设要删除的节点的下一个节点为p。先移动到要删除位置前面的节点previous，再让previous指向节点p。20.#删除表中pos位置的节点28.21.def removeItem(self， pos):22.previous=self.head #要删除位置的前一个位置 任务二 编程整理图书 活动2 用链式存储实现线性表(3)删除数据元素23.if pos==0: #如果要删除的是链表头节点24.self.head=self.head.next25.return26.n=927.while n