首页 > 基础资料博客日记

Java-基础（数据结构与算法篇）

2024-03-07 02:00:08基础资料围观418次

本篇文章分享Java-基础（数据结构与算法篇），对你有帮助的话记得收藏一下，看Java资料网收获更多编程知识

概念

概念

数据结构（data structure）：数据在计算机中的存储与组织形式；其主要目的是为了对数据进行高效地访问和修改；数据结构包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据结构。

算法（algorithm）：在特定的计算模型下，旨在解决特定问题的一系列指令。

程序 = 数据结构 + 算法

一、时间复杂度

时间复杂度是对一个算法运行时间长短的量度，用大O表示，记作T(n) =O(f(n))

若T(n) = Cn(C为常数)，则执行次数是线性的

若T(n) = Clogn，则执行次数是用对数计算的

若T(n) = C，则执行次数是常量

若T(n) = C1n^2+C2n，则执行次数是用多项式计算

为了解决时间分析的难题，有了渐进时间复杂度的概念，也就是大O表示法；大O表示法简化了时间函数T(n)，让其简化到一个数量级，这个数量级可以n，n²，n³，也就是T(n) =O(n)

大O表示法有以下几个原则：

如果运行时间是常数量级，则用常数1表示

只保留时间函数中的最高阶项

如果最高阶项存在，则会省去最高阶项前面的系数

常见的时间复杂度按照从低到高的顺序：O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等

二、算法度量工具

𝑂(𝑛) 表达算法最坏情况的度量

𝜃(𝑛) 表达算法最好情况的度量

Ω(𝑛) 表达了一个算法的平均值

数组（Array）

一、概念

数组是一种物理上连续，逻辑上也连续的数据结构；是有限个相同数据类型变量所组成的有序集合，数组中的每一个变量或其他类型被称为元素

数组的特点是在内存中顺序存储，可以很好的实现逻辑上的顺序表，但数组的空间大小一旦创建了就不能被改变；正因为是顺序存储所以数组有了下标，这使得查询或更改速度得到了很大的提升，数组按照地址访问，可以在O(1)时间复杂度内完成高校访问

1.静态初始化

静态初始化有两种方式

第一种：数据类型[ ] 数组名 = new 数据类型[ ]{value1,value2,value3, ......}

第二种：数据类型[ ] 数组名 = {value1,value2,value3, ......};

2.动态初始化

数据类型[ ] 变量名 = new 数据类型[长度];

二、基本操作

1、遍历

public static void traverse(int[] arr){
		for(int i = 0;i < arr.length;i++){
			System.out.print(arr[i]+" ");
		}
	}

2、添加

public static void add(int[] arr){
		//当传进来的数组有值时，会将原来的值就行覆盖
		for(int i = 0;i < arr.length;i++){
			arr[i] = i;
		}
	}

3、删除

public static void delete(int index,int[] arr){
		int temp;
		//将后一项的值与前一项的值进行调换，以这种方式来就行删除
		for(int i = index;i < arr.length-1;i++){
			arr[i] = 0;//将前一项的值清零
			temp = arr[i];
			arr[i] = arr[i+1];
			arr[i+1] = temp;
		}
	}

4、更改

public static void update(int index,int data,int[] arr){
		for(int i = 0;i < arr.length;i++){
			if(i == index) arr[i] = data;
		}
	}

5、查询

public static int search(int index,int[] arr){
		//查询指定位置的元素
		for(int i = 0;i < arr.length;i++){
			if(i == index) return arr[i];
		}
		return -1;
	}

6、扩容

public static int[] grow(int[] arr){
		//用原数组的大小的两倍初始化新数组，并返回新数组
		int[] newArr = new int[arr.length<<1];
		for(int i = 0;i < arr.length;i++) newArr[i] = arr[i];
		return newArr;
	}

链表（List）

一、概念

链表和数组同属于线性结构，他与数组是互补的。数组属于静态存储结构，而链表属于动态存储结构

