数据结构重点
- P36 前插法后插法创建单链表
- P53 算法设计题(1) (7)
- P60 链栈的入栈、出栈
- P125 例5.1
- P139 例5.2
- P142 例5.3
- P154 邻接矩阵
- P156 邻接表
- P166 普里姆算法
- P168 克鲁斯卡尔算法
- P175 例6.3
- P193 折半查找
- P201 二叉排序树的创建
- P241 冒泡排序
- P243 快速排序
- P251 筛选法调整堆
一.P36 前插法后插法创建单链表
1.前插法
前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。
代码描述：
void CreateList_H(LinkList& L, int n)
{
L = new Lnode;
L->next = NULL;
for (int i = 0; i < n; ++i) {
p = new Lnode;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
算法时间复杂度为 O（n）。
2.后插法创建单链表
void CreateList_R(LinkList& L, int n) {
L = new Lnode;
L->next = NULL;
r = L;
for (i = 0; i < n; ++i) {
p = new Lnode;
cin >> p->data;
p->next = null;
r->next = p;
r = p;
}
}
算法时间复杂度为 O（n）。
二.P53 算法设计题(1) (7)
(1 )将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的存储空间。表中不允许有重复的数据。
课后习题答案：
void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc)
{
pa = La->next; pb = Lb->next;
Lc = pc = La; //用La的头结点作为Lc的头结点
while (pa && pb)
{
if (pa->data < pb->data) { pc->next = pa; pc = pa; pa = pa->next; }
//取较小者La中的元素，将pa链接在pc的后面，pa指针后移
else if (pa->data > pb->data) { pc->next = pb; pc = pb; pb = pb->next; }
//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移
else //相等时取La中的元素，删除Lb中的元素
{
pc->next = pa; pc = pa; pa = pa->next;
q = pb->next; delete pb; pb = q;
}
}
pc->next = pa ? pa : pb; //插入剩余段
delete Lb; //释放Lb的头结点
}
说明：第三方的出现使得情况减少！！！
(7)设计一个算法，将链表中所有结点的链接方向 “原地” 逆转，即要求仅利用原表的存储空间，换句话说，要求算法的空间复杂度为 0(1)。
void Do(LinkList& L) {
//1->2->3->4
r = L->next;
L->next = NULL;
while (r) {
p = r->next;
r->next = L->next;
L->next = r;
r = p;
}
}
三.链栈的入栈、出栈
注意：非课后标准答案
void Push(LinkStack& L, SElemType e) {
p = new StackNode;
p->data = e;
p->next = L;
L = p;
}
void pop(LinkStack& L, SElemType e) {
if (L == NULL)e = NULL;
else
{
p = L;
e = L->data;
L = L->next;
delete p;
}
}
四.P125 例5.1
已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA, 请画出这棵二叉树。
由后序遍历特征，根结点必在后序序列尾部，即根结点是 A;
由中序遍历特征，根结点必在 其中间，而且
其左部必全部是左子树子孙(BDCE),
其右部必全部是右子树子孙(FHG);
继而，根据后序中的 DECB 子树可确定 B 为 A 的左孩子，根据 HGF 子串可确定 F 为 A的右孩子；依此类推，可以唯一地确定一棵二叉树，如图 5.13 所示。