怎么建网站详细步骤,wordpress解决速度慢,装饰工程施工组织设计,厦门网站建设有哪些公司第五章:树和二叉树
先序遍历二叉树的非递归算法。
void PreOrderTraverse(BiTree T, void (*Visit)(TElemType)) {//表示用于查找的函数的指针Stack S; BiTree p T;InitStack(S);//S模拟工作栈while (p || !StackEmpty(S)) {//S为空且下一个结点为空#xff0c;意味着结束遍…第五章:树和二叉树
先序遍历二叉树的非递归算法。
void PreOrderTraverse(BiTree T, void (*Visit)(TElemType)) {//表示用于查找的函数的指针Stack S; BiTree p T;InitStack(S);//S模拟工作栈while (p || !StackEmpty(S)) {//S为空且下一个结点为空意味着结束遍历if (p) {//p有值则Push进栈为一个工作进程Visit(p-data); Push(S, p); p p-lchild;//先序遍历先Visit} else {
//p为空则它的上级被Pop出去成为新的p再取右孩子。在下一个循环中如果它的上级没右孩子则说明它的上级是叶子结点或两端已经工作栈弹出了则再Pop出它的上级的上级此时它的上级已经无用工作栈弹出取它上级的兄弟结点Pop(S, p); p p-rchild;}}
}利用工作栈的思想过程十分复杂多多复习巩固加深 层序遍历二叉树
void LayerTraverse(BiTree T, void (*Visit)(TElemType)) {Queue Q; BiTree p;InitQueue(Q);EnQueue(Q, T);while (!QueueEmpty(Q)) {DeQueue(Q, p);
//每有一个父母结点出队列就把它的左右孩子放到队尾排队确保一层一层遍历if (p) {Visit(p-data);EnQueue(Q, p-lchild); EnQueue(Q, p-rchild);}}
}计算二叉树中每个结点的层次
void LevelRecur(BiTree T, int lev) {if (T) {lev;//准备遍历下一层cout T-data lev endl;LevelRecur(T-lchild, lev);LevelRecur(T-rchild, lev);//下一层启动}
}
void Level(BiTree T) {LevelRecur(T, 0);
}输出二叉树根结点到所有叶子结点的路径
void OutPath(BiTree T, Stack S) {//使用一个栈存储路径起到回溯的作用if (T) {Push(S, T);if (!T-lchild !T-rchild)PrintStack(S);//S栈中元素依次输出不取出OutPath(T-lchild, S);OutPath(T-rchild, S);Pop(S, T);//该节点左右孩子搜索完则出栈不再计入路径中}
}由扩展的先序序列即波兰式建立二叉树
void CreateBiTree(BiTree T) {// 读入扩展的先序序列假定数据元素为字符型#表示NULLchar ch; scanf(%c, ch);if (ch #) T NULL;else {T new BiTNode; T-data ch;CreateBiTree(T-lchild);//依次建立二叉树CreateBiTree(T-rchild);}
}先根遍历树孩子链表实现
void PreOrderRecur(CTree T, int loc, void (*Visit)(TElemType)) {if (loc -1) return;Visit(T.nodes[loc].data);//先查询根结点ChildPtr p;for (p T.nodes[loc].firstchild; p; p p-next) {PreOrderRecur(T, p-child, Visit);//取出下个孩子并查询}
}
void PreOrderTree(CTree T, void (*Visit)(TElemType)) {PreOrderRecur(T, T.root, Visit);
}计算树的深度孩子兄弟链表实现
int TreeDepth(CSTree T) {if (!T) return 0;//最简单情况遍历结束条件CSTree p; int maxh 0;//maxh为全局变量for (p T-firstchild; p; p p-nextsibling) {//到T的下一个孩子并且遍历其孩子的兄弟int h TreeDepth(p);//当前遍历结点的深度if (h maxh) maxh h;}return maxh 1;
}构造huffman树
typedef unsigned int WeightType;
typedef struct {TElemType data;WeightType weight; // 叶子权值的类型int parent, lchild, rchild; // 三叉静态链表
} HTNode, *HuffmanTree;
void CreateHuffmanTree(HuffmanTree HT, int n) {int m 2*n-1; // 最终将得到2n-1个结点HT new HTNode[m];for (i0; in; i) {cin HT[i].data HT[i].weight;HT[i].lchild HT[i].rchild HT[i].parent -1;//-1即示意为为null}//输入结点值for (in; im; i) {Select(HT, i-1, s1, s2); HT[s1].parentHT[s2].parenti;HT[i].weight HT[s1].weight HT[s2].weight;//两个结点的父母的权值为它们加和HT[i].lchilds1; HT[i].rchilds2; HT[i].parent -1;}
}const unsigned int MAX_WEIGHT UINT_MAX;
void Select(HuffmanTree HT, int s, int l, int r) {// 本函数的作用是从HT[0..s]中找到权值最小的两个结点WeightType WL MAX_WEIGHT, WR MAX_WEIGHT;for (i0; is; i) {if (HT[i].parent -1) {if (HT[i].weight WL) {WR WL; WL HT[i].weight; rl; li;} else if (HT[i].weight WR) {WR HT[i].weight; ri;}}}
}第六章图
深度优先遍历DFS
bool visited[MAX_VERTEX_NUM];
void DFS(Graph G, int v) {//类似于先根遍历Visit(v); visited[v] true;for (int wAdjVex(G, v); w ! -1; wAdjVex(G, v, w)) {if (!visited[w])DFS(G, w);}
}
void DFSTraverse(Graph G) {for (int v0; vG.vexnum; v)visited[v] false;//初始化visited表for (int v0; vG.vexnum; v)if (!visited[v])DFS(G, v);//如果没有查找到没遍历过的则弹出工作栈返回上一级
}
int AdjVex(MGraph G, int v, int w-1) {//邻接矩阵for (int jw1; jG.vexnum; j)if (G.arcs[v][j] ! INFINITY) return j;//找找它可能的出路return -1;
}int AdjVex(ALGraph G, int v, int w-1) {//邻接表ArcNode *p G.vertices[v].firstarc;if (w ! -1) {while (p p-adjvex ! w) p p-nextarc;if (p) p p-nextarc;}return p ? p-adjvex : -1;
}广度优先搜索BFS
bool visited[MAX_VERTEX_NUM];
void BFS(Graph G, int v) {//类似于层序遍历Visit(v); visited[v] true;Queue Q; InitQueue(Q); EnQueue(Q, v);while (!QueueEmpty(Q)) {DeQueue(Q, v);for (int wAdjVex(G, v); w ! -1; wAdjVex(G, v, w)) {if (!visited[w]) {Visit(w); visited[w] true; EnQueue(Q, w);}}}
}
void BFSTraverse(Graph G) {for (int v0; vG.vexnum; v)visited[v] false;//初始化for (int v0; vG.vexnum; v)if (!visited[v])BFS(G, v);
}利用DFS求简单路径
bool visited[MAX_VERTEX_NUM];
bool DFS_SimplePathRecur(Graph G, int vi, int vj, Stack S) {Push(S, vi); visited[vi] true;//S存储过往路径if (vi vj) {Print(S); return true;}for (int wAdjVex(G, vi); w ! -1; wAdjVex(G, vi, w)) {if (!visited[w]) {if (DFS_SimplePathRecur(G, w, vj, S))return true;}}Pop(S, vi); visited[vi] false; return false;
}
void DFS_SimplePath(Graph G, int vi, int vj) {Stack S; InitStack(S);for (int v0; vG.vexnum; v)visited[v] false;if (DFS_SimplePathRecur(G, vi, vj, S))cout Found a path endl;
}使用Prim算法得出最小生成树
void Prim(MGraph G, int v0) {// 用于存储F集合的两个数组邻接顶点和最小边int adjvex[MAX_VERTEX_NUM], lowcost[MAX_VERTEX_NUM];for (int j0; jG.vexnum; j) {if (j!v0) {adjvex[j] v0;lowcost[j] G.arcs[v0][j];}}lowcost[v0] INFINITY;for (int i0; iG.vexnum-1; i) { // 循环n-1次int k MinEdge(lowcost, G.vexnum);//该顶点的连接的最小边printf((%d, %d): %d\n, k, adjvex[k], lowcost[k]);lowcost[k] INFINITY;for (int j0; jG.vexnum; j) {if (G.arcs[k][j] lowcost[j]) {adjvex[j] k;lowcost[j] G.arcs[k][j];}}}
}得出拓扑排序
void TopologicalSort(ALGraph G) {//思路找头结点并删除它和它连接的路径继续下一个int InDegree[MAX_VERTEX_NUM];FindInDegree(G, InDegree);Stack S; InitStack(S);for (int i0; iG.vexnum; i)if (!InDegree[i]) Push(S, i);int count 0; // 统计输出顶点的个数while (!StackEmpty(S)) {int i; Pop(S, i); count;cout G.vertices[i].data endl; ArcNode *p;for (pG.vertices[i].firstarc; p; pp-nextarc) {k p-adjvex;if (!(--InDegree[k])) Push(S, k);}}if (countG.vexnum)cout The graph has loop endl;
}void FindInDegree(ALGraph G, int *InDegree) {for (int i0; iG.vexnum; i) InDegree[i] 0;for (int i0; iG.vexnum; i) {for (ArcNode *pG.vertices[i].firstarc; p; pp-nextarc) {InDegree[p-adjvex];}}
}第七章查找表
二分查找折半查找静态表
int Search_Bin(StaticSearchTable ST, KeyType key) {//其中ST为从小到大的顺序表int low1, highST.length;while (low high) {mid (low high) / 2;if (key ST.data[mid].key) return mid;else if (key ST.data[mid].key) high mid - 1;//取前一半else low mid 1;//取后一半}return 0;
}二叉查找树的查找方法递归算法
BiTree Search_BST(BiTree T, KeyType key) {//题外话对二叉查找树进行中序遍历可得到有序数列if (!T || key T-data.key)return T;else if (key T-data.key)//此时的左右孩子被赋予了更多意义return Search_BST(T-lchild, key);elsereturn Search_BST(T-rchild, key);
}二叉查找树的查找方法非递归算法
bool SearchBST(BiTree T, KeyType key, BiTree p, BiTree f) {// 若查找到key则返回true此时p指向等于key的// 结点f是p的双亲若p等于根结点则f为NULL// 若查找不到key则返回false此时p为NULLf// 指向查找过程中最后一个比较的结点f NULL; p T;while (p key ! p-data.key) {f p;//保存f则允许了回溯到父母结点的操作if (key p-data.key) p p-lchild;//向左走呢还是向右走呢else p p-rchild;}if (!p) return false;else return true;
}二叉查找树的插入
bool InsertBST(BiTree T, KeyType key) {BiTree p, f;bool found SearchBST(T, key, p, f);if (found) return false;//查找成功则不插入
//反之在查找失败的查找路径上最后一个结点的左或右插入BiTree t new BiTNode;t-data.key key; t-lchild t-rchild NULL;if (!f) T t;//如果二叉树为空则插入第一条数据else if (key f-data.key) f-lchild t;else f-rchild t;return true;
}二叉查找树的删除
bool DeleteBST(BiTree T, KeyType key) {BiTree p, f;bool found SearchBST(T, key, p, f);if (!found) return false;if (p-lchild p-rchild) {//有左右孩子的条件BiTree q p, t p-rchild;//将结点替代为右子树上最小的结点也可为左子树上最大的结点while (t-lchild) { q t; t t-lchild; }//一直向左子树查找找到“最左”的t即最小p-data t-data;//替代if (q ! p) q-lchild t-rchild;//q为t的双亲由于t无左子树则只需要将t的右子树接到q上即可完成交接t的转移。else q-rchild t-rchild; delete t;//如果p是t的双亲则直接插上} else {BiTree q p-lchild ? p-lchild : p-rchild;if (!f) T q;else if (p f-lchild) f-lchild q;else f-rchild q; delete p;}return true;
}写出判别一颗二叉树是否为二叉排序树的算法设二叉排序树中不存在关键字值相同的结点。
elemType arr[MAXN]; // 存放中序遍历结果
int k0; // 记录访问过的结点数
void Inorder_Traversal (TreeNode∗ T){if (!T) return;Inorder_Traversal (T−left);arr [k] T−val; // 记录结点值k;Inorder_Traversal (T−right, arr);
}bool Is_Binary_Sort_Tree(TreeNode∗ T){Inorder_Traversal (T); // 先中序遍历for (int i1; ik; i)if (arr [ i ] arr[i−1]) // 判断是否递增return false ;return true;
}
第八章排序
简单排序
void SelectSort(SqTable L) {for (int i1; iL.len; i) {int ji;for (int kL.len; ki; --k)if (L.r[k].key L.r[j].key) jk;if (i!j) {// 这里我们将L.r[i]和L.r[j]交换// 另一种做法是将L.r[i..j-1]各个后移一位然后令L.r[i]L.r[j]RcdType tmp L.r[i]; L.r[i] L.r[j]; L.r[j] tmp;}}
}冒泡排序
void BubbleSort(SqTable L) {bool change true;for (int in; i2 change; --i) {// 这里我们设置一个标记如果j从1到i-1循环中没有发生元素的互换// 说明整个序列已经是有序的了无需考虑更小的ichange false;for (int j1; ji-1; j) {if (L.r[j].key L.r[j1].key) {RcdType tmp L.r[j]; L.r[j] L.r[j1]; L.r[j1] tmp;change true;}}}
}插入排序
void InsertSortSub(SqTable L, int low, int high) {// 这个子函数对L.r[low..high]做简单插入排序for (int ilow1; ihigh; i)if (L.r[i].key L.r[i-1].key) {RcdType tmp L.r[i];for (int ji-1; tmp.key L.r[j].key jlow; --j)L.r[j1] L.r[j]; // 元素后移L.r[j1] tmp; // 插入到合适位置}
}
void InsertSort(SqTable L) {InsertSortSub(L, 1, L.len);
}希尔排序
void ShellSortSub(SqTable L, int dk) {// 一趟增量为dk的插入排序for (int idk1; iL.len; i) {if (L.r[i].key L.r[i-dk].key) {RcdType tmp L.r[i];for (int ji-dk; tmp.key L.r[j].key j1; j-dk)L.r[jdk] L.r[j];L.r[jdk] tmp;}}
}
void ShellSort(SqTable L, int delta[], int k) {// delta是每趟排序的增量值for (int i0; ik; i)ShellSortSub(L, delta[i]);
}快速排序
void QSort(SqTable L, int low, int high) {// 对L[low..high]进行快速排序if (low high) {int pivotloc Partition(L, low, high);QSort(L, low, pivotloc-1);QSort(L, pivotloc1, high);}
}
void QuickSort(SqTable L) {QSort(L, 1, L.len);
}
int Partition(SqTable L, int low, int high) {// 选择一个枢轴将L.r[low..high]分为两部分// 返回枢轴最后所在的位置以便进一步划分// 划分以后在枢轴之前之后的元素都小于大于或等于枢轴int pivotloc low; // 枢轴可以任意选取例如取第一个位置RcdType tmp L.r[pivotloc];KeyType pivotkey tmp.key;while (lowhigh) {while (lowhigh L.r[high].keypivotkey) --high;L.r[low] L.r[high];while (lowhigh L.r[low].keypivotkey) low;L.r[high] L.r[low];}L.r[low] tmp;return low;
}
堆排序
void HeapAdjust(SqTable L, int s, int m) {// 已知L.r[s..m]中除了L.r[s]以外都满足大顶堆的定义// 本函数通过调整使得L.r[s..m]成为一个大顶堆RcdType tmp L.r[s];for (int i2*s; im; i*2) { // 每次向下一层if (im L.r[i].keyL.r[i1].key) i;if (tmp.key L.r[i].key) break; // 已经找到合适的位置L.r[s] L.r[i]; s i; // 与孩子换位}L.r[s] tmp;
}
void HeapSort(SqTable L) {int i; RcdType tmp;for (iL.len/2; i0; --i)HeapAdjust(L, i, L.len); // 构造初始大顶堆for (iL.length; i1; --i) {tmp L.r[i];L.r[i] L.r[1];L.r[1] tmp; // 将最大的关键字放到L.r[i]HeapAdjust(L, 1, i-1); // 对L.r[1..i-1]调用筛选法重新调整为堆}
}归并排序
void Merge(RcdType* Rs, RcdType* Rt, int s, int m, int t) {// 已知Rs[s..m]和Rs[m1..t]都是有序表将它们归并存储到Rt[s..t]int i,j,k;for (is, jm1, ks; im jt; k) {//两表的排序在此处if (Rs[i].key Rs[j].key) Rt[k] Rs[i];else Rt[k] Rs[j];}for (; im; i, k) Rt[k] Rs[i];//当一个有序表取完时剩下直接安进去for (; jt; j, k) Rt[k] Rs[j];
}
void MSort(RcdType* Rs, RcdType* Rt, int low, int high) {//递归算法if (low high) {//lowhigh时无需归并int mid (lowhigh)/2;MSort(Rs, Rt, low, mid); MSort(Rs, Rt, mid1, high);Merge(Rs, Rt, low, mid, high);for (int ilow; ihigh; i) Rs[i] Rt[i];//将Rt复制到Rs上}
}
void MergeSort(SqTable L) {RcdType* tmp new RcdType[L.len1];MSort(L.r, tmp, 1, L.len);delete []tmp;
}基数排序
const int RADIX 128; // 每个“基本关键字”的取值范围称为基数
const int KEY_LENGTH 5; // 共有5个“基本关键字”
typedef char KeyType[KEY_LENGTH]; // 关键字类型为长度为5的字符串
void RadixPass(RcdType *R, RcdType *T, int n, int k) {int j; int count[RADIX];for (j0; jRADIX; j) count[j] 0;for (j1; jn; j) count[R[j].key[k]];for (j1; jRADIX; j) count[j] count[j-1] count[j];for (jn; j0; --j) {int p R[j].key[k]; T[count[p]] R[j]; count[p]--;}for (j1; jn; j) R[j] T[j];
}
void RadixSort(SqTable L) {RcdType *tmp new RcdType[L.len1];for (int k KEY_LENGTH-1; k0; --k)RadixPass(L.r, tmp, L.len, k);delete []tmp;
}ps对于C语言有以下便捷操作
提供sort函数一般用快速排序实现不稳定
提供stable_sort函数一般用归并排序实现稳定
提供priority_queue数据结构即堆 万字文章整理不易写了整整一天半点个赞权当支持一下
这是上一卷内容
数据结构经典算法总复习上卷-CSDN博客
加油诸位 文章转载自： http://www.morning.dcccl.cn.gov.cn.dcccl.cn http://www.morning.knqck.cn.gov.cn.knqck.cn http://www.morning.ntqgz.cn.gov.cn.ntqgz.cn http://www.morning.rykw.cn.gov.cn.rykw.cn http://www.morning.bqqzg.cn.gov.cn.bqqzg.cn http://www.morning.nkqxb.cn.gov.cn.nkqxb.cn http://www.morning.pymff.cn.gov.cn.pymff.cn http://www.morning.mwcqz.cn.gov.cn.mwcqz.cn http://www.morning.clbzy.cn.gov.cn.clbzy.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.dlgjdg.cn.gov.cn.dlgjdg.cn http://www.morning.lanyee.com.cn.gov.cn.lanyee.com.cn http://www.morning.qwwcf.cn.gov.cn.qwwcf.cn http://www.morning.fbrshjf.com.gov.cn.fbrshjf.com http://www.morning.srhqm.cn.gov.cn.srhqm.cn http://www.morning.ctbr.cn.gov.cn.ctbr.cn http://www.morning.wsyq.cn.gov.cn.wsyq.cn http://www.morning.zsleyuan.cn.gov.cn.zsleyuan.cn http://www.morning.cdrzw.cn.gov.cn.cdrzw.cn http://www.morning.xgbq.cn.gov.cn.xgbq.cn http://www.morning.kbdjn.cn.gov.cn.kbdjn.cn http://www.morning.bssjz.cn.gov.cn.bssjz.cn http://www.morning.hqgkx.cn.gov.cn.hqgkx.cn http://www.morning.kpxky.cn.gov.cn.kpxky.cn http://www.morning.bcngs.cn.gov.cn.bcngs.cn http://www.morning.dbphz.cn.gov.cn.dbphz.cn http://www.morning.fllfz.cn.gov.cn.fllfz.cn http://www.morning.lwwnq.cn.gov.cn.lwwnq.cn http://www.morning.kmcfw.cn.gov.cn.kmcfw.cn http://www.morning.nbsbn.cn.gov.cn.nbsbn.cn http://www.morning.rnzwh.cn.gov.cn.rnzwh.cn http://www.morning.nbsfb.cn.gov.cn.nbsfb.cn http://www.morning.plkrl.cn.gov.cn.plkrl.cn http://www.morning.gktds.cn.gov.cn.gktds.cn http://www.morning.rcrfz.cn.gov.cn.rcrfz.cn http://www.morning.gwyml.cn.gov.cn.gwyml.cn http://www.morning.mtdfn.cn.gov.cn.mtdfn.cn http://www.morning.xqxlb.cn.gov.cn.xqxlb.cn http://www.morning.mgwdp.cn.gov.cn.mgwdp.cn http://www.morning.sdecsd.cn.gov.cn.sdecsd.cn http://www.morning.uycvv.cn.gov.cn.uycvv.cn http://www.morning.hjrjy.cn.gov.cn.hjrjy.cn http://www.morning.hnmbq.cn.gov.cn.hnmbq.cn http://www.morning.ndnhf.cn.gov.cn.ndnhf.cn http://www.morning.nkwgy.cn.gov.cn.nkwgy.cn http://www.morning.dzgyr.cn.gov.cn.dzgyr.cn http://www.morning.zpstm.cn.gov.cn.zpstm.cn http://www.morning.lgmty.cn.gov.cn.lgmty.cn http://www.morning.wrcgy.cn.gov.cn.wrcgy.cn http://www.morning.xqkcs.cn.gov.cn.xqkcs.cn http://www.morning.gllhx.cn.gov.cn.gllhx.cn http://www.morning.pqcrz.cn.gov.cn.pqcrz.cn http://www.morning.fmtfj.cn.gov.cn.fmtfj.cn http://www.morning.rxdsq.cn.gov.cn.rxdsq.cn http://www.morning.mkrjf.cn.gov.cn.mkrjf.cn http://www.morning.zxqyd.cn.gov.cn.zxqyd.cn http://www.morning.gbnsq.cn.gov.cn.gbnsq.cn http://www.morning.lgmgn.cn.gov.cn.lgmgn.cn http://www.morning.mjgxl.cn.gov.cn.mjgxl.cn http://www.morning.qgjxy.cn.gov.cn.qgjxy.cn http://www.morning.kmqwp.cn.gov.cn.kmqwp.cn http://www.morning.blxor.com.gov.cn.blxor.com http://www.morning.rzrbw.cn.gov.cn.rzrbw.cn http://www.morning.pjwrl.cn.gov.cn.pjwrl.cn http://www.morning.jxtbr.cn.gov.cn.jxtbr.cn http://www.morning.trmpj.cn.gov.cn.trmpj.cn http://www.morning.qxdrw.cn.gov.cn.qxdrw.cn http://www.morning.rswtz.cn.gov.cn.rswtz.cn http://www.morning.mkhwx.cn.gov.cn.mkhwx.cn http://www.morning.zlnmm.cn.gov.cn.zlnmm.cn http://www.morning.qxmnf.cn.gov.cn.qxmnf.cn http://www.morning.gnkbf.cn.gov.cn.gnkbf.cn http://www.morning.ssjry.cn.gov.cn.ssjry.cn http://www.morning.rdlfk.cn.gov.cn.rdlfk.cn http://www.morning.wmqxt.cn.gov.cn.wmqxt.cn http://www.morning.krtky.cn.gov.cn.krtky.cn http://www.morning.kttbx.cn.gov.cn.kttbx.cn http://www.morning.qynpw.cn.gov.cn.qynpw.cn http://www.morning.gtcym.cn.gov.cn.gtcym.cn http://www.morning.sqskm.cn.gov.cn.sqskm.cn
