15.5 一些代码

阅读信息

约 850 个字 8 分钟本页总访问量：加载中... 次

课上复习

线性表顺序存储：数组链式存储：链表数组与链表存储的优缺点链表的操作典型习题：实现单链表的原地逆转（循环不变式），分别用一元多项式的两种表示实现多项式加法

堆栈顺序栈：数组，top++, top-- lianzhan：链表，top 即头指针应用：括号匹配检验，表达式求值，n 节汉诺塔问题（典型递归），迷宫问题快速排序递归用堆栈怎么实现？每次递归偶参数，这个参数代表起点终点大小，一种方法将参数压到堆栈中，每次循环从堆栈中抛出元素，拆成两个再压到堆栈中可以把所有递归用循环实现，核心是将参数压到堆栈中迷宫问题：用数组表示迷宫，0 表示通路，1 表示墙。一直沿着某个方向走。每次将（位置坐标，方向选择）压栈，回头表示先不断压栈再不断抛出。回溯法。

两个堆栈实现队列入队：如果栈 1 满但栈 2 空，将栈 1 中元素倒入栈 2，再将新元素放入栈 1 如果栈 1 有元素但没满，将栈 2 倒回栈 1，再新元素入栈出队：如果栈 2 有元素，直接抛出如果栈 2 空，将栈 1 所有元素倒入栈 2，再抛出

再一个数组中表示两个堆栈，实现空间共享：两头表示两个堆栈，从两边向中间放。满的判定：top_right == top_left + 1

树，level 和 degree 中序遍历时，n 在 m 前的条件是：n 在 m 的左方任意两点之间路径的长度的最大值定义未树的直径。给定树求直径

给定链表表示的二叉树，判断其是否为完全二叉树

左边是查找树，右边是查找树，根节点比左儿子打，比右儿子小，是不是查找树？不是左边是堆，右边是堆，根比左右儿子大，是不是堆？是

设计算法，判断一个序列可不可能是查找顺序初始为负无穷到正无穷。每次碰到小的元素，更新左边界；碰到大的元素，更新右边界。

树的双亲表示法和孩子表示法，左儿子右兄弟表示法。

图的表示：邻接矩阵，邻接表，逆邻接表，十字链表（有向图）

用 Floyd 算法判断图是否有回路？ Floyd：邻接矩阵的幂相加。检查对角线上元素，如果对角线上有非零元，则有环。

给定村庄和不同村庄间道路的长度。寻找位置，使其到各个村庄的距离之和最小。

哈希，求等概率成功与不成功查找的平均查找次数。

给定哈希函数和哈希结果，求最小的输入序列：构建有向图，求最小的拓扑序列

排序的辅助空间堆排序：无辅助空间快速排序：递归需要栈空间归并排序：额外需要数组

排序算法是否稳定：需要交换的肯定不稳定

很大的数据，在不完全排序的前提下找出前 m 小的元素：建立大小为 m 的堆，将所有元素依次插入

用快速排序找到第 k 大的元素

快速排序的非递归算法？将递归转化为循环？

一些代码

BST.c

C
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode* Position;
typedef Position BinTree; /* 二叉树类型 */
struct TNode {            /* 树结点定义 */
    ElementType Data;     /* 结点数据 */
    BinTree Left;         /* 指向左子树 */
    BinTree Right;        /* 指向右子树 */
};

Position Find(ElementType X, BinTree BST) {
    if (!BST)
        return NULL; /*查找失败*/
    if (X > BST->Data)
        return Find(X, BST->Right); /*在右子树中继续查找*/
    else if (X < BST->Data)
        return Find(X, BST->Left); /*在左子树中继续查找*/
    else                           /* X == BST->Data */
        return BST;                /*查找成功，返回结点的找到结点的地址*/
}

Position IterFind(ElementType X, BinTree BST) {
    while (BST) {
        if (X > BST->Data)
            BST = BST->Right; /*向右子树中移动，继续查找*/
        else if (X < BST->Data)
            BST = BST->Left; /*向左子树中移动，继续查找*/
        else                 /* X == BST->Data */
            return BST;      /*查找成功，返回结点的找到结点的地址*/
    }
    return NULL; /*查找失败*/
}

Position FindMin(BinTree BST) {
    if (!BST)
        return NULL; /*空的二叉搜索树，返回NULL*/
    else if (!BST->Left)
        return BST; /*找到最左叶结点并返回*/
    else
        return FindMin(BST->Left); /*沿左分支继续查找*/
}

Position FindMax(BinTree BST) {
    if (BST)
        while (BST->Right) /*沿右分支继续查找，直到最右叶结点*/
            BST = BST->Right;
    return BST;
}

BinTree Insert(BinTree BST, ElementType X) {
    if (!BST) { /* 若原树为空，生成并返回一个结点的二叉搜索树 */
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else { /* 开始找要插入元素的位置 */
        if (X < BST->Data)
            BST->Left = Insert(BST->Left, X); /*递归插入左子树*/
        else if (X > BST->Data)
            BST->Right = Insert(BST->Right, X); /*递归插入右子树*/
        /* else X已经存在，什么都不做 */
    }
    return BST;
}

BinTree Delete(BinTree BST, ElementType X) {
    Position Tmp;
    if (!BST)
        printf("要删除的元素未找到");
    else {
        if (X < BST->Data)
            BST->Left = Delete(BST->Left, X); /* 从左子树递归删除 */
        else if (X > BST->Data)
            BST->Right = Delete(BST->Right, X); /* 从右子树递归删除 */
        else {                                  /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */
            if (BST->Left && BST->Right) {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin(BST->Right);
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete(BST->Right, BST->Data);
            } else { /* 被删除结点有一个或无子结点 */
                Tmp = BST;
                if (!BST->Left) /* 只有右孩子或无子结点 */
                    BST = BST->Right;
                else /* 只有左孩子 */
                    BST = BST->Left;
                free(Tmp);
            }
        }
    }
    return BST;
}

表达式树

C
/*
二元表达式可以很自然的联系到二叉树:
以基本运算对象作为叶节点中的数据,
以运算符作为非叶节点中的数据,
其两棵子树是它的运算对象,
子树可以是基本运算对象，也可以是复杂表达式.

算式表达式和表达式树的关系如下：
    表达式树的先根遍历：前缀表达式
    表达式树的中根遍历：中缀表达式
    表达式树的后根遍历：后缀表达式

构建表达式树:
1. 给定一个表达式的中缀形式：(4+1*(5-2))-6/3
2. 首先将每个运算加上括号，区分优先级，得到(4+(1*(5-2)))-(6/3)
3. 括号外的-优先级最低，作为根节点，(4+(1*(5-2)))作为左子树，(6/3)作为右子树；
4. 递归的转换4+(1*(5-2))，+最为根节点，4是左子树，
    (1*(5-2))是右子树。*是右子树的根节点，1是左子树，(5-2)是右子树。
    最后计算(5-2)，-是根节点，5是左子树，2是右子树。
构造好表达式树之后，前缀表达式和中缀表达式可根据先根遍历和后根遍历得到。
    前缀表达式：- + 4 * 1 - 5 2 / 6 3
    后缀表达式：4 1 5 2 - * + 6 3 / -
*/

#include <stdio.h>
#define MAXN 1000

int lch[MAXN], rch[MAXN];
char op[MAXN];
int nc = 0;  // 结点数

int build_tree(char* s, int x, int y) {
    int i, c1 = -1, c2 = -1, p = 0;
    int u;
    if (y - x == 1)  // 仅一个字符，建立单独结点
    {
        u = ++nc;
        lch[u] = rch[u] = 0;
        op[u] = s[x];
        return u;
    }
    for (i = x; i < y; i++) {
        switch (s[i]) {
            case '(':
                p++;
                break;
            case ')':
                p--;
                break;
            case '+':
            case '-':
                if (!p)
                    c1 = i;
                break;
            case '*':
            case '/':
                if (!p)
                    c2 = i;
                break;
        }
    }
    if (c1 < 0)
        c1 = c2;  // 找不到括号外的加减号，就用乘除号
    if (c1 < 0)
        return build_tree(s, x + 1, y - 1);  // 整个表达式被一对括号括起来
    u = ++nc;
    lch[u] = build_tree(s, x, c1);
    rch[u] = build_tree(s, c1 + 1, y);
    op[u] = s[c1];
    return u;
}

线索二叉树

C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

// 线索二叉树
typedef struct ThreadNode {
    int data;
    struct ThreadNode *left, *right;
    int ltag, rtag;  // tag为0表示有孩子
} ThreadNode;

// 指向当前访问变量的前驱
ThreadNode* pre = NULL;

void visit(ThreadNode* node);

// 初始化节点
ThreadNode* initNode() {
    ThreadNode* Node = (ThreadNode*)malloc(sizeof(ThreadNode));
    Node->left = NULL;
    Node->right = NULL;
    Node->ltag = 0;  // 默认节点有左右孩子
    Node->rtag = 0;
    return Node;
}

// 插入新节点并赋值
bool insertNode(ThreadNode* node, int data, int contain) {
    ThreadNode* newNode = initNode();
    // contain为0时向左插入,为1时向右插入
    if (node->left == NULL && contain == 0) {
        node->left = newNode;
        newNode->data = data;
        return true;
    } else if (node->right == NULL && contain == 1) {
        node->right = newNode;
        newNode->data = data;
        return true;
    }
    free(newNode);
    return false;
}

// 边中序遍历边线索化二叉树
void InThread(ThreadNode* node) {
    if (node != NULL) {
        InThread(node->left);   // 遍历左子树
        visit(node);            // 访问根节点
        InThread(node->right);  // 遍历右子树
    }
}

// 创建中序线索化二叉树
void createInThread(ThreadNode* node) {
    // 重置全局变量
    pre = NULL;
    InThread(node);
    // 最后一个遍历的节点的后继设置为NULL
    pre->right = NULL;
    pre->rtag = 1;
}

// 找到以node为根的子树中，最先被中序遍历的节点
ThreadNode* FirstNode(ThreadNode* node) {
    // 当为空时
    if (node == NULL) {
        return NULL;
    }
    while (node->ltag == 0) {
        node = node->left;
    }
    return node;
}

// 找到以node为根的子树中，最后被中序遍历的节点
ThreadNode* LastNode(ThreadNode* node) {
    if (node == NULL) {
        return NULL;
    }
    while (node->rtag == 0) {
        node = node->right;
    }
    return node;
}

// 访问根节点
void visit(ThreadNode* node) {
    if (node->left == NULL) {
        node->left = pre;
        node->ltag = 1;
    }

    if (pre != NULL && pre->right == NULL) {
        pre->right = node;
        pre->rtag = 1;
    }
    pre = node;
}

// 在中序二叉树中找到p的后继节点
ThreadNode* NextNode(ThreadNode* p) {
    if (p->rtag == 0) {
        return FirstNode(p->right);
    }
    return p->right;
}

void visit0(ThreadNode* thread_node) {
    printf("%d  ", thread_node->data);
}

// 利用线索对二叉树进行非递归遍历
void Inorder(ThreadNode* rootNode) {
    for (ThreadNode* p = FirstNode(rootNode); p != NULL; p = NextNode(p)) {
        visit0(p);
    }
}

// 在中序二叉树中找到p的前驱节点
ThreadNode* BeforeNode(ThreadNode* p) {
    if (p->ltag == 0) {
        return LastNode(p->left);
    }
    return p->left;
}

// 利用线索对二叉树进行非递归逆序遍历
void InorderNi(ThreadNode* rootNode) {
    for (ThreadNode* p = LastNode(rootNode); p != NULL; p = BeforeNode(p)) {
        visit0(p);
    }
}

int main(void) {
    // 初始化二叉树
    ThreadNode* rootNode = initNode();
    // 测试根节点插入数据
    rootNode->data = 1;
    printf("根节点数据:%d\n", rootNode->data);
    // 测试往二叉树创建节点
    insertNode(rootNode, 2, 0);
    insertNode(rootNode, 3, 1);
    printf("第二层左节点数据:%d\n第二层右节点数据:%d\n", rootNode->left->data,
           rootNode->right->data);
    insertNode(rootNode->left, 4, 1);
    insertNode(rootNode->right, 5, 1);
    printf("第三层第一个节点右指针数据:%d\n第三层第二个节点右指针数据:%d\n",
           rootNode->left->right->data, rootNode->right->right->data);
    insertNode(rootNode->left->right, 6, 0);
    printf("第四层第一个节点左指针数据:%d\n",
           rootNode->left->right->left->data);

    createInThread(rootNode);

    printf("中序遍历:\n");
    Inorder(rootNode);
    printf("\n逆中序遍历:\n");
    InorderNi(rootNode);
}