链表是逻辑上连续的存储单元，但物理上不连续。链表的基本存储单元是节点（node),存储单元之间使用引用或指针相互链接。同一个数组只能存储同种数据类型的元素，链表也一样，同一个链表只能存储同种数据类型，链表可以为空。链表的第一个节点称为头节点，最后一个节点称为尾节点，当链表为空时，头节点和尾节点相同，都指向null

相邻节点彼此称为前驱或后继，一个节点的前驱或后继必须唯一，没有前驱的节点称为首节点，没有后继的称为末节点，链表按照关系访问，最坏情况的时间复杂度是O(n)

链表分类：单向链表、双向链表、循环链表

二、单向链表

单向链表的每一个节点Node包含两个部分，一部分是存放数据的变量data，另一部分是引用next，指向下一个节点，节点结构如下：

public class Node{
	int data;
	Node next;
}

1、遍历链表

//遍历
public static void traverse(){
	Node current = first;
	while(current != null){
		System.out.print(current.data);
		current = current.next;
	}
}

2、添加节点

//头插法
public static void addFirst(int data){
	Node node = new Node();
	node.data = data;
	if(first == null) last = node;
	else node.next = first;
	first = node;
	size++;
}

//尾插法
public static void addLast(int data){
	Node node = new Node();
	node.data = data;
	if(last == null) first = node;
	else last.next = node;
	last = node;
	size++;
}

//任意位置添加
public static void add(int index,int data){
	Node node = new Node();
	node.data = data;
	Node current1 = first;//创建一个指针指向头结点
	Node current2 = first.next;//创建一个指针指向头结点的下一个节点
	for(int i = 1;i < size;i++){
		if(i == index){
			current1.next = node;
			node.next = current2;
		}
		current1 = current1.next;
		current2 = current2.next;
	}
	if(index == 0)addFirst(data);//若添加的位置是头部，则调用头插法
	if(index == size)addLast(data);//调用尾插法
    size++;
}

3、修改数据

//根据指定内容修改
public static void updateByData(int oldData,int newData){
	Node current = first;
	while(current != null){
		if(current.data == oldData) current.data = newData;
		current = current.next;
	}
}

//根据指定位置修改
public static void updateByIndex(int index,int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index) current.data = data;
		current = current.next;
	}
}

4、删除节点

//删除头节点
public static void deleteFirst(){
    if(size == 1){
        first = null;
        last = null;
    }
	first = first.next;
	size--;
}
//删除尾节点
public static void deleteLast(){
	Node current = first;
	for(int i = 0;i < size; i++){
		if(i == size-2){
			last = current;
			last.next = null;
			size--;
			break;
		}
        if(size == 1){
            first = null;
            last = null;
            size--;
            break;
        }
		current = current.next;
	}
}
//根据指定位置删除
public static void deleteByIndex(int index){
	Node current1 = first;
	Node current2 = first.next;
	for(int i = 1;i < size;i++){	
		if(index == 0)deleteFirst();
		if(index == i){
			if(i == size)deleteLast();
			else{
				current1.next = current2.next;	
				current2 = current1.next;
				size--;
				break;
			}
		}
		current1 = current1.next;
		current2 = current2.next;
	}
}
//根据指定内容删除
public static void deleteByData(int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current == null){
			deleteFirst();
			break;
		}
		if(current.data == data){
			deleteByIndex(i);
			i--;
		}
		current = current.next;
	}
}

5、查找数据

//根据位置查找返回数据
public static int searchByIndex(int index){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index){
			return current.data;
		}
		current = current.next;
	}
	return -1;
}

//根据数据查找返回首个数据的位置
public static int searchByData(int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == data){
			return i;
		}
		current = current.next;
	}
	return -1;
}

6、翻转链表

//链表翻转
public static void reverse(){
	if(first == null) return;
	Node one = first, two = first.next;
	first.next = null;
	while(two != null) {
		Node three = two.next;
		two.next = one;
		one = two;
		two = three;
	}
	last = first;
	first = one;
}

