一.指针
定义
int *p
存放地址，而不是存在值的变量
int *p = &a, p = &a 地址赋值
*p表示的是指针存放的地址的内容
数组与指针
数组int a[100]
其中a就是一个指针，但是这个指针存的地址是不能修改的
a[i] 等价于*(a + i)
函数传参数的传的是也是这个指针，所以修改时是会修改数组的值的
参数写int a[]和int *a是一样的
指针数组
二.new的使用
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main() //给指针动态分配内存
{int *p = new int;delete p;int *q = new int[10];delete []q;int **k = new int*[10]; //10乘5 REP(i, 0, 10)k[i] = new int[5];REP(i, 0, 10)delete []k[i];delete []k;return 0;
}
三.类
用类和指针实现单链表
关键在于用struct储存节点，成员有指针
每一个节点都是一个指针，配合new 和 delete操作
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;struct node //链表中的节点用结构体，整个链表用类
{int data;node *next; //注意这里的类型是本身
};class List
{node *head; //一个链表类只有一个表头就可以了。注意是指针
public:List() { head = 0; } //无参构造要new表头。不过这个函数其实可以删掉void out(){node *p = head;while(p){printf("%d", p->data);if(p->next) putchar(' ');else puts("");p = p->next;}}List(int* a, int n){node *t = new node();t->data = a[1];head = t;node *p = head;_for(i, 2, n){node *t = new node();t->data = a[i];p->next = t;p = p->next;}out();}void Insert(int pos, int val){node *p = head;_for(i, 2, pos){p = p->next;if(!p){puts("error");return;}}node *t = new node();t->data = val;t->next = p->next;p->next = t;out();}void Remove(int pos){if(pos == 1){head = head->next;out();return;}node *p = head;_for(i, 3, pos){p = p->next;if(!p->next){puts("error");return;}}node *t = p->next;p->next = p->next->next;delete t;out();}~List(){while(head){node *t = head;head = head->next;delete t;}}
};int main()
{int T; scanf("%d", &T);while(T--){int n, a[100];scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);List C(a, n);int m; scanf("%d", &m);while(m--){int pos, val;scanf("%d%d", &pos, &val);C.Insert(pos, val);}int k; scanf("%d", &k);while(k--){int pos;scanf("%d", &pos);C.Remove(pos);}}return 0;
}
拷贝构造函数
注意类中有指针的时候，一定要写拷贝构造函数
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;class node
{int *a, n;
public:node() { a = 0; n = 0; }node(int *v, int N) //注意这里要传n进来 不能用sizeof 因为这样只会算头指针{n = N;a = new int[n];REP(i, 0, n) a[i] = v[i];}node(node &p) //拷贝构造函数{n = p.n;a = new int[n];REP(i, 0, n) a[i] = p.a[i] - 1;}void out(){REP(i, 0, n)printf("%d ", a[i]);puts("");}~node() { delete []a; }
};int main()
{int k[5] = {1, 2, 3, 4, 5};node A(k, 5);A.out();node B = A;B.out();return 0;
}
静态成员和静态成员函数
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;class node
{int a;static int mx;
public:node(int a = 0) : a(a) {}static void Find(node now){mx = max(now.a, mx);}static int get() { return mx; }
};
int node::mx = 0;int main()
{node x[5];REP(i, 0, 5){int a; cin >> a;x[i] = node(a);x[i].Find(x[i]);}cout << x[0].get();return 0;
}
四.重载运算符
可以重载+-*/
也可以重载用于输入输出的 << >>
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a) ; i < (b); i++)
#define _for(i, a, b) for(int i = (a) ; i <= (b); i++)
using namespace std;class C
{int a, b;
public:C(int a = 0, int b = 0) : a(a), b(b) {}C operator + (C x);friend ostream& operator << (ostream& o, const C& c);
};C C::operator + (C x)
{C res;res.a = a + x.a;res.b = b + x.b;return res;
}ostream& operator << (ostream& o, const C& c)
{o << c.a << " " << c.b;return o;
}int main()
{C A(1, 2), B(2, 3);cout << A + B;return 0;
}
这里着重讲一下重载 <<
ostream& operator << (ostream& o, const C& c)
{o << c.a << " " << c.b;return o;
}<<是一个运算符，类比加法
ostream是一个类
<<是头文件里面已经写好了
return o是为了可以连续输出，如cout << a << b
否则只能cout << a
这里的引用，ostream的引用是因为可以操作原来的，不加的话就要复制一份，而ostream这个类很大，很浪费资源
c重载也是直接操作，不写的话就要复制。这个复制要写拷贝构造函数
如果类里面有指针的时候，不写拷贝构造，就直接复制，导致两个指针指向同一个地方，而不是复制出来一份，就是错误的
所以这里避免这种情况，就直接引用
注意如果是临时对象是不能直接引用的，要写const才能引用临时对象
同时const保证了引用之后这个对象不会被误改
这个函数是一个独立的函数，写在类外面的，同时注意要写友元
重载前++后++
#include <bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;class node
{int a, b;
public:node(int a = 0, int b = 0) : a(a), b(b) {}node operator ++ () //前++ 先+再返回{a++;return *this;}node operator ++ (int) //加一个int就变成了后++ 注意先返回再加{node t = *this;b++; //注意是b不是t.breturn t;}void out(){printf("%d %d\n", a, b);}
};int main()
{node A(2, 3);(++A).out();node B(2, 3);(B++).out();return 0;
}
重载double()
#include <bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;class node
{int a, b;
public:node(int a = 0, int b = 0) : a(a), b(b) {}operator double() //前面不写返回类型{return 1.0 * a / b;}
};int main()
{node A(1, 2);cout << double(A);return 0;
}重载[] =
大多数运算符可以通过成员函数和非成员函数进行重载但是下面这四种运算符只能通过成函数进行重载：
= 赋值运算符，（）函数调用运算符，[ ]下标运算符，->通过指针访问类成员的运算符。
这道题重载=要引用
因为对象里面有指针
返回的时候如果没有引用，其实是把当前这个*this浅拷贝了
这样delete的时候就会对同一个内存空间delete两次就会出错
所以如果类里面有指针的话，最好写一个拷贝构造函数。当然如果你没有delete就不会暴露这个问题
在其他函数的传参，返回的时候会拷贝
这道题如果你不写拷贝构造的话，返回的值就要引用
如果类里面有指针又有析构函数的话，一定要写一个拷贝构造函数
什么时候调用拷贝构造函数？
一个对象以值传递的方式传入函数体 传值
一个对象以值传递的方式从函数返回 函数返回值
一个对象需要通过另外一个对象进行初始化。 初始化
第三点意味着
node a = b 调用了拷贝构造函数
node a
a = b 则没有调用
总结一下
当类里面有指针的时候
额外写一个拷贝构造函数
不然析构函数 delete的时候会出错
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;class CArray
{int n, m;int **data;
public:CArray() { n = m = 0; data = 0; }CArray(int nval, int mval) : n(nval), m(mval){data = new int*[n];REP(i, 0, n)data[i] = new int[m];}int operator () (int i, int j){return data[i][j];}CArray& operator = (const CArray& c) // 返回指针要引用 {int n = c.n, m = c.m;data = new int*[n];REP(i, 0, n)data[i] = new int[m];REP(i, 0, n)REP(j, 0, m)data[i][j] = c.data[i][j];return *this;}int* operator [] (int i) // {return data[i];}~CArray(){REP(i, 0, n) delete []data[i];delete []data;}
};int main()
{int T;int n, m;cin >> T;while(T--){cin >> n >> m;CArray mata(n, m);REP(i, 0, n)REP(j, 0, m)cin >> mata[i][j];cout << "MatrixA:" << endl;REP(i, 0, n){REP(j, 0, m)cout << mata(i, j) << " ";cout << endl;}cout << "MatrixB:" << endl;CArray matb;matb = mata;REP(i, 0, n){REP(j, 0, m)cout << matb[i][j] << " ";cout << endl;}}return 0;
}
重载加减号时一定要写const node& a
尤其有指针的时候
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;class Set
{int n, *data;
public:Set() { n = 0; data = 0; }Set(int N, int a[]){n = N;data = new int[n];REP(i, 0, n) data[i] = a[i];}~Set() { delete []data; }friend Set operator + (const Set& A, const Set& B);friend Set operator - (const Set& A, const Set& B);friend Set operator * (const Set& A, const Set& B);friend ostream& operator << (ostream& out, const Set& c);
};Set operator + (const Set& A, const Set& B) //
{int t[100] = {0}, cnt = 0;REP(i, 0, A.n) t[cnt++] = A.data[i];REP(i, 0, B.n){bool ok = 1;REP(j, 0, cnt)if(t[j] == B.data[i]){ok = 0;break;}if(ok) t[cnt++] = B.data[i];}return Set(cnt, t);
}Set operator - (const Set& A, const Set& B)
{int t[100] = {0}, cnt = 0;REP(i, 0, A.n)REP(j, 0, B.n){if(A.data[i] == B.data[j]) break;if(j == B.n - 1) t[cnt++] = A.data[i];}return Set(cnt, t);
}Set operator * (const Set& A, const Set& B)
{int t[100] = {0}, cnt = 0;REP(i, 0, A.n)REP(j, 0, B.n)if(A.data[i] == B.data[j]){t[cnt++] = A.data[i];break;}return Set(cnt, t);
}ostream& operator << (ostream& out, const Set& c)
{out << ":";REP(i, 0, c.n){out << c.data[i];if(i != c.n - 1) out << " ";}return out;
}int main()
{int T, n, a[100], b[100];cin >> T;while(T--){cin >> n;REP(i, 0, n) cin >> a[i];Set A(n, a);cin >> n;REP(i, 0, n) cin >> b[i];Set B(n, b);cout << "A" << A << endl;cout << "B" << B << endl;cout << "A+B" << A+B << endl;cout << "A*B" << A*B << endl;cout << "(A-B)+(B-A)" << (A-B)+(B-A) << endl;cout << endl;}return 0;
}
五.模板
可以表示任何数据类型
也可以用类，但是要自己定义运算符
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;template <class T>T ma(T a, T b)
{return a > b ? a : b;
}int main()
{cout << (1, 2) << endl;cout << (1.5, 2.3) << endl;cout << ("a", "b") << endl;return 0;
}
如果需要有多个可变的变量，那这么写
template <class T1, class T2, class T3>上面是函数模板，下面是类模板
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;template <class T>
class node
{T x;
public:node(T x) : x(x) {}T f(T x);
};template <class T> //类外函数的格式。注意要写上类型
T node<T>::f(T x) { return x * 2; }int main()
{node<int> A(2); //类模板必须要指定是什么类型return 0;
}
六.继承
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;class V
{int *space, size;
protected: //继承中可以用 int n;
public:V(int sz = 8) : size(sz), n(0), space(new int[sz]) {}void ins(int x, int n);int del(int pos);};class S:public V
{using V::ins; //禁用using V::del;
public:S(int sz = 16) : V(sz) {}void push(int x) { ins(x, n); }int pop(int x) { return del(n - 1); }
};int main()
{return 0;
}
class Point_1D
{
protected:double x;
public:Point_1D(double x = 0) : x(x) {}double distance() { return fabs(x); }
};class Point_2D:public Point_1D
{
protected:double y;
public:Point_2D(double x = 0, double y = 0) : Point_1D(x), y(y) {} //这里调用基类的构造函数，写x(x)会报错 另外 参数如果引用的话，调用时不能用临时变量double distance() { return sqrt(x * x + y * y); } //继承中可以有同名函数，在哪调用就用那个};七.多态与虚函数
/*b是祖先 b1是子孙可以写b = b1 把多的地方去掉b1 = b不能当基类和派生类用同样的函数时，基类用虚函数写引用或指针的时候可以调用派生类的函数*/#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;class B
{
public:virtual void print() { puts("B"); }
};class B1: public B
{
public:void print() { puts("B1"); }
};void out1(B b)
{b.print();
}void out2(B *b)
{b->print();
}void out3(B& b)
{b.print();
}int main()
{B1 b;out1(b);out2(&b);out3(b);return 0;
}
#include<bits/stdc++.h>
using namespace std;class A
{
public:A() { puts("A birth"); }virtual ~A() { puts("A death"); } //析构函数的虚函数
}; //如果不写virtual的话，派生类无法调用析构函数class B: public A
{
public:B() { puts("B birth"); }~B() { puts("B death"); }
};int main()
{A *p;p = new B();delete p;return 0;
}
#include<bits/stdc++.h>
using namespace std;class B
{
protected:int b;
public:B(): b(8) {}
};class B1: virtual public B
{
public:void add() { b++; }void B1show() { cout << b << endl; }
};class B2: virtual public B //虚继承，这样才是同一个b 否则有2个基类，2个b
{
public:void sub() { b--; }void B2show() { cout << b << endl; }
};class C: public B1, public B2
{
public:void inc() { add(); }void dec() { sub(); }
};int main()
{C a;a.inc();a.B1show();a.dec();a.B2show();return 0;
}
八.链表
注意几个点
一.空节点是没有next的，会错误
所以查找节点的过程中要在过程中判断是否为空节点
要时刻牢记这点
二.删除节点操作要特判删除头节点的情况