《数据结构与算法》实验和课程Github资源
《数据结构与算法》实验：线性结构及其应用——算术表达式求值
《数据结构与算法》实验：树型结构的建立与遍历
《数据结构与算法》实验：图结构的建立与搜索
《数据结构与算法》实验：查找结构的实验比较——二叉查找树BST & 二分（折半）查找
《数据结构与算法》实验：排序算法实验比较——选择排序 & 堆排序
注意：正文文字为宋体小4号，图中文字为宋体5号。行距为多倍行距1.25。
源程序与此报告打包提交，压缩包采用学号命名。
// lab5.cpp#include <algorithm>#include <cstdio>#include <cstdlib>#include <iostream>#include <windows.h>using namespace std;#define Swap(x, y) (a[x] = a[x] ^ a[y], a[y] = a[x] ^ a[y], a[x] = a[x] ^ a[y])#define N 1000000int a[N + 5];void HeapAdjust(int x, int n) //调整堆{if (x * 2 > n) return;int maxi = x * 2 + 1 > n ? x * 2 : (a[x * 2] < a[x * 2 + 1] ? x * 2 : x * 2 + 1);if (a[maxi] < a[x]) Swap(x, maxi), HeapAdjust(maxi, n);}void HeapSort(int n){for (int i = n; i >= 1; i--) HeapAdjust(i, n); //建立最小堆for (int i = n; i > 1; i--){Swap(1, i); //取出堆根节点HeapAdjust(1, i - 1); //调整堆，此时大小减1}}void Print(int n){for (int i = 1; i < n; i++) printf("%d ", a[i]);printf("%d\n\n", a[n]);}void SelectSort(int n){int mini;for (int i = 1; i < n; i++){mini = i;for (int j = i + 1; j <= n; j++)if (a[j] < a[mini]) mini = j;if (i != mini) Swap(i, mini);}}#define M 10int main(){freopen("init.txt", "r", stdin);//freopen("output.txt", "w", stdout);int n;DWORD sta, end;scanf("%d", &n);for (int j = 1; j <= 5; j++){for (int i = 1; i <= n; i++) scanf("%d", &a[i]);sta = GetTickCount();for (int i = 1; i <= M; i++) HeapSort(n);end = GetTickCount();printf("Heap%d %.6lfs\n", j, (double)(end - sta) / 1000 / M);}for (int j = 1; j <= 5; j++){for (int i = 1; i <= n; i++) scanf("%d", &a[i]);sta = GetTickCount();SelectSort(n);end = GetTickCount();printf("Select%d %.6lfs\n", j, (double)(end - sta) / 1000 / M);}fclose(stdin);fclose(stdout);return 0;}
// create_data.cpp#include <cstdio>#include <cstdlib>#define N 100000#define M (1 << 30)int main(){freopen("init.txt", "w", stdout);printf("%d\n", N);for (int j = 1; j <= 5; j++, printf("\n"))for (int i = 1; i <= N; i++){int x = rand() % M + 1, y = rand() % 15;x = x << y;printf("%d ", x);}fclose(stdout);return 0;}
# d.py 画图import matplotlib.pyplot as pltimport numpy as npimport seaborn as snsheap_n = [10000, 50000, 100000, 200000, 300000]heap_t = [0.001575, 0.008575, 0.016, 0.03555, 0.051975]slct_n = [10000, 50000, 100000, 200000, 300000]slct_t = [0.01095, 0.257425, 1.054325, 4.168375, 9.321475]plt.rcParams["figure.figsize"] = (10.0, 6.0)fig = plt.figure()style = ["darkgrid", "dark", "white", "whitegrid", "ticks"]sns.set_style(style[2])ax1 = fig.add_subplot(111)ax1.set_ylim([0, 1])ax1.plot(heap_n, heap_t, "c", ms=10, lw=1, marker="o") # 设置线粗细，节点样式ax1.set_ylabel("Heap_time", fontsize="20")ax1.tick_params(labelsize=10)for x, y in zip(heap_n, heap_t): # # 添加数据标签plt.text(x, y + 0.01, str(y) + "s", ha="center", va="bottom", fontsize=8, rotation=0)# plt.plot(heap_t, label="heap")# plt.legend(bbox_to_anchor=(0.15, 1.0))ax2 = ax1.twinx()ax2.set_ylim([0, 10])ax2.plot(slct_n, slct_t, "darkviolet", ms=7, lw=1, marker="o") # 设置线粗细，节点样式ax2.set_ylabel("Select_time", fontsize="20")ax2.tick_params(labelsize=10)for x, y in zip(slct_n, slct_t): # # 添加数据标签plt.text(x, y + 0.1, str(y) + "s", ha="center", va="bottom", fontsize=8, rotation=0)# plt.plot(slct_t, label="slct")"""plt.legend(bbox_to_anchor=(0.0, 1.02, 1.0, 0.102),loc=0,ncol=3,mode="expand",borderaxespad=0.0,)"""plt.savefig(r"D:\GZN\HIT\个人文件\秋数据结构与算法\Lab5\1.png", dpi=1000, bbox_inches="tight")plt.grid()plt.show()
