泛型算法-1

yeshan333

CPP

文章首发于：2019年1月3日

CPP

泛型算法-1

泛型算法实现了一些经典算法的公共接口，如排序和搜索；称它们是“泛型的”，是因为它们可以用于不同类型的元素的和多种容器类型（不仅包括标准库类型，还包括内置的数组类型），以及其它类型的序列。

** 大多数算法都定义在头文件algorithm中 **

算法永远不会执行容器的操作

阅读全文

标准库容器

yeshan333

CPP

文章首发于：2018年12月1日

CPP

阅读全文

再探函数

yeshan333

CPP

文章首发于：2018年11月22日

CPP

main:处理命令行

//main函数的两种定义形式
int main(int argc,char **argv[])
int main(int argc,char *argv[])

argc:指的是命令行中输入参数的个数
argv:一个数组，它存储了所有的命令行参数

阅读全文

IO类型

yeshan333

CPP

文章首发于：2018年11月22日

CPP

IO库

** IO库设施: **

istream类型:提供输入操作
ostream类型:提供输出操作
cin:一个istream对象，从标准输入读取数据
cout:一个ostream对象，从标准输出写入数据
cerr:一个ostream对象，通常用于输出程序错误信息，写入到标准错误
>>运算符:用来从一个istream对象读取输入数据
<<运算符:用来向一个ostream对象写入数据
getline函数:从一个给定的istream读取一行数据，存入一个给定的string对象中

阅读全文

二分查找

yeshan333

Algorithm

文章首发于：2018年11月19日

CPP

Algorithm

Python

二分查找算法

二分查找的基本思想: 将 n 个元素分成大致相等的两部分，取 a[n/2] 与 x(查找目标值) 做比较，如果x == a[n/2] ,则找到 x,算法中止；否则，如果x < a[n/2],则只要在数组 a 的左半部分继续搜索 x,如果x > a[n/2], 则只要在数组 a 的右半部搜索 x。

使用二分查找算法的前提：待查找序列是有序的

时间复杂度分析

由算法核心思想可知：每次对比都将下一步的比对范围缩小一半。每次比对后剩余数据项如下表:

剩余数据项表

最好情况

即要找的元素正好在初始查找序列的中间一次比较出结果，时间复杂度为 $ O(1) $。

最坏情况

即比对范围只剩下 1 个数据项的情况这个数据项即为正要找的元素。这时，可求解如下方程组($ i $ 为比较次数)：

$$ \frac{n}{2^i}=1 $$

时间复杂度为 $ O(log(n)) $

平均时间复杂度

进行平均时间复杂度分析时需要讨论：随着元素个数n的增多，需要几步算法才能终止？查找成功有多少种情况？查找失败有多少种情况？

设 $ n=2^k-1 $, $ k $ 为比较次数。易知，对于 $$ t=1,2,…, \lfloor log(n) \rfloor + 1 $$, 会有 $ 2^{t-1} $ 个元素在 $ t $ 步之后使算法成功终止。总共有 $ (2n+1) $ 种情况，$ n $ 种情况为成功结束，$ (n+1) $ 种情况为失败终止。

由此可得二分搜索的平均比较次数为 $ (k = \lfloor log(n) \rfloor + 1) $：
$$ A(n)= \frac{1}{2n+1}(\sum_{i=1}^{k}i2^{i-1} + k(n+1)) $$
根据初等数学等差乘等比数列求和的错位相减法/裂项相消法。易知,
$$ \sum_{i=1}^{k}i2^{i-1} = 2^k(k-1)+1 $$

使用裂项相消法
由 $ \sum_{i=1}^{k}i2^{i-1} $，设 $ a_i=i2^{i-1},(i=1,…,k) $。注意到，$ a_i=(k-1)2^k-(k-2)2^{k-1} $。
$$ \sum_{i=1}^{k}i2^{i-1}=0\times2^1+1+1\times2^2-0\times2^1+2\times2^3-1\times2^2+…+(k-1)2^k-(k-2)2^{k-1}=2^k(k-1)+1 $$

