数据结构与算法、网络模型总结

基本数据结构

数组

特点：

1. 存储空间连续

2. 只能防止相同数据类型

3. 可随机读写

4. 中间插入或删除元素时间复杂度O(n)

链表

特点：

1. 可使用零散的内存空间

2. 每个元素包含下一个或上一个元素指针

3. 查找元素时间复杂度为O(n)

4. 插入和删除元素总体成本比数组低

hash表

数组和链表的组合，可在O(1)时间内访问和增删数据

栈

数组或链表限定操作条件：后进先出。

队列

数组或链表限定操作条件：先进先出。

二叉排序树

定义：

1. 左子树上所有节点的值均小于或等于它根节点的值

2. 右子树上所有节点的值均大于或等于它根节点的值

3. 左、右子树也分别为二叉排序树

特点：

可在O(logn)时间复杂度内查找到元素

缺点：

在最坏情况下会退化为链表，查找时间复杂度提高到O(n)

平衡二叉树和红黑树

两者都可解决二叉排序树左右子树不平衡或退化为链表到问题

平衡二叉树大量增删时，效率低下，而红黑树最多只需要3次旋转就会从新达到平衡

但红黑树的平衡性不如平衡二叉树，故查找效率不如平衡二叉树。

网络模型

阻塞式I/O模型



当进程在等待数据时，若该数据一直没有产生，则该进程将一直等待，直到等待的数据产生为止，这个过程中进程的状态是阻塞的。





非阻塞式I/O模型

在非阻塞式I/O模型中，当进程等待内核的数据，而当该数据未到达的时候，进程会不断询问内核，直到内核准备好数据。





I/O多路复用

由一个线程轮询，当有数据可读或可写时，调用相应的处理函数。

常用的IO多路复用技术有两种，select和epoll。

select特点是线程轮询所有队列中的socket，逐个处理，当队列中socket数量过多时，轮询消耗时间较多。

epoll则是通过事件响应的方式唤醒处理线程。效率较select高且无最大待处理socket数量限制。