python算法与数据结构-循环链表(41)

喜欢ヅ旅行 2023-10-06 12:41 16阅读 0赞

**阅读目录**

*  [一、循环链表的介绍][Link 1]
 *  [二、循环链表基本操作的python代码实现][python]
 *  [三、循环链表基本操作的C语言实现][C]

#### 一、循环链表的介绍 ####

上一篇我们已经讲过单链表，本篇给大家讲解循单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点，其基本操作和单链表思路一样。

![format_png][]

常用的操作有

1.  创建节点
2.  创建循环链表
3.  判断是否为空
4.  头部插入
5.  循环链表的遍历
6.  尾部插入
7.  获取链表长度
8.  根据下标插入一个节点
9.  根据下标删除一个节点
10. 查找是否包含一个节点，并返回其在链表中的位置
11. 根据下标找节点
12. 根据下标修改节点的值
13. 对链表排序

#### 二、循环链表基本操作的python代码实现 ####

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

class Node():
        def __init__(self,num):
            self.element = num
            self.next = None
            
    class CricleLinkList(object):
        def __init__(self):
            self.head = None
            self.length = 0
    
        # 1、判断是否为空
        def is_empty(self):
            if self.head == None:
                return True
            else:
                return False
        
        # 2、头部插入
        def add(self, num):
            # 创建要插入的节点
            node = Node(num)
            if self.is_empty()==True:
                # 如果为空直接插入
                self.head = node
                # 并且把自身的next执行头结点
                node.next = self.head
            else:
                # 将原来的头结点作为插入节点的next
                node.next = self.head
                current = self.head
                # 循坏找到最后一个节点
                while current.next != self.head:
                    current = current.next
                # 将最后一个节点的next执行插入节点
                current.next = node
                # 将插入的节点设置为头结点，完成循坏闭合
                self.head = node
            # 每次添加完成一次，长度加1
            self.length += 1
    
        # 3、遍历
        def travel(self):
            if self.is_empty() == True:
                print("你要遍历的循环链表为空")
                return
            
            print("你要遍历的循环链表元素有：", end=" ")
            current = self.head
            # 先把第一个元素打印一下
            print("%d " % current.element, end=" ")
            # 打印只有一个元素的时候，第一个元素打印不出来，所以先把第一个打印出来
            while current.next != self.head:
                
                current = current.next
                print("%d " % current.element, end=" ")
            print("")
                    
        # 4、尾部插入
        def append(self,num):
            node = Node(num)
            if self.is_empty() == True:
                self.add(num)
            else:
                current = self.head
                while current.next != self.head:
                    current = current.next
                node.next = self.head
                current.next = node
            # 每次添加完成一次，长度加1
            self.length += 1
                
        # 5、指定位置插入
        def insertAtIndex(self,num,index):
            if index<=0 or index>self.length+1:
                print("你要插入的位置不对，请重新选择位置")
                return
            elif self.is_empty() == True:
                self.add(num)
            elif index==1:
                self.add(num)
            elif index == self.length+1:
                self.append(num)
            else:
                current = self.head
                for i in range(index-2):
                    current = current.next
                node = Node(num)
                node.next = current.next
                current.next = node
                
            # 每次添加完成一次，长度加1
            self.length += 1
    
        # 6、按索引删除
        def deleteByIndex(self,index):
            
            if index<=0 or index>self.length:
                print("你要插入的位置不对，请重新选择位置")
                return
            elif self.is_empty() == True:
                print("你要删除的链表为空")
                return
            elif index == 1:
                current = self.head
                for i in range(1,self.length):
                    current = current.next
                current.next = self.head.next
                self.head = self.head.next
            else:
                current = self.head
                for i in range(index-2):
                    current = current.next
                current.next = current.next.next
            # 每次删完长度减1
            self.length -= 1
    
        # 7、查找是否包含,并返回位置
        def isContain(self,num):
            if self.is_empty() == True:
                print("你要查询的链表为空")
                return
            else:
                current = self.head
                for i in range(self.length):
                    if current.element == num:
                        print("你要找到元素在第%d个节点"%(i+1))
                        return i+1
                    current = current.next
                print("没有找到你要的元素")
            return -1
        
        # 8、根据下标找节点
        def searchNodeByIndex(self,index):
            if index<=0 or index>self.length:
                print("你要查询的位置不对，请重新选择位置")
                return
            elif self.is_empty() == True:
                print("你要查询的链表为空")
            else:
                current = self.head
                for i in range(1,index):
                    current = current.next
                print("你要查找%d位置上的节点的值是%d"%(index,current.element))
                
        # 9、根据下标修改节点的值
        def modifyByIndex(self,index,num):
            if index <= 0 or index > self.length:
                print("你要查询的位置不对，请重新选择位置")
                return
            elif self.is_empty() == True:
                print("你要修改的链表为空")
            else:
                current = self.head
                for i in range(1, index):
                    current = current.next
                current.element = num
                
        # 10、排序
        def sort(self):
            if self.length<=0:
                return
            for i in (0,self.length-1):
                current = self.head
                for j in range(0,self.length-i-1):
                    if current.element>current.next.element:
                        temp = current.element
                        current.element = current.next.element
                        current.next.element = temp
                    current = current.next
            
                
    if __name__ == '__main__':
        
        print("======1、创建循环链表 ======")
        cricle_link_list = CricleLinkList()
    
        print("======2、验证是否为空 ======")
        empty = cricle_link_list.is_empty()
        if empty == True:
            print("你查询的链表为空")
        else:
            print("你查询的链表不为空")
        
        print("\n======3、验证头插和遍历 ======")
        cricle_link_list.add(1)
        cricle_link_list.travel()
        
        print("\n======4、继续验证头插和遍历 ======")
        cricle_link_list.add(2)
        cricle_link_list.travel()
        
        print("\n======5、验证尾插 ======")
        cricle_link_list.append(3)
        cricle_link_list.travel()
        
        print("\n======6、验证按位置插入 ======")
        cricle_link_list.insertAtIndex(0,2)
        cricle_link_list.travel()
        
        print("\n======7、验证按位置删除 ======")
        cricle_link_list.deleteByIndex(5)
        cricle_link_list.travel()
        
        print("\n======8、验证查找是否包含元素 ======")
        cricle_link_list.isContain(2)
        
        print("\n======9、验证根据下标查找元素 ======")
        cricle_link_list.searchNodeByIndex(3)
        
        print("\n======10、验证修改 ======")
        cricle_link_list.modifyByIndex(3,5)
        cricle_link_list.travel()
        
        print("\n======11、验证排序 ======")
        cricle_link_list.sort()
        cricle_link_list.travel()

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