三、单向循环链表

单向链表中，当尾节点的next指向了头结点，就形成了单向循环链表，循环链表中大部分代码都不用更改，基本与单向链表一致，为了大家阅读方便我就全部写上了

1、判断是否循环

//判断是否循环（快慢追逐法）
public static boolean isCircul(){
	Node fast = first,slow = first;
	while(fast != null && slow != null){
		fast = fast.next.next;
		if(fast == slow) return true;
		slow = slow.next;
	}
	return false;
}

2、遍历

//遍历
public static void traverse(){
	Node current = first;
	for(int i = 0;i < size;i++){
		System.out.print(current.data);
		current = current.next;
	}
}

3、添加

//头插法
public static void addFirst(int data){
	Node node = new Node();
	node.data = data;
	if(first == null) last = node;
	else node.next = first;
	first = node;
	last.next = first;
	size++;
}
//尾插法
public static void addLast(int data){
	Node node = new Node();
	node.data = data;
	if(last == null) first = node;
	else last.next = node;
	last = node;
	last.next = first;
	size++;
}
//任意位置添加（与单向链表相同）
public static void add(int index,int data){
	Node node = new Node();
	node.data = data;
	Node current1 = first;//创建一个指针指向头结点
	Node current2 = first.next;//创建一个指针指向头结点的下一个节点
	for(int i = 1;i < size;i++){
		if(i == index){
			current1.next = node;
			node.next = current2;
		}
		current1 = current1.next;
		current2 = current2.next;
	}
	if(index == 0)addFirst(data);//若添加的位置是头部，则调用头插法
	if(index == size)addLast(data);//调用尾插法
	size++;
}

4、删除

//删除头节点
public static void deleteFirst(){
    if(size == 1){
        first = null;
        last = null;
    }
	first = first.next;
	size--;
}
//删除尾节点
public static void deleteLast(){
	Node current = first;
	for(int i = 0;i < size; i++){
		if(i == size-2){
			last = current;
			last.next = first;//这里与单向链表不同
			size--;
			break;
		}
        if(size == 1){
            first = null;
            last = null;
            size--;
            break;
        }
		current = current.next;
	}
}
//根据指定位置删除
public static void deleteByIndex(int index){
	Node current1 = first;
	Node current2 = first.next;
	for(int i = 1;i < size;i++){	
		if(index == 0)deleteFirst();
		if(index == i){
			if(i == size)deleteLast();
			else{
				current1.next = current2.next;	
				current2 = current1.next;
				size--;
				break;
			}
		}
		current1 = current1.next;
		current2 = current2.next;
	}
}
//根据指定内容删除
public static void deleteByData(int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current == null){
			deleteFirst();
			break;
		}
		if(current.data == data){
			deleteByIndex(i);
			i--;
		}
		current = current.next;
	}
}

5、更改

//根据指定内容修改
public static void updateByData(int oldData,int newData){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == oldData) current.data = newData;
		current = current.next;
	}
}
//根据指定位置修改
public static void updateByIndex(int index,int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index) current.data = data;
		current = current.next;
	}
}

6、查询

//根据位置查找返回数据
public static int searchByIndex(int index){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index){
			return current.data;
		}
		current = current.next;
	}
	return -1;
}
//根据数据查找返回首个数据的位置
public static int searchByData(int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == data){
			return i;
		}
		current = current.next;
	}
	return -1;
}

四、双向链表

链表按照关系访问，最坏情况的时间复杂度是O(n)，与单向链表不同的是双向链表中的节点有前驱与后驱的引用，这样可以使得链表相对于单向链表更易于访问，节点结构：

public class Node{
	int data;
	Node prev;
	Node next;
}

1、遍历

//遍历
public static void traverse(){
	Node current = first;
	while(current != null){
		System.out.print(current.data+" ");
		current = current.next;
	}
}

2、添加

