数据结构课本中的算法

//函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函数返回值类型，其值是函数结果状态代码。
typedef int Status;

ADT Complex{
    数据对象 : D = {e1, e2 | e1, e2∈R, R是实数集}
    数据关系 : S = {<e1, e2> | e1是复数的实部, e2 是复数的虚部}
    基本操作 :
        Creat(&C, x, y)
        操作结果 : 构造复数C,
        其实部和虚部分别被赋予参数x和y的值.
        GetReal(C)
        初始条件 : 复数C已存在.
        操作结果 : 返回复数C的实部值.
        GetImag(C)
        初始条件 : 复数C已存在.
        操作结果 : 返回复数C的虚部值.
        Add(C1, C2)
        初始条件 : C1,C2是复数.
        操作结果 : 返回两个复数C1和C2的和.
        Sub(C1, C2)
        初始条件 : C1,C2是复数.
        操作结果 : 返回两个复数C1和C2的差.
} ADT Complex

typedef struct // 复数类型
{
    float Realpart;  // 实部
    float Imagepart; // 虚部
} Complex;

#include<iostream>

struct Complex {  // 直接使用 struct 定义类型
    float Realpart;  // 实部
    float Imagepart; // 虚部
};

void Create(Complex &C, float x, float y) {
    // 构造一个复数
    C.Realpart = x;
    C.Imagepart = y;
}

float GetReal(const Complex &C) {  // 使用引用并添加 const 以避免不必要的复制，并表明不会修改参数
    // 取复数C=x+yi的实部
    return C.Realpart;
}

float GetImag(const Complex &C) {
    // 取复数C=x+yi的虚部
    return C.Imagepart;
}

Complex Add(const Complex &C1, const Complex &C2) {
    // 求两个复数C1和C2的和sum
    Complex sum;
    sum.Realpart = C1.Realpart + C2.Realpart;
    sum.Imagepart = C1.Imagepart + C2.Imagepart;
    return sum;
}

Complex Sub(const Complex &C1, const Complex &C2) {
    // 求两个复数C1和C2的差difference
    Complex difference;
    difference.Realpart = C1.Realpart - C2.Realpart;
    difference.Imagepart = C1.Imagepart - C2.Imagepart;
    return difference;
}

int main() {
    Complex a;  // 直接声明一个 Complex 对象
    Create(a, 1, 2);
    std::cout << "Real part: " << GetReal(a) << ", Imaginary part: " << GetImag(a) << std::endl;
    return 0;
}

for (i = 1; i <= n; i++)     // 频度为n+1
    for (j = 1; j <= n; j++) // 频度为n*(n+1)
    {
        c[i][j] = 0;                               // 频度为n^2
        for (k = 1; k <= n; k++)                   // 频度为n^2*(n + 1)
            c[i][j] = c[i][j] + a[i][k] * b[k][j]; // 频度为n^3
    }

//- - - - - 顺序表的存储结构- - - - -
#define MAXSIZE 100 // 顺序表可能达到的最大长度
typedef struct
{
    ElemType *elem; // 存储空间的基地址
    int length;     // 当前长度
} SqList;           // 顺序表的结构类型为SqList

Status InitList(SqList &L)
{                                   // 构造一个空的顺序表L
    L.elem = new ElemType[MAXSIZE]; // 为顺序表分配一个大小为MAXSIZE的数组空间
    if (!L.elem) exit(OVERFLOW);     //存储分配失败退出
    L.length = 0;                   // 空表长度为0
    return OK;
}

Status GetElem(SqList L, int i, ElemType &e)
{
    if (i < 1 || i > L.length)
        return ERROR;  // 判断i值是否合理，若不合理，返回ERROR
    e = L.elem[i - 1]; // elem[i-1]单元存储第i个数据元素
    return OK;
}

int LocateElem(SqList L, ElemType e)
{ // 在顺序表L中查找值为e的数据元素，返回其序号
    for (i = 0; i < L.length; i++)
        if (L.elem[i] == e)
            return i + 1; // 查找成功，返回序号i+1
    return 0;             // 查找失败，返回0
}

Status ListInsert(SqList &L, int i, ElemType e)
{ // 在顺序表L中第i个位置插入新的元素e，
    if ((i < 1) || (i > L.length + 1)) return ERROR; // i值不合法
    if (L.length == MAXSIZE) return ERROR;            // 当前存储空间已满
    for (j = L.length - 1; j >= i - 1; j--)
        L.elem[j + 1] = L.elem[j];  //插入位置及之后的元素后移
    L.elem[i - 1] = e;              //将新元素e放入第i个位置
    ++L.length;                     // 表长加1
    return OK;
}

Status ListDelete(SqList &L, int i)
{ // 在顺序表L中删除第i个元素，i值的合法范围是1≤i≤L.length
    if ((i < 1) || (i > L.length))
        return ERROR; // i值不合法
    for (j = i; j <= L.length - 1; j++)
        L.elem[j - 1] = L.elem[j]; // 被删除元素之后的元素前移
    --L.length;                    // 表长减1
    return OK;
}

typedef struct LNode
{
    ElemType data;      // 节点的数据域
    struct LNode *next; // 节点的指针域
} LNode, *LinkList;     // LinkList为指向结构体LNode的指针类型

Status InitList(LinkList &L)
{                   // 构造一个空的单链表L
    L = new LNode;  // 生成新节点作为头节点，用头指针L指向头节点
    L->next = NULL; // 头节点的指针域置空
    return OK;
}

LNode *LocateElem(LinkList L，ElemType e)
{                             // 在带头节点的单链表L中查找值为e的元素
    p = L->next;              // 初始化，p指向首元节点
    while (p && p->data != e) // 顺链域向后查找，直到p为空或p所指节点的数据域等于e
        p = p->next;          // p指向下一个节点
    return p;                 // 查找成功返回值为e的节点地址p，查找失败p为NULL
}

Status ListInsert(LinkList &L, int i, ElemType e)
{ // 在带头节点的单链表L中第i个位置插入值为e的新节点
    p = L;
    j = 0;
    while (p && (j < i - 1))
    {
        p = p->next;
        ++j;
    } // 查找第i − 1个节点，p指向该节点
    if (!p || j > i - 1)
        return ERROR;  // i＞n+1或者i＜1
    s = new LNode;     // 生成新节点*s
    s->data = e;       // 将节点*s的数据域置为e
    s->next = p->next; // 将节点*s的指针域指向节点ai
    p->next = s;       // 将节点*p的指针域指向节点*s
    return OK;
}

Status ListDelete(LinkList &L, int i)
{ // 在带头节点的单链表L中，删除第i个元素
    p = L;
    j = 0;
    while ((p->next) && (j < i - 1)) // 查找第i − 1个节点，p指向该节点
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || (j > i - 1))
        return ERROR;  // 当i>n或i<1时，删除位置不合理
    q = p->next;       // 临时保存被删节点的地址以备释放
    p->next = q->next; // 改变删除节点前驱节点的指针域
    delete q;          // 释放删除节点的空间
    return OK;
}

