1、链表
class Node {
Node next = null;
int data;
/*
* 构造一个节点
*/
public Node(int d){
data = d;
}
/*
* 添加元素d到链表
*/
void appendToTail(int d){
Node end = new Node(d);
Node n = this;
while(n.next != null){
n = n.next;
}
n.next = end;
}
/*
* 从头节点为head的链表删除元素d
*/
Node deleteNode(Node head, int d){
Node n = head;
if(head == null)
return null;
if(head.data == d)
return head.next;
while(n.next != null){
if(n.next.data == d){
n.next = n.next.next;
}
}
return head;
}
}
2、堆栈
/*
* 用链表实现堆栈
*/
class Stack {
//top指向栈顶元素
Node top;
int pop(){
/*
* 如果堆栈非空，将栈顶元素弹出
*/
if(top == null){
return 0;
}
int item = top.data;
top = top.next;
return item;
}
void push(int item){
/*
* 将元素压人堆栈
*/
Node t = new Node(item);
t.next = top;
top = t;
}
Object peek(){
/*
* 返回栈顶元素
*/
return top.data;
}
}
3、队列
/*
* 用链表实现队列
*/
class Queue {
//first指向队列头，end指向队列尾
Node first, last;
//将元素添加进队列
void enqueue(int item){
if(first == null){
last = first = new Node(item);
}else{
last.next = new Node(item);
last = last.next;
}
}
//出队列操作
int dequeue(){
if(first == null){
return 0;
}
int item = first.data;
first = first.next;
return item;
}
}
4、图遍历
class Solution {
/*
class Node {
Node next = null;
int data;
boolean visited;
ArrayList<Node> adjacent;
}
*/
//访问节点
void visit(Node root){
//methods
}
//深度优先搜索,递归实现
void dfs(Node root){
if(root == null)
return;
visit(root);
root.visited = true;
for(Node n : root.adjacent){
if(n.visited == false){
dfs(n);
}
}
}
//广度优先搜索，队列实现
void bfs(Node root){
java.util.Queue<Node> queue = new java.util.LinkedList();
root.visited = true;
visit(root);
queue.add(root);
while(!queue.isEmpty()){
Node r = queue.remove();
for(Node n : r.adjacent){
if(n.visited == false){
n.visited = true;
visit(n);
queue.add(n);
}
}
}
}
}