//头插法
public static void addFirst(int data){
	Node node = new Node();
	node.data = data;
	if(first == null) last = node;
	else first.prev = node;
	node.next = first;
	first = node;
	size++;
}
//尾插法
public static void addLast(int data){
	Node node = new Node();
	node.data = data;
	if(last == null) first = node;
	else last.next = node;
	node.prev = last;
	last = node;
	size++;
}
//任意位置添加
public static void add(int index,int data){
	Node current = first;
	Node node = new Node();
	node.data = data;
	if(index == 0) addFirst(data);
	else if(index == size) addLast(data);
	else{
		for(int i = 0;i < size;i++){
			if(index == i){
				node.prev = current.prev;
				node.next = current;
				current.prev.next = node;
				current.prev = node;
				size++;
				current = current.prev;
			}
			current = current.next;
		}
	}
}

3、删除

//删除头节点
public static void deleteFirst(){
	if(first == null) return;
	first = first.next;
	first.prev =null;
	size--;
}
//删除尾节点
public static void deleteLast(){
	if(last == null) return;
	last = last.prev;
	last.next = null;
	size--;
}
//根据指定位置删除
public static void deleteByIndex(int index){
	Node current = first;//这里相对于单向链表来就体现出优势了
	for(int i = 0;i < size;i++){
		if(index == 0) deleteFirst();
		if(index == size-1) deleteLast();
		if(i == index){
			current.prev.next = current.next;
			current.next.prev = current.prev;
			size--;
		}
		current = current.next;
	}
}
//根据指定数据删除
public static void deleteByData(int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == data){
			deleteByIndex(i);
			i--;
		}
		current = current.next;
	}
}

4、查询

//根据位置查询，返回数据
public static int researchByIndex(int index){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index) return current.data;
		current = current.next;
	}
	return -1;
}

//根据内容查询，返回首个元素的位置
public static int researchByData(int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == data) return i;
		current = current.next;
	}
	return -1;
}

5、更改

//根据指定位置更改
public static void updateByIndex(int index,int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index) current.data = data;
		current = current.next;
	}
}
//根据指定内容更改
public static void updateByData(int oldData,int newData){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == oldData) updateByIndex(i,newData);
		current = current.next;
	}
}

五、双向循环链表

1、判断是否循环

//判断是否循环(顺坏与逆环)
public static boolean isCircul(){
	Node current1 = first;
	Node current2 = first;
	while(current1 != null && current2 != null){
		if(current1.next == first && current2.prev ==first) return true;
		current1 = current1.next;
		current2 = current2.prev;
	}
	return false;
}

2、遍历

//遍历
public static void traverse(){
	Node current = first;
	do{
		System.out.print(current.data+" ");
		current = current.next;
	}while(current != first);
}

3、添加

//头插法
public static void addFirst(int data){
	Node node = new Node();
	node.data = data;
	if(first == null) last = node;
	else first.prev = node;
	node.next = first;
	first = node;
	first.prev = last;
	last.next = first;
	size++;
}
//尾插法
public static void addLast(int data){
	Node node = new Node();
	node.data = data;
	if(last == null) first = node;
	else last.next = node;
	node.prev = last;
	last = node;
	first.prev = last;
	last.next = first;
	size++;
}
//任意位置添加
public static void add(int index,int data){
	Node current = first;
	Node node = new Node();
	node.data = data;
	if(index == 0) addFirst(data);
	else if(index == size) addLast(data);
	else{
		for(int i = 0;i < size;i++){
			if(index == i){
				System.out.println("current.data="+current.data);
				node.prev = current.prev;
				node.next = current;
				current.prev.next = node;
				current.prev = node;
				size++;
				current = current.prev;
			}
			current = current.next;
		}
	}
}

4、删除

