单向循环链表

单链表的一个变形是单向循环链表, 链表的最后一个节点的next域不再为None, 而是指向链表的头节点.

单向循环链表如图所示:

单向循环链表

同样单向循环链表也是要使用python来对它的基本功能进行一个封装. 总体大致的功能如下:

• is_empty() 判断链表是否为空
• length() 返回链表的长度
• travel() 遍历
• add(item) 在头部添加一个节点
• append(item) 在尾部添加一个节点
• insert(pos, item) 在指定位置pos添加节点
• remove(item) 删除一个节点
• search(item) 查找节点是否存在

注意: 区别单链表的操作如图:(图为单链表操作)

单链表的操作

单向循环链表的操作多了一个尾部指向头部的链接.

python实现其基本功能

事先定义一个节点, 包含数据元素的本身和它 的next区域的指向None.

class Node(object):     '''节点    '''    def __init__(self, item):        self.item = item        self.next = None

结果如下(还是那句话, 写完一个功能调试一下):

node节点运行调试图

总体功能布局

同样需要事先初始化节点, 其实就是对之前的单链表的功能进行直接的更改, 可以直接把之前的代码复制过来,看看是否可以满足单向循环链表的的功能, 如果可以直接过去就好, 如果不行重新修改. (注意和之前单链表的区别, 循环的终止点, 设置循环的终止, 到哪里才算是一次循环的完成)

class SinCycLinkedlist(object):    '''    单向循环链表    '''    def __init__(self):        self.__head = None    def is_empty(self):        '''        判断链表是否为空        '''    def length(self):        '''        返回链表的长度        '''    def travel(self):        '''        遍历链表        '''    def add(self, item):        '''        头部添加节点        '''    def append(self, item):        '''        尾部添加节点        '''    def insert(self, pos, item):        '''        指定位置添加节点        '''    def remove(self, item):        '''        删除节点        '''    def search(self, item):        '''        查找节点是否存在        '''if __name__ == "__main__":    ll = SinCycLinkedlist()

基本功能大致如上.

判断链表是否为空

这功能和之前的单链表是一样的, 只需要判断头节点是否为空, 直接返回True or False就好了.

def is_empty(self):    '''    判断链表是否为空    '''    return self.__head == None

返回链表长度

通过循环遍历来计算元素的个数, 没遍历一个count就加1, 但是这里的循环的终止条件, 要变, 不能使用之前的. 终止条件改为 cur.next != self.__head 直接判断最后一个节点的下一个区域是否指向头结点, 如果是结束一次循环, 如果不是继续往后遍历.代码如下:

def length(self):    '''    返回链表的长度    '''    if self.is_empty():        return 0    count = 1    cur = self.__head    while cur.next != self.__head:        count += 1        cur = cur.next    return count

遍历链表打印里面的元素

同样是和之前的单链表的是一样的, 只是循环的条件得改掉, 由于是头尾相连的, 导致之前的cur != None 在非空链表中不可以使用每个元素都是有值的, 没有指向None的元素. 每个元素的next区域都有指向, 每个元素cur.next != None也是不可以使用的.所以还是改成cru.next != self.__head以最后一个节点和头节点作为比较.代码如下:

def travel(self):    '''    遍历链表    '''    if self.is_empty():        return    cur = self.__head    print (cur.item) # 头节点没有参与循环, 要直接打印出来    while cur.next != self.__head:        cur = cur.next        print (cur.item)    print ("") # 换行

头部添加节点

单向循环链表头部添加节点

先定义要添加的节点node, 判断是否为空, 如果是空的话, 直接按照头结点的添加, 头节点指向node, node的next区域指向头节点.如果不是, 添加的节点指向__head, 移到链表尾部, 将结尾部节点的next指向node. 如代码:

def add(self, item):    '''    头部添加节点    '''def travel(self):    '''    遍历链表    '''    if self.is_empty():        return    cur = self.__next    print (cur.item) # 头节点没有参与循环, 要直接打印出来    while cur.next != self.__head:        cur = cur.next        print (cur.item)    print ("") # 换行def travel(self):    '''    遍历链表    '''    if self.is_empty():        return    cur = self.__next    print (cur.item) # 头节点没有参与循环, 要直接打印出来    while cur.next != self.__head:        cur = cur.next        print (cur.item)    print ("") # 换行    node = Node(item)    if self.is_empty():        self.__head = node        node.next = self.__head    else:        # 添加的节点指向__head        node.next = self.__head        # 移到链表的尾部, 将尾部节点的next指向node        cur = self.__head        while cur.next != self.__head:            cur = cur.next        cur.next = node        # __head 指向添加node的        self.__head = node

