首页  思维导图  详情

算法

2023-04-12 15:58:25   0  举报





AI智能生成

算法

算法导论

算法与数据结构

作者其他创作

大纲/内容

基础

基础编程模型

Java基础

Java程序的基本结构

原始数据类型与表达式

语句

简便记法

数组

静态方法

API

Java库

标准库

自己编写的库

字符串

标准输入/输出

命令和参数

标准输出

格式化输出

标准输入

重定向与管道

基于文件的输入输出

标准绘图库（基本方法）

标准绘图库（控制方法）

二分查找

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

数据抽象

对象知识（略）

背包、队列和栈

背包

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

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\n", mean);       StdOut.printf("Std dev: %.2f\n", std);     } }

队列

先进先出队列（或简称队列）是一种基于先进先出（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;         }     } }

算法分析

时间复杂度

空间复杂度

排序

初级排序算法

归并排序

快速排序

优先队列

应用

查找

符号表

二叉查找树