数据项-------------------学生表里的姓名的 一个姓名 linjinbo
数据元素-----------------------表里的一列 林进波这一列
数据对象-----------------------整个表
- 逻辑结构
- 存储结构
逻辑
- 线性结构
- 非线性结构
存储
- 顺序存储结构
查询的速度快 - 链式存储结构
添加的速度快 - 索引存储结构
- 散列存储结构
添加和查询的速度快
算法
通俗的解题思路
时间复杂度
算法中语句的执行次数称为时间频度 t(n)
t(n)
时间复杂度
O(n) 是t(n) 的去掉 常数项 去掉 低次幂 去掉 高次项的系数 次幂
留下的东西
最坏时间复杂度
O 最坏时间复杂度
时间复杂度的求法
- 找出基本语句
- 计算执行次数的数量级
- 用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
二叉树的查找
二叉树的非递归中序遍历
层次遍历
图
图的存储
二维数组
- 矩阵来记录是否有路径
- 邻接表 链式存储结构
就一个数组 ++++每个数组的一项
后连接了一个链表
深度优先
类似树的先根遍历 而可以用递归或者是栈来实现
广度优先
类是于树的层次遍历 可以用队列来实现
网友评论