《数据结构》课件1第3章线性表.pptx
《《数据结构》课件1第3章线性表.pptx》由会员分享,可在线阅读,更多相关《《数据结构》课件1第3章线性表.pptx(83页珍藏版)》请在文库网上搜索。
1、主要学习内容1线性表的概念和性性表的概念和性质线性表的性表的顺序序实现23线性表的性表的链式式实现4线性表性表应用及其下算法用及其下算法设计线性表概念及性质v线性表性表简称表,称表,是是由由n(n0)个数据元素构成的有限序列。)个数据元素构成的有限序列。n称为线性表的表长,当n=0,表长为0,表中没有元素,称为空线性表,简称空表;当n0,非空表,记为:L=(a0,a1,a2,ai,an-1);每个元素有一个固定的位序号,如元素a0的位序号是0,ai的位序号是i;例如,A=(5,3,2,9)包含4个整数,这4个元素的位序依次为0、1、2、3。线性表v线性表性表中元素之中元素之间的次序非常的次序非
2、常重要重要。v举例:例:一个一个单词是是字符构成的字符构成的线性表性表;一一篇文章是篇文章是单词构成的构成的线性表性表;一一个菜个菜谱是由操作指令构成的是由操作指令构成的线性表性表;一一个文件是磁个文件是磁盘上的数据上的数据块构成的构成的线性表性表。线性表vL=(a0,a1,a2,ai,an-1),除除了了首首元元素素a0,每每个个元元素素都都有有一一个个直直接接前前驱,除了尾元素,除了尾元素an-1,每个元素都有一个直接后,每个元素都有一个直接后继;v元元素素之之间的的关关系系为一一对一一的的线性性关关系系,线性性表表的的逻辑结构构是是线性性结构。构。v如如果果线性性表表中中的的元元素素值随
3、随着着位位序序的的增增大大递增增或或递减减,则该线性性表表称称为有序表;有序表;v如如果果元元素素值的的大大小小和和位位序序之之间没没有有特特定定关关系系,则该线性性表表称称为无无序表。序表。线性表v有有穷性:性:线性表中的元素个数是有限的;性表中的元素个数是有限的;v同同构构性性:一一般般来来说,线性性表表中中所所有有元元素素具具有有相相同同的的性性质,即即具具有有相同的相同的类型;如果数据元素性型;如果数据元素性质不同,通常不具有不同,通常不具有实际应用意用意义;v不不同同类型型元元素素构构成成的的线性性表表,如如一一个个整整数数线性性表表和和一一个个书目目单,虽然然作作用用和和应用用场合
4、合不不同同,但但其其元元素素之之间的的逻辑关关系系和和基基本本操操作作是相同的。是相同的。线性表特点T类型型元素构成的元素构成的线性表是由性表是由T类型型元素构成的有限序列元素构成的有限序列,并且具有以下基本操作:,并且具有以下基本操作:(1)创建一个空建一个空线性表(性表(init););(2)判断)判断线性表是否性表是否为空(空(empty););(3)求出)求出线性表的性表的长度(度(len););(4)将)将线性表清空(性表清空(clear););(5)在指定位置插入一个元素()在指定位置插入一个元素(insert););(6)删除指定位置的元素(除指定位置的元素(remove););
5、(7)获取指定位置的元素(取指定位置的元素(retrieve););(8)用指定元素替)用指定元素替换线性表的指定位置性表的指定位置处的元素(的元素(replace););(9)判断指定元素)判断指定元素item在在线性表中是否存在(性表中是否存在(contains););(10)对线性表中每个元素性表中每个元素进行遍行遍历(traverse)。)。线性表的抽象数据类型ADT1)动态性:线性表是动态的结构,可以进行元素的插入或删除,长度可以变化。2)基于位序进行插入、删除、读写等操作。vPython列表(列表(list)表元素可不同构实现ADT中的全部方法vPython元元组(tuple)表不
6、可以改变,不能修改、添加、删除元素,只能按位序访问vPython字符串(字符串(str)表中元素限定为单个字符字符串操作Python内置线性结构 线性表抽象类fromabcimportABCMeta,abstractmethodclassAbstractList(metaclass=ABCMeta):抽象表类,metaclass=ABCMeta表示AbstractList类为ABCMeta的子类abstractmethoddef_init_(self):初始化线性表abstractmethoddefempty(self):判断表是否为空abstractmethoddef_len_(self):
7、返回表中元素的个数abstractmethoddefclear(self):清空表abstractmethoddefinsert(self,i,item):在表中i号位置插入元素item“abstractmethoddefremove(self,i):删除i号位置的元素abstractmethoddefretrieve(self,i):获取i号位置的元素abstractmethoddefreplace(self,i,item):用item替换表中i号位置的元素abstractmethoddefcontains(self,item):判断表中是否包含元素itemabstractmethoddef
8、traverse(self):输出表中的所有元素v按操作方法不同按操作方法不同普通线性表、列表,是Python列表的抽象概念栈队列双端队列优先队列v按数据元素按数据元素类型不同型不同字符串线性结构分类v顺序存序存储v链式存式存储线性表的存储线性表的顺序存储v所所有有元元素素按按照照逻辑顺序序依依次次存存储在在一一块连续的的存存储空空间中中,简称称顺序表。序表。v具具有有前前驱、后后继关关系系的的两两个个元元素素其其内内存存映映像像也也相相邻,即即元元素素之之间物理位置的相物理位置的相邻直接反映其直接反映其逻辑关系的前后。关系的前后。顺序存储元素内置的顺序表an-1n-1aiia11a00数据元
9、素数据元素逻辑地址逻辑地址an-1Location(a0)+(n-1)*caiLocation(a0)+i*ca1Location(a0)+ca0Location(a0)数据元素数据元素存储地址存储地址c 是是一个一个元素的大小。元素的大小。an-1Location(a0)+(n-1)*caiLocation(a0)+i*ca1Location(a0)+ca0Location(a0)数据元素数据元素存存储地址地址c 是一个指针(引用)的大小是一个指针(引用)的大小,指向元素对象。指向元素对象。元素外置的顺序表v不不管管是是元元素素内内置置的的顺序序表表和和外外置置的的顺序序表表,根根据据元元素
10、素位位序序号号可可以以直直接接定定位位到到元元素素的的地地址址,对元元素素的的存存取取操操作作可可以以在在O(1)时间内内完完成。成。v称称顺序表具有随机存取(序表具有随机存取(Random Access)或直接存取的特性。)或直接存取的特性。v示意示意图:顺序表特点及简化表示012i-1a0a1a2aian-1entryv如如线性表性表A=(5,3,2,9)v在在Python语言中直接将其表示言中直接将其表示为一个一个list,如,如alst=5,3,2,9v未封装未封装实现。顺序表存储1:用Python列表直接表示Python列表的存储64位机,每个指针8个字节Python列表的空间递增机
11、制倍增策略和增量策略相结合倍增策略:将原来数组的容量乘以一个大于1的常数;增量策略是给数组容量增加一个数值。在空间较小时,采用倍增机制;在列表空间较大时,采用增量策略,依次增加9,10,11,12,14,16,18个空间。从空表开始生成长度为1000(10000)的表,需要27(46)次空间追加操作。列表长度0,总占用字节数56列表长度1,总占用字节数88,表元素容器大小4,增加大小:4列表长度5,总占用字节数120,表元素容器大小8,增加大小:4列表长度9,总占用字节数184,表元素容器大小16,增加大小:8列表长度17,总占用字节数256,表元素容器大小25,增加大小:9列表长度26,总占
12、用字节数336,表元素容器大小35,增加大小:10列表长度36,总占用字节数424,表元素容器大小46,增加大小:11列表长度47,总占用字节数520,表元素容器大小58,增加大小:12列表长度59,总占用字节数632,表元素容器大小72,增加大小:14列表长度73,总占用字节数760,表元素容器大小88,增加大小:16列表长度89,总占用字节数904,表元素容器大小106,增加大小:18列表长度107,总占用字节数1064,表元素容器大小126,增加大小:20列表长度127,总占用字节数1240,表元素容器大小148,增加大小:22列表长度149,总占用字节数1440,表元素容器大小173,
13、增加大小:25列表长度174,总占用字节数1664,表元素容器大小201,增加大小:28列表长度202,总占用字节数1920,表元素容器大小233,增加大小:32列表长度234,总占用字节数2208,表元素容器大小269,增加大小:36列表长度270,总占用字节数2528,表元素容器大小309,增加大小:40列表长度310,总占用字节数2888,表元素容器大小354,增加大小:45列表长度355,总占用字节数3296,表元素容器大小405,增加大小:51列表长度406,总占用字节数3752,表元素容器大小462,增加大小:57列表长度463,总占用字节数4264,表元素容器大小526,增加大小
14、:64扩容总次数:21import syslst=empty_size=b=sys.getsizeof(lst)count=0print(列表长度%4d,总占用字节数%4d%(0,b)for k in range(500):lst.append(None)a=len(lst)old_b=b b=sys.getsizeof(lst)if b!=old_b:print(列表长度%4d,总占用字节数%4d,表元素容器大小%4d,增加大小:%4d%(a,b,(b-empty_size)/8,(b-old_b)/8)count+=1print(扩容总次数:,count)整个算法O(n)resize所花时
15、间可以忽略;每个append操作的摊销时间复杂度仍为O(1)。顺序表存储2:用python的list封装实现利用底层C数组实现顺序表v定定义一一个个自自定定义类DynamicArrayList来来模模拟一个一个顺序表;序表;v利利用用ctypes模模块提提供供的的底底层C数数组实现线性性表表的的顺序序存存储,需需import ctypes ;v底底层C数数组对应于于内内存存中中的的一一块容容量量确确定定的的连续内内存存空空间,线性性表表元元素素依依次次直直接接存存放放在在该数数组中中,即即元元素素内内置置方方式式顺序存序存储。顺序表存储3:利用底层C数组实现顺序表importctypesfro
16、mAbstractListimportAbstractListclassDynamicArrayList(AbstractList):def_init_(self):defempty(self):def_len_(self):defclear(self):definsert(self,i,item):defremove(self,i):defretrieve(self,i):defreplace(self,i,item):defcontains(self,item):defappend(self,item):deftraverse(self):def_str_(self):def_make_a
17、rray(self,c):def_resize(self,c):初始化def _init_(self,cap=0):初始化一个空表 super()._init_()self._cur_len=0#线性表元素个数计数 self._capacity=cap#默认数组容量 self._entry=self._make_array(self._capacity)#存放所有表元素的数组def _make_array(self,c):#私有方法 返回一个容量为c的数组 return(c*ctypes.py_object)()O(1)判空、求长度、清空def empty(self):return self.
18、_cur_len=0def _len_(self):返回线性表中元素个数 return self._cur_lendef clear(self):del self._entry self._capacity=0 self._cur_len=0 O(1)插入 insert(self,i,item)if self._cur_len=self._capacity:#如果线性表的空间已用完 if self._capacity=0:cap=4 else:cap=2*self._capacity self._resize(cap)#给线性表扩容1倍空间 O(n)for j in range(self._c
19、ur_len,i,-1):#线性表尾部至i号位置所有元素后移 self._entryj=self._entryj-1 self._entryi=item#将新元素item放在i号位置 self._cur_len+=1#表长增1def insert(self,i,item):将元素item插入到表的i号位置 if not 0=i=self._cur_len:raise IndexError(插入位置不合法)数组空间扩容def _resize(self,c):#保护方法 将数组空间扩容至c.temp=self._make_array(c)#生成新的更大的数组temp for k in range(
20、self._cur_len):#将原线性表元素复制到新数组temp中 tempk=self._entryk self._entry=temp#启用新数组temp存放线性表元素 self._capacity=c#当前线性表的容量为c按位置删除 def remove(self,i)def remove(self,i):if not 0=i self._cur_len:raise IndexError(删除位置不合法)O(n)item=self._entryi for j in range(i,self._cur_len-1):#将找到位置之后的元素后移。self._entryj=self._ent
21、ryj+1 self._cur_len-=1#表长减1 return item#返回被删除元素按值查找def contains(self,item):for i in range(self._cur_len):if self._entryi=item:return True return FalseO(n)按位置读写def retrieve(self,i):if not 0=i self._cur_len:raise IndexError(读取位置不合法)return self._entryidef replace(self,i,item):if not 0=i self._cur_len:r
22、aise IndexError(写入位置不合法)self._entryi=itemO(1)随机存取vPython语言言的的列列表表和和C语言言的的数数组都都可可以以用用来来实现线性性表表的的顺序序存存储,并且其基本操作的,并且其基本操作的实现和和时间性能也大体一致。性能也大体一致。v在在具具体体存存储和和使使用用时,Python语言言的的列列表表更更加加方方便便灵灵活活,C语言言的数的数组空空间更加更加紧凑。凑。vPython列列表表的的本本质就就相相当当于于一一个个指指针数数组,凡凡是是用用列列表表实现的的各各个数据个数据结构都可以用构都可以用C语言数言数组或或array模模块中的数中的数组
23、来来实现。说明线性表的链式实现v线性性表表的的链式式实现不不需需要要使使用用连续内内存存空空间,表表中中的的数数据据元元素素可可以存以存储在任意可用空在任意可用空间中。中。v链式式结构通构通过显式的指式的指针域来表明元素的前域来表明元素的前驱、后、后继关系。关系。v链式式结构构中中,元元素素在在内内存存中中的的映映像像称称为结点点,结点点包包含含两两大大部部分分:元元素素值和和指指针域域,其其中中指指针域域用用于于记录其其后后继结点点或或前前驱结点点的的地址。地址。v线性性表表的的链式式实现结构构简称称为链表表,根根据据结点点中中指指针域域的的数数目目及及尾部尾部结点指点指针的定的定义,可以分
24、,可以分为单链表、双向表、双向链表、循表、循环链表等。表等。v最常最常见的的链表形式是表形式是单链表。表。链表概述v单链表表的的每每个个结点点包包含含2个个域域,其其中中entry域域存存储元元素素,next域域存存储后后继结点的指点的指针。v在在Python语言言中中,entry域域存存储的的是是元元素素的的指指针,而而在在其其他他语言言如如C+中,中,entry域存域存储的即是元素的即是元素值。单链表的结点结点类class Node:def _init_(self,data,link=None):self.entry=data self.next=linkv L=(a0,a1,a2,ai,
25、an-1)Python语言中单链表的存储C、Java等语言中单链表的存储单链表单链表示意图用首结点指针head代表整个线性表带头结点的单链表a0aian-1headai-1ai+1首结点尾结点头结点用头结点指针head代表整个线性表python的对象名即指针单链表类fromAbstractListimportAbstractListfromNodeimportNodeclassLinkedList(AbstractList):def_init_(self):defempty(self):def_len_(self):defclear(self):definsert(self,i,item):d
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 线性