数据项-------------------学生表里的姓名的 一个姓名 linjinbo
数据元素-----------------------表里的一列 林进波这一列
数据对象-----------------------整个表

• 逻辑结构
• 存储结构

逻辑

• 线性结构
• 非线性结构

存储

• 顺序存储结构
  查询的速度快
• 链式存储结构
  添加的速度快
• 索引存储结构
• 散列存储结构
  添加和查询的速度快

算法

通俗的解题思路

时间复杂度

算法中语句的执行次数称为时间频度 t(n)
t(n)

时间复杂度

O(n) 是t(n) 的去掉 常数项 去掉 低次幂 去掉 高次项的系数 次幂
留下的东西

最坏时间复杂度

O 最坏时间复杂度

时间复杂度的求法

1. 找出基本语句
2. 计算执行次数的数量级
3. 用O 表示

• int i=1;
  O(1)
• int i=1;
  int i=1;
  int i=1;
  int i=1;
  int i=1;
  O(1)

int n= 8
for( i,i<1000n+100 ,I++ ){
    mm++;
}
t(n)=1000n+100
O(n)=n

 
 for (int i = 0; i <n ; i=i*2) {
            mm++;
        }

O(logn)

for (int i = 0; i <n ; i=i*2) {
            for (int j = 0; j <n ; j++) {
                
            } 
        }
n*logn

for (int i = 0; i <n ; i=i++) {
            for (int j = 0; j <i ; j++) {
                mm++;
            } 
        }

1+2+3+4+......+n=T(n的平方) 等差数列
O(n的平方)

空间复杂度

  for (int i = 0; i <n ; i=i++) {
            for (int j = 0; j <n ; j++) {
                for (int k = 0; k < n; k++) {
                    m++
                }
            } 
        }

只有4个变量
S(n)=O(n)

    int fun(int[] aa, int t) {
        if (t == 1) {
            return 4;
        } else {
            fun(aa ,t);
        }
        return 0;
    }
递归
空间复杂度 O(n)  空间用的多  但是思路清晰

递归求最大值

public class hello {
    public static void main(String[] args) {
        int mm[] = {4, 3, 1, 6, 8, 34, 74, 3462, 32, 2};
        int max = max(mm, mm.length - 1);
        System.out.println(max);
    }
    static int max(int aa[], int n) {
        if (n == 0) {
            return aa[0];
        }
        int bb = max(aa, n - 1);
        return Math.max(bb, aa[n]);
    }
}

线性表

逻辑结构
一个前驱一个后继

数组实现(顺序表)

通过索引找数据 数组中只存 数据
查找的时间复杂度
(1+2+3+...+n)1/n=O(n)

链表

地址无规律
节省空间 但是要存地址

arraylist

public class ArraList implements List {
    private  Object [] elementdata ;
    private int size;

    public ArraList() {
        this(4);
    }

    public ArraList(int cap) {
        elementdata=new Object[cap];
    }


    @Override
    public boolean add(Object o) {
        if(size==elementdata.length){
          Object [] elementdata2=  new Object[elementdata.length+4];
            for (int i = 0; i <elementdata.length ; i++) {
                elementdata2[i]=elementdata[i];
            }
            elementdata=elementdata2;
        }
        elementdata[size]=o;
        size++;
        return false;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        if(size==0){
            return true;
        }
        return false;
    }
    @Override
    public Object get(int index) {
        if (index<0||index>size-1){
            throw new RuntimeException("越界异常");
        }
        return elementdata[index];
    }
其他的方法没写

Linklist

同样的继承于list

节点类
public class Node {
    Object data;
    Node next;
}

在linkedlist中维护 头节点和size变量
public class LinkList implements List {
    Node head = new Node(); //头节点
    int size; //一共的节点数量



......
}


 @Override
    public void add(int index, Object element) {
        if (index <= size&&index>=0) {
            Node node = new Node(element);
            node.next = null;
            Node p = head;
            for (int i = 0; i < index; i++) {
                p = p.next;

            }
            node.next = p.next;
            p.next = node;
            size++;
        }
        else {
            System.out.println("添加索引不对");
        }
    }

栈和队列

都是线性结构 操作受限制
也有数组实现和链式表实现 但是

• 数组中的指针其实就是个索引 就是
  0 1 2 3 4 5 6 和链式指针
• 链式指针是对象的引用

java 中

• stack 栈 父类是vector --------------stack已经废弃
• queue 队列
• deque 双端队列 当作栈来处理
  一般不用 ArrayDeque arrayDeque;
  LinkList linkList;
  实现类

