精华内容
下载资源
问答
  • 单向循环链表一、基本介绍二、单向循环链表的使用三、Josephu(约瑟夫)问题1、问题分析2、代码实现 一、基本介绍   顾名思义,在内存中单向循环链表就是将单链表的最后一个...1、定义单向循环链表基本结构 class...

    一、基本介绍

      顾名思义,在内存中单向循环链表就是将单链表的最后一个节点的next再指向单链表的第一个节点,在逻辑结构上就是将原来的一条链变成首尾相接的一个圆环,从而实现单链表的一个循环。如下图(此处为无头节点的单向链表):
    单向循环链表内存结构
    单向循环链表逻辑结构图

    二、单向循环链表的使用

    1、定义单向循环链表基本结构

    class Node1 {
        //这里的变量用private修饰,所以下面需要定义get、set方法
        //和单链表相同,此处可以声明多个data
        private int data;
        private Node1 next;
    	//空参构造器
        public Node1() {
        }
    	//带参构造器
        public Node1(int data) {
            this.data = data;
        }
        public int getData() {
            return data;
        }
    
        public void setData(int data) {
            this.data = data;
        }
    
        public Node1 getNext() {
            return next;
        }
    
        public void setNext(Node1 next) {
            this.next = next;
        }
    }
    

    2、同样我们再定义一个类来添加增删改查基本操作(与普通单链表相似,但要让尾节点指向首节点)

    class CircleSingleLinkedList1 {
        //创建一个first节点
        private Node1 first;
    
        //添加节点,这里默认data唯一,不可重复添加
        public void addNode(Node1 node) {
            if (first == null) {
                first = node;
                first.setNext(first);
                return;
            }
            Node1 temp = first;
            boolean flag = false;
            while (true) {
                if (temp.getNext() == first) {
                    break;
                }
                if (node.getData() == temp.getData()) {
                    flag = true;
                    break;
                }
                temp = temp.getNext();
            }
            if (flag) {
                System.out.printf("节点%d已经存在,不可重复添加\n",node.getData());
            } else {
                temp.setNext(node);
                node.setNext(first);
            }
        }
    
        //按data的大小排序添加,这里默认data唯一,不可重复添加
        public void addNodeByOrder(Node1 node) {
            if (first == null) {
                first = node;
                first.setNext(first);
                return;
            }
            Node1 temp = first;
            boolean flag = false;
            while (true) {
                if (temp.getNext() == first) {
                    break;
                }
                if (temp.getNext().getData() > node.getData()) {
                    break;
                } else if (temp.getNext().getData() == node.getData()) {
                    flag = true;
                    break;
                }
                temp = temp.getNext();
            }
            if (flag) {
                System.out.printf("节点%d已经存在,不可重复添加\n",node.getData());
            } else {
                node.setNext(temp.getNext());
                temp.setNext(node);
            }
        }
    
        //删除节点
        public void deleteN(int no) {
            if (first == null) {
                System.out.println("链表为空");
                return;
            }
            Node1 temp = first;
            boolean flag = false;
    
            if (no == first.getData()) {
                while (true) {
                    if (temp.getNext() == first) {
                        break;
                    }
                    temp = temp.getNext();
                }
                first = first.getNext();
                temp.setNext(first);
            }
    
            while (true) {
                if (temp.getNext() == first) {
                    break;
                }
                if (no == temp.getNext().getData()) {
                    flag = true;
                    break;
                }
                temp = temp.getNext();
            }
            if (flag) {
                temp.setNext(temp.getNext().getNext());
            } else {
                System.out.println("未找到该节点");
            }
        }
    
        //修改链表
        public void update(Node1 node) {
            if (first == null) {
                System.out.println("链表为空");
                return;
            }
            Node1 temp = first;
            boolean flag = false;
            while (true) {
                if (temp.getNext() == first) {
                    break;
                }
                if (node.getData() == temp.getData()) {
                    flag = true;
                    break;
                }
                temp = temp.getNext();
            }
            if (flag) {
                temp.setData1(node.getData1());
            } else {
                System.out.println("未找到该节点");
            }
    
        }
    
        //遍历
        public void showNode() {
            if (first == null) {
                System.out.println("链表为空");
                return;
            }
            Node1 curNode = first;
            while (true) {
                System.out.printf("节点%d的data是%d\n", curNode.getData(),curNode.getData1());
                if (curNode.getNext() == first) {
                    break;
                }
                curNode = curNode.getNext();
            }
        }
    }
    

    3、写一个Demo来测试一下

    /**
     * @author dankejun
     * @create 2020-03-31 16:18
     */
    public class CircleSingleLinkedListExer {
        public static void main(String[] args) {
            CircleSingleLinkedList1 linkedList1 = new CircleSingleLinkedList1();
            Node1 node1 = new Node1(1, 10);
            Node1 node2 = new Node1(2, 20);
            Node1 node3 = new Node1(3, 30);
            Node1 node4 = new Node1(4, 40);
    //自定义顺序添加节点
    //        linkedList1.addNode(node1);
    //        linkedList1.addNode(node2);
    //        linkedList1.addNode(node3);
    //        linkedList1.addNode(node4);
    		//按data大小添加节点
            linkedList1.addNodeByOrder(node1);
            linkedList1.addNodeByOrder(node3);
            linkedList1.addNodeByOrder(node2);
            linkedList1.addNodeByOrder(node4);
            System.out.println("原来的链表为:");
            linkedList1.showNode();
            System.out.println();
    
    
            Node1 node5 = new Node1(3, 50);
            linkedList1.update(node5);
            System.out.println("修改后的链表为:");
            linkedList1.showNode();
            System.out.println();
            
            linkedList1.deleteN(2);
            System.out.println("删除后的链表为:");
            linkedList1.showNode();
        }
    
    }
    

    测试结果:
    循环链表增删改查测试结果

    三、Josephu(约瑟夫)问题

    	有n个人,编号为1~n,从第k个人开始报数,从1开始报,报到m的人会出列,然后从第m+1个人开始,重复以上过程。在出列了n-1个人后,
    问出列的序列和最后一个人的编号是?
    

    1、问题分析

      我们可以用一个不带头节点的循环链表来处理Josephu问题。先创建一个有n个节点的循环单链表,然后从k节点起从1开始计数,计到m,就把当前节点从链表中删除,然后从m+1个节点起再从1开始计数,知道链表中只剩下一个节点为止。
    需要注意:

    • 我们通过移动first指针,使first指针指向要出列的人,将其删除,所以需要创建一个辅助指针指向链表尾。
    • 由于从k个人开始报数,所以在报数前,需要将first和helper移动k-1次。
    • 当报数时,将first和helper移动m-1次。
    • 将first指针所处的节点删除,再将first和helper向后移动一个节点:
      first = first.next
      helper.next = first

    2、代码实现

    1、定义一个链表结构

    class Boy {
        private int no;
        private Boy next;
    
        public Boy(int no) {
            this.no = no;
        }
    
        public int getNo() {
            return no;
        }
    
        public void setNo(int no) {
            this.no = no;
        }
    
        public Boy getNext() {
            return next;
        }
    
        public void setNext(Boy next) {
            this.next = next;
        }
    }
    

    2、创建一个类来定义基本方法

    class CircleSingleLinkedList {
        //创建一个first节点
        private Boy first = null;
    
        //添加一个节点
        public void addBoy(int nums) {
            if (nums < 1) {
                System.out.println("nums的值不正确");
                return;
            }
            Boy curBoy = null;//辅助节点
            for (int i = 1; i <= nums; i++) {
                Boy boy = new Boy(i);
                if (i == 1) {
                    first = boy;
                    first.setNext(first);
                    curBoy = first;
                } else {
                    curBoy.setNext(boy);
                    boy.setNext(first);
                    curBoy = boy;
                }
            }
        }
    
        //遍历
        public void showBoy() {
            if (first == null) {
                System.out.println("链表为空");
                return;
            }
            Boy curBoy = first;
            while (true) {
                //System.out.printf("小孩的编号%d\n", curBoy.getNo());
                if (curBoy.getNext() == first) {
                    break;
                }
                curBoy = curBoy.getNext();
            }
            
        }
    
        //根据用户输入计算出出圈的顺序
    
        /**
         *
         * @param startnum  表示从第几个小孩开始
         * @param countnum  表示数几下
         * @param nums  表示最初有几个小孩
         */
        public void countBoy(int startnum, int countnum, int nums) {
            if (first == null || startnum < 1 || startnum > nums) {
                System.out.println("参数输入有误");
                return;
            }
            Boy helper = first;
            while (true) {
                if (helper.getNext() == first) {
                    break;
                }
                helper = helper.getNext();
            }
            for (int i = 0; i < startnum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            while (true) {
                if (helper == first) {//只剩一个节点
                    break;
                }
                for (int i = 0; i < countnum - 1; i++) {
                    first = first.getNext();
                    helper = helper.getNext();
                }
                //此时first节点指向出圈的节点
                System.out.printf("小孩%d出圈\n",first.getNo());
                first = first.getNext();
                helper.setNext(first);
            }
            System.out.printf("最后留在圈中的是%d\n", first.getNo());
        }
    
    }
    

    3、写一个Demo来测试

    /**
     * @author dankejun
     * @create 2020-03-27 17:33
     */
    public class Josepfu {
        public static void main(String[] args) {
            CircleSingleLinkedList list = new CircleSingleLinkedList();
            list.addBoy(5);
            list.showBoy();
    
            list.countBoy(1, 2, 5);
        }
    }
    

    测试结果:
    约瑟夫问题测试结果

    展开全文
  • 单向循环链表和双向循环链表

    千次阅读 2019-11-25 11:58:10
    单向循环链表和双向循环链表1.单向循环链表2.双向循环链表 关于顺序表、单向链表和双向链表请将鼠标移步 此处点击 1.单向循环链表 代码实现: //#pragma once //作为头文件时加上这行 #include<stdio.h> #...

    单向循环链表和双向循环链表


    关于顺序表、单向链表和双向链表请将鼠标移步 此处点击

    1.单向循环链表

    代码实现:

    //#pragma once				//作为头文件时加上这行
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    typedef int DataType;
    typedef struct Node
    {
    	DataType data;
    	struct Node *next;
    }CycleLinkedList;
    
    /*以下的第几个结点都不包括头节点,即头结点不计入下标*/
    
    /*初始化链表,新定义的链表结点必须先初始化*/
    void ListInit(CycleLinkedList* head);
    /*判断链表是否非空*/
    int ListNotEmpty(CycleLinkedList* head);
    /*返回链表元素个数*/
    int ListLength(CycleLinkedList* head);
    /*在下标为i[0,size]的位置处插入一个元素x,位于该处及该处后的元素依次后移,成功返回1,失败返回0*/
    int ListInsert(CycleLinkedList* head, int i, DataType x);
    /*将下标为i[0,size]的位置元素删除,并把值保存在x中,位于该处元素后的元素依次前移,成功返回1,失败返回0*/
    int ListDelete(CycleLinkedList* head, int i, DataType *x);
    /*放问下标为i[0,size]的位置元素,并把值保存在x中,成功返回1,失败返回0*/
    int ListGet(CycleLinkedList* head, int i, DataType *x);
    /*撤销单链表的空间*/
    void ListDestory(CycleLinkedList* head);
    
    void ListInit(CycleLinkedList* head)
    {
    	head->next = head;
    }
    
    int ListNotEmpty(CycleLinkedList* head)
    {
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	if (head->next == head)return 0;
    	else return 1;
    }
    
    int ListLength(CycleLinkedList* head)
    {
    	int i = 0;
    	CycleLinkedList* p = head;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	while (p->next != head)
    	{
    		i++;
    		p = p->next;
    	}
    	return i;
    }
    
    int ListInsert(CycleLinkedList* head, int i, DataType x)
    {
    	CycleLinkedList *p = head, *p1 = NULL;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	/*两种情况会退出循环*/
    	/*第一种是i不为0 && p->next==head退出,退出后i--,即i不为-1,也就是链表结点不足*/
    	/*第二种是i为0时退出,i--后为-1,此时无论p->next是否为head,p都是所找的结点*/
    	while (i-- && p->next != head)	//找到下标为i的结点的前一个结点
    	{								//注意此处&&的短路规则i--应位于&&前
    		p = p->next;
    	}
    	if (i != -1)
    	{
    		printf("插入参数不合法\n");
    		return 0;
    	}
    	p1 = (CycleLinkedList*)malloc(sizeof(CycleLinkedList));
    	p1->data = x;
    	p1->next = p->next;
    	p->next = p1;
    }
    
    int ListDelete(CycleLinkedList* head, int i, DataType *x)
    {
    	CycleLinkedList *p = head, *p1 = NULL;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	while (i-- && p->next != head)	//找到下标为i的结点的前一个结点
    	{
    		p = p->next;
    	}
    	if (i != -1)
    	{
    		printf("删除参数不合法\n");
    		return 0;
    	}
    	p1 = p->next;
    	*x = p1->data;
    	p->next = p1->next;
    	free(p1);
    }
    
    int ListGet(CycleLinkedList* head, int i, DataType *x)
    {
    	CycleLinkedList *p = head, *p1 = NULL;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	while (i-- && p->next != head)	//找到下标为i的结点的前一个结点
    	{
    		p = p->next;
    	}
    	if (i != -1)
    	{
    		printf("参数不合法\n");
    		return 0;
    	}
    	p = p->next;
    	*x = p->data;
    	return 1;
    }
    
    void ListDestory(CycleLinkedList* head)
    {
    	CycleLinkedList *p = head->next, *p1 = NULL;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	while (p->next != head)
    	{
    		p1 = p;
    		p = p->next;
    		free(p1);
    	}
    	free(p);
    }
    

    测试函数:

    void test()
    {
    	int i, x, size;
    	//也可用malloc动态申请内存,但是最后要自己调用free释放内存
    	CycleLinkedList head;
    	ListInit(&head);
    	for (i = 0; i < 10; i++)
    		ListInsert(&head, i, i);
    	printf("将下标为5处的元素删除\n");
    	ListDelete(&head, 5, &x);
    	printf("被删除的元素为:%d\n", x);
    	printf("插入元素10到下标为5处:\n", x);
    	ListInsert(&head, 15, 15);	//此行插入不合法 
    	ListInsert(&head, 5, 10);
    	printf("将链表输出\n");
    	size = ListLength(&head);
    	for (i = 0; i < size; i++)
    	{
    		ListGet(&head, i, &x);
    		printf("%d ", x);
    	}
    	ListDestory(&head);
    }
    

    运行结果:
    在这里插入图片描述

    2.双向循环链表

    代码实现:

    //#pragma once				//作为头文件时加上这行
    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    typedef int DataType;
    typedef struct Node
    {
    	DataType data;
    	struct Node *prior;
    	struct Node *next;
    }CycleDoublyList;
    
    /*初始化链表,新定义的链表结点必须先初始化*/
    void ListInit(CycleDoublyList* head);
    /*判断链表是否非空,非空返回1,空返回0*/
    int ListNotEmpty(CycleDoublyList* head);
    /*返回链表元素个数*/
    int ListLength(CycleDoublyList* head);
    /*在下标为i[0,size]的位置处插入一个元素x,位于该处及该处后的元素依次后移,成功返回1,失败返回0*/
    int ListInsert(CycleDoublyList* head, int i, DataType x);
    /*将下标为i[0,size]的位置元素删除,并把值保存在x中,位于该处元素后的元素依次前移,成功返回1,失败返回0*/
    int ListDelete(CycleDoublyList* head, int i, DataType *x);
    /*放问下标为i[0,size]的位置元素,并把值保存在x中,成功返回1,失败返回0*/
    int ListGet(CycleDoublyList* head, int i, DataType *x);
    /*撤销单链表的空间*/
    void ListDestory(CycleDoublyList* head);
    
    void ListInit(CycleDoublyList* head)
    {
    	head->prior = head;
    	head->next = head;
    }
    
    int ListNotEmpty(CycleDoublyList* head)
    {
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	if (head->next == head)return 0;
    	return 1;
    }
    
    int ListLength(CycleDoublyList* head)
    {
    	CycleDoublyList *p = head;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	int i = 0;
    	while (p->next != head)
    	{
    		i++;
    		p = p->next;
    	}
    	return i;
    }
    
    int ListInsert(CycleDoublyList* head, int i, DataType x)
    { 
    	CycleDoublyList *p = head, *p1 = NULL;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	/*两种情况会退出循环*/
    		/*第一种是i不为0 && p->next==head退出,退出后i--,即i不为-1,也就是链表结点不足*/
    		/*第二种是i为0时退出,i--后为-1,此时无论p->next是否为head,p都是所找的结点*/
    	while (i-- && p->next != head)	//找到下标为i的结点的前一个结点
    	{								//注意此处&&的短路规则i--应位于&&前
    		p = p->next;
    	}
    	if (i != -1)
    	{
    		printf("插入参数不合法\n");
    		return 0;
    	}
    	p1 = (CycleDoublyList*)malloc(sizeof(CycleDoublyList));
    	p1->data = x;
    	/*下方代码 将新结点p1加到链表中,位于p后*/
    	p1->next = p->next;
    	p1->prior = p;
    	p->next = p1;
    	if (p1->next != NULL)p1->next->prior = p1;	//若插入的元素下标不是链表尾
    	return 1;
    }
    
    int ListDelete(CycleDoublyList* head, int i, DataType *x)
    {
    	CycleDoublyList *p = head, *p1 = NULL;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	while (i-- && p->next != head)	//找到下标为i的结点的前一个结点
    	{								//注意此处&&的短路规则i--应位于&&前
    		p = p->next;
    	}
    	if (i != -1) {
    		printf("删除参数i不合法\n");
    		return 1;
    	}
    	p1 = p->next;
    	*x = p1->data;
    	/*下方代码 将p1从链表中删除*/
    	p->next = p1->next;
    	if (p1->next != NULL)p1->next->prior = p;	//若插入的元素下标不是链表尾
    	free(p1);
    	return 1;
    }
    
    int ListGet(CycleDoublyList* head, int i, DataType *x)
    {
    	CycleDoublyList *p = head, *p1 = NULL;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	while (i-- && p->next != head)	//找到下标为i的结点的前一个结点
    	{
    		p = p->next;
    	}
    	if (i != -1)
    	{
    		printf("删除参数不合法\n");
    		return 0;
    	}
    	p1 = p->next;
    	*x = p1->data;
    	/*下方代码 将p1从链表中删除*/
    	return 1;
    }
    
    void ListDestory(CycleDoublyList* head)
    {
    	CycleDoublyList *p = head->next, *p1 = NULL;
    	if (head == NULL) {
    		printf("头结点为NULL\n");
    		return;
    	}
    	while (p->next != head)
    	{
    		p1 = p;
    		p = p->next;
    		free(p1);
    	}
    	free(p);
    }
    

    测试函数:

    void test()
    {
    	int i, x, size;
    	//也可用malloc动态申请内存,但是最后要自己调用free释放内存
    	CycleDoublyList head;
    	ListInit(&head);
    	for (i = 0; i < 10; i++)
    		ListInsert(&head, i, i);
    	printf("将下标为5处的元素删除\n");
    	ListDelete(&head, 5, &x);
    	printf("被删除的元素为:%d\n", x);
    	printf("插入元素10到下标为5处:\n", x);
    	ListInsert(&head, 15, 15);	//此行插入不合法 
    	ListInsert(&head, 5, 10);
    	printf("将链表输出\n");
    	size = ListLength(&head);
    	for (i = 0; i < size; i++)
    	{
    		ListGet(&head, i, &x);
    		printf("%d ", x);
    	}
    	ListDestory(&head);
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 本文介绍了单向链表的一种特例——单向循环链表,并使用单向循环链表实现了队列这种数据结构。

    【数据结构与算法Python描述】单向线性链表简介及其Python实现给出了链表的最简单形式——单向线性链表,以及其Python语言实现和相关应用。

    实际上,基于单向线性链表的变形很多,而单向循环链表(本文简称“循环链表”)是其中一种较为常见的形式。

    一、单向循环链表引入

    在文章【数据结构与算法Python描述】队列和双端队列简介及其高效率版本Python实现中,我们首次引入了循环的概念,但实际上列表的内存模型并不存在任何首尾相连的特征,只是通过使用取模运算可以使得类似循环的特点。

    对于链表,特别是单向线性链表,通过对其进行一定的变形可以获得真正意义上的环状形态,即如下图所示,让原本引用None的单向线性链表尾结点的next域引用头结点。

    在这里插入图片描述

    实际上,对于循环链表,已经不存在所谓头和尾的概念了,所以一般地可将循环链表画成如下图所述形式。对于这一说法以及循环链表的模型类比理解,一个现实中的例子是上海的地铁4号线,这是一条以横贯方式连接上海所有主要地铁线的环形线。

    在这里插入图片描述

    尽管说循环链表不存在开始和结束的概念,还是有必要定义一个变量使其引用循环链表中的某一个结点,上图使用名为current的变量,只有这样才能通过类似current = current.next的语法遍历找到链表中的所有节点。

    二、单向循环链表应用

    对于循环链表,我们不会像单向线性链表一样去实现其ADT的所有方法,因为循环不存在所谓头(尾)部插入(删除)等概念,即使实现了也大同小异。更多地,我们将循环链表的一些特性来实现特定的功能,比如下面的循环调度算法。

    1. 循环调度算法

    循环调度算法可以实现这样一种功能:对于某一个对象集合,该算法可以一种循环的方式挨个获取对象中的每个元素,然后对该元素做某种处理。

    典型地使用循环调度算法的案例是计算机CPU为电脑上的不同应用分配执行时间片,我们知道计算机上的CPU数量一般远小于正在运行的应用数量,计算机就是利用诸如循环调度算法实现CPU在不同应用之间轮流切换执行,从而达到看似多个应用同时执行的效果。

    2. 循环链表实现队列

    2.1 分析

    对于循环调度算法的实现,可以使用一个普通的队列来实现,即循环执行下列三个步骤:

    • 使用e = queue.dequeue()获取应用e
    • 为元素e代表的应用服务;
    • 使用queue.enqueue(e)将已被服务的元素e重新入队。

    在这里插入图片描述

    实际上,如果使用【数据结构Python描述】队列和双端队列简介及基于列表的Python实现中的ListQueue来实现循环调度算法,则在每次循环中都需要先对某一元素执行一次队头出队操作,再对同一个元素执行一次队尾入队操作。

    如果使用循环链表的思想,那么头结点出队然后在尾结点处入队的动作只需一个方法(一般名为rotate())即可实现,如下图所示:

    • 先将队列的头尾结点链接在一起;
    • 然后在该方法中使用标记当前头和尾结点的变量,使得在一次循环中将当前头结点变为尾结点,当前头结点的下一个结点成为新的头结点。

    在这里插入图片描述

    2.2 ADT

    由上述分析,如果将使用循环链表思想实现支持循环调度算法的队列命名为CircularQueue,则其ADT至少包含下列方法:

    方法名称方法描述
    __len__()重写该方法,使对于CircularQueue的对象可以使用len()方法
    is_empty()判断CircularQueue对象是否为空
    first()返回但并不删除队列的头部元素
    rotate()完成头部元素出队并从尾部入队操作
    enqueue(e)向当前队列的尾部加入新的元素
    dequeue()删除当前队列中在队头的元素

    2.3 实现

    为了实现上述ADT包含的方法,乍一看似乎两个指向结点的变量,即self._headself._tail。实际上,使用一个self._tail即可,因为总是可以通过self._tail.next来获取头结点的引用。

    因此,使用下列两个变量即可实现CircularQueue类:

    • self._tail:指向尾结点的变量;
    • self._size:保存当前队列中元素数量的变量。
    class Empty(Exception):
        """尝试对空队列进行删除操作时抛出的异常"""
        pass
    
    
    class _Node:
        """节点类"""
    
        def __init__(self, element, next=None):
            """
            :param element: 节点代表的对象元素
            :param next: 下一个节点
            """
            self.element = element
            self.next = next
            
    
    class CircularQueue:
        """支持循环调度算法的队列"""
        
        def __init__(self):
            """创建一个空的队列"""
            self._tail = None
            self._size = 0
            
        def __len__(self):
            """
            返回队列中元素个数
            :return: 队列中元素个数
            """
            return self._size
        
        def is_empty(self):
            """
            如果队列为空则返回True,否则返回False
            :return: 队列是否为空的标识
            """
            return self._size == 0
        
        def first(self):
            """
            返回但不删除队头结点的元素
            :return: 队头结点的元素
            """
            if self.is_empty():
                raise Empty('当前队列为空!')
            head = self._tail
            return head.element
        
        def rotate(self):
            """
            完成头部元素出队并从尾部入队操作
            :return: None
            """
            if self._size > 0:
                self._tail = self._tail.next  # 标识尾结点的变量指向当前头结点
                
        def enqueue(self, element):
            """
            向当前队列的尾部加入新的对象元素
            :param element: 待从尾部入队的对象元素
            :return: None
            """
            node = _Node(element)  # 元素封装成结点
            if self.is_empty():
                self._tail = node
                self._tail.next = node  # 链表成环
            node.next = self._tail.next  # 新结点和当前头结点建链
            self._tail.next = node  # 当前尾结点和新结点建链
            self._tail = node  # 新结点成为尾结点
            self._size += 1
            
        def dequeue(self):
            """
            删除当前队列中在队头的元素
            :return: 队头的元素
            """
            if self.is_empty():
                raise Empty('当前队列为空!')
            old_head = self._tail.next
            if self._size == 1:
                self._tail = None  # 将队列置为空
            else:
                self._tail.next = old_head.next  # 直接跳过旧的头结点
            self._size -= 1
            return old_head.element
    

    对于上述代码,有两点值得记录的是:

    • 对于rotate()方法,在Python的collections模块中,其deque类有个功能类似的同名方法;
    • 对于enqueue(e)方法,由于出现了两次完全一样的语句self._tail = node,其代码可以修改成如下形式:
    def enqueue(self, element):
        """
        向当前队列的尾部加入新的对象元素
        :param element: 待从尾部入队的对象元素
        :return: None
        """
        node = _Node(element)  # 元素封装成结点
        if self.is_empty():
            node.next = node  # 链表成环
        node.next = self._tail.next  # 新结点和当前头结点建链
        self._tail.next = node  # 当前尾结点和新结点建链
        self._tail = node  # 新结点成为尾结点
        self._size += 1
    
    展开全文
  • 单向循环链表

    2019-01-14 10:53:12
    单向循环链表 单向循环链表: 在单向链表中,头指针是相当重要的,因为单向链表的操作都需要头指针,所以如果头指针丢失或者破坏, 那么整个链表都会遗失,并且浪费链表内存空间。 单向循环链表的构成: 如果把...

    单向循环链表


    单向循环链表:

    在单向链表中,头指针是相当重要的,因为单向链表的操作都需要头指针,所以如果头指针丢失或者破坏,
    那么整个链表都会遗失,并且浪费链表内存空间。
    

    单向循环链表的构成:

    如果把单链表的最后一个节点的指针指向链表头部,而不是指向NULL,那么就构成了一个单向循环链表。
    

    python实现单向循环链表

    class Node():
        '''单循环链表的结点:next默认指向头结点'''
        def __init__(self,elem):
            self.elem = elem
            self.next = None
    
    class SingleCycleLinkList():
        '''循环单链表'''
        def __init__(self,node=None):
            self.__head = node
            #node如果不是指向None,说明不是空链表,next虚需要指向自己,构成环
            if node:
                node.next = node
    
        def is_empty(self):
            '''链表是否为空'''
            # 如果头结点为None,说明为空,返回true
            return self.__head == None
    
    
        def length(self):
            '''链表长度:求链表长度需要从头开始遍历并计数;
            注意考虑特殊情况,即链表为空链表,即头结点为None,不会进入循环,需要加判断如果链表为空,直接返回0 ;
            另一种特殊情况,循环链表只有一个结点,cur.next ==self.__head ,
            不会进入循环,返回的count为1'''
            if self.__head == None:
                return 0
            else:
                # 游标cut表示指向当前结点,初始指向头结点 
                cur =self.__head
                # count用来计数,从1开始
                count = 1
                #循环退出条件:由于单循环链表的尾结点不指向None,而是指向头结点;
                #所以当游标cur.next指向头结点时,整个链表循环一遍,循环结束。
                while cur.next != self.__head:
                    #循环一次,count计数加1
                    count += 1
                    #游标cur也向后移动一个结点
                    cur = cur.next
                # 循环结束,count的值即为链表长度,返回count
                return count 
           
        
        def travel(self):
            '''遍历整个链表:需要从头开始,输出每个结点的元素;
             注意考虑特殊情况,即链表为空链表,即头结点为None,不需要输出任何元素,所以需要另外写判断处理,如果为空,直接返回
            另一种特殊情况,链表只有一个结点,即cur.next == self._head ,不会进入循环,直接打印结点,符合要求 '''
            if self.is_empty():
                return
            else:
                #定义游标cur表示指向当前结点,初始指向头结点
                cur = self.__head
                #循环退出条件:由于单循环链表的尾结点不指向None,而是指向头结点;
                #所以当游标cur.next指向头结点时,整个链表循环一遍,循环结束
                while cur.next != self.__head:
                    #输出当前指向元素
                    print(cur.elem,end=' ')
                    #游标向后移动一个结点
                    cur = cur.next
                #由于循环结束时,即cur指向最后一个结点时,无法进入循环,所以最后一个结点没有输出,循环结束后补上最后一个结点
                print(cur.elem)
           
        
        def add(self,item):
            '''在头部插入结点:不需要遍历;
            注意考虑特殊情况,链表为空链表,即头结点为None,需单独判断处理。
            考虑另一种特殊情况,即非空时且链表只有一个元素,此时cur.next ==self.__head
            不会进入循环,符合要求,不用单独处理'''
            #定义要插入的结点
            node = Node(item)
            #判断如果链表为空,要插入的node即为头结点
            if self.is_empty():
                self.__head == node
                #自己的next指向自己形成循环
                node.next = node
            else:
                #如果链表不会空
                cur = self.__head
                while cur.next != self.__head:
                    cur =  cur.next
                
                # 现将要插入的结点的next指向头结点
                node.next = self.__head
                # 再将头结点变成要插入的结点
                self.__head = node
                #循环结束后此时cur指向最后一个结点
                cur.next = self.__head
    
    
          
        def append(self,item):
            '''在尾部插入结点:需要从头遍历找到尾结点,在其后插入结点;
            考虑特殊情况,即向空链表尾部插入结点,空链表即头结点为空,需单独考虑,故需要在开始是判断链表是否为空'''
            #定义要插入的结点
            node = Node(item)
            #如果循环链表为空
            if self.__head == None:
                #要插入的node即为头结点
                self.__head = node
                # 自己的next指向自己形成循环
                node.next = node
            else:
                # 定义游标cur表示指向当前结点,初始时指向头结点
                cur = self.__head
                #循环退出条件,找到尾结点退出,即cur.next 指向头结点self.__head
                while cur.next != self.__head:
                    # 游标向后移动一个结点
                    cur = cur.next
                # 循环结束后,游标刚好指向尾结点,插入元素,首先要插入的结点的next指向头结点
                node.next = self.__head #或者node.next = cur.next也行
                # 当前结点的next指向要插入的结点
                cur.next = node
    
            
        
        def insert(self,pos,item):
            '''在指定位置插入结点:插入前需要遍历找到指定位置,在指定位置前插入;
            考虑特殊情况,如果pos输入的值小于等于0,则认为是在头部插入一个结点,
            如果输入的pos值比链表长度还大,则认为要在为不插入结点'''
            # 定义要插入的结点
            node = Node(item)
            if pos <= 0:
                self.add(item)
            elif pos > self.length()-1:
                self.append(item)
            else:
                # 定义游标pre表示指向所找位置的前一个结点,初始从头结点开始
                pre = self.__head
                #从头开始循环并用count计数,循环退出条件为 count < pos-1
                # count =0  pre指向0号结点  count=1 pre指向1号结点,pre到pos-1的结点即可
                count = 0
                while count < pos-1:
                    # count加1
                    count += 1
                    # pre向后移动一个结点
                    pre = pre.next 
                #循环结束,pre指向pos-1的结点,即pos的前一个结点,在pos结点的前面,pos-1结点的后面插入元素
                node.next = pre.next
                pre.next = node
    
    
                   
    
        def remove(self,item):
            '''删除指定元素结点:遍历找到元素为item的结点,便删除,如果链表中有多个结点的元素与item相同,则只删除第一个;
            注意考虑特殊情况,链表为空,直接返回false即可,需单独判断
            另外的特殊情况,链表不为空,若删除的为第一个结点,需单独判断操作,
            由于循环结束时,没有判断尾结点,需要在循环结束后单独判断,并考虑特殊情况即循环链表中只有一个节点的情况'''
            if self.is_empty():
                return False
            else:
                #定义游标cur指向当前结点,初始指向头结点
                cur = self.__head
                #定义游标pre指向当前结点的前一个结点,初始也指向头结点
                pre = self.__head
                # 从头开始循环遍历每个结点,cur.next指向头结点时,说明循环结束
                while cur.next != self.__head:
                    if cur.elem == item:
                        #如果找到了,判断是否为第一个结点
                        if cur == self.__head:
    
                            #如果要删除的是第一个结点
                            # 先循环找到尾结点
                            #定义游标rear,初始指向头结点
                            rear = self.__head
                            while rear.next != self.__head:
                                rear = rear.next
                            #循环结束,此时rear指向尾结点
                            self.__head = cur.next
                            rear.next = self.__head
                        else:
                            #要删除的元素是循环链表中间的元素
                            pre.next = cur.next
                            #返回True,循环结束
                        return True
                    else:
                        #如果没有找到,游标pre向后移动一个结点
                        pre = cur
                        # 游标cur也移动一个结点,注意,一定是先移动pre后移动cur,保持前后关系
                        cur = cur.next
                #循环结束,此时cur指向最后一个结点,并没有判断
                if cur.elem == item:
                    #如果最后一个结点就是要删除的结点,
                    #判断 链表是否只有一个结点
                    if cur == self.__head:
                        #如果只有这一个结点,即让链表为空
                        self.__head = None
                    else:
                        # 删除,即将pre结点的next指向头结点
                        pre.next = cur.next
                        return True
                return False
    
    
         
                                
    
        
        def search(self,item):
            '''查询指定元素结点:从头循环遍历链表,找到第一个元素为item的结点,输出值;
            注意考虑特殊情况 如果链表为空,则cur就是指向None,直接返回flase,需单独判断处理;
            考虑另一种特殊情况,如果链表只有一个结点,即cur.next 开始就指向头结点,则不进入循环直接判断,程序合理'''
            if self.is_empty():
                return False
            else:
                # 定义游标cur 表示指向当前结点,初始指向头结点
                cur = self.__head
                #循环链表,查找
                while cur.next != self.__head:
                    if cur.elem == item :
                        # 如果找到了,则输出,并返回True
                        print(cur.elem)
                        return True
                    else:
                        #如果没有找到,cur向后移动一个结点
                        cur = cur.next
                #循环退出后cur指向尾结点,无法进入循环,需要判断
                if cur.elem == item:
                    print(cur.elem)
                    return True
                # 整个链表遍历结束仍然没有找到,返回false
                return False
    
    if __name__ == '__main__':
    
        ll = SingleCycleLinkList()
        print(ll.is_empty())
        res = ll.length()
        print(res)
        ll.append(10)
        ll.append(8)
        ll.append(3)
        ll.append(5)
        ll.append(4)
        ll.travel()
        ll.add(100)
        ll.travel()
        res = ll.length()
        print(res)
        ll.travel()
        print(ll.is_empty())
        ll.insert(3,50)
        ll.travel()
        ll.insert(0,90)
        ll.travel()
        ll.insert(8,40)
        ll.travel()
        ll.search(3)
        ll.search(90)
        ll.search(40)
    
        ll.remove(8)
        ll.travel()
        ll.remove(90)
        ll.travel()
        ll.remove(40)
    
        ll.travel()
    
        
            
    
    True
    0
    10 8 3 5 4
    100 10 8 3 5 4
    6
    100 10 8 3 5 4
    False
    100 10 8 50 3 5 4
    90 100 10 8 50 3 5 4
    90 100 10 8 50 3 5 4 40
    3
    90
    40
    90 100 10 50 3 5 4 40
    100 10 50 3 5 4 40
    100 10 50 3 5 4
    
    展开全文
  • 在我的上篇博客中,详细介绍了关于单链表的实现,...单向循环链表和普通的单链表区别主要在于尾结点,单链表的尾结点指向null,而单向循环链表是将尾结点的指针指向了头结点,首尾相连,从而构成了循环链表。如下图...
  • 单向循环链表: 如果把单链表的最后一个节点的指针指向链表头部,而不是指向NULL,那么就构成了一个单向循环链表,通俗讲就是把尾节点的下一跳指向头结点。 单向循环链表 –多个节点和只有一个节点的结构分析 双向...
  • Python单向循环链表

    2020-04-15 10:51:54
    一、单向循环链表定义 单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。 操作: is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) 在...
  • 1.单向链表 2.单向循环链表 3.双向链表 4.链表与顺序表的对比 5.自定义单向链表 6.自定义单向循环链表 7.自定义双向链表
  • 单向循环链表 #定义节点 class Node(object): def __init__(self,elem,next_=None): self.elem=elem self.next=next_ class CircleLinklist(object): def __init__(self,node=None): self.hea...
  • 主要介绍了Python实现的单向循环链表功能,简单描述了单向循环链表的概念、原理并结合实例形式分析了Python定义与使用单向循环链表的相关操作技巧,需要的朋友可以参考下
  • 1.单向循环链表   对于单链表而言,最后一个结点的指针域是空指针,如果将该链表头结点指针指向最后一个结点的指针域当中,则使得链表头尾结点相连,整个链表形成一个环,就构成了单向循环链表。其他的与单链表...
  • C++单向循环链表实现

    2021-08-15 19:37:13
    单向循环链表与单向链表十分相似,具有关单向链表详细理论与实现...而单向循环链表将尾部node的指针域指向头部node,首位相连构成单向循环链表,具体形式为: 具体实现代码为: 1、链表定义 //定义节点 class...
  • 数据结构之链表(单向链表、双向链表、单向循环链表、双向循环链表、静态链表、动态链表) 单向链表 概念 单向链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。链表是使用指针进行构造的列表,并且...
  • 主要介绍了python单向循环链表原理与实现方法,结合实例形式详细分析了Python单向循环链表概念、原理、定义及使用方法,需要的朋友可以参考下
  • 单向循环链表定义 单向循环链表(Single Cycle Linked List)是单链表的一个变形,将链表中最后一个节点的next域不再为None,而是指向链表的头节点。 节点示意图 单向循环链表示意图 单向循环链表的基本操作 is_...
  • 单向循环链表的简单实现

    万次阅读 多人点赞 2017-07-10 19:31:14
    单向循环链表:  在单向链表中,头指针是相当重要的,因为单向链表的操作都需要头指针,所以如果头指针丢失或者破坏,那么整个链表都会遗失,并且浪费链表内存空间。 单向循环链表的构成:  如果把单链表的...
  • 单向循环链表.zip

    2019-09-18 23:09:54
    单向循环链表源码,包括List的接口定义的源码,实现了List接口的方法。
  • python单向循环链表

    2018-08-28 10:08:09
    单向循环链表 单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。   操作 is_empty() 判断链表是否为空 length() 返回链表的长度 travel() 遍历 add(item) ...
  • 单向循环链表是单向链表的一个拓展,主要区别在于单向循环链表尾节点的next不再指向None,而是指向链表的头节点。 下面通过代码一步步实现单向循环链表并附上注释和测试,主要实现以下几个基本方法:  is_empty()...
  • Python实实现现的的单单向向循循环环链链表表功功能能示示例例 这篇文章主要介绍了Python实现的单向循环链表功能,简单描述了单向循环链表的概念原理并结合实例形式分析 了Python定义与使用单向循环链表的 关操作技巧...
  • 1 定义2 Python手写单向循环链表2.1 先定义节点2.2 增删改查2.3 实例参考 1 定义 在之前的博客:数据结构与算法 | 链表-2:单链表的实现中笔者提到了单向链表的相关实现,本期博客将注重单向循环链表的实现! 单向...
  • Python实现单向循环链表 关于链表的介绍,请参考:https://blog.csdn.net/weixin_43790276/article/details/104033254 本篇文章使用 Python 来实现一个单向循环链表。 一、定义一个创建节点的类 链表是由一个个...
  • 1.单向循环链表定义单向循环链表的元素存储和队列的顺序存储ArrayQueueLoop的优化有点像,元素是围绕着连接在一起的,(存放元素)就像一个圆环一样的结构,而不是一条直线。 单向循环链表图示。 单向循环...
  • 文章目录四-下, 单向循环链表4.0 定义和概念4.1 单向循环链表的应用--约瑟夫问题 四-下, 单向循环链表 4.0 定义和概念 单链表的指针域只存储了向后的指针,到了尾结点就无法继续向后的操作。 本篇文章将介绍单向...
  • 本篇文章将介绍单向循环链表,它和单链表的区别在于结尾点的指针域不是指向null,而是指向头结点,形成首尾相连的环。这种首尾相连的单链表称为单向循环链表。循环链表可以从任意一个结点出发,访问到链表中的全部...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,133
精华内容 9,653
关键字:

单向循环链表定义