【数据结构】之循环链表

将单链表中终端节点的指针端由空指针改为指向头结点,形成一个环,这种头尾相接的单链表成为(单)循环链表。

循环链表不一定要有头结点。

循环链表与单链表的主要差异:在判断空链表的条件上:原来判断head.next()是否为null;现在需要判断reat.next是否等于rear。

循环链表不是用头指针,而是用尾(rear)指针来表示循环链表。

两个单循环链表的链接:

①断开A链表中尾指针指向头指针的环

②令A链表的的尾指针指向B链表的第一个结点

③将B链表的头结点释放

④令B链表的尾指针指向A链表的头结点。

  • 判断单链表中是否有环:链表的尾结点指向了链表中的某个结点。

方法一:

使用两个指针,p和q,p每次都往前走一步,而q每次都从头开始走到p所在的位置。如果不存在环,则p累计走的步数和q当次走的步数应该是一样的。如果不一样了,出现p步数大于q步数的情况,则存在环。

方法二:

快慢指针:使用p/q两个指针,p每次向前走一步,q每次向前走两步,若在某个时刻p==q,则存在环。

发表在 数据结构与算法 | 标签为 | 留下评论

【Java】J2SE学习笔记(三):字符串

*计算int型数据的位数:先将int型转为String类型(String.valueOf(int));然后再调用string.length()。

*使用split划分字符串,存储在String数组中:

String s ="Msds,weds,dsa";
String[] split = s.split(",");

*计算字符串中有多少"java":

public class TestString2{
    public static void main(String args[]){
        String s = "javasunjavaheljavajavalojavajagoodjavajava";
        String stringToFind = "java";
        int index = -1;
        int count = 0;
        while((index = s.indexOf(stringToFind))!=-1){
            count++;
            s = s.substring(index + stringToFind.length());
        }
        System.out.println(count+"java");
    }
}

*String和StringBuffer的区别:

String代表不可变的字符串序列;StringBuffer代表可变的字符串序列。

例如:在做字符串连接运算时: s1 += s2;在String中,内存这样执行:首先开辟一块内存区域,大小为s1+s2,再把s1,s2按顺序复制到新开辟的内存中,再令s1指向这块新内存。而StringBuffer则可以直接做连接:直接在s1后面开辟空间,不用做copy了。

StringBuffer可以直接append、delete、insert、reverse。

*将字符串数组解析为double数组:

 public class ArrayParser{
    public static void main(String args[]){
        double[][] d ;
        String s = "1,2;3,4,5;6,7,8";
        String[] sFirst = s.split(";");
        d = new double[sFirst.length][];
        for(int i=0;i<</span>sFirst.length;i++){
            String[] sSecond = sFirst[i].split(",");
            d[i] =new double[sSecond.length];
            for(int j=0;j<</span>sSecond.length;j++){
                d[i][j] = Double.parseDouble(sSecond[j]);
                System.out.println(d[i][j]);
            }
        }
        for (int i=0;i<</span>d.length;i++){
            for(int j=0;j<</span>d[i].length;j++){
                System.out.print(d[i][j]);
                System.out.print("  ");
            }
            System.out.println();
        }
    }
}

发表在 Java技术 | 标签为 , , | 留下评论

【软件开发】Head First 软件开发

1、不可采用一步到位式开发,应采取多个开发循环周期,每个循环包括需求、设计、编码、测试,每个循环都应有产品与客户进行沟通交流,以确定方向。

2、不断与客户交流,确认和细化客户需求。将客户需求和使用情节以其易于理解的方式进行逐条展现,双方进行确定,消除存在的假设,以免造成后续开发的风险。根据客户需求,估计开发耗时,合理确定完成所有需求的耗时。

3、与客户一起进行优先级的制定,合理规划里程碑构建版本所包含的功能内容,里程碑构建版本应尽早实现,然后不断迭代增加新功能。在确定优先级之后,根据优先级和每个需求的所需开发时间来进行开发循环的制定。

4、使用白板以良好的跟踪项目的工作和进度,观察各个任务标签是处于进行中还是已完成的状态,优先级、预估时间、负责开发的人等等信息。同时,跟踪整个项目的进展情况,为意想不到的开发任务预留合理的时间。

5、进行良好的设计,遵循单一责任原则,每一个对象都应该集中在实现与其相关的单一的责任上。同时也应该遵守不自我重复原则,避免通过把共同事物抽取或分离出来,以及把它们置于同一地方来复制代码。合理使用白板,进行项目任务分工和进度跟踪。

6、使用版本控制来跟踪软件的修改并分发给团队成员。使用标记Tags去跟踪项目的里程碑版本(某个开发循环的结束、发布版本、漏洞修复版本等等)。标记是对某一个版本的代码的快照,代码不可以提交到标记上。另外,使用分支branches去维护代码的独立副本,但只在绝对有必要的情况下开设分支。为软件增加新功能的任务,主要放在主干当中。当某一个版本发布之后,需要对该版本的代码进行持续维护和漏洞修复,但又不能影响主干继续开发新的功能,所以可将这个发布的版本再建里一个分支,进行漏洞修复。分支在未来的某一天将最终被丢弃,分支当中修复的漏洞需要合并到主干代码当中。

