以下是为您整理出来关于【算法导论】合集内容，如果觉得还不错，请帮忙转发推荐。
1、概念二叉搜索树性质：设x是二叉搜索树的一个节点，那么：a) 对x左子树中任意节点y, y.key < x.keyb) 对x右子树种任意节点y, y.key >= x.key 2、数据结构 1struct TreeNode2{3 TreeNode(int key): left(NULL), right(NULL), parent(NULL), key(key) {};4 TreeNode* left;5 TreeNode* right;6 TreeNode* parent;7int key;8};910class Tree 11{ 12public: 13 Tree(): m_root(NULL) {}; 14 TreeNode* minimu...
设有n=2k个选手参加比赛，要求设计一个满足一下要求的比赛日程表:（1）每个选手必须与其他的n-1个选手个比赛一次；（2）每个选手每天只能赛一次 。 按此要求可以把比赛日程表设计成一个n行n-1列的二维表，其中第i行第j列表示第i个选手在 第j天比赛的选手。 代码：（分治策略） 1 #include<stdio.h>2 #include<math.h>3 4void gametable(int k)5{6int a[100][100];7int n,temp,i,j,p,t;8 n=2;//k=0两个参赛选手日程可以直接求得...
堆数据结构是一种数组对象，它可以被视为一颗完全二叉树，树中每个节点和数组中存放该节点值的那个元 素对应。如果表示堆的数组为A，那么树的根为A[1]。一、 堆1. 表示堆的数组A是一个具有两个属性的对象：length(A)是数组中的元素个数，heap-size(A)是存放在A中的堆的元素个数；A[heap-size(A)]之后的元素都不属于相应的堆。也就是：Heap-size(A)<=length(A)。2. 给定某个节点的下标i，其父节点PARENT(i)，左儿子LEFT(i)和右儿子R...
12.3-1 二叉搜索树insert操作的递归版本void insert1(Node* pRoot, Node* pAdd) {bool bLeft = pAdd->key < pRoot->key;Node* pNextRoot = bLeft ? pRoot->left : pRoot->right;if(pNextRoot)insert1(pNextRoot, pAdd);else{pAdd->parent = pRoot;if(bLeft)pRoot->left = pAdd;elsepRoot->right = pAdd;} } 12.3-2 insert过程途经n个节点后遇到了空节点，便将待插入的元素安放上去了，接下来的search过程先路过同样的n个节点，最后...
题目：对于一棵有N个结点的树，设计在O(N)时间内完成的先序、中序与后序遍历算法 一、先序遍历递归实现：void InOrder( SearchTree T ) {if ( T != NULL ){Visit( T );InOrder( T->Left );InOrder( T->Right );} }非递归实现：版本一：栈模拟（深度优先搜索）void PreOrder( SearchTree T ) {Stack S;while( T != NULL || !S.Empty() ){if ( T != NULL ){S.push( T );Visit( T );T = T->Left; }else{T = S.pop();T = T->Right;}} ...
原文请参考：http://www.cnblogs.com/Anker/archive/2013/01/22/2872261.html本章介绍了算法分析中的渐进分析符号，几个重要渐进记号的定义如下：Θ(g(n))={ f(n): 存在正常数c1,c2和n0，使对所有的n>=n0，有0<=c1g(n)<=f(n)<=c2g(n) }O(g(n))={ f(n): 存在正常数c和n0，使对所有n>=n0，有0<=f(n)<=cg(n) }Ω(g(n))={ f(n): 存在正常数c和n0，使对所有n>=n0，有0<=cg(n)<=f(n) }o(g(n))={ f(n): 对任意正常数c，存在常数n0>0，使对...
斐波拉契堆是由一组最小堆有序树组成，每棵树遵循最小堆性质，并且每棵树都是有根而无序的。所有树的根通过left和right指针来形成一个环形的双链表，称为该堆的根表。 对于一个给定的斐波拉契堆H ，可以通过指向包含最小关键字的树根指针H.min来访问。堆中每个节点还包含x.mark,x.degree两个域，x.degree表示x的子女表中的子女个数；x.mark表示从x上次成为另一个节点子女以来是否失掉一个孩子。斐波拉契对的结构如下：势能函数：...
主定理常用于计算递推式的时间复杂度。 原文：http://www.cnblogs.com/jdflyfly/p/3954637.html
第一章~第二章：1. 几种常见的排序方法1.1 插入排序#!/usr/bin/env python# -*- coding:UTF-8 -*-‘‘‘CLRS p10‘‘‘ def insertion_sort(A): for j in range(1,len(A),1): key = A[j] i = j-1 while i >= 0 and A[i] > key: A[i+1] = A[i] i = i-1 A[i+1] = key if __name__ == ‘__main__‘: A = [9,3,5,2,3,5,7,8,9,1] insertion_sort(A) 1.2 选择排序#!/usr/bi...
散列表直接寻址表 一个数组T[0..m-1]中的每个位置分别对应全域U中的一个关键字，槽k指向集合中一个关键字为k的元素，如果该集合中没有关键字为k的元素，则T[k] = NIL全域U={0,1,…,9}中的每个关键字都对应于表中的一个下标值，由实际关键字构成的集合K={2,3,5,8}决定表中的一些槽，这些槽包含指向元素的指针，而另一些槽包含NIL 直接寻址的技术缺点非常明显：如果全域U很大，则在一台标准的计算机可用内存...