数据结构使用作业

Yes12 · 发表于 2023-11-20 09:04

public class RecType {
int key;
String data;
public RecType(int d)
{ key=d; }
}
class SqListSortClass {
final int MAXN = 100;
RecType[] R;
int n;
public void swap(int i, int j) {
      RecType tmp = R[i];
      R[i] = R[j];
      R[j] = tmp;
}
public void CreateR(int[] a) {
      R = new RecType[MAXN];
      for (int i = 0; i < a.length; i++)
         R[i] = new RecType(a[i]);
      n = a.length;
}
public void Disp() {
      for (int i = 0; i < n; i++)
         System.out.print(R[i].key + "");
      System.out.println();
}
public void CreateR1(int[] a) {
      R = new RecType[MAXN];
      for (int i = 0; i < a.length; i++)
         R[i + 1] = new RecType(a[i]);
      n = a.length;
}
public void Disp1() {
      for (int i = 1; i <= n; i++)
         System.out.print(R[i].key + "");
      System.out.println();
}
public void InsertSort() {
      RecType tmp;
      int j;
      for (int i = 1; i < n; i++) {
         if (R[i].key < R[i - 1].key) {
            tmp = R[i];
            j = i - 1;
            do {
                  R[j + 1] = R[j];
                  j--;
            } while (j >= 0 && R[j].key > tmp.key);
            R[j + 1] = tmp;
         }
      }
}
public void BinInsertSort() {
      int low, high, mid;
      RecType tmp;
      for (int i = 1; i < n; i++) {
         if (R[i].key < R[i - 1].key) {
            tmp = R[i];
            low = 0;
            high = i - 1;
            while (low <= high) {
                  mid = (low + high) / 2;
                  if (tmp.key < R[mid].key)
                     high = mid - 1;
                  else
                     low = mid + 1;
            }
            for (int j = i - 1; j >= high + 1; j--)
                  R[j + 1] = R[j];
            R[high + 1] = tmp;
         }
      }
}
public void ShellSort() {
      RecType tmp;
      int d = n / 2;
      while (d > 0) {
         for (int i = d; i < n; i++) {
            tmp = R[i];
            int j = i - d;
            while (j >= 0 && tmp.key < R[j].key) {
                  R[j + d] = R[j];
                  j = j - d;
            }
            R[j + d] = tmp;
         }
         d = d / 2;
      }
}
public void BubbleSort() {
      boolean exchange = false;
      for (int i = 1; i < n - 1; i++) {
         exchange = false;
         for(int j = n - 1; j > i; j--)
            if (R[j].key < R[j - 1].key) {
                  swap(j, j - 1);
                  exchange = true;
            }
         if (!exchange) return;
      }
}
}
class S686{
public static void main(String[] arge){
      SqListSortClass ssc=new SqListSortClass();
      int[] date ={6,3,9,5,4,6,8,7,5,2,4};
      ssc.CreateR(date);
      ssc.Disp();
      ssc.InsertSort();
      ssc.Disp();
}
}

backaxe · 发表于 2023-11-24 08:55

[Java] 纯文本查看 复制代码

// 定义一个记录类型 RecType，包含键（key）和数据（data）
public class RecType {
    int key;
    String data;

    // 构造器，只初始化 key
    public RecType(int d) {
        key = d;
    }
}

// 定义一个排序类，包含排序相关的方法
class SqListSortClass {
    final int MAXN = 100; // 定义最大元素数量
    RecType[] R; // 存储 RecType 对象的数组
    int n; // 实际存储的元素数量

    // 交换数组中的两个元素
    public void swap(int i, int j) {
        RecType tmp = R[i];
        R[i] = R[j];
        R[j] = tmp;
    }

    // 创建排序数组，从整型数组 a 中初始化
    public void CreateR(int[] a) {
        R = new RecType[MAXN];
        for (int i = 0; i < a.length; i++)
            R[i] = new RecType(a[i]);
        n = a.length;
    }

    // 打印排序数组的键值
    public void Disp() {
        for (int i = 0; i < n; i++)
            System.out.print(R[i].key + "");
        System.out.println();
    }

    // 创建排序数组的另一个版本，偏移一位开始存储
    public void CreateR1(int[] a) {
        R = new RecType[MAXN];
        for (int i = 0; i < a.length; i++)
            R[i + 1] = new RecType(a[i]);
        n = a.length;
    }

    // 打印排序数组键值的另一个版本，从 1 开始打印
    public void Disp1() {
        for (int i = 1; i <= n; i++)
            System.out.print(R[i].key + "");
        System.out.println();
    }

    // 插入排序算法
    public void InsertSort() {
        RecType tmp;
        int j;
        for (int i = 1; i < n; i++) {
            if (R[i].key < R[i - 1].key) {
                tmp = R[i];
                j = i - 1;
                do {
                    R[j + 1] = R[j];
                    j--;
                } while (j >= 0 && R[j].key > tmp.key);
                R[j + 1] = tmp;
            }
        }
    }

    // 二分插入排序算法
    public void BinInsertSort() {
        int low, high, mid;
        RecType tmp;
        for (int i = 1; i < n; i++) {
            if (R[i].key < R[i - 1].key) {
                tmp = R[i];
                low = 0;
                high = i - 1;
                while (low <= high) {
                    mid = (low + high) / 2;
                    if (tmp.key < R[mid].key)
                        high = mid - 1;
                    else
                        low = mid + 1;
                }
                for (int j = i - 1; j >= high + 1; j--)
                    R[j + 1] = R[j];
                R[high + 1] = tmp;
            }
        }
    }

