常见的一些算法

发表时间：2003-10-3 22:54:12 [回复]

　楼主

在网上看到的一些东西,贴出来供大家参考.

俱怀逸兴壮思飞
欲上青天揽明月

作者：lanjingquan
专家分：500

发表时间：2003-10-3 22:55:17 [回复]

　第1楼

发信人: Marslv (梦幻人生), 信区: Program
标题: 算法--黑白棋子(转)
发信站: BBS汕头大学郁金香站 (Sat Oct 21 23:57:24 2000), 转信
发信人: jek (好好学习天天向上), 信区: Program
标题: 黑白棋子
发信站: BBS 荔园晨风站 (Sat Mar 11 14:50:46 2000), 转信
//黑白棋子
#include <iostream.h>
int sp;
char c[20];
int i,m;
void mv(int);
void mos(int);
void main()
{int n;
cout<<"Input (n>=4)";cin>>n;
m=n;
for(i=1;i<=n;i++)
{c[i]='0';c[i+n]='1';}
sp=n*2+1;
mv(n);
cin>>i;
}
void mv(int n)
{
if(n==4)
{
mos(4);
mos(8);
mos(2);
mos(7);
mos(1);
}
else
{
mos(n);
mos(2*n-1);
mv(n-1);
}
}
void mos(int k)
{
c[sp]=c[k];
c[sp+1]=c[k+1];
sp=k;
c[k]='_';
c[k+1]='_';
for(i=1;i<=2*m+2;i++)
cout<<c[i];
cout<<endl;
}
--
..-~\
/ `-'\.'`- :
|/`._
||.-.{
\|`-'`.

俱怀逸兴壮思飞
欲上青天揽明月

此帖尚未评分

作者：lanjingquan
专家分：500

发表时间：2003-10-3 22:56:20 [回复]

　第2楼

发信人: LaoHong (批处理中), 信区: Program
标题: 计算24点的程序
发信站: BBS汕头大学郁金香站 (Sun Sep9 18:30:55 2001), 转信
看大家一直在孜孜以求的计算24, 不如贴个程序出来,
可以在1秒种之内解决任何计算24的问题. 当然想算25, 26...
也是可以的. 希望以此作为24问题的终结.
#include "stdafx.h"
//
//原理, 将4个数字和3个运算符按"波兰表达式"组成一个序列,
// 计算该序列的值是否为所求目标. 可以对这个序列的组成
// 进行遍历, 以确定是否有解.
//根据我的计算如果只限于用1-10之间的数字计算24, 总共有
// 715个不同的题目, 其中566个有解. 如果是1-13, 则有
// 1820个不同的题目, 其中1362个有解
//
int total = 0; //解的个数
int sp; //当前表达式栈指针
int s[7]; //表达式栈
void Evaluate(int& fz, int& fm)
//计算表达式的值, fz, fm为计算结果的分子, 分母
{
int op, l, m, opn[4];
op = s[sp]; //取栈顶元素
for (l = 0; l < 4; l += 2)
{
if ((m = s[++sp]) > 0) //是数字
{
opn[l] = m;
opn[l + 1] = 1;
}
else //是运算符
Evaluate(opn[l], opn[l + 1]);
}
//根据运算符进行计算
//opn[0]/opn[1] 是第一个操作数,
//opn[2]/opn[3] 是第二个操作数,
switch (op)
{
case -4: //乘法
fz = opn[0] * opn[2];
fm = opn[1] * opn[3];
break;
case -3: //加法
fz = opn[0] * opn[3] + opn[1] * opn[2];
fm = opn[1] * opn[3];
break;
case -2: //减法
fz = opn[0] * opn[3] - opn[1] * opn[2];
fm = opn[1] * opn[3];
break;
case -1: //除法
fz = opn[0] * opn[3];
fm = opn[1] * opn[2];
break;
}
}
void Display(CString& m)
//将表达式转换为字符串
{
int i;
CString n;
CString n;
m = "";
for (i = 0; i < 7; i++)
{
switch (s[i])
{
case -4: m += " *"; break;
case -3: m += " +"; break;
case -2: m += " -"; break;
case -1: m += " /"; break;
default: n.Format("%3d", s[i]); m += n; break;
}
}
}
void Compute(int target, int a, int b, int c, int d, CStringArray& ma)
// target - 计算结果(一般为24)
// a, b, c, d - 参加计算的4个数
// ma - 解的字符串表达形式
{
int l1, l2, l3, op1, op2, op3;
int l, fz, fm, num[4];
CString m;
//记录表达式中间四个元素的排列方式
// 其中loc[i][0], loc[i][1]表示第二, 第三两个运算符的位置
// loc[i][2], loc[i][3]表示第一, 第二两个操作数的位置
int loc[5][4] = {{1, 2, 3, 4}, {1, 3, 2, 4}, {1, 4, 2, 3},
{2, 3, 1, 4}, {2, 4, 1, 3}};
//num中记录a, b, c, d的一个排列
for (l1 = 0; l1 < 4; l1++)
{
num[l1] = a;
for (l2 = 0; l2 < 4; l2++)
{
if (l2 == l1) continue;
num[l2] = b;
for (l3 = 0; l3 < 4; l3++)
{
if (l3 == l1 || l3 == l2) continue;
num[l3] = c;
num[6 - l1 - l2 - l3] = d;
//表达式最后两个必须是数字
s[5] = num[2];
s[6] = num[3];
for (l = 0; l < 5; l++)
{
s[loc[l][2]] = num[0];
s[loc[l][3]] = num[1];
for (op1 = -4; op1 < 0; op1++)
{
//表达式第一个必须运算符
s[0] = op1;
for (op2 = -4; op2 < 0; op2++)
{
s[loc[l][0]] = op2;
for (op3 = -4; op3 < 0; op3++)
{
s[loc[l][1]] = op3;
sp = 0;
Evaluate(fz, fm);
//分母不为0, 可以整除, 商为24表示计算成功
if (fm != 0 && fz % fm == 0 && fz / fm == target)
{
Display(m);
ma.Add(m);
total++;
//这里加return就是只求一个解,
//否则是求出全部解(没有考虑剔除重复解)
return;
}
}
}
}
}
}
}
}
}
--

俱怀逸兴壮思飞
欲上青天揽明月

此帖尚未评分

作者：lanjingquan
专家分：500

发表时间：2003-10-3 22:57:32 [回复]

　第3楼

发信人: Marslv (梦幻人生), 信区: Program
标题: Huffman算法 (转)
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:42:31 2000), 转信
发信人: bury (颓废的埋葬), 信区: Programming
标题: Huffman算法
发信站: 逸仙时空 Yat-sen Channel (Wed Apr 19 13:37:43 2000), 站内信件
发信站: BBS 水木清华站 (Sat Feb 26 23:47:50 2000)
以前写的一个C程序不见了,刚好在华工的站上
有VC的,就顺手贴了过来了,算法流程应该是最
重要的,很多讲数字压缩的都有Huffman算法.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dir.h>
#include <dos.h>
#include <direct.h>
#include <bios.h>
#include <conio.h>
#include <time.h>
#define EXIT_OK 0
#define EXIT_FAILED -1
//////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
FILE*infile, *outfile;
unsigned long inttextsize = 0, codesize = 0, printcount = 0;
void Error(char *message)
{
printf("\n%s\n", message);
exit(-1);
}
/* LZSS Parameters */
#define N4096/* Size of string buffer */
#define F60//* Size of look-ahead buffer 60
#define THRESHOLD2
#define NILN/* End of tree's node*/
unsigned char
text_buf[N + F -1];//-1
intmatch_position, match_length,
lson[N + 1], rson[N + 257], dad[N + 1];
void InitTree(void)/* Initializing tree */
{
inti;
for (i = N + 1; i <= N + 256; i++)
rson[i] = NIL;/* root */
for (i = 0; i < N; i++)
dad[i] = NIL;/* node */
}
void InsertNode(int r)/* Inserting node to the tree */
{
inti, p, cmp;
unsigned char*key;
unsigned c;
cmp = 1;
key = &text_buf[r];
p = N + 1 + key[0];
rson[r] = lson[r] = NIL;
match_length = 0;
for ( ; ; ) {
if (cmp >= 0) {
if (rson[p] != NIL)
p = rson[p];
else {
rson[p] = r;
dad[r] = p;
return;
}
} else {
if (lson[p] != NIL)
p = lson[p];
else {
lson[p] = r;
dad[r] = p;
return;
}
}
for (i = 1; i < F; i++)
if ((cmp = key[i] - text_buf[p + i]) != 0)
break;
if (i > THRESHOLD) {
if (i > match_length) {
match_position = ((r - p) & (N - 1)) - 1;
if ((match_length = i) >= F)
break;
}
if (i == match_length) {
if ((c = ((r - p) & (N - 1)) - 1) < match_po
sitoon) {
match_position = c;
}
}
}
}
dad[r] = dad[p];
lson[r] = lson[p];
rson[r] = rson[p];
dad[lson[p]] = r;
dad[rson[p]] = r;
if (rson[dad[p]] == p)
rson[dad[p]] = r;
else
lson[dad[p]] = r;
dad[p] = NIL;/* remove p */
}
void DeleteNode(int p)/* Deleting node from the tree */
{
intq;
if (dad[p] == NIL)
return;/* unregistered */
if (rson[p] == NIL)
q = lson[p];
else
if (lson[p] == NIL)
q = rson[p];
else {
q = lson[p];
if (rson[q] != NIL) {
do {
q = rson[q];
} while (rson[q] != NIL);
rson[dad[q]] = lson[q];
dad[lson[q]] = dad[q];
lson[q] = lson[p];
dad[lson[p]] = q;
}
rson[q] = rson[p];
dad[rson[p]] = q;
}
dad[q] = dad[p];
if (rson[dad[p]] == p)
rson[dad[p]] = q;
else
lson[dad[p]] = q;
dad[p] = NIL;
}
/* Huffman coding parameters */
#define N_CHAR(256 - THRESHOLD + F)
/* character code (= 0..N_CHAR-1) */
#define T(N_CHAR * 2 - 1)/* Size of table */
#define R(T - 1)/* root position */
#define MAX_FREQ0x8000
}
/* update when cumulative frequency
*/
/* reaches to this value */
typedef unsigned char uchar;
/*
* Tables for encoding/decoding upper 6 bits of
* sliding dictionary pointer
*/
/* encoder table */
uchar p_len[64] = {
0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
};
uchar p_code[64] = {
0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
};
/* decoder table */
uchar d_code[256] = {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
};
uchar d_len[256] = {
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
};
unsigned freq[T + 1];/* cumulative freq table */
/*
* pointing parent nodes.
* area [T..(T + N_CHAR - 1)] are pointers for leaves
*/
int prnt[T + N_CHAR];
/* pointing children nodes (son[], son[] + 1)*/
int son[T];
unsigned getbuf = 0;
uchar getlen = 0;
int GetBit(void)/* get one bit */
{
int i;
while (getlen <= 8) {
if ((i = getc(infile)) < 0) i = 0;
getbuf |= i << (8 - getlen);
getlen += 8;
}
i = getbuf;
getbuf <<= 1;
getlen--;
return (i<0);
}
int GetByte(void)/* get a byte */
{
long int i;
while (getlen <= 8) {
if ((i = getc(infile)) < 0) i = 0;
getbuf |= i << (8 - getlen);
getlen += 8;
}
i = getbuf;
getbuf <<= 8;
getlen -= 8;
return (i>>8);
}
unsigned putbuf = 0;
uchar putlen = 0;
void Putcode(int l, unsigned c)/* output c bits */
{
putbuf |= c >> putlen;
if ((putlen += l) >= 8) {
putc(putbuf >> 8, outfile);
if ((putlen -= 8) >= 8) {
putc(putbuf, outfile);
codesize += 2;
putlen -= 8;
putbuf = c << (l - putlen);
} else {
putbuf <<= 8;
codesize++;
}
}
}
/* initialize freq tree */
void StartHuff()
{
int i, j;
for (i = 0; i < N_CHAR; i++) {
freq[i] = 1;
son[i] = i + T;
prnt[i + T] = i;
}
i = 0; j = N_CHAR;
while (j <= R) {
freq[j] = freq[i] + freq[i + 1];
son[j] = i;
prnt[i] = prnt[i + 1] = j;
i += 2; j++;
}
freq[T] = 0xffff;
prnt[R] = 0;
}
/* reconstruct freq tree */
void reconst()
{
int i, j, k;
unsigned f, l;
/* halven cumulative freq for leaf nodes */
j = 0;
for (i = 0; i < T; i++) {
if (son[i] >= T) {
freq[j] = (freq[i] + 1) / 2;
son[j] = son[i];
j++;
}
}
/* make a tree : first, connect children nodes */
for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
k = i + 1;
f = freq[j] = freq[i] + freq[k];
for (k = j - 1; f < freq[k]; k--);
k++;
l = (j - k) * 2;
/* movmem() is Turbo-C dependent
rewritten to memmove() by Kenji */
/* movmem(&freq[k], &freq[k + 1], l); */
(void)memmove(&freq[k + 1], &freq[k], l);
freq[k] = f;
/* movmem(&son[k], &son[k + 1], l); */
(void)memmove(&son[k + 1], &son[k], l);
son[k] = i;
}
/* connect parent nodes */
for (i = 0; i < T; i++) {
if ((k = son[i]) >= T) {
prnt[k] = i;
} else {
prnt[k] = prnt[k + 1] = i;
}
}
}
/* update freq tree */
void update(int c)
{
int i, j, k, l;
if (freq[R] == MAX_FREQ) {
reconst();
}
c = prnt[c + T];
do {
k = ++freq[c];
/* swap nodes to keep the tree freq-ordered */
if (k > freq[l = c + 1]) {
while (k > freq[++l]);
l--;
freq[c] = freq[l];
freq[l] = k;
i = son[c];
prnt[i] = l;
if (i < T) prnt[i + 1] = l;
j = son[l];
son[l] = i;
prnt[j] = c;
if (j < T) prnt[j + 1] = c;
son[c] = j;
c = l;
}
} while ((c = prnt[c]) != 0);/* do it until reaching the root */
}
unsigned code, len;
void EncodeChar(unsigned c)
{
unsigned i;
int j, k;
i = 0;
j = 0;
k = prnt[c + T];
/* search connections from leaf node to the root */
do {
i >>= 1;
/*
if node's address is odd, output 1
else output 0
*/
if (k & 1) i += 0x8000;
j++;
} while ((k = prnt[k]) != R);
Putcode(j, i);
code = i;
len = j;
update(c);
}
void EncodePosition(unsigned c)
{
unsigned i;
/* output upper 6 bits with encoding */
i = c >> 6;
Putcode(p_len[i], (unsigned)p_code[i] << 8);
/* output lower 6 bits directly */
Putcode(6, (c & 0x3f) << 10);
}
void EncodeEnd()
{
if (putlen) {
putc(putbuf >> 8, outfile);
codesize++;
}
}
int DecodeChar()
{
unsigned c;
c = son[R];
/*
* start searching tree from the root to leaves.
* choose node #(son[]) if input bit == 0
* else choose #(son[]+1) (input bit == 1)
*/
while (c < T) {
c += GetBit();
c = son[c];
}
c -= T;
update(c);
return c;
}
int DecodePosition()
{
unsigned i, j, c;
/* decode upper 6 bits from given table */
i = GetByte();
c = (unsigned)d_code[i] << 6;
j = d_len[i];
/* input lower 6 bits directly */
j -= 2;
while (j--) {
i = (i << 1) + GetBit();
}
return c | i & 0x3f;
}
/* Compression */
void Encode(void)/* Encoding/Compressing */
{
inti, c, len, r, s, last_match_length;
fseek(infile, 0L, 2);
textsize = ftell(infile);
if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
Error("Unable to write");/* write size of original te
xt /
if (textsize == 0)
return;
rewind(infile);
textsize = 0;/* rewind and rescan */
StartHuff();
InitTree();
s = 0;
r = N - F;
for (i = s; i < r; i++)
text_buf[i] = ' ';
for (len = 0; len < F && (c = getc(infile)) != EOF; len++)
text_buf[r + len] = c;
textsize = len;
for (i = 1; i <= F; i++)
InsertNode(r - i);
InsertNode(r);
do {
if (match_length > len)
match_length = len;
if (match_length <= THRESHOLD) {
match_length = 1;
EncodeChar(text_buf[r]);
} else {
EncodeChar(255 - THRESHOLD + match_length);
EncodePosition(match_position);
}
last_match_length = match_length;
for (i = 0; i < last_match_length &&
(c = getc(infile)) != EOF; i++) {
DeleteNode(s);
text_buf[s] = c;
if (s < F - 1)
text_buf[s + N] = c;
s = (s + 1) & (N - 1);
r = (r + 1) & (N - 1);
InsertNode(r);
}
if ((textsize += i) > printcount) {
printf("%12ld\r", textsize);
printcount += 1024;
}
while (i++ < last_match_length) {
DeleteNode(s);
s = (s + 1) & (N - 1);
r = (r + 1) & (N - 1);
if (--len) InsertNode(r);
}
} while (len > 0);
EncodeEnd();
printf("input: %ld bytes\n", textsize);
printf("output: %ld bytes\n", codesize);
}
void Decode(int pnum,int all)/* Decoding/Uncompressing */
{
inti, j, k, r, c;
unsigned long intcount;
if (fread(&textsize, sizeof textsize, 1, infile) < 1)
Error("Unable to read");/* read size of original text */
if (textsize == 0)
return;
StartHuff();
for (i = 0; i < N - F; i++)
text_buf[i] = ' ';
r = N - F;
for (count = 0; count < textsize; ) {
c = DecodeChar();
if (c < 256) {
putc(c, outfile);
text_buf[r++] = c;
r &= (N - 1);
count++;
} else {
i = (r - DecodePosition() - 1) & (N - 1);
j = c - 255 + THRESHOLD;
for (k = 0; k < j; k++) {
c = text_buf[(i + k) & (N - 1)];
putc(c, outfile);
text_buf[r++] = c;
r &= (N - 1);
count++;
}
}
if (count > printcount) {
process(0,count*100L/textsize);
process(1,pnum+count*(long)all/textsize);
printcount += 1024;
}
}
process(0,99);
process(1,pnum+all);
}
//解码调用程序
int exact(char *s1,char *s2,int pnum,int all)
{
char s[100];
infile=fopen(s1,"rb");
if(infile==NULL)
{
sprintf(s,"File %s not found",s1);
OutWindow(s);
return 1;
}
sprintf(s,"%s\\%s",destpath,s2);
outfile=fopen(s,"wb");
Decode(pnum,all);
fclose(infile);
fclose(outfile);
textsize=0;
codesize=0;
printcount = 0;
getbuf = 0;
getlen = 0;
putbuf = 0;
putlen = 0;
return 0;
}
--

俱怀逸兴壮思飞
欲上青天揽明月

此帖尚未评分

作者：lanjingquan
专家分：500

发表时间：2003-10-3 22:58:46 [回复]

　第4楼

俱怀逸兴壮思飞
欲上青天揽明月

此帖尚未评分

作者：lanjingquan
专家分：500

发表时间：2003-10-3 23:00:35 [回复]

　第5楼

发信人: Marslv (梦幻人生), 信区: Program
标题: 最小生成树(转）
发信站: BBS汕头大学郁金香站 (Sun Oct 22 00:30:24 2000), 转信
最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图
中选择n－1条边并使这个图仍然连通(也即得到了一棵生成树),同时还要考虑使树
的权最小。
　　为了得到最小生成树,人们设计了很多算法,最著名的有prim算法和kruskal算
法。教材中介绍了prim算法,但是讲得不够详细,理解起来比较困难,为了帮助大家
更好的理解这一算法,本文对书中的内容作了进一步的细化,希望能对大家有所帮助
。
　　假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则
prim算法通过以下步骤可以得到最小生成树:
　　1:初始化:U={u 0},TE={}。此步骤设立一个只有结点u 0的结点集U和一个空
的边集TE作为最小生成树的初始行态,在随后的算法执行中,这个行态会不断的发生
变化,直到得到最小生成树为止。
　　2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边
加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条
边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次
边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的
那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发
生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解
算法时要密切注意。
　　3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我
们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了
n－1条边,这n－1条边就是需要求出的最小生成树的边。
　　了解了prim算法的基本思想以后,下面我们就可以看看具体的算法。
　　为了和教材保持一致,我们仍然规定:连通网用邻接矩阵net表示,若两个顶点之
间不存在边,其权值为计算机内允许最大值,否则为对应边上的权值。
　　　首先定义数据类型:
　　type adjmatrix=array [1．.n,1..n] of real;
　　//定义一个n＊n的矩阵类型adjmatrix,以便存储邻接矩阵//
　　edge=record
　　　　　beg,en:1..n;
　　　　　length:real;
　　　　　end;
　　//定义边的存储结构为edge,其中beg是边的起点, en 是边的终点,length是边
的权值//
　　 treetype=array [1..n－1] of edge;
　　//定义一个基类型为edge的数组类型　 treetype,其元素个数为n－1个//
　 var net:adjmatrix;
　　//定义一个adjmatrix类型的变量net,图的邻接矩阵就存放在net中//
　　tree:treetype;
　　//定义一个treetype类型的变量tree,tree中可以存放n－1条边的信息，包括
起点、终点及权值。在算法结束后，最小生成树的n－1 条边就存放在tree中//
　　算法如下(设n为构造的出发点)：
　 procedure prim(net:adjmatrix;var tree:treetype);
　　//过程首部.参数的含义是:值参数net传递图的邻接矩阵,变参tree指明最小生
成树的存放地址//
　　begin
　for v:=1 to n－1 do
　　//此循环将顶点n与图中其它n－1个顶点形成的n－1条边存放在变量tree中
//
　　[tree[v].beg:=n;
　　tree[v].en:=v;
　　tree[v].length:=net[v]]
　　for k:=1 to n－1 do
　　//此循环执行算法思想中的步骤2,循环体每执行一次,TE中将增加一条边,在算
法中,这条增加的边存放在变量tree中的第k个元素上,可以这样认为,tree中从第1
到第k号元素中存放了TE和U的信息。注意:在算法思想中我们特别提醒了TE和U的动
态性,表现在算法中,这种动态性体现在循环变量k的变化上。//
　　[min:=tree[k].length;
　　for j:=k to n－1 do
　　　if tree[j].length<min then
　　　　 [min:=tree[j].length;
　　　　 m:=j;]
　　　//上面两条语句用于搜索权值最小的边//
　　v:=tree[m].en;
　　//此语句记录刚加入TE中的边的终点,也即即将加入U中的顶点//
　　edge:=tree[m];
　　tree[m]:=tree[k];
　　tree[k]:=edge;
　　//上面三句用于将刚找到的边存储到变量tree的第k号元素上//
　　for j:=k＋1 to n－1 do
　　//此循环用于更新tree中第k＋1到第n－1号元素。更新以后这些元素中的en子
项是各不相同的,它们的全部就是集合V－U;beg子项则可以相同,但它们需满足两个
条件:一是应属于集合U;另一是beg子项和en子项行成的边,在所有与顶点en联系的
边中权值应最小。//
　　[d:=net[v.tree[j].en];
　　　if d<tree[j].length
　　　　then [tree[j].length:=d;
　　　　　　tree[j].beg:=v;]
　　　]
　　]
　　for j:=1 to n－1 do
　　//此循环用于输出最小生成树//
　　writeln(tree[j].beg,tree[j].en,tree[j].length);
　　end;
　　此算法的精妙之处在于对求权值最小的边这一问题的分解(也正是由于这种分
解，而导致了算法理解上的困难)。按照常规的思路,这一问题应该这样解决:分别
从集合V－U和U中取一顶点,从邻接矩阵中找到这两个顶点行成的边的权值,设V－U
中有m个顶点,U中有n个顶点,则需要找到m＊n个权值,在这m＊n个权值中,再查找权
最小的边。循环每执行一次,这一过程都应重复一次，相对来说计算量比较大。而
本算法则利用了变量tree中第k＋1到第n－1号元素来存放到上一循环为止的一些比
较结果,如以第k＋1号元素为例,其存放的是集合U中某一顶点到顶点tree.en的边,
这条边是到该点的所有边中权值最小的边,所以,求权最小的边这一问题,通过比较
第k＋1号到第n－1号元素的权的大小就可以解决,每次循环只用比较n－k－2次即可
，从而大大减小了计算量。
--
.\ |/
~-.`. \|.-~_
`.\-.\.-~\
`-'/~~ -.~/
.-~/|`-._ /~~-.~ -- ~
/|\~- . _\

俱怀逸兴壮思飞
欲上青天揽明月

此帖尚未评分

作者：lanjingquan
专家分：500