春风博客

春天里,百花香...

导航

<2008年6月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

统计

公告

MAIL: junglesong@gmail.com
MSN: junglesong_5@hotmail.com

Locations of visitors to this page

常用链接

留言簿(11)

随笔分类(224)

随笔档案(126)

个人软件下载

我的其它博客

我的邻居们

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

整形数组实用类,用于求两数组的并交差集

package com.sitinspring;

/**
 * 整形数组实用类,能求两数组的并交差集,不借助于集合类
 * 
@author: sitinspring(junglesong@gmail.com)
 * @date: 2008-6-24-下午10:13:33
 
*/

public final class IntegerArrayUtil{
    
// 私有构造函数,防止创建IntegerArrayUtil的实例
    private IntegerArrayUtil(){
        
    }

    
    
/**
     * 取得两数组并集
     * 
@param arr1
     * 
@param arr2
     * 
@return
     
*/

    
public static int[] union(int[] arr1,int[] arr2){
        DynamicArray dynamicArray
=new DynamicArray();
        
        
for(int temp:arr1){
            dynamicArray.add(temp);
        }

        
        
for(int temp:arr2){
            
if(!exist(temp,arr1)){
                dynamicArray.add(temp);
            }

        }

        
        
return dynamicArray.getArr();
    }

    
    
/**
     * 取得两数组交集
     * 
@param arr1
     * 
@param arr2
     * 
@return
     
*/

    
public static int[] intersact(int[] arr1,int[] arr2){
        DynamicArray dynamicArray
=new DynamicArray();
        
        
for(int temp:arr1){
            
if(exist(temp,arr2)){
                dynamicArray.add(temp);
            }

        }

        
        
return dynamicArray.getArr();
    }

    
    
/**
     * 取得两数组差集
     * 
@param arr1
     * 
@param arr2
     * 
@return
     
*/

    
public static int[] minus(int[] arr1,int[] arr2){
        DynamicArray dynamicArray
=new DynamicArray();
        
        
for(int temp:arr1){
            
if(!exist(temp,arr2)){
                dynamicArray.add(temp);
            }

        }

        
        
return dynamicArray.getArr();
    }

    
    
/**
     * 判断number在数组arr中是否存在
     * 
@param number
     * 
@param arr
     * 
@return
     
*/

    
private static boolean exist(int number,int[] arr){
        
for(int temp:arr){
            
if(number==temp){
                
return true;
            }

        }

        
        
return false;
    }

    
    
/**
     * 显示数组元素
     * 
@param arr
     
*/

    
private static void display(int[] arr){
        
for(int temp:arr){
            System.out.print(temp
+",");
        }

        
        System.out.println();
    }

    
    
public static void main(String[] args){
        
int[] arr1={1,2,3,4,5,0,-1,-2,-3,-4,-5,};
        
int[] arr2={6,2,7,4,8,0,-1,-2,};

        System.out.print(
"数组arr1为");
        display(arr1);
        System.out.print(
"数组arr2为");
        display(arr2);
        System.out.print(
"arr1和arr2的并集为");
        display(IntegerArrayUtil.union(arr1, arr2));
        System.out.print(
"arr1和arr2的交集为");
        display(IntegerArrayUtil.intersact(arr1, arr2));
        System.out.print(
"arr1和arr2的差集为");
        display(IntegerArrayUtil.minus(arr1, arr2));
    }

}

输出:
数组arr1为1,2,3,4,5,0,-1,-2,-3,-4,-5,
数组arr2为6,
2,7,4,8,0,-1,-2,
arr1和arr2的并集为1,
2,3,4,5,0,-1,-2,-3,-4,-5,6,7,8,
arr1和arr2的交集为2,
4,0,-1,-2,
arr1和arr2的差集为1,
3,5,-3,-4,-5,

动态数组类:
package com.sitinspring;

/**
 * 动态数组类,以数组为数据容器实现动态数组的功能
 * 
@author: sitinspring(junglesong@gmail.com)
 * @date: 2008-6-23-下午10:08:09
 
*/

