数据结构期末复习（C++部分）

1.参数传递

1)值传递

形参是实参的拷贝，改变形参的值不会影响实参的值

传递是单向的 从实参到形参

参数的值只能传入，不能传出

pass in the copy

2)引用传递

pass in the variable itself doesn\'t have to make copy save space

引用即为实参的别名，对引用的操作相当于对实参直接操作

语法：类型名&引用名=目标变量int&a=b

对数组的引用 int(&a)[4]=b 类型 (&引用名)[数组中元素数量]=数组名

对指针的引用 int(*&)a=b 类型(*&)应用名=指针

引用被创建是必须初始化，引用类型必须与目标类型相同

int main(){

int a=6;

int b=8;

void passByValue(int x)

{x=9;}

void passByReference(int &x)

{x=10;}

int a; &a; // address of a

int& a = b; // the "&" now means you\'re declaring a reference to "b".

Of course, when declaring a refence, you must immidiately assign it to something. References must always refer to something, they can\'t refer to nothing. So...

int& a; // not valid.

int& a = b; // valid.

To use it with function, you need to declare the function this way, to accept referneces: void function(int& a); // takes a reference to an int.

引用传参 返回多值

#include<iostream>
using namespace std;
#include <string>
int find_char(<span style="color:#ff0000;">const string s,int &a</span>)
{
  cout<<"the string is "<<s<<endl;
  decltype(s.size()) i=0;  //i 的类型个s.size 一样
   i=s.find(\' \',0);     //从索引0开始找第一个为空格的，返回索引，失败返回-1
   for(auto b=s.begin();b!=s.end();b++) //使用C++迭代器查找string中总的空格数
   {
       if(*b==\' \')
         <span style="color:#ff0000;">a++;  //这个引用参数虽然没有输出，但是我们仍然可以得到它，这就是引用的好处</span>
   }
     return i;
}
int main()
{
   string s="university software institute";
   int k=0;
   cout<<"the blank characters of first index is "<<find_char(s,k)<<endl;
   cout<<"the sum of black characters have "<<k<<endl;  //引用形参，形参改变，实参也跟着改变。
   return 0;  //<span style="color:#ff0000;">实现了一个返回值，却可以得到两个有用的参数</span>

}

3)指针传递

形参指向实参地址的指针，当对形参的指向操作时，就相当于对实参本身进行的操作

总结一下指针和引用的相同点和不同点：

★相同点：

●都是地址的概念；

指针指向一块内存，它的内容是所指内存的地址；而引用则是某块内存的别名。

★不同点：

●指针是一个实体，而引用仅是个别名；

 basic difference

pointer have the freedom to move around and point to different value 

 the reference is assigned one time and it just become the reference to that location in the memory.

https://www.youtube.com/watch?v=sxHng1iufQE

●引用只能在定义时被初始化一次，之后不可变；指针可变；引用“从一而终”，指针可以“见异思迁”；

●引用没有const，指针有const，const的指针不可变；（具体指没有int& const a这种形式，而const int& a是有     的，  前者指引用本身即别名不可以改变，这是当然的，所以不需要这种形式，后者指引用所指的值不可以改变）

●引用不能为空，指针可以为空；

●“sizeof 引用”得到的是所指向的变量(对象)的大小，而“sizeof 指针”得到的是指针本身的大小；

void swapint(int *a,int *b)
{
int temp;
temp=*a;
a=*b;
*b=temp;
}
void swapint(int &a,int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}

• ps+2

• s[2]

• ps[2]

• *(ps+2)

ps+2指向o字符的地址 而不是\'o\'
指针的引用

int m_value = 1;
void func(int *&p)
{
    p = &m_value;

    // 也可以根据你的需求分配内存
    p = new int;
    *p = 5;
}
int main(int argc, char *argv[])
{
    int n = 2;
    int *pn = &n;
    cout << *pn << endl;
    func(pn);
    cout << *pn <<endl;
    return 0;
}

https://www.cnblogs.com/li-peng/p/4116349.html

2.函数指针

void traverse(void (*visit)(List_Entry&))

https://zhuanlan.zhihu.com/p/37306637

函数返回类型（*指针变量)(形参列表）

int (*fp)(int a)

函数指针的应用

void List::traverse(void(*visit)(int &))
{for(int i=0;i<count;i++)
(*visit)(entry[i]);}
void print(int &x)
{cout<<x<<endl;}
mylist.traverse(print);

3.内存分配

https://blog.csdn.net/yuhushangwei/article/details/77489240

new :basically find a block of memory that is big enough to accommodate our needs and then give us  a pointer to point to that block of memory.

int * b=new int;//simply allocate an int

int * b=new int[50];//allocate an array

delete []b;

Entity * c=new Entity//Entity is a class allocate enough memory in the heap to store the memory and call the constructor

similar to Entity * c=(Entity*)malloc(sizeof(Entity))

the only difference is that the former will call a constructor while the latter will just allocate memory

you had better not use the latter

new is an operator 

变量的生命周期

除非静态局部变量外的变量生命周期是程序运行期一直存在

非静态局部变量 程序运行出局部作用域即被销毁

　　这条短短的一句话就包含了堆与栈，看到 new，我们首先就应该想到，我们分配了一块堆内存，那么指针 p 呢？他分配的是一块栈内存，所以这句话的意思就是：在栈内存中存放了一个指向一块堆内存的指针 p。

栈上变量函数结束时自动释放

4.类和成员变量

private只能在类内访问不能在类外访问

友元函数 普通函数访问某个类的私有和保护成员

友元类 类A的成员函数可以访问类B的私有和保护成员

https://blog.csdn.net/jackystudio/article/details/11799777

class A{
public: friend void getweight(A &p,int n);
private:int weight;
}
void getweight(A &pn,int w)
{
pn.weight=w;
}

5.constructor

class Entity{
float X,Y;
Entity(){
X=0.0f;
Y=0.0f;}

constructor with parameter

Entity(float x,float y)
{X=x;Y=y;}

Entity(float x,float y):X(x),Y(y)

int main()
{
Entity e;
Entity e(10.0f,50.0f);
}

参数化列表实现一般构造函数

Human(int _id,double _height):id(_id),height(_height)

相当于Human(int _id,double _height)

{id=_id;

height=_height;}

default constructor like ~Entity(){}

copy constructor

struct calculate
{float x,y;}
int main()
{
calculate * a=new calculate();
calculate * b=a;
b++;//will not effect a
b->x=2;//affect both a and b because a and b are both pointing to the same memory address

拷贝构造函数 

若没有显示地写一个构造函数 系统会自动创建一个构造函数

CExample A(100);
CExample B = A;
// CExample B(A);

后两种都会调拷贝构造函数

浅拷贝在指针调用时存在问题 

浅拷贝就是再用一个新的指针p2指向这片内存空间m1;

   深拷贝就是用一个新的指针p3指向m1的副本m2

   delete一个浅拷贝，首先要确定是不是有其它的指针还在指向这片空间。不然，其他指向这片空间的指针直接就是野指针了。为什么野指针那么是绝对要禁止的？野指针现在指向了一片内存区间，这片内存区间以前是有意义的，现在被释放了，操作系统可能会讲这边区间放上其它程序数据。那么，野指针仍然指向了这片区间。如果此时使用野指针，改变了这片内存的数据，那么程序应该直接崩溃。
————————————————
原文链接：https://blog.csdn.net/suifengpiao_2011/article/details/41448733

两个指针同时delete同一块地址会出现问题

copy

class string{
private :char * m_buffer;//point to the buffer of chars
unsigned int m_size;
public: string(const char *string)
{m_size=strlen(string);
m_buffer=new char[m_size];
for(int i=0;i<m_size;i++)
{m_buffer[i]=string[i];
}//memcpy(m_buffer,string,m_size);
};

 构造函数

特点 名字与类名相同

没有返回值

调用时机

栈空间上

main(){

X x;<-调用构造函数

}<-调用析构函数

堆空间上 *X a=new X;<-调用构造函数

看程序输出时 不要漏构造函数和析构函数的输出

5.destructor

the } at the end of the function just call the destructor

6.const

成员函数后加const

Error_code top(int &item) const;

不能在函数中修改成员变量，不能调用不带const的成员函数

因为不带const的成员函数很有可能会修改成员变量的值

const常对象只能调用const成员函数

const List myList;
myList.GetLength();//正确

const List myList;
myList.DeleteNode(3);//错误 调用非const
详见https://www.jianshu.com/p/a90a2036d39c

成员函数中参数加const

Error_code push(const int &item);

传递过来的参数item在函数中不能改变