Commitc59d1df

shengshijun

committed

1, 修改双向链表中的bug.

2, 修改readme,制定下一步计划.

1 parent09420aa commitc59d1dfCopy full SHA for c59d1df

File tree

2 files changed

+58

-34

lines changed

README.md
src/list
- linked_list.py

2 files changed

+58

-34

lines changed

`‎README.md`

Lines changed: 9 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -4,7 +4,6 @@ algorithm`
`4`	`4`	`在阅读算法导论的时候。我用Python写的一些算法，这些算法大部分使用list来作为底层存储数据的结构。但是python的list用的是链表实现，因此有些操作性能不高。`
`5`	`5`
`6`	`6`	`#算法`
`7`		`--------------`
`8`	`7`	`##排序算法：sort文件夹下面`
`9`	`8`	`1. 冒泡排序`
`10`	`9`	`2. 插入排序`
`@@ -91,5 +90,14 @@ algorithm`
`91`	`90`	`3. Set`
`92`	`91`
`93`	`92`
	`93`	`+未来计划`
	`94`	`+=====================`
	`95`	`+#在学习redis源码的过程中修改各个数据结构的实现,目的是使用更加精细的规则去提高数据结构的性能`
	`96`	`+#添加更多注释并且格式化代码,注释中注重于设计的思考`
	`97`	`+#添加算法导论中其他高级的数据结构`
	`98`	`+#计划完成一些在线的题库`
	`99`	`+`
	`100`	`+`
	`101`	`+`
`94`	`102`
`95`	`103`

`‎src/list/linked_list.py`

Lines changed: 49 additions & 33 deletions

Original file line number	Diff line number	Diff line change
`@@ -2,7 +2,8 @@`
`2`	`2`	`# -- coding:utf-8 --`
`3`	`3`
`4`	`4`	`"""`
`5`		`-实现一个带哨兵的双向循环链表。一个哨兵是一个空对象，在双向链表实现中简化了改变链接的时候需要判断None的情况。`
	`5`	`+实现一个带哨兵的双向循环链表。一个哨兵是一个空对象`
	`6`	`+在双向链表实现中简化了改变链接的时候需要判断None的情况。`
`6`	`7`	`实现这个链表的过程时刻记得更新插入和删除节点的前后节点的指针`
`7`	`8`	`"""`
`8`	`9`	`from__builtin__importobject`
`@@ -12,87 +13,92 @@ class LinkedList(object):`
`12`	`13`	`classNode(object):`
`13`	`14`	`"""docstring for LinkedList.Node"""`
`14`	`15`
`15`		`-def__init__(self,key,prev,next):`
	`16`	`+def__init__(self,value,prev,next_node):`
`16`	`17`	`super(LinkedList.Node,self).__init__()`
`17`		`-self.key=key`
	`18`	`+self.value=value`
`18`	`19`	`self.prev=prev`
`19`		`-self.next=next`
	`20`	`+self.next_node=next_node`
`20`	`21`
`21`	`22`	`def__str__(self):`
`22`		`-returnstr(self.key)`
	`23`	`+returnstr(self.value)`
`23`	`24`
`24`	`25`	`def__init__(self,*arg):`
	`26`	`+"""`
	`27`	`+ 创建一个链表`
	`28`	`+ :param arg: 可变参数,是列表的初始元素`
	`29`	`+ :return:`
	`30`	`+ """`
`25`	`31`	`super(LinkedList,self).__init__()`
	`32`	`+# dump对象的prev指针始终指向列表的尾巴`
	`33`	`+# 而列表的最后一个元素的next指针则始终指向列表开头,整个列表就是一个环`
`26`	`34`	`self.__dump=LinkedList.Node(None,None,None)`
`27`	`35`	`self.__dump.prev=self.__dump`
`28`		`-self.__dump.next=self.__dump`
	`36`	`+self.__dump.next_node=self.__dump`
`29`	`37`	`self.__length=0`
`30`		`-forkeyinarg:`
`31`		`-self.append(key)`
	`38`	`+forvalueinarg:`
	`39`	`+self.append(value)`
`32`	`40`
`33`	`41`	`definsert(self,index,value):`
`34`	`42`	`ifindex>self.__length:`
`35`	`43`	`raiseIndexError("can not insert beyond the list")`
	`44`	`+`
`36`	`45`	`cur_pos=0`
`37`	`46`	`cur_node=self.__dump`
`38`	`47`	`whilecur_pos<index:`
`39`		`-cur_node=cur_node.next`
	`48`	`+cur_node=cur_node.next_node`
`40`	`49`	`cur_pos+=1`
	`50`	`+`
`41`	`51`	`prev_node=cur_node.prev`
`42`	`52`	`node=LinkedList.Node(value,prev_node,cur_node)`
`43`	`53`	`cur_node.prev=node`
`44`		`-prev_node.next=node`
	`54`	`+prev_node.next_node=node`
