闲聊
儿童节快乐啊，虽然不是我们的节日，对于现在的我来说就是啊一个月又过去了，这一个月的计划又没有完成，没关系，6月继续努力！！
数据结构回顾
小知识点
- 邻接矩阵适用于稠密图的存储，而邻接链表适用于稀疏图的存储
- 一种抽象数据类型应该包含数据和操作两部分。（数据描述和操作声明）
- 在一棵二叉树的链式存储中，每个存储结点至少要包含2个指针域。[lchild data rchild]
- 通常情况下，查找数据相对较快的是哈希查找方法。
- 一个算法应该具有5个特性：可行性、有穷性、确定性、输入和输出。
- 数据结构的存储结构一般又：顺序存储、链式存储、索引存储和哈希存储四类。
- 数据结构涉及数据的逻辑结构、存储结构以及对数据的运算这三个方面的内容。
- 队列的特点是：先进先出，栈的特点是先进后出。
- 抽象类型树的存储结构有：双亲表示法、孩子表示法与孩子兄弟表示法等多种方法。
- 直接插入排序算法在平均情况下的时间复杂度为：$O(n^2)$，在最坏情况下的时间复杂度为$O(n^2)$。
- 快速排序算法在平均情况下的时间复杂度为：$O(nlog_2n)$，在最坏情况下的时间复杂度为：$O(n^2)$。（待排序列越接近无序，该算法效率越高）
快些选一堆，快速排序、希尔排序、简单选择排序，堆排序都是不稳定的，其他都是稳定的。 平均情况下：快速排序、希尔排序（复杂度了解即可）、归并排序和堆排序的时间复杂度均为$O(nlog_2n)$,（快些归队），其他都是$O(n^2)$。特殊的，基数排序：$O(d(n+r_d))$。最坏情况下：快速排序的时间复杂度为$O(n^2)$，其他和平均情况相同。
- 最小生成树算法
- 普里姆算法（Prim）:局部到整体思想，选点再选边。适合点比较少，边比较多的图。
- 克鲁斯卡尔（Kruskal）：先把所有顶点包含尽力啊，再来考虑最小权值（找到一条边，要验证是否构成了一个环，如果构成了一个环，则退回上一步，找比当前权值大一点的那条边。适合点多的图。
- 哈夫曼树解题一般方法：
- 将给出序列排序
- 选择出两个最小的数
- 将选出的2个数从数列中去除并且将两个数的和放入数列中
- 重复第一步
- 根结点不用编码，一般情况下，左分支编码为0，右分支编码为1。
- 用链接方式存储的队列，在进行删除运算时：头尾指针都可能要修改。（一般情况下，删除操作只需要移动头指针，但是当最后一个元素被删除时，要修改队尾指针，使其指向头指针。
- 散列表存储中冲突处理步骤时：往后移直到合理！
- 循环队列也存在空间溢出问题。（之前说因为顺序对存在假溢出问题所以使用循环队列，但是这里假溢出是指下标溢出，但是循环队列中依旧会存在空间溢出的问题）
- 二叉树结构是度不大于2的树结构
- 拓扑排序算法常用来判定一个有向图是否有环，所以有向有环图或者有向无环图都适用。
- 对于给定的n个元素，可以构造出的逻辑结构有：集合、线性结构、树形结构、图状结构或网状结构四种。
- 根据数据结构中元素之间相互关系的不同特性，通常有四类基本结构：集合结构、线性结构、树形结构、图状结构。
- 根据n个元素建立一个有序单链表的时间复杂度为：$O(n^2)$。
- 队列的插入操作在队尾进行。
- 若一个有向图有n个顶点和e条边，若采用邻接链表作为其存储结构，则该图的空间复杂度为：$O(n+e)$。
- 分支结点就是度不为0的结点
- 线性表只要以关键字有序方式存储就能进行折半查找。
- 对于具有e条边的无向图，他的邻接链表中共有2e个边结点。（对于任意一条边，在用邻接表表示时都需要表示2次，每次都涉及2个结点。
冒泡排序：
void bubble_sort(int a[], int n)
{
int i, j, temp;
for (i=n-1; i>0; i--)
{
for (j=0; j<i; j++)
{
if (a[j] > a[j+1])
{
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
直接插入排序
void straight_insert_sort(int a[], int n)
{
int i, j, temp;
for(i = 1; i < n; i++)
{
temp = a[i];
for(j = i - 1; a[i] < a[j]; j--)
{
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
恋词U29、U30
- territory n.领土；领地；领域；范围；版图；地域
- fearsome adj.可怕的
- commemorate v.纪念；庆祝
- drain n.排水沟；下水道；慢慢流出；消耗 v.流干；喝光；慢慢排去
- ditch n.沟；水道；渠道 v.开沟；修渠
- slack adj.懈怠的；松弛的；萧条的
- scarce adj.缺乏的；不足的；稀有的；罕见的
- unilateral adj.（行动或决定）一方的；单边的
- intrude v.侵入；闯入；打扰；侵扰
- monotonous adj.（声音）单调的；毫无变化的
- spontaneous adj.自发的；自然的；非由外力诱发的
- dullness n.单调
- moan n.呻吟声 v.呻吟
- mock v.嘲笑；讥笑；蔑视 adj.仿制的
- groan v.呻吟；抱怨 n.呻吟声；叹息
- sarcastic adj.讽刺的；挖苦的；尖刻的
- plague n.瘟疫；祸患；灾难；麻烦事；讨厌的人 v.不断困扰；使烦恼
- lag v.落后于；滞后于； n.落后；滞后
- deficiency n.缺乏；不足；缺陷；缺点
- lump n.块；肿块；瘤
- shrug v.n 耸肩
- shrug off 不把..当回事
- shove v.乱放；乱塞；用力推
- brainstorm v.集思广益；头脑风暴；集体献计
- puffed adj.气喘吁吁的；呼吸急促的
- moisture n.潮湿；湿气；湿度；水分
- census n.人口普查；人口调查
- cunning adj.狡猾的；狡诈的；巧妙的 n.狡猾；诡诈
- dust n.灰尘；粉尘 v.掸去
- leave sb in the dust 把某人远远抛在后面；使某人望尘莫及
- dilute v.稀释；冲淡 adj.稀释的；冲淡的
- fabulous adj.极好的；绝妙的；特别的；非凡的
- bind v.捆绑；困扎；束缚
- agitate v.鼓动；煽动；使焦虑
- lumber n.木材；树木；大木料
- tactic n.策略；战略
- deceit n.欺骗；欺骗行为
- tricky adj.难办的；难对付的；狡猾的，诡计多端的
- fraud n.欺诈；骗子；冒名顶替者
计组-C1-1.3