//删除头节点
public static void deleteFirst(){
	if(first == null) return;
	first = first.next;
	first.prev = last;
	last.next = first;
	size--;
}
//删除尾节点
public static void deleteLast(){
	if(last == null) return;
	last = last.prev;
	last.next = first;
	first.prev = last;
	size--;
}
//根据指定位置删除
public static void deleteByIndex(int index){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(index == 0) deleteFirst();
		if(index == size-1) deleteLast();
		if(i == index){
			current.prev.next = current.next;
			current.next.prev = current.prev;
			size--;
		}
		current = current.next;
	}
}
//根据指定数据删除
public static void deleteByData(int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == data){
			deleteByIndex(i);
			i--;
		}
		current = current.next;
	}
}

5、查询

//根据位置查询，返回数据
public static int researchByIndex(int index){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index) return current.data;
		current = current.next;
	}
	return -1;
}

//根据内容查询，返回首个元素的位置
public static int researchByData(int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == data) return i;
		current = current.next;
	}
	return -1;
}

6、修改

//根据指定位置更改
public static void updateByIndex(int index,int data){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index) current.data = data;
		current = current.next;
	}
}
//根据指定内容更改
public static void updateByData(int oldData,int newData){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(current.data == oldData) updateByIndex(i,newData);
		current = current.next;
	}
}

栈（Stack）

一、概念

栈（stack）是一种操作受限的线性序列，只能在栈的顶部插入和删除数据，底部为盲端，栈是一种后进先出（LIFO）或先进后出（FILO）的数据结构

二、数组实现栈

public static String[] stack = new String[3];
public static int top = -1;

//入栈
public static void push(String data){
	//扩容（将栈里的元素出栈到临时栈，再由临时栈出栈到新栈中）
	if(isFull()){
		String[] tmpStack = new String[stack.length]; 
		int temTop = -1;
		while(!isEmpty()){
			tmpStack[++temTop] = pop();
		}
		top = temTop;
		stack = tmpStack;
		String[] newStack = new String[tmpStack.length << 1];//两倍扩容
		int newTop = -1;
		while(!isEmpty()){
			newStack[++newTop] = pop();
		}
		top = newTop;
		stack = newStack;
	}
	stack[++top] = data;
}
//出栈
public static String pop(){
	if(isEmpty()) return null;
	return stack[top--];
}
//查看栈顶元素
public static String top(){
	if(isEmpty()) return null;
	return stack[top];
}
//判断栈是否为空
public static boolean isEmpty(){
	return  top == -1;
}
//判断栈是否满
public static boolean isFull(){
	return top == (stack.length - 1);
}

三、链表实现栈

1、单向链表实现

在单向链表中，那些用不到的方法我就不加上去了，其中为了便于栈的实现，我做了一些修改，代码如下：

节点：

public class Node{
	String data;
	Node next;
}

单向链表：

public static Node first,last;
public static int size;
//尾插法
public static void addLast(String data){
	Node node = new Node();
	node.data = data;
	if(last == null) first = node;
	else last.next = node;
	last = node;
	size++;
}
//删除尾结点
public static String deleteLast(){
	String tmpData;
	Node current = first;
	for(int i = 0;i < size; i++){
		if(i == size-2){
			last = current;
			tmpData = last.next.data;
			last.next = null;
			size--;
			return tmpData;
		}
		if(size == 1 ){
			first = null;
			last = null;
			size--;
			return current.data;
		}
		current = current.next;
	}
	return null;
}
//根据指定位置查询
public static String searchByIndex(int index){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index){
			return current.data;
		}
		current = current.next;
	}
	return null;
}

栈：

public static List stack = new List();
public static int top = -1;

//入栈
public static void push(String data){
	stack.addLast(data);
	top++;
}
//出栈
public static String pop(){
	if(isEmpty()) return null;
	top--;
	return stack.deleteLast();
}
//查看栈顶元素
public static String top(){
	if(isEmpty()) return null;
	return stack.searchByIndex(top);
}
//判断栈是否为空
public static boolean isEmpty(){
	return  top == -1;
}

2、双向链表实现

与单链表一样，我对双链表也进行了一定的修改，代码如下：

节点：

public class Node{
	String data;
	Node prev;
	Node next;
}

双链表：

