软件测试修炼之路 A Tester

数据结构和算法


数据结构

  1. String/Array/Matrix

常用方法:

toCharArray() //get char array of a String
Arrays.sort()  //sort an array
Arrays.toString(char[] a) //convert to string
charAt(int x) //get a char at the specific index
length() //string length
length //array size 
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf() //string to integer
String.valueOf() //integer to string
  1. 链表

定义:

class Node {
	int val;
	Node next;

	Node(int x){
	val = x;
	next = null;
	}
}

栈(Stack)

class Stack{
	Node top;

	public Node peek(){
		if (top != null){
			return top;
	}

		return null
	}

	public Node pop(){
		if (top == null){
			return null;
		}else{
			Node temp = top;
			top = top.next;
			return temp;
		}

	}

	public void push(Node n){
		if (n != null){
			n.next = top;
			top = n;
		}
	}
}

队列(Queue)

class Queue{
	Node first, last;

	public void enqueue(Node n){
		if(first == null){
			first = n;
			last = first;
		}else{
			last.next = n;
			last = n;
		}

	}

	public Node dequeue(){
		if(first == null){
			return null;
		}else{
			Node temp = new Node(first.val)
			first = first.next;
			return temp;
		}

	}
}

3.树&堆

class TreeNode{
	int value;
	TreeNode left;
	TreeNode right;
}

来自:http://www.csdn.net/article/2014-04-10/2819237-Top-10-Algorithms-for-Coding-Interview

4.Graph

class GraphNode{
	int val;
	GraphNode next;
	GraphNode[] neighbors;
	boolean visited;

	GraphNode(int x){
		val =x;
	}

	GraphNode(int x, GraphNode[] n){
		val = x;
		neighbors = n;
	}

	public String toString(){
		return "value:" + this.val;
	}
}

常用数据结构和算法

http://www.cricode.com/3208.html http://www.cricode.com/2001.html http://www.cricode.com/3212.html http://www.cnblogs.com/liuling/p/2013-7-24-01.html

冒泡排序

public class BubbleSort{
	public static void sort(int[] values){
		int temp;
		for(int i = 0; i < values.length; i++){
			for(int j = 0; j<values.length-i-1; j++){
				if(values[j] > values[j+1]){
					temp = values[j];
					values[j] = values[j+1];
					values[j+1] = temp;
				}
			}
		}
	}
}

插入排序

public class InsertSort{
	public static int[] sort(int[] array){
		for(int i = 1; i < array.length; i++){
			int temp = array[i];
			for(int j = i - 1; j >= 0 && temp < array[j]; j--){
				array[j+1] = array[j];
				array[j] = temp;
			}
		}
	}
}

快速排序

void QuickSort(int s[], int l, int r){
	if(l < r){
		int i = l, j = r, x = s[l];
		while(i < j)
		{
			while(i < j && s[j] >= x)
				j--;
			if(i < j)
				s[i++] = s[j];
			while(i < j && s[i] < x)
				i++;
			if(i < j)
				s[j--] = s[i];
		}
		s[i] = x;
		QuickSort(s, l, i - 1);
		QuickSort(s, i+1, r);
	}
}

Comments