数据结构——函数填空题
链队出队入队
入队：新指针p赋给队尾的下一个，再赋给队尾
出队：队首指针赋给p，后移 p的下一个赋给队首指向的下一个
若队尾==p，则证明首尾相连为1个
字符串匹配算法
二叉树
统计二叉树度为1的节点
树T为空，若左孩子为空，右孩子不为空，则递归1+该函数（右孩子）；反之，同样可得
最后返回 函数（左孩子）+函数（右孩子）
计算二叉树深度
若为空，否则：m n 分别嵌套左右孩子用此函数，谁大返回谁+1 if else
创建哈夫曼树
挑选函数（树，i-1,s1,s2）两个未被处理的最小权值的下标
两个的父母一起赋值i，树 i 结点 的左右孩子分别赋值 s1，s2，
则第i个结点的值就等于s1 s2结点的权重相加
图
最小生成树
closedge为数组，vexnum表示顶点总量
Min 遍历数组，找到不等于0的最小权值结点（小于当前min ），用i标记下标
实现Prim算法 构建最小生成树
更新顶点 dajvex对应vexs，lowcost 对应权值大小 arcs，以上均在图G的附带下进行
最短路径DJ算法
S表示该顶点未加入最短路径集合
D表示初始权值大小
第一块填空：w未加入集合，且权值小于最小值，则更新当前最近结点
第二块：如果w未加入集合，且通过v到w的距离更短（权值更小）：v的权值+两个权值边<w的权值，则更新w的权值大小为上面二者之和，通过的更新为v
堆排序
void HeapAdjust(int *a, int i, int n) // 调整堆
{
int max, j;
max = a[i]; // 保存当前父节点的值
for (j = 2 * i; j <= n; j = j * 2) // 沿较大的孩子节点向下筛选
{
if (j < n && a[j] < a[j + 1]) // 比较左右孩子
j++; // j指向较大的孩子
if (max >= a[j]) // 若父节点已大于等于最大孩子
break; // 筛选结束
a[i] = a[j]; // 否则将较大孩子上移
i = j; // 继续向下筛选
}
a[i] = max; // 将初始父节点值插入最终位置
}
void BuildHeap(int *a, int n) // 建立堆
{
int i;
for (i = n / 2; i >= 1; i--) // 从最后一个非叶节点开始调整
{
HeapAdjust(a, i, n);
}
}
void HeapSort(int *a, int n) // 堆排序
{
int i;
BuildHeap(a, n); // 初始建堆
for (i = n; i >= 1; i--) // 逐步将最大值交换到末尾
{
swap(a[1], a[i]); // 交换堆顶和当前末尾元素
HeapAdjust(a, 1, i - 1); // 调整剩余元素为堆
}
}
堆排序
快速排序
int Partition(SqList &L, int low, int high) { int pivotkey;pivotkey = L.elem[low]; // 选择第一个元素作为枢轴while (low < high) {while (low < high && L.elem[high] >= pivotkey) high--; // 从右向左找小于枢轴的元素L.elem[low] = L.elem[high];while (low < high && L.elem[low] <= pivotkey)low++; // 从左向右找大于枢轴的元素L.elem[high] = L.elem[low];}L.elem[low] = pivotkey; // 枢轴放入最终位置return low;
}void QSort(SqList &L, int low, int high) {int pivotloc;if (low < high) { pivotloc = Partition(L, low, high); // 划分QSort(L, low, pivotloc - 1); // 对左子表递归排序QSort(L, pivotloc + 1, high); // 对右子表递归排序}
}创建哈希表
初始位置为空，探测下一个位置（H0+i）%m，找到空位