`45`	`55`	`self.__length+=1`
`46`	`56`	`returnnode`
`47`	`57`
`48`	`58`	`defappend(self,value):`
`49`	`59`	`last_node=self.__dump.prev`
`50`	`60`	`node=LinkedList.Node(value,last_node,self.__dump)`
`51`	`61`	`# 现在结尾的节点指向新加的结尾点`
`52`		`-last_node.next=node`
	`62`	`+last_node.next_node=node`
`53`	`63`	`self.__dump.prev=node`
`54`	`64`	`self.__length+=1`
`55`		`-# 处理空链表的情况`
`56`		`-ifself.__dump.nextisself.__dump:`
`57`		`-self.__dump.next=node`
`58`	`65`	`returnnode`
`59`	`66`
`60`	`67`	`defprepend(self,value):`
`61`		`-node=LinkedList.Node(value,self.__dump,self.__dump.next)`
`62`		`-self.__dump.next=node`
`63`		`-self.__dump.next.prev=node`
`64`		`-# 处理空链表的情况`
`65`		`-ifself.__dump.previsself.__dump:`
`66`		`-self.__dump.prev=node`
	`68`	`+node=LinkedList.Node(value,self.__dump,self.__dump.next_node)`
	`69`	`+self.__dump.next_node.prev=node`
	`70`	`+self.__dump.next_node=node`
`67`	`71`	`self.__length+=1`
`68`	`72`	`returnnode`
`69`	`73`
`70`	`74`	`defsearch(self,value):`
`71`		`-cur_node=self.__dump.next`
`72`		`-whilecur_nodeisnotself.__dumpandcur_node.key!=value:`
`73`		`-cur_node=cur_node.next`
`74`		`-returncur_node.key`
	`75`	`+cur_node=self.__dump.next_node`
	`76`	`+whilecur_nodeisnotself.__dumpandcur_node.value!=value:`
	`77`	`+cur_node=cur_node.next_node`
	`78`	`+returncur_node.value`
`75`	`79`
`76`	`80`	`defdelete(self,value):`
`77`		`-cur_node=self.__dump.next`
`78`		`-whilecur_nodeisnotself.__dumpandcur_node.key!=value:`
`79`		`-cur_node=cur_node.next`
	`81`	`+cur_node=self.__dump.next_node`
	`82`	`+whilecur_nodeisnotself.__dumpandcur_node.value!=value:`
	`83`	`+cur_node=cur_node.next_node`
	`84`	`+`
`80`	`85`	`# 如果不是空链表，那么就是查找到了相应的元素`
`81`	`86`	`ifcur_nodeisnotself.__dump:`
`82`		`-cur_node.prev.next=cur_node.next`
`83`		`-cur_node.next.prev=cur_node.prev`
	`87`	`+cur_node.prev.next_node=cur_node.next_node`
	`88`	`+cur_node.next_node.prev=cur_node.prev`
	`89`	`+self.__length-=1`
`84`	`90`
`85`		`-returncur_node.key`
	`91`	`+returncur_node.value`
`86`	`92`
`87`	`93`	`def__len__(self):`
`88`	`94`	`returnself.__length`
`89`	`95`
`90`	`96`	`def__str__(self):`
`91`		`-cur_node=self.__dump.next`
	`97`	`+cur_node=self.__dump.next_node`
`92`	`98`	`li= []`
`93`	`99`	`whilecur_nodeisnotself.__dump:`
`94`	`100`	`li.append(str(cur_node))`
`95`		`-cur_node=cur_node.next`
	`101`	`+cur_node=cur_node.next_node`
`96`	`102`	`return'['+", ".join(li)+']'`
`97`	`103`
`98`	`104`
`@@ -103,10 +109,20 @@ def main():`
`103`	`109`	`li.delete(5050)`
`104`	`110`	`printli`
`105`	`111`	`li=LinkedList()`
`106`		`-forxinxrange(1,10):`
	`112`	`+forxinrange(1,10):`
`107`	`113`	`li.insert(0,x)`
`108`	`114`	`printli`
`109`	`115`
	`116`	`+li=LinkedList()`
	`117`	`+forxinrange(1,10):`
	`118`	`+li.append(x)`
	`119`	`+printli`
	`120`	`+`
	`121`	`+li=LinkedList()`
	`122`	`+forxinrange(1,10):`
	`123`	`+li.prepend(x)`
	`124`	`+printli`
	`125`	`+`
`110`	`126`
`111`	`127`	`if__name__=='__main__':`
`112`	`128`	`main()`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commitc59d1df

File tree

2 files changed

2 files changed

`‎README.md`

`‎src/list/linked_list.py`

0 commit comments