C++｜理解指针的关键在于理解指针的赋值、移动及其相关的表达式

数据存储到内存对于强类型的C++来说，有四个属性：

地址、类型、尺寸、值；

普通变量名称显式表示的是其值，可通过取值运算符“&”取得其地址；

如果一个变量的值保存的是某一块内存的首地址，这样的变量称为指针变量，其显式表示的是地址，可通过解引用运算符“*”来引用其值。

如果一个变量声明时类似指针变量、使用时类似普通变量，这样的变量在C++中称为引用，是一个由编译器实现了自动解引用的指针常量。

理解指针的关键在于各种数据结构中对于指针移动的理解。指针的移动的实质就是通过一个合法的指针变量的算术运算，来更新地址的值，这样指针变量有了新的值，也就是相当于指针发生了移动。当指针变量做左值时，赋值符号可以理解为指针的指向或移动：

p = head; // p指向（移动到）head

p = p->next; // p指向（移动到）p指向的下一个元素

1 顺序表

对于数组，数组名指向内存块的首地址，下标相当于是首地址的偏移量，所以下标的++、--运算其与整数的算术运算可以理解为地址的移动：

	int arr[] = { 1, 1, 2, 3, 5, 8, 13, 21 };
 int size = sizeof(arr)/sizeof(arr[0]);
	for(int i=size-1; i>=0; i--)
		cout<<arr[i]<<" ";
	int* p = arr;
	for(int j=0; j<size; j++)
		cout<<*(p+j)<<" ";

2 链表

链表是通过节点的指针域来实现节点之间的联系：

pRead=pRead->next;表示指针pRead指向其指向的下一个元素：

void Showlist(node *head)
{
	node *pRead=head;			//访问指针一开始指向表头
	cout<<"链表中的数据为：" <<endl;
	while (pRead!=NULL)			//当访问指针存在时（即没有达到表尾之后）
	{
		cout<<pRead->data;		//输出当前访问结点的数据
		pRead=pRead->next;		//访问指针向后移动（指针偏移）
	}
	cout<<endl;
}

3 二叉树（如果用数组模拟）

堆是一棵完全二叉树，可以用数组模拟，树的上、下两层的下标有*2或/2的关系

#include <iostream>
using namespace std;
const int MAX = 55;
typedef struct Heap
{
	int sizeHeap;
	int* heapData;
}HEAP,*LPHEAP;
LPHEAP createHeap()
{
	LPHEAP heap=(LPHEAP)malloc(sizeof(HEAP));
	heap->sizeHeap=0;
	heap->heapData=(int*)malloc(sizeof(int)*MAX);
	return heap;
}
int size(LPHEAP heap)
{
	return heap->sizeHeap;
}
int empty(LPHEAP heap)
{
	return heap->sizeHeap==0;
}
void moveToCorrectPos(LPHEAP heap, int curPos)//向上渗透，curPos一般取最后一个元素的下标
{
	while(curPos>1)
	{
		int Max=heap->heapData[curPos];
		int parentIndex=curPos/2;
		if(Max>heap->heapData[parentIndex])
		{
			heap->heapData[curPos]=heap->heapData[parentIndex];
			heap->heapData[parentIndex]=Max;
			curPos=parentIndex;//向上移动
		}
		else
		{
			//break;
		}
	}
}
void insertHeap(LPHEAP heap, int data) //放到当前堆的最后面并按条件往上移
{
	++heap->sizeHeap;
	heap->heapData[heap->sizeHeap]=data;
	moveToCorrectPos(heap,heap->sizeHeap);
}
int popHeap(LPHEAP heap)
{
	int Max=heap->heapData[1];
	int curPos=1;
	int childIndex=curPos*2;
	while(childIndex<=heap->sizeHeap)
	{
		int temp = heap->heapData[childIndex];
		if(childIndex+1<=heap->sizeHeap && temp<heap->heapData[childIndex+1])
		{
			temp=heap->heapData[++childIndex];
		}
		heap->heapData[curPos]=temp;
		curPos=childIndex;//下移一层
		childIndex*=2;
	}
	heap->heapData[curPos]=heap->heapData[heap->sizeHeap];
	--heap->sizeHeap;
	return Max;
}
void main()
{
	LPHEAP heap=createHeap();
	for(int i=1;i<11;++i)
	{
		insertHeap(heap,i);
	}
	for(i=1;i<11;++i)
	{
		printf("%d\t",heap->heapData[i]);
	}
	printf("\n");
	while(!empty(heap))
	{
		printf("%d\t",popHeap(heap));
	}
 system("pause");
}
/*
10 9 6 7 8 2 5 1 4 3
10 9 8 7 6 5 4 3 2 1
*/

