数据结构与算法(二)循环链表的实现

Posted on | In

前言

今儿是大年初一,白天看完流浪地球这部科幻电影,号称中国科幻电影的一个里程碑。剧情紧凑，特性也不错很有质感。特别末日的的地下城生活片段。一个字棒。 晚上闲来无事单算研究下大话数据结构这部分，填补下数据结构这方面的弱点。

什么是循环链表

  • 将单链表中终端结点的指针端自空指针改为指向头结点,就使整个单链表形成一 个环,这种头尾:相接的单链表称为单循环链表,简称循环链表。

循环列表的生活情境

  • 比出 ,你是一业务员, 家在上海。儒要经常出差,行程就是上海到北京一路上的 城市,找客户谈生意或分公司办理业务。你从上海出发,乘火车路经多个城市停留 后,再乘飞机返回上海,以后,每隔一段时间,你基本还要按照这样的行程开展业务

输入图片说明

  • 有一次你先到南京开会，接下来要对以上的城市走一遍。此时有人对你说,不行,你得从上海开始,因为上海是第一站。 你会对这人说什么?神经病。哪有这么傻 的,直接回上海根本没有必要,你可以从南京开始,下一站蚌埠,直到北京,之后再 考虑走完上海及苏南的几个城市。显然这表示你是从当中一结点开始遍历整个链裴 , 这都是原来的单链表结构解决不了的问题。

循环链袭和单链表的主要差异

  • 循环链袭和单链表的主要差异就在于循环的判断条件土,原沫是判断 p->next(指针域)
    是否为空,现在则是 p-> next 不等于头结点,则循环未结束。
  • 在单链表中,我们有了头结点时,我们可以用 0(1)的时间访问第一个结点,但对于要访问到最后一个结点,却需要 O(n)时间,因为我们需要将单链表全部扫描一编。
  • 循环链表的尾指针方式就用0(1)的时间访问到尾部元素

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
public class CycleLinkList {

    Node head; // 头指针
    Node current;// 当前结点对象
    int size;// 结点个数

    public CycleLinkList() {
        // 初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
        this.head = current = new Node(null);
        this.size = 0;// 单向链表，初始长度为零。
        this.head.next = this.head; //最后一个元素指针域指向头结点
    }

