【数据结构】线性表:Python语言描述
1.线性表Python的 2.链接表单向链接表 的结点是一个二元组。 其表元素域elem保存着作为表元素的数据项(或者数据项的关联信息),链接域next里保存着同一个表里的下一个结点的标识。 首先定义一个简单的表结点类: class LNode: def __init__(self,elem,next_=None): self.elem = elem self.next = next_ 这个类里只有一个初始化方法,它给对象的两个域赋值。方法的第二个参数用名字next_,是为了避免与Python标准函数next重名。这也是Python程序中命名的一个惯例。第二个参数还提供了默认值,只是为了使用方便。 2.1 基本链表操作创建空链表只需要把相应的表头变量设置为空链接,在Python语言中将其设置为None。 删除链表应丢弃这个链表里的所有结点。这个操作的实现与具体的语言环境有关。在一些语言(如C语言)里,需要通过明确的操作释放一个个结点所用的存储。在Python中,这个操作很简单,只需简单地将表指针赋值为None,就抛弃了链表原有的所有结点。Python解释器的存储管理系统会自动回收不用的存储。 判断表是否为空将表头变量的值与空链接比较。在Python语言中,就是检查相应变量的值是否为None。 判断表是否满一般而言链表不会满,除非程序用光了所有可用的存储空间。 加入元素在链表里加入新元素时,并不需要移动已有的数据,只需为新元素安排一个新结点,然后根据操作要求,把新结点连在表中的正确元素。也就是说,插入新元素的操作是通过修改链接,接入新结点,从而改变表结构的方式实现的。 表首端加入
q = LNode(13) q.next = head.next head = q 注意,即使在插入前head指的是空表,上面三步也能正确完成工作。这个插入只是一次安排新存储和几次赋值,操作具有常量时间复杂度。 一般情况的元素插入要想在单链表里的某位置插入一个新结点,必须先找到该位置之前的那个结点,因为新结点需要插入它的后面,需要修改它的next域 设变量pre已指向要插入元素位置的前一结点,操作也分为三步: q = LNode(13) q.next = pre.next pre.next = q 删除元素删除表首元素 一般情况的元素删除 扫描、定位和遍历链表操作的复杂度求表的操作def length(head): p,n = head,0 while p is not None: n += 1 p = p.next return n 3.3.3 单链表类的实现(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |