2.1《线性表结构及其实现》

1.3认识数据抽象 高中信息技术/教科版/选择性必修1 目录 1问题导入 2.新课讲授 3.实践操作 4.课堂小结 1.问题导入 同学们，数据结构有几种类型？你认为哪一种最简单？你能举一些线性结构的例子吗？ 数据结构有线性结构、树形结构和图状结构三种结构类型。我觉得线性结构最简单，它是最常见的数据组织结构。 排列好的图书、餐厅刷卡就餐都是线性结构。 那线性结构有什么特点呢？我们一起来回顾一下吧！ 知识回顾——线性结构 数据元素之间的排列次序存在一种明确的先后关系，这样的数据组织方式称为线性结构。 在线性结构中，除了最后一个元素，每个元素都有一个唯一的后继元素，所有元素都排成一个线性序列。 这种图书排列方式是线性的吗？ 不是。因为它的排列是无序的。不符合线性排列的有序特征。 2.新课讲授 线性表的概念 线性表(linear list)按线性结构组织数据元素。在线性表中，数据元素之间存在前后的顺序关系。每个数据元素都有一个顺序号，顺序号是连续的整数。通过顺序号可以访问数据元素。线性表中的数据元素可以是一个数或一个字符，也可以是一个对象。 线性表中的顺序号从0开始，而日常生活中说第几个元素，一般是从1 开始，比如第 12个元素的顺序号为11，请注意区分。 任务一 手工整理图书 活动1 认识线性排列 填一填 （1）从左数第1本书的书名是 , 紧挨着它的后一本是 。 （2）第3本书的书名是 ，紧挨着它的后一本是 ，紧挨着它的前一本是 。 （3）第8本书的书名是 ，紧挨着它的前一本是 。 《数据与计算》 《信息系统与社会》 《数据与数据结构》 《人工智能初步》 《信息系统与社会》 《算法初步》 《开源硬件项目合计》 任务一 手工整理图书 活动2 整理图书 填一填 （1）添加图书。图书馆新采购了图书《移动应用设计》，放在书架最右边，请在图左图中相应的书脊上写上书名。 （2）借阅图书。有同学借阅了图书《人工智能初步》，请在右图中相应的书脊上写上书名。 移动应用设计 三维设计与创意 开源硬件项目设计 算法初步设计 任务一 手工整理图书 活动2 整理图书 填一填 （3）归还图书。有同学归还了图书《网络基础》，需将该书放置在图书《数据管理与分析》左面，请在图中相应的书脊上写上书名。 （4）查询图书。经过以上操作后，图书列表中共有 本图书，第8本书的书名是 。 网络基础 三维设计与创意 开源硬件项目设计 9 算法初步 线性表的特征 在线性表中插入或删除数据元素，该元素之后的数据元素顺序号都将改变。 线性表中的顺序号从0开始，而日常生活中说第几个元素，一般是从1 开始，比如第 12个元素的顺序号为11，请注意区分。 从以上活动可以看出，线性表的基本操作主要包括追加、删除、插入、查询等操作。为了便于在程序中使用线性表解决问题，需要定义线性表抽象数据类型(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的值为item self.items[pos]=item def 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=temp 15.return 任务二 编程整理图书 活动2 用链式存储实现线性表 (2)追加数据元素 16.tail= #tai1先指向头节点 17.while tail.next!=None: #tail还没有指向最后节点 18.tail=tail.next #向后移动 19.tail.next= #链接新节点 self.head temp 任务二 编程整理图书 活动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.next 25.return 26.n=9 27.while n<pos-1: #找到要删除的前一个节点 28.previous=previous.next 29.n=n+1 30.previous.next= #删除节点 previous.next.next 任务二 编程整理图书 活动2 用链式存储实现线性表 (4)获取数据元素 获得链表指定位置的数据元素，需要先从头节点移动到指定位置，再返回该位置的数据元素。请补全下面的代码。 31.#得到pos位置的数据元素 32.def getItem(self,pos): 33.current=self.head #没到指定位置 34.count=0 35.while count<pos: 36.current= #指向下一个节点 37.count=count+1 #数加1 38.return current.data #返回数据元素 current.next 任务二 编程整理图书 活动2 用链式存储实现线性表 (5)获取数据元素个数 从头节点遍历整个链表，并计算数据元素节点的个数。 39.#统计链表的节点数 40.def size(self): 41.current=self.head #指向头节点 42.count=0 43.while current!=None: #不是链表的结尾#节点数增加1 44.count=count+1 #节点数加1 45.current= #指向下一个节点 46.return count #返回节点数 current.next 任务二 编程整理图书 活动2 用链式存储实现线性表 (6)判断线性表是否为空 判断线性表是否为空,可以通过判断头节点引用是否为None 实现。 47.def isEmpty(self): #判断链表是否为空 48.return self.head==None (7)插入数据元素 插入节点需要先产生一个新节点，放置要插入的数据元素;然后从头节点移动到插入位置前面的节点previous;最后让新节点指向previous的后一个节点，让previous指向新节点。请补全下面的代码。 任务二 编程整理图书 活动2 用链式存储实现线性表 49.#将item插入表中pos位 50.def insertItem(self,item,pos): 51.temp=Node(item) #生成新节点 52.if pos==0: #如果在头节点前插人 53.temp.next=self.head #新节点指向头节点 54..self.head=temp #头节点指向新节点 55..return (7)插入数据元素 任务二 编程整理图书 活动2 用链式存储实现线性表 56.previous=self.head #指向插入位置前一节点 57.n=0 #计数变量置0 58.while n<pos-1: #找到pos位置的前一个位置#计数加1 59.n=n+1 #计数加1 60.previous=previous.next #指向下一节点 61.temp.next= #指向插入位置处节点 6.previous.next=temp #前一节点指向新节点 previous.next (7)插入数据元素 任务二 编程整理图书 活动2 用链式存储实现线性表 链表 用链式存储实现的线性表叫链表。链表由一系列的节点通过链接串连在一起。 在链表中，相邻节点的存储位置不一定相邻，节点之间的顺序由链接关系决定。在插入和删除数据元素时，并不需要移动节点，所以效率很高。但链表中每个节点都增加了引用信息，需要使用额外的存储空间。 另外，在访问数据元素时，要从头节点开始依次向后移动寻找，效率不如顺序表高。 3.实践操作 教科书第41页的程序还不能运行，接下来我们对照这些ADT接口标准，实现线性表，让教科书第41页的程序能正常进行。 1.两位同学一组，参考教科书第41页至第47页，一人选择利用顺序存储，另一人选择链式存储实现LinearList类。目标是让教科书第41页的程序能正确运行。哪位同学的程序能正常运行，请举手示意。 2.用顺序表实现的同学，向对方讲解顺序表、数组的概念。用链表实现的同学，向对方讲解链表的概念和特点。 4.课堂小结 本节我们从实际生活中引出线性表并对线性表常用的操作进行抽象，引出了线性表抽象数据类型；介绍了线性表的实现方案，引出了顺序表、数组和链表等概念。 请同学们认真完成教材中的拓展练习哦！ 下节课见！ $$