$$ A(n)= \frac{1}{2n+1}(\sum_{i=1}^{k}i2^{i-1} + k(n+1)) $$
$$ \sum_{i=1}^{k}i2^{i-1} = 2^k(k-1)+1 $$
综上可得，$$ A(n) = \frac{1}{2n+1}((k-1)2^{k}+1+k2^k) $$

当 $ n $ 非常大时，可得
$$ A(n) \approx \frac{1}{2^{k+1}}((k-1)2^{k}+k2^k)=\frac{(k-1)}{2}+\frac{k}{2}=k-\frac{1}{2} $$
所以 $ A(n)<k=O(log(n)) $ ，平均时间复杂度为$ O(log(n)) $。

代码实现

# -*- coding: utf-8 -*-
# binary_search

def binary_search(list_1, item):

    low = 0
    high = len(list_1)-1

    while low <= high:
        '''使用 // 整除运算符可以不用int进行类型转换'''
        #每次都检查中间的元素
        mid = (low + high)/2
        guess = list_1[int(mid)]

        if guess == item:
            return int(mid)#返回所在位置的索引
        if guess < item:   #猜的数字小了，修改low
            low = mid+1
        if guess > item:   #猜的数字大了，修改high
            high = mid-1
    return None

def main():

    list_2 = [1,2,3,4,5,6,7,8,9]

    print(binary_search(list_2, 8))
    print(binary_search(list_2, 10))

main()

运行效果

#include<iostream>
#include<typeinfo>
using namespace std;

int binary_search(int a[9],int n,int x)//n为元素个数
{
    int mid;
    int high,low=0;
	int guess;

    high = n-1;//数组下标从0开始

	while(low <= high)
    {
        mid = (high+low)/2;
        guess = a[mid];
        if(guess == x)
            return mid;
        if(guess > x)
            high = mid-1;
		if(guess < x)
		    low = mid+1;
    }
    return -1;
}

int main()
{
	int temp;
    int a[9] = {1,2,3,4,5,6,7,8,9};

	cout<<sizeof(a)/sizeof(int)<<endl;
	cout<<typeid(sizeof(a)/sizeof(int)).name()<<endl;
    temp = binary_search(a,sizeof(a)/sizeof(int),5);
	cout<<temp<<endl;

	return 0;
}

运行效果

附：C++ 使用头文件typeinfo下的typeid(parameter).name()可获取参数获取类型名

C++面向对象-8

yeshan333

CPP

文章首发于：2018年11月15日

CPP

使用struct关键字定义类

* 使用class和struct定义类的唯一区别就是默认的访问权限 *]

使用struct关键字，定义在第一个访问说明符之前的成员是public
使用class关键字，定义在第一个访问说明符之前的成员是private

定义在类内的成员函数是自动inline的

#include<cstring>
#include<iostream>
using namespace std;

struct Sales_data{
	/*
	- isbn成员函数用于返回对象的ISBN编号
	- combine成员函数，用于将一个Sales_data对象加到另一个对象上
	- avg_price成员函数，用于返回售出书籍的平均价格
	*/
	string isbn() const{return bookNo;}//这是一个常量成员函数，不能改变调用它的对象的内容
	Sales_data& combine(const Sales_data&);
	double avg_price() const;

	string bookNo;              //ISBN
	unsigned units_sold = 0;    //销售总数
	double  revenue = 0.0;      //收益
};

double Sales_data::avg_price() const
{
	if(units_sold)
	    return revenue/units_sold;
	else
	   return 0;
}

Sales_data& Sales_data::combine(const Sales_data &rhs)
{
	units_sold += rhs.units_sold;
	revenue += rhs.revenue;
	return *this;//返回调用该函数的对象
}

/*
* Salse_data的非成员接口函数：
- add函数，执行两个Sales_data对象的加法
- read函数，将数据从istream读入到Sales_data对象中
- print函数，将Sales_data对象的值输出到ostream
*/
Sales_data add(const Sales_data& ,const Sales_data&);
ostream &print(ostream& , const Sales_data&);
istream &read(istream& , const Sales_data&);