运行结果为：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

======1、创建循环链表 ======
    ======2、验证是否为空 ======
    你查询的链表为空
    
    ======3、验证头插和遍历 ======
    你要遍历的循环链表元素有： 1  
    
    ======4、继续验证头插和遍历 ======
    你要遍历的循环链表元素有： 2  1  
    
    ======5、验证尾插 ======
    你要遍历的循环链表元素有： 2  1  3  
    
    ======6、验证按位置插入 ======
    你要遍历的循环链表元素有： 2  0  1  3  
    
    ======7、验证按位置删除 ======
    你要插入的位置不对，请重新选择位置
    你要遍历的循环链表元素有： 2  0  1  3  
    
    ======8、验证查找是否包含元素 ======
    你要找到元素在第1个节点
    
    ======9、验证根据下标查找元素 ======
    你要查找3位置上的节点的值是1
    
    ======10、验证修改 ======
    你要遍历的循环链表元素有： 2  0  5  3  
    
    ======11、验证排序 ======
    你要遍历的循环链表元素有： 0  2  3  5

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

#### 三、循环链表基本操作的C语言实现 ####

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

//
    //  main.m
    //  循环链表
    //
    //  Created by 侯垒 on 2019/6/27.
    //  Copyright © 2019 可爱的侯老师. All rights reserved.
    //
    
    #include <stdio.h>
    // 创建节点结构体
    typedef struct N
    {
        int element;
        struct N *next;
    }Node;
    
    // 1、创建节点
    Node *createNode(int num)
    {
        Node *node = (Node *)malloc(sizeof(Node));
        node->element = num;
        node->next = NULL;
        return node;
    }
    
    // 2、创建循环链表
    Node *createCricleLinkList(int num)
    {
        Node *head = createNode(num);
        head->next = head;
        return head;
    }
    
    // 3、判断是否为空
    int is_empty(Node *head)
    {
        if (head == NULL)
        {
            return 1;
        }
        return 0;
    }
    
    //4、头部插入
    Node *add(Node *head,int num)
    {
        Node* node = createNode(num);
        Node *current = head;
        if (is_empty(head)==1)
        {
            head = node;
            node->next = head;
        }
        else
        {
            node->next = head;
            while (current->next != head)
            {
                current = current->next;
            }
            current->next = node;
            head = node;
        }
        return head;
    }
    
    // 5、遍历
    void travel(Node *head)
    {
        if (is_empty(head) == 1)
        {
            printf("你遍历的链表为空\n");
        }
        else
        {
            printf("\n你要遍历的循环链表元素有：");
            Node *current = head;
            printf("%d ",current->element);
            while (current->next != head)
            {
                current = current->next;
                printf("%d ",current->element);
            }
            printf("\n");
        }
    }
    
    // 5、尾部插入
    Node *append(Node *head,int num)
    {
        Node *node = createNode(num);
        if (is_empty(head)==1)
        {
            add(head, num);
        }
        else
        {
            Node *current = head;
            while (current->next != head)
            {
                current = current->next;
            }
            node->next = head;
            current->next = node;
        }
        return head;
    }
    
    // 6、获取链表长度
    int getLength(Node *head)
    {
        int count = 1;
        Node *current = head;
        if (is_empty(head)==1)
        {
            return 0;
        }
        else
        {
            while (current->next !=head)
            {
                current = current->next;
                count++;
            }
            return count;
        }
    }
    
    // 7、根据下标插入节点
    Node * insertByIndex(Node *head,int num,int index)
    {
        int len = getLength(head);
        if (index<=0||index>len+1)
        {
            printf("你要插入的位置不对，请重新选择位置");
        }
        else if (index == 1)
        {
            head = add(head, num);
        }
        else
        {
            Node *current = head;
            for (int i=1; i<index-1; i++)
            {
                current = current->next;
            }
            Node *node = createNode(num);
            node->next = current->next;
            current->next = node;
        }
        return head;
    }
    
    // 8、根据下标删除
    Node *deleteByIndex(Node *head,int index)
    {
        int len = getLength(head);
        if (index<=0||index>len)
        {
            printf("\n你要删除的位置不对，请重新选择位置");
        }
        else if (index == 1)
        {
            Node *current = head;
            for (int i=1; i<len; i++)
            {
                current = current->next;
            }
            current->next = head->next;
            head = head->next;
        }
        else
        {
            Node *current = head;
            for (int i=0; i<index-2; i++)
            {
                current = current->next;
            }
            current->next = current->next->next;
        }
        return head;
    }
    
    // 9、查找是否包含，并返回位置
    int isContain(Node *head,int num)
    {
        int len = getLength(head);
        Node *current = head;
        for (int i= 0; i<len; i++)
        {
            if (current->element == num)
            {
                return i+1;
            }
            current=current->next;
        }
        return 0;
    }
    
    // 10、根据下标找节点
    Node *searchNodeByIndex(Node *head,int index)
    {
        Node *current = head;
        int len = getLength(head);
        if (index<=0||index>len)
        {
            printf("\n你要查询的位置不对，请重新选择位置");
        }
        else
        {
            
            for (int i =1 ; i<index; i++)
            {
                current = current->next;
            }
            printf("\n你要查找的%d位置上的值为%d",index,current->element);
        }
        return current;
    }
    
    // 11、根据下标修改节点的值
    void modefyByIndex(Node *head,int index,int num)
    {
        Node *current = head;
        int len = getLength(head);
        if (index<=0||index>len)
        {
            printf("\n你要修改的位置不对，请重新选择位置");
        }
        else
        {
            for (int i =1 ; i<index; i++)
            {
                current = current->next;
            }
            current->element = num;
        }
    }
    
    // 12、排序
    void sort(Node *head)
    {
        int len = getLength(head);
        if (len<=0)
        {
            return;
        }
        for (int i = 0; i<len-1; i++)
        {
            Node *current = head;
            for (int j=0; j<len-i-1; j++)
            {
                if (current->element >current->next->element)
                {
                    int temp = current->element;
                    current->element = current->next->element;
                    current->next->element = temp;
                }
                current = current->next;
            }
        }
    }
    
    int main(int argc, const char * argv[])
    {
        printf("=====1、创建循环链表=====");
        Node *head = createCricleLinkList(1);
        
        printf("\n=====2、验证是否为空=====\n");
        int empty = is_empty(head);
        if (empty == 1)
        {
            printf("你创建的循环链表为空");
        }
        else
        {
            printf("你创建的循环链表不为空");
        }
        
        printf("\n=====3、验证头插和遍历=====");
        travel(head);
        head =  add(head, 0);
        travel(head);
        
        printf("\n=====4、验证尾插=====");
        head = append(head, 2);
        travel(head);
        
        printf("\n=====5、验证根据下表插入=====");
        head = insertByIndex(head, 3, 2);
        travel(head);
        
        printf("\n=====6、验证根据下表删除=====");
        head = deleteByIndex(head, 3);
        travel(head);
        
        printf("\n=====7、验证是否包含=====");
        int num = 3;
        int index = isContain(head, num);
        if (index != 0)
        {
            printf("\n你查找的数据%d在第%d个位置",num,index);
        }
        else
        {
            printf("\n没有找到你要的数据\n");
        }
        
        printf("\n=====8、验证根据下标找节点=====");
        searchNodeByIndex(head, 2);
        printf("\n=====9、验证根据下标修改节点值=====");
        modefyByIndex(head,2,4);
        travel(head);
        
        printf("\n=====10、验证排序=====");
        sort(head);
        travel(head);
        
        return 0;
    }

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

