有了指针，就有了自由访问内存空间的手段。
指针的基本概念：
每个变量都被存放在从某个内存地址开始的若干字节中。
指针也叫作指针变量，大小为4个字节（64位计算机为8个字节）的变量，其内容代表一个内存地址。
通过指针，能够对该指针指向的内存空间进行读写。
如果把内存的每一个字节都想象成一个房间，那么内存地址相当于房间号，而指针里存放的就是房间号。
指针变量的赋值、定义：
类型说明符 *变量名
int *p； p是一个指针，变量p的类型是int*。
char *c；c是一个指针，变量c的类型是char*。
float *d；d是一个指针，变量d的类型是float*。
如何访问int型变量a前面一个字节？
int a；
char*p=（char*）&a；
--p；
printf（“%c”，*p）；//可能会导致运行出错
*p=‘A’；//可能会导致运行出错（可能不让访问）
（以上方法是错误的）
int *p1，*p2；int n=4；
char *pe1，*pe2；
p1=（int*）100；
p2=(int*)200;
cout<<"1)"<<p2-p1<<endl;
通过指针访问其指向的内存空间：
int *p=（int*）40000；
*p=5000；
int n=*p；
若干=sizeof（int），因为int*p。
指针定义的总结：
T*p；T可以是任何类型，如float，int char。
p的类型是T*。
*p的类型是T。
通过表达式*p可以读写从地址p开始的sizeof（T）个字节。
*是间接引用运算符。
指针用法：
char ch=‘A’；
char *pc=&ch；
&取地址符
指针的作用：
不需要通过变量就可以直接对内存空间进行操作。通过指针，程序能访问的内存空间就不仅限于变量所占有的内存空间。
指针的互相赋值：
不同类型的指针，如果不经过强制类型转换，不可以相互赋值。
int*pn，char*pc，char c=0x65；
pn=pc；//类型不匹配，编译出错
pn=*c；//类型不匹配，编译出错
pn=（int*）&c；
int n=*pn；//n值不确定
*pn=0x12345678；//编译没毛病，但运行会错误，可能会导致程序的崩溃
指针的运算：
1.两个同类型的指针变量可以比较大小（比较地址的大小）
地址p1<地址p2 == p1<p2 值为真
地址p1=地址p2 == p1==p2 值为真
地址p1>地址p2 == p1>p2 值为真
2.两个同类型的指针变量，可以相减
两个T*类型的指针p1和p2
p1-p2=（地址p1-地址p2）/sizeof（T）
3.指针变量加减一个整数的结果是一个指针
p：T*类型的指针
n：整数类型的变量或常量
p+n：T*类型的指针，指向地址：地址p+n*sizeof(T)
n+p，p-n，*（p+n），*（p-n）含义自明
4.指针变量可以自增自减
T*类型的指针p指向地址n
p++，++p：p指向n+sizeof（T）
p--，--p：p指向n-sizeof（T）
5.指针可以用下标运算符“[ ]”进行运算
p是一个T*类型的指针，n是整数类型的常量或变量。
p【n】=*（p+n）
空指针：
地址0不能访问。指向地址0的指针就是空指针。
可以用“NULL”关键字对任何类型的指针进行赋值，NULL实际上就是整数0。
int *p1=NULL;char *pc=NULL;int *p2=0;
指针可以作为条件表达式使用，如果指针的值为NULL，则相当于假，反之为真。
if（p）等价于if（p！=NULL）。
指针作为函数参数：
#include<bits/stdc++.h>
using namespace std;
void swap(int *p1,int *p2)//p1 形参
{
int temp=*p1;
*p1=*p2;
*p2=temp;
}
int main(){
int n=3,m=4;//n实参
swap(&n,&m);
cout<<m<<' '<<n<<endl;
return 0;
}
指针和数组：
数组的名字是一个指针常量，指向数组的初始地址。
T a[n];
a的类型是T*
可以用a给T*类型的指针赋值
a是编译时其值就已经确定了的，不能够对a进行赋值
作为函数形参时，T*p和T p[ ]是等价的
void（int T*p）{cout<<sizeof(p)};
void(int T p[ ]){cout<<sizeof(p)};
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[200];int *p;
p=a;//p指向数组a的初始地址，亦指p指向了a[0]
*p=10;//使得a[0]=10
*(p+1)=20;//a[1]=20
p[0]=30;//p[i]和*p[i+1]是等效的，使得a[0]=30
p[4]=40;//a[4]=40
for(int i=0;i<10;i++)//对数组a的前十个元素进行赋值
*(p+i)=i;
++p;//p指向a[1]
cout<<p[0]<<endl;//输出1 p[0]等效于*p，p[0]即是a[1]
p=a+6;//p指向a[6]
cout<<*p<<endl;//输出6
return 0;
}
翻转
代码：
#include<bits/stdc++.h>
using namespace std;
void reverse(int *p,int size){
for(int i=0;i<size；i++){
int temp=p[i];
p[i]=p[size-i];
p[size-i]=temp;
}
}
int main(){
int a[5]={1,2,3,4,5};
reverse(a,sizeof(a/sizeof(int));
for(int i=0;i<5;i++)
cout<<*(a+i)<<',';
return 0;
}
动态数组：
指针可以动态申请空间，如果一次申请多个变量空间，系统给的地址是连续的，就可以当做数组使用，这就是传说中的动态数组的一种。
#include<bits/stdc++.h>
using namespace std;
int n;
int *a;
int main(){
cin>>n;
a=new int[n+1];
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=2;i<=n;i++)
a[i]+=a[i-1];
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
return 0;
}
动态数组的优点：
在OI中，对于大数据可能超空间的情况是比较纠结的事，用小数组只能得部分分，大数组可能爆空间同时又爆零，使用动态数组可以在确保小数据没问题的前提下，尽量满足大数据的需求。
指针和字符串：
字符串常量的类型是char*
字符数组名的类型是char*,就是一个地址。
注意：可以使用字符数组名或者字符指针输出一个字符串，而面对一个数值型数据是不能企图用数组名输出它的全部元素的。
如：
int i[10];
……
printf("%d\n",i);
代码:
#include<bits/stdc++.h>
using namespace std;
int main(){
char*p="please input your name:\n";
cout<<p;
char name[20];
char*pname=name;
cin>>pname;
cout<<"your name is "<<pname;
return 0;
}
字符串指针作函数参数：
将一个字符串从一个函数传递到另一个函数，可以用地址传递的方法，即用字符数组名作参数或用指向字符的指针变量做参数。在被调用的函数中可以改变字符串的内容，在主调函数中可以得到改变了的字符串。
例题：
输入一个长度最大为100的字符串，以字符数组的方式存储，再将字符串倒序储存，输出倒序储存后的字符串（这里以字符指针为函数参数）
#include<bits/stdc++.h>
using namespace std;
void swapp(char &a,char &b){
char t;
t=a;
a=b;
b=t;
}
void work(char *str){
int len=strlen(str);
for(int i=0;i<=len/2;i++)
swapp(str[i],str[len-i-1]);
}
int main(){
char s[110];
char *str=s;
gets(s);
work(str);
printf("%s",s);
return 0;
}
字符串操作函数：
void指针：
void*p；
可以用任何类型的指针对void指针进行赋值或初始化
double d=1.54;
void*p=&d;
void*p1;
p1=&d;
因sizeof（void）没有定义，所以对于void*类型的指针p，*p无定义，++p，--p，p+=n，p-=n，p+n，p-n等均无定义。
内存操作库函数memset：
头文件cstring中声明：
void*memset(void*dest,int ch,int n);
将从dest开始的n个字节，都设置成ch，返回值是dest，ch只有最低的字节起作用。
内存操作库函数memcpy：
头文件cstring中声明：
void*memcpy(void*dest,void*src,int n);
将地址src开始的n个字节，拷贝到地址dest。返回值是dest。
注意！有缺陷，在dest区间和src区间有重叠时可能出问题！
试手：
1.输入n个数，使用指针变量访问输出。
#include<bits/stdc++.h>
using namespace std;
int a[111],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int *p=&a[1];
for(int i=1;i<=n;i++){
cout<<*p<<' ';
p++;
}
return 0;
}
2.无类型指针运用：
#include<bits/stdc++.h>
using namespace std;
int a=10;
double b=3.5;
void *p;
int main(){
p=&a;
cout<<*(int *)p<<endl;
p=&b;
cout<<*(double*)p<<endl;
return 0;
}
3.多重指针：
#include<bits/stdc++.h>
using namespace std;
int a=10;
int *p;
int **pp;
int main(){
p=&a;
pp=&p;
cout<<a<<' '<<*p<<' '<<**pp;
return 0;
}
多重指针除了可以多次间接访问数据，OI上主要的应用是动态的多维数组。
4.访问数组
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[5],i,*pa=a;
for(i=0;i<5;i++)
cin>>a[i];
for(i=0;i<5;i++)
cout<<*(pa+i);
return 0;
}
5.行列转换问题
描述：矩阵可以认为是N*M的二维数组，现在有一个巨大但稀疏的矩阵。
N，M范围是：1<=N,M<=100000，有K个位置有数据，K的数据范围是1<=K<=100000。
矩阵输入的方式是从上到下，从左到右扫描，极路由数据的坐标位置和值，这是按照行优先的方式保存数据的。现在要求按照列优先的方式输出数据，即从左到右，从上到下扫描，输出有数据的坐标和值。
输入格式:
第一行，三个整数N，M，K；下面有K行，每行三个整数：a，b，c，表示的a行b列有数据c，数据在int范围内，保证是行优先的次序。
输出格式：
一行，K个整数，是按照列优先次序输出的数。
样例输入：
4 5 9
1 2 12
1 4 23
2 2 56
2 5 78
3 2 100
3 4 56
4 1 73
4 3 34
4 5 55
样例输出：
73 12 56 100 34 23 56 78 55
样例解释：
分析：
由于N,M可能会很大，直接开二维数组太大，不可行。解决问题的方法有很多种，下面的程序使用了指针和动态数组，根据每一列的实际数据个数来申请该列的空间，使每列的数组长度不同。算法是O（N+M+K）的时间复杂度（即程序的运算量）。
参考程序：
#include<cstdio>
using namespace std;
const int LP=100001;
int n,m,k;
int x[LP],y[LP],d[LP];
int c[LP];//每列的数据个数
int *a[LP];//每列一个指针，准备申请数组
/*这里固定大小为LP的一个指针数组，占用空间为5*4*LP字节，约2M
还可以在输入n，m后，在申请动态数组，当n，m较小时，占用更小的空间
a[i]表示第i列的指针*/
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=k; i++) {
scanf("%d%d%d",&x[i],&y[i],&d[i]);//x [i]和y[i]是第i个数据所在的行号和列号
c[y[i]]++//统计c数组中每列数据的个数;
}
for(int i=1; i<=m; i++)
a[i]=new int [c[i]];//第i列指针申请数组空间
for(int i=1; i<=k; i++) {//收集k个数据到相应的列中
*a[y[i]]=d[i];//数据放在相应列的数组中，也可以写成a[y[i]][0]=d[i]
a[y[i]]++;//数组指针移到下一个位置
}
for(int i=1; i<=m; i++) {//列优先
a[i]-=c[i];//指针回到每列的前面
for(int j=1; j<=c[i]; j++,a[i]++)
printf("%d ",*a[i]);
}
return 0;
}
说明：特别的，可以把指针当数组名用。
指针与函数：
编写一个函数，将三个整型变量排序，并将三者中的最小值赋给第一个变量，次小值赋给第二个变量，最大值赋给第三个变量。
#include<bits/stdc++.h>
using namespace std;
void swap(int *x,int*y){
int t=*x;
*x=*y;
*y=t;
}
void sort(int *x,int *y,int *z){
if(*x>*y)swap(x,y);
if(*x>*z)swap(x,z);
if(*y>*z)swap(y,z);
}
int main(){
int a,b,c;
cin>>a>>b>>c;
sort(&a,&b,&c);
cout<<a<<' '<<b<<' '<<c;
return 0;
}
函数返回指针：
一个函数可以返回整数值，字符值，实型值等，也可以返回指针联系的数据（即地址）。
定义：
类型名*函数名（参数列表）；
如
int *a(int a,int b)
a是函数名，调用它后得到一个指向整型数据的指针（地址）
注意：在*a的两侧没有括号；在a的两侧分别为*运算符和（）运算符，由于（）的优先级高于*，因此a先与（）结合。在函数前面有一个*，表示此函数是返回指针类型的函数。最前面的int表示返回的指针指向整型变量。
例题：
编写一个函数，用于在一个包含N个整数的数组中找到第一个质数，若有则返回函数的地址，否则返回NULL（空指针）。
#include<bits/stdc++.h>
using namespace std;
int n,a[10001];
bool isprime(int n) {
if(n<2)return false;
if(n==2) return true;
for(int i=2; i<=sqrt(n); i++)
if(n%i==0)
return false;
return true;
}
int *find() {
for(int i=1; i<=n; ++i)
if(isprime(a[i]))
return &a[i];
return NULL;
}
int main() {
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
int *p=find();
if(p!=NULL)
cout<<p<<endl<<*p<<endl;
else
printf("can't find!");
return 0;
}
函数指针和函数指针数组：
使用函数指针调用函数示例：
#include<bits/stdc++.h>
using namespace std;
int t(int a){
return a;
}
int main(){
cout<<t<<endl;//显示函数地址
int(*p)(int a);//定义函数指针变量p
p=t;//将t的地址赋给函数指针p
cout<<p(5)<<","<<(*p)(10)<<endl;
//输出p(5)是C++的写法，（*p）(10)是兼容C
return 0;
}
函数指针的基本操作：
1.声明函数指针
注意：一定要这样声明！int （*fp）（int）
2.获取函数的地址
3.使用函数指针来调用函数
使用typedef定义函数指针示例：
#include<bits/stdc++.h>
using namespace std;
int sum(int a,int b){
return a+b;
}
typedef int (*LP)(int,int);
int main(){
LP p=sum;
cout<<p(2,5);
return 0;
}
在软件开发编程中，函数指针的一个广泛应用是菜单功能函数的调用，通常选择菜单的某个选项都会调用相应的功能函数，而且有些软件的菜单会根据情况发生变化（上下文敏感）如果使用switch/case或if语句处理起来会比较复杂，不利于代码的维护，可以考虑使用函数指针数组方便灵活的实现。
结构体指针：
当一个指针变量用来指向一个结构体变量时，称之为结构体指针。
定义：
结构体名*结构体指针变量名
char stu {
char name[20];
char sex;
float score;
} *p;
或
char stu {
char name[20];
char sex;
float score;
} ;
stu *p;
结构体指针变量必须要赋值后才能使用，赋值是把结构体变量的首地址赋予该指针变量，不能把结构名赋予该指针变量。
如p=&stu是错误的；
引用结构体指针变量指向的结构体变量的成员的方法如下：
1.指针名->成员名
2.（*指针名）.成员名
示例：
#include<bits/stdc++.h>
using namespace std;
struct stu{
char name[20];
char sex;
float score;
}s[3]={{"xiaoming",'f',356},
{"xiaoliang",'f',350},{"xiaohong",'m',0}};
int main(){
stu*p;
printf("Name Sex Score\n");
for(p=s;p<s+3;p++)
printf("%-9s%3c%7d\n",p->name,p->sex,p->score);
return 0;
}
这里p++起到了移动指针的作用
自引用结构：
自引用结构是实现动态数据结构的基石，包括动态的链表，堆，栈，树，无不是自引用结构的具体实现。