//输入的交易信息包括ISBN、售出总数、售出价格
istream &read(istream &is, Sales_data &item)
{
    double price = 0.0;
	is>>item.bookNo>>item.units_sold>>price;
}
ostream &print(ostream &os, const Sales_data &item)
{
    os<<item.isbn()<<" "<<item.units_sold<<" "
	  <<item.revenue<<" "<<item.avg_price();
	return os;
}

Sales_data add(const Sales_data &lhs, const Sales_data &rhs)
{
	Sales_data sum = lhs;//把lhs的数据成员拷贝给sum
	sum.combine(rhs);
	return sum;
}

int main()
{
	Sales_data total;
	string temp;
	temp = "shansan";
	total.bookNo = temp;
	//total.bookNo = "shansan";
	cout<<total.bookNo<<endl;
	cout<<total.isbn()<<endl;
	return 0;
}

运行结果

使用`=default`保留默认的构造函数 & 构造函数初始值列表

当我们需要其他构造函数的时，同时也希望保留默认的构造函数时候，可以使用= default
构造函数初始值是成员函数的一个列表，每个名字后面紧跟括号括起来的（或则在花括号内的）成员初始值。不同成员的初始值通过逗号分隔
构造函数初始值列表只说明用于初始化成员的值,而不限定初始化的具体执行顺序
但是如果一个成员是用另一个成员来初始化的，那么这两个成员的初始化顺序就很重要
consturctor(parameter):initializer_list,注意那个冒号，构造函数不能被声明成const的

#include<cstring>
#include<iostream>
using namespace std;

struct Sales_data{
    //新增构造函数
    //使用构造函数初始值列表，注意那个冒号
    //这两个构造函数的函数体都是空的，构造函数没有返回类型
	Sales_data() = default;//保留默认构造函数
	Sales_data(const string &s) :bookNo(s) {}
	Sales_data(const string &s, unsigned n, double p):bookNo(s),units_sold(n),revenue(p*n) {}
	//声明一个constructor，定义放在类外了
	Sales_data(istream&);


	string isbn() const{return bookNo;}//这是一个常量成员函数，不能改变调用它的对象的内容
	Sales_data& combine(const Sales_data&);
	double avg_price() const;

	string bookNo;
	unsigned units_sold = 0;
	double  revenue = 0.0;
};


double Sales_data::avg_price() const
{
	if(units_sold)
	    return revenue/units_sold;
	else
	   return 0;
}

Sales_data& Sales_data::combine(const Sales_data &rhs)
{
	units_sold += rhs.units_sold;
	revenue += rhs.revenue;
	return *this;//返回调用该函数的对象
}

/*
* Salse_data的非成员接口函数：
- add函数，执行两个Sales_data对象的加法
- read函数，将数据从istream读入到Sales_data对象中
- print函数，将Sales_data对象的值输出到ostream
*/
Sales_data add(const Sales_data& ,const Sales_data&);
ostream &print(ostream& , const Sales_data&);
istream &read(istream& , const Sales_data&);

//输入的交易信息包括ISBN、售出总数、售出价格
istream &read(istream &is, Sales_data &item)
{
    double price = 0.0;
	is>>item.bookNo>>item.units_sold>>price;
}
ostream &print(ostream &os, const Sales_data &item)
{
    os<<item.isbn()<<" "<<item.units_sold<<" "
	  <<item.revenue<<" "<<item.avg_price()<<endl;
	return os;
}

Sales_data add(const Sales_data &lhs, const Sales_data &rhs)
{
	Sales_data sum = lhs;//把lhs的数据成员拷贝给sum
	sum.combine(rhs);
	return sum;
}

//类外定义新的构造函数
Sales_data::Sales_data(istream &is)
{
    read(is,*this);//从is中读入一条信息存到this对象中
}