public static Node first,last;
public static int size;
//头插法
public static void addFirst(String data){
	Node node = new Node();
	node.data = data;
	if(first == null) last = node;
	else first.prev = node;
	node.next = first;
	first = node;
	size++;
}
//删除头节点
public static String deleteFirst(){
	if(first == null) return null;
	if(first.next == null) return first.data;
	first = first.next;
	size--;
	return first.prev.data;
}
//根据位置查询，返回数据
public static String searchByIndex(int index){
	Node current = first;
	for(int i = 0;i < size;i++){
		if(i == index) return current.data;
		current = current.next;
	}
	return null;
}

栈（与单链表的相同，为了方便阅读我也把代码粘出来）：

public static LinkedList stack = new LinkedList();
public static int top = -1;
//入栈
public static void push(String data){
	stack.addFirst(data);
	top++;
}
//出栈
public static String pop(){
	if(isEmpty()) return null;
	top--;
	return stack.deleteFirst();
}
//查看栈顶元素
public static String top(){
	if(isEmpty()) return null;
	return stack.searchByIndex(top);
}
//判断栈是否为空
public static boolean isEmpty(){
	return  top == -1;
}

队列（Queue）

队列也是一种操作受限制的线性序列，链表有队头与队尾，队列只能在队尾插入数据，在队头删除数据

一、用数组实现队列

//遍历
public static void traverse(){
	for(int i = 0;i < size;i++){
		System.out.print(queue[i]+" ");
	}
}
//入队
public static void enqueue(String data){
	if(isFull()) return;
	queue[size++] = data;
}
//出队
public static String dequeue(){
	String data = queue[0];
	if(isEmpty()) return null;
	for(int i = 1;i < size;i++) queue[i-1] = queue[i];
	size--;
	return data;
}
//判断满
public static boolean isFull(){
	return size == queue.length;
}
//判断空
public static boolean isEmpty(){
	return size == 0;
}

二、用链表实现队列

1、单向链表实现

//遍历
public static void traverse(){
	Node current = head;
	while(current != null){
		System.out.print(current.data+" ");
		current = current.next;
	}
}
//入队
public static void enqueue(String data){
	Node node = new Node();
	node.data = data;
	if(isEmpty()) head = node;
	else tail.next = node;
	tail = node;
	size++;
}
//出队
public static String dequeue(){
	String data;
	if(isEmpty()) return null;
	data = head.data;
	head = head.next;
	size--;
	return data;
}
//判断空
public static boolean isEmpty(){
	return size == 0;
}

2、双向链表实现

//遍历
public static void traverse(){
	Node current = head;
	while(current != null){
		System.out.print(current.data+" ");
		current = current.next;
	}
}
//入队
public static void enqueue(String data){
	Node node = new Node();
	node.data = data;
	if(isEmpty()) head = node;
	else tail.next = node;
	tail = node;
	size++;
}
//出队
public static String dequeue(){
	String data;
	if(isEmpty()) return null;
	data = head.data;
	head = head.next;
	size--;
	return data;
}
//判断空
public static boolean isEmpty(){
	return size == 0;
}

三、循环队列

因为单向链表实现流程基本相同，这里就用数组与双向链表来实现

1、数组实现循环队列

public static String[] queue = new String[6];
public static int head,tail,count;//count 用来计数
//遍历
public static void traverse(){
	for(int i = head;i <= count;i++){
		System.out.print(queue[i]+" ");
	}
}
//入队
public static void enqueue(String data){
	if(isFull())return;
	queue[tail++] = data;
	tail %= queue.length;
	count++;
}
//出队
public static String dequeue(){
	if(isEmpty()) return null;
	String data = queue[head++];
	head %= queue.length;
	count--;
	return data;
}
//判断满
public static boolean isFull(){
	return (tail+1)%queue.length+1 == head;
}
//判断空
public static boolean isEmpty(){
	return tail == head;
}
//返回队列大小
public static int getSize(){
	return count;
}

2、双向链表实现循环队列

