T1二分查找

/*
算法思想:在数组a中, 从下标l到r中二分查找x
先找到中间点下标, 若x等于中间点, 直接返回下标即可
若x小于中间点, 说明答案在中间点的左边, 更新右边界即可
若x大于中间点, 说明答案在中间点的右边, 更新左边界即可
直至最后 l > r也没找到答案, 返回-1即可.

*/
int Binary_search(int a[], int l, int r, int x)
{
    while (l <= r)
    {
        int mid = (l + r) / 2; // 算出中间点下标
        if (a[mid] == x) return mid;
        if (a[mid] > x) r = mid - 1;
        else l = mid + 1;
    }

    return -1;
}

T2构建二叉排序树

/*
算法思想：不妨设线性表L为vector顺序存储,用build函数传入树的根节点,再依次遍历L,
用插入函数insert来插入每个节点构成二叉排序树。
*/

struct TreeNode 
{
    int val;
    TreeNode *left, *right;
    TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}

void insert(TreeNode* &u, int x)
{
    if (!u) u = new TreeNode(x); // 若当前节点为空，直接插入
    else if (x <= u->val) insert(u->left, x); // 若插入值不大于当前节点的值，往其左子树插入
    else insert(u-right, x); // 若插入值大于当前节点的值，往其右子树插入
}

void bulid(TreeNode* &root, vector<int> L)
{
    for (int i = 0; i < L.size(); i ++ )
        insert(root, L[i]);
}

T3删除链表的特定值

/*
算法思想：
可以设计一个del函数, 传入单链表头结点, min, max, 然后依次遍历链表L的每个点, 若不符合取值则删除，最后返回修改后链表的头结点
*/

struct LNode
{
    int val;
    LNode* next;
};

ListNode* del(ListNode* L, int min, int max)
{
    ListNode* p = L;
    while (p->next)
    {
        if (p->next->val >= min && p->next->val <= max)
        {
            ListNode* t = p->next;
            p->next = t->next;
            delete t;
        }
        else p = p->next;
    }

    return L;
}

T4写出DFS生出树（森林）的树边

/*
算法思想：
不妨设邻接表存储的图用dfs生成树
依次遍历每个点, 若当前点不在树中, 则dfs生成一棵以该点为根的树
*/

const int N = 1000; // 最大的点数

bool st[N]; // 标记是否在树中

struct ArcNode // 边结点
{
    int adjvex; // 指向的点
    ArcNode* next; // 下一条边
    ArcNode(int _adjvex): adjvex(_adjvex), next(NULL) {}
};

typedef struct VexNode
{
    int data; // 点的信息
    ArcNode* firstArc; // 第一条边
}AdjList[N];

struct LGraph
{
    int vexnum, arcnum;
    AdjList vexlist;
    LGraph(): vexlist() {}
};

void dfs(LGraph* g, int u)
{
    st[u] = true; // 先更新遍历点的状态
    for (ArcNode *p = g->vexlist[u].firstArc; p; p = p->next) // 再依次遍历点u的边
    {
        if (!st[p->adjvex]) // 若该点不在集合中, 则将u到该点的边加入生成树, 递归该点
        {
            printf("%d-%d ", u, p->adjvex);
            dfs(g, p->adjvex);
        }
    }
}

void Create(LGraph* g)
{
    for (int i = 1; i < g->vexnum; i ++ ) // 遍历每个点
        if (!st[i]) dfs(g, i); // 不在集合, 则生成一棵树
}