高级农民
- 积分
- 3082
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2011-2-22
- 最后登录
- 1970-1-1
|
- class DataSet {
- public int begin;
- public int end;
- public DataSet(int i, int j) {
- begin = i;
- end = j;
- }
- }
- class StackX {
- private int top;
- private int[] stackArray;
- private int size;
- public StackX(int i) {
- top = -1;
- size = i;
- stackArray = new int[size];
- }
- public void push(int i) {
- stackArray[++top] = i;
- }
- public int peek() {
- return stackArray[top];
- }
- public int pop() {
- int temp = stackArray[top--];
- return temp;
- }
-
- public boolean isEmpty() {
- return top == -1;
- }
- }
- class DSArray {
- private DataSet[] DSArr;
- private int num;
- private final int MAX_NUM = 10;
- private int[] elementArr;
- private StackX stackImpl;
- private DataSet[] newDS;
- private int k = 0;
- public DSArray() {
- DSArr = new DataSet[MAX_NUM];
- elementArr = new int[MAX_NUM * 2];
- num = 0;
- stackImpl = new StackX(MAX_NUM);
- }
-
- public void combine() {
- newDS = new DataSet[MAX_NUM];
-
- for (int i = 0; i < num * 2; i++) {
- if (isBegin(elementArr[i])) {
- stackImpl.push(elementArr[i]);
- //System.out.println("The element pushed is: " + elementArr[i]);
- } else {
- int temp = stackImpl.pop();
- if (stackImpl.isEmpty()) {
- //System.out.println("The current number of new data sets is: " + k);
- DataSet ds = new DataSet(temp, elementArr[i]);
- //System.out.print("[" + ds.begin + ", " + ds.end + "]");
- newDS[k++] = ds;
- }
- }
- }
- }
- public void displayNewDS() {
- System.out.println("All the new data sets are: ");
- //System.out.println("The size of newDS[] is: " + newDS.length);
- for (int i = 0; i < k; i++) {
- System.out.print("[" + newDS[i].begin + ", " + newDS[i].end + "]");
- }
- System.out.println();
- }
- public boolean isBegin(int i) {
- for (int j = 0; j < num; j++) {
- if (i == DSArr[j].begin) {
- return true;
- }
- }
- return false;
- }
- public void insert(int b, int e) {
- DataSet ds = new DataSet(b, e);
- DSArr[num++] = ds;
- }
- public void move() {
- int j = 0;
- for (int k = 0; k < num; k++) {
- elementArr[j] = DSArr[k].begin;
- j++;
- elementArr[j] = DSArr[k].end;
- j++;
- }
- }
- public void displayDataSets() {
- System.out.println("All the data sets are: ");
- for (int i = 0; i < num; i++) {
- System.out.print("[" + DSArr[i].begin + ", " + DSArr[i].end + "]");
- System.out.print(" ");
- }
-
- System.out.println();
- }
- public void displayElements() {
- System.out.println("All the elements in datasets are: ");
- for (int a = 0; a < num * 2; a++) {
- System.out.print(elementArr[a] + " ");
- }
- System.out.println();
- }
- public void quickSort(int left, int right) {
- if (left >= right) {
- return;
- } else {
- int pivot = elementArr[right];
- int p = partition(left, right, pivot);
- quickSort(left, p - 1);
- quickSort(p + 1, right);
- }
- }
- public int partition(int left, int right, int pivot) {
- int lptr = left - 1;
- int rptr = right;
- while (true) {
- while (elementArr[++lptr] < pivot) {
- ;
- }
- while (rptr > 0 && elementArr[--rptr] > pivot) {
- ;
- }
- if (lptr >= rptr) {
- break;
- } else {
- swap(lptr, rptr);
- }
- }
- swap(lptr, right);
- return lptr;
- }
- public void swap(int l, int r) {
- int temp;
- temp = elementArr[l];
- elementArr[l] = elementArr[r];
- elementArr[r] = temp;
- }
- }
- public class CombineIntervals {
- public static void main(String[] args) {
-
- int DataSetsNUM = 4;
- DSArray dsa = new DSArray();
- dsa.insert(2, 4);
- dsa.insert(3, 7);
- dsa.insert(1, 7);
- dsa.insert(10, 18);
-
- dsa.displayDataSets();
- dsa.move();
- dsa.quickSort(0, DataSetsNUM * 2 - 1);
- dsa.displayElements();
- dsa.combine();
- dsa.displayNewDS();
- }
- }
复制代码
来个超完整版 |
|