數(shù)據(jù)存儲(chǔ)到內(nèi)存對(duì)于強(qiáng)類型的C++來說，有四個(gè)屬性：

地址、類型、尺寸、值；

普通變量名稱顯式表示的是其值，可通過取值運(yùn)算符“&”取得其地址；

如果一個(gè)變量的值保存的是某一塊內(nèi)存的首地址，這樣的變量稱為指針變量，其顯式表示的是地址，可通過解引用運(yùn)算符“*”來引用其值。

如果一個(gè)變量聲明時(shí)類似指針變量、使用時(shí)類似普通變量，這樣的變量在C++中稱為引用，是一個(gè)由編譯器實(shí)現(xiàn)了自動(dòng)解引用的指針常量。

理解指針的關(guān)鍵在于各種數(shù)據(jù)結(jié)構(gòu)中對(duì)于指針移動(dòng)的理解。指針的移動(dòng)的實(shí)質(zhì)就是通過一個(gè)合法的指針變量的算術(shù)運(yùn)算，來更新地址的值，這樣指針變量有了新的值，也就是相當(dāng)于指針發(fā)生了移動(dòng)。當(dāng)指針變量做左值時(shí)，賦值符號(hào)可以理解為指針的指向或移動(dòng)：

p = head; // p指向（移動(dòng)到）head

p = p->next; // p指向（移動(dòng)到）p指向的下一個(gè)元素

1 順序表

對(duì)于數(shù)組，數(shù)組名指向內(nèi)存塊的首地址，下標(biāo)相當(dāng)于是首地址的偏移量，所以下標(biāo)的++、--運(yùn)算其與整數(shù)的算術(shù)運(yùn)算可以理解為地址的移動(dòng)：

	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 鏈表

鏈表是通過節(jié)點(diǎn)的指針域來實(shí)現(xiàn)節(jié)點(diǎn)之間的聯(lián)系：

pRead=pRead->next;表示指針pRead指向其指向的下一個(gè)元素：

void Showlist(node *head)
{
	node *pRead=head;			//訪問指針一開始指向表頭
	cout<<"鏈表中的數(shù)據(jù)為：" <<endl;
	while (pRead!=NULL)			//當(dāng)訪問指針存在時(shí)（即沒有達(dá)到表尾之后）
	{
		cout<<pRead->data;		//輸出當(dāng)前訪問結(jié)點(diǎn)的數(shù)據(jù)
		pRead=pRead->next;		//訪問指針向后移動(dòng)（指針偏移）
	}
	cout<<endl;
}

3 二叉樹（如果用數(shù)組模擬）

堆是一棵完全二叉樹，可以用數(shù)組模擬，樹的上、下兩層的下標(biāo)有*2或/2的關(guān)系

