1. Toy模板网首页
  2. > Toy博客

第1关：单循环链表的实现—链表的添加、遍历任务描述相关知识单循环链表添加操作遍历循环链表编程要求测试说明任务描述在操作单链表时，

10月前 作者：四阿哥108 分类：Toy博客 阅读(46) 违法举报

这篇具有很好参考价值的文章主要介绍了第1关：单循环链表的实现—链表的添加、遍历任务描述相关知识单循环链表添加操作遍历循环链表编程要求测试说明任务描述在操作单链表时，。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第1关：单循环链表的实现—链表的添加、遍历

200

  • 任务要求
  • 参考答案
  • 评论42
  • 任务描述
  • 相关知识
    • 单循环链表
      • 添加操作
      • 遍历循环链表
  • 编程要求
  • 测试说明

任务描述

在操作单链表时，我们有时希望从单链表中的任一结点出发都能遍历整个链表，但对于单链表来说，只有从头结点开始才能扫描表中的全部结点。因此我们需要改动链表，使其首尾相接，这样就能满足我们的需求。

本关任务：完成带头结点的单循环链表的添加功能，遍历链表并输出。

相关知识

单循环链表

循环链表是一种首尾相接的链表。其特点是无需增加存储量，只需对表的链接方式稍作改变，即可使得表操作更加方便灵活。

在单链表中，将末尾结点的指针域null改为指向表头结点或开始结点，就得到单链形式的循环链表，称为单循环链表。

为使空表和非空表的处理方式一致，循环链表中也可以设置一个头结点。这样空循环链表仅有一个自成循环的头结点。 如下图：

添加操作

单循环链表的添加操作与普通的单链表操作类似，只需添加时注意处理尾结点，使其指向头结点。下面是添加操作示意图。

这里采用的是尾插法，即在链表的末尾添加结点。我们使tail指向链表尾结点，因此添加结点node时只需改动tail和新结点node之间的链接关系即可。由于有头结点，所以空表和非空表的处理方式是一样的。

 

    

  1. node.next=tail.next;
    2. 

  2. tail.next=node;
    3. 

  3. tail=node;
    4. 



遍历循环链表
 

在循环链表中，链表的尾结点不是指向null。因此要输出链表元素时，其终止条件就不再是像非循环链表那样判断p==null或p.next==null，而是判别它们是否等于某一指定结点，如头结点head。如下图所示：
 
 

编程要求
 

本关的编程任务是补全右侧代码片段中Begin至End中间的代码，具体要求如下：
 

    

  • 完成单循环链表的添加功能；
    • 

  • 遍历单循环链表，并输出元素的值。
    • 



具体请参见后续测试样例
 

本关涉及的代码文件MyCircleLinkedList.java的代码框架如下：
 

 
 

package step1;
 
/**
 * Created by sykus on 2018/1/15.
 */
public class MyCircleLinkedList {
    private Node head;//头结点, 不存数据
    private Node tail;//尾结点, 指向链表的最后一个节点
    private int size;
 
    public MyCircleLinkedList() {
        head = new Node(Integer.MIN_VALUE, null);
        head.next = head;
        tail = head;
        size = 0;
    }
 
    /**
     * 添加到链表尾部
     *
     * @param item
     */
    public void add(int item) {
        /********** Begin *********/
        Node node = new Node(item, tail.next);
        tail.next = node;
        tail = node;
        size++;
 
 
 
        /********** End *********/
    }
 
    /**
     * 遍历链表并输出元素
     */
    public void output() {
        /********** Begin *********/
        Node p = head;
        while (p.next != head) {
                p = p.next;
                System.out.println(p.item);
        }
 
 
 
        /********** End *********/
    }
 
    public boolean isEmpty() {
        return head.next == head;
    }
 
    public int size() {
        return size;
    }
 
    //结点内部类
    private static class Node {
        int item;
        Node next;
 
        Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}
//智科01 421045 

 

第二关
 

package step2;
 
/**
 * Created by sykus on 2018/1/15.
 */
public class MyCircleLinkedList {
    private Node head;//头结点, 不存数据
    private Node tail;//尾结点, 指向链表的最后一个节点
    private int size;
 
    public MyCircleLinkedList() {
        head = new Node(Integer.MIN_VALUE, null);
        head.next = head;
        tail = head;
        size = 0;
    }
 
    /**
     * 添加到链表尾部
     *
     * @param item
     */
    public void add(int item) {
        Node node = new Node(item, tail.next);
        tail.next = node;
        tail = node;
        ++size;
 
    }
 
    /**
     * 遍历链表并输出元素
     */
    public void output() {
        Node p = head;
        while (p.next != head) {
            p = p.next;
            System.out.println(p.item);
        }
    }
 
 
    /**
     * 删除从头结点开始的第index个结点
     * index从0开始
     *
     * @param index
     * @return
     */
    public int remove(int index) {
        checkPosIndex(index);
 
        /********** Begin *********/
          Node f = head;
            while ((index--) > 0) {
                f = f.next;
            }
            Node del = f.next;
            if (del == tail) {
                tail = f;
            }
            f.next = del.next;
            del.next = null;
            int oldVal = del.item;
            del = null;
            --size;
            return oldVal;
 
 
 
        /********** End *********/
    }
 
