欢迎大家来到IT世界,在知识的湖畔探索吧!
数据存储到内存对于强类型的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)<<" ";
欢迎大家来到IT世界,在知识的湖畔探索吧!
2 链表
链表是通过节点的指针域来实现节点之间的联系：
pRead=pRead->next;表示指针pRead指向其指向的下一个元素：
欢迎大家来到IT世界,在知识的湖畔探索吧!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;的表达式实现：
欢迎大家来到IT世界,在知识的湖畔探索吧!#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－
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/30352.html
