信息学奥数NOIP数据结构ppt课件.ppt

《信息学奥数NOIP数据结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学奥数NOIP数据结构内容概要指针与数组链表树图指针int*p;实际存储的是目标的地址初始化NULL，空指针运算符取地址运算符“&”：返回变量所在的地址。一般用于变量。取值运算符“*”：返回地址对应的值，或用于改变指针所指内存空间的值。操作newdelete赋值**注意函数体内的new【指针与指针引用】数组一维数组intarray[n];int*array=newint[n];delete[]array;二维数组intmatrix[n][m];int**matrix=newint*[n];int*Array=newint[n*m];行优先：Array[x*

2、m+y]=matrix[x][y];列优先：Array[y*n+x]=matrix[x][y];多维数组三维数组intmatrix[n][m][k];int*Array=newint[n*m*k];行优先：Array[x*m*k+y*k+z]=matrix[x][y][z];多维数组同理链表包含数据体和指针循环链表双向链表structLinkedList{intdata;LinkedList*next;};452452254structDoubleLinkedList{intdata;LinkedList*next;LinkedList*pre;};链表操作查

3、找从表头扫到表尾，找到即停插入删除452452一个有趣的问题给一个链表，用O(1)的空间，问链表有没有环35345434树树是包含n(n>0)个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件：有且仅有一个结点K0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根(root)除K0外，K中的每个结点，对于关系N来说有且仅有一个前驱。K中各结点，对关系N来说可以有m个后继(m≥0)ABCDEFGHI树的基本概念结点（Node）：树中的元素，包含数据项及若干指向其子树的分支结点的度（Degree）：结点拥有的后继（或子树）数结点的层数：根节点到该节

4、点的距离+1，根为第一层叶子（Leaf）：度为零的结点，也称端结点孩子（Child）：结点的后继父节点（Parent）：节点的前驱兄弟（Sibling）：同一前驱的其他后继深度（Depth)：树中结点的最大层数森林（Forest）：M棵互不相交的树的集合ABCDEFGHI树的存储结构树的节点保存数据、子树指针、父指针可用数组模拟链表A^B^C^^^DE^^^F^^^G^^^H^^^I^^^typedefdoubleElementType;structTreeNode{ElementTypedata;TreeNode*parent;intdegree;TreeN

5、ode*children[MAX_DEG];//vectorchildren;};TreeNodetree[MAX_NODE];//RootVoidF(TreeNode*p){printf(“%d”,p->data);intI;for(i=0;idegree;i++)F(p->children[i]);}建树通常，题目会给出点数n，和n-1条边，但边可能没有方向性51213241512354structEdge{intnext,link;};Edgeedges[MAX_N*2];intnodesLink[MAX_N];voidad

6、dEdge(int*nodesLink,Edge*edge,int&edgeCount,constintx,constinty){edge[++edgeCount].next=nodesLink[x];nodesLink[x]=edgeCount;edge[edgeCount].link=y;}如果有方向性addEdge一次，无方向性addEdge两次。树的遍历先根遍历先遍历根，再依次遍历所有子树(ABEFCDGHI)后根遍历先遍历所有子树，再遍历根(EFBCGHIDA)分层遍历逐层扫描这棵树，一般用于宽度优先搜索(ABCDEFGHI)ABCDEFGHI//R

7、ootVoidF(TreeNode*p){intI;for(i=0;idegree;i++)F(p->children[i]);DP(p);}二叉树的定义与存储结构二叉树即所有节点的度均小于等于二的树二叉树子树有顺序，分为左子树和右子树二叉树的存储结构顺序存储利用数组存储，根节点下标为1，节点k的左孩子与右孩子下标分别为2k和2k+1，父节点下标为k/2取整链式存储同树的存储方式，也可用数组模拟链表ABCDEFGHIJ123456810111371291415structBinTreeNode{ElementTypedata;BinTreeNode*p

8、arent;BinTreeNode*l