分类目录归档：C/C++数据结构

2006 07-11

哲学家就餐问题 –C原代码

HOT

作者： cboy 分类： C/C++数据结构 评论： 暂无评论

/*题目：一群哲学家围坐在一个圆桌，手上持有密码m，并从1开始编了号取初值m，哲学家从1开始报数, 报到m的哲学家停止吃饭，退出圆桌，求哲学家退出的顺序。要求:n和初值m由完家输入.手上的密码随机产生.最后要打印出编号对应的密码，输出哲学家离开的相后顺序 分析:可用循环链表实现，链表数据类型为结构体，记录编号和相应密码，另外设标志哲学家报数的变量mouth, 它的值和哲学家嘴上报的数相等...

阅读全文

2006 07-02

排序小结(文章)

HOT

作者： VC爱好者 分类： C/C++数据结构 评论： 暂无评论

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。    而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。    对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。   &nbs...

阅读全文

2006 07-02

面试题目：猫吃老鼠问题的求解算法改进

HOT

作者： VC爱好者 分类： C/C++数据结构 评论： 暂无评论

一、问题描述 现有n个老鼠围成一圆圈，有一只猫从任意位置开始吃老鼠，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？题目要求是任给老鼠数n，输出猫最后吃的老鼠的编号。 二、代码说明 #include <iostream>#include <vector>using namespace std;int fun1(int itotal);int main(){ &nbs...

阅读全文

2006 07-02

采用非递归方式遍历目录及其子目录的文件

HOT

作者： VC爱好者 分类： C/C++数据结构 评论： 暂无评论

  搜索一个目录及其子目录下所有的文件是比较常见的需求，而采用递归方式进行搜索则是一个非常直观的算法。但是，由于目录中文件数量往往比较大，而每个文件名又往往占用许多空间，目录嵌套比较深的情况下，这种递归算法对于程序的堆栈是一个严重的威胁。本文给出一种非递归的算法进行目录下所有文件的检索和遍历。typedef BOOL (*PROCESS_FILE_FUNCTION)(LPCTS...

阅读全文

2006 06-28

计算圆周率 Pi (π)值, 精确到小数点后 10000 位

HOT

作者： VC爱好者 分类： C/C++数据结构 评论： 暂无评论

大家都知道π=3.1415926……无穷多位, 历史上很多人都在计算这个数, 一直认为是一个非常复杂的问题。现在有了电脑, 这个问题就简单了。电脑可以利用级数计算出很多高精度的值, 有关级数的问题请参考《高等数学》,以下是比较有名的有关π的级数:其中有些计算起来很复杂, 我们可以选用第三个, 比较简单, 并且收敛的非常快。因为计算π值, 而这个公式是计算π/2的, 我们把它变形:π = 2 + 2...

阅读全文

2006 06-12

如何用有限个点拟合出光滑的曲线

HOT

作者： cboy 分类： C/C++数据结构 评论： 暂无评论

/* 二次抛物线法绘制曲线函数 */ void paowuxian(int *x,int *y,int n,unsigned int k) { unsigned int i,j; float t1,t2,t3,t,a,b,c,d,tx,ty; *x=*(x+1);*(y)=*(y+1); *(x+n+1)=*(x+n);*(y+n+1)=*(y+n); t=0.5/k; setcolor(10);...

阅读全文

2006 06-05

字符串近似匹配算法

HOT

作者： VC爱好者 分类： C/C++数据结构 评论： 暂无评论

字符串的近似匹配，就是允许在匹配时有一定的误差，比如在字串“以前高手好久不见”中找“以前是高手”也能成功。具体地说，错误可以有三种类型：加字符（以前也是高手）、漏字符（以前高手）和替换字符（以前石膏手）。下面的函数在text中查找子串pat，最多允许有k个错误。返回的是匹配的终点（我还没想好如何确定起点，呵呵）。至于算法的原理，现在一下子说不清楚，只能说这是一个非确定性有限自动机，以后有时间的话再...

阅读全文

2006 06-05

二叉树实现源代码

HOT

作者： VC爱好者 分类： C/C++数据结构 评论： 9 条评论

二叉树实现源代码如下：#include <conio.h>#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -2typedef int status;typedef struct BiNode{...

阅读全文

2006 06-05

霍夫曼树编码的实现

HOT

作者： VC爱好者 分类： C/C++数据结构 评论： 暂无评论

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <conio.h>typedef struct{    unsigned int Weight;    unsigned int Parent...

阅读全文

2006 06-05

打造最快的Hash表

HOT

作者： VC爱好者 分类： C/C++数据结构 评论： 1 条评论

(暴雪用的MPQ文件)最近在网上看到篇文章，一起拜一拜暴雪先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但...也只能如此了...

阅读全文

2006 05-31

算术编码用c++的实现 [转]

HOT

作者： cboy 分类： C/C++数据结构 评论： 暂无评论

算术编码在图象数据压缩标准（如jpeg，jbig）中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码。算术编码用到了两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。     算术编码需要输入的是符号，各个符号的概率还有...

阅读全文

2006 05-30

拓扑排序算法

HOT

作者： cboy 分类： C/C++数据结构 评论： 暂无评论

 一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ Activity On Vertex, AOV）网络。有向图的顶点代表任务，有向边(i, j) ...

阅读全文

2006 05-30

五子棋的核心算法

HOT

作者： cboy 分类： C/C++数据结构 评论： 暂无评论

五子棋是一种受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。这里设计和实现了一个人机对下的五子棋程序，采用了博弈树的方法，应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程。 一、相关的数据结构 关于盘面情况的表示，以链表形式表示当前盘面的情况，目的是可以允许用户进行悔棋、回退等操作。   C...

阅读全文

2006 05-30

KMP 算法解析

HOT

作者： cboy 分类： C/C++数据结构 评论： 暂无评论

先看看最“朴素”的算法，当然程序写成下面这个样子，我已经可以体会出这位原创高人的功力了：

阅读全文

2006 05-30

[递归算法实例]求一个9位数,满足这样的条件^^^^^^

HOT

作者： cboy 分类： C/C++数据结构 评论： 1 条评论

题目要求:    求一个9位数,该数的每一位均是1-9之间的数,但是每位上的数字各不相同.最后使得这个9位数从高位开始,前一位能被1整除,前两位能被2整除,前三位能被3整除,前四位能被4整除……一直到整个9位数能被9整除.算法设计:    对于这类题,相信大多数人一拿到手就想到穷举所有的可能性(如果你不这样想,那你就是例外了:)呵呵).刚...

阅读全文