网站后台密码忘了怎么办,wordpress 滑块插件,上海松江做网站公司,北京微信网站搭建费用今天看了一下数据结构的书#xff0c;发现其实数据结构没有几种#xff0c;线性表#xff0c;数组#xff0c;字符串#xff0c;队列和栈#xff0c;等等#xff0c;其实是一回事#xff0c;然后就是树结构#xff0c;图结构。数据结构的理论并不难#xff0c;主要是…今天看了一下数据结构的书发现其实数据结构没有几种线性表数组字符串队列和栈等等其实是一回事然后就是树结构图结构。数据结构的理论并不难主要是要自己写一下这些数据结构以及对应的基本的操作方法这样就能够更快的提高。这一篇blog写一下线性表。线性表分为顺序表和链表一、顺序表顺序表就是相对于表中的数据地址也是顺序的所以可以随机存取。但是在操作插入和删除元素的时候由于要满足地址的连续性所以要移动很多的元素位置因此插入或者删除一个顺序表的元素的时间复杂度是o(n)。很多时候在对顺序表做合并的时候需要先对表中的元素进行排序然后再进行处理这样可以避免每次都从头进行查询。二、链表链表就失去了顺序表的随机存取特点即每次从中取一个元素都要从头开始找这样耗费了一些时间时间复杂度为o(n)但是在做插入和删除以及两个链表合并的时候就方便了很多只需要做一点指针修改就可以了。链表中的每一个元素节点都包含了数据部分和下一个节点的指针。一般在链表的头部附设一个头结点而且头结点一般不存储数据而是存放一些长度等附加信息或者不存储。在很多语言中没有指针这一概念而有数组的概念比如java和pythonjava中的数组还要求定义数组的类型也就是说必须都是同一类型的数据而python则没有要求所以python的list更贴近链表的真正含义。这种用数组描述的链表叫做静态链表。使用静态链表来描述链表对此类语言要方便很多了本身这些语言都提供了内置类来处理链表。除此之外还有循环链表双向链表(解决了无法向前搜索的问题但是在修改指针的时候需要有更多的操作)。 # -*- codingutf-8 -*-# 这个例子是Python版本的单链表class Node(object):def __init__(self, value, next0):self.value valueself.next next # 指针class LinkedList(object):# 链表的数据结构def __init__(self):self.head 0 # 头部def __getitem__(self, key):if self.is_empty():print Linked list is empty.returnelif key 0 or key self.get_length():print The given key is wrong.returnelse:return self.get_elem(key)def __setitem__(self, key, value):if self.is_empty():print Linked list is empty.returnelif key 0 or key self.get_length():print The given key is wrong.returnelse:return self.set_elem(key, value)def init_list(self, data): # 按列表给出 dataself.head Node(data[0])p self.head # 指针指向头结点print p, self.headfor i in data[1:]:p.next Node(i) # 确定指针指向下一个结点p p.next # 指针滑动向下一个位置print self.head.next.nextdef get_length(self):length 0p self.headwhile p ! 0: # 0 值就是Node结点中默认的 0 值表示下一个结点没有了即没有为其赋值length 1p p.nextreturn lengthdef is_empty(self):if self.head 0:return Trueelse:return Falsedef insert_node(self, index, value):if index 0 or index self.get_length():print Can not insert node into the linked list.elif index 0:temp self.headself.head Node(value, temp)else:p, post self.head, self.headfor i in xrange(index):post pp p.nexttemp ppost.next Node(value, temp)def delete_node(self, index):if index 0 or index self.get_length()-1:print Wrong index number to delete any node.elif self.is_empty():print No node can be deleted.elif index 0:temp self.headself.head temp.nextelif index self.get_length():p self.headfor i in xrange(self.get_length()-2):p p.nextp.next 0else:p self.headfor i in xrange(index-1):p p.nextp.next p.next.nextdef show_linked_list(self): # 打印链表中的所有元素if self.is_empty():print This is an empty linked list.else:p, container self.head, []for _ in xrange(self.get_length()-1):container.append(p.value)p p.nextcontainer.append(p.value)print containerdef clear_linked_list(self): # 将链表置空self.head 0def get_elem(self, index):if self.is_empty():print The linked list is empty. Can not get element.elif index 0 or index self.get_length()-1:print Wrong index number to get any element.else:p self.headfor _ in xrange(index):p p.nextreturn p.valuedef set_elem(self, index, value):if self.is_empty():print The linked list is empty. Can not set element.elif index 0 or index self.get_length()-1:print Wrong index number to set element.else:p self.headfor _ in xrange(index):p p.nextp.value valuedef get_index(self, value):p self.headfor i in xrange(self.get_length()):if p.value value:return ielse:p p.nextreturn -1l LinkedList()print The length of linked list now is: , l.get_length()print l.is_empty()l.init_list([1, 5, 12, fjd, 45, 999])print The length of linked list now is: , l.get_length()print l.is_empty()l.insert_node(4, 100)l.insert_node(6, cecil)l.show_linked_list()print The value of index 0 is: , l.get_elem(0)l.set_elem(0,1000)l.show_linked_list()print the index of *** is: , l.get_index(1009)print The length of linked list now is: , l.get_length()l.delete_node(3)#l.clear_linked_list()l.show_linked_list()以上就是本文的全部内容希望对大家的学习有所帮助也希望大家多多支持聚米学院。
