数据结构-清华-邓俊辉

学堂在线，数据结构、1.重复的元素构成一个区间，只需保留一个元素而已。1.根据 ，同一元素，被删除元素之后的元素，重复的元素，需要反复删除，移动。

数据结构-清华-邓俊辉

• 2023-01-07 1.调整样式； 2.补充第二章内容详情；
• 第一章 绪论
• 第二章 向量
  • 2023-01-07 重新补充格式
  • A.抽象数据类型
    • 02A1. 接口与实现
      • 
    • 02A2-1 向量ADT
      • 
    • 02A2-2接口操作实现
      • 
    • 02A3-1. 构造与西沟
    • 02A3-2 复制
      •  预留 2*（hi-lo） 预留一定空间，避免反复扩容； 算法复杂度来自while(lo<hi) 循环；主体复杂度来自于被复制的个数； 向量的宽度，向量被复制后的初始化规模 [lo----hi); 左闭；右开；
  • B.可扩充向量
    • 02B1-1. 可扩充向量
      • 
      • 静态空间管理（不可扩充）
        • 
        • size
        • capacity
    • 02B1-2. 动态空间管理
      • 蝉
        • 金蝉脱壳
        • 换壳扩容
          • 空间
            • 
          • 扩容算法实现
            •  无效，指向某个地址，但给地址并没有我们需要的值；野指针； 容量加倍策略？
    • 02B1-3 递增式扩容
      •  
    • 02B1-4. 加倍式扩容
      •  1,2,4,8,16 ，2n次扩容； 
    • 对比
      •   装填因子： 空间利用率， 当前数量/容量； 递增：100% 代表全部装填； 倍增： 50% 代表超过50%即装填；
    • 02B2. 分摊复杂度
      •   
      • 1.平均
      • 2.分摊
    • 子主题
  • C.无序向量
    • 2023-01-08 补充资料
    • 02C1-1. 概述
      • 常用类型 
      • 1.没有顺序的向量
      • 2.没法排序的向量
    • 02C1-2. 循秩访问
      •  教学方便，简单校验； 0<=r<_size; 视频PPT与教案有区别： 
    • 02C1-3. 插入
      •   1.d e 如何填入 , 2. 注意： 1.for 循环，从最后不断递减 i--; 所有元素移动的秩序 后优先，即最后的元素先移动；不能颠倒，否则数据被覆盖；  2. 扩容； 可能存在（a）情况，数据可能满载，导致上溢了；进行扩容；而扩容由expend(); 
    • 02C1-4. 区间删除
      •  1. 区间 删除[lo,hi); 2.填充空白，元素左移动； （自前向后前移操作，顺序不能颠倒）,下图b,c间红线表示； 
    • 02C1-5. 单元删除
      •   1.单元素删除，批量操作特例； [r] =[r,r+1); 2. 单个删除，被删除的后续们，统一前移动； 3.每次循环耗时正比于删除区间的后缀长度 = n-hi =O(n) 4. 而循环次数等于区间宽度 = hi-lo =O(n); 由3,4 得知 总体O(n)复杂度；
    • 02C2. 查找
      •  1.由hi-->lo 查找； 2. 输入敏感 （input-sensitive） ： 最好，最差相差悬殊，输入敏感的算法；与规模有关； 最好O（1）：第一个元素命中； 最差O（n）：最后一个元素命中； 无序： 只有判等： 有序： 判定，比较 
      • 1.判等
        • 
      • 2.比较
        • 
    • 02C3. 去重/唯一化
      • 去重：     
    • 02C4. 遍历
      •    
  • D1.有序向量：唯一化
    • 02D1-1. 有序性
      •  1. 逆序则计数；n+=(_elem[i-1] >_elem[i]);统计逆序程度；
      • 1.顺序、逆序
      • 2.逆序程度
    • 02D1-2. 唯一化（低效版）
      •     向量_elem[i-1] 与向量_elem[i]相同（==），移除当前向量；否则增加； 时间复杂度 每个都是i-1;
      • 1.重复的元素构成一个区间，只需保留一个元素而已。
    • 02D1-3. 复杂度（低效版）
      •  1. 运行时间取决于while 循环；
      • 亦步亦趋
      • 1.根据 ，同一元素，被删除元素之后的元素，重复的元素，需要反复删除，移动
    • 子主题
    • 02D1-4. 唯一化（高效版）
      •  
      • 一步到位
      • 2.重复区间为单位，重复删除雷同政策；性能必将改进
    • 02D1-5. 实例与分析（高效版）
      •  1.n-1词迭代；累计O(n)次； 比对，复制，只有比对不同才复制； 2.通过巧妙设置向量长度，删除重复元素； 
    • 子主题
  • D2.有序向量：二分查找(A)
    • 2023-01-07 补充笔记；
    • 02D2-1. 概述
      •  
    • 02D2-2. 接口
      • 
    • 02D2-3. 语义
      • 
    • 02D2-4. 原理
      • 
    • 02D2-5. 实现
      • 
    • 02D2-6. 实例
      • 
• 第三章 列表
• 第四章 栈与队列
• 第五章 二叉树
• 第六章 图
• 第七章 图的应用
• 主题
• 主题
  • 子主题
    • 标注