//判断是否循环
public static boolean isCircul(){
	Node current1 = head;
	Node current2 = head;
	while(current1 != null && current2 != null){
		if(current1.next == head && current2.prev == head) return true;
		current1 = current1.next;
		current2 = current2.prev;
	}
	return false;
}
//遍历
public static void traverse(){
	Node current = head;
	for(int i = 0;i < size;i++){
		System.out.print(current.data+" ");
		current = current.next;
	}
}
//入队
public static void enqueue(String data){
	Node node = new Node();
	node.data = data;
	if(isEmpty())head = node;
	else tail.next = node;
	node.prev = tail;
	tail = node;
	tail.prev = node;
	tail.next = head;
	size++;
}
//出队
public static String dequeue(){
	String data;
	if(isEmpty())return null;
	data = head.data;
	head = head.next;
	head.prev = tail;
	tail.next =head;
	size--;
	return data;
}
//判断是否为空
public static boolean isEmpty(){
	return size == 0;
}

树（Tree）

一、概念

树中任意一个顶点，都有深度和高度，跟节点是所有节点的公共祖先且深度为0，没有后代的节点称作叶子，所有叶子深度中最大者称为树的高度，空树的高度为-1

节点度不超过2的树称为二叉树，同一个节点的孩子和子树均分左右，深度为m的树，最多有2^m-1个节点，含有n个节点、高度为h的二叉树中h<n<2^h+1，当n=h+1时退化为链表，二叉树还分为满二叉树与真二叉树，满二叉树满足条件：n = 2^h-1，真二叉树是二叉树通过引入外部节点，使得原有的节点度数统一为2

二、实现二叉树

1、节点：

public class TreeNode{
	String data;
	TreeNode left;
	TreeNode right;
}

2、二叉树：

//先序遍历
public static void preTraverse(TreeNode root){
	if(root == null) return;
	System.out.print(root.data+" ");
	preTraverse(root.left);
	preTraverse(root.right);
}
//使用栈的方式来实现先序遍历
public static void preTraverseByStack(TreeNode root){
	Stack stack = new Stack();
	stack.push(root);
	while(!stack.empty()){
		TreeNode node = (TreeNode)stack.pop();
		if(node == null) continue;
		System.out.print(node.data + " ");
		stack.push(node.right);
		stack.push(node.left);
	}
}
//中序遍历
public static void inTraverse(TreeNode root){
	if(root == null) return;
	preTraverse(root.left);
	System.out.print(root.data+" ");
	preTraverse(root.right);
}
//后续遍历
public static void TraversePost(TreeNode root){
	if(root == null) return;
	preTraverse(root.left);
	preTraverse(root.right);
	System.out.print(root.data+" ");
}

排序

一、冒泡排序

public static void bubbleSort(int[] arr){
		for(int i = 0;i < arr.length;i++){
			for(int j = i;j < arr.length;j++){
				int tmp;
				if(arr[i] > arr[j]){
					tmp = arr[i];
					arr[i] = arr[j];
					arr[j] = tmp;
				}
			}
		}
	}

二、选择排序

public static void selectSort(int[] arr){
		for(int i = 0;i < arr.length;i++){
			int min = i;
			for(int j = i+1;j < arr.length;j++){
				if(arr[j] < arr[min]) min = j;
			}
			int tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}
	}

三、插入排序

public static void insertSort(){
		for(int i = 0; i < arr.length-1; i++){
			for(int j = i + 1; j > 0; j--){
				if(arr[j] < arr[j-1]){
					int t = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = t;
				}else break;
			}
				
		}
	}

四、快速排序

public static void quickSort(int[] arr,int low,int hight){
		for(int i = 0; i < arr.length-1; i++) {
			for(int j = i + 1; j > 0; j--) {
				if(arr[j] < arr[j-1]) {
					int t = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = t;
				} else break;
			}
				
		}
	}
	public int partition(int[] arr, int low, int high) {
		int value = arr[low];
		int left = low, right = high;
		while(left < right) {
			while(left < right && arr[right] > value) right--;
			while(left < right && arr[left] < value) left++;
			int t = arr[right];
			arr[right] = arr[left];
			arr[left] = t;
		}
		arr[left] = value;
		return left;
	}

