算法与数据结构 --- 线性表 --- 顺序表和链表的比较，以及线性表的应用

第一部分 --- 顺序表和链表的比较

 即结点中存储的数据占的内存空间大小 除以 结点占的总内存空间大小

 

1.存储空间的溢出指的是当要存储的数据过多，存储空间不够时的数据溢出现象

---

第二部分 --- 线性表的应用

1.线性表在合并后不能够出现重复元素，而有序表在合并后，合并的总表中会出现所有的元素（可重复出现），且里面的元素依然按照值非递减有序排列

 

 1.上面这个算法的逻辑是：在Lb找元素，找到元素后将元素传给e，然后在La表中查找e，如果没找到的话就执行插入操作，如果找到的话就什么都不执行，继续循环

1.这个算法的本质就是在不停的从两个表组成的总元素中选最小元素（结合非递减排序特性选取）

1.最后一行那里补上一个7

 

1.关于时间复杂度：一般情况下我们都是考虑基础语句的最坏情况（最多次执行次数）作为时间复杂度，而上面算法中作为基础语句的循环判断的最坏情况（最多执行次数）为 La + Lb，所以算法复杂度为 O（La的长度 + Lb的长度）

（对于if语句而言，执行了if里的语句就不会再去执行else中的语句，所以x = a，y = b的时候就表明if判断总共执行了 a + b 次，上面这个循环也同理 ）

2.关于空间复杂度，由于我们在算法中创建了一个新的表Lc，且Lc的长度是La表的长度加上Lb表的长度，所以算法的空间复杂度就是上面那个了。

 

 给 pc -> next 赋值pa后，pc -> next是否为真，若为真的话则给pc -> next赋值pa，若为假的话则赋值pb

 （没有用处的头结点可以直接释放掉）

1.创建两个指针，然后让这两个指针分别指向两个链表的首元结点

2.插入剩余段那里要注意 段 这个词， 在链表中接上了某一个结点之后就相当于将这个结点后面的所有结点也跟着接上了

3.关于空间复杂度：由于我们在算法中没有创建新的内存空间，所以空间复杂度为O(1)

4.关于时间复杂度 --- 一般总是要考虑在最坏情况下的时间复杂度，所以上面的算法中作为基础语句的循环判断的最坏情况就是执行 La + Lb次，所以算法复杂度为 O（La的长度 + Lb的长度）

---

第三部分 --- 案例分析