7、运用自动化构建工具,比如makefile使用的Makefile脚本,java构建工具ant使用的build.xml。

8、测试主要包括三种类型。黑箱测试:站在用户角度,进行功能性测试,关心程序的输入和输出,状态转换,边界案例和缓冲溢出错误等等。灰箱测试:除了做一些功能性的测试,还会进入一部分程序中,比如查询当前数据库内容等。白箱测试:完全了解代码结构和逻辑,针对代码情况做测试。JUnit可以提供Java程序的自动化测试。运用持续集成工具CI,自动管理代码提交和版本控制,程序构建和自动化测试,并通过邮件告知构建和测试情况,并生成网页以供查询。CruiseControl就是一个典型的CI工具。同时,CI生成的报告也会包含测试覆盖率的参数。

9、测试驱动开发,先根据要完成的某项功能编写测试代码,然后实现最简单的程序代码以使得测试代码可以正常运行。不断依此重复,直到实现整个程序的所有功能。可以使用Mock模拟对象来提供测试所需要的各种对象的变化。

10、在结束开发循环之时,要合理进行系统测试,并记录下发现的错误,生成缺陷单,标志为待修复、已修复、已验证、已关闭、重新打开等,以方便查看错误处理和修复情况。缺陷单应详细记录错误问题,复现方法,严重程度,优先级以及预期正确的效果等。开源的错误记录软件有Bugzilla和Mantis。

发表在 软件开发 | 标签为 | 一条评论

【Java】设计模式

1、策略模式

2、观察者模式

3、装饰者模式

4、工厂方法模式和抽象工厂模式

5、单例模式

6、命令模式

7、适配器模式和外观模式

发表在 Java技术 | 标签为 , | 留下评论

【Java】Object当中函数的作用

equals()函数:

在Java当中可以使用==操作符来判断两个基本数据类型的变量的值是否相等,而对于引用类型变量,例如对象而言,使用==是判断两个引用是否指向堆内存当中的同一块地址。

对于对象是否相等应该使用equals()函数。该函数定义于Object类当中,但是该类当中的equals()方法仅仅是直接比较了两个对象的引用是否指向堆内存当中的同一块地址,即与==运算符的功能是一样的。所以在自己定义的类当中,应该覆写equals()函数。

一般而言,判断两个对象是否相同的主要依据有两个,在某些情况下可能判断相等的标准比较特殊:

  1. 两个对象是否是相同类型的对象;

  2. 两个对象当中的成员变量的值是否相同;

class User{
    String name;
    int age;
    
    public boolean equals(Object obj){
    	if(this==obj) return true;//先判断两个引用是否指向同一块堆内存地址
    	if(!obj instanceof User) return false;//判断类型是否相同
    	else{
    		User user = (User)obj;
    		if(this.age==user.age && this.name.equals(user.name))//判断成员变量是否相同
    			return true;
    		else
    			return false;
    	}
    }
}

hashCode()函数:

hashCode()函数用于返回某个对象的hash值,对于调用equals()函数判断为相等的两个对象,其返回的hash值也应该相等。例如:

public int hashCode(){
    int result = 17;//任意一个正质数
    
    result = 31 * result + age;
    result = 31 * result + name.hashCode();
    
    return result;
}

toString()函数:

toString()函数用于将对象转换成String字符串,以便程序有更好的可读性。例如:

User user = new User();
System.out.println(u);

此时就会调用user对象的toString()方法。可以自己定义toString()方法,例如:

public String toString(){
    String result = "age:" + age + ",name:" + name;
    return result;
}

发表在 Java技术 | 标签为 , | 留下评论

【Java】类集框架

类集框架-容器类

位于java.util包中,用于存储和管理对象。

主要分为三大类-集合、列表和映射。

集合Set-对象无序,无重复对象

列表List-对象按照索引位置排序,可以有重复对象

映射Map-每一个元素包含一个键对象和一个值对象,键对象不可以重复,值对象可以重复

ArrayList<String> arrayList = new ArrayList<String>();

arrayList.add("a");
arrayList.add("b");
arrayList.add("c");
arrayList.add("d");

arrayList.remove(1);
arrayList.size();
arrayList.get(1);

Collection接口中的主要方法(Set、List的父类)

add(Object o);

remove(Object o);

clear();

isEmpty();

size();

Iterator接口中的主要方法

hasNext();

next();

Iterator -> Collection -> Set -> HashSet;

Set<String> set = new HashSet<String>();
set.add("a");
set.add("b");
set.add("c");
set.add("d");
Iterator<String> it = set.iterator();
while(it.hasNext()){
    String s = it.next();
    System.out.println(s);
}

映射Map<K,V>,如果键已经存在,新的值将覆盖原来的值。

发表在 Java技术 | 标签为 , | 留下评论

【Java】数组