void CreateList_H(LinkList &L, int n)
{ // 逆位序输入n个元素的值，建立带表头节点的单链表L
    L = new LNode;
    L->next = NULL; // 先建立一个带头节点的空链表
    for (i = 0; i < n; ++i)
    {
        p = new LNode;  // 生成新节点*p
        cin >> p->data; // 输入元素值赋给新节点*p的数据域
        p->next = L->next;
        L->next = p; // 将新节点*p插入到头节点之后
    }
}

void CreateList_R(LinkList &L, int n)
{ // 正位序输入n个元素的值，建立带表头节点的单链表L
    L = new LNode;
    L->next = NULL; // 先建立一个带头节点的空链表
    r = L;          // 尾指针r指向头节点
    for (i = 0; i < n; ++i)
    {
        p = new LNode;  // 生成新节点
        cin >> p->data; // 输入元素值赋给新节点*p的数据域
        p->next = NULL;
        r->next = p; // 将新节点*p插入尾节点*r之后
        r = p;       // r指向新的尾节点*p
    }
}

//- - - - - 双向链表的存储结构- - - - -
typedef struct DuLNode
{
    ElemType data;         // 数据域
    struct DuLNode *prior; // 指向直接前驱
    struct DuLNode *next;  // 指向直接后继
} DuLNode, *DuLinkList;

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{                                 // 在带头节点的双向链表L中第i个位置之前插入元素e
    if (!(p = GetElem_DuL(L, i))) // 在L中确定第i个元素的位置指针p
        return ERROR;             // p为NULL时，第i个元素不存在
    s = new DuLNode;              // 生成新节点*s
    s->data = e;                  // 将节点*s数据域置为e
    s->prior = p->prior;          // 将节点*s插入L中
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}

Status ListDelete_DuL(DuLinkList &L, int i)
{                                 // 删除带头节点的双向链表L中的第i个元素
    if (!(p = GetElem_DuL(L, i))) // 在L中确定第i个元素的位置指针p
        return ERROR;             // p为NULL时，第i个元素不存在
    p->prior->next = p->next;     // 修改被删节点的前驱节点的后继指针
    p->next->prior = p->prior;    // 修改被删节点的后继节点的前驱指针
    delete p;                     // 释放被删节点的空间
    return OK;
}

void MergeList(List &LA, List LB)
{ // 将所有在线性表LB中但不在LA中的数据元素插入LA中
    m = ListLength(LA);
    n = ListLength(LB); // 求线性表的长度
    for (i = 1; i <= n; i++)
    {
        GetElem(LB, i, e);          // 取LB中第i个数据元素赋给e
        if (!LocateElem(LA, e))     // LA中不存在和e相同的数据元素
            ListInsert(LA, ++m, e); // 将e插在LA的最后
    }
}

voidMergeList_Sq(SqListLA, SqListLB, SqList &LC)
{ // 已知顺序有序表LA和LB的元素按值非递减排列
    // 归并LA和LB得到新的顺序有序表LC，LC的元素也按值非递减排列
    LC.length = LA.length + LB.length; // 新表长度为待合并两表的长度之和
    LC.elem = newElemType[LC.length];  // 为合并后的新表分配一个数组空间
    pc = LC.elem;                      // 指针pc指向新表的第一个元素
    pa = LA.elem;
    pb = LB.elem; // 指针pa和pb的初值分别指向两个表的第一个元素
    pa_last = LA.elem + LA.length - 1;         // 指针pa_last指向LA的最后一个元素
    pb_last = LB.elem + LB.length - 1;         // 指针pb_last指向LB的最后一个元素
    while ((pa <= pa_last) && (pb <= pb_last)) // 未达到LA和LB的表尾
    {
        if (*pa <= *pb)
            *pc++ = *pa++; // 依次摘取两表中值较小的节点插入LC的最后
        else
            *pc++ = *pb++;
    }
    while (pa <= pa_last)
        *pc++ = *pa++; // 已到达LB表尾，依次将LA的剩余元素插入LC的最后
    while (pb <= pb_last)
        *pc++ = *pb++; // 已到达LA表尾，依次将LB的剩余元素插入LC的最后
}

void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC)
{ // 已知单链表LA和LB的元素按值非递减排列
    // 归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列
    pa = LA->next;
    pb = LB->next; // pa和pb的初值分别指向两个表的第一个节点
    LC = LA;       // 用LA的头节点作为LC的头节点
    pc = LC;       // pc的初值指向LC的头节点
    while (pa && pb)
    {                             // LA和LB均未到达表尾，依次“摘取”两表中值较小的节点插入到LC的最后
        if (pa->data <= pb->data) // 摘取pa所指节点
        {
            pc->next = pa; // 将pa所指节点链接到pc所指节点之后
            pc = pa;       // pc指向pa
            pa = pa->next; // pa指向下一节点
        }
        else // 摘取pb所指节点
        {
            pc->next = pb; // 将pb所指节点链接到pc所指节点之后
            pc = pb;       // pc指向pb
            pb = pb->next; // pb指向下一节点
        }
    } // while
    pc->next = pa ? pa : pb; // 将非空表的剩余段插入到pc所指节点之后
    delete LB;               // 释放LB的头节点
}

//- - - - - 顺序栈的存储结构- - - - -
#define MAXSIZE 100 // 顺序栈存储空间的初始分配量
typedef struct
{
    SElemType *base; // 栈底指针
    SElemType *top;  // 栈顶指针
    int stacksize;   // 栈可用的最大容量
} SqStack;

Status InitStack(SqStack &S)
{                                    // 构造一个空栈S
    S.base = new SElemType[MAXSIZE]; // 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
    if (!S.base)
        exit(OVERFLOW);    // 存储分配失败
    S.top = S.base;        // top初始为base，空栈
    S.stacksize = MAXSIZE; // stacksize置为栈的最大容量MAXSIZE
    return OK;
}

Status Push(SqStack &S, SElemType e)
{ // 插入元素e为新的栈顶元素
    if (S.top - S.base == S.stacksize)
        return ERROR; // 栈满
    *S.top++ = e;     // 将元素e压入栈顶，栈顶指针加1
    return OK;
}

Status Pop(SqStack &S, SElemType &e)
{ // 删除S的栈顶元素，用e返回其值
    if (S.top == S.base)
        return ERROR; // 栈空
    e = *--S.top;     // 栈顶指针减1，将栈顶元素赋给e
    return OK;
}

SElemType GetTop(SqStack S)
{                                  // 返回S的栈顶元素，不修改栈顶指针
    if (S.top != S.base)           // 栈非空
        return *(S.top - 1); // 返回栈顶元素的值，栈顶指针不变
}

//- - - - - 链栈的存储结构- - - - -
typedef struct StackNode
{
    ElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;

Status InitStack(LinkStack &S)
{ // 构造一个空栈S，栈顶指针置空
    S = NULL;
    return OK;
}

Status Push(LinkStack &S, SElemType e)
{                      // 在栈顶插入元素e
    p = new StackNode; // 生成新节点
    p->data = e;       // 将新节点数据域置为e
    p->next = S;       // 将新节点插入栈顶
    S = p;             // 修改栈顶指针为p
    return OK;
}

Status Pop(LinkStack &S, SElemType &e)
{ // 删除S的栈顶元素，用e返回其值
    if (S == NULL)
        return ERROR; // 栈空
    e = S->data;      // 将栈顶元素赋给e
    p = S;            // 用p临时保存栈顶元素空间，以备释放
    S = S->next;      // 修改栈顶指针
    delete p;         // 释放原栈顶元素的空间
    return OK;
}

SElemType GetTop(LinkStack S)
{                       // 返回S的栈顶元素，不修改栈顶指针
    if (S != NULL)      // 栈非空
        return S->data; // 返回栈顶元素的值，栈顶指针不变
}

void TraverseList(LinkList p)
{
    if (p == NULL)
        return; // 递归终止
    else
    {
        cout << p->data << endl; // 输出当前节点的数据域
        TraverseList(p->next);   // p指向后继节点继续递归
    }
}

void Hanoi(int n, char A, char B, char C)
{ // 将塔座A上的n个圆盘按规则搬到塔座C上，塔座B作为辅助塔座
    if (n == 1)
        move(A, 1, C); // 将编号为1的圆盘从塔座A移到塔座C
    else
    {
        Hanoi(n - 1, A, C, B); // 将A上编号为1至n-1的圆盘移到塔座B，塔座C作为辅助塔座
        move(A, n, C);         // 将编号为n的圆盘从塔座A移到塔座C
        Hanoi(n - 1, B, A, C); // 将B上编号为1至n-1的圆盘移到塔座C，塔座A作为辅助塔座
    }
}

//- - - - - 队列的顺序存储结构- - - - -
#define MAXQSIZE 100 // 队列可能达到的最大长度
typedef struct
{
    QElemType *base; // 存储空间的基地址
    int front;       // 头指针
    int rear;        // 尾指针
} SqQueue;

Status InitQueue(SqQueue &Q)
{                                     // 构造一个空队列Q
    Q.base = new QElemType[MAXQSIZE]; // 为队列分配一个最大容量为MAXQSIZE的数组空间
    if (!Q.base)
        exit(OVERFLOW);   // 存储分配失败
    Q.front = Q.rear = 0; // 将头指针和尾指针置为0，队列为空
    return OK;
}

int QueueLength(SqQueue Q)
{ // 返回Q的元素个数，即队列的长度
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

Status EnQueue(SqQueue &Q, QElemType e)
{                                           // 插入元素e为Q的新的队尾元素
    if ((Q.rear + 1) % MAXQSIZE == Q.front) // 若尾指针在循环意义上加1后等于头指针，表明队满
        return ERROR;
    Q.base[Q.rear] = e;               // 新元素插入队尾
    Q.rear = (Q.rear + 1) % MAXQSIZE; // 队尾指针加1
    return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e)
{ // 删除Q的队头元素，用e返回其值
    if (Q.front == Q.rear)
        return ERROR;                   // 队空
    e = Q.base[Q.front];                // 保存队头元素
    Q.front = (Q.front + 1) % MAXQSIZE; // 队头指针加1
    return OK;
}

QElemType GetHead(SqQueue Q)
{                               // 返回Q的队头元素，不修改队头指针
    if (Q.front != Q.rear)      // 队列非空
        return Q.base[Q.front]; // 返回队头元素的值，队头指针不变
}

//- - - - - 队列的链式存储结构- - - - -
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;
typedef struct
{
    QueuePtr front; // 队头指针
    QueuePtr rear;  // 队尾指针
} LinkQueue;

Status InitQueue(LinkQueue &Q)
{                                 // 构造一个空队列Q
    Q.front = Q.rear = new QNode; // 生成新节点作为头节点，队头和队尾指针指向此节点
    Q.front->next = NULL;         // 头节点的指针域置空
    return OK;
}

Status EnQueue(LinkQueue &Q, QElemType e)
{                  // 插入元素e为Q的新的队尾元素
    p = new QNode; // 为入队元素分配节点空间，用指针p指向
    p->data = e;   // 将新节点数据域置为e
    p->next = NULL;
    Q.rear->next = p; // 将新节点插入队尾
    Q.rear = p;       // 修改队尾指针
    return OK;
}

Status DeQueue(LinkQueue &Q, QElemType &e)
{ // 删除Q的队头元素，用e返回其值
    if (Q.front == Q.rear)
        return ERROR;        // 若队列为空，则返回ERROR
    p = Q.front->next;       // p指向队头元素
    e = p->data;             // e保存队头元素的值
    Q.front->next = p->next; // 修改头节点的指针域
    if (Q.rear == p)
        Q.rear = Q.front; // 最后一个元素被删，队尾指针指向头节点
    delete p;             // 释放原队头元素的空间
    return OK;
}

QElemType GetHead(LinkQueue Q)
{                                   // 返回Q的队头元素，不修改队头指针
    if (Q.front != Q.rear)          // 队列非空
        return Q.front->next->data; // 返回队头元素的值，队头指针不变
}

int Index_BF(SString S, SString T, int pos)
{ // 返回模式T在主串S中第pos个字符开始第一次出现的位置。若不存在，则返回0
    // 其中，T非空，1≤pos≤S.length
    i = pos;
    j = 1;                           // 初始化
    while (i≤S.length && j≤T.length) // 两个串均未比较到串尾
    {
        if (S.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
        } // 继续比较后继字符
        else
        {
            // i是在主串中的位置，减去对比的长度j，等于本次没有比较，且i回退一格，所以+1是i回到原本的位置，+2是去下一个字符所在的位置
            i = i - j + 2;
            j = 1;
        } // 指针后退，重新开始匹配
    }

    if (j > T.length)           // 此时i，j在正确匹配的后一格，减去模式串长度=正确匹配时的第一个元素的位置
        return i - T.length;    // 匹配成功
    else
        return 0;               // 匹配失败
}

int Index_KMP(SString S, SString T, int pos)
{ // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
    // 其中，T非空，1≤pos≤S.length
    i = pos;
    j = 1;
    while (i <= S.length && j <= T.length) // 两个串均未比较到串尾
    {
        if (j == 0‖S.ch [i] == T.ch[j])
        {
            ++i;
            ++j;
        } // 继续比较后续字符
        else
            j = next[j]; // 模式串向右移动
    }
    if (j > T.length)
        return i - T.length; // 匹配成功
    else
        return 0; // 匹配失败
}

void get_next(SString T, int next[])
{ // 求模式串T的next函数值并将其存入数组next
    i = 1;
    next[1] = 0;
    j = 0;
    while (i < T.length)
    {
        if (j == 0‖T.ch [i] == T.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

void get_nextval(SString T, int nextval[])
{ // 求模式串T的next函数修正值并将之存入数组nextval
    i = 1;
    nextval[1] = 0;
    j = 0;
    while (i < T.length)
    {
        if (j == 0‖T.ch [i] == T.ch[j])
        {
            ++i;
            ++j;
            if (T.ch[i] != T.ch[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

void InOrderTraverse(BiTree T)
{          // 中序遍历二叉树T的递归算法
    if (T) // 若二叉树非空
    {
        InOrderTraverse(T->lchild); // 中序遍历左子树
        cout << T->data;            // 访问根节点
        InOrderTraverse(T->rchild); // 中序遍历右子树
    }
}

void InOrderTraverse(BiTree T)
{ // 中序遍历二叉树T的非递归算法
    InitStack(S);
    p = T;
    q = new BiTNode;
    while (p || !StackEmpty(S))
    {
        if (p) // p非空
        {
            Push(S, p);    // 根指针进栈
            p = p->lchild; // 根指针进栈，遍历左子树
        }
        else // p为空
        {
            Pop(S, q);       // 退栈
            cout << q->data; // 访问根节点
            p = q->rchild;   // 遍历右子树
        }
    }
}

void CreateBiTree(BiTree &T)
{ // 按先序次序输入二叉树中节点的值（单字符），创建二叉链表表示的二叉树T
    cin >> ch;
    if (ch == '#')
        T = NULL; // 递归结束，建空树
    else          // 递归创建二叉树
    {
        T = new BiTNode;         // 生成根节点
        T->data = ch;            // 根节点数据域置为ch
        CreateBiTree(T->lchild); // 递归创建左子树
        CreateBiTree(T->rchild); // 递归创建右子树
    } // else
}

void Copy(BiTree T, BiTree &NewT)
{                  // 复制一棵和T完全相同的二叉树
    if (T == NULL) // 如果是空树，递归结束
    {
        NewT = NULL;
        return;
    }
    else
    {
        NewT = new BiTNode;
        NewT->data = T->data;          // 复制根节点
        Copy(T->lchild, NewT->lchild); // 递归复制左子树
        Copy(T->rchild, NewT->rchild); // 递归复制右子树

    } // else
}

int Depth(BiTree T)
{ // 计算二叉树T的深度
    if (T == NULL)
        return 0; // 如果是空树，深度为0，递归结束
    else
    {
        m = Depth(T->lchild);      // 递归计算左子树的深度记为m
        n = Depth(T->rchild);      // 递归计算右子树的深度记为n
        if (m > n) return (m + 1); // 二叉树的深度为m与n的较大者加1
        else return (n + 1);
    }
}

int NodeCount(BiTree T)
{ // 统计二叉树T中节点的个数
    if (T == NULL)
        return 0; // 如果是空树，则节点个数为0，递归结束
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    // 否则节点个数为左子树的节点个数+右子树的节点个数+1
}

void InThreading(BiThrTree p)
{ // pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
    if (p)
    {
        InThreading(p->lchild); // 左子树递归线索化
        if (!p->lchild)         // p的左孩子为空
        {
            p->LTag = 1;     // 给p加上左线索
            p->lchild = pre; // p的左孩子指针指向pre（前驱）
        } // if
        else
            p->LTag = 0;

        if (!pre->rchild) // pre的右孩子为空
        {
            pre->RTag = 1;   // 给pre加上右线索
            pre->rchild = p; // pre的右孩子指针指向p（后继）
        } // if
        else
            pre->RTag = 0;
        pre = p;                // 保持pre指向p
        InThreading(p->rchild); // 右子树递归线索化
    }
}

void InOrderThreading(BiThrTree &Thrt, BiThrTree T)
{                         // 中序遍历二叉树T，并将其中序线索化，Thrt指向头节点
    Thrt = new BiThrNode; // 建头节点
    Thrt->LTag = 0;       // 头节点没有前驱，Ltag一定为0，头节点有左孩子，若树非空，则其左孩子为树根
    Thrt->RTag = 1;       // 头节点的右孩子指针为右线索
    Thrt->rchild = Thrt;  // 初始化时右指针指向自己
    if (!T)
        Thrt->lchild = Thrt; // 若树为空，则左指针也指向自己
    else
    {
        Thrt->lchild = T;
        pre = Thrt;               // 头节点的左孩子指向根，pre初值指向头节点
        InThreading(T);     // 调用算法5.7，对以T为根的二叉树进行中序线索化
        pre->rchild = Thrt; // 算法5.7结束后，pre为最右节点，pre的右线索指向头节点
        pre->RTag = 1;
        Thrt->rchild = pre; // 头节点的右线索指向pre
    }
}

void InOrderTraverse_Thr(BiThrTree T)
{ // T指向头节点，头节点的左链lchild指向根节点，可参见线索化算法5.8。
    // 中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出
    p = T->lchild; // p指向根节点
    while (p != T) // 空树或遍历结束时，p==T
    {
        while (p->LTag == 0) p = p->lchild; // 沿左孩子向下
        cout << p->data;                    // 访问其左子树为空的节点
        while (p->RTag == 1 && p->rchild != T)
        {
            p = p->rchild;
            cout << p->data; // 沿右线索访问后继节点
        }
        p = p->rchild; // 转向p的右子树
    }
}

void CreateHuffmanTree(HuffmanTree &HT, int n)
{ // 构造哈夫曼树HT
    if (n <= 1)
        return;
    m = 2 * n - 1;  // n个节点，n-1个间隔，共2n-1个节点
    HT = new HTNode[m + 1];  // 0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根节点
    for (i = 1; i <= m; ++i) // 将1～m号单元中的双亲、左孩子，右孩子的下标都初始化为0
    {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for (i = 1; i <= n; ++i) // 输入前n个单元中叶子节点的权值
        cin >> HT[i].weight;
    /*- - - - - - - - - - -初始化工作结束，下面开始创建哈夫曼树- - - - - - - - - -*/
    for (i = n + 1; i <= m; ++i) 
    { // 通过n-1次的选择、删除、合并来创建哈夫曼树
        Select(HT, i - 1, s1, s2);
        // 在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的节点,并返回它们在HT中的序号s1和s2
        HT[s1].parent = i;
        HT[s2].parent = i;
        // 得到新节点i，从森林中删除s1，s2，将s1和s2的双亲域由0改为i
        HT[i].lchild = s1;
        HT[i].rchild = s2;                            // s1,s2分别作为i的左右孩子
        HT[i].weight = HT[s1].weight + HT[s2].weight; // i的权值为左右孩子权值之和
    } // for
}

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{                            // 从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
    HC = new char *[n + 1];  // 分配存储n个字符编码的编码表空间
    cd = new char[n];        // 分配临时存放每个字符编码的动态数组空间
    cd[n − 1] = '\0';        // 编码结束符
    for (i = 1; i <= n; ++i) // 逐个字符求哈夫曼编码
    {
        start = n - 1; // start开始时指向最后，即编码结束符位置
        c = i;
        f = HT[i].parent; // f指向节点c的双亲节点
        while (f != 0)    // 从叶子节点开始向上回溯，直到根节点
        {
            --start; // 回溯一次start向前指一个位置
            if (HT[f].lchild == c)
                cd[start] = '0'; // 节点c是f的左孩子，则生成代码0
            else
                cd[start] = '1'; // 节点c是f的右孩子，则生成代码1
            c = f;
            f = HT[f].parent; // 继续向上回溯
        } // 求出第i个字符的编码
        HC[i] = new char[n - start]; // 为第i个字符编码分配空间
        strcpy(HC[i], &cd[start]);   // 将求得的编码从临时空间cd复制到HC的当前行中
    } // for
    delete cd; // 释放临时空间
}

//-----图的邻接矩阵存储表示-----
#define MaxInt 32767     // 表示极大值，即∞
#define MVNum 100        // 最大顶点数
typedef char VerTexType; // 假设顶点的数据类型为字符型
typedef int ArcType;     // 假设边的权值类型为整型
typedef struct
{
    VerTexType vexs[MVNum];     // 顶点表
    ArcType arcs[MVNum][MVNum]; // 邻接矩阵
    int vexnum, arcnum;         // 图的当前点数和边数
} AMGraph;

Status CreateUDN(AMGraph &G)
{                                  // 采用邻接矩阵表示法，创建无向网G
    cin >> G.vexnum >> G.arcnum;   // 输入总顶点数，总边数
    for (i = 0; i < G.vexnum; ++i) // 依次输入点的信息
        cin >> G.vexs[i];
    for (i = 0; i < G.vexnum; ++i) // 初始化邻接矩阵，边的权值均置为极大值MaxInt
        for (j = 0; j < G.vexnum; ++j)
            G.arcs[i][j] = MaxInt;
    for (k = 0; k < G.arcnum; ++k) // 构造邻接矩阵
    {
        cin >> v1 >> v2 >> w; // 输入一条边依附的顶点及权值
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);        // 确定v1和v2在G中的位置，即顶点数组的下标
        G.arcs[i][j] = w;            // 边<v1, v2>的权值置为w
        G.arcs[j][i] = G.arcs[i][j]; // 置<v1, v2>的对称边<v2, v1>的权值为w
    } // for
    return OK;
}

//- - - - -图的邻接表存储表示- - - - -
#define MVNum 100      // 最大顶点数
typedef struct ArcNode // 边节点
{
    int adjvex;              // 该边所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条边的指针
    OtherInfo info;          // 和边相关的信息
} ArcNode;
typedef struct VNode // 顶点信息
{
    VerTexType data;
    ArcNode *firstarc;   // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum]; // AdjList表示邻接表类型
typedef struct           // 邻接表
{
    AdjList vertices;
    int vexnum, arcnum; // 图的当前顶点数和边数
} ALGraph;

Status CreateUDG(ALGraph &G)
{                                  // 采用邻接表表示法，创建无向图G
    cin >> G.vexnum >> G.arcnum;   // 输入总顶点数，总边数
    for (i = 0; i < G.vexnum; ++i) // 输入各点，构造表头节点表
    {
        cin >> G.vertices[i].data;     // 输入顶点值
        G.vertices[i].firstarc = NULL; // 初始化表头节点的指针域为NULL
    } // for
    for (k = 0; k < G.arcnum; ++k) // 输入各边，构造边表
    {
        cin >> v1 >> v2; // 输入一条边依附的两个顶点
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        // 确定v1和v2在G中的位置，即顶点在G.vertices中的序号
        p1 = new ArcNode; // 生成一个新的边节点*p1
        p1->adjvex = j;   // 邻接点序号为j
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1;
        // 将新节点*p1插入顶点vi的边表头部
        p2 = new ArcNode; // 生成另一个对称的新的边节点*p2
        p2->adjvex = i;   // 邻接点序号为i
        p2->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = p2;
        // 将新节点*p2插入顶点vj的边表头部
    } // for
    return OK;
}

//- - - - -有向图的十字链表存储表示- - - - -
#define MAX_VERTEX_NUM 20
typedef struct ArcBox
{
    int tailvex, headvex;         // 该弧的尾和头顶点的位置
    struct ArcBox *hlink, *tlink; // 分别为弧头相同和弧尾相同的弧的链域
    InfoType *info;               // 该弧相关信息的指针
} ArcBox;
typedef struct VexNode
{
    VertexType data;
    ArcBox *firstin, *firstout; // 分别指向该顶点第一条入弧和出弧
} VexNode;
typedef struct
{
    VexNode xlist[MAX_VERTEX_NUM]; // 表头向量
    int vexnum, arcnum;            // 有向图的当前顶点数和弧数
} OLGraph;

//- - - - -无向图的邻接多重表存储表示- - - - -
#define MAX_VERTEX_NUM 20
typedef enum
{
    unvisited,
    visited
} VisitIf;
typedef struct EBox
{
    VisitIf mark;               // 访问标记
    int ivex, jvex;             // 该边依附的两个顶点的位置
    struct EBox *ilink, *jlink; // 分别指向依附这两个顶点的下一条边
    InfoType *info;             // 该边信息指针
} Ebox;
typedef struct VexBox
{
    VertexType data;
    EBox *firstedge; // 指向第一条依附该顶点的边
} VexBox;
typedef struct
{
    VexBox adjmulist[MAX_VERTEX_NUM];
    int vexnum, edgenum; // 无向图的当前顶点数和边数
} AMLGraph;

bool visited[MVNum]; // 访问标志数组，其初值为“false”
void DFS(Graph G, int v)
{ // 从第v个顶点出发递归地深度优先遍历图G
    cout << v;
    visited[v] = true; // 访问第v个顶点，并置访问标志数组相应分量值为true
    for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
        // 依次检查v的所有邻接点w ，FirstAdjVex(G, v)表示v的第一个邻接点
        // NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w≥0表示存在邻接点
        if (!visited[w])
            DFS(G, w); // 对v的尚未访问的邻接顶点w递归调用DFS()
}

void DFSTraverse(Graph G)
{ // 对非连通图G进行深度优先遍历
    for (v = 0; v < G.vexnum; ++v)
        visited[v] = false;        // 访问标志数组初始化
    for (v = 0; v < G.vexnum; ++v) // 循环调用算法6.3
        if (!visited[v])
            DFS(G, v); // 对尚未访问的顶点调用DFS
}

void DFS _AM(AMGraph G, int v)
{ // 图G为邻接矩阵类型，从第v个顶点出发深度优先搜索遍历图G
    cout << v;
    visited[v] = true;             // 访问第v个顶点，并置访问标志数组相应分量值为true
    for (w = 0; w < G.vexnum; w++) // 依次检查邻接矩阵v所在的行
        if ((G.arcs[v][w] != 0) && (!visited[w]))
            DFS_AM(G, w);
    // G.arcs[v][w]!=0表示w是v的邻接点，如果w未访问，则递归调用DFS_AM()
}

void DFS_AL(ALGraph G, int v)
{ // 图G为邻接表类型，从第v个顶点出发深度优先搜索遍历图G
    cout << v;
    visited[v] = true;          // 访问第v个顶点，并置访问标志数组相应分量值为true
    p = G.vertices[v].firstarc; // p指向v的边链表的第一个边节点
    while (p != NULL)           // 边节点非空
    {
        w = p->adjvex; // 表示w是v的邻接点
        if (!visited[w])
            DFS_AL(G, w); // 如果w未访问，则递归调用DFS_AL()
        p = p->nextarc;   // p指向下一个边节点
    } // while
}

void BFS(Graph G, int v)
{ // 按广度优先非递归遍历连通图G
    cout << v;
    visited[v] = true;     // 访问第v个顶点，并置访问标志数组相应分量值为true
    InitQueue(Q);          // 辅助队列Q初始化，置空
    EnQueue(Q, v);         // v入队
    while (!QueueEmpty(Q)) // 队列非空
    {
        DeQueue(Q, u); // 队头元素出队并置为u
        for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
            // 依次检查u的所有邻接点w，FirstAdjVex(G,u)表示u的第一个邻接点
            // NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w≥0表示存在邻接点
            if (!visited[w]) // w为u的尚未访问的邻接顶点
            {
                cout << w;
                visited[w] = true; // 访问w，并置访问标志数组相应分量值为true
                EnQueue(Q, w);     // w入队
            } // if
    } // while
}

// 辅助数组的定义，用来记录从顶点集U到V-U的权值最小的边
struct
{
    VerTexType adjvex; // 最小边在U中的那个顶点
    ArcType lowcost;   // 最小边上的权值
} closedge[MVNum];

void MiniSpanTree_Prim(AMGraph G, VerTexType u)
{                                  // 无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边
    k = LocateVex(G, u);           // k为顶点u的下标
    for (j = 0; j < G.vexnum; ++j) // 对V−U的每一个顶点初始化closedge[j]
        if (j != k)
            closedge[j] = {u, G.arcs[k][j]}; //{adjvex, lowcost}
    closedge[k].lowcost = 0;                 // 初始，U={u}
    for (i = 1; i < G.vexnum; ++i)
    { // 选择其余n-1个顶点，生成n-1条边(n=G.vexnum)
        k = Min(closedge);
        // 求出T的下一个节点 ：第k个顶点，closedge[k]中存有当前最小边
        u0 = closedge[k].adjvex; // u0为最小边的一个顶点，u0∈U
        v0 = G.vexs[k];          // v0为最小边的另一个顶点，v0∈V − U
        cout << u0 << v0;        // 输出当前的最小边(u0, v0)
        closedge[k].lowcost = 0; // 第k个顶点并入U集
        for (j = 0; j < G.vexnum; ++j)
            if (G.arcs[k][j] < closedge[j].lowcost) // 新顶点并入U后重新选择最小边
                closedge[j] = {G.vexs[k], G.arcs[k][j]};
    } // for
}

// 辅助数组Edges的定义
struct
{
    VerTexType Head; // 边的始点
    VerTexType Tail; // 边的终点
    ArcType lowcost; // 边上的权值
} Edge[arcnum];

// 辅助数组Vexset的定义
int Vexset[MVNum];

void MiniSpanTree_ Kruskal(AMGraph G)
{                                  // 无向网G以邻接矩阵形式存储，构造G的最小生成树T，输出T的各条边
    Sort(Edge);                    // 将数组Edge中的元素按权值从小到大排序
    for (i = 0; i < G.vexnum; ++i) // 辅助数组，表示各顶点自成一个连通分量
        Vexset[i] = i;
    for (i = 0; i < G.arcnum; ++i) // 依次查看数组Edge中的边
    {
        v1 = LocateVex(G, Edge[i].Head); // v1为边的始点Head的下标
        v2 = LocateVex(G, Edge[i].Tail); // v2为边的终点Tail的下标
        vs1 = Vexset[v1];                // 获取边Edge[i]的始点所在的连通分量vs1
        vs2 = Vexset[v2];                // 获取边Edge[i]的终点所在的连通分量vs2
        if (vs1 != vs2)                  // 边的两个顶点分属不同的连通分量
        {
            cout << Edge[i].Head << Edge[i].Tail; // 输出此边
            for (j = 0; j < G.vexnum; ++j)        // 合并vs1和vs2两个分量，即两个集合统一编号
                if (Vexset[j] == vs2)
                    Vexset[j] = vs1; // 集合编号为vs2的都改为vs1
        } // if
    } // for
}

void ShortestPath_DIJ(AMGraph G, int v0)
{                           // 用Dijkstra算法求有向网的v0顶点到其余顶点的最短路径
    n = G.vexnum;           // n为G中顶点的个数
    for (v = 0; v < n; ++v) // n个顶点依次初始化
    {
        S[v] = false;         // S初始为空集
        D[v] = G.arcs[v0][v]; // 将v0到各个终点的最短路径长度初始化为弧上的权值
        if (D[v] < MaxInt)
            Path[v] = v0; // 如果v0和v之间有弧，则将v的前驱置为v0
        else
            Path[v] = -1; // 如果v0和v之间无弧，则将v的前驱置为-1
    } // for
    S[v0] = true; // 将v0加入S
    D[v0] = 0;    // 源点到源点的距离为0
    /*--------初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集---------*/
    for (i = 1; i < n; ++i) // 对其余n − 1个顶点，依次进行计算
    {
        min = MaxInt;
        for (w = 0; w < n; ++w)
            if (!S[w] && D[w] < min)
            {
                v = w;
                min = D[w];
            }                   // 选择一条当前的最短路径，终点为v
        S[v] = true;            // 将v加入S
        for (w = 0; w < n; ++w) // 更新从v0出发到集合V − S上所有顶点的最短路径长度
        {
            if (!S[w] && (D[v] + G.arcs[v][w] < D[w]))
            {
                D[w] = D[v] + G.arcs[v][w]; // 更新D[w]
                Path[w] = v;                // 更改w的前驱为v
            } // if
        }
    } // for
}

void ShortestPath_Floyd(AMGraph G)
{                                  // 用弗洛伊德算法求有向网G中各对顶点i和j之间的最短路径
    for (i = 0; i < G.vexnum; ++i) // 各对顶点之间初始已知路径及距离
        for (j = 0; j < G.vexnum; ++j)
        {
            D[i][j] = G.arcs[i][j];
            if (D[i][j] < MaxInt && i != j)
                Path[i][j] = i; // 如果i和j之间有弧，则将j的前驱置为i
            else
                Path[i][j] = -1; // 如果i和j之间无弧，则将j的前驱置为-1
        } // for
    for (k = 0; k < G.vexnum; ++k)
        for (i = 0; i < G.vexnum; ++i)
            for (j = 0; j < G.vexnum; ++j)
                if (D[i][k] + D[k][j] < D[i][j]) // 从i经k到j的一条路径更短
                {
                    D[i][j] = D[i][k] + D[k][j]; // 更新D[i][j]
                    Path[i][j] = Path[k][j];     // 更改j的前驱为k
                } // if
}

Status TopologicalSort(ALGraph G, int topo[])
{ // 有向图G采用邻接表作为存储结构
    // 若G无回路，则生成G的一个拓扑序列topo并返回OK，否则ERROR
    FindInDegree(G, indegree); // 求出各顶点的入度并存入数组indegree中
    InitStack(S);              // 栈S初始化为空
    for (i = 0; i < G.vexnum; ++i)
        if (!indegree[i])
            Push(S, i);    // 入度为0者进栈
    m = 0;                 // 对输出顶点计数，初始为0
    while (!StackEmpty(S)) // 栈S非空
    {
        Pop(S, i);                  // 使栈顶顶点vi出栈
        topo[m] = i;                // 将顶点vi保存在拓扑序列数组topo中
        ++m;                        // 对输出顶点计数
        p = G.vertices[i].firstarc; // p指向顶点vi的第一个邻接点
        while (p != NULL)
        {
            k = p->adjvex; // vk为vi的邻接点
            --indegree[k]; // vi的每个邻接点的入度减1
            if (indegree[k] == 0)
                Push(S, k); // 若入度减为0，则入栈
            p = p->nextarc; // p指向顶点vi下一个邻接节点
        } // while
    } // while
    if (m < G.vexnum)
        return ERROR; // 该有向图有回路
    else
        return OK;
}

Status CriticalPath(ALGraph G)
{ // G为邻接表存储的有向网，输出G的各项关键活动
    if (!TopologicalOrder(G, topo))
        return ERROR;
    // 调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR
    n = G.vexnum;           // n为顶点个数
    for (i = 0; i < n; i++) // 给每个事件的最早发生时间置初值0
        ve[i] = 0;
    /*- - - - - - - - - - - 按拓扑次序求每个事件的最早发生时间 - - - - - - - - - -*/
    for (i = 0; i < n; i++)
    {
        k = topo[i];                // 取得拓扑序列中的顶点序号k
        p = G.vertices[k].firstarc; // p指向k的第一个邻接顶点
        while (p != NULL)
        {                                  // 依次更新k的所有邻接顶点的最早发生时间
            j = p->adjvex;                 // j为邻接顶点的序号
            if (ve[j] < ve[k] + p->weight) // 更新顶点j的最早发生时间ve[j]
                ve[j] = ve[k] + p->weight;
            p = p->nextarc; // p指向k的下一个邻接顶点
        } // while
    } // for
    for (i = 0; i < n; i++) // 给每个事件的最迟发生时间置初值ve[n-1]
        vl[i] = ve[n - 1];
    /*- - - - - - - - - - - - -按逆拓扑次序求每个事件的最迟发生时间- -- - - - - - - - - - - -*/
    for (i = n - 1; i >= 0; i--)
    {
        k = topo[i];                // 取得拓扑序列中的顶点序号k
        p = G.vertices[k].firstarc; // p指向k的第一个邻接顶点
        while (p != NULL)           // 根据k的邻接点，更新k的最迟发生时间
        {
            j = p->adjvex;                 // j为邻接顶点的序号
            if (vl[k] > vl[j] - p->weight) // 更新顶点k的最迟发生时间vl[k]
                vl[k] = vl[j] - p->weight;
            p = p->nextarc; // p指向k的下一个邻接顶点
        } // while
    } // for
    /*- - - - - - - - - - - - - -- -判断每一活动是否为关键活动- -- - - - - - - - - - - -*/
    for (i = 0; i < n; i++) // 每次循环针对vi为活动开始点的所有活动
    {
        p = G.vertices[i].firstarc; // p指向i的第一个邻接顶点
        while (p != NULL)
        {
            j = p->adjvex;         // j为i的邻接顶点的序号
            e = ve[i];             // 计算活动<vi, vj>的最早开始时间
            l = vl[j] - p->weight; // 计算活动<vi, vj>的最迟开始时间
            if (e == l)            // 若为关键活动，则输出<vi, vj>
                cout << G.vertices[i].data << G.vertices[j].data;
            p = p->nextarc; // p指向i的下一个邻接顶点
        } // while
    } // for
}

typedef struct
{
    KeyType key;        // 关键字域
    InfoType otherinfo; // 其他域
} ElemType;
typedef struct
{
    ElemType *R; // 存储空间基地址
    int length;  // 当前长度
} SSTable;

int Search_Seq(SSTable ST, KeyType key)
{ // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
    for (i = ST.length; i >= 1; --i)
        if (ST.R[i].key == key)
            return i; // 从后往前查找
    return 0;
}

int Search_Seq(SSTable ST, KeyType key)
{                      // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
    ST.R[0].key = key; // “监视哨”
    for (i = ST.length; ST.R[i].key != key; --i); // 从后往前找
    return i;
}

int Search_Bin(SSTable ST, KeyType key)
{ // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
    low = 1;
    high = ST.length; // 置查找区间初值
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (key == ST.R[mid].key)
            return mid; // 找到待查元素
        else if (key < ST.R[mid].key)
            high = mid - 1; // 继续在前一子表进行查找
        else
            low = mid + 1; // 继续在后一子表进行查找
    } // while
    return 0; // 表中不存在待查元素
}

//- - - - -二叉排序树的二叉链表存储表示- - - - -
typedef struct
{
    KeyType key;        // 关键字项
    InfoType otherinfo; // 其他数据项
} ElemType;             // 每个节点的数据域的类型
typedef struct BSTNode
{
    ElemType data;                   // 每个节点的数据域包括关键字项和其他数据项
    struct BSTNode *lchild, *rchild; // 左右孩子指针
} BSTNode, *BSTree;

BSTree SearchBST(BSTree T, KeyType key)
{ // 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
    // 若查找成功，则返回指向该数据元素节点的指针，否则返回空指针
    if ((!T) || key == T->data.key)
        return T; // 查找结束
    else if (key < T->data.key)
        return SearchBST(T->lchild, key); // 在左子树中继续查找
    else
        return SearchBST(T->rchild, key); // 在右子树中继续查找
}

void InsertBST(BSTree &T, ElemType e)
{ // 当二叉排序树T中不存在关键字等于e.key的数据元素时，则插入该元素
    if (!T)
    {                                 // 找到插入位置，递归结束
        S = new BSTNode;              // 生成新节点*S
        S->data = e;                  // 新节点*S的数据域置为e
        S->lchild = S->rchild = NULL; // 新节点*S作为叶子节点
        T = S;                        // 把新节点*S链接到已找到的插入位置
    }
    else if (e.key < T->data.key)
        InsertBST(T->lchild, e); // 将*S插入左子树
    else if (e.key > T->data.key)
        InsertBST(T->rchild, e); // 将*S插入右子树
}

void CreatBST(BSTree &T)
{             // 依次读入关键字为key的节点，将相应节点插入二叉排序树T中
    T = NULL; // 将二叉排序树T初始化为空树
    cin >> e;
    while (e.key != ENDFLAG) // ENDFLAG为自定义常量，作为输入结束标志
    {
        InsertBST(T, e); // 将此节点插入二叉排序树T中
        cin >> e;
    }
}

void DeleteBST(BSTree &T, KeyType key)
{ // 从二叉排序树T中删除关键字等于key的节点
    p = T;
    f = NULL; // 初始化
    /*------------下面的while循环从根开始查找关键字等于key的节点*p---------------*/
    while (p)
    {
        if (p->data.key == key)
            break; // 找到关键字等于key的节点*p，结束循环
        f = p;     //*f为*p的双亲节点
        if (p->data.key > key)
            p = p->lchild; // 在*p的左子树中继续查找
        else
            p = p->rchild; // 在*p的右子树中继续查找
    } // while
    if (!p)
        return; // 找不到被删节点则返回
    /*----考虑3种情况实现p所指子树内部的处理 ：*p左右子树均不空、无右子树、无左子树---*/
    q = p;
    if ((p->lchild) && (p->rchild)) // 被删节点*p左右子树均不空
    {
        s = p->lchild;
        while (s->rchild) // 在*p的左子树中继续查找其前驱节点，即最右下节点
        {
            q = s;
            s = s->rchild; // 向右到尽头
        }
        p->data = s->data; // s指向被删节点的“前驱”
        if (q != p)
            q->rchild = s->lchild; // 重接*q的右子树
        else
            q->lchild = s->lchild; // 重接*q的左子树
        delete s;
        return;
    } // if
    else if (!p->rchild) // 被删节点*p无右子树，只需重接其左子树
    {
        p = p->lchild;
    } // else if
    else if (!p->lchild) // 被删节点*p无左子树，只需重接其右子树
    {
        p = p->rchild;
    } // else if
    /*-----------------将p所指的子树挂接到其双亲节点*f相应的位置----------------*/
    if (!f)
        T = p; // 被删节点为根节点
    else if (q == f->lchild)
        f->lchild = p; // 挂接到*f的左子树位置
    else
        f->rchild = p; // 挂接到*f的右子树位置
    delete q;
}

#define m 3 // B-树的阶，暂设为3
typedef struct BTNode
{
    int keynum;                // 节点中关键字的个数，即节点的大小
    struct BTNode *parent;     // 指向双亲节点
    KeyType K[m + 1];          // 关键字向量，0号单元未用
    struct BTNode *ptr[m + 1]; // 子树指针向量
    Record *recptr[m + 1];     // 记录指针向量，0号单元未用
} BTNode, *BTree;              // B-树节点和B-树的类型
typedef struct
{
    BTNode *pt; // 指向找到的节点
    int i;      // 1 ～ m，在节点中的关键字序号
    int tag;    // 1表示查找成功，0表示查找失败
} Result;       // B-树的查找结果类型

Result SearchBTree(BTree T, KeyType key)
{ // 在m阶B-树T上查找关键字key，返回结果(pt,i,tag)
    // 若查找成功，则特征值tag=1，指针pt所指节点中第i个关键字等于key
    // 否则特征值tag=0，等于key的关键字应插入在指针pt所指节点中第i个和第i+1个关键字之间
    p = T;
    q = NULL;
    found = FALSE;
    i = 0; // 初始化，p指向待查节点，q指向p的双亲
    while (p && !found)
    {
        i = Search(p, key);
        // 在p->K[1..keynum]中查找i，使得p->K[i]<=key<p->K[i+1]
        if (i > 0 && p->K[i] == key)
            found = TRUE; // 找到待查关键字
        else
        {
            q = p;
            p = p->ptr[i];
        }
    }
    if (found)
        return (p, i, l); // 查找成功
    else
        return (q, i, 0); // 查找不成功，返回key的插入位置信息
}

Status InsertBTree(BTree &T, KeyType key, BTree q, int i)
{ // 在m阶B-树T上节点*q的K[i]与K[i+1]之间插入关键字key
    // 若引起节点过大，则沿双亲链进行必要的节点分裂调整，使T仍是m阶B-树
    x = key;
    ap = NULL;
    finished = FALSE; // x表示新插入的关键字，ap为一个空指针
    while (q && !finished)
    {
        Insert(q, i, x, ap); // 将x和ap分别插入q->key[i+1]和q->ptr[i+1]
        if (q->keynum < m)
            finished = TRUE; // 插入完成
        else                 // 分裂节点
        {
            // s向上取整
            s = ceil((m + 1) / 2);
            split(q, s, ap);
            x = q->K[s];
            // 将q->K[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新节点*ap
            q = q->parent;
            if (q)
                i = Search(q, x); // 在双亲节点*q中查找x的插入位置
        } // else
    } // while
    if (!finished)            // T是空树（参数q初值为NULL）或者根节点已分裂为节点*q和*ap
        NewRoot(T, q, x, ap); // 生成含信息（T,x,ap）的新的根节点*T，原T和ap为子树指针
    return OK;
}

//- - - - -开放地址法散列表的存储表示- - - - -
#define m 20 // 散列表的表长
typedef struct
{
    KeyType key;        // 关键字项
    InfoType otherinfo; // 其他数据项
} HashTable[m];
#define NULLKEY 0 // 单元为空的标记
int SearchHash(HashTable HT, KeyType key)
{                // 在散列表HT中查找关键字为key的元素，若查找成功，返回散列表的单元标号，否则返回-1
    H0 = H(key); // 根据散列函数H（key）计算散列地址
    if (HT[H0].key == NULLKEY)
        return -1; // 若单元H0为空，则所查元素不存在
    else if (HT[H0].key == key)
        return H0; // 若单元H0中元素的关键字为key，则查找成功
    else
    {
        for (i = 1; i < m; ++i)
        {
            Hi = (H0 + i) % m; // 按照线性探测法计算下一个散列地址Hi
            if (HT[Hi].key == NULLKEY)
                return -1; // 若单元Hi为空，则所查元素不存在
            else if (HT[Hi].key == key)
                return Hi; // 若单元Hi中元素的关键字为key，则查找成功
        } // for
        return -1;
    } // else
}

void InsertSort(SqList &L)
{ // 对顺序表L进行直接插入排序
    for (i = 2; i <= L.length; ++i)
        if (L.r[i].key < L.r[i - 1].key) // “<”，需将r[i]插入有序子表
        {
            L.r[0] = L.r[i];                              // 将待插入的记录暂存到监视哨中
            L.r[i] = L.r[i - 1];                          // r[i-1]后移
            for (j = i - 2; L.r[0].key < L.r[j].key; --j) // 从后向前寻找插入位置
                L.r[j + 1] = L.r[j];                      // 记录逐个后移，直到找到插入位置
            L.r[j + 1] = L.r[0];                          // 将r[0]即原r[i]，插入正确位置
        } // if
}