    // 希尔排序算法
    public void ShellSort() {
        RecType tmp;
        int d = n / 2;
        while (d > 0) {
            for (int i = d; i < n; i++) {
                tmp = R[i];
                int j = i - d;
                while (j >= 0 && tmp.key < R[j].key) {
                    R[j + d] = R[j];
                    j = j - d;
                }
                R[j + d] = tmp;
            }
            d = d / 2;
        }
    }

    // 冒泡排序算法
    public void BubbleSort() {
        boolean exchange = false;
        for (int i = 1; i < n - 1; i++) {
            exchange = false;
            for(int j = n - 1; j > i; j--)
                if (R[j].key < R[j - 1].key) {
                    swap(j, j - 1);
                    exchange = true;
                }
            if (!exchange) return;
        }
    }
}

TL1ng · 发表于 2023-11-20 13:19

如果有解释就更好了

TL1ng · 发表于 2023-11-20 13:38

本帖最后由 TL1ng 于 2023-11-20 13:39 编辑

public class RecType { int key; // 键值 String data; // 数据 public RecType(int d) { key = d; }}class SqListSortClass { final int MAXN = 100; // 最大容量 RecType[] R; // 用于存储记录的数组 int n; // 记录的数量 public void swap(int i, int j) { RecType tmp = R; R = R[j]; R[j] = tmp; } public void CreateR(int[] a) { R = new RecType[MAXN]; for (int i = 0; i < a.length; i++) R = new RecType(a); n = a.length; } public void Disp() { for (int i = 0; i < n; i++) System.out.print(R.key + " "); System.out.println(); } public void CreateR1(int[] a) { R = new RecType[MAXN]; for (int i = 0; i < a.length; i++) R[i + 1] = new RecType(a); n = a.length; } public void Disp1() { for (int i = 1; i <= n; i++) System.out.print(R.key + " "); System.out.println(); } public void InsertSort() { RecType tmp; int j; for (int i = 1; i < n; i++) { if (R.key < R[i - 1].key) { tmp = R; j = i - 1; do { R[j + 1] = R[j]; j--; } while (j >= 0 && R[j].key > tmp.key); R[j + 1] = tmp; } } } public void BinInsertSort() { int low, high, mid; RecType tmp; for (int i = 1; i < n; i++) { if (R.key < R[i - 1].key) { tmp = R; low = 0; high = i - 1; while (low <= high) { mid = (low + high) / 2; if (tmp.key < R[mid].key) high = mid - 1; else low = mid + 1; } for (int j = i - 1; j >= high + 1; j--) R[j + 1] = R[j]; R[high + 1] = tmp; } } } public void ShellSort() { RecType tmp; int d = n / 2; while (d > 0) { for (int i = d; i < n; i++) { tmp = R; int j = i - d; while (j >= 0 && tmp.key < R[j].key) { R[j + d] = R[j]; j = j - d; } R[j + d] = tmp; } d = d / 2; } } public void BubbleSort() { boolean exchange = false; for (int i = 1; i < n - 1; i++) { exchange = false; for(int j = n - 1; j > i; j--) if (R[j].key < R[j - 1].key) { swap(j, j - 1); exchange = true; } if (!exchange) return; } }}class S686 { public static void main(String[] arge) { SqListSortClass ssc = new SqListSortClass(); int[] date = {6, 3, 9, 5, 4, 6, 8, 7, 5, 2, 4}; ssc.CreateR(date); ssc.Disp(); ssc.InsertSort(); ssc.Disp(); }}
这段代码主要是实现了一个排序算法的类 SqListSortClass ，其中包含了几种不同的排序算法的实现，以及一个测试类 S686 。下面是对每个类和方法的详细注释： - RecType 类：表示记录类型，包含一个键值 key 和一个数据 data 。它有一个构造函数 RecType(int d) 用于初始化键值。 - SqListSortClass 类：排序算法类，包含以下方法： - swap(int i, int j) ：交换数组中索引为 i 和 j 的元素。 - CreateR(int[] a) ：根据给定的整数数组 a 创建记录数组 R ，将数组中的每个元素转换为 RecType 类型的对象，并将记录数量 n 设置为数组长度。 - Disp() ：打印记录数组 R 中的键值。 - CreateR1(int[] a) ：类似于 CreateR() 方法，但是将记录数组的索引从1开始。 - Disp1() ：类似于 Disp() 方法，但是从索引1开始打印记录数组的键值。 - InsertSort() ：插入排序算法实现，将记录数组 R 按照键值从小到大进行排序。 - BinInsertSort() ：二分插入排序算法实现，将记录数组 R 按照键值从小到大进行排序。 - ShellSort() ：希尔排序算法实现，将记录数组 R 按照键值从小到大进行排序。 - BubbleSort() ：冒泡排序算法实现，将记录数组 R 按照键值从小到大进行排序。 - S686 类：测试类，包含 main() 方法用于创建一个 SqListSortClass 对象并测试插入排序算法的功能。

Yes12 · 发表于 2023-11-20 16:47

TL1ng 发表于 2023-11-20 13:19
如果有解释就更好了

我忘记写注释了

帐号		自动登录	找回密码
密码			注册[Register]

[Java 原创] 数据结构使用作业

个人中心