链表尾部的添加

和之前的单链表差不多, 判断是否是空链表, 如果是头节点指向node, node的next区域指向self.__head, 如果不是, 移动到链表的尾部, 注意循环结束的条件cur.next != self.__head , 找到尾节点之后将尾节点指向node, 再将node指向头节点__head, 注意指向的先后顺序, 先是cur.next指向再是node的next指向, 注意区分先后顺序, 每种指向的区别, 先后的影响. 代码如下:

def append(self, item):    '''    尾部添加节点    '''    node = Node(item)    if self.is_empty():        self.__head = node        node.next = self.__head    else:        # 移动到链表的尾部        cur = self.__head        while cur.next != self.__head:            cur = cur.next        # 将尾节点指向node        cur.next = node        # 将node的指向头结点__head        node.next = self.__head

区别单链表的尾部添加节点, 区别注意尾部的指向问题. 单链表尾部如图所示:

单链表尾部添加, 注意区别

指定位置添加节点

基本思路和前面的单链表一样.先判断插入的位置. 如果是头部插入直接调用self.add()函数就可以 ( 这里使用pos<=0来表示头部的插入, 传递进来的参数小于0了, 就认为他是要在头部进行插入 ) , 如果是尾部直接调用前面的self.append()函数就好 ( 使用pos > self.length - 1 来表示在尾部插入传递进来的参数, 要求的位置超过了链表应有的长度, 就认为直接在尾部进行插入 ) . 注意pos参数传递过来, 判断插入的位置的时候注意一定要区别和链表本身的长度之间的区别, 是加一还是减一. 指定其他位置的插入, 使用count来计数, 如果count < pos - 1 接着向后移动就可以了 , 如果不满足条件了, 注意节点插入的先后顺序. 思考为什么是count < pos - 1 而不是正好等于或者加一. 详细代码如下:

def insert(self, pos, item):    '''    指定位置添加节点    '''    if pos <= 0:        self.add(item)    elif pos > (self.length() - 1):        self.append(item)    else:        node = Node(item)        cur = self.__head        count = 0        # 移动到指定位置的前一个位置        while count < (pos - 1):            count += 1            cur = cur.next        node.next = cur.next        cur.next = node

注意node的插入的先后顺序

删除一个节点

这里需要引入pre游标来辅助我们判断节点, 对节点进行删除.

判断链表是否为空, 如果是直接返回, 空链表不需要删除. 如果头结点的元素就是要查找的元素item, 进入分支判断, 如果链表不止一个节点, 先找到尾节点, 将尾节点的next指向第二个节点(注意这些节点之间next区域移动的先后顺序, 注意之间的区别). 如果链表只有一个节点该怎么办.

第一个节点不是要删除的, 先找到要删除的元素, 再通过区域的指向来进行删除. 代码如下:

def remove(self, item):    '''    删除节点    '''    # 若链表为空    if self.is_empty():        return    # 将cur 指向头节点    cur = self.__head    pre = None    # 若头节点就是要找的    if cur.item == item:        # 如果链表不止一个节点        if cur.next != self.__head:            # 先找到尾节点, 将尾节点的next指向第二个节点            while cur.next != self.__head:                cur = cur.next            # cur指向了尾节点            cur.next = self.__head.next            self.__head = self.__head.next        else:            # 链表只有一个节点            self.__head = None    else:        pre = self.__head        # 第一个节点不是要删除的        while cur.next != self.__head:            # 找到了要删除的元素            if cur.item == item:                # 删除                pre.next = cur.next                return            else:                pre = cur                cur = cur.next            # cur指向尾节点            if cur.item == item:                # 尾部删除                pre.next = cur.next

查找节点是否存在

这个功能和单链表中的差不多就是一个循环判断的条件不一样, 注意新的判断条件是cur的next区域是否等于头节点.详细代码如下:

def search(self, item):    '''    查找节点是否存在    '''    if self.is_empty():        return False    cur = self.__head    if cur.item == item:        return True    while cur.next != self.__head:        cur = cur.next        if cur.item == item:            return True    return False

最后功能测试如下:

if __name__ == "__main__":    ll = SinCycLinkedlist()    ll.add(1)    ll.add(2)    ll.append(3)    ll.insert(2,4)    ll.insert(4,5)    ll.insert(0,6)    print ("length:",ll.length())    ll.travel()    print (ll.search(3))    print (ll.search(7))    ll.remove(1)    print ("length:", ll.length())    ll.travel()

运行结果如下:

链表运行结果如图所示

上传代码之后, 缩进可能会有点小问题, 注意一定要注意缩进