大学计算机第三章笔记

大学计算机第三章讲述了算法与程序、数据结构、线性结构的存储与处理、数据的查找与排序，适用于考试复习的同学！

第三章

• 算法
  • 算法
    • 对数据的描述，灵魂
    • 特征：可行性、确定性、有穷性
    • 复杂度
      • 时间复杂度
        • 算法所执行的基本运算次数
      • 空间复杂度
        • 算法在运行过程中临时占用存储空间大小
  • 程序：为实现特定目标或解决特定问题而用程序设计语言描述的是和计算机执行的指令序列
    • 对操作的描述
• 数据结构
  • 数据元素
  • 数据项
  • • • 逻辑结构
        • 给人看的，与数据如何存储无关，独立于计算机
        • 线性结构--线性表、栈、队列、字符、串、文件、数据、广义表
        • 非线性结构--树、图
      • 存储结构
        • 人不可见
        • 顺序：地址连续，检索方便，插入和删除较麻烦
          • 优先选择
        • 链式：地址任意
          • 数据域
          • 指针域
        • 索引
        • 散列
    • • 数据的运算
        • 检索、插入、删除、更新、排序
• 线性结构的存储与处理
  • 线性表
    • 基本操作
      • 查找
      • 插入：平均移动n/2次
      • 删除：平均移动n-1/2次
    • 链式存储结构
    • 线性链表
      • 单链表
      • 循环单链表
      • 双向链表
      • 基本运算
        • • 查找：时间复杂度o(n)
          • 插入：时间复杂度o(1)
          • 删除：时间复杂度o(1)
  • 先进后出：栈
  • 先出后进：队
• 数据的查找与排序
  • 排序
    • 冒泡排序法
    • 快速排序法
    • 插入排序法
    • 选择排序法
  • 查找
    • 顺序查找
    • 二分查找