首页  思维导图  详情

算法

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;
        }
    }
}

算法分析

时间复杂度

空间复杂度

排序

初级排序算法

归并排序

快速排序

优先队列

应用

查找

符号表

二叉查找树