    //使用当前结点对象 定位到要操作结点的前一个结点。
    public void index(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数错误！");
        }
        // 说明在头结点之后操作。
        if (index == -1){
            // 第一个数据元素结点的下标是0，那么头结点的下标自然就是-1
            return;
        }
        current = head.next;
        int temp=0;	 	//临时变量 用户循坏判断当前节点是否到达
        while (current!=head && temp<index){
            //循环找到插入节点的前一个节点
            current=current.next;
            temp++;
        }
    }


    /**
     * 删除思路：
     *
     * 1。定位到当前要删除的下标的对像的前一个节点
     * 2. 通过改变当前删除对象前一个节点的指针域。》指向当前要删除对象的指针域指向的下一个节点。
     * @param index
     * @throws Exception
     */
    public void delete(int index) throws Exception {
        // 判断链表是否为空
        if (isEmpty()) {
            throw new Exception("链表为空，无法删除！");
        }
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index - 1);// 定位到要操作结点的前一个结点对象。
        current.setNext(current.next.next);
        size--;
    }

    /**
     * 获取思路：
     * 		从头节点开始遍历。用临时变量temp记录遍历的次数。一直遍历等于index就不会再行循坏，直接取出当前下标的节点
     * @param index
     * @return
     * @throws Exception
     */
    public Object get(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数非法！");
        }
        index(index);
        return current.getElement();
    }

    /**
     * 指定位置插入节点
     * @param index
     * @param obj
     * @throws Exception
     */
    public void insert(int index, Object obj) throws Exception {
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj,current.next));
        size++;

    }

    /**
     * 未指定下标末尾插入
     * @param obj
     * @throws Exception
     */
    public void insert(Object obj) throws Exception {
        /**
         * 1.判断当前节点指向一下节点的指针域是否为空
         * 如果指针域为空 说明是此节点是末尾节点
         * 直接在尾部修改默认节点的指针域执指向新增的节点，并把新增的节点的指针域指向null
         */
        while (current.next!=null){
            //循环判断当前节点指针域是否有下一个节点
            current=current.next;
        }
        current.setNext(new Node(obj, current.next));
        size++;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return this.size;
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Node {
	Object element; // 数据域
	Node next; // 指针域

	// 头结点的构造方法
	public Node(Node nextval) {
		this.next = nextval;
	}

	// 非头结点的构造方法
	public Node(Object obj, Node nextval) {
		this.element = obj;
		this.next = nextval;
	}

	// 获得当前结点的指针域
	public Node getNext() {
		return this.next;
	}

	// 获得当前结点数据域的值
	public Object getElement() {
		return this.element;
	}

	// 设置当前结点的指针域
	public void setNext(Node nextval) {
		this.next = nextval;
	}

	// 设置当前结点数据域的值
	public void setElement(Object obj) {
		this.element = obj;
	}

	public String toString() {
		return this.element.toString();
	}


}

约瑟夫环

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1] 结果+1即为原问题的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Yuesefu {

    /**
     * 构建循环链表
     * @param totalCol
     * @return
     */
    public node createNodes(int totalCol){
        node head = null; //定义一个头结点
        node[] nodes = new node[totalCol]; //数组结点存放41个人
        for(int i = 0; i < totalCol ; i++){
            nodes[i] = new node();
            nodes[i].node = i+1 ; //数据域赋值  不能让从0开始赋值 +1
            if(i==0){ //为0时就是是头结点
                // 初始化头结点
                head = nodes[i];
            }else{
                //当前下标结点的前一个节点对象的指针域指向当前i的结点
                nodes[i-1].next = nodes[i];
            }
        }
        nodes[totalCol-1].next = head ; //最后一个结点的指针域指向头结点
        return head ;
    }

public void begin(int total,int key){
        int sort = 0 ; //删除的序号
        int n = total ; //总人数
        node head = createNodes(total);
        //判断循环链表是不是只剩下一个节点
        while(head.next != head){
            for(int i = 1 ; i < key-1 ; i++){
                //1 ：每报数为3的人前一个节点 也就是2 并替代当前头结点
                head = head.next;

            }
            //2：用一个临时节点代替为当前报数为3的结点
            node temp = head.next;
            System.out.println("第"+(++sort)+"个自杀的为："+temp.node);

            //3：使头结点的指针域指向报数为3的结点的next指向的结点
            head.next = temp.next;
            //替换头结点 等于当前报数为3的人结点  循环以上步骤直到最后一个结点自杀完毕
            head = head.next;

        }
        System.out.println("第"+(++sort)+"个自杀的为："+head.node);
    }

    public static void main(String[] args) {
        Yuesefu y = new Yuesefu();
        y.begin(41,3);
    }
}
class node {
    node next ; //指针域
    int node ; //数据域
    public node getNext() {
        return next;
    }
    public void setNext(node next) {
        this.next = next;
    }
    public int getNode() {
        return node;
    }
    public void setNode(int node) {
        this.node = node;
    }

}

算法流程如下：

  • 1.初始化循环链表,从下标1开始自增赋值。头结点单数据域默认为空。单独处理不存放值
  • 2.赋值到最后totalCol-1的结点 也就是尾部结点。它的指针域指向头结点形成单向循环链表。
  • 3.循序开始判断链表是不是只剩下一个节点。也就是结点的指针域是否指向头结点。如果是就直接退出while并自杀此结点
  • 4.当结点的指针域不是指向头结点时。循环操作i<k-1次循环找到当前报数为3的前一个节点。并使头结点替换
  • 5 用一个临时节点代替为当前报数为3的结点（也就是步骤4找的结点的next指向）输出它已自杀
  • 6.使头结点的指针域指向报数为3的结点的next指向的结点。最后替换头结点等于当前报数为3的人结点 循环以上步骤直到最后一个结点自杀完毕

输入图片说明

觉得本文不错的话，分享一下给小伙伴吧~