**Kruskal算法**是求图最小生成树的一种算法，另外一种是[Prim算法](http://blog.csdn.net/u012796139/article/details/49865361)。    **Kruskal算法思想**：Kruskal算法按照边的权重(从大到小)处理它们，将边加入最小生成树中，加入的边不会对已经加入的边构成环，直到树中含有V-1条边为止。 **源代码**示例： ~~~ #include #include #include #include #include using namespace std; class Edge { public: Edge(size_t _v, size_t _w, double _weight) : v(_v), w(_w), weight(_weight) {} double getWeight() const { return weight; } size_t either() const { return v; } size_t other(size_t v) const { if (v == this->v) return this->w; else if (v == this->w) return this->v; else { cout << "error in Edge::other()" << endl; exit(1); } } void print() const{ cout << "(" << v << ", " << w << ", " << weight << ") "; } private: size_t v, w; // 两个顶点 double weight; // 权重 }; /// 加权无向图 class EdgeWeithtedGraph { public: EdgeWeithtedGraph(size_t vertax_nums) : vertaxs(vertax_nums), edges(0), arr(vertax_nums) {} void addEdge(const Edge e); vector adj(size_t v) const { return v < arrSize() ? arr[v] : vector(); } vector allEdges() const; // 返回加权无向图的所有边 size_t arrSize() const { return arr.size(); } size_t vertax() const { return vertaxs; } size_t edge() const { return edges; } void printVertax(size_t v) const; void printGraph() const; private: size_t vertaxs; // 顶点个数 size_t edges; // 边的个数 vector> arr; // 邻接表 }; /// 无向图数据结构，用于测试Kruskal算法中的边是否能构成环 class Graph { public: Graph(size_t n) : arr(n), edges(0), vertaxs(n) {} void addEdge(size_t a, size_t b) { if (!(a < arr.size() && b < arr.size())) return; arr[a].push_back(b); arr[b].push_back(a); edges++; } vector adj(size_t n) const { if (n < arr.size()) return arr[n]; else return vector(); } /// 返回顶点个数 size_t vertax() const { return arr.size(); } private: vector> arr; // 邻接表 size_t edges; // 边的个数 size_t vertaxs; // 顶点个数 }; /// 使用深度优先遍历判断Graph是否是无环图 class Cycle { public: Cycle(const Graph &graph) : marked(graph.vertax()), has_cycle(false) { for (size_t i = 0; i < graph.vertax(); i++) marked[i] = false; for (size_t i = 0; i < graph.vertax(); i++) { if (!marked[i]) dfs(graph, i, i); } } bool hasCycle() const { return has_cycle; } private: void dfs(const Graph &graph, size_t v, size_t u) { marked[v] = true; vector vec = graph.adj(v); for (size_t i = 0; i < vec.size(); i++) { if (!marked[vec[i]]) dfs(graph, vec[i], v); else if (vec[i] != u) // 无环图其实就是树，此时v是树中一个节点，其父节点为u，当marked[vec[i]]==true时，表示v的父节点一定为u，否则图中有环 has_cycle = true; } } vector marked; bool has_cycle; }; /// 判断最小生成树中是否有环，在Kruskal算法算法中被调用 bool hasCycle(vector vec, size_t nvextax) { if (vec.size() == 0) return false; Graph graph(nvextax); for (size_t i = 0; i < vec.size(); i++) { size_t v = vec[i].either(); size_t w = vec[i].other(v); graph.addEdge(v, w); } Cycle cycle(graph); return cycle.hasCycle(); } /// 为了存放Kruskal算法过程中的边，这些边按照权值从小到大排列 template struct greator { bool operator()(const T &x, const T &y) { return x.getWeight() < y.getWeight(); } }; /// 最小生成树的Kruskal算法 class KruskalMST { public: KruskalMST(const EdgeWeithtedGraph &graph) { set> pq; // 计算过程保存边的set vector vec = graph.allEdges(); set::iterator miniter; for (size_t i = 0; i < vec.size(); i++) // 将所有的边存到pq中 pq.insert(vec[i]); while (!pq.empty() && mst.size() < graph.arrSize() - 1) // graph.arrSize()可替换为变量 { miniter = pq.begin(); mst.push_back(*miniter); if (hasCycle(mst, graph.arrSize())) removeEdge(*miniter); pq.erase(miniter); } } vector edges() const { return mst; } void printEdges() const { for (size_t i = 0; i < mst.size(); i++) { mst[i].print(); } cout << endl; } private: void removeEdge(Edge e) { size_t v = e.either(); size_t w = e.other(v); for (size_t i = 0; i < mst.size(); i++) { size_t iv = mst[i].either(); size_t iw = mst[i].other(iv); if (v == iv && w == iw) { mst.erase(mst.begin() + i); return; } } } vector mst; }; int main(void) { EdgeWeithtedGraph graph(8); graph.addEdge(Edge(0, 7, 0.16)); graph.addEdge(Edge(0, 2, 0.26)); graph.addEdge(Edge(0, 4, 0.38)); graph.addEdge(Edge(0, 6, 0.58)); graph.addEdge(Edge(1, 7, 0.19)); graph.addEdge(Edge(5, 7, 0.28)); graph.addEdge(Edge(2, 7, 0.34)); graph.addEdge(Edge(4, 7, 0.37)); graph.addEdge(Edge(1, 3, 0.29)); graph.addEdge(Edge(1, 5, 0.32)); graph.addEdge(Edge(1, 2, 0.36)); graph.addEdge(Edge(2, 3, 0.17)); graph.addEdge(Edge(6, 2, 0.40)); graph.addEdge(Edge(3, 6, 0.52)); graph.addEdge(Edge(4, 5, 0.35)); graph.addEdge(Edge(6, 4, 0.93)); cout << "arrSize: " << graph.arrSize() << endl; cout << "vertax: " << graph.vertax() << endl; cout << "edge: " << graph.edge() << endl; cout << "----------------" << endl; graph.printGraph(); cout << endl; // 输出无向图的所有边 vector vec = graph.allEdges(); for (size_t i = 0; i < vec.size(); i++) vec[i].print(); cout << endl << endl; // Kruskal算法 KruskalMST prim(graph); prim.printEdges(); system("pause"); return 0; } void EdgeWeithtedGraph::addEdge(const Edge e) { size_t v = e.either(); size_t w = e.other(v); if (!(v < arrSize() && w < arrSize())) return; arr[v].push_back(e); arr[w].push_back(e); this->edges++; } vector EdgeWeithtedGraph::allEdges() const { vector vec; for (size_t i = 0; i < arrSize(); i++) { for (size_t j = 0; j < arr[i].size(); j++) { if (arr[i][j].other(i) > i) // 所有边的权重各不不同，可以这样判断，每个边只保留一个 vec.push_back(arr[i][j]); } } return vec; } void EdgeWeithtedGraph::printVertax(size_t v) const { if (v >= arrSize()) return; for (size_t i = 0; i < arr[v].size(); i++) arr[v][i].print(); cout << endl; } void EdgeWeithtedGraph::printGraph() const { for (size_t i = 0; i < arrSize(); i++) { cout << i << ": "; printVertax(i); } } ~~~ **参考资料**：      1、[https://github.com/luoxn28/algorithm_data_structure](https://github.com/luoxn28/algorithm_data_structure) （里面有常用的数据结构源代码，图相关算法在graph文件夹中）      2、《算法 第4版》 图的Prim算法章节      3、[Prim算法](http://blog.csdn.net/u012796139/article/details/49865361)

      **Prim算法**是求图(无向图)中最小生成树的一种算法，另外一种是**Kruskal算法**。     **Prim算法思想**：Prim算法的每一步都会为一棵生长中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入树中。  **源代码**示例： ~~~ #include #include #include #include #include using namespace std; class Edge { public: Edge(size_t _v, size_t _w, double _weight) : v(_v), w(_w), weight(_weight) {} double getWeight() const { return weight; } size_t either() const { return v; } size_t other(size_t v) const { if (v == this->v) return this->w; else if (v == this->w) return this->v; else { cout << "error in Edge::other()" << endl; exit(1); } } void print() const{ cout << "(" << v << ", " << w << ", " << weight << ") "; } private: size_t v, w; // 两个顶点 double weight; // 权重 }; class EdgeWeithtedGraph { public: EdgeWeithtedGraph(size_t vertax_nums) : vertaxs(vertax_nums), edges(0), arr(vertax_nums) {} void addEdge(const Edge e); vector adj(size_t v) const { return v < arrSize() ? arr[v] : vector(); } vector allEdges() const; // 返回加权无向图的所有边 size_t arrSize() const { return arr.size(); } size_t vertax() const { return vertaxs; } size_t edge() const { return edges; } void printVertax(size_t v) const; void printGraph() const; private: size_t vertaxs; // 顶点个数 size_t edges; // 边的个数 vector> arr; // 邻接表 }; /// 为了存放Prim算法过程中的边，这些边按照权值从小到大排列 template struct greator { bool operator()(const T &x, const T &y) { return x.getWeight() < y.getWeight(); } }; /// 最小生成树的Prim算法的延时实现 class LazyPrimMST { public: LazyPrimMST(const EdgeWeithtedGraph &graph) : marked(graph.arrSize()) { if (graph.arrSize() == 0) // 防止为空图 return; for (size_t i = 0; i < marked.size(); i++) marked[i] = false; visit(graph, 0); set::iterator miniter; while (!pq.empty()) { miniter = pq.begin(); size_t v = miniter->either(); size_t w = miniter->other(v); if (marked[v] && marked[w]) { pq.erase(miniter); continue; } mst.push_back(*miniter); pq.erase(miniter); if (!marked[v]) visit(graph, v); if (!marked[w]) visit(graph, w); } } vector edges() const { return mst; } void printEdges() const { for (size_t i = 0; i < mst.size(); i++) { mst[i].print(); } cout << endl; } private: void visit(const EdgeWeithtedGraph &graph, size_t v) { marked[v] = true; vector vec = graph.adj(v); for (size_t i = 0; i < vec.size(); i++) { if (!marked[vec[i].other(v)]) pq.insert(vec[i]); } } vector marked; vector mst; // 最小生成树的边 set> pq; // 计算过程保存边的set }; int main(void) { EdgeWeithtedGraph graph(8); graph.addEdge(Edge(0, 7, 0.16)); graph.addEdge(Edge(0, 2, 0.26)); graph.addEdge(Edge(0, 4, 0.38)); graph.addEdge(Edge(0, 6, 0.58)); graph.addEdge(Edge(1, 7, 0.19)); graph.addEdge(Edge(5, 7, 0.28)); graph.addEdge(Edge(2, 7, 0.34)); graph.addEdge(Edge(4, 7, 0.37)); graph.addEdge(Edge(1, 3, 0.29)); graph.addEdge(Edge(1, 5, 0.32)); graph.addEdge(Edge(1, 2, 0.36)); graph.addEdge(Edge(2, 3, 0.17)); graph.addEdge(Edge(6, 2, 0.40)); graph.addEdge(Edge(3, 6, 0.52)); graph.addEdge(Edge(4, 5, 0.35)); graph.addEdge(Edge(6, 4, 0.93)); cout << "arrSize: " << graph.arrSize() << endl; cout << "vertax: " << graph.vertax() << endl; cout << "edge: " << graph.edge() << endl; cout << "----------------" << endl; graph.printGraph(); cout << endl; // 输出无向图的所有边 vector vec = graph.allEdges(); for (size_t i = 0; i < vec.size(); i++) vec[i].print(); cout << endl << endl; // prim算法 LazyPrimMST prim(graph); prim.printEdges(); system("pause"); return 0; } void EdgeWeithtedGraph::addEdge(const Edge e) { size_t v = e.either(); size_t w = e.other(v); if (!(v < arrSize() && w < arrSize())) return; arr[v].push_back(e); arr[w].push_back(e); this->edges++; } vector EdgeWeithtedGraph::allEdges() const { vector vec; for (size_t i = 0; i < arrSize(); i++) { for (size_t j = 0; j < arr[i].size(); j++) { if (arr[i][j].other(i) > i) // 所有边的权重各不不同，可以这样判断，每个边只保留一个 vec.push_back(arr[i][j]); } } return vec; } void EdgeWeithtedGraph::printVertax(size_t v) const { if (v >= arrSize()) return; for (size_t i = 0; i < arr[v].size(); i++) arr[v][i].print(); cout << endl; } void EdgeWeithtedGraph::printGraph() const { for (size_t i = 0; i < arrSize(); i++) { cout << i << ": "; printVertax(i); } } ~~~ **参考资料**：       1、[https://github.com/luoxn28/algorithm_data_structure](https://github.com/luoxn28/algorithm_data_structure) （里面有常用的数据结构源代码，图相关算法在graph文件夹中）       2、《算法 第4版》 图的Prim算法章节

      对一个**有向无环图**(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为**拓扑排序**。(摘抄自：[拓扑排序-百度百科](http://baike.baidu.com/link?url=LQa-nm5WHvlG9AFeR27hZOvYN3HCyfgyLZiVFzh6TfULibSs3QGawKSwR5_dzy58dN7fx6H56zGyfoGA57Z2fq))。       首先对于一个优先图需要先判断是否存在环，然后再进行拓扑排序操作。如何判断有向图是否存在环呢，参考：[有向图是否有环](http://blog.csdn.net/u012796139/article/details/49863539)。  **源代码**示例： ~~~ #include #include #include #include using namespace std; class Digraph { public: Digraph(size_t nvertax) : arr(nvertax), vertaxs(nvertax), edges(0) {} void addEdge(size_t a, size_t b); void removeEdge(size_t a, size_t b); void addVertax(size_t v); void removeVertax(size_t v); Digraph reverse() const; vector adj(size_t v) const; void showAdj(size_t v) const; void showDigraph() const; size_t edge() const { return edges; } size_t vertax() const { return vertaxs; } size_t arrSize() const { return arr.size(); } private: vector> arr; // 邻接表 size_t vertaxs; // 顶点个数 size_t edges; // 边的个数 }; /// 使用深度优先遍历在有向图中寻找有向环 class DirectedCycle { public: DirectedCycle(const Digraph &graph) : marked(graph.arrSize()), edgeto(graph.arrSize()), on_stack(graph.arrSize()) { for (size_t i = 0; i < graph.arrSize(); i++) marked[i] = on_stack[i] = false; for (size_t i = 0; i < graph.arrSize(); i++) { if (!marked[i]) dfs(graph, i); } } bool hasCycle() const { return !sta.empty(); } stack cycle() const { return sta; } private: void dfs(const Digraph &graph, size_t v) { on_stack[v] = true; marked[v] = true; vector vec = graph.adj(v); for (size_t i = 0; i < vec.size(); i++) { if (this->hasCycle()) return; else if (!marked[vec[i]]) { edgeto[vec[i]] = v; dfs(graph, vec[i]); } else if (on_stack[vec[i]]) { for (size_t x = v; x != vec[i]; x = edgeto[x]) sta.push(x); sta.push(vec[i]); sta.push(v); } } on_stack[v] = false; } vector marked; vector edgeto; vector on_stack; stack sta; }; /// 有向图中基于深度优先遍历的顶点排序，保证图中没有有向环 class DepthFirstOrder { public: DepthFirstOrder(const Digraph &graph) : marked(graph.arrSize()) { for (size_t i = 0; i < marked.size(); i++) marked[i] = false; for (size_t i = 0; i < graph.arrSize(); i++) { if (!marked[i]) dfs(graph, i); } } vector getPre() const { return pre; } vector getPost() const { return post; } stack getReversePost() const { return reverse_post; } private: void dfs(const Digraph &graph, size_t v) { marked[v] = true; pre.push_back(v); vector vec = graph.adj(v); for (size_t i = 0; i < vec.size(); i++) { if (!marked[vec[i]]) dfs(graph, vec[i]); } post.push_back(v); reverse_post.push(v); } vector marked; vector pre; // 所有顶点的前序排列 vector post; // 所有顶点的后序排列 stack reverse_post; // 所有顶点的逆后序排列 }; /// 拓扑排序，借助于DepthFirstOrder来实现,保证图中没有环 class Topological { public: Topological(const Digraph &graph) { DepthFirstOrder dfs(graph); stack sta = dfs.getReversePost(); while (!sta.empty()) { order.push_back(sta.top()); sta.pop(); } } vector getOrder() const { return order; } private: vector order; // 顶点的拓扑顺序 }; int main(void) { Digraph graph(13); graph.addEdge(0, 1); graph.addEdge(0, 5); graph.addEdge(0, 6); graph.addEdge(2, 0); graph.addEdge(2, 3); graph.addEdge(3, 5); graph.addEdge(5, 4); graph.addEdge(6, 4); graph.addEdge(6, 9); graph.addEdge(7, 6); graph.addEdge(8, 7); graph.addEdge(9, 10); graph.addEdge(9, 11); graph.addEdge(9, 12); graph.addEdge(11, 12); cout << graph.vertax() << endl; cout << graph.edge() << endl; graph.showDigraph(); cout << endl; DirectedCycle cycle(graph); stack sta; if (cycle.hasCycle()) { cout << "graph has cycle" << endl; sta = cycle.cycle(); while (!sta.empty()) { cout << sta.top() << " "; sta.pop(); } cout << endl; } else cout << "graph hasn't cycle" << endl; Topological topo(graph); vector vec = topo.getOrder(); for (size_t i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << endl; system("pause"); return 0; } void Digraph::addEdge(size_t a, size_t b) { if (!(a < vertax() && b < vertax())) return; arr[a].push_back(b); edges++; } void Digraph::removeEdge(size_t a, size_t b) { if (!(a < vertax() && b < vertax())) return; vector::iterator iter = find(arr[a].begin(), arr[a].end(), b); if (iter != arr[a].end()) { arr[a].erase(iter); edges--; } } void Digraph::addVertax(size_t v) { if (v != arrSize()) return; arr.push_back(vector()); vertaxs++; } void Digraph::removeVertax(size_t v) { if (v >= arrSize()) return; vector::iterator iter; for (size_t i = 0; i < arrSize(); i++) { if (i == v) { edges -= arr[i].size(); // 减去头部是v的边的个数 arr[i].clear(); vertaxs--; } else { iter = find(arr[i].begin(), arr[i].end(), v); if (iter != arr[i].end()) { arr[i].erase(iter); edges--; } } } } Digraph Digraph::reverse() const { Digraph graph(vertax()); vector vec; for (size_t i = 0; i < arrSize(); i++) { vec = adj(i); for (size_t j = 0; j < vec.size(); j++) { graph.addEdge(vec[j], i); // 取得该图的反向图 } } return graph; } vector Digraph::adj(size_t v) const { if (v < arrSize()) return arr[v]; else vector(); } void Digraph::showAdj(size_t v) const { if (v >= arrSize()) return; vector vec = adj(v); for (size_t i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << endl; } void Digraph::showDigraph() const { for (size_t i = 0; i < arr.size(); i++) { cout << i << ": "; showAdj(i); } } ~~~ **参考资料**：       1、[https://github.com/luoxn28/algorithm_data_structure](https://github.com/luoxn28/algorithm_data_structure) （里面有常用的数据结构源代码，图相关算法在graph文件夹中）       2、《算法 第4版》 图有关章节

# 红黑树       红黑树是很多平衡树的一种，保证最坏情况下基本动态几何操作时间复杂度为O(log(n)) **1、红黑树性质** (1)   每个节点是红色的，或者是黑色的 (2)   根节点是黑色的 (3)   每个叶节点(nil)是黑色的 (4)   如果一个节点是黑色的，则它的连个子节点都是黑色的 (5)   对每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点  **2、旋转**       旋转是保持二叉搜索树局部性质的操作，包括左旋和右旋。当在节点x上做左旋时，假设它的右孩子为y而不是T.nil，X可为其右孩子不是T.nil的任何节点，同理，X做右旋也是一样的。  ** ** **伪代码如下(左旋)**  **旋转代码(左旋-C)** ~~~ static void left_rotate(rbTree *T, rbtreeNode * x) { rbtreeNode *y = x->right; x->right = y->left; if(y->left != T->nil) y->left->p = x; y->p = x->p; if(x->p == T->nil) T->root = y; else if(x == x->p->left) x->p->left = y; else x->p->right = y; y->left = x; x->p = y; } ~~~ 3、插入        在O(log(n))时间内插入一个节点，RB-INSERT过程完成该操作，像一个普通的二叉搜索树一样，然后将要插入的节点Z着为红色。为了保持红黑树的性质，调用一个辅助函数RB-INSERT-FIXUP来对节点从新着色并旋转。待插入节点Z已保存了数据项。 **RB-INSERT过程伪代码**  ** ** **RB-INSERT-FIXUP过程伪代码**   **注意：**Case1属于if判断条件中，Case2和Case3输入else语句中的，Case2是else语句中的if判断语句的。具体可以看代码 **RB-INSERT代码实现(C)** ~~~ int rbtree_insert(rbTree *T, DataTypedef num) { rbtreeNode *y = T->nil; rbtreeNode *x = T->root; rbtreeNode *z = NULL; if(!rbtree_in(T, num)) { z = (rbtreeNode *)malloc(sizeof(rbtreeNode)); if(z == NULL) err_sys("no space for z in rbtree"); z->data = num; } else return ERR; while(x != T->nil) //y is parent point of x { y = x; if(z->data < x->data) x = x->left; else x = x->right; } z->p = y; if(y == T->nil) T->root = z; else if(z->data < y->data) y->left = z; else y->right = z; z->left = T->nil; z->right = T->nil; z->color = RED; if( rbtree_fixup(T, z) ) return OK; else return ERR; } ~~~ **RB-INSERT-FIXUP过程分析** 第1-15行的while循环在每次迭代的开始始终保持以下3个条件是不变的 (1)   节点z是红节点 (2)   如果z.p是根节点，则z.p是黑节点 (3)   如果有任何红黑树性质贝破坏，则至多有一条被破坏，或是性质2，或是性质4(各个性质见红黑树性质总结)。如果性质2被破坏，则因为z是根节点且是红节点。性质4被破坏则是因为z和z.p都是红节点。 **循环终止条件：**      循环终止因为z.p是黑色的(如果z是根节点，则z.p是黑色哨兵节点)，这样，在循环终止时并没有违反性质4，唯一可能不成立的就是性质2，不过第16行恢复了这个性质。 **循环保持条件：**       循环保持有6中条件，其中3种和另外3种是对称的，这取决于z的父节点z.p是z的祖父节点z.p.p的左孩子还是右孩子。情况1、2、3的区别就在于z的父节点的兄弟节点(z的叔节点)的颜色不同，加入y指向z的叔节点，如果y的颜色是红色的，则执行情况1，否则转向情况2和3。在所有的3种情况中，z的祖父节点z.p.p是黑色的，因为他的父节点z.p是红色的，故性质4只有在z和z.p之间被破坏了。  **情况1：z的叔节点y是红色的**       此时对应Case1，将z.p和y都着成黑色，解决z和z.p都是红色的问题，将z.p.p着成红色保持性质5，然后把z.p.p作为新节点z来继续进行while循环，指针z上移两层  **情况2：z的叔节点y是黑色的且z是一个右孩子** **情况3：z的叔节点y是黑色的且z是一个左孩子**       两种情况中，y都是黑色的，通过z是左孩子还是右孩子来区分，情况2中可以通过一个左旋来转化为情况3，此时z为左孩子。因为z和z.p都是红节点，对黑高(从某个节点出发，不含该节点，到达一个叶节点的任意一条简答路径上的黑色节点数为该节点的黑高)和性质5都无影响。在情况3中，改变某些节点颜色并做一次右旋，保持性质5，这样不在有两个红色节点相邻，处理完毕，此时z.p是黑色的，所以无需再执行while循环了。  **RB-INSERT-FIXUP代码实现(C)** ~~~ static int rbtree_fixup(rbTree *T, rbtreeNode *z) { rbtreeNode *y = NULL; /* * while循环在每次迭代的开头都保持3个部分的不变式 * 1 节点z是红色节点 * 2 如果z.p是根节点，则z.p是黑节点 * 3 如果有任何红黑性质被破坏，则至多只有一条被破坏，或是性质2(根为黑色节点)，或是性质4(如果一个节点是红色的， * 则它的两个子节点都是黑色的) */ while(z->p->color == RED) { if(z->p == z->p->p->left)//在所有的情况中，z的祖父节点z.p.p是黑色的，以为z.p是红色的 { y = z->p->p->right; // Case1: z uncle node y is red if(y->color == RED) { z->p->color = BLACK; y->color = BLACK; z->p->p->color = RED; z = z->p->p; } else { // Case2: z uncle node y is black, but z is right node if(z == z->p->right) { z = z->p; left_rotate(T, z); } // Case3: z uncle node y is black, but z is left node z->p->color = BLACK; z->p->p->color = RED; right_rotate(T, z->p->p); } } else { y = z->p->p->left; if(y->color == RED) { z->p->color = BLACK; y->color = BLACK; z->p->p->color = RED; z = z->p->p; } else { if(z == z->p->left) { z = z->p; right_rotate(T, z); } z->p->color = BLACK; z->p->p->color = RED; left_rotate(T, z->p->p); } } } T->root->color = BLACK; return OK; } ~~~ **4、删除**       删除操作与插入操作相比，略显复杂，与插入操作一样，也要花费O(log(n))时间。 从红黑树中删除节点，需设计一个供TREE-DELETE调用的子过程TRANSPLANT，并应用到红黑树中，TRANSPLANT过程用来调整两个节点的关系，其中的一个节点要替换掉另一个节点 **TRANSPLANT过程**       u节点表示将要被替换掉的节点，v节点是准备替换u节点的  **RB-TRANSPLANT代码实现(C)** ~~~ static void rbtree_transplant(rbTree *T, rbtreeNode *u, rbtreeNode *v) { if(u->p == T->nil) { T->root = v; } else if(u == u->p->left) { u->p->left = v; } else { u->p->right = v; } v->p = u->p; } ~~~ **RB-DELETE过程**       RB-DELETE中，z节点是要被删除的节点，其中记录了节点y的踪迹，y有可能导致红黑树性质破坏，当想删除节点z，且z的子节点少于2个时，z从书中删除，并让y称为z。当z有两个子节点时，y应该是z的后继，并且将y移到z的位置。在节点被删除或者移动时，必须记住y的颜色，并且记录节点x的踪迹，将x移到y的原来的位置，因为节点x可能引起红黑树性质破坏。删除节点z后，RB-DELETE-FIXUP过程通过改变颜色和执行旋转来恢复红黑树性质。       我们保存节点x的踪迹，使它移至节点y的原来位置。第4、7和11行的赋值语句令x或指向y的唯一子节点或指向y哨兵T.nil(y没有子节点的话)。       第5、8或14行调用RB-TRANSPLANT时，传递的第2个参数与x相同      如果y是黑色的，则有可能引入一个或多个破坏红黑色的情况，所以在第22行调用RB-TRANSPLANT来恢复红黑树性质。如果y是红色的，当y被删除或移动时，红黑树性质依然成立，因为(1) 树中黑高没有变化 (2) 不存在两个相邻的红节点，因为y在树中占据了z的位置，z的位置肯定不会违反红黑树性质的。另外，如果y是z的右孩子，则y的原右孩子x代替y，如果y是红色的，则x一定是黑色的，一次用x替代y不会使两个红节点相邻。 (3) 如果y是红色的，就不会是根节点，所以根节点仍然是黑色的。 **y为黑节点情况分析**  **RB-DELETE代码实现(C)** ~~~ void rbtree_delete(rbTree *T, DataTypedef data) { rbtreeNode *z = rbtree_find(T, data); rbtreeNode *y; rbtreeNode *x; enum ColorTypedef y_oldcolor; if(z == T->nil) { printf("the rbtree hasn't %d\n", data); return; } y = z; y_oldcolor = y->color; if(z->left == T->nil) { x = z->right; rbtree_transplant(T, z, z->right); } else if(z->right == T->nil) { x = z->left; rbtree_transplant(T, z, z->left); } else { y = rbtree_findmin(T, z->right); y_oldcolor = y->color; x = y->right; if(y->p == z) { x->p = y; } else { rbtree_transplant(T, y, y->right); y->right = z->right; y->right->p = y; } rbtree_transplant(T, z, y); y->left = z->left; y->left->p = y; y->color = z->color; } if(y_oldcolor == BLACK) rbtree_delete_fixup(T, x); free(z); //printf("free the node is ok\n\n"); } ~~~ RB-DELETE-FIXUP过程  ps：图片上的情况层次关系对应不是很齐，可以看码来的清楚 **4中情况的转换关系** 1 -> 2、3、4 2 -> 1、2、3、4、修复 (只有Case2是节点上移，所有有可能会使x=root) 3 -> 4 4 -> 修复 无论哪个Case，要么是为了到达平衡两个节点，路径上黑色数目相同的目的，要么是通过变形间接达到这个目的。 while循环的目标是将额外的黑色沿树上移，直到： (1)   x指向红黑节点，此时在第23行处将x着为(单个)黑色 (2)   x指向根节点，此时可以简单地移除额外的黑色 (3)   执行适当的旋转和重新着色  **代码中的4种情况图示** ****      上图给出了代码中出现的四种情况，再具体研究每一个情况时，先看看如何证实每种情况中的变换保证性质5。关键思想是在每种情况下，从子树的跟(包括跟)到每棵子树之间的黑色节点个数(包括x的额外黑色)并不被变换改变，因此，如果性质5在变换之前成立，则在变换之后也成立。比如：在情况1中，在变换前后，根节点到子树a或b之间的黑色节点数是3(因为x增加了一层黑色)，类似的，在变换前后根节点到其余的4个子树的叶节点中的任何一个的黑节点数是2。在图13-7(b)中，计数是还要包括所示子树的根节点的color属性的值，它是RED或是BLACK，如果定义count(RED)=0以及count(BLACK)=1，那么变换前后根节点至a的黑节点都为2+count(c)。在此情况下，变换之后新节点x具有color属性的c，但是这个节点的颜色是红黑(如果c=RED)或者双重黑色的(如果c=BLACK)。其他情况可以类似加以验证。 **情况1：x的兄弟节点w是红色的**       情况1(见RB-DELETE-FIXUP的第5-8行和图13-7(a))发生在节点x的兄弟节点w为红色时。因为w必须有黑色子节点，所有可以改变w的x.p的颜色，然后对x.p做一次左旋而不违反红黑树的任何性质。现在x的新兄弟节点是旋转之前w的某个子节点，其颜色为黑色。这样，就将情况1转变为了情况2、3或者4。       当节点w为黑色时，属于情况2、3或者4；这些情况有w的子节点颜色来区分了。 **情况2：x的兄弟节点w是黑色的，而且w的两个子节点都是黑色的**       在情况2(见RB-DELETE-FIXUP的第10-11行和图13-7(b))，w的两个子节点都是黑色的，因为w也是黑色的，所以从x和w上去掉一重黑色，使得x只有一重黑色而w为红色。为了补偿从x和w中去掉的一重黑色，在原来是红色或黑色的x.p上增加一重额外的黑色。通过将x.p作为新节点x来重复while循环。注意到，如果通过情况1进入到情况2，则新节点x就是红黑色的，因为原来的x.p是红色的，因此，新节点x的color属性值为RED，并且在测试循环条件后循环终止。然后，在第23行处将新节点x着为(单一)黑色。 **情况3：x的兄弟节点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的**       情况3(见RB-DELETE-FIXUP的第13-16行和图13-7(c))发生在w为黑色且其左孩子为红色，右孩子为黑色时。可以交换w和其左孩子w.left的颜色，然后对w进行右旋而不违反红黑树的性质。现在x的新节点w是一个有红色右孩子的黑色节点，这样我们就从情况3转换成了情况4。 **情况4：x的兄弟节点w是黑色的，且w的右孩子是红色的**       情况4(见RB-DELETE-FIXUP的第17-21行和图13-7(d))发生在节点x的兄弟节点w为黑色且w的右孩子为红色时，通过进行某些颜色修改并对x.p做一次左旋，可以去掉x的额外黑色，从而使它变为单重黑色，而且不破坏红黑树性质。将x设为设为根root后，当while循环测试其循环条件时，循环终止。 **RB-DELETE-FIXUP代码实现(C)** ~~~ static void rbtree_delete_fixup(rbTree *T, rbtreeNode *x) { rbtreeNode *w; while(x != T->root && x->color == BLACK)//while循环中，x总是指向一个具有双重黑色的非根界节点 { if(x == x->p->left) { w = x->p->right; if(w->color == RED) //情况1：x的兄弟节点w是红色 { w->color = BLACK; x->p->color = RED; left_rotate(T, x->p); w = x->p->right; } if(w->left->color == BLACK && w->right->color == BLACK) //情况2:x的兄弟节点w是黑色，而且w的两个子节点都是黑色的 { w->color = RED; x = x->p; } else { if(w->right->color == BLACK) //情况3：x的兄弟节点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的 { w->left->color = BLACK; w->color = RED; right_rotate(T, w); w = x->p->right; } w->color = x->p->color; //情况4：x的兄弟节点w是黑色的，且w的右孩子是红色的 x->p->color = BLACK; w->right->color = BLACK; left_rotate(T, x->p); x = T->root; } } else//x = x->p->right { w = x->p->left; if(w->color == RED) { w->color = BLACK; x->p->color = RED; right_rotate(T, x->p); w = x->p->left; } if(w->left->color == BLACK && w->right->color == BLACK) { w->color = RED; x = x->p; } else { if(w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; left_rotate(T, w); w = x->p->left; } w->color = x->p->color; x->p->color = BLACK; w->left->color = BLACK; right_rotate(T, x->p); x = T->root; } } } x->color = BLACK; } ~~~ **删除分析：**  参考资料： 1、《算法导论》第13章 红黑树 2、《数据结构与算法分析基础》-C语言描述 3、完整的工程代码实现见：[http://download.csdn.net/detail/u012796139/8673483](http://download.csdn.net/detail/u012796139/8673483)

优先队列包括二叉堆、d-堆、左式堆、斜堆、二项队列等 1、二叉堆        堆是一棵被完全填满的二叉树，有可能例外的是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。        堆序的性质：在一个堆中，对于每一个节点X，X的父亲的关键字小于（或等于）X中的关键字，根节点除外（它没有父节点）。完全二叉树可以用数组实现。  //关于二叉堆的头文件定义       如果要插入的元素是新的最小值，那么它将一直被推向堆顶。这样在某一个时刻，i将是1，我们就需要另Insert函数令程序跳出while循环，这个值必须保证小于或者至少等 于堆中的任何值，我们称之为标记。 ~~~ #ifndef BITHEAP_H_INCLUDED #define BITHEAP_H_INCLUDED #include #include typedef int ElementType; struct HeapStruct; typedef struct HeapStruct *PriorityQueue; PriorityQueue BitHeap_Init(int max_elements); void BitHeap_Insert(ElementType x, PriorityQueue H); ElementType BitHeap_Delete(PriorityQueue H); void BitHeap_Show(PriorityQueue H); int BitHeap_Free(PriorityQueue H); #endif // BITHEAP_H_INCLUDED ~~~ //二叉堆中的功能函数的定义  ~~~ #include "bitheap.h" struct HeapStruct { int Capacity; int Size; ElementType *Elements; }; static void print_err(char *str); static int IsFull(PriorityQueue H); static int IsEmpty(PriorityQueue H); PriorityQueue BitHeap_Init(int max_elements) { PriorityQueue H; H = (PriorityQueue)malloc(sizeof(struct HeapStruct)); if(H == NULL) print_err("no space for H in BitHeap"); H->Elements = (ElementType *)malloc((max_elements+1) * sizeof(ElementType)); H->Elements[0] = (1<<31); if(H->Elements == NULL) print_err("no space for H->Elements in BitHeap"); H->Capacity = max_elements; H->Size = 0; return H; } void BitHeap_Insert(ElementType x, PriorityQueue H) { int i; if(IsFull(H)) { printf("the heap is full\n"); return; } for(i = ++H->Size; H->Elements[i/2] > x; i /= 2) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = x; } ElementType BitHeap_Delete(PriorityQueue H) { ElementType min_val, last_val; int i, child; if(IsEmpty(H)) { printf("the bitheap is empty\n"); return (1<<31); } min_val = H->Elements[1]; last_val = H->Elements[H->Size--]; for(i = 1; 2*i < H->Size; i = child) { child = 2 * i; if(child != H->Size && (H->Elements[child+1] < H->Elements[child])) child++; if(last_val > H->Elements[child]) H->Elements[i] = H->Elements[child]; else break; } H->Elements[i] = last_val; return min_val; } void BitHeap_Show(PriorityQueue H) { int i; if(H != NULL) { for(i = 1; i <= H->Size; i++) printf("%d ", H->Elements[i]); } printf("\n"); } int BitHeap_Free(PriorityQueue H) { if(H != NULL) { free(H->Elements); free(H); } return 1; } /* * flowing function is used by function in bitheap.c */ static int IsFull(PriorityQueue H) { return (H->Size == H->Capacity); } static int IsEmpty(PriorityQueue H) { return (H->Size == 0); } static void print_err(char *str) { perror(str); exit(-1); } ~~~ //关于二叉堆的测试函数 main.c ~~~ #include #include #include "bitheap.h" int main() { PriorityQueue H; H = BitHeap_Init(15); BitHeap_Insert(4, H); BitHeap_Insert(2, H); BitHeap_Insert(7, H); BitHeap_Insert(3, H); BitHeap_Insert(12, H); BitHeap_Insert(8, H); BitHeap_Show(H); BitHeap_Delete(H); BitHeap_Show(H); if(BitHeap_Free(H)) printf("\nfree the bitheap is ok.\n"); return 0; } ~~~ 2、d-堆是二叉堆的简单推广，它恰像一个二叉堆，只是所有的节点都有d个儿子（可以说二叉堆是2-堆） 3、优先队列还包括了左式堆、斜堆、二项队列等。       可以参考《数据结构与算法分析-C语言描述》第6章 - 优先队列（堆）

      散列是一种用于以常数平均时间执行插入、删除和查找的技术。理想的散列数据结构只不过是一个包含有关键字的具有固定大小的数组。典型情况下，一个关键字就是一个 带有相关值（工资信息等）的字符串。       散列函数主要的问题就是解决冲突的消除问题。如果当一个元素被插入时另一个元素已经存在（散列值存在），那么就会产生冲突。解决这种冲突的方法有几种，一般用最 简单的两种：分离链接法、开放地址法       1.分离链接法  //分离链接散列表的头文件声明 ~~~ #ifndef HASH_H_INCLUDED #define HASH_H_INCLUDED #include #include typedef unsigned int Index; typedef int DataType; struct ListNode; typedef struct ListNode *Position; typedef Position List; struct HashTbl; typedef struct HashTbl *HashTable; HashTable Hash_InitTable(int TableSize); void Hash_Insert(DataType key, HashTable H); void Hash_Delete(DataType key, HashTable H); void Hash_Show(HashTable H); int Hash_Free(HashTable H); #endif // HASH_H_INCLUDED ~~~ //分离链接散列表的功能函数声明 ~~~ #include "hash.h" struct ListNode { DataType Data; Position Next; }; struct HashTbl { int TableSize; List *TheLists; }; void Print_Err(char *str); int NextPrime(int n); Index Hash(const int key, int tablesize) { unsigned int hashval = 0; int x; x = key; if(x < 0) { printf("the key is low 0\n"); exit(-1); } while(x != 0) { hashval = (hashval << 3) + x%10; x /= 10; } return hashval % tablesize; } HashTable Hash_InitTable(int Size) { HashTable H; int i; H = (HashTable)malloc(sizeof(struct HashTbl)); if(H == NULL) Print_Err("no space for malloc H"); H->TableSize = NextPrime(Size); H->TheLists = (List *)malloc(sizeof(List) * H->TableSize); if(H->TheLists == NULL) Print_Err("no space for malloc H->TabLists"); for(i = 0; i < H->TableSize; i++) { H->TheLists[i] = (List)malloc(sizeof(struct ListNode)); if(H->TheLists[i] == NULL) Print_Err("no space for malloc H->TabLists[i]"); else H->TheLists[i]->Next = NULL; } return H; } Position Hash_Find(DataType key, HashTable H) { Position P; List L; L = H->TheLists[Hash(key, H->TableSize)]; P = L->Next; while(P != NULL && P->Data != key) P = P->Next; return P; } void Hash_Insert(DataType key, HashTable H) { Position pos, new_cell; List L; pos = Hash_Find(key, H); if(pos == NULL) { new_cell = malloc(sizeof(struct ListNode)); if(new_cell == NULL) Print_Err("no space in Hash_Insert"); else { L = H->TheLists[Hash(key, H->TableSize)]; new_cell->Next = L->Next; new_cell->Data = key; L->Next = new_cell; } } } void Hash_Delete(DataType key, HashTable H) { Position pos, front_cell, cur_cell; List L; pos = Hash_Find(key, H); if(pos != NULL) { L = H->TheLists[Hash(key, H->TableSize)]; front_cell = L; while(front_cell->Next != NULL && front_cell->Next->Data != key) { front_cell = front_cell->Next; } cur_cell = front_cell->Next; front_cell->Next = cur_cell->Next; free(cur_cell); } } int Hash_Free(HashTable H) { int i; for(i = 0; i < H->TableSize; i++) free(H->TheLists[i]); free(H->TheLists); free(H); return 1; } void Hash_Show(HashTable H) { int i; Position p; printf("H->TableSize:%d\n", H->TableSize); for(i = 0; i < H->TableSize; i++) { printf("H->TheLists[%d]: ", i); p = H->TheLists[i]; p = p->Next; while(p != NULL) { printf("%d ", p->Data); p = p->Next; } printf("\n"); } } /* * hash.c中要用到的子函数 */ void Print_Err(char *str) { printf("%s\n", str); exit(-1); } int IsPrime(unsigned int n) { unsigned int i; if(n < 2) return -1; for(i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; } int NextPrime(int n) { int i; for(i = n; ; i++) { if(IsPrime(i) == 1) return i; } exit(-1); } ~~~ //main.c函数测试 ~~~ #include #include #include "hash.h" int main() { HashTable H = NULL; H = Hash_InitTable(6); Hash_Insert(1, H); Hash_Insert(2, H); Hash_Insert(3, H); Hash_Insert(24, H); Hash_Insert(5, H); Hash_Insert(6, H); Hash_Show(H); Hash_Delete(24, H); Hash_Show(H); if(Hash_Free(H) == 1) printf("free the HashTable is ok\n"); return 0; } ~~~       1.开放定址法 因为开放定址法都要置入表内，所以开放定址法所需要的表要比分离链接散列用表大。 开放定址法分为线性探测法、平方探测法、双散列        平方探测是消除线性探测中一次聚集问题的冲突解决办法，平方探测就是冲突函数为二次函数的探测方法。流行的选择是F(i)=i^2，上图显示了使用该冲突函数所得到的开 放定址散列表。       如果使用平方探测法，且表的大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。哪怕表有比一半多一个的位置被填满时，那么插入都有可能失败 （虽然这是难以见到的） //开放定址法头文件声明-（平方探测法） ~~~ #ifndef HASH_H_INCLUDED #define HASH_H_INCLUDED #include #include typedef unsigned int Index; typedef Index Position; struct HashTbl; typedef int DataType; typedef struct HashTbl *HashTable; HashTable Hash_Init(int Size); void Hash_Insert(DataType key, HashTable H); void Hash_Delete(DataType key, HashTable H); void Hash_Show(HashTable H); int Hash_Free(HashTable H); #endif // HASH_H_INCLUDED ~~~ //开放定址法功能函数声明-（平方探测法） ~~~ #include "hash.h" enum KindOfEntry {Legitimate, Empty, Deleted}; struct HashEntry { DataType Data; enum KindOfEntry Info; }; typedef struct HashEntry Cell; struct HashTbl { int TableSize; Cell *TheCells; }; void Print_Err(char *str); int NextPrime(int n); HashTable Hash_Init(int Size) { HashTable H; int i; H = (HashTable)malloc(sizeof(struct HashTbl)); if(H == NULL) Print_Err("no space for H in Hash_Init()"); H->TableSize = NextPrime(Size); H->TheCells = (Cell *)malloc(sizeof(Cell) * H->TableSize); if(H->TheCells == NULL) Print_Err("no space for H->TheCells in Hash_Init()"); for(i = 0; i < H->TableSize; i++) H->TheCells[i].Info = Empty; return H; } Index Hash(const int key, int tablesize) { unsigned int hashval = 0; int x; x = key; if(x < 0) { printf("the key is low 0\n"); exit(-1); } while(x != 0) { hashval = (hashval << 3) + x%10; x /= 10; } return hashval % tablesize; } Position Hash_Find(DataType key, HashTable H) { Position cur_pos; int cnt; cnt = 0; cur_pos = Hash(key, H->TableSize); while(H->TheCells[cur_pos].Info != Empty && H->TheCells[cur_pos].Data != key) { cur_pos += (2 * ++cnt - 1); if(cnt >= H->TableSize) cnt -= H->TableSize; } return cur_pos; } void Hash_Insert(DataType key, HashTable H) { Position pos; pos = Hash_Find(key, H); if(H->TheCells[pos].Info != Legitimate) { H->TheCells[pos].Info = Legitimate; H->TheCells[pos].Data = key; } } void Hash_Delete(DataType key, HashTable H) { Position pos; pos = Hash_Find(key, H); if(H->TheCells[pos].Info == Legitimate) { H->TheCells[pos].Info = Empty; //H->TheCells[pos].Data = key; } } void Hash_Show(HashTable H) { int i; printf("H->TableSize: %d\n", H->TableSize); for(i = 0; i < H->TableSize; i++) { if(H->TheCells[i].Info == Legitimate) { printf("H->TheCells[%d]: %d\n", i, H->TheCells[i].Data); } else { printf("H->TheCells[%d]:\n", i); } } printf("\n"); } int Hash_Free(HashTable H) { if(H != NULL) { free(H->TheCells); free(H); } return 1; } /* * hash.c中要用到的子函数 */ void Print_Err(char *str) { printf("%s\n", str); exit(-1); } int IsPrime(unsigned int n) { unsigned int i; if(n < 2) return -1; for(i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; } int NextPrime(int n) { int i; for(i = n; ; i++) { if(IsPrime(i) == 1) return i; } exit(-1); } ~~~ //main.c测试主函数-（平方探测法） ~~~ #include #include #include "hash.h" int main() { HashTable H; H = Hash_Init(6); Hash_Insert(1, H); Hash_Insert(2, H); Hash_Insert(3, H); Hash_Insert(13, H); Hash_Insert(14, H); Hash_Show(H); Hash_Delete(3, H); Hash_Show(H); Hash_Insert(3, H); Hash_Show(H); if(Hash_Free(H)) printf("free the hash is ok\n"); return 0; } ~~~ 3.其他的散列还有再散列和可扩展列。 

1. 链表       记录一下《数据结构与算法分析 - C语言描述》的第3章，表、栈和队列，在这记录一下哈^_^       当释放链表的的空间时，可以用free函数通知系统回收它，free(P)的结果是，P正在指向的地址没变，但在该地址处的数据此时已无定义了。 //关于链表的定义 ~~~ #ifndef LIST_H_INCLUDED #define LIST_H_INCLUDED #include #include typedef struct NODE Node; typedef struct NODE *List; typedef struct NODE *Position; List Creat(void); Position Find(int x, List L); Position FindPre(int x, List L); void Insert(int x, List L, Position p); void Delete(int x, List L); void DeleteList(List L); void Show(List L); struct NODE { int data; struct NODE *next; }; #endif ~~~ //关于链表功能函数的定义 ~~~ #include "list.h" List Creat(void) { List L; L = (List)malloc(sizeof(Node)); if(L == NULL) exit(-1); L->next = NULL; return L; } Position Find(int x, List L) { List p = L->next; while(p->data != x && p != NULL) p = p->next; return p; } Position FindPre(int x, List L) { List p = L->next; while(p->next->data != x && p->next != NULL) p = p->next; return p; } void Insert(int x, List L, Position p) { Position tmpp; L = L; tmpp = (Position)malloc(sizeof(Node)); if(tmpp == NULL) exit(-1); tmpp->data = x; tmpp->next = p->next; p->next = tmpp; } int IsLast(Position p, List L) { L = L; return p->next == NULL; } void Delete(int x, List L) { Position p, tmpL; p = FindPre(x, L); if(!IsLast(p, L)) { tmpL = p->next; p->next = tmpL->next; free(tmpL); } } void DeleteList(List L) { Position p; p = L; while(p != NULL) { L = p->next; free(p); p = L; } } void Show(List L) { Position p; p = L->next; while(p != NULL) { printf("%d ", p->data); p = p->next; } putchar('\n'); } ~~~ //链表的测试主函数 ~~~ #include #include #include "list.h" //非递归的形式把一个链表翻转过来 List reverse(List L) { Position preNode = NULL; Position nextNode = NULL; L = L->next; while(L != NULL) { nextNode = L->next; L->next = preNode; preNode = L; L = nextNode; } return preNode; } //递归的形式把一个链表翻转过来 List reverse1(List L) { Position nextNode, reverseNode; if(L == NULL || L->next == NULL) return L; nextNode = L->next; L->next = NULL; reverseNode = reverse1(nextNode); nextNode->next = L; return reverseNode; } int main(void) { List list; list = Creat(); Insert(1, list, list); Insert(2, list, Find(1, list)); Insert(3, list, Find(2, list)); Insert(4, list, Find(3, list)); Show(list); //list->next = reverse1(list->next); // Show(list); DeleteList(list); return 0; } ~~~ 2. 栈       栈的数组实现 //关于栈的定义 ~~~ #ifndef LIST_H_INCLUDED #define LIST_H_INCLUDED #include #include typedef struct stack { int Capacity; int TopOfStack; int *Array; }Stack; #define EmptyTOS (-1) #define MinStackSize 5 Stack *StackCreat(int maxNum); int IsEmpty(Stack *S); int IsFull(Stack *S); int Push(Stack *S, int x); int Pop(Stack *S, int *x); int ShowStack(Stack *S); int FreeStack(Stack *S); #endif // LIST_H_INCLUDED ~~~ //关于栈的功能函数的定义 ~~~ #include "list.h" Stack *StackCreat(int maxNum) { Stack *S; if(maxNum < MinStackSize) { printf("the maxNum is low the MinStackSize\n"); return NULL; } S = (Stack *)malloc(sizeof(Stack)); if(S == NULL) exit(-1); S->Array = (int *)malloc(sizeof(int) * maxNum); if(S->Array == NULL) exit(-1); S->Capacity = maxNum; S->TopOfStack = EmptyTOS; return S; } int IsEmpty(Stack *S) { return S->TopOfStack == EmptyTOS; } int IsFull(Stack *S) { return S->TopOfStack == (S->Capacity-1); } int Push(Stack *S, int x) { if(IsFull(S)) { printf("the stack is full\n"); return 0; } else S->Array[++S->TopOfStack] = x; return 1; } int Pop(Stack *S, int *x) { if(IsEmpty(S)) { return 0; } else { *x = S->Array[S->TopOfStack--]; return 1; } } int ShowStack(Stack *S) { int x; while(Pop(S, &x) != 0) printf("%d ", x); return 1; } int FreeStack(Stack *S) { free(S->Array); free(S); return 1; } ~~~ //栈的测试主函数 ~~~ #include "list.h" int main() { Stack *S; S = StackCreat(6); Push(S, 6); Push(S, 5); Push(S, 4); Push(S, 3); Push(S, 2); Push(S, 1); Push(S, 10); ShowStack(S); printf("\n%d\n", S->TopOfStack); if(FreeStack(S)) printf("Free Stack is ok\n"); return 0; } ~~~ 3. 队列       队列从尾部插入，从头部弹出数据。 //关于队列的定义 ~~~ #ifndef LIST_H_INCLUDED #define LIST_H_INCLUDED #include #include #define QUEUESIZE 10 typedef struct QueueRecord *Queue; typedef int ElementType; int IsEmpty(Queue Q); void MakeEmpty(Queue Q); Queue CreatQueue(void); void Enqueue(int x, Queue Q); int Outqueue(Queue Q); int Delete(Queue Q); struct QueueRecord { int Capacity; int Front; int Rear; int Size; ElementType *Array; }; #endif // LIST_H_INCLUDED ~~~ //关于队列的功能函数定义 ~~~ #include "list.h" void Error(char *str) { fprintf(stderr, "%s\n", str); exit(-1); } int IsEmpty(Queue Q) { return Q->Size == 0; } void MakeEmpty(Queue Q) { Q->Size = 0; Q->Front = 1; Q->Rear = 0; } Queue CreatQueue(void) { Queue Q; Q = (Queue)malloc(sizeof(struct QueueRecord)); if(Q == NULL) Error("No space"); Q->Array = (int *)malloc(QUEUESIZE * sizeof(int)); if(Q->Array == NULL) Error("No space"); Q->Capacity = QUEUESIZE; Q->Front = 0; Q->Rear = 0; Q->Size = 0; return Q; } static int Succ(int Value, Queue Q) { if(++Value == Q->Capacity) Value = 0; return Value; } int IsFull(Queue Q) { return Q->Size == Q->Capacity; } void Enqueue(int x, Queue Q) { if(IsFull(Q)) { Delete(Q); Error("Full Queue"); } else { Q->Size++; Q->Array[Q->Rear] = x; Q->Rear = Succ(Q->Rear, Q); } } int Outqueue(Queue Q) { int x; if(IsEmpty((Q))) { Delete(Q); Error("Empty Queue"); } else { Q->Size--; x = Q->Array[Q->Front]; Q->Front = Succ(Q->Front, Q); } return x; } int Delete(Queue Q) { int *p; p = Q->Array; free(p); free(Q); printf("Free the queue is ok\n"); return 1; } ~~~ //队列的测试主函数 ~~~ #include #include #include "list.h" int main(void) { Queue Q; Q = CreatQueue(); Enqueue(1, Q); Enqueue(2, Q); Enqueue(3, Q); Enqueue(4, Q); Enqueue(5, Q); Enqueue(6, Q); Enqueue(7, Q); Enqueue(8, Q); Enqueue(9, Q); Enqueue(10, Q); printf("The queue has %d elements\n", Q->Size); printf("%d\n", Outqueue(Q)); printf("%d\n", Outqueue(Q)); printf("%d\n", Outqueue(Q)); printf("%d\n", Outqueue(Q)); printf("%d\n", Outqueue(Q)); Delete(Q); return 0; } ~~~

      学习了《数据结构与算法分析-C语言描述》的第7章关于排序的章节，记录一下了^_^ 1. 插入排序       插入排序由N-1趟排序组成，对于P=1趟到P=N-1趟，插入排序保证位置0到位置P的元素为已排序状态，插入排序利用了这样的事实，位置0到P-1的位置上的元素是已经排好 序的时间复杂度为O(N^2) ~~~ void Insert(int a[], int n) { int i, j, t; for(i = 1; i < n; i++) { t = a[i]; for(j = i; j>0 && a[j-1]>t; j--) a[j] = a[j-1]; a[j] = t; } } ~~~ 2. 希尔排序       希尔排序是对插入排序的一种改进......        默认初始inc增量是n/2 ~~~ void Shellsort(int a[], int n) { int i, j, inc, t; for(inc = n/2; inc > 0; inc /= 2) { for(i = inc; i < n; i++) { t = a[i]; for(j = i; j >= inc; j -= inc) { if(t < a[j-inc]) a[j] = a[j-inc]; else break; } a[j] = t; } } } ~~~ 3. 堆排序 ~~~ static void _swap(int *x, int *y) { int t; t = *x; *x = *y; *y = t; } #define LeftChild(i) (2*(i)) static void _pass(int a[], int i, int n) { int child, t; for(t = a[i]; LeftChild(i) < n; i = child) { child = LeftChild(i); if(a[child+1] > a[child]) child++; if(child != n-1 && t < a[child]) a[i] = a[child]; else break; } a[i] = t; } void Heapsort(int a[], int n) { int i; for(i = n/2; i >= 0; i--) _pass(a, i, n); for(i = n-1; i > 0; i--) { _swap(&a[0], &a[i]); _pass(a, 0, i); } } ~~~ 4. 归并排序       该算法基本的操作是合并两个已排序的表。这两个表示已排序的，所以若将输出到第三个表中则该算法可以通过对输入数据一趟排序来完成。 虽然归并排序的运行时间是O(log(N))，但是它很难用于主存排序，主要问题在于合并两个排序的表需要线性附加内存。 ~~~ static void _merge(int a[], int tmpa[], int lpos, int rpos, int rend) { int n, lend, tmppos, i; lend = rpos - 1; n = rend - lpos + 1; tmppos = lpos; while(lpos <= lend && rpos <= rend) { if(a[lpos] <= a[rpos]) tmpa[tmppos++] = a[lpos++]; else tmpa[tmppos++] = a[rpos++]; } while(lpos <= lend) tmpa[tmppos++] = a[lpos++]; while(rpos <= rend) tmpa[tmppos++] = a[rpos++]; for(i = 0; i < n; i++, rend--) a[rend] = tmpa[rend]; } static void _msort(int a[], int tmpa[], int lpos, int rpos) { int mid; if(lpos < rpos) { mid = (lpos +rpos) / 2; _msort(a, tmpa, lpos, mid); _msort(a, tmpa, mid+1, rpos); _merge(a, tmpa, lpos, mid+1, rpos); } } void Mergesort(int a[], int n) { int *tmpa; if(n < 2) return; tmpa = (int *)malloc(n * sizeof(int)); if(tmpa != NULL) { _msort(a, tmpa, 0, n-1); free(tmpa); } else printf("No space exist.\n"); } ~~~ 5 快速排序       快速排序是在实践中最快的已知排序方法，它的平均运行时间为O(log(N))。 ~~~ int _pass(int a[], int low, int high) { int t; t = a[low]; if(low < high) { while(low < high) { while(low < high && a[high] >= t) high--; a[low] = a[high]; while(low < high && a[low] <= t) low++; a[high] = a[low]; } a[low] = t; } return low; } void _quickpass(int a[], int low, int high) { int mid; if(low < high) { mid = _pass(a, low, high); _quickpass(a, low, mid-1); _quickpass(a, mid+1, high); } } void Quicksort(int a[], int n) { _quickpass(a, 0, n-1); } ~~~ 6. 外部排序       以上的排序算法都是将输入数据装入内存，而在一些应用中，他们的输入数据量太大装不进内存，这就要用到外部排序，它用来处理很大的输入的。 合并时外部排序的中心思想。^_^

     看了《数据结构与算法分析》的第4章，讲树的内容，感觉写的不错。记录一下^_^ 1 查找树ADT-二叉查找树      假设树中的每个节点被指定一个关键字值，在我们的例子中，虽然任意复杂的关键字都是允许的，为了简单起见，假设他们都是整型。对于树中的每个节点，它的做左子树所 有关键字小于X的关键字，而它的右子树中所有关键字值大于X的关键字值。 //关于二叉查找树的定义 ~~~ #ifndef TREE_H_INCLUDED #define TREE_H_INCLUDED #include #include typedef struct TREENODE TreeNode; typedef struct TREENODE *Position; typedef struct TREENODE *SearchTree; typedef int ElementType; SearchTree MakeEmpty(SearchTree T); Position Find(ElementType x, SearchTree T); Position FindMin(SearchTree T); Position FindMax(SearchTree T); SearchTree Insert(ElementType x, SearchTree T); SearchTree Delete(ElementType x, SearchTree T); ElementType Retrieve(Position P); int Travel(SearchTree T); int Height(SearchTree T); struct TREENODE { ElementType data; SearchTree left; SearchTree right; }; #endif // TREE_H_INCLUDED ~~~ //关于二叉查找树的功能函数定义 ~~~ #include "tree.h" SearchTree MakeEmpty(SearchTree T) { if(T != NULL) { MakeEmpty(T->left); MakeEmpty(T->right); free(T); } return NULL; } Position Find(ElementType x, SearchTree T) { if(T == NULL) return NULL; else if(x < T->data) return Find(x, T->left); else if(x > T->data) return Find(x, T->right); else return T; } Position FindMin(SearchTree T) { if(T != NULL) while(T->left != NULL) T = T->left; return T; } Position FindMax(SearchTree T) { if(T != NULL) while(T->right != NULL) T = T->right; return T; } SearchTree Insert(ElementType x, SearchTree T) { if(T == NULL) { T = (Position)malloc(sizeof(TreeNode)); if(T == NULL) exit(-1); T->data = x; T->left = T->right = NULL; } else if(x < T->data) T->left = Insert(x, T->left); else if(x > T->data) T->right = Insert(x, T->right); return T; } SearchTree Delete(ElementType x, SearchTree T) { Position tmpnode; if(T == NULL) { printf("the tree have not any treenode\n"); exit(-1); } else if(x < T->data) T->left = Delete(x, T->left); else if(x > T->data) T->right = Delete(x, T->right); else if(T->left && T->right) { tmpnode = FindMin(T->right); T->data = tmpnode->data; T->right = Delete(T->data, T->right); } else { tmpnode = T; if(T->left == NULL) T = T->right; else if(T->right == NULL) T = T->left; free(tmpnode); } return T; } ElementType Retrieve(Position P) { return P->data; } int Travel(SearchTree T) { if(T != NULL) { Travel(T->left); printf("%d ", T->data); Travel(T->right); } return 1; } int Max(int a, int b) { return (a >= b ? a : b); } int Height(SearchTree T) { if(T == NULL) return 0; else return 1 + Max(Height(T->left), Height(T->right)); } ~~~ //二叉查找树测试的主函数 ~~~ #include #include #include "tree.h" int main() { SearchTree root = NULL; root = Insert(2, root); Insert(1, root); Insert(3, root); Insert(4, root); Travel(root); printf("min = %d, max = %d\n", FindMin(root)->data, FindMax(root)->data); printf("the tree height %d\n", Height(root)); Delete(4, root); Travel(root); printf("min = %d, max = %d\n", FindMin(root)->data, FindMax(root)->data); printf("the tree height %d\n", Height(root)); if(MakeEmpty(root) == NULL) printf("Free the tree is ok\n"); return 0; } ~~~ 2 AVL树 一颗AVl树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。（空树的高度定义为0） 单旋转>>  双旋转>>  //关于AVL树的定义 ~~~ #ifndef AVLTREE_H_INCLUDED #define AVLTREE_H_INCLUDED #include #include typedef struct AVLNODE AvlNode; typedef struct AVLNODE *Position; typedef struct AVLNODE *AvlTree; typedef int ElementType; int Height(Position P); AvlTree MakeEmpty(AvlTree T); Position Find(ElementType x, AvlTree T); Position FindMin(AvlTree T); Position FindMax(AvlTree T); AvlTree Insert(ElementType x, AvlTree T); AvlTree Delete(ElementType x, AvlTree T); ElementType Retrieve(Position P); struct AVLNODE { ElementType data; AvlTree left; AvlTree right; int Height; }; #endif // AVLTREE_H_INCLUDED ~~~ //关于AVL树的功能函数定义 ~~~ #include "avltree.h" int Height(Position P) { if(P == NULL) return 0; else return P->Height; } AvlTree MakeEmpty(AvlTree T) { if(T != NULL) { MakeEmpty(T->left); MakeEmpty(T->right); free(T); } return NULL; } Position Find(ElementType x, AvlTree T) { if(T == NULL) return NULL; else if(x < T->data) return Find(x, T->left); else if(x > T->data) return Find(x, T->right); else return T; } Position FindMin(AvlTree T) { if(T != NULL) while(T->left != NULL) T = T->left; return T; } Position FindMax(AvlTree T) { if(T != NULL) while(T->right != NULL) T = T->right; return T; } //----------------- Insert() ------------------ static int _max(int a, int b) { //return (a >= b ? a : b); if(a > b) return a; else return b; } static Position SingleRotateWithLeft(Position k2) { Position k1; k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->Height = 1 + _max(Height(k2->left), Height(k2->right)); k1->Height = 1 + _max(Height(k1->left), k2->Height); return k1; } static Position SingleRotateWithRight(Position k1) { Position k2; k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->Height = _max(Height(k1->left), Height(k1->right)) + 1; k2->Height = _max(k1->Height, Height(k2->right)) + 1; return k2; } static Position DoubleRotateWithLeft(Position k3) { k3->left = SingleRotateWithRight(k3->left); return SingleRotateWithLeft(k3); } static Position DoubleRotateWithRight(Position k1) { k1->right = SingleRotateWithLeft(k1->right); return SingleRotateWithRight(k1); } AvlTree Insert(ElementType x, AvlTree T) { if(T == NULL) { T = (Position)malloc(sizeof(AvlNode)); if(T == NULL) exit(-1); T->data = x; T->Height = 0; T->left = T->right = NULL; } else if(x < T->data) { T->left = Insert(x, T->left); if(Height(T->left) - Height(T->right) == 2) { if(x < T->left->data) T = SingleRotateWithLeft(T); else T = DoubleRotateWithLeft(T); } } else if(x > T->data) { T->right = Insert(x, T->right); if(Height(T->right) - Height(T->left) == 2) { if(x > T->right->data) T = SingleRotateWithRight(T); else T = DoubleRotateWithRight(T); } } T->Height = _max(Height(T->left), Height(T->right)) + 1; return T; } ~~~ //AVL树测试的主函数 ~~~ #include #include #include "avltree.h" int Trave(AvlTree T) { if(T != NULL) { Trave(T->left); printf("%d ", T->data); Trave(T->right); } return 1; } int Trave0(AvlTree T) { if(T != NULL) { printf("%d ", T->data); Trave0(T->left); Trave0(T->right); } return 1; } void root(AvlTree avltree) { printf("\n \n", avltree->data); printf(" left = %d root->right = %d>\n", avltree->left->data, avltree->right->data); } int main() { AvlTree avltree = NULL; avltree = Insert(10, avltree); avltree = Insert(12, avltree); avltree = Insert(14, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(16, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(8, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(4, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(6, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); avltree = Insert(7, avltree); root(avltree); printf("The avltree height is %d\n", avltree->Height); Trave0(avltree); printf("\n"); Trave(avltree); printf("\n"); if(MakeEmpty(avltree) == NULL) printf("Free the avltree is ok\n"); return 0; } ~~~

二叉树在树结构的应用中起着非常重要的作用，二叉树很多操作简单，并且任何树都可以与二叉树进行相互转换。一个具有n个节点的二叉树，一共有2n个指针域，其中只有n-1个用来指向节点的左右孩子，其余的n+1个指针为空。 二叉树具有很多重要特征： 1. 二叉树的第I层之多有2^(i-1)个节点 2. 具有n个节点的完全二叉树的深度为[log2(n)] + 1 3. 如果i=1，则节点i就是根节点，无双亲；否则其双亲是节点[i/2]。（i是节点的标号） 二叉树有几种存储结构： 1. 顺序存储结构 2. 链式存储结构(在有n个节点的二叉链表中有n+1个空链域) 二叉树的遍历： 限定先左后右的顺序的话，有三种遍历方法。先序遍历，中序遍历，后序遍历。（DLR，LDR，LRD） 除了这三种方式外，还可从上到下，从左到右按层次进行。 线索二叉树： 非线性化结构线性化操作，在每个节点增加两个指针域fwd和bkwd，分别指示节点在依任一次遍历是得到的前驱和后继的信息。以这种节点结构构成的叫做线索链表。 在一棵非线索二叉树以某种次序遍历是其变为一棵线索二叉树的过程称为二叉树的线索化。对于寻找前驱和后继节点这两种运算而言，线索树优于非线索树。但也有缺点，在进行插入和删除操时，线索树比非线索树的时间开销大，原因在于线索树进行插入和删除操作时，除了修改相应的指针外，还要修改相应的线索。 --------------------华丽滴分割线----------------------------------- 关于二叉树结构的定义说明： ~~~ typedef char datatype; typedef struct bitnode { datatype data; int lflag, rflag; struct bitnode *lchild, *rchild; }BitNode, *BitTree; ~~~ 二叉树的创建 ~~~ BitTree CreatBitTree(void) { char ch; BitTree root; scanf("%c", &ch); if(ch == '#') root = NULL; else { if(!(root = (BitTree)malloc(sizeof(BitNode)))) return 0; root->data = ch; root->lflag = 0; root->rflag = 0; root->lchild = CreatBitTree(); root->rchild = CreatBitTree(); } return root; } ~~~ 二叉树的复制，返回一个指向二叉树的指针 ~~~ BitTree CopyBitTree(BitTree T) { BitTree root; if(!T) root = NULL; else { if(!(root=(BitTree)malloc(sizeof(BitNode)))) return 0; root->data = T->data; root->lflag = T->lflag; root->rflag = T->rflag; root->lchild = CopyBitTree(T->lchild); root->rchild = CopyBitTree(T->rchild); } return root; } ~~~ 二叉树的遍历，三种方式遍历，先序、中序和后序遍历方式 ~~~ //先序遍历 void PreOrderTraverse(BitTree root) { if(root) { printf("%c->", root->data); PreOrderTraverse(root->lchild); PreOrderTraverse(root->rchild); } } //中序遍历 void InOrderTraverse(BitTree root) { if(root) { InOrderTraverse(root->lchild); printf("%c->", root->data); InOrderTraverse(root->rchild); } } //后序遍历 void PostOrderTraverse(BitTree root) { if(root) { PostOrderTraverse(root->lchild); PostOrderTraverse(root->rchild); printf("%c->", root->data); } } ~~~ 二叉树的释放 ~~~ void FreeBitTree(BitTree root) { if(root) { FreeBitTree(root->lchild); FreeBitTree(root->rchild); free(root); } } ~~~ //---------------------------线索化二叉树----------------------------- ~~~ BitTree pre; //记录上一个节点的指针 //先序线索化二叉树 void PreThreading(BitTree p); int PreOrderThreading(BitTree *root, BitTree T) //先序线索化二叉树 { if(!((*root) = (BitTree)malloc(sizeof(BitNode)))) exit(1); (*root)->lflag = 0; (*root)->rflag = 1; (*root)->rchild = (*root); if(!T) { (*root)->lchild = *(root); return 0; } else { (*root)->lchild = T; pre = *(root); PreThreading(T); pre->rchild = *(root); pre->rflag = 1; (*root)->rchild = pre; return 1; } } void PreThreading(BitTree p) //先序建立节点的搜索化 { if(p) { if(!p->lchild) { p->lchild = pre; p->lflag = 1; } if(!pre->rchild) { pre->rchild = p; pre->rflag = 1; } pre = p; if(p->lflag == 0) PreThreading(p->lchild); if(p->rflag == 0) PreThreading(p->rchild); } } //中序线索化二叉树 void InThreading(BitTree p); int InOrderThreading(BitTree *root, BitTree T) //中序线索化二叉树 { if(!((*root) = (BitTree)malloc(sizeof(BitNode)))) exit(1); (*root)->lflag = 0; (*root)->rflag = 1; (*root)->rchild = (*root); if(!T) { (*root)->lchild = *(root); return 0; } else { (*root)->lchild = T; pre = *(root); InThreading(T); pre->rchild = *(root); pre->rflag = 1; (*root)->rchild = pre; return 1; } } void InThreading(BitTree p) { if(p) { InThreading(p->lchild); //左子树线索化 if(!p->lchild) { p->lchild = pre; p->lflag = 1; } if(!pre->rchild) { pre->rchild = p; pre->rflag = 1; } pre = p; InThreading(p->rchild); } } ~~~ //---------------------------遍历线索化二叉树----------------------------- ~~~ //先序遍历线索化二叉树 void PreOrderTraverse_Threaing(BitTree root) //该root为头结点 { BitTree p = root, par; p = root->lchild; while(p != root) { printf("%c->", p->data); while(p->lflag == 0) { p = p->lchild; printf("%c->", p->data); } while((p->rflag==1) && (p->rchild != root)) { p = p->rchild; printf("%c->", p->data); } if(p->lflag == 0) p = p->lchild; else p = p->rchild; } } //中序遍历线索化二叉树 void InOrderTraverse_Threaing(BitTree root) //该root为头结点 { BitTree p = root; p = root->lchild; while(p != root) { while(p->lflag == 0) { p = p->lchild; } printf("%c->", p->data); while((p->rflag==1) && (p->rchild != root)) { p = p->rchild; printf("%c->", p->data); } p = p->rchild; } } ~~~ //---------------------------释放线索化二叉树----------------------------- ~~~ //释放先序线索化二叉树 void FreePreOrderThreading(BitTree root) { BitTree p = root, t; static int num = 0; printf("释放先序线索化链表······\n"); t = p; p = root->lchild; while(p != root) { if(t != root) { free(t); num++; } while(p->lflag == 0) { t = p; p = p->lchild; free(t); num++; } while((p->rflag==1) && (p->rchild != root)) { t = p; p = p->rchild; free(t); num++; } if(p->lflag == 0) { t = p; p = p->lchild; } else { t = p; p = p->rchild; } } free(t); num++; free(root); num++; printf("释放先序线索化链表%d个节点成功\n", num); } //释放中序线索化二叉树 void FreeInOrderThreading(BitTree root) { BitTree p = root, t; static int num = 0; printf("\n释放中序线索化链表······\n"); t = p; p = root->lchild; while(p != root) { while(p->lflag == 0) { t = p; p = p->lchild; } while((p->rflag==1) && (p->rchild != root)) { t = p; free(t); num++; p = p->rchild; } t = p; p = p->rchild; free(t); num++; } free(root); num++; printf("释放中序线索化链表%d个节点成功\n\n", num); } ~~~ //**********************求解关于二叉树的一些问题***************************// 1. 递归求解二叉树中叶子节点的数目 ~~~ int LeafCount(BitTree root) { if(!root) return 0; else if(!root->lchild && !root->rchild) return 1; else return (LeafCount(root->lchild) + LeafCount(root->rchild)); } ~~~ 2. 递归将二叉树所有节点的左右子树节点相互交换 ~~~ void BitTreeRevolute(BitTree root) { BitTree p; p = root->lchild; root->lchild = root->rchild; root->rchild = p; if(root->lchild) BitTreeRevolute(root->lchild); if(root->rchild) BitTreeRevolute(root->rchild); } ~~~

双向链表就是在单项链表的基础上增加了一个前向指针域。基本操作还是一样的，该双向链表是带有头节点的，最后一个节点的next指针域是为空的，不是指向首节点的。 双向链表的结构定义 ~~~ typedef char datatype; typedef struct node { datatype data; struct node *prior, *next; }linknode; typedef linknode *linklist; ~~~ 创建一个链表 ~~~ linklist CreatDlist(void) { char ch; linklist head; linknode *p, *h, *r; head = (linknode *)malloc(sizeof(linknode)); head->next = NULL; h = head; r = head; while((ch = getchar()) != '\n') { p = (linknode *)malloc(sizeof(linknode)); p->data = ch; p->next = NULL; if(r == head) { r->next = p; } else { r->next = p; r->prior = h; h = h->next; } r = p; } return head; } ~~~ 找到链表中一个节点 ~~~ linknode * GetNode(linklist head, int i) { linknode *p = head; int j = 0; while(p && jnext; j++; } return p; } ~~~ 插入一个节点 ~~~ void InsetDlist(linklist head, datatype ch, int i) { linknode *p = head->next, *t; int j = 0; while(p && j < i-1) { p = p->next; j++; } t = (linknode *)malloc(sizeof(linknode)); t->data = ch; t->prior = p; t->next = p->next; p->next = t; t->next->prior = t; } ~~~ 删除一个节点 ~~~ void DeleteDlist(linklist head, int i) { linknode *p = head->next; int j = 0; while(p && j < i-1) { p = p->next; j++; } p->next->prior = p->prior; p->prior->next = p->next; puts("a"); free(p); } ~~~ 显示整个双向链表 ~~~ void ShowDlist(linklist head) { linknode *p = head; while(p) { printf("%c", p->data); p = p->next; } putchar('\n'); } ~~~ 释放整个双向链表 ~~~ void FreeDlist(linklist head) { linknode *p; int i = 0; p = head; while(p) { free(p); head = head->next; p = head; i++; } printf("\nthe dlist free is ok.the node has %d.\n", i); } ~~~ 双向链表的测试程序 ~~~ #include #include #include "dlist.h" void show(linknode *p) { printf("p->prior:%c\n", p->prior->data); printf("p->data:%c\n", p->data); printf("p->next:%c\n", p->next->data); } int main(void) { linklist head; //linknode *p; head = CreatDlist(); ShowDlist(head->next); p = GetNode(head, 3); show(p); DeleteDlist(head, 3); p = GetNode(head, 3); show(p); InsetDlist(head, 'x', 2); ShowDlist(head->next); FreeDlist(head); return 0; } ~~~

关于头结点，一般链表都会有头结点，他会有几个好处： 1. 开始起始点的位置放在头结点的指针域中，这样在头结点的数据域可以存放一些其他数据，比如链表长度等。 2. 并且链表的第一个位置上的操作和其他位置的操作是一样的，这样空表和非空表的操作是一样的。 //    链表数据的定义，每个节点存放一个字符 ~~~ typedef char datatype; typedef struct node { datatype data; struct node *next; }linknode; typedef linknode *linklist; ~~~ 建立链表 ~~~ //--------- 头插法建立单链表 linklist CreatList(void) { datatype ch; linklist head; linknode *p; head = NULL; while((ch = getchar()) != '\n') { p = (linknode *)malloc(sizeof(linknode)); if(p == NULL) { printf("error: no space to get.\n"); return NULL; } p->data = ch; p->next = head; head = p; } return head; } //--------- 尾插法建立单链表，但是链表不带头结点 linklist CreatLinst2(void) { datatype ch; linklist head; linknode *p, *r; head = NULL; r = NULL; while((ch = getchar()) != '\n') { p = (linknode *)malloc(sizeof(linknode)); p->data = ch; if(head == NULL) head = p; else r->next = p; r = p; } if(r != NULL) r->next = NULL; return head; } ~~~ //--------- 尾插法建立单链表，带头结点，头结点暂时没有存放什么东西，可以存放链表的长度信息等。 ~~~ linklist CreatList1(void) { datatype ch; linklist head; linknode *p, *r; head = (linknode *)malloc(sizeof(linknode)); if(head == NULL) { printf("error: no space to get.\n"); return NULL; } r = head; while((ch = getchar()) != '\n') { p = (linknode *)malloc(sizeof(linknode)); p->data = ch; r->next = p; r = p; } r->next = NULL; return head; } ~~~ 删除链表 ~~~ //--------------------------- 没有头节点的话，删除的i值不能小于1，为1时其实是删除了首节点的后面的那一个节点。 (首节点不是头结点哈) //删除节点的时候，这个函数不能删除的第一个节点，有头节点的话就不能删除头结点，没有的话就不能删除首节点。 void DeleteNode(linklist head, int i) { int j = 0; linknode *p = head, *t; while(p && j < i-1) { p = p->next; j++; } if(!p || j>i-1) exit(1); t = p->next; p->next = t->next; free(t); } ~~~ 插入链表 //-------------------第一个节点的序号是0，如果有头节点的话，头结点的序号就是0 ~~~ void InsetNode(linklist head, datatype x, int i) { int j = 0; linknode *p, *t; p = head; while(p && j < i-1) { p = p->next; j++; } if(!p || j >i-1) exit(1); t = (linknode *)malloc(sizeof(linknode)); t->data = x; t->next = p->next; p->next = t; } ~~~ 查找链表 ~~~ // -------------------------------按序号查找-------------------------------- linklist GetNode(linklist head, int i) { int j = 0; linknode *p = head; while(p->next && jnext; j++; } if(i == j) return p; else return NULL; } ~~~ // -------------------------------按值查找--------------------------- ~~~ linklist locatenode(linklist head, datatype key) { linklist p = head; while(p && p->data!=key) { p = p->next; } return p; } ~~~ 显示链表 ~~~ //------------- 无头结点的显示链表 void ShowList(linklist head) { linklist p = head; while(p != NULL) { printf("%c", p->data); head = head->next; p = head; } printf("\n"); } ~~~ 释放链表 ~~~ void FreeList(linklist head) { linklist p = head; while(p != NULL) { head = head->next; free(p); p = head; } printf("\nfree list is ok.\n"); } ~~~

> 原文出处：[数据结构与算法分析-C语言描述](http://blog.csdn.net/column/details/datastructures.html) 作者：[u012796139](http://blog.csdn.net/u012796139) **本系列文章经作者授权在看云整理发布，未经作者允许，请勿转载！** # 数据结构与算法分析-C语言描述 > 学习《数据结构与算法分析-C语言描述》时写的一些代码和记录。