运行结果为：

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

=====1、创建循环链表=====
    =====2、验证是否为空=====
    你创建的循环链表不为空
    =====3、验证头插和遍历=====
    你要遍历的循环链表元素有：1 
    
    你要遍历的循环链表元素有：0 1 
    
    =====4、验证尾插=====
    你要遍历的循环链表元素有：0 1 2 
    
    =====5、验证根据下表插入=====
    你要遍历的循环链表元素有：0 3 1 2 
    
    =====6、验证根据下表删除=====
    你要遍历的循环链表元素有：0 3 2 
    
    =====7、验证是否包含=====
    你查找的数据3在第2个位置
    =====8、验证根据下标找节点=====
    你要查找的2位置上的值为3
    =====9、验证根据下标修改节点值=====
    你要遍历的循环链表元素有：0 4 2 
    
    =====10、验证排序=====
    你要遍历的循环链表元素有：0 2 4

![复制代码][aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]

--------------------

侯哥语录：我曾经是一个职业教育者，现在是一个自由开发者。我希望我的分享可以和更多人一起进步。分享一段我喜欢的话给大家："我所理解的自由不是想干什么就干什么，而是想不干什么就不干什么。当你还没有能力说不得时候，就努力让自己变得强大，拥有说不得权利。"

来源:[https://www.cnblogs.com/Se7eN-HOU/p/11099974.html][https_www.cnblogs.com_Se7eN-HOU_p_11099974.html]

[Link 1]: https://www.cnblogs.com/Se7eN-HOU/p/11099974.html#_label0
[python]: https://www.cnblogs.com/Se7eN-HOU/p/11099974.html#_label1
[C]: https://www.cnblogs.com/Se7eN-HOU/p/11099974.html#_label2
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvNzUxNzU0LzIwMTkwNi83NTE3NTQtMjAxOTA2MjcxNTIxNTE4NzQtMTAwNDUxMjAwNy5wbmc?x-oss-process=image/format,png
[aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jb21tb24uY25ibG9ncy5jb20vaW1hZ2VzL2NvcHljb2RlLmdpZg
[https_www.cnblogs.com_Se7eN-HOU_p_11099974.html]: https://www.cnblogs.com/Se7eN-HOU/p/11099974.html

发表评论取消回复

表情：

评论列表（有 0 条评论，16人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构与算法】双链表&循环链表&静态链表

单链表：各个结点在内存中星罗棋布、散落天涯静态链表：分配一整片连续的内存空间，各个结点集中安置，0号结点充当 “头结点”，下一个结点的数组下标（也称为游标）充当 “指针”...

深碍√TFBOYSˉ_/ 2024年04月26日 02:19/ 0 赞/ 98 阅读

相关 python算法与数据结构-循环链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIx

妖狐艹你老母/ 2023年10月06日 12:41/ 0 赞/ 19 阅读

相关 python算法与数据结构-循环链表(41)

阅读目录 [一、循环链表的介绍][Link 1] [二、循环链表基本操作的python代码实现][python] [三、循环链表基本操作的C语言实现][C]

喜欢ヅ旅行/ 2023年10月06日 12:41/ 0 赞/ 17 阅读

相关 python算法与数据结构-单链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIx

小灰灰/ 2023年10月06日 12:29/ 0 赞/ 69 阅读

相关 python算法与数据结构-单链表

阅读目录 [一、链表][Link 1] [二、单链表介绍][Link 2] [三、单链表结构][Link 3] [四、单链表的常用操作图解][Link

╰半橙微兮°/ 2023年10月06日 12:29/ 0 赞/ 64 阅读

相关 python算法与数据结构-双向链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIx

た入场券/ 2023年10月06日 01:25/ 0 赞/ 55 阅读

相关 python算法与数据结构-双向链表

阅读目录 [一、双向链表的介绍][Link 1] [二、双向链表插入和删除的图解][Link 2] [三、双向链表的python代码实现][python]

待我称王封你为后i/ 2023年10月06日 01:24/ 0 赞/ 59 阅读

相关《数据结构》—— 循环链表与静态链表

循环链表一、循环单链表 1.1 初始化循环单链表二、循环双链表 2.1 循环双链表初始化思想

小鱼儿/ 2022年09月11日 03:28/ 0 赞/ 229 阅读

相关 Python数据结构与算法-线性表（链表）

1.单向链表：（10/31增加根据索引删除结点，删除头结点额尾部结点） 1.单向链表： class SingleNode(): def _

清疚/ 2022年05月14日 07:46/ 0 赞/ 328 阅读

相关数据结构与算法（008）：线性表-循环链表

循环链表循环，顾名思义就是：绕。打个比方，就是从前山上有座庙，庙里有个老和尚和一个小和尚，有一天老和尚对小和尚说“从前山上有座庙，庙里有个老和尚和一个小和尚，有一天

ゞ浴缸里的玫瑰/ 2022年02月04日 00:21/ 0 赞/ 271 阅读