C++基础代码--20余种数据结构和算法的实现

简介: C++基础代码--20余种数据结构和算法的实现

C++基础代码--20余种数据结构和算法的实现

  过年了,闲来无事,翻阅起以前写的代码,无意间找到了大学时写的一套C++工具集,主要是关于数据结构和算法、以及语言层面的工具类。过去好几年了,现在几乎已经回忆不起当年写代码时的情况,不过,通过文件头部注释里的日期,还是依稀想起了那些日子发生的一些事情,不禁感慨了一番。感概之余,随便翻阅了一下,发现当年的编程手法和现在相比,略显稚嫩,风格也相差的比较大了,明显受到当时读的一些经典C++书籍的影响。不过好在代码质量都算可以,都属于基础的语言层面以及数据结构的代码,操作指针比较小心,每个类也都有测试的样例,感觉对初学者应该会有用,于是拿到这里放出来,希望能对准备学习和正在学习C++语言编程的朋友有所裨益。

做了个表,看一下这个工具集里都有哪些C++类

   

  基本上可以分为两大类,一种是关于数据结构和算法的(例如:RBtree,stack),另一种是关于C++语言本身层面的(例如:reference_count,Uncopyable)。这些类,可以在如今C++标准库或者其它C++库(如:boost)中找到类似的实现,实现它们的目的不是想自己造轮子,而是通过实现,来深入的理解到一些更本质的东西。很多时候,人们往往“知其然,不知其所以然”,当然,世界这么大,什么事情都想要“知其所以然”是不可能、也是不应该的,但是对于初学者而言,了解C++中常用的编程手法的本质,“知其所以然”,还是很必要的。

  如果想在自己的项目中使用这些代码,有的地方还是需要注意和考虑一下的,比如Auto_ptr,它的原理仿照std::auto_ptr,当然,现在已经不推荐使用了,更应该使用std::unique_ptr或std::shared_ptr,而Uncopyable也可以通过更为方便的宏定义来实现,只需要在类定义private域中加入该宏即可。

1 #define DISABLE_COPY_AND_ASSIGN(type_name) \
2     type_name(const type_name&); \
3     type_name& operator=(const type_name&)


  这里我把其中的两个基础算法——sorting中的“插入排序”和“快速排序”贴出来,估计一些要参加笔试和面试的朋友可能会感兴趣。

 1 //-------------insertion sort-------------------------
 2 template<typename T>
 3 void insertion_sort(T a[], int n)
 4 {
 5     T tm;
 6     for (int i=0; i!=n; ++i) {
 7         tm = a[i];
 8         int k=i;
 9         for (; k>0; --k) {
10             if (tm >= a[k-1])
11                 break;
12             a[k] = a[k-1];
13         }
14         a[k] = tm;
15     }
16 }
17 //---------------------------------------------------
 1 //------------------quick sort----------------------
 2 template<typename T>
 3 T median(T a[], int left, int right)
 4 {
 5     int center = (left + right) / 2;
 6     T tm;
 7     if (a[left] > a[center]) {
 8         tm = a[left];
 9         a[left] = a[center];
10         a[center] = tm;
11      }
12     if (a[left] > a[right]) {
13         tm = a[left];
14         a[left] = a[right];
15         a[right] = tm;
16     }
17     if (a[center] > a[right]) {
18         tm = a[center];
19         a[center] = a[right];
20         a[right] = tm;
21     }
22 
23     tm = a[center];
24     a[center] = a[right-1];
25     a[right-1] = tm;
26 
27     return a[right-1];
28 }
29 
30 template<typename T>
31 void q_sort(T a[], int left, int right)
32 {
33     // 如果剩余未排序的数组长度太小,使用插入排序算法进行剩余数组的排序
34     if (left+4 <= right) {
35         T pivot = median(a,left,right);
36         int i = left;
37         int j = right - 1;
38         while (true) {
39             while (a[++i] < a[pivot]);
40             while (a[--j] > a[pivot]);
41             if (i < j) {
42                 T tm = a[i];
43                 a[i] = a[j];
44                 a[j] = tm;
45             }
46             else
47                 break;
48         }//while
49         T tm = a[i];
50         a[i] = a[right-1];
51         a[right-1] = tm;
52 
53         q_sort(a,left,i-1);
54         q_sort(a,i+1,right);
55     }
56     else
57         insertion_sort(a+left,right-left+1);
58 }
59 
60 template<typename T>
61 void quicksort(T a[], int n)
62 {
63     q_sort(a,0,n-1);
64 }
65 //--------------------------------------------------


下载地址:https://files.cnblogs.com/haibindev/data_structures_and_algorithms.7z

目录
相关文章
|
2月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
112 0
|
10天前
|
机器学习/深度学习 算法 Java
[算法与数据结构] 谈谈线性查找法~
该文章详细介绍了线性查找法的基本概念与实现方法,通过Java代码示例解释了如何在一个数组中查找特定元素,并分析了该算法的时间复杂度。
|
9天前
|
存储 算法 安全
超级好用的C++实用库之sha256算法
超级好用的C++实用库之sha256算法
17 1
|
29天前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
117 6
|
29天前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
|
29天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表,常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈,顺序栈使用数组存储,链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛,如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成,链栈则基于单链表的头插法实现。
157 3
|
1月前
|
机器学习/深度学习 存储 算法
经典算法代码
这段代码展示了多个经典算法,包括:穷举法解决“百钱买百鸡”问题;递推法计算“猴子吃桃”问题;迭代法求解斐波那契数列及折纸高度超越珠峰的问题。同时,还提供了希尔排序算法实现及披萨票务订购系统和汉诺塔问题的链表存储解决方案。每部分通过具体案例解释了算法的应用场景与实现方法。
24 3
|
29天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
9天前
|
存储 算法 安全
超级好用的C++实用库之国密sm4算法
超级好用的C++实用库之国密sm4算法
22 0
|
9天前
|
算法 安全 Serverless
超级好用的C++实用库之国密sm3算法
超级好用的C++实用库之国密sm3算法
20 0