/* 二进制转换为十进制 */
#include<stdio.h>
#include<stdlib.h>
#define INCREMENT 8
typedef char Elemtype;
typedef struct Stack {
Elemtype *top;
Elemtype *base;
int stackSize;
}Stack;
Stack *initStack( int n ) //栈初始化函数
{
Stack *s = (Stack *)malloc(sizeof(Stack));
s -> base = ( Elemtype * )malloc( sizeof(Elemtype) * n );
if ( s -> base == NULL )
exit(0);
...
阅读全文
/* 无向图的邻接表法创建图的C代码实现 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxSize 20 //图顶点的最大数量
typedef char VertexType;
//全局变量，记录图的结点的数量
int VertexNum;
//定义图顶点
typedef struct GraphNode {
VertexType ver;
struct GraphNode *next;
}GraphNode;
//用邻接表法创建图
void CreateGraph( GraphNode **g )
{
VertexType c...
阅读全文
Prim算法
涉及到的几个基础知识
生成树： 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的，是连通图的极小连通子图，包含途中所有顶点，有且仅有n-1条边。非连通图的生成树则组成一个声称森林；若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。
图的遍历： 和树的遍历相似，若从图中某顶点出发，访问遍途中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历。图的...
阅读全文
算法基本思想
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入...
阅读全文
算法基本思想和过程
单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。
一.最短路径的最优子结构性质
该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。
假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j...
阅读全文
基本概念
树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结...
阅读全文
/* 斐波那契查找法 */
#include <stdio.h>
#include <stdlib.h>
int Fib( int k )
{
if( 1 == k || 2 == k )
return 1;
else
return Fib(k-1)+Fib(k-2);
}
int FibSearch( int *a, int n, int key )
{
int k = 1;
int nFib;
int *b;
int low, mid, high;
while( Fib(k) < n ) //找到Fib[k]
k++;
nFib = Fib(k);
b = (int *)realloc( a, sizeof(int)*nFib ); //扩充数组的大小
for( int...
阅读全文
环境变量
$HOME
当前用户的家目录
$PATH
以冒号分隔的用来搜索命令的目录列表
$PS1
命令提示符，通常是$字符，但在bash中，可以使用一些更复杂的值。例如，字符串[\u@\h\w]$就是一个流行的默认值，它给出用户名/机器名和当前的目录名，当然也包括一个$提示符。
$PS2
二级提示符，用来表示后续的输入，通常是 > 字符。
$IFS
输入域分隔符。当shell读取输入时，它给出用来分隔单词的一组字符，他们通常是空格，制表符和...
阅读全文
平衡二叉树的相关概念
二叉搜索树上实现查找的时间复杂度与从根节点到所查对象节点的路径成正比，最坏情况下等于树的高度。
在构造二叉搜索树时，如果输入对象的序列恰好是按其关键码大小有序，则结果将产生一棵单支树。
例如：输入序列为{11,39,46,38,75}在这样的树上查找所需要的时间是O(n)（与节点个数成正比）。
平衡树（Balanced Tree）：高度为O(logn)的树。
平衡二叉树（Balanced Binary Tree）：由阿德尔森一维尔斯...
阅读全文
/*闭散列表的建立、查找、插入、删除*/
#include <stdio.h>
#define NIL -1 //假设关键字为非负整数
#define DEL -2
typedef int KeyType;
KeyType HashTable[13]; //便于验证算法，关键字个数假定为不超过13，哈希表长定为13
//关键字插入函数
void InsertHashTable(KeyType k)
{
for(int i=0; i<13; i++)
if( NIL == HashTable[(k%13+i)%13] || DEL == HashTable[(k%13+i)%13] ) {
HashTable[(k%13+i)%1...
阅读全文