int main()
{
	Sales_data total;//调用默认的构造函数
	string temp;
	temp = "shansan";
	total.bookNo = temp;
	//total.bookNo = "shansan";
	cout<<total.bookNo<<endl;
	cout<<total.isbn()<<endl;

	Sales_data let("shansan.top",33,33);//调用构造函数Sales_data(const string &s, unsigned n, double p)
	cout<<let.bookNo<<" "<<let.units_sold<<" "<<let.revenue<<endl;

	Sales_data read_print;//调用默认的构造函数
	read(cin,read_print);
	print(cout,read_print);

	Sales_data dada(cin);//调用构造函数Sales_data(istream &is)
	print(cout,dada);

	return 0;
}

运行结果

委托构造函数

一个委托构造函数使用它所属类的其他构造函数执行它自己的初始化过程
它把自己的一些或全部职责委托给了其他构造函数
一个委托构造函数和其他构造函数一样也有一个成员初始值列表和一个函数体
委托构造函数的成员初始值列表只有一个入口，就是类名本身。类名后面紧跟圆括号括起来的初始值列表，参数列表必须与另一个构造函数匹配
当一个构造函数委托给另一个构造函数时，受委托的构造函数的初始值列表和函数体被依次执行

#include<iostream>
using namespace std;

class People{
	public:
		//非委托构造函数使用对应的实参初始化成员
        People(string m,string x,int n):first_name(m),last_name(x),age(n) {}

		//其余构造函数全部委托给另一个构造函数
		//注意使用冒号
		People(): People("li","lei",18){}
		People(string insert): People(insert,"wan",33){}
        People(int a): People("wu","ge",a){}

		int print_info(People temp)
		{
		    cout<<temp.first_name<<" "<<temp.last_name<<" "<<temp.age<<endl;
		    return 0;
		}
	private:
		string first_name;
		string last_name;
		int age;
};

int main()
{
	People num_1("shan","san",18);//调用构造函数 People(string m,string x,int n)
    num_1.print_info(num_1);

    People num_2;//调用委托构造函数 People("li","lei",18)
    num_2.print_info(num_2);

    People num_3("six");//调用委托构造函数 People(string insert)
	num_3.print_info(num_3);

	People num_4(100);//调用委托构造函数 People(int a)
	num_4.print_info(num_4);
	return 0;
}

运行结果

精度(precision)控制

yeshan333

CPP

文章首发于：2018年11月6日

CPP

C++输出精度（precision）控制,格式化输出

使用cout对象的成员

setprecision()
setf()
width()
fill()
flags(ios::fixed)

阅读全文

C++标准库类型

yeshan333

CPP

文章首发于：2018年11月5日

CPP

标准库类型string

标准库类型string表示可变长的字符序列
使用string类型必须包含string头文件，string定义在命名空间std中

定义和初始化string对象

初始化string对象的方式

初始化方式	说明
string s1	默认初始化，s1是一个空字符串
string s2(s1)	s2是s1的副本
string s2=s1	等价于s2(s1)，s2是s1的副本
string s3(“shansan”)	s3是字面值”shansan”的副本，除了字面值最后的那个空字符串外
string s3=”shansan”	等价于s3(“shansan”)
string s4(n,’c’)	把s4初始化为由连续n个字符c组成的串

阅读全文

C++11特性-1

yeshan333

CPP

文章首发于：2018年11月5日

CPP

c++11特性

列表初始化

使用花括号来初始化对象
使用列表初始化内置类型的变量，可能会存在丢失信息的风险

阅读全文

坑人的C++-2

yeshan333

CPP

文章首发于：2018年10月22日

CPP

C++文件和流

在C++中进行文件处理，可使用标准库fstream

它定义了三个新的数据类型，用于从文件写入流和从文件读取流

数据类型	描述
ofstream	该数据类型表示输出文件流，用于创建文件并向文件中写入信息
ifstream	该数据类型表示输入文件流，用于从文件中读取信息
fstream	该数据类型通常表示文件流，同时具有ofstream和ifstream两种功能，他可以创建文件，向文件中写入信息，从文件中读取信息