    public boolean isEmpty() {
        return head.next == head;
    }
 
    public int size() {
        return size;
    }
 
    private void checkPosIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
 
    //结点内部类
    private static class Node {
        int item;
        Node next;
 
        Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}
 
 

第3关：双向循环链表的实现—链表的插入
 

package step3;
 
/**
 * Created by sykus on 2018/1/15.
 */
public class MyDoubleLinkedList {
 
    private Node head;//头结点
    private Node tail;//指向链表的尾结点
    private int size;
 
    public MyDoubleLinkedList() {
        head = new Node(null, Integer.MIN_VALUE, null);
        head.next = head.prev = head;
        tail = head;
        size = 0;
    }
 
    /**
     * 添加元素到表尾
     *
     * @param item
     */
    public void add(int item) {
 
        /********** Begin *********/
        Node newNode = new Node(null, item, null);
            tail.next = newNode;
            newNode.prev = tail;
            newNode.next = head;
            head.prev = newNode;
            tail = newNode;
            ++size;
 
 
 
        /********** End *********/
 
    }
 
    /**
     * 打印双向链表
     *
     * @param flag true从左向右顺序打印, false从右向左顺序打印
     */
    public void printList(boolean flag) {
        Node f = head;
        if (flag) {//向右
            while (f.next != head) {
                f = f.next;
                System.out.print(f.item + " ");
            }
        } else {//向左
            while (f.prev != head) {
                f = f.prev;
                System.out.print(f.item + " ");
            }
        }
    }
 
    public int size() {
        return size;
    }
 
    //结点内部类
    private static class Node {
        int item;
        Node next;//直接后继引用
        Node prev;//直接前驱引用
 
        Node(Node prev, int item, Node next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
}

 
 

第4关：双向循环链表的实现—链表的删除文章来源地址https://www.toymoban.com/news/detail-736401.html
 

package step4;
 
/**
 * Created by sykus on 2018/1/15.
 */
public class MyDoubleLinkedList {
 
    private Node head;//头结点
    private Node tail;//指向链表的尾结点
    private int size;
 
    public MyDoubleLinkedList() {
        head = new Node(null, Integer.MIN_VALUE, null);
        head.next = head.prev = head;
        tail = head;
        size = 0;
    }
 
    /**
     * 添加元素到表尾
     *
     * @param item
     */
    public void add(int item) {
        Node newNode = new Node(null, item, null);
        tail.next = newNode;
        newNode.prev = tail;
        newNode.next = head;
        head.prev = newNode;
        tail = newNode;
        ++size;
    }
 
    /**
     * 删除指定位置index出的结点，并返回其值
     *
     * @param index
     * @return
     */
    public int remove(int index) {
        checkPosIndex(index);//
 
        /********** Begin *********/
         Node p = head.next;
            while ((index--) > 0) {
                p = p.next;
            }
            if (p == tail) {
                tail = p.prev;
            }
            p.prev.next = p.next;
            p.next.prev = p.prev;
            int val = p.item;
            p = null;
            --size;
            return val;
 
 
        
 
        /********** End *********/
    }
 
    /**
     * 打印双向链表
     *
     * @param flag true从左向右顺序打印, false从右向左顺序打印
     */
    public void printList(boolean flag) {
        Node f = head;
        if (flag) {//向右
            while (f.next != head) {
                f = f.next;
                System.out.print(f.item + " ");
            }
        } else {//向左
            while (f.prev != head) {
                f = f.prev;
                System.out.print(f.item + " ");
            }
        }
    }
 
    public int size() {
        return size;
    }
 
    private void checkPosIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
 
    //结点内部类
    private static class Node {
        int item;
        Node next;//直接后继引用
        Node prev;//直接前驱引用
 
        Node(Node prev, int item, Node next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }
}
 
                    
到了这里，关于第1关：单循环链表的实现—链表的添加、遍历任务描述相关知识单循环链表添加操作遍历循环链表编程要求测试说明任务描述在操作单链表时，的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

                

                

                                                

                   

                       
                            
                            
                            
                            
                    
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

                

                                

                    
分享到：

                    领支付宝红包
                    赞助服务器费用
                

                            

            

		        
相关文章

			    
			

        

                
    

    



    
觉得文章有用就打赏一下文章作者



    
支付宝扫一扫打赏

    
博客赞助





    
微信扫一扫打赏

    
请作者喝杯咖啡吧~博客赞助











    
支付宝扫一扫领取红包，优惠每天领

	

	    
二维码1

	    
领取红包

	

	

	    
二维码2

	    
领红包