数据结构与算法

Day3 链表

数组&链表的存储结构

• 数组需要连续的内存空间来存储
• 不需要连续的内存空间来存储，通过指针将一组零散的内存块串联起来

指针含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量

单链表

循环链表

双向链表

双向循环链表

链表vs链表性能

链表代码技巧

• 警惕指针丢失和内存泄漏

  • 插入操作，注意操作顺序
  • 删除链表结点时，注意手动释放内存空间

• 加入哨兵

  • 处理边界情况
  • 针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理

• 边界处理
  • 如果链表为空时，代码是否能正常工作
  • 如果链表只包含一个结点时，代码是否能正常工作
  • 如果链表只包含两个结点时，代码是否能正常工作
  • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作

链表思考题

• 单链表反转
• 链表中环的检测
• 两个有序的链表合并
• 删除链表倒数第 n 个结点
• 求链表的中间结点
• 用链表判断一个字符串为回文字符串

引用地址

代码地址waiting...

数据结构与算法

第二天【数组】

思考

1. 数组如何实现随机访问
2. 低效的“插入”和“删除”
3. 数组的访问越界问题
4. 容器能否完全替代数组

数组如何实现随机访问

数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组类型相同的数据

1. 线性表&非线性表

2. 连续的内存空间

• 计算公式

// data_type_size 存储的类型数据大小
a[i]_address = base_address + i + data_type_size

• 随机访问

时间复杂度为O(1)：数组支持随机访问，支持下标随机访问

低效的’插入‘和‘删除’

• 插入操作

  • 队首：时间复杂度 O(n) 所有数组数据后移一位
  • 队尾：时间复杂度 O(1) 不需要移动数据
  • 插入第K个位置：时间复杂度O(1)
  • 平均时间复杂度：(1+2+~+n)/n = O(n)

• 删除操作

  • 队首：时间复杂度 O(n)
  • 队尾：时间复杂度 O(1)
  • 删除某几个连续空间数据：垃圾回收机制，先标记为删除，当数组储存空间不足时，一次性清理已标记删除的数据

数组的访问越界问题

C语言数组越界，会一直处于死循环（了解C语言越界问题）

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

容器能否完全代替数组

1. JAVA ArrayList无法存储基本类型，特别关注性能优化可以选择数组
2. 数据大小事先已知，可以选择数组
3. 多维数组[][]

数组下标为何从0开始

a[k]_address = base_address + k * type_size
a[k]_address = base_address + (k - 1) * type_size

1. cpu多做一次减法指令操作
2. 历史问题，采用C语言格式，下标从0开始

课后思考

1. 多维数组[m][n]内存寻址计算方式？

a[i][j]_address = base_address + (i * n + j) * type_size

2. JVM垃圾回收机制

JVM标记清除算法：

大多数主流虚拟机采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有 GC ROOTS，将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后，清理工作才会开始。

不足：1.效率问题。标记和清理效率都不高，但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。

回答引用于此

打卡第一天

复杂度分析

1. 所有代码的执行时间T(n)与每行代码的执行次数成正比

   T(n) = O(f(n))

2. 大O时间复杂度表示法

• 代码执行时间随数据增长的变化趋势（渐进时间复杂度-时间复杂度）

• 只关注循环次数最多的那一段代码

• 加法法则：总复杂度等于量级最大的那段代码的次数

• 乘法法则：嵌套代码等于嵌套内外代码复杂度的乘积

• 常见时间复杂度大O表示法

  • 常量阶O(1)
  • 指数阶O(2^n)
  • 对数O(logn)
  • 阶乘O(n!)
  • 线性阶O(n)
  • 线性对数阶O(nlogn)
  • 平方阶 立方阶 ~ k方阶O(n^2)

3. 空间复杂度

• 算法执行时间随数据规模大小的增长趋势（占cpu内存分配大小）

4. 复杂度分析

• 最好、最坏情况时间复杂度
• 平均情况时间复杂度
• 均摊情况时间复杂度

5. 课后思考

// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个2倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来array数组中的数据依次copy到new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array复制给array，array现在大小就是2倍len了
     array = new_array;
     len = 2 * len;
   }
   // 将element放到下标为i的位置，下标i加一
   array[i] = element;
   ++i;
}

最好时间复杂度是：O(1) 数组空闲时，直接插入对应的下标
最坏时间复杂度是：O(n) 数组非空闲时，申请两倍大小，遍历2*n次，常数阶忽略
均摊时间复杂度：O(1) 每2n次遍历之后连续接n-1次O(1)操作