#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一般取最后一個(gè)元素的下標(biāo)
{
	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;//向上移動(dòng)
		}
		else
		{
			//break;
		}
	}
}
void insertHeap(LPHEAP heap, int data) //放到當(dāng)前堆的最后面并按條件往上移
{
	++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 二叉樹（如果用鏈表實(shí)現(xiàn)）

用鏈表實(shí)現(xiàn)的二叉樹，其節(jié)點(diǎn)的下移可以用諸如p = p->left;的表達(dá)式實(shí)現(xiàn)：

#include "stdio.h"
#include <iostream>
#include <queue>
using namespace std;
typedef struct BiTNode{
 char data;							/*結(jié)點(diǎn)的數(shù)據(jù)域*/
 struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/
} BiTNode , *BiTree;
void CreatBiTree(BiTree *T){						/*按先序遍歷的思想創(chuàng)建一棵二叉樹*/
 char c;
 scanf("%c",&c);
 if(c == ' ') *T = NULL;
 else{
 *T = (BiTNode * )malloc(sizeof(BiTNode)); /*創(chuàng)建根結(jié)點(diǎn)*/
 (*T)->data = c;								/*向根結(jié)點(diǎn)中輸入數(shù)據(jù)*/
 CreatBiTree(&((*T)->lchild));				/*遞歸地創(chuàng)建左子樹*/
 CreatBiTree(&((*T)->rchild));				/*遞歸地創(chuàng)建右子樹*/
 }
}
void PreOrderTraverse(BiTree T ){		/*先序遍歷二叉樹*/
 if(T){								/*遞歸結(jié)束條件，T為空*/
 printf("%3c",T->data);			/*訪問根結(jié)點(diǎn),將根結(jié)點(diǎn)內(nèi)容輸出*/
 PreOrderTraverse(T->lchild);	/*先序遍歷T的左子樹*/
 PreOrderTraverse(T->rchild);	/*先序遍歷T的右子數(shù)*/
 }
}
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;					/*將根結(jié)點(diǎn)的指針（地址）入隊(duì)列*/
 front = -1;
 rear = 0;
 while(front<rear)				/*當(dāng)隊(duì)列不為空時(shí)進(jìn)入循環(huán)*/
 {
 p = queue[++front];		/*取出隊(duì)頭元素*/
 visit(p); 				/*訪問p指向的結(jié)點(diǎn)元素*/
 if(p->lchild!=NULL)		/*將p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針入隊(duì)列*/
 queue[++rear] = p->lchild;
 if(p->rchild!=NULL)		/*將p結(jié)點(diǎn)的右孩子結(jié)點(diǎn)指針入隊(duì)列*/
 queue[++rear] = p->rchild;
 }
 }
}
void layerOrderTraverse2(BiTree T)	//按層遍歷，使用queue
{
	BiTree p;
	queue <BiTree> q;
	if(T!=NULL)
	{
		q.push(T);					/*將根結(jié)點(diǎn)的指針（地址）入隊(duì)列*/
		while(! q.empty())			/*當(dāng)隊(duì)列不為空時(shí)進(jìn)入循環(huán)*/
		{
 p = q.front();		
			q.pop();				/*取出隊(duì)頭元素*/
 visit(p); 				/*訪問p指向的結(jié)點(diǎn)元素*/
 if(p->lchild!=NULL)		/*將p結(jié)點(diǎn)的左孩子結(jié)點(diǎn)指針入隊(duì)列*/
 q.push(p->lchild);
 if(p->rchild!=NULL)		/*將p結(jié)點(diǎn)的右孩子結(jié)點(diǎn)指針入隊(duì)列*/
 q.push(p->rchild);
		}
	}
}
main()
{
 BiTree T = NULL; /*最開始T指向空*/
 printf("需要?jiǎng)?chuàng)建和遍歷的二叉樹：\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); /*創(chuàng)建二叉樹*/
 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 棧（如果用數(shù)組模擬）

如果用一個(gè)整數(shù)來模擬棧頂指針：int top=0;則其++、--的操作便相當(dāng)于是指針的移動(dòng)。

#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef struct BiTNode{
	char data;/*結(jié)點(diǎn)的數(shù)據(jù)域*/
	struct BiTNode *lchild , *rchild;/*指向左孩子和右孩子*/
} BiTNode , *BiTree;
void CreatBiTree(BiTree *T){/*按先序序列創(chuàng)建一棵二叉樹*/
	char c;
	scanf("%c",&c);
	if(c == ' ') *T = NULL;
	else{
		*T = (BiTNode * )malloc(sizeof(BiTNode));/*創(chuàng)建根結(jié)點(diǎn)*/
		(*T)->data = c;/*向根結(jié)點(diǎn)中輸入數(shù)據(jù)*/
		CreatBiTree(&((*T)->lchild));/*遞歸地創(chuàng)建左子樹*/
		CreatBiTree(&((*T)->rchild));/*遞歸地創(chuàng)建右子樹*/
	}
}
void PreOrderTraverse(BiTree T ){/*先序遍歷二叉樹*/
	if(T){/*遞歸結(jié)束條件，T為空*/
		printf("%3c",T->data);/*訪問根結(jié)點(diǎn),將根結(jié)點(diǎn)內(nèi)容輸出*/
		PreOrderTraverse(T->lchild);/*先序遍歷T的左子樹*/
		PreOrderTraverse(T->rchild);/*先序遍歷T的右子數(shù)*/
	}
}
void InOrderTraverse(BiTree T){/*中序遍歷二叉樹*/
	if(T){/*如果二叉樹為空，遞歸遍歷結(jié)束*/
		InOrderTraverse(T->lchild);/*中序遍歷T的左子樹*/
		printf("%3c",T->data);/*訪問根結(jié)點(diǎn)*/
		InOrderTraverse(T->rchild);/*中序遍歷T的右子數(shù)*/
	}
}
void PosOrderTraverse(BiTree T){/*后序遍歷二叉樹*/
	if(T){/*如果二叉樹為空，遞歸遍歷結(jié)束*/
		PosOrderTraverse(T->lchild);/*后序遍歷T的左子樹*/
		PosOrderTraverse(T->rchild);/*后序遍歷T的右子數(shù)*/
		printf("%3c",T->data);/*訪問根結(jié)點(diǎn)*/
	}
}
void PreOrder_NR(BiTree T)//深度優(yōu)先非遞歸前序遍歷
{
	BiTree Ptr;
	BiTree Stack[MAX];//棧定義
	int top=0;//棧頂指針
	Ptr = T;
	do
	{
		while(Ptr!=NULL)//樹結(jié)點(diǎn)非空，遍歷其左子樹
		{
			printf("%3c",Ptr->data);//操作結(jié)點(diǎn)
			Stack[top]=Ptr;//樹結(jié)點(diǎn)進(jìn)棧
			top++;
			Ptr=Ptr->lchild;//查看左子樹
		}
		if(top>0)//棧非空，出棧
		{
			top--;
			Ptr=Stack[top];
			Ptr=Ptr->rchild;//取棧頂點(diǎn)結(jié)點(diǎn)右子樹
		}
	} while(top>0 || Ptr!=NULL);
}
main()
{
	BiTree T = NULL;/*最開始T指向空*/
	printf("需要?jiǎng)?chuàng)建和遍歷的二叉樹：\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);/*創(chuàng)建二叉樹*/
	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深度優(yōu)先非遞歸前序遍歷二叉樹\n");
	PreOrder_NR(T);
	getchar(); getchar();
}

6 隊(duì)列（如果用數(shù)組模擬）

對(duì)于隊(duì)列，如果用數(shù)組來模擬，用int front、rear來模擬隊(duì)列的頭部和尾部指針，則rear++;、front++可以理解為指針的移動(dòng)，其代碼實(shí)例可見上述第4節(jié)的內(nèi)容。

－End－