西南交通大学数据结构实验报告(Java实现版)

忘是亡心i 2023-09-24 13:09 133阅读 0赞

**目录**

一.题目

二.解决

三.测试

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

## 一.题目 ##

> 实验题目：循环队列的分解
> 
> 实验内容及要求：
> 
> 从控制台屏幕循环提供如下菜单:
> 
> 1.  元素入队
> 2.  元素出队
> 3.  显示当前队列元素
> 4.  分解队列
> 5.  退出程序
> 
> 元素入队：输入一个整数，元素入队，队满应提示无法入队；
> 
> 元素出队：显示出队元素，队空应提示出队失败；
> 
> 显示当前队列元素：显示当前队列中所有元素；
> 
> 分解队列：输入一个正整数n(n=2,3,4)，利用原队列元素，将队列分解为n个子队列，
> 
> 第i个子队列含有模n余i的所有元素(i=0,1,2,...,n-1)。利用出队操作在屏幕上打印这n个子队列的元素。若子队列没有元素，显示队空。
> 
> 示例：
> 
> 原队列元素为: 1,2,3,4,5,6,7
> 
> 输入n=3，则输出为
> 
> 原队列：1,2,3,4,5,6,7
> 
> 0号子队列: 3,6
> 
> 1号子队列:1,4,7
> 
> 2号子队列:2,5
> 
> 实验目的：掌握循环队列的基本操作算法。

## 二.解决 ##

package Exercise;
    
    import org.jetbrains.annotations.NotNull;
    
    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            System.out.println("请输入队列的长度");
            Scanner in = new Scanner(System.in);
            int len = in.nextInt();
            Round_robin_queues round_robin_queues = new Round_robin_queues(len+1);
            boolean bool = true;
            while (bool) {
                System.out.println("---------------循环队列的分解---------------");
                System.out.println("1.元素入队");
                System.out.println("2.元素出队");
                System.out.println("3.显示当前队列元素");
                System.out.println("4.分解队列");
                System.out.println("5.退出程序");
                System.out.println("请您选择操作：");
                int choice = in.nextInt();
                switch (choice) {
                    case 1:     //元素入队
                        System.out.println("请输入一个整数入队:");
                        int num = in.nextInt();
                        round_robin_queues.addQueue(num);
                        System.out.println("入队成功!");
                        break;
                    case 2:     //元素出队
                        System.out.println(round_robin_queues.getQueue()+"已成功出队!");
                        break;
                    case 3:     //显示当前队列元素
                        System.out.print("当前队列元素有:");
                        round_robin_queues.show();
                        System.out.println("");
                        break;
                    case 4:     //分解队列
                        System.out.println("您要把队列分解成多少个子队列:");
                        int n = in.nextInt();
                        round_robin_queues.splitQueue(round_robin_queues,n);
                        break;
                    case 5:     //退出程序
                        bool = false;
                        System.out.println("--------正在退出程序--------");
                        break;
                    default:
                        System.out.println("您输入的操作命令不存在！");
                }
            }
        }
    }
    
    class Round_robin_queues {
        private int  maxSize; //数组最大容量
        private int front; // 队列头
        private int rear; //队列尾
        private int[] arr; //队列数组
    
        public Round_robin_queues(int arrMaxSize){//构造器初始化队列
            maxSize = arrMaxSize;
            arr = new int[maxSize];
            front = 0; //头指针
            rear = 0; //尾指针
        }
        //判断队列是否满
        public boolean isFull(){
            return (rear + 1)%maxSize == front;
        }
    
        //判断队列是否为空
        public boolean isEmpty(){
            return rear == front;
        }
    
        //添加数据到队列
        public void addQueue(int n){
            if(isFull()){
                System.out.println("队列已满,无法入队");
            }
            else{
                arr[rear] = n;//直接加入数据
                rear = (rear + 1)% maxSize;//因为循环队列，要考虑模运算
            }
        }
    
        //从队列中取数据
        public String getQueue(){
            String string = "";
            //判断队列是否为空
            if(isEmpty()){
                string = "队列为空，出队失败";
            }
            else{
                //先把front对应的值保存到一个临时变量
                //循环队列，front后移要模运算
                //返回临时变量
                int value = arr[front];
                front = (front + 1) % maxSize;
                string = String.valueOf(value);
            }
            return string;
        }
    
        //计算数组中的有效数据个数
        public int size(){
            return (rear + maxSize - front) %maxSize;
        }
    
        //显示队列数据
        public void show(){
            for (int i = front; i < front + size(); i++) {
                System.out.print(arr[(i+maxSize)%maxSize] + " ");
            }
        }
    
        //分解队列
        public void splitQueue(@NotNull Round_robin_queues round_robin_queues , int n){
            if (round_robin_queues.isEmpty()){
                System.out.println("原队列为空,故每个子队列均为空");
            }
            else {
                Round_robin_queues[] round_robin_queues_list = new Round_robin_queues[n];
    
                //实例化每个子队列
                for (int i = 0 ; i < n ; i++) {
                    round_robin_queues_list[i] = new Round_robin_queues(round_robin_queues.maxSize/n+2);
                }
    
                //输出原队列
                {
                    System.out.print("原队列:");
                    round_robin_queues.show();
                    System.out.println();
                }
    
                //拆分队列
                Round_robin_queues round_robin_queues_split = round_robin_queues;
                int size = round_robin_queues_split.size();
                for (int i = 1 ; i < size+1 ; i++){
                    int index = (i+n) % n;
                    round_robin_queues_list[index].addQueue(Integer.valueOf(round_robin_queues_split.getQueue()));
                }
    
                //将每个子队列输出
                for (int i = 0 ; i < n ; i++){
                    if (round_robin_queues_list[i].isEmpty()) {
                        System.out.println("第" + i + "个子队列为空");
                    }
                    else {
                        System.out.print(i+"号子队列:");
                        round_robin_queues_list[i].show();
                    }
                    System.out.println("");
                }
            }
        }
    }

## 三.测试 ##

![0930181b00134dee8414547795f23457.png][]

[0930181b00134dee8414547795f23457.png]: https://img-blog.csdnimg.cn/0930181b00134dee8414547795f23457.png