2019-02-25

数据结构和算法分析

郝斌老师数据结构自学视频

数据结构概述

定义:
我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某个功能(比如查找某个元素,删除某个元素,对所有元素进行排序等)而执行的响应操作,这个相应的操作也叫算法。

数据结构 = 个体 + 个体的关系
算法 = 对存储数据的操作

数据结构的地位
数据结构是软件中最核心的课程

程序 = 数据的存储 + 数据的操作 + 可被计算机执行的语言

算法

解题的方法和步骤
衡量算法的标准

  1. 时间复杂度 程序大概要执行的次数,而非执行的时间
  2. 空间复杂度 算法执行过程中大概所占用的最大内存
  3. 难易程度
  4. 健壮性

预备知识

指针
指针是c语言的灵魂
定义
地址就是内存单元的编号,从0开始的非负整数,范围: 0-- FFFFFFFF [0~4G-1]
指针:

  • 指针就是地址,地址就是指针
  • 指针变量是存放内存单元的地址的变量
  • 指针的本质是一个操作受限的非负整数
    分类:
  1. 基本类型的指针
  2. 指针和数组的关系

结构体 动态内存的分配和释放

模块一: 线性结构

  • 连续存储 [数组]
  • 离散存储 [链表]

线性结构的常见应用:

  • 队列

专题:递归
模块二:非线性结构

模块三:查找和排序

  • 二分查找

排序

  • 冒泡
  • 插入
  • 选择
  • 归并排序
  • 快速排序

Java中的容器和数据结构

  • Iterator接口
  • Map 哈希表