«

C++ 数据结构和算法入门笔记

时间:2021-7-24 18:10     作者:独元殇     分类: C/C++


C++ 的 OO 思想

OO 思想就是面向对象思想

一个再复杂的模型都是由千千万万的对象组成,就是根本思想。

世界上的所有事物都可以看做是对象,二对于每个对象,抽想起来均可以分为两个要素,属性行为

面向对象,不再是面对一个个函数和变量,要放眼大局,面对一个个对象来看问题。

封装思想

把对象的属性结合成一个独立的系统。

抽象

对一个具体问题进行概括的过程,例如,面包房提供一个抽象---“订单”

继承

子类有其基类(父类)的全部属性和方法,称为继承。

多态

在基类中定义的属性和行为被继承后,可以具有不同的数据类型或表现行为等特性。在共性中寻找个性。

C 与 C++ 的联系

如下程序

#include <stdio.h>

int addArray( int array[], int n);

int main()
{
    int data[] = {0,1,2,3,4,5,6,7,8,9};
    int size = sizeof(data) / sizeof(data[0]);

    printf("the size of data is : %d\n", sizeof(data));

    printf("the ret is : %d\n",addArray( data, size ));
     return 0;
}

int addArray( int array[], int n)
{
    int sum = 0;
    int i;

    printf("the size of array is : %d\n", sizeof(array));

    for( i = 0; i < n; i++)
    {
        sum += array[i];
    }

    return sum;
}

结果是

the size of data is : 40
the size of array is : 8
the ret is : 45

为什么不同呢?

因为`array``那个地方是把他当成了一个指针,8个字节,它不会把整个数组传进来,而是只传递一个地址,这样效率高。

那么将这个程序转化为c++,下面这个就是c++版本

#include <iostream>

using namespace std;

int addArray( int *array, int n);

int main()
{
    int data[] = {0,1,2,3,4,5,6,7,8,9};
    int size = sizeof(data) / sizeof(data[0]);

    cout << "the size of data is" << addArray( data, size ) << endl;
     return 0;
}

int addArray( int *array, int n)
{
    int sum = 0;
    int i;

    for( i = 0; i < n; i++)
    {
        sum += array[i];
    }

    return sum;
}

这个程序展示了C++对象的第一次使用,这个对象就是cout

cout是输出流对象,是 console out (控制台输出)的缩写,属于 basic_ostream 类的对象,而 ostream 类在中定义。

using namespace std;

C++ 标准库所使用的所有标识符,都是在同一个特殊的名字空间 (std) 中来定义的。与java中的概念是一样的。

如果没有这句话,我们将这样使用 std::cout 来调用输出流对象。

一般这句话都是给程序员偷懒用的。

<< 体现了 C++ 的特点,可以支持重载。

c 和 c++ 的简单转换

先看 c 版本,可以输入一串字符,以空格为隔,然后得出它们相加后的结果

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i;
    int sum = 0;
    char ch;

    printf("please type a list of number and space : ");

    while(scanf("%d", &i) == 1)
    {
        sum += i;
        while( (ch=getchar()) == ' ' )  // 屏蔽空格
        ;

         if( ch == '\n' )
         {
             break;
         }
         ungetc( ch,stdin );  // 将变量 出中存放的字符退回给stdio输入流

    }

    printf("the ret is : %d", sum);
    printf("\n");

    return 0;
}

这是 c++ 版本的

#include <iostream>

using namespace std;

int main()
{
    int sum = 0;

    cout << "please type a list of number and space : ";

    int i;
    while(cin >> i)
    {
        sum += i;
        while( cin.peek() == ' ' )
        {
            cin.get();
        } 
        if( cin.peek() == '\n' )
        {
             break;
        }
    }

    cout << "the ret is : " << sum << endl;

    return 0;
}

使用了流对象 cin ,它知道如何从用户终端读取数据,

cin >> i,这个有称为提取操作,一次从输入流对象中提取一个整数,当用户键盘输入时,对应字符将输入到操作系统的键盘缓存区中。

如果用户不进行操作,程序会进行阻塞。>>最初被定义为右移操作符,这里进行了重载。

while(cin >> i)中,表达式返回输入流本身,但如果到了文件尾或非法值,则返回 false 。

比如,在上面例子中,如果在程序运行时输入的是小数点,则会发生内部错误,返回0。

另外,c是在开头声明变量,而c++ 则允许我们在任意位置声明变量,大大提高了C++的可读性。

cin、cout 的多个方法

cinistream类的对象

第一个使用例子

#include <iostream>

using namespace std;
// 这个程序可以忽略前 7 个字符
// 并且字符的长度最大是 9 个
int main()
{
    char buf[20];  // 可以输入 19 个字符

    cin.ignore(7);
    cin.getline( buf, 10 );

    cout << buf << endl;

    return 0;
}

第二个使用例子

#include <iostream>

using namespace std;
// 这个程序会把你写的东西原封不动再给你打印一遍
int main()
{
    char p;  

    cout << "type some text:" << endl;

    while(cin.peek() != '\n' )
    {
        p = cin.get();
        cout << p;
    }

    cout << endl;

    return 0;
}

第三个小程序

#include <iostream>

using namespace std;
// 这个程序会提取前 20 个字符
int main()
{
    const int SIZE = 50;
    char buf[SIZE];  

    cout << "type some text:" << endl;
    cin.read( buf, 20 );

    cout << "the size of you type :" << cin.gcount() << endl;

    cout << "what you type is :";
    cout.write( buf,20);
    cout << endl;

    return 0;
}

文件和 IO

文件复制

先上来一个 c 语言版本的吧

#include <stdio.h>
#include <stdlib.h>

using namespace std;
// 这个程序会复制两个文件
int main(int argc,char * argv[] )
{
    FILE *in ,*out;
    int ch;

    if(argc != 3)
    {
        fprintf( stderr, "style: copyFile souer dest \n");
        exit( EXIT_FAILURE );
    }

    if( ( in = fopen( argv[1], "rb")) == NULL)
    {
        fprintf( stderr, "error of %s \n", argv[1]);
    }
    if( ( out = fopen( argv[2], "wb")) == NULL)
    {
        fprintf( stderr, "error of %s \n", argv[2]);
        fclose( in );  // 必须记得关掉
        exit( EXIT_FAILURE );
    }

    while( (ch = getc(in)) != EOF )
    {
        if( putc( ch,out ) == EOF )
        {
            break;
        }
    }
    if( ferror( in ))
    {
        printf("read %s error", argv[1] );
    }
    if( ferror( out ))
    {
        printf("read %s error", argv[2] );
    }

    printf("successful");

    fclose( in ); 
    fclose( in );

    return 0;
}

首先

int main(int argc,char * argv[] )int argc是几个参数

int * argv[] 的每个指针指向命令行的字符串,如

a.exe a.txt b.txt

这个就是 argv[] = {a.exe,a.txt,b.txt}

in 和 out 是我们声明的两个文件指针,为 IO 流对象使用

通过 fopen() 函数,我们以二进制形式按可读、可写的方式打开两个文件,并返回指针给 in 和 out 。

然后就是 c++ ,不过这个例子则只输出文件内容,而不是复制
运用的是 读取类 ifstream

#include <fstream>
#include <iostream>

using namespace std;
// 这个程序会复制两个文件
int main()
{
    ifstream in;

    in.open( "b" );
    if( !in )
    {
         cerr << "open this error" << endl;
         return 0;
    }

    char x;
    while( in >> x )
    {
        cout << x;
    }

    return 0;
}

运用写入类 ofstream

#include <fstream>
#include <iostream>

using namespace std;
// 这个程序会创建一个文件 test.txt 并写入 0123456789
int main()
{
    ofstream out;

    out.open( "test.txt" );
    if( !out )
    {
         cerr << "open this error" << endl;
         return 0;
    }

    for( int i=0; i < 10; i++ )
    {
        out << i;
    }

    out << endl;
    out.close();

    return 0;
}

c++ 的文件操作

常见的打开模式

ios::in -- 打开一个可读取的文件
ios::out -- 打开一个可写入文件
ios::binary -- 以二进制形式打开一个文件
ios::app -- 写入的所有数据将追加其末尾
ios::trunk -- 删除文件原内容
ios::nocreat -- 如果要打开的文件不存在,则 open 函数无法进行
ios::noreplece -- 如果要打开的文件已经存在,试图用 open 函数打开时将返回一个错误。

使用打开模式的例子

#include <fstream>
#include <iostream>

using namespace std;
// 这个程序会在 test.txt 后追加 0123456789
int main()
{
    ofstream out;

    out.open( "test.txt" );
    if( !out )
    {
         cerr << "open this error" << endl;
         return 0;
    }

    for( int i=0; i < 10; i++ )
    {
        out << i;
    }

    out << endl;
    out.close();

    return 0;
}

或者

#include <fstream>
#include <iostream>

using namespace std;
// 这个程序会在 test.txt 后追加 ccgxk.com
int main()
{
    fstream fp( "test.txt" , ios::app | ios::out );

    if( !fp ) 
    {
         cerr << "open this error" << endl;
         return 0;
    }

    fp << "ccgxk.com";

    static char str[10];

    fp.seekg(ios::beg);  // 让文件指针指向文件头,而 ios::end 则是文件尾
    fp >> str;
    cout << str << endl;

    fp.close();

    return 0;
}

为什么可以用 ios::app | ios::out ?
因为 ios::app = 0x1 ios::out = 0x2....它们相加不会互相干扰

小结

#include <fstream>
#include <iostream>

// 这个程序简单演示一个输入输出
int main()
{
    char answer;

    std::cout << "can you yes?(y/n)"<<"\n";
    std::cin >> answer;

    switch(answer)
    {
        case 'y':
        case 'Y':
            std::cout << "successful" << "\n";
            break;

        case 'n':
        case 'N':
            std::cout << "error" << "\n";
            break;

        default:
            std::cout << "warning!" << "\n";
            break;
    }

    std::cin.ignore(100,'\n'); // 加上这两行,就能阻塞了
    std::cin.get();

    return 0;
}
#include <iostream>

// 这个程序简单演示一个华氏温度与摄氏温度的相互转换
int main()
{
    // 华氏温度 == 摄氏温度 X 9.0 ÷ 5.0 + 32
    const unsigned short ADD_SUBTRACT = 32 ;
    const double RATIO = 9.0 / 5.0 ;

    double tempIn , tempOut;
    char typeIn, typeOut;

    std::cout << "type a temp";
    std::cin >> tempIn >> typeIn;

    std::cin.ignore(100, '\n');
    std::cout << "\n";

    switch (typeIn)
    {
    case 'C':
    case 'c':
        tempOut = tempIn * RATIO + ADD_SUBTRACT;
        typeOut = 'F';
        typeIn = 'c';

        break;

    case 'F':
    case 'f':
        tempOut = (tempIn - ADD_SUBTRACT) / RATIO;
        typeOut = 'C';
        typeIn = 'F';
        break;

    default:
        tempOut = 'E';
        break;
    }

    if( typeOut != 'E')
    {
        std::cout << tempIn <<typeIn
            << " = " << tempOut
            << typeOut << "\n\n";
    }

    return 0;
}

函数的重载

有着同样的名字,却有不同参数,相同用途的函数。

重载函数,可以简化编程工作和提高代码可读性。它不是一个面向对象的特征。只是简化编程工作的一种方案。简化工作也是C++的一个追求。

重载一定要谨慎,不要无的放矢,乱点鸳鸯。

我们只能通过不同的参数进行重载,但不能通过不同的返回值。

通过下面这个例子来说明一个简单的重载

#include <iostream>

void convertTemperature( double tempIn, char typeIn);
void convertTemperature( int tempIn, char typeIn);

// 这个程序简单演示一个华氏温度与摄氏温度的相互转换
int main()
{
    double tempIn ;
    char typeIn;

    int tempIntIn;

    std::cout << "type a temp";
    std::cin >> tempIn >> typeIn;

    std::cin.ignore(100, '\n');
    std::cout << "\n";

    convertTemperature( tempIn, typeIn);

    std::cout << "type a temp(int)";
    std::cin >> tempIntIn >> typeIn;

    std::cin.ignore(100, '\n');
    std::cout << "\n";

    convertTemperature( tempIntIn, typeIn);

    return 0;
}
void convertTemperature( double tempIn, char typeIn)
{
    // 华氏温度 == 摄氏温度 X 9.0 ÷ 5.0 + 32
    const unsigned short ADD_SUBTRACT = 32 ;
    const double RATIO = 9.0 / 5.0 ;

    double  tempOut;
    char typeOut;

    switch (typeIn)
    {
    case 'C':
    case 'c':
        tempOut = tempIn * RATIO + ADD_SUBTRACT;
        typeOut = 'F';
        typeIn = 'c';

        break;

    case 'F':
    case 'f':
        tempOut = (tempIn - ADD_SUBTRACT) / RATIO;
        typeOut = 'C';
        typeIn = 'F';
        break;

    default:
        tempOut = 'E';
        break;
    }

    if( typeOut != 'E')
    {
        std::cout << tempIn <<typeIn
            << " = " << tempOut
            << typeOut << "\n\n";
    }

}
void convertTemperature( int tempIn, char typeIn)
{
    // 华氏温度 == 摄氏温度 X 9.0 ÷ 5.0 + 32
    const unsigned short ADD_SUBTRACT = 32 ;
    const double RATIO = 9.0 / 5.0 ;

    int  tempOut;
    char typeOut;

    switch (typeIn)
    {
    case 'C':
    case 'c':
        tempOut = tempIn * RATIO + ADD_SUBTRACT;
        typeOut = 'F';
        typeIn = 'c';

        break;

    case 'F':
    case 'f':
        tempOut = (tempIn - ADD_SUBTRACT) / RATIO;
        typeOut = 'C';
        typeIn = 'F';
        break;

    default:
        tempOut = 'E';
        break;
    }

    if( typeOut != 'E')
    {
        std::cout << tempIn <<typeIn
            << " = " << tempOut
            << typeOut << "\n\n";
    }
}

复杂的数据类型

复杂 == 简单 + 简单

数据类型亦是如此,面向对象更是如初。

分为三类,数组、指针、结构。

数组

优点是可以吧很多同类型的值储存到同一变量下。

一个例子,给定 10 个数,将它们加起来

#include <iostream>

// 这个程序可以得到
int main()
{
    const unsigned short ITEM = 10;
    int num[ITEM];

    std::cout << "type " << ITEM << " int:\n\n";

    for(int i = 0; i < ITEM ; i++)
    {
        std::cout << "the " << i+1 << " num:";

        while ( !(std::cin >> num[i]) )  // 如果用户输入非法字符,提示重新输
        {
            std::cin.clear();
            std::cin.ignore( 100, '\n');
            std::cout << "type the num again!";
        }

    }
    int total = 0;  // 必须为 0 ,否则会出错

    for(int j = 0; j < ITEM; j++)
    {
        total += num[j];
    }

    std::cout << "total is" << total << "\n"; 
    std::cout << "total(ping_jun) is" << (float)total/ITEM; 

    return 0;
}

一个简单的 string 字符串

#include <iostream>
#include <string>

// 这个程序可以输什么就什么
int main()
{
    std::string str;
    std::cout << "type some text:";
    std::getline( std::cin, str);
    std::cout << str;

    return 0;
}

指针

地址是在内存里的地址。在c++中,变量类型是根据它们的自然边界进行对齐的。

一般32位操作系统的内存对齐值为 1000H = 4kb ,4kb 就是一页,64则是8kb,文件对齐值为 200H

变量的地址在程序执行期间是不会发生变化的。

一般我们这样声明 type * pointerName

int * p;
int pp = 123;
p = &pp;

注意:

int *p1,p2,p3 X // 这样只会将 p1 给设置为指针类型
int *p1,*p2,*p3 V

另外还有 void * p 这样的指针。

寻址

对于变量我们可以用两种方法进行索引,一是变量名,二是通过地址。

这里我们要用一个新的操作符,叫做取址的操作符 "&",它的作用就是获得变量的地址。

我们习惯这样使用

int var = 123;
std::cout << "Address is :" << &var;

解引用

std::cout << *aPointer ;

假设 aPointer 是变量 a 的指针,那么 aPointer 和 a 它们表示的将是同一个值,因此 aPointer = 123 ;

实例

#include <iostream>
#include <string>

// 这个程序是指针的使用实例
int main()
{
    int a = 123;
    float b = 3.14;
    char c = 'C';
    unsigned long d = 19880808;
    std::string e = "I Love Kohunglee";

    std::cout << "a is" << a << "\n";
    std::cout << "b is" << b << "\n";
    std::cout << "c is" << c << "\n";
    std::cout << "d is" << d << "\n";
    std::cout << "e is" << e << "\n";

    int *aP = &a;
    float *bP = &b;
    char *cP = &c;
    unsigned long *dP = &d;
    std::string *eP = &e;

    *aP = 1234;
    *bP = 3.1415;
    *cP = 'D';
    *dP = 120220223;
    *eP = "I Love ccgxk";

    std::cout << "a is -" << a << "\n";
    std::cout << "b is -" << b << "\n";
    std::cout << "c is -" << c << "\n";
    std::cout << "d is -" << d << "\n";
    std::cout << "e is -" << e << "\n\n";

    return 0;
}

星号的两种用途

第一种是创建指针,
[ex] int *myP = &myInt;

第二种是对指针进行解引用
[ex] *myP = 3998

群 P 和无类型指针

C++ 允许群 P ,一个变量可以有多个指针

也支持无类型指针

void *vP

注意,一个无类型指针解引用前,要先将它转化为一种适当的数据类型

指针和数组

数组有很多个地址,但是指针指向的是数组是基地址,也就是第一个元素的地址。

如果想通过指针访问其他数组的元素,应该怎么办呢?它是按照数据类型来进行 ++ 的

这是一个例子

#include <iostream>
#include <string>

// 这个程序是数组指针的使用实例
int main()
{
    const unsigned short ITEMS = 5;

    int intArray[ITEMS] = {1,2,3,4,5};
    char charArray[ITEMS] = {'c','c','g','x','k'};

    int *intPrt = intArray;
    char *charPrt = charArray;

    std::cout << "array out : " << "\n";
    for( int i= 0; i < ITEMS; i++)
    {
        std::cout << *intPrt << " at " << intPrt<< '\n';
        intPrt++;
    }

    std::cout << "array2 out : " << '\n';
    for( int i= 0; i < ITEMS; i++)
    {
        std::cout << *charPrt << " at " << charPrt<< '\n';
        charPrt++;
    }

    return 0;
}

结构

是程序员定义的数据类型,structure

就是结构体,里面的成员是没有限制的。

example

struct test
{
    std::string:: name;
};  // 切记,这里有一个分号

结构与指针

指针指向第一个元素的地址。

指针类型必须与指向地址的变量类型一样。

比如 test *pTest = &test

我们可以通过对指针进行解引用来访问响应的变量值。

譬如 (*pJiayu).name = "newName";

或者 i.e.

pJiayu -> name = "newName";

传值、传址和传引用

一个通过解引用来交换两个变量的案例

#include <iostream>
#include <string>

void swap(int *x, int *y );
void swap2(int *x, int *y );

// 这个程序是指针的交换地址实例
int main()
{
    int x ,y;

    std::cout << "type two num(x,y):";
    std::cin >> x >> y;

    swap2( &x, &y );

    std::cout << "the swap ret is : x=" << x << " y=" << y << "\n";

}

// 通过第三方中介变量 temp 来替换
void swap(int *x, int *y )
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

// 通过异或
void swap2(int *x, int *y )
{
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}

/*
swap2 的原理

比如
*x = 10101010
*y = 11100000 
xor= 01001010
*/

引用传递

c++ 完善了地址的这个概念

根据上面那个案例,我们可以直接这样写那个函数

swap( &x, &y );  --变成-->  
swap( x, y );

void swap(int *x, int *y );  --变成-->  
void swap(int &x, int &y );

联合、枚举和类型别名

联合

联合与结构很像,但它每次只能储存这些值中的某一个,存另一个值时会把上一个值覆盖掉。

创建

union password
{
    unsigned long birthday;
    unsigned short ssn;
    char *pet;
};

使用

password psw_1;

psw_1.birthday = 20011206;
psw_1.pet = "bengbeng";  // 此时 psw_1.birthday 会被丢弃(覆盖)

枚举

枚举类型用来创建一个可取值的列表

enum weekdays{ one, two, three, four, five};

一个例子

#include <iostream>
#include <string>

// 这个程序是枚举的应用实例
int main()
{
    enum week { mon, tues, wendnes, thurs, fri};

    week today;
    today = mon;

    std::cout << "today = " << today << "\n";
    today = tues;
    std::cout << "today = " << today << "\n";
}

枚举的好处

  1. 对变量的可取值加以限制
  2. 可以用作 Switch 条件语句的 case 标号

类型别名

可以为类型创建一个别名

typedef int* intPointer;

自此后,可以像下面这样来定义整型指针了。

intpointer myPointer;

对象

对象与结构体的区别

对象的内部可以有变量和函数,而结构通常只能由各种变量构成。

创建一个类

OOP 的过程的第一步是创建一个类,每个类和变量一样都有一个名字。

class Car
{
public:
    std::string color;
    std::string engine;
    float gas_tank;
    unsigned int wheel;

    void fill_tank( float liter );
    void running(void);=

};

void Car::fill_tank(float liter)
{
    gas_tank += liter;
}

类名第一个字母采用大写是一种习惯。

有些程序员喜欢吧类的声明和函数的定义分别存入 .h 和 .cpp 文件内。

C++ 允许在类里声明常量,但不允许对它进行赋值。

你也可以在声明某个类的时候,创建一些该类的对象,但也应避免使用这种做法,就如下面一样。

class Car
{

} car1, car2;

当然,吧一个对象赋值给另一个同类对象时,将会自动使同名属性有同样的值,这是一个快捷操作。就像下面这样。

Car car1, car2;
car1.setColor("WHITE");
...
car1 = car2;

构造器

创建构造器

class Car
{
public:
    std::string color;
    std::string engine;
    float gas_tank;
    unsigned int wheel;

    Car(void);
    void fill_tank( float liter );
    void running(void);=

};

Car::Car(void)
{
    this -> color = red;
}

创建析构器

析构器是不带参数的,所以析构器的声明永远是如下格式

~ClassName();

类的继承

继承的语法

class SubClass : public SuperClass {...}

class Pig : public Animal {...}

标签: 原创 C++ 数据结构

推荐阅读: