闲聊

儿童节快乐啊，虽然不是我们的节日，对于现在的我来说就是啊一个月又过去了，这一个月的计划又没有完成，没关系，6月继续努力！！

数据结构回顾

小知识点

• 邻接矩阵适用于稠密图的存储，而邻接链表适用于稀疏图的存储
• 一种抽象数据类型应该包含数据和操作两部分。（数据描述和操作声明）
• 在一棵二叉树的链式存储中，每个存储结点至少要包含2个指针域。[lchild data rchild]
• 通常情况下，查找数据相对较快的是哈希查找方法。
• 一个算法应该具有5个特性：可行性、有穷性、确定性、输入和输出。
• 数据结构的存储结构一般又：顺序存储、链式存储、索引存储和哈希存储四类。
• 数据结构涉及数据的逻辑结构、存储结构以及对数据的运算这三个方面的内容。
• 队列的特点是：先进先出，栈的特点是先进后出。
• 抽象类型树的存储结构有：双亲表示法、孩子表示法与孩子兄弟表示法等多种方法。
• 直接插入排序算法在平均情况下的时间复杂度为：$O(n^2)$，在最坏情况下的时间复杂度为$O(n^2)$。
• 快速排序算法在平均情况下的时间复杂度为：$O(nlog_2n)$，在最坏情况下的时间复杂度为：$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