本人开辟一个专栏,把严蔚敏 数据结构 这本书上的算法和数据结构用C++实现,网上和她书本光盘也带了C的实现方法,但是其实对于初学者来说真不是那么好自己运行看结构,和自己去修改“玩”的。
本人觉得写程序的能力应该是“玩”出来的,不然会觉得学计算机编程很枯燥的。
所以这里都是给出了完整的C++数据结构或算法程序。
而在C++里面和C其实没有根本的区别,但是我们可以很好的利用C++的一些容器,就可以不用自己求定义一些基本的数据结构了,比如与线性表可以直接用vector。
本专栏也会特意用到了C++11的新特性,用VS2012编译环境。其实这些特性非常好的,建议赶紧学起来。我也尽量解析好这些新特性和一些C++基础吧。
先讲一下本文主要要用到的稍微高级一点而重要的一些C++基础:
1. C++模板:
模板简单的来说就是可以让你定义一个通用的类型,模板的关键字为typename和class,这两个关键字用在模板中基本上是一样的作用。class是旧的关键字,现在都建议用typename,这样是为了避免和类关键字class混淆。
如
template<typename T>
void mergeList(vector<T> &t, vector<T> &t1, vector<T> &t2);
这样你就可以定义你的函数的时候把T当做比如int,double,vector,甚至是你自己定义的类来使用了。模板很多书都把它放到书本的后面介绍了,好像很高级似的,其实用多几次就一点都不神秘。
2.Function Objects 函数对象
(下面内容翻译引用 The C++ Programming Language 这本书的部分内容,部分自己写)
又叫functor;其实就是一个类,不过这种类可以当做函数一样来调用。 也可以说表面上是一个类,不过用法确实像函数一样来使用。
如:
template<typename T>
class Less_than {
const T val; // value to compare against
public:
Less_than(const T& v) :val(v) { }
bool operator()(const T& x) const { return x<val; } // call operator
};
函数调用operator()执行函数调用,调用操作符();
初始化:
Less_than<int> lti {42}; // lti(i) will compare i to 42 using < (i<42)
Less_than<string> lts {"Backus"}; // lts(s) will compare s to "Backus" using < (s<"Backus")
然后我们就可以调用这样的对象,就好像我们调用函数一样:
void fct(int n, const string & s)
{
bool b1 = lti(n); // true if n<42
bool b2 = lts(s); // true if s<"Backus"
// ...
}
如果用好STL就知道其实这样的函数对象是很常用的。
而且大家不要以为这样定义一个类,执行效率会下降,其实恰恰相反,这样的函数对象可以内置(inline),函数对象调用实际上比直接调用函数更加快。而且函数对象可以自带数据,把数据和操作结合起来(正是类的优点),我们不用再去定义更多的变量,这也是它的美丽之处。函数对象自带数据和高效性使得函数对象在作为算法参数的时候特别有用。
下面是合并两序列的算法程序:
/*****
已知两线性表中的数据元素按值非递减排列,归并两线性表到新的线性表,是的数据元素也按值非递减排列
*****/
#include<iostream>
#include<vector>
using namespace std;
template<typename T>
void mergeList(vector<T> &t, vector<T> &t1, vector<T> &t2)
{
auto iter1=t1.begin(), iter2=t2.begin();
while(iter1!=t1.end() && iter2!=t2.end())
{
if(*iter1<=*iter2)
{
t.push_back(*iter1);
++iter1;
}
else
{
t.push_back(*iter2);
++iter2;
}
}
while(iter1!=t1.end())
{
t.push_back(*iter1);
iter1++;
}
while(iter2!=t2.end())
{
t.push_back(*iter2);
iter2++;
}
}
template<class C, class Oper>
void for_all(C &c, Oper op)
{
for(auto x:c) //C++新特性,记住其实就是一种方便循环遍历数据的写法
op(x);
}/*写一个通用的函数,增加其可重用性,配合下面的Print函数就可以打印各种不同的数据到屏幕,非常方便。*/
template<typename T>
class Print
{
public:
Print(){}
void operator()(const T& x) const{cout<<x<<" ";}
};//这就是函数对象,这里并没有带数据,只是一个简单的输出操作。
int main()
{
int a[4]={1,2,5,8};
vector<int> vecI1(a,a+4);
//vecI1={1,2,5,8};这个写法是C++11的新标准,可惜的是VS2012还不支持,只能用就的初始化了
int b[7]={2,4,5,7,9,10,30};
vector<int> vecI2(b,b+7);
vector<int> vecI;
mergeList(vecI, vecI1, vecI2);//不局限是vector<int>类型
for_all(vecI,Print<int>());
cout<<endl;
return 0;
}
总结:
主要的算法函数就是mergeList,本算法并不难,拿本程序,左改改,右改改,就很快可以掌握这个算法了,也可以同时学学C++一举两得。也可以换一换排序的数据类型,其实本程序还支持一般的数组排序。
分享到:
相关推荐
数据结构与算法 c++实现 两个单链表合并为一个单链表,两个表的元素交错排列,新表用原表结点的内存空间 按元素序列的奇偶分割单链表 适合大二初学数据结构与算法 程序有详细备注 顺序表 单链表
本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找...
合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法。它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个...
他的主要研究方向是数据结构,算法和教育学。 目录 : 第1章 引论 1.1 本书讨论的内容 1.2 数学知识复习 1.2.1 指数 1.2.2 对数 1.2.3 级数 1.2.4 模运算 1.2.5 证明方法 ...
用于学习/提炼/重新确认/纠正算法、数据结构、基础计算机科学知识。 解决问题 反复练习,因为上帝没有给我们捷径。 细绳 解码字符串 - 短字距 - 索引处的解码字符串 - 确定两个字符串是否接近 - 简化路径 - 反向字符...
数据结构算法演示(Windows版) 使 用 手 册 一、 功能简介 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法...
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
1 5 抽象类型和基本数据结构 11 1 5 1 栈 11 1 5 2 字典 12 1 5 3 队列 12 1 5 4 优先级队列和最小堆 13 1 5 5 并查集 16 1 6 技术 18 1 6 1 比较 18 1 6 2 排序 18 1 6 3 扫描 19 1 6 4 贪婪算法 20 1 6 5 动态规划...
数据结构,算法和有用设计的C ++实现。 建立状态 Linux 视窗 覆盖范围 大纲 数据结构 名称 资源 基准化 注意 定义 是 链接的数据结构,由一组顺序链接的记录组成。 它还支持合并排序。 是 采用完整二进制树形式的...
以C++语言实现了一些常用算法。为了方便调试,每个cpp文件都单独可以运行。 分治和递归 : 最大子序列和 二分法查找 汉诺塔 动态规划 最大连续乘积子数组、最长递增子序列数组(不一定连续)、最大连续子数组和 从0...
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
一些众所周知的数据结构的实现 阵列:Python的API 与大O的复杂性 堆栈: 实现, 复杂度 队列: 实现, 复杂 链接列表: 实现, 复杂度 二叉树: 实现, 复杂度 二进制搜索树: 实现, 复杂度 没有节点类的二进制搜索...
编写和调试一个存储管理的模拟程序,加深对动态分区存储管理方式及实现过程的理解,了解动态分区分配方式中使用数据结构和分配算法。 二、实验要求 1、实现内存回收和分配过程。 2、实验后按规定要求写出实验报告。 ...
1-1-9 结构数据类型的变化............................................ 13 1-1-10 数组和指针技术的不同......................................... 14 1-2 C++存储技术............................................
450数据结构和算法问题 此存储库包含该Love Babbar在SDE表中给出的DS Algo练习问题的解决方案 使用的语言-C ++ 进展- 类别/标签 问题 解 数组 最小和最大数组 数组 反转阵列 数组 找到数组的“ Kth”最大和最小元素...
课程名称: 数据结构 学分: 3 大纲编号 062204 试卷编号: 考试方式: 闭卷 满分分值: 100 考试时间: 120 分钟 组卷日期: 2006年5月18日 组卷教师(签字) 张宏 审定人(签字) 王树梅 学生班级: 计算机学院 ...
常用代码模板2——数据结构 链表与邻接表:树与图的存储 栈与队列:单调队列、单调栈 kmp Trie 并查集 堆 Hash表 C++ STL使用技巧 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论 DFS与BFS 树与图的遍历...
###数据结构和算法 大批 加一: # 合并排序数组:# 排序 搜索 二分查找:代码、#、#、# 选择 数组中第 K 个最大元素:# 递归 排列:#、# 哈希 二和:# 同构字符串:# 注意:构建堆,O(n); 提取根并重建 O(logn) 从...
基本知识浏览算法: 出生问题组合二进制序列除数向后递归接近技术贪心算法排序算法常规排序算法QuickSort快速排序算法分配计数算法堆排序基数排序,合并排序动态计划数据结构: 堆队列排队2个头(双端/dɛk/) 堆...
caffe_ocr是一个对现有主流ocr算法研究实验性的项目,目前实现了CNN + BLSTM + CTC的识别架构,并在数据准备,网络设计,调参等方面进行了很多的实验。代码包含了对lstm ,warp-ctc,multi-label等的适应和修改,还...