python数据结构与算法 18 无序列表的实现

2014-03-23

无序列表的实现：链表

节点类

Listing 1

`classNode:`
`    def__init__(self,initdata):`
`        self.data= initdata`
`        self.next=None`
` `
`    defgetData(self):`
`        returnself.data`
` `
`    defgetNext(self):`
`        returnself.next`
` `
`    defsetData(self,newdata):`
`        self.data= newdata`
` `
`    defsetNext(self,newnext):`
`        self.next= newnext`

`>>> temp= Node(93)`
`>>> temp.getData()`
`93`

无序列表类

Listing 2

`classUnorderedList:`
` `
`    def__init__(self):`
`        self.head=None`

`>>> mylist= UnorderedList()`

Listing 3

`defisEmpty(self):`
`    returnself.head==None`

`>>> mylist.add(31)`
`>>> mylist.add(77)`
`>>> mylist.add(17)`
`>>> mylist.add(93)`
`>>> mylist.add(26)`
`>>> mylist.add(54)`

Listing 4

`defadd(self,item):`
`    temp = Node(item)`
`    temp.setNext(self.head)`
`    self.head= temp`

Listing 5

 `defsize(self):` ` current =self.head` ` count =0` ` while current !=None:` ` count = count +1` ` current = current.getNext()` ` ` ` return count`

Listing 6

 `defsearch(self,item):` ` current =self.head` ` found =False` ` while current !=Noneandnot found:` ` if current.getData()== item:` ` found =True` ` else:` ` current = current.getNext()` ` ` ` return found`

`>>> mylist.search(17)`
`True`

17在列表中，遍历过程只需到含17的节点，在这点上，found被置True，while的条件不成立，退出循环，返回found&#20540;。如图10所示

`defremove(self,item):`
`    current =self.head`
`    previous =None`
`    found =False`
`    whilenot found:`
`        if current.getData()== item:`
`            found =True`
`        else:`
`            previous = current`
`            current = current.getNext()`
` `
`    if previous ==None:`
`        self.head= current.getNext()`
`    else:`
`        previous.setNext(current.getNext())`

class Node:

def __init__(self, initdata):

self.data = initdata

self.next = None

def getData(self):

return self.data

def getNext(self):

return self.next

def setData(self, newdata):

self.data = newdata

def setNext(self, newnext):

self.next = newnext

classUnorderedList:

def __init__(self):

def isEmpty(self):

temp = Node(item)

def size(self):

count = 0

while current != None:

count = count &#43; 1

current = current.getNext()

return count

def search(self, item):

found = False

if current.getData() == item:

found = True

else:

current = current.getNext()

return found

def remove(self, item):

previous = None

found = False

if current.getData() == item:

found = True

else:

previous = current

current = current.getNext()

if previous == None:

else:

previous.setNext(current.getNext())

mylist =UnorderedList()

print(mylist.size())

print(mylist.search(93))

print(mylist.search(100))

print(mylist.search(100))

print(mylist.size())

mylist.remove(54)

print(mylist.size())

mylist.remove(93)

print(mylist.size())

mylist.remove(31)

print(mylist.size())

print(mylist.search(93))