06.2链表.pdf

信息技术组陈功杰6.2 数据结构链表数据与数据结构1.数据结构使用数据元素、维护这种关系节点、记录、顶点0123456789next123456789-1next3468217-195线性表：除头、尾外，每个元素有唯一的前驱和后继数组：逻辑结构相邻的元素，存储结构上也相邻链表：逻辑结构相邻，存储结构上不一定相邻2.数组和链表1a2a3a4a71421526477NULL78head3.1 链表节点的定义class _Node():定义每个节点拥有的属性#_slots_ 是一个元组，定义并保证每个节点只能拥有的属性#好处是节省内存使用_slots_=_element,_nextdef _init_(self,item,next=None):self._element=itemself._next=next3.2 链表类的定义class Link():一个只带表头指针的单向链表#嵌套定义节点的类class _Node():定义每个节点拥有的属性#_slots_ 是一个元组，定义并保证每个节点只能拥有的属性#好处是节省内存使用_slots_=_element,_nextdef _init_(self,item,next=None):self._element=itemself._next=next#链表定义开始def _init_(self):初始化空链表self._head=Noneself._size=0def _len_(self):返回链表的长度，用系统函数len()可以调用之return self._size调用：a=Link()3.3 插入元素def insert(self,k,item):在第k个位置(从0数)插入一个新节点，节点值是item#插在头部if k=0:newest=self._Node(item,self._head)self._head=_self._size+=1return#插在其他位置p=self._headwhile _:#先走到被插位置的前一个p=p._nextk-=1newest=self._Node(item,p._next)_self._size+=1k 1p._next=newestnewest3.4 删除元素（并返回被删除的元素值）def pop(self,k):删除第k个元素（从0数）if k=0:item=self._head._elementself._head=_self._size-=1return itemp=self._headwhile k 1:#先走到被删元素的前一个p=p._nextk-=1q=p._next_self._size-=1return _self._head._nextp._next=q._nextq._element3.5 链表的输出def _str_(self):将链表转成字符串，可以用str()函数或print()函数调用之res=p=self._headwhile _:res+=str(p._element)+p=p._nextres+=str(p._element)return resp._next!=None作业请用链表类完成“测验1719:【Python数据结构】数组”的A、B、C三题