4 二叉树（如果用链表实现）

用链表实现的二叉树，其节点的下移可以用诸如p = p->left;的表达式实现：

#include "stdio.h"
#include <iostream>
#include <queue>
using namespace std;
typedef struct BiTNode{
 char data;							/*结点的数据域*/
 struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/
} BiTNode , *BiTree;
void CreatBiTree(BiTree *T){						/*按先序遍历的思想创建一棵二叉树*/
 char c;
 scanf("%c",&c);
 if(c == ' ') *T = NULL;
 else{
 *T = (BiTNode * )malloc(sizeof(BiTNode)); /*创建根结点*/
 (*T)->data = c;								/*向根结点中输入数据*/
 CreatBiTree(&((*T)->lchild));				/*递归地创建左子树*/
 CreatBiTree(&((*T)->rchild));				/*递归地创建右子树*/
 }
}
void PreOrderTraverse(BiTree T ){		/*先序遍历二叉树*/
 if(T){								/*递归结束条件，T为空*/
 printf("%3c",T->data);			/*访问根结点,将根结点内容输出*/
 PreOrderTraverse(T->lchild);	/*先序遍历T的左子树*/
 PreOrderTraverse(T->rchild);	/*先序遍历T的右子数*/
 }
}
void visit(BiTree p) {
	printf("%3c",p->data);
}
void layerOrderTraverse(BiTree T)	//按层遍历
{
 BiTree queue[20],p;
 int front,rear;
 if(T!=NULL)
 {
 queue[0] = T;					/*将根结点的指针（地址）入队列*/
 front = -1;
 rear = 0;
 while(front<rear)				/*当队列不为空时进入循环*/
 {
 p = queue[++front];		/*取出队头元素*/
 visit(p); 				/*访问p指向的结点元素*/
 if(p->lchild!=NULL)		/*将p结点的左孩子结点指针入队列*/
 queue[++rear] = p->lchild;
 if(p->rchild!=NULL)		/*将p结点的右孩子结点指针入队列*/
 queue[++rear] = p->rchild;
 }
 }
}
void layerOrderTraverse2(BiTree T)	//按层遍历，使用queue
{
	BiTree p;
	queue <BiTree> q;
	if(T!=NULL)
	{
		q.push(T);					/*将根结点的指针（地址）入队列*/
		while(! q.empty())			/*当队列不为空时进入循环*/
		{
 p = q.front();		
			q.pop();				/*取出队头元素*/
 visit(p); 				/*访问p指向的结点元素*/
 if(p->lchild!=NULL)		/*将p结点的左孩子结点指针入队列*/
 q.push(p->lchild);
 if(p->rchild!=NULL)		/*将p结点的右孩子结点指针入队列*/
 q.push(p->rchild);
		}
	}
}
main()
{
 BiTree T = NULL; /*最开始T指向空*/
 printf("需要创建和遍历的二叉树：\n");
	printf(" A\n");
	printf(" / \\\n");
	printf(" B E\n");
	printf(" / \\ \\\n");
	printf(" C D F\n");
 printf("Input some characters to create a binary tree\n");
 printf("（按先序序列建立）\n");
 printf("例如，ABC##D##E#F##↙，#表示空格,↙表示回车\n");
 printf("Input some characters to create a binary tree:\n");
 CreatBiTree(&T); /*创建二叉树*/
 printf("\nThe squence of layerorder traversaling binary tree:\n");
 layerOrderTraverse(T); 
 printf("\nThe squence of PreOrder traversaling binary tree:\n"); 
 PreOrderTraverse(T);

 layerOrderTraverse2(T);
 getchar(); getchar();
}