静态声明:

int arr [] = {5,1,2};

动态声明:

int arr [] = new int[10];

数组长度:

arr.length

起始下标为0

元素默认值

int数组:0

boolean数组:false

char数组:空字符\0

数组遍历:

for循环

二维数组:

静态定义方法:

int arr [][] = {{1,2,3},{4,5,6},{7,8,9}};

二维数组当中的元素,即各个一维数组可以不等长。

int arr [][] = {{1,2,3},{4,5,6},{7,8}};

Java允许各个一维数组不等长,且不会自动补齐到等长。

动态定义方法:

int arr [][] = new int[3][5];

发表在 Java技术 | 标签为 , | 留下评论

【Java】线程

创建线程的方法

方法一:

定义一个线程类,继承Thread类,并覆写其中的run()方法。run()方法称为线程体。

然后创建一个线程类的对象,调用它的start()方法,即可产生新线程进行执行。

如果直接调用run()方法,那么就在当前线程中运行,并未产生新的线程。

方法二:

产生一个实现Runnable接口的类,覆写其中的run()方法,然后将该实现Runnable接口的类的对象用来构造一个Thread对象,然后调用Thread的start()方法。

线程的简单控制

中断线程:

Thread.sleep();//休眠,会抛出异常,需要做try…catch

Thread.yield();//当前线程让出CPU,然后包括当前线程在内的各线程再次竞争CPU

线程优先级:

getPriority();

setPriority();

线程的优先级为1-10

静态常量:

MAX_PRIORITY 最大优先级,数值为10

MIN_PRIORITY 最小优先级,数值为1

线程名称:

Thread.setName();

Thread.getName();

获取当前执行的线程:

Thread.currentThread();

线程同步:

多线程访问公用的数据时,有可能会产生错误,这时需要线程同步。

线程同步方法,同步代码块:

synchronized(Object){
    //需要进行同步的代码,在这当中可以对公用的数据进行操作
    //某个线程进行数据修改时,获得this这个同步锁,其他线程无法获得锁,从而无法进行数据访问
}

该同步代码块,表示某段代码锁定在某个对象上。当多个线程中,都有同步代码块锁定在同一个对象上时,第一个执行的线程会获得该对象的占有权,则其他锁定在该对象上的同步代码块就因为没有取得该对象的占有权而无法执行,直到占有该对象的线程同步代码块执行完毕,释放了对该对象的占有权。

同步方法:

synchronized关键字也可以用于修饰成员方法:

public synchronized void fun(){
}

当使用同步方法,相当于整个方法当中的代码都是在同步代码块当中,而此时锁定的对象是this对象,即调用fun()方法的对象。

发表在 Java技术 | 标签为 , | 留下评论

【Java】内部类与匿名内部类

class A{
    int i;
    class B{
        int j;
        int funB(){
            return i+j;
        }
    }
}

这里B就是A的内部类,经过编译之后,生成A.class和A$B.class两个类文件。内部类可以直接使用外部类当中的成员变量和成员函数。每一个内部类对象都与对应的外部类对象相关联。

在外部使用内部类的方法:

class Test{
    public static void main(String args []){
        A a = new A();
        A.B b = a.new B();//A.B b = new A().new B();
        a.i = 1;
        b.j = 3;
        int result = b.funB();//此处的返回值为4
    }
}

匿名内部类的实现

1.实现抽象接口

interface A{
    public void doSomething();
}

2.实现某个类

class B{
    public void fun(A a){
        System.out.println("B类的fun函数");
        a.doSomething();
    }
}

3.在测试文件中进行测试

class Test{
    public static void main(String args []){
        B b = new B();
        b.fun(new A(){
            public void doSomething(){
                System.out.println("匿名内部类");
            }
        });
    }
}

发表在 Java技术 | 标签为 , | 留下评论

【Java】IO系统

IO系统的分类

  1. 输入流和输出流;

  2. 字节流和字符流;

  3. 节点流和处理流;

字节流:读写时以字节为单位,InputStream、OutputStream,都是抽象类。

子类有:FileInputStream、FileOutputStream

核心方法:

int read(byte [] buffer, int offset, int length);
void write(byte [] buffer, int offset, int length);

字符流:读写时以字符为单位,Reader,Writer,都是抽象类。

子类有:FileReader、FileWriter

核心方法:

int read(char [] buffer, int offset, int length);
void write(char [] buffer, int offset, int length);

字节流和字符流在使用时会产生异常,所以要用try…catch…结构来进行捕捉。在finally当中对打开的字节流或者字符流进行关闭。

处理流:例如BufferedReader,里面有readLine函数一次性读取一行内容。

生成BufferedReader对象的方法:

BufferedReader in = new BufferedReader(new FileReader("foo.in"));

构造函数传入的参数是一个Reader对象的引用。这里使用了装饰者的设计模式。

节点流(例如FileReader)是真正读取数据的,而处理流(例如BufferedReader)是对节点流做的装饰者。

发表在 Java技术 | 标签为 , | 留下评论