  LinkedList mm =new LinkedList();
        Stack stack=new Stack();
        mm.push(1);
        mm.push(2);
        mm.push(3);
        int size = mm.size();
        for (int i = 0; i <size ; i++) {
            System.out.println(mm.pop());
        }

这里判空 可以用isempty

二叉树 是递归定义的

规定
左子树 右子树
根节点 插入

树的节点

public class Node {
    Object value;
    Node l;
    Node r;
}

二叉树
public class linkedbinarytree implements BinaryTree {
    private Node root;
}
里面就维护了一个根节点

手动建树
测试类
 Node node7=new Node(7,null,null);
        Node node5=new Node(5,null,null);
        Node node3=new Node(3,null,null);
        Node node6=new Node(6,null,node7);
        Node node4=new Node(4,null,node5);
        Node node2=new Node(2,node3,node6);
        Node node1=new Node(1,node4,node2);
        linkedbinarytree linkedbinarytree = new linkedbinarytree(node1);



二叉树里面的方法
    //先序
    public void pre() {
        if (root != null) {
            System.out.print(root.value);
            linkedbinarytree linkedbinarytree = new linkedbinarytree(root.l);
            linkedbinarytree.pre();
            linkedbinarytree linkedbinarytree1 = new linkedbinarytree(root.r);
            linkedbinarytree1.pre();
        }
    }

    //    中序
    void midle() {
        if (root != null) {
            linkedbinarytree linkedbinarytree = new linkedbinarytree(root.l);
            linkedbinarytree.midle();
            System.out.print(root.value);
            linkedbinarytree linkedbinarytree1 = new linkedbinarytree(root.r);
            linkedbinarytree1.midle();
        }
    }

    //     后序列
    void after() {
        if (root != null) {
            linkedbinarytree linkedbinarytree = new linkedbinarytree(root.l);
            linkedbinarytree.after();
            linkedbinarytree linkedbinarytree1 = new linkedbinarytree(root.r);
            linkedbinarytree1.after();
            System.out.print(root.value);
        }
    }

    int gethight() {
        if (root != null) {
            linkedbinarytree linkedbinarytree = new linkedbinarytree(root.r);
            int gethight = linkedbinarytree.gethight();
            linkedbinarytree linkedbinarytree2 = new linkedbinarytree(root.l);
            int gethight1 = linkedbinarytree2.gethight();
            return Math.max(gethight,gethight1)+1;
        }
        else return 0;
    }
    int getsize(){
        if (root != null) {
            linkedbinarytree linkedbinarytree = new linkedbinarytree(root.r);
            int getsize = linkedbinarytree.getsize();
            linkedbinarytree linkedbinarytree2 = new linkedbinarytree(root.l);
            int getsize2 = linkedbinarytree2.getsize();
            return  getsize+getsize2+1 ;
        }
        else return 0;

    }
全是递归

还有一些非递归的遍历方法
比如中序遍历是用栈来实现的
测试类
  System.out.println(linkedbinarytree.isempty());
        System.out.println("先序遍历");
        linkedbinarytree.pre();
        System.out.println("\n中序遍历");
        linkedbinarytree.midle();
        System.out.println("\n后序遍历");
        linkedbinarytree.after();
        System.out.println("\n二叉树高度");
        System.out.println("\n"+linkedbinarytree.gethight());
        System.out.println("\n二叉树节点个数");
        System.out.println("\n"+linkedbinarytree.getsize());


结果:
false
先序遍历
1452367
中序遍历
4513267
后序遍历
5437621
二叉树高度
4
二叉树节点个数
7


二叉树的查找


二叉树的非递归中序遍历
 
层次遍历

图

图的存储

二维数组

• 矩阵来记录是否有路径
• 邻接表 链式存储结构
  就一个数组 ++++每个数组的一项
  后连接了一个链表

深度优先

类似树的先根遍历 而可以用递归或者是栈来实现

广度优先

类是于树的层次遍历 可以用队列来实现