• 实验四中的实验3的样本程序与“实验三：排序查找的实现及其应用”中的“二叉搜索树查找算法程序”合并为一个功能更加完善的程序
• 以下代码由冯文龙编写而成
• 学号 : 18029111
• Website : 独清独醒

#include 
#include "stdlib.h"
#include 
#include 
#include 
#include "ctype.h"
#define Null 0
#define False 0
#define True 1

typedef int KeyType;
typedef struct {
    char name[20];
    KeyType key;
    int otherterm;
} ElemType;
typedef struct bnode {
    ElemType data;
    struct bnode* lchild, * rchild;
} BiTree;
BiTree* f = Null, * p = Null, * root = Null; /* f,p 为BiTree 类型的全局变量*/

BiTree* InsertBst(BiTree* tr, BiTree* s) {
    /* 将新结点s插入到由tr所指的二叉搜索树中*/
    BiTree* f, * p;
    p = tr;
    while (p != Null) {
        f = p;
        if (s->data.key == p->data.key)    return tr;
        if (s->data.key < p->data.key)        p = p->lchild;
        else                            p = p->rchild;
    }
    if (tr == Null) return(s);
    if (s->data.key < f->data.key)            f->lchild = s;
    else                                f->rchild = s;
    return(tr);
}

BiTree* creatord() {        /* 建立二叉搜索树*/
    BiTree* tr, * s;
    int x;
    char myname[20];
    tr = Null;
    printf("请输入数据记录的关键字值[值为-1时结束输入！]: ");
    scanf("%d", &x);
    while (x != -1) {
        printf("输入该记录的名称: ");
        scanf("%s", &myname[0]);
        s = (BiTree*)malloc(sizeof(BiTree));
        s->data.key = x;
        strcpy(s->data.name, myname);
        s->data.otherterm = 0;
        s->lchild = Null;
        s->rchild = Null;
        tr = InsertBst(tr, s);
        printf("请输入下一个数据记录的关键字值[值为-1时结束输入！]: ");
        scanf("%d", &x);
    }
    return(tr);
}

BiTree* SearchBST(BiTree * T, KeyType key) {    //二叉搜索树递归查找
    if (T == NULL)    return Null;            // 查找失败
    else if (key == T->data.key) return T;    //查找成功
    else if (key < T->data.key)
        return SearchBST(T->lchild, key);    //查找左子树
    else    return SearchBST(T->rchild, key);//查找右子树
}

BiTree * SearchBSTWithoutRecursion(BiTree * T, KeyType key) {//二叉搜索树非递归查找
    p = T;
    while (p) {
        if (key == p->data.key)    return  p;    //查找成功
        if (key < p->data.key) p = p->lchild;    //查找左子树
        else    p = p->rchild;                //查找右子树
    }
    return NULL;    //查找失败
}

int ModiSearchBST(BiTree * T, KeyType key) {    //用于插入的查找
    p = T;
    while (p) {
        if (key == p->data.key)    return 1;
        else if (key < p->data.key) {
            f = p;    p = p->lchild;
        }
        else {
            f = p;    p = p->rchild;
        }
    }
    return 0;
}

int InsertBST(BiTree * T, ElemType e) {//二叉搜索树的插入算法
    BiTree* s;
    if (!ModiSearchBST(T, e.key)) {
        printf("结点不存在，插入新结点!\n");
        s = (BiTree*)malloc(sizeof(BiTree));
        s->data = e;
        s->lchild = NULL;    s->rchild = NULL;
        if (!f)    T = s;
        else if (e.key < f->data.key)    f->lchild = s;
        else                        f->rchild = s;
        return 1;
    }
    printf("结点存在!\n");
    return 0;
}



void bst_delete(BiTree * T, KeyType key) {//二叉搜索树的删除算法
    BiTree* parent, * p, * q, * child;
    parent = NULL;    p = T;
    while (p) {
        if (p->data.key == key)    break;
        parent = p;
        p = (key < p->data.key) ? p->lchild : p->rchild;
    }
    if (!p)        return;
    q = p;
    if (q->lchild && q->rchild)
        for (parent = q, p = q->lchild; p->rchild; parent = p, p = p->rchild);
    child = (p->lchild) ? p->lchild : p->rchild;
    if (!parent)    T = child;
    else {
        if (p == parent->lchild)    parent->lchild = child;
        else                    parent->rchild = child;
        if (p != q)                q->data.key = p->data.key;
    }
    free(p);
}

void InOrder(BiTree * tr) {        /* 中序遍历二叉树*/
    if (tr != Null) {
        InOrder(tr->lchild);
        printf("%-4d;", tr->data.key);
        printf("%-10s;", tr->data.name);
        printf("%-4d\n", tr->data.otherterm);
        InOrder(tr->rchild);
    }
}/* InOrder */



void DestOrder(BiTree* tr) {        /*从右子树开始遍历二叉排序树*/
    if (tr != NULL) {
        DestOrder(tr->rchild);
        printf("%4d", tr->data.key);
        DestOrder(tr->lchild);
    }
}




void main() {
    int key;
    ElemType e;
    char cmd;
    do {
        do {
            system("cls");
            printf("\n\tc,C......创建二叉搜索树");
            printf("\n\ti,I .....中序遍历结果");
            printf("\n\td,D......查找关键字");
            printf("\n\ts,S......关键字插入结点");
            printf("\n\ts,B......删除结点的关键字"); 
            printf("\n\ts,E......数据递减输出结果");
            printf("\n\tq,Q......退出\n\t请选择:");
            cmd = getchar();
        } while ((toupper(cmd) != 'D') && (toupper(cmd) != 'Q') && (toupper(cmd) != 'I') && (toupper(cmd) != 'C') && (toupper(cmd) != 'S'));
        switch (cmd) {
        case 'c':
        case 'C':
            root = creatord();
            break;
        case 'i':
        case 'I': 
            InOrder(root);
            _getch();
            break;
        case 'd':
        case 'D':
            printf("输入要查找的关键字");
            scanf("%d", &key);
            printf("输出二叉搜索树递归查找的结果：\n");
            p = SearchBST(root, key);
            if (p)
                printf("查找成功!\n");
            else
                printf("查找失败!\n");
            printf("输出二叉搜索树非递归查找的结果：\n");
            p = SearchBSTWithoutRecursion(root, key);
            if (p)
                printf("查找成功!\n");
            else
                printf("查找失败!\n");
            _getch();
            break;
        case 's':
        case 'S':
            printf("输入关键字插入的节点");
            scanf("%d", &e.key);
            printf("输入该记录的名称: ");
            scanf("%s", e.name);
            e.otherterm = 0;
            InsertBST(root, e);
            _getch();
            break;
        case 'b':
        case 'B':
            printf("输入删除结点的关键字");
            scanf("%d", &key);
            bst_delete(root, key);
            _getch();
            break;
        case 'e':
        case 'E':
            DestOrder(root);
            _getch();
            break;
        }
    } while ((cmd != 'q') && (cmd != 'Q'));
    system("pause");
}

• 实验三中实验6代码
• 以下代码由高宇编写而成
• 学号 : 18029101

#include"pch.h"
#include
//#include "stdafx.h"
#include 
#include "stdlib.h"
#include 
#include 
#define MaxSize 100    //线性表最大元素个数，可调。
//#define FValue 1010;    //配置卡号初值。

typedef  struct {
    long  cno;        // 学号
    float  mark;// 学生成绩
    float cflag;    

} ElemType;    //自定义数据类型，可调。
typedef  struct {
    ElemType  *list;    // 存储空间基址指针
    int  size;        // 当前元素个数
    int maxsize;        // 存储空间长度    
} SqList;

void init_sq(SqList &L);
int find(SqList L, long cardnumber);
int addnew(SqList &L, long &cardnumber);
void actnew(SqList &L);

void display(SqList L);
void SelectSort(SqList &L);
void displayall(SqList L);
void exitout();

int _tmain(int argc, _TCHAR* argv[]) {
    long cardnumber;
    long cnum;
    int flag;

    SqList student;
    char choose = '\0';
    //cnum = FValue;
    init_sq(student);

    while (1) {
        system("cls");
        fflush(stdin);
        printf("\n\n\n\n");
        printf("\n\t||---------------------------------------------------------||");
        printf("\n\t|                       1. 记录学生成绩                     |");
        printf("\n\t|                       2. 求平均分                         |");
        printf("\n\t|                       3. 成绩汇总                         |");
        printf("\n\t|                       4. 学生信息查询                     |");
        printf("\n\t|                       5. 信息显示(按成绩递减排序)         |");
        printf("\n\t|                       0. 退   出                          |");
        printf("\n\t|---------------------------------------------------------- |");
        printf("\n\t请选择(0-5)：");
        choose = getchar();
        switch (choose) {
        case '1': flag = addnew(student, cnum);
            if (flag == -1) {
                printf("内存分配错误，无法增加新卡！\n");
                _getch();
            }
            else {
                printf("学生信息录入成功！\n");
                printf("请按任意键继续…");
                _getch();
            }
            break;
        case '2': actnew(student);
            printf("请按任意键继续…");
            _getch();
            break;
        case '3':  displayall(student);
            
                printf("请按任意键继续…");
                
            break;
        case '4': display(student);
            break;
        
        case '5': SelectSort(student);
            displayall(student);

            break;
        case 'e': break;
        case '0': exitout();
            break;
        default: printf("\n\t输入错误，请重新选择！");
            _getch();
        }
    }
}

void init_sq(SqList &L) {    //顺序表初始化
    L.list = (ElemType *)malloc(MaxSize * sizeof(ElemType));
    L.size = 0;
    L.maxsize = MaxSize;
}

int againMalloc(SqList &L) {//存储空间再分配
    ElemType *newbase = (ElemType *)realloc(L.list, (L.maxsize * 2) * sizeof(ElemType));
    if (!newbase) {
        printf("存储空间分配失败！");
        return 0;
    }
    L.list = newbase;
    L.maxsize = 2 * L.maxsize;
    return 1;
}

int find(SqList L, long cardnumber) {//按值查找元素，返回元素所在位置；失败时返回。
    int i;
    L.list[0].cno = cardnumber;    //监视哨存放在list[0]
    //从尾至头递减查找
    for (i = L.size; cardnumber != L.list[i].cno; i--);
    return i;                //查找成功：返回找到记录的下标；
                        //查找失败：返回
}


int addnew(SqList &L, long &cardnumber) {
    int f;
    float b;
    long a;    

    printf("请输入学号");
    scanf_s("%ld",&a );
    printf("请输入成绩");
    scanf_s("%f", &b);
    L.list[L.size].cno = a;
    L.list[L.size].mark = b;
    L.size++;
    
    
    if (L.size >= L.maxsize) {
        f = againMalloc(L);
        if (!f)    return -1;
    }

    
    return 1;
}

void actnew(SqList &L)
{

    float z=0;
    int i;