Python数据结构-01

Python链表及其实例化

#链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序；每个结构包含元素和指向下一个元素的指针。
#最后一个单元的指针指向NULL。为了方便链表的删除与插入操作，可以为链表添加一个表头

#1.单向链表的实现
##1.1 Node实现
  ##每个Node分为两个部分，一部分含有链表的元素，可以称为数据域；另一部分为指针，指向下一个Node
class Node():
    __slots__ = ['_item', '_next'] #限定Node实例的属性

    def __init__(self, item):
        self._item = item
        self._next = None   #None的指针部分默认指向None

    #获得当前元素
    def getItem(self):
        return self._item

    #获得当前Node指针
    def getNext(self):
        return self._next

    #设置当前元素
    def setItem(self,newitem):
        self._item = newitem

    #设置当前Node指针
    def setNext(self,newnext):
        self._next = newnext


##1.2 SinglelinkedList的实现
class SingleLinkedList():
    def __init__(self):
        self._head = None  #初始化链表为空表
        self._size = 0

##1.3 检测链表是否为空
    def isEmpty(self):
        return self._head == None

##1.4 add在链表前端添加元素
    def add(self, item):
        temp = Node(item)
        temp.setNext(self._head)
        self._head = temp

##1.5 append在链表尾部添加元素
    def append(self, item):
        temp = Node(item)
        if self.isEmpty():
            self._head = temp  #若为空表，将添加的元素设为第一个元素
        else:
            current = self._head
            while current.getNext() != None:
                current = current.getNext() #遍历链表
            current.setNext(temp)  #此时current为链表最后的元素

##1.6 search检索元素是否在链表中
    def search(self, item):
        current = self._head
        founditem = False
        while current != None and not founditem:
            if current.getItem() ==item:
                founditem = True
            else:
                current = current.getNext()
        return founditem

##1.7 index索引 元素 在链表中的位置
    def index(self, item):
        current = self._head
        count = 0
        found = None
        while current != None and not found:
            count += 1
            if current.getItem() == item:
                found = True
            else:
                current = current.getNext()
        if found:
            return count
        else:
            raise  (ValueError, '%s is not in linkedlist' % item)

##1.8 remove删除链表中的某项元素    删除操作可以通过修改一个指针来实现！
    def remove(self,item):
        current = self._head #代表当前指针
        pre = None # 前一个元素指针
        while current != None: # 1.链表中存在元素 2. 挨个查找 直到找到最后一个元素
            if current.getItem() == item: #即头指针指向的元素即为要删除的元素
                # self._head 和 pre.setNext的区别而已  以下引用来区分pre是不是none
                if not pre: #pre=None成立执行 免得出现None.setNext() 这种错误
                    self._head = current.getNext()  #重新赋值head
                else:
                    pre.setNext(current.getNext())  #设置指针 pre指向的元素为下一个
                break
            else: #没有找到要删除元素 继续往下走
                pre = current
                current = current.getNext #指针后移

##1.9 链表中插入元素
    def insert(self, pos, item):
        if pos <= 1:
            self.add(item)

        elif pos > self.get_length():
            self.append(item)
        else: #在中间插入
            temp = Node(item)
            count = 1
            pre = None
            current = self._head
            while count < pos:
                count += 1
                pre = current
                current = current.getNext()
            pre.setNext(temp)
            temp.setNext(current)

##2.0 获得链表长度

    def get_length(self):
        """
        获取链表长度
        :return: int
        """
        current_node = self._head
        if current_node:
            i = 1
            while current_node.getNext():
                current_node = current_node.getNext()
                i += 1
            return i
        else:
            return 0

#2.1 打印链表
    def print_linkedList(self):
        if self.isEmpty():
            print('LinkedList\'s length is 0!')
        else:
            node = self._head  #?
            print("Head --> ", node._item, end='')
            while node._next:  #node._next  和node.getNext()都可以
                node = node._next
                print('-->', node._item, end='')
            print('-->None. LinkedList node finished')

##2.2 更新node
    def update(self, value, index):
        """
        为链表中某个位置的节点修改值
        :param value: 要修改的值
        :param index: 位置索引
        :return: None
        """
        if type(index) is int:
            if index > self.get_length():
                #所以超出范围直接提示并退出
                print('Index is out of range')
                return
            else:
                this_node = Node(item=value)
                if index == 0:
                    this_node._next = self._head._next
                    self._head = this_node
                else:
                    current_node = self._head
                    while index - 1:
                        current_node = current_node._next
                        index -= 1
                    this_node._next = current_node._next._next
                    current_node._next = this_node
                    return
        else:
            print('Index value is not int')
            return



#单链表实例化 实现操作
#实例化单链表
sigleLinkList = SingleLinkedList()

#前端添加元素
sigleLinkList.add('front')
#末尾添加元素
sigleLinkList.append('abc')
#插入元素
sigleLinkList.insert(3,'def')
#打印链表长度
print(sigleLinkList.get_length())
#打印整个链表
sigleLinkList.print_linkedList()
#索引某个元素并打印出来
index = sigleLinkList.index('abc')
print(index)
#链表是否为空
print(sigleLinkList.isEmpty())
#更新链表元素
sigleLinkList.update('hahah', 2)
#更新后打印链表看看
sigleLinkList.print_linkedList()
#移除元素
sigleLinkList.remove('front')
#移除元素后打印看看
sigleLinkList.print_linkedList()