五、归并排序

public static void mergeSort(int[] arr, int low, int high) {
		if ((high - low) < 1) return;
		int mi = (high + low) >> 1;
		mergeSort(arr, low, mi);
		mergeSort(arr, mi + 1, high);
		merge(arr, low, mi, high);
	}
	
	public static void merge(int[] arr, int low, int mi, int high) {
		System.out.print("low : " + low + "   mi : " + mi + "   high : " + high);
		System.out.println();
		int[] tempArr = new int[high - low + 1];
		int lb = low, lc = mi + 1, la = 0;
		while (lb <= mi && lc <= high) {
			if (arr[lb] <= arr[lc]) tempArr[la++] = arr[lb++];
			else tempArr[la++] = arr[lc++];
		}
		while (lb <= mi) tempArr[la++] = arr[lb++];
		while (lc <= high) tempArr[la++] = arr[lc++];
		for (int i = 0; i < tempArr.length; i++) {
			arr[i + low] = tempArr[i];
		}
	}

六、希尔排序

public static void sort(int[] a) {
        int n = a.length;
        int h = 1;
        while (h < n/3) h = 3*h + 1;
        while (h >= 1) {
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                    int swap = a[j];
                    a[j] = a[j-h];
                    a[j-h] = swap;
                }
            }
            h /= 3;
        }
    }
    public static boolean less(int v, int w) {
        return (v - w) < 0;
    }
    public static void show(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + "  ");
        }
    }

七、二分查找

private static int find(int[] arr, int start, int end, int data) {
		if (start > end) return -1;
		int mid = (start + end) / 2;
		if (data < arr[mid]) return find(arr, start, mid - 1, data);
		else if (arr[mid] < data) return find(arr, mid + 1, arr.length, data);
		else if (arr[mid] == data) return mid;
		else return -1;
	}

	private static int search(int[] arr, int start, int end, int data) {
		while (start <= end) {
			int mid = (start + end) / 2;
			if (data < arr[mid]) end = mid - 1;
			else if (arr[mid] < data) start = mid + 1;
			else return mid;
		}
		return -1;
	}

特别感谢

特别感谢我的老师鹏哥的悉心教导

文章来源:https://blog.csdn.net/weixin_59413946/article/details/131736110
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！

标签：

首页 > 基础资料 博客日记

Java-基础（数据结构与算法篇）

概念

一、时间复杂度

二、算法度量工具

数组（Array）

一、概念

1.静态初始化

2.动态初始化

二、基本操作

1、遍历

2、添加

3、删除

4、更改

5、查询

6、扩容

链表（List）

一、概念

二、单向链表

1、遍历链表

2、添加节点

3、修改数据

4、删除节点

5、查找数据

6、翻转链表

三、单向循环链表

1、判断是否循环

2、遍历

3、添加

4、删除

5、更改

6、查询

四、双向链表

1、遍历

2、添加

3、删除

4、查询

5、更改

五、双向循环链表

1、判断是否循环

2、遍历

3、添加

4、删除

5、查询

6、修改

栈（Stack）

一、概念

二、数组实现栈

三、链表实现栈

1、单向链表实现

2、双向链表实现

队列（Queue）

一、用数组实现队列

二、用链表实现队列

1、单向链表实现

2、双向链表实现

三、循环队列

1、数组实现循环队列

2、双向链表实现循环队列

树（Tree）

一、概念

二、实现二叉树

1、节点：

2、二叉树：

排序

一、冒泡排序

二、选择排序

三、插入排序

四、快速排序

五、归并排序

六、希尔排序

七、二分查找

特别感谢

相关文章

最新发布

点击排行

本站推荐

标签云

首页 > 基础资料博客日记