数据结构---
案例一
1.随机生成n个工人工时，100以内，工号分别为2021101到2021100+n
2.以工时数为关键字分别使用选择排序、冒泡排序、插入排序进行升序排序。
3.把排序后的结果输出，包括工号工时数
4.比较三种算法对相同的n值数组排序所花的时间
代码如下：
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;struct Work {int work_no; //工号int work_hours; //工时数
};Work* generate_array(int n) { //随机生成工人工号和工时，方法二调用//创建 n 个结构体数组 Work* workers = new Work[n];for (int i = 0; i < n; i++) {workers[i].work_no = 2021101 + i;//rand()函数不接受参数，要取得[a,b)的随机整数，使用(rand() % (b-a))+ a （结果值 [a，b) ） workers[i].work_hours = rand() % 100;}return workers;
}Work* generate_array(int n, int* arr) { //随机生成工人工号和手动输入工人的工时，方法一调用//创建 n 个结构体数组 Work* workers = new Work[n];for (int i = 0; i < n; i++) {workers[i].work_no = 2021101 + i;//rand()函数不接受参数，要取得[a,b)的随机整数，使用(rand() % (b-a))+ a （结果值 [a，b) ） workers[i].work_hours = arr[i];}return workers;
}void print_array(Work* workers, int n) {//打印结构体数组中的工号和工时数据 输入：数组,打印的个数 for (int i = 0; i < n; i++) {cout << "工号: " << workers[i].work_no << " 工时数: " << workers[i].work_hours << endl;}
}void print_array_work_hours(Work* workers, int n) {//打印结构体数组中的 工时数据 输入：数组,打印的个数 //cout << "生成的随机工时数为: ";//方式二时用这句cout << "生成的工时数为: ";//方式一时用这句 for (int i = 0; i < n; i++) {cout << workers[i].work_hours << " ";}cout << endl;
}void select_work(Work* workers, int n) {//选择排序算法 for (int i = 0; i < n - 1; i++) { int minIndex = i; //把i当作是最小值的初始索引//从i+1 开始遍历到最一个数 for (int j = i + 1; j < n; j++) {// 将 < 改成 > 就是降序排列 if (workers[j].work_hours < workers[minIndex].work_hours)minIndex = j;//如果 遍历的数比 minIndex 索引所在数小，则重新记录 minIndex 索引 }if (minIndex != i) {//把最小值交换到 i 所在的索引值，swap()函数是一种用于交换变量值的函数 swap(workers[i], workers[minIndex]);}cout << "选择排序-第 " << i + 1 << " 次排序: ";for (int j = 0; j < n; j++) {cout << workers[j].work_hours << " ";}cout << endl;}
}void bubble_work(Work* workers, int n) {//冒泡排序算法 for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {// 将 > 改成 < 就是降序排列 if (workers[j].work_hours > workers[j + 1].work_hours) {//果 遍历的数 比后一个数大，则交换数据位置 swap(workers[j], workers[j + 1]);}}cout << "冒泡排序-第 " << i + 1 << " 次排序: ";for (int j = 0; j < n; j++) {cout << workers[j].work_hours << " ";}cout << endl;}
}void insert_work(Work* workers, int n) {//插入排序算法for (int i = 1; i < n; i++) {Work key = workers[i]; //把第 i 个workers数据，复制给 key。 i 从1 开始 int j = i - 1; //对比数据为 j ， j 从0开始 while (j >= 0 && workers[j].work_hours > key.work_hours) {// 如果 对比数据 j > key数据 则 将 workers[j] （当前数据）插入到workers[j+1]（后一个数据）workers[j + 1] = workers[j];j = j - 1;}workers[j + 1] = key;cout << "插入排序-第 " << i << " 次排序: ";for (int j = 0; j < n; j++) {cout << workers[j].work_hours << " ";}cout << endl;}
}void deepCopyWorkers(const Work* source, Work* destination, int n) {//用于进行Work结构体的深复制for (int i = 0; i < n; ++i) {destination[i].work_no = source[i].work_no;destination[i].work_hours = source[i].work_hours;}
}int main() {srand(time(0));clock_t start, end;Work* workp;// 方法一，手动输入10个数据/*int n;n = 10;int* Arr = new int[n];cout << "请输入10个1-99的工时数据: "<<endl;cin >> Arr[0] >> Arr[1] >> Arr[2] >> Arr[3] >> Arr[4] >> Arr[5] >> Arr[6] >> Arr[7] >> Arr[8] >> Arr[9];cout << endl;*/// -----------------------方法一结束// 方法二，手动输入指定个数据，自动生成1-99的工时数据:/*int n;cout << "请输入数组的数量: ";cin >> n;*///-----------------------方法二结束//workp = generate_array(n); //随机生成工人工号和工时 方式二时调用 //workp = generate_array(n, Arr); //随机生成工人工号和手动输入工人的工时 方式一时调用 print_array_work_hours(workp, n);//打印初始的工时数据cout << endl;Work* copiedWorkers = new Work[n];//深复制结构体对象// 选择排序start = clock();deepCopyWorkers(workp, copiedWorkers, n);// 进行深复制select_work(copiedWorkers, n);end = clock();cout << "选择排序时间=: " << (end - start) / (double)CLOCKS_PER_SEC << "秒" << endl;cout << endl;// 冒泡排序start = clock();deepCopyWorkers(workp, copiedWorkers, n);// 进行深复制bubble_work(copiedWorkers, n);end = clock();cout << "冒泡排序时间=: " << (end - start) / (double)CLOCKS_PER_SEC << "秒" << endl;cout << endl;// 插入排序start = clock();deepCopyWorkers(workp, copiedWorkers, n);// 进行深复制insert_work(copiedWorkers, n);end = clock();cout << "插入排序时间=: " << (end - start) / (double)CLOCKS_PER_SEC << "秒" << endl;cout << endl;print_array(copiedWorkers, n);//打印结构体数组中的工号和工时数据 输入：数组,打印的个数 delete[] workp;delete[] copiedWorkers;return 0;
}
案例二
C++编写如下代码
1.二叉树的构建（打印输出）
2.二叉树的前序、中序和后序遍历 （打印输出）
二叉树的打印和构建。指定、手动和随机输入数值构建二叉树，并输出前序、中序和后序遍历（重点）
#include <iostream>
#include <ctime>
#include <cstdlib>using namespace std;struct TreeNode {//------------------------------ 二叉树的结构int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(0), right(0) {}
};TreeNode* insert(TreeNode* root, int val) {//---- 二叉树插入数值if (root == 0) {return new TreeNode(val);}if (val < root->val) {root->left = insert(root->left, val);} else if (val > root->val) {root->right = insert(root->right, val);}return root;
}void preorderTraversal(TreeNode* root) {//前序遍历if (root != 0) {cout << root->val << " "; // 访问根节点preorderTraversal(root->left); // 遍历左子树preorderTraversal(root->right); // 遍历右子树}
}void inorderTraversal(TreeNode* root) {//中序遍历if(root != 0) {inorderTraversal(root->left); // 遍历左子树cout << root->val << " "; // 访问根节点inorderTraversal(root->right); // 遍历右子树}
}void postorderTraversal(TreeNode* root) {//后序遍历if(root != 0) {postorderTraversal(root->left); // 遍历左子树postorderTraversal(root->right); // 遍历右子树cout << root->val << " "; // 访问根节点}
}void printBinaryTree(TreeNode* root, int level = 0) { //打印二叉树if (root == nullptr) {return;}printBinaryTree(root->right, level + 1); // 先打印右子树for (int i = 0; i < level; ++i) {std::cout << " "; // 控制每一层的缩进}std::cout << root->val << std::endl; // 输出节点的值printBinaryTree(root->left, level + 1); // 再打印左子树
}int TreeNodeCount(TreeNode* root) {//求二叉树的节点数if (root == NULL)return 0;else if (root->left == NULL && root->right == NULL)return 1;elsereturn TreeNodeCount(root->left) + TreeNodeCount(root->right)+1;}int TreeDepth(TreeNode* root) {//求二叉树的深度 if (root == NULL) return 0;else {int i = TreeDepth(root->left);int j = TreeDepth(root->right);return i > j ? i + 1 : j + 1;}
}int main() {
TreeNode* root = 0;
//方式一，手动输入节点数值/*int n,a;cout<<"请输入树的节点个数:"<<endl;cin>>n;cout<<"请输入不重复的节点值:"<<endl;for(int i = 0;i<n;i++){cin>>a;if(i == 0){root = insert(root, a);}else {insert(root, a);}}*///--------------------方法一语句结束//方式二，指定输入节点值 /*root = insert(root, 50);insert(root, 30);insert(root, 20);insert(root, 40);insert(root, 70);insert(root, 60);
insert(root, 80);*///---------方法二语句结束//方法三，节点值随机生成
srand(time(NULL)); // 初始化随机数生成器int n;cout<<"请输入树的节点个数:"<<endl;cin>>n;for(int i = 0; i < n; i++) { root = insert(root, rand() % 100); // 插入一个0到99的随机数}//-----------方法三语句结束std::cout << "打印二叉树：" << std::endl;printBinaryTree(root);//调用打印函数打印二叉树cout << "前序遍历: ";preorderTraversal(root);cout << endl;cout << "中序遍历: ";inorderTraversal(root);cout << endl;cout << "后序遍历: ";postorderTraversal(root);cout << endl;cout << "该树的节点数为：" << TreeNodeCount(root) << endl;
cout << "该树的深度为："<< TreeDepth(root)<< endl;
cout << endl << "*****注意！该程序无法插入重复值！*****" <<endl;return 0;
}
根据二叉树的两种遍历结果构建二叉树 （重点）
先序和中序以及中序和后序遍历重建二叉树
#include <iostream>
#include <vector>
using namespace std;// Definition for binary tree
struct TreeNode {char val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}TreeNode(char x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
/* 先序遍历第一个位置肯定是根节点node，
中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，p右边的肯定是node的右子树的中序数组
另一方面，先序遍历的第二个位置到p，也是node左子树的先序子数组，剩下p右边的就是node的右子树的先序子数组
把四个数组找出来，分左右递归调用即可*/class Solution {//前序和中序重建二叉树
public:TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {return buildTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);}TreeNode* buildTree(vector<char>& preorder, int l1, int r1, vector<char>& inorder, int l2, int r2) {if (l1>r1 || l2>r2) return nullptr;char root = preorder[l1];int mid = l2;while (inorder[mid]!=root) mid++;TreeNode* s = new TreeNode(root);int x = mid-l2; // 这里是左半部分的长度s->left = buildTree(preorder, l1+1, l1+x, inorder, l2, mid-1);s->right = buildTree(preorder, l1+x+1, r1, inorder, mid+1, r2);return s;}
};class Solution2 {//中序和后序重建二叉树
public:TreeNode* buildTree(vector<char>& inorder, vector<char>& postorder) {return buildTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);}TreeNode* buildTree(vector<char>& inorder, vector<char>& postorder, int l1, int r1, int l2, int r2) {if (l1>r1 || l2>r2) return nullptr;char root = postorder[r2];int mid = l1;while (inorder[mid]!=root) mid++;TreeNode* s = new TreeNode(root);int x = mid-l1;s->left = buildTree(inorder, postorder, l1, mid-1, l2, l2+x-1);s->right = buildTree(inorder, postorder, mid+1, r1, l2+x,r2-1);return s;}
};void printBinaryTree(TreeNode* root, int level = 0) { //打印二叉树if (root == nullptr) {return;}printBinaryTree(root->right, level + 1); // 先打印右子树for (int i = 0; i < level; ++i) {std::cout << " "; // 控制每一层的缩进}std::cout << root->val << std::endl; // 输出节点的值printBinaryTree(root->left, level + 1); // 再打印左子树
}//test=====后序递归遍历二叉树
void Posorder(TreeNode* &T)
{if (T)//当结点不为空的时候执行{//左右中Posorder(T->left);Posorder(T->right);cout << T->val;}else{//cout << " ";T = NULL;}
}//test=====前序递归遍历二叉树
void preorder(TreeNode* &T)
{if (T)//当结点不为空的时候执行{//中左右cout << T->val;Posorder(T->left);Posorder(T->right);}else{//cout << " ";T = NULL;}
}int main()
{//方法一手动输入：两次输入顺序不同，不能有不同值 /*int n;cout<<"请输入遍历向量长度："<<endl;cin>>n;char a[n],b[n],c; cout<<"请输入第一个遍历的值(字母或数字)："<<endl ;for(int i = 0;i<n;i++){cin>>a[i];}cout<<"请输入第二个遍历的值(字母或数字)："<<endl ;for(int i = 0;i<n;i++){cin>>b[i];}vector<char>pre(a,a+n);vector<char>vin(b,b+n);*///--------------方法一结束 //方法二固定值输入 vector<char>pre{'1','2','4','7','3','5','6','8'};vector<char>vin{'4','7','2','1','5','3','8','6'};//-----------方法二结束 cout<<"第一个遍历向量的值:" <<endl;for(int i = 0;i < pre.size();i++){cout<<pre[i]<<" ";} cout<<endl;cout<<"第二个遍历向量的值:" <<endl;for(int i = 0;i < pre.size();i++){cout<<vin[i]<<" ";} cout<<endl;Solution T;TreeNode* node=T.buildTree(pre, vin);//测试---输出后续遍历cout << "后序遍历为:" << endl;Posorder(node);cout << endl;std::cout << "打印二叉树：" << std::endl;printBinaryTree(node);//调用打印函数打印二叉树cout << endl;Solution2 T2;TreeNode* node2=T2.buildTree(pre, vin);cout << "前序遍历为: "<< endl;preorder(node2);cout << endl;std::cout << "打印二叉树：" << std::endl;printBinaryTree(node2);//调用打印函数打印二叉树cout << endl;system("pause");
}
顺序查找和二分法查找的执行和比较次数
#include
using namespace std;
//顺序查找与二分查找
//顺序查找就是循环
//二分查找
//使用前提：数据必须排序
int ordersearch(int* a, int x, int n, int count[])//顺序查找
{int k = -1;for (int i=0; i < n; i++){count[0]++;if (a[i] == x){k = i;cout << "找到了元素位置：" << k+1 << endl;return k;}}return k;
}int binarysearch(int* a, int x, int n, int count[])//二分查找
{int low;int high;low = 0;high = n - 1;while (low <= high){int mid = (low + high) / 2;count[0]++; //记录查找次数if (a[mid] == x){cout << "找到了元素位置：" << mid+1 << endl;return mid;}else if (a[mid] < x){low = mid + 1;}else if (a[mid] > x){high = mid - 1;}}return -1;
}void selectionSort(int arr[], int n) {for (int i = 0; i < n; i++) {// 寻找[i, n)区间里的最小值int minIndex = i;for (int j = i + 1; j < n; j++)if (arr[j] < arr[minIndex])minIndex = j;swap(arr[i], arr[minIndex]);}}int main() {//方法一，这里是手动输入数组值的代码 /*cout<<"输入数组大小"<<endl;int num;cin>>num;int a[num],b[num];int count[1] = { 0 };cout<<"输入数组的值"<<endl;int c;for(int i = 0;i<num;i++){cin>>c;b[i] = a[i] = c;} *///------------方法一手动输入数组值代码结束 int a[] = { 11,33,44,56,78,89,99,101,123,235,678 };//方法二固定数组值时的语句 int num = sizeof(a) / sizeof(int);//-----------------------固定数组值时的语句int count[1] = { 0 }; //------------------------------方法二固定数组值时的语句结束/*while(1){//------------------这里是执行查找时的语句 cout<<"请选择要执行的操作（1、顺序查找 2、二分查找 0、退出）："<<endl;int j;cin>>j;if(j==1) {cout<<"输入查找的值"<<endl;int z,k;cin>>k;z = ordersearch(a,k, num, count);if(z == -1)cout<<"未找到要查询的值"<<endl;}else if(j==2){cout<<"二分查找前排序，排序后的数组为："<<endl;selectionSort(a, num);for(int i = 0;i < num;i++){cout<<a[i]<<" ";}cout<<"输入查找的值"<<endl;int x,y;cin>>y;x = binarysearch(a,y, num, count);if(x == -1)cout<<"未找到要查询的值"<<endl;}else if(j==0){break;}else cout<<"请正确的查找方式"<<endl; } *///---------------执行查找代码结束 //以下是两种查找方法性能比较的代码 cout<<"比较前排序，排序后的数组为："<<endl;selectionSort(a, num);for(int i = 0;i < num;i++){cout<<a[i]<<" ";}cout<<endl<<endl;ordersearch(a, a[num-1], num, count);cout << "顺序检索在最差情况下(这里用的是检索的是最后一个）的比较次数为：" << count[0] << endl;count[0] = 0;binarysearch(a, a[num-1], num,count);cout << "二分检索在最差情况下(这里用的是检索的是最后一个）的比较次数为：" << count[0] << endl;count[0] = 0;ordersearch(a, a[(int)(num-1)/2], num, count);cout << "顺序检索在一般情况下(这里用的是检索的是中间一个）的比较次数为：" << count[0] << endl;count[0] = 0;binarysearch(a, a[0], num, count);cout << "二分检索在一般情况下(这里用的是检索的是第一个）的比较次数为：" << count[0] << endl;count[0] = 0;ordersearch(a, a[0], num, count);cout << "顺序检索在最佳情况下(这里用的是检索的是第一个）的比较次数为：" << count[0] << endl;count[0] = 0;binarysearch(a,a[(int)(num-1)/2], num, count);cout << "二分检索在最佳情况下(这里用的是检索的是中间一个）的比较次数为：" << count[0] << endl;//-------------两种查找方法性能比较代码结束 return 0;
}
图的构建
#include <iostream>
using namespace std;const int MaxSize = 10; //图中最多顶点个数
int visited[MaxSize]={0};template <class DataType>
class MGraph
{
public:MGraph(DataType a[ ], int n, int e); //构造函数，建立具有n个顶点e条边的图~MGraph( ) { } //析构函数为空void DFSTraverse(int v); //深度优先遍历图void BFSTraverse(int v); //广度优先遍历图
private:DataType vertex[MaxSize]; //存放图中顶点的数组int arc[MaxSize][MaxSize]; //存放图中边的数组int vertexNum, arcNum; //图的顶点数和边数
};补充1//
template <class DataType>
MGraph<DataType>::MGraph(DataType a[], int n, int e){for(int i=0;i<vertexNum;i++){ //重置访问痕迹 visited[i]=0;}int i,j,k;vertexNum = n;arcNum = e;for(i = 0;i < vertexNum; i++){vertex[i] = a[i];}for( j = 0; j < vertexNum; j++){for(k = 0; k < vertexNum;k++){arc[j][k] = 0;}}for(k = 0;k < arcNum; k++){cout<<"请输入边的两个顶点的编号：";cin>>i>>j;arc[i][j] = 1;arc[j][i] = 1;}
// for( j = 0; j < vertexNum; j++){
//
// for(k = 0; k < vertexNum;k++){
// cout<<arc[j][k];
// }
// cout<<endl;
// }
} //深度优先
template <class DataType>
void MGraph<DataType>::DFSTraverse(int v){cout<<vertex[v];visited[v] = 1;for(int i=0;i<vertexNum;i++){if(arc[v][i]==1&&visited[i]==0){DFSTraverse(i);}}
}//广度优先
template <class DataType>
void MGraph<DataType>::BFSTraverse(int v){for(int i=0;i<vertexNum;i++){ //重置访问痕迹 visited[i]=0;} int w, j, Q[MaxSize]; //Q作为队列存储访问的点以及其连接的点 int front = -1, rear = -1; //初始化头指针和尾指针 cout<<vertex[v]; //输出输入v的对应字符 visited[v] = 1; //把V设定为访问过 Q[++rear] = v; //将访问过的v入队列 while(front != rear){ //判定栈是否为空，如果为空就结束 w = Q[++front]; //w暂存Q栈读取出来的数 for(j = 0; j < vertexNum; j++){ //循环访问所有的数字，看是否与w连接但没有被访问过 if(arc[w][j]==1&&visited[j]==0){ //如果与w连接但是没有被访问过的话 cout<<vertex[j]; //就输出这个数字对应的字符 visited[j] = 1; //并且将这个数字设置为访问过 Q[++rear] = j; //再将这个字符入栈Q }} //循环完毕当前的w的字符，所有w对应连接的字符都被访问并且入队列完毕 } //继续循环，直到所有的队列里面的数字被访问完毕
}
//int main( )
{char ch[]={'A','B','C','D','E','F'};MGraph<char> MG(ch, 6, 6);
补充2//cout<<"深度优先遍历序列是："; MG.DFSTraverse(0); cout<<endl;cout<<"广度优先遍历序列是："; MG.BFSTraverse(0);
}