public class DynamicArray {
    
/** *//**
     * 用于存储数据的数组
     
*/

    
private int[] arr;

    
/** *//**
     * 初始化大小
     
*/

    
private static final int initSize = 10;

    
/** *//**
     * 当前元素个数
     
*/

    
private int currItemsCount = 0;

    
/** *//**
     * 构造函数一,固定大小
     
*/

    
public DynamicArray() {
        arr 
= new int[initSize];
    }

    
    
/** *//**
     * 构造函数二,指定大小
     
*/

    
public DynamicArray(int len) {
        arr 
= new int[len];
    }


    
/** *//**
     * 取得位置在i的元素
     
*/

    
public int get(int i) {
        
if (i < currItemsCount) {
            
return arr[i];
        }


        
return -999;
    }


    
/** *//**
     * 取得数组中已有元素的个数
     * 
@return
     
*/

    
public int size() {
        
return currItemsCount;
    }


    
/** *//**
     * 添加一个元素到数组
     * 
@param number
     
*/

    
public void add(int number) {
        
if (currItemsCount >= arr.length) {
            
int[] arrNew = new int[arr.length * 2];
            
for (int i = 0; i < arr.length; i++{
                arrNew[i] 
= arr[i];
            }


            arr 
= arrNew;
        }


        arr[currItemsCount] 
= number;
        currItemsCount
++;
    }


    
/** *//**
     * 删除位置在i的元素
     * 
@param removeIndex
     
*/

    
public void remove(int removeIndex) {
        
if (removeIndex < arr.length) {
            
if (removeIndex > currItemsCount) {
                
int[] arrNew = new int[arr.length - 1];
                
for (int j = 0; j < arrNew.length; j++{
                    arrNew[j] 
= arr[j];
                }


                arr 
= arrNew;
            }
 else {
                
int[] arrNew = new int[arr.length - 1];
                
for (int j = 0; j < removeIndex; j++{
                    arrNew[j] 
= arr[j];
                }


                
for (int j = removeIndex + 1; j < arr.length; j++{
                    arrNew[j 
- 1= arr[j];
                }

                currItemsCount
--;
                arr 
= arrNew;
            }

        }

    }


    
/** *//**
     * 取得添值部分的数组
     * 
@return
     
*/

    
public int[] getArr() {
        
int[] arrNew = new int[currItemsCount];

        
for (int i = 0; i < arrNew.length; i++{
            arrNew[i] 
= arr[i];
        }


        
return arrNew;
    }

    
    
/** *//**
     * 取得已排序的数组
     * 
@return
     
*/

    
public int[] getSortedArr(){
        
int[] arrSorted = getArr();
        insertSort(arrSorted);
        
return arrSorted;
    }


    
/** *//**
     * 进行插入排序
     * 
@param arr
     
*/

    
private static void insertSort(int[] arr) {
        
int i, temp;
        
// 插入位置
        int insertPos;
        
for (i = 1; i < arr.length; i++{
            
// 当前需要进入已排序队列的项
            temp = arr[i];
            insertPos 
= i;

            
// 向右移动
            while (0 < insertPos && arr[insertPos - 1>= temp) {
                arr[insertPos] 
= arr[insertPos - 1];
                
--insertPos;
            }


            
// 当前项该处于的位置
            arr[insertPos] = temp;
        }

    }


    
/** *//**
     * 显示添值部分的数组
     *
     
*/

    
public void display() {
        System.out.print(
"现有元素有:");
        
for (int i = 0; i < currItemsCount; i++{
            System.out.print(arr[i] 
+ ",");
        }

        System.out.print(
"\n");
    }


    
/** *//**
     * 显示数组的所有子元素,包括添值和未添值部分
     *
     
*/

    
public void displayAll() {
        System.out.print(
"所有元素有:");
        
for (int i = 0; i < arr.length; i++{
            System.out.print(arr[i] 
+ ",");
        }

        System.out.print(
"\n");
    }


    
/** *//**
     * 程序入口
     * 
@param args
     
*/

    
public static void main(String[] args) {
        DynamicArray dArray 
= new DynamicArray(12);

        dArray.add(
1);
        dArray.add(
2);
        dArray.add(
3);
        dArray.add(
4);
        dArray.add(
5);
        dArray.display();
        dArray.displayAll();

        dArray.add(
6);
        dArray.add(
7);
        dArray.add(
8);
        dArray.add(
9);
        dArray.add(
10);
        dArray.display();
        dArray.displayAll();

        dArray.add(
11);
        dArray.add(
12);
        dArray.add(
13);
        dArray.add(
14);
        dArray.add(
15);
        dArray.display();
        dArray.displayAll();

        dArray.remove(
3);
        dArray.display();
        dArray.displayAll();

        dArray.remove(
0);
        dArray.display();
        dArray.displayAll();

        dArray.remove(
10);
        dArray.display();
        dArray.displayAll();

        dArray.add(
2);        
        dArray.add(
3);
        dArray.add(
4);
        dArray.add(
3);
        dArray.add(
4);
        
        dArray.display();
        System.out.print(
"已排序数组元素為:");
        
int[] arr = dArray.getSortedArr();
        
for (int i = 0; i < arr.length; i++{
            System.out.print(arr[i] 
+ ",");
        }

        System.out.print(
"\n");
    }

}

posted on 2008-06-24 22:51 sitinspring 阅读(1201) 评论(0)  编辑  收藏 所属分类: Java基础算法数据结构


只有注册用户登录后才能发表评论。


网站导航:
 
sitinspring(http://www.blogjava.net)原创,转载请注明出处.