#includeusing namespace std; #define Maxsize 50 typedef struct { int number; //学号，即关键字 char name[5]; char sex[2]; int age; }record; typedef struct { record stu[Maxsize]; int length; }seqlist; //表建立 void Create(seqlist& a) { a.length = 0; cout << "请依次输入学号、姓名、性别、年龄" << endl; int num = 0; int i = 0; while (true) { cout << "学号（输入为0，默认终止）：" << endl; cin >> num; if (num == 0) { break; } else { a.stu[i].number = num; cout << "姓名:" ; cin >> a.stu[i].name; cout << endl; cout << "性别："; cin >> a.stu[i].sex; cout << endl; cout << "年龄: "; cin >> a.stu[i].age; cout << endl; i++; a.length++; } } } //顺序查找 void Sqsearch(seqlist a) { int num = 0; cout << "请输入待查找学生的学号："; cin >> num; for(int i=0;i> temp; key = temp - 1; int low = 0; int high = a.length - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (key == mid) { cout << "成功找到!" << endl; cout << "学生信息为：" << endl; cout << "年龄为：" << a.stu[mid].age << endl; cout << "名字为：" << a.stu[mid].name << endl; cout << "性别为：" << a.stu[mid].sex << endl; return; } else if (key < mid) { high = mid - 1; } else { low = mid + 1; } } } //输出整个表 void showlist(seqlist a) { for (int i = 0;i < a.length;i++) { cout << "学号为：" << a.stu[i].number << endl; cout << "年龄为：" << a.stu[i].age << endl; cout << "名字为：" << a.stu[i].name << endl; cout << "性别为：" << a.stu[i].sex << endl; } } int main() { seqlist a; Create(a); cout << "输出创建后的表！" << endl; showlist(a); cout << "顺序查找" << endl; Sqsearch(a); cout << "折半查找" << endl; Search_Bin(a); }
题目要求：建立顺序表（有序表），分别对其进行顺序查找和折半查找，顺序查找实现的思路比较简单，从前到后遍历比较关键字即可（可以引入哨兵方便一些操作），折半查找的核心就是“分为区间块”，从中间往两头出发（需要注意一下下标，这里仔细一点就行），折半查找的前提和顺序查找不同，对于顺序查找而言，只需要顺序表，在物理上（内存中）满足线性关系即可完成遍历，但是对于折半查找而言，需要的不仅仅是顺序表，而要对顺序表按照大小进行排序形成有序表，因此在实现折半查找时，要先实现顺序表的排序算法（此处实验中没有要求，可以自己键入有顺序的顺序表来避免排序工作。）
#includeusing namespace std; #define Maxsize 50 typedef struct { int number; //关键字 char name[5]; char sex[2]; int age; }ElemType; //定义数据域类型 typedef struct BSTNode { ElemType data; struct BSTNode* lchild, * rchild; }BSTNode,*BSTree; //定义结点 //二叉排序树的插入 void InsertBST(BSTree &T, ElemType e) { BSTree S; if (!T) //如果是空树，直接插入根结点 { S = new BSTNode; S->data = e; S->lchild = S->rchild = NULL; T = S; } else if (e.number < T->data.number) //如果小于根结点则往左继续递归 { InsertBST(T->lchild, e); } else if (e.number > T->data.number) //如果大于根结点则往右继续递归 { InsertBST(T->rchild, e); } } //二叉排序树的创建 void CreatBST(BSTree &T) { ElemType e ; int n1 = 0; T = NULL; cout << "请输入根节点" << endl; cout << "请输入学号："; cin >> e.number; cout << endl; cout << "请输入名字:"; cin >> e.name; cout << endl; cout << "请输入性别:"; cin >> e.sex; cout << endl; cout << "请输入年龄："; cin >> e.age; cout << endl; cout << "请输入结点个数："; cin >> n1; cout << endl; while(e.number!=0) { InsertBST(T, e); cout << "请输入学号："; cin >> e.number; cout << endl; cout << "请输入名字:"; cin >> e.name; cout << endl; cout << "请输入性别:"; cin >> e.sex; cout << endl; cout << "请输入年龄："; cin >> e.age; cout << endl; } cout << "建立成功！" << endl; } //二叉排序树的查找 //若查找成功， 则返回指向该数据元素结点的指针,否则返回空指针 BSTree SearchBST(BSTree T, int e) { if (!T || e == T->data.number) { return T; //找到或树为空 } else if (e < T->data.number) { return SearchBST(T->lchild, e); } else { return SearchBST(T->rchild, e); } } //输出二叉排序树 void InorderTree(BSTree T) { if (T) { //学号 名字 性别 年龄 InorderTree(T->lchild); cout << "学号：" << T->data.number << endl; cout << "名字：" << T->data.name << endl; cout << "性别：" << T->data.sex << endl; cout << "年龄：" << T->data.age << endl; InorderTree(T->rchild); } } int main() { BSTNode* T = NULL; BSTNode* P = NULL; int n = 0; CreatBST(T);//在该函数内部递归调用了插入函数 InorderTree(T); cout << "请输入要咨询的学生的学号："; cin >> n; cout << endl; P = SearchBST(T, n); InorderTree(P); system("pause"); return 0; }
题目要求：构建二叉排序树，并实现插入、创建、查找操作（删除操作比较复杂，可以不做）
二叉树的算法核心在于递归（栈）的使用，按照大小顺序构建二叉树。此刻不去赘述二叉排序树的数据结构特点，而只谈算法实现中的一些技巧。
插入算法内部含有三个并行语句（根据结点关键词来选择执行语句），如果结点为空，则直接插入data，插入算法的递归体现在对待插入结点的选择，若要实现n个结点的二叉树构建，需要用到循环语句。体现在第66行的while循环语句，这里有一个注意的点，在执行过while判定后，首先执行插入语句，再执行输入新的data，而且根结点的搭建是在while语句外，这里主要涉及到一个顺序问题，具体解释起来同样会显得连篇累牍，如果不采取这个顺序，可能会使得结点个数出问题（和n不相同）。输出二叉树的实现思路比较简单，中序遍历访问结点即可（这里只能采用中序遍历，否则就会破坏二叉排序树的顺序）
