数据结构复习

线性表

算法1.1 将原本有序的两个带头节点的单链表La和Lb合并成Lc。

void mergeList(LinkedList La, LinkedList Lb, LinkedList &Lc)
{
	Node *p = La->next, *q = Lb->next;
	Lc = La;
	while (p && q) {
		if (p->data <= q->data) {
			Lc->next = p;
			p = p->next;
		} else {
			Lc->next = q;
			q = q->next;
		}
		Lc = Lc->next;
	}
if (p) Lc->next = p;
else Lc->next = q;
}

以后再补充。

树和二叉树

• 二叉树的性质除了一堆显而易见的，只剩下一个$n_0 = n_2 + 1$。

• 满二叉树和完全二叉树：自己区分。

算法2.1 二叉树的先序中序后序遍历

void visit(BinTree T)
{
	if (!T) return;
	print(T->data);
	visit(T->lc);
	visit(T->rc);
}

线索二叉树：若没有孩子，则lc->前驱，rc->后继。

树转二叉树：lc->长子，rc->兄弟。

森林转二叉树：先把根节点拼起来变成树，然后树转二叉树。

哈夫曼树和哈夫曼编码

图