5 栈（如果用数组模拟）

如果用一个整数来模拟栈顶指针：int top=0;则其++、--的操作便相当于是指针的移动。

#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef struct BiTNode{
	char data;/*结点的数据域*/
	struct BiTNode *lchild , *rchild;/*指向左孩子和右孩子*/
} BiTNode , *BiTree;
void CreatBiTree(BiTree *T){/*按先序序列创建一棵二叉树*/
	char c;
	scanf("%c",&c);
	if(c == ' ') *T = NULL;
	else{
		*T = (BiTNode * )malloc(sizeof(BiTNode));/*创建根结点*/
		(*T)->data = c;/*向根结点中输入数据*/
		CreatBiTree(&((*T)->lchild));/*递归地创建左子树*/
		CreatBiTree(&((*T)->rchild));/*递归地创建右子树*/
	}
}
void PreOrderTraverse(BiTree T ){/*先序遍历二叉树*/
	if(T){/*递归结束条件，T为空*/
		printf("%3c",T->data);/*访问根结点,将根结点内容输出*/
		PreOrderTraverse(T->lchild);/*先序遍历T的左子树*/
		PreOrderTraverse(T->rchild);/*先序遍历T的右子数*/
	}
}
void InOrderTraverse(BiTree T){/*中序遍历二叉树*/
	if(T){/*如果二叉树为空，递归遍历结束*/
		InOrderTraverse(T->lchild);/*中序遍历T的左子树*/
		printf("%3c",T->data);/*访问根结点*/
		InOrderTraverse(T->rchild);/*中序遍历T的右子数*/
	}
}
void PosOrderTraverse(BiTree T){/*后序遍历二叉树*/
	if(T){/*如果二叉树为空，递归遍历结束*/
		PosOrderTraverse(T->lchild);/*后序遍历T的左子树*/
		PosOrderTraverse(T->rchild);/*后序遍历T的右子数*/
		printf("%3c",T->data);/*访问根结点*/
	}
}
void PreOrder_NR(BiTree T)//深度优先非递归前序遍历
{
	BiTree Ptr;
	BiTree Stack[MAX];//栈定义
	int top=0;//栈顶指针
	Ptr = T;
	do
	{
		while(Ptr!=NULL)//树结点非空，遍历其左子树
		{
			printf("%3c",Ptr->data);//操作结点
			Stack[top]=Ptr;//树结点进栈
			top++;
			Ptr=Ptr->lchild;//查看左子树
		}
		if(top>0)//栈非空，出栈
		{
			top--;
			Ptr=Stack[top];
			Ptr=Ptr->rchild;//取栈顶点结点右子树
		}
	} while(top>0 || Ptr!=NULL);
}
main()
{
	BiTree T = NULL;/*最开始T指向空*/
	printf("需要创建和遍历的二叉树：\n");
	printf(" A\n");
	printf(" / \\\n");
	printf(" B E\n");
	printf(" / \\ \\\n");
	printf(" C D F\n");
	printf("Input some characters to create a binary tree\n");
	printf("（按先序序列建立）\n");
	printf("例如，ABC##D##E#F##↙，#表示空格,↙表示回车\n");
	CreatBiTree(&T);/*创建二叉树*/
	printf("The squence of preorder traversaling(先序遍历) binary tree\n");
	PreOrderTraverse(T);/*先序遍历二叉树*/
	printf("\nThe squence of inorder traversaling(中序遍历) binary tree\n");
	InOrderTraverse(T);/*中序遍历二叉树*/
	printf("\nThe squence of posorder traversaling(后序遍历) binary tree\n");
	PosOrderTraverse(T);/*后序遍历二叉树*/
	printf("\n深度优先非递归前序遍历二叉树\n");
	PreOrder_NR(T);
	getchar(); getchar();
}

6 队列（如果用数组模拟）

对于队列，如果用数组来模拟，用int front、rear来模拟队列的头部和尾部指针，则rear++;、front++可以理解为指针的移动，其代码实例可见上述第4节的内容。

－End－