算法

 2023-04-12 15:58:25







算法

算法导论

算法与数据结构

举报

猜你喜欢

大纲/内容

Java程序的基本结构

原始数据类型与表达式

语句

简便记法

数组

静态方法

Java库

标准库

自己编写的库

API

字符串

命令和参数

标准输出

格式化输出

标准输入

重定向与管道

基于文件的输入输出

标准绘图库（基本方法）

标准绘图库（控制方法）

标准输入/输出

二分查找（Binary Search）也称为折半查找，是一种在有序数组中查找特定元素的算法。该算法每次都将待查找的区间缩小一半，直到找到目标元素或者区间为空为止。

二分查找

Java基础

基础编程模型

对象知识（略）

数据抽象

public class Stats{ public static void main(String[] args) { Bag＜Double＞ numbers = new Bag＜Double＞(); while (! StdIn.isEmpty()) numbers.add(StdIn.readDouble()); int N = numbers.size(); double sum = 0.0; for (double x : numbers) sum += x; double mean = sum/N; sum = 0.0; for (double x : numbers) sum += (x - mean)＊(x - mean); double std = Math.sqrt(sum/(N-1)); StdOut.printf(\"Mean: %.2f\\

背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中元素的数量）。

背包

子主题

先进先出队列（或简称队列）是一种基于先进先出（FIFO）策略的集合类型。

队列

下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型。

栈

定容栈

泛型

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型的元素和一个指向另一条链表的引用。

private class Node{ Item item; Node next;}

结构

在表头插入结点

从表头删除结点

在表尾插入结点

其他位置的插入和删除操作

删除指定的结点

在指定结点前插入一个新结点

for (Node x = first; x ! = null; x = x.next){ // 处理x.item}

遍历

增删改查

操作

public class Stack＜Item＞ implements Iterable＜Item＞{ private Node first; // 栈顶（最近添加的元素） private int N; // 元素数量 private class Node { // 定义了结点的嵌套类 Item item; Node next; } public boolean isEmpty() { return first == null; } // 或：N == 0 public int size() { return N; } public void push(Item item) { // 向栈顶添加元素 Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; N++; } public Item pop() { //从栈顶删除元素 Item item = first.item; first = first.next; N--; return item; } // iterator()的实现请见算法1.4 // 测试用例main()的实现请见本节前面部分}

下压堆栈（链表实现）

栈的实现

public class Queue＜Item＞ implements Iterable＜Item＞{ private Node first; // 指向最早添加的结点的链接 private Node last; // 指向最近添加的结点的链接 private int N; // 队列中的元素数量 private class Node { // 定义了结点的嵌套类 Item item; Node next; } public boolean isEmpty() { return first == null; } // 或： N == 0. public int size() { return N; } public void enqueue(Item item) { // 向表尾添加元素 Node oldlast = last; last = new Node(); last.item = item; last.next = null; if (isEmpty()) first = last; else oldlast.next = last; N++; } public Item dequeue() { // 从表头删除元素 Item item = first.item; first = first.next; if (isEmpty()) last = null; N--; return item; } // iterator()的实现请见算法1.4 // 测试用例main()的实现请见前面}

先进先出队列

队列的实现

import java.util.Iterator;public class Bag＜Item＞ implements Iterable<Item>{ private Node first; //链表的首结点 private class Node { Item item; Node next; } public void add(Item item) { // 和Stack的push()方法完全相同 Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; } public Iterator<Item> iterator() { return new ListIterator(); } private class ListIterator implements Iterator<Item> { private Node current = first; public boolean hasNext() { return current ! = null; } public void remove() { } public Item next() { Item item = current.item; current = current.next; return item; } }}

背包的实现

链表

集合类数据类型的实现

背包、队列和栈

时间复杂度

空间复杂度

算法分析

基础

初级排序算法

归并排序

快速排序

优先队列