首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
逆算法编写比赛 ? 有兴趣的兄弟来玩玩
发表于: 2005-5-17 16:45 10797

逆算法编写比赛 ? 有兴趣的兄弟来玩玩

riijj 活跃值
7
2005-5-17 16:45
10797

[逆算法编写比赛 ]

最近制作 crackme 的兄弟比较少，可能大家都在忙了，

( 我正在参与 carvingdbg 的开发，所以暂时没有研究 crackme 了..)  

现在跟大家玩一个小型比赛，希望让初入门的兄弟可以看到大侠的技术，从中学习到一些技巧

这个比赛是要写出一段 compression (压缩) 程序的 decompression (解压缩) 程序。这段程序是我从一个 GPL project 上看到的

源码来自 :  Runuo source   ( uo emulator)
源码名字 :  Compression.cs
源码语言 :  C#
性质 :      Huffman coding( 压缩的性质不是根据出现次数，而是根据 uo 的资料性质，进行查表 )
用途 :      把传送到网络的资料先进行压缩，

我把这个源码拿来作今次比赛的原程序，参赛者的任务是要写出一个最好的解压缩程序。   (最快速，最有效率，代码质素最好)

有兴趣玩这个比赛的兄弟，可以把自己写好的源码贴上来。

胜出者将会由投票选出，由于这个比赛是没有奖品的，只属自愿性质，所以参赛者不需要太认真，最重要是互相交流。  


[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)

收藏
免费 ・7
支持
分享
最新回复 (24)
riijj
雪    币： 2319
活跃值： (565)
能力值： (RANK：300 )
在线值：
发帖
回帖
粉丝
私信
2 楼 

/***************************************************************************
 *                               Compression.cs
 *                            -------------------
 *   begin                : May 1, 2002
 *   copyright            : (C) The RunUO Software Team
 *   email                : info@runuo.com
 *
 *   $Id: Compression.cs,v 1.3 2005/01/22 04:25:04 krrios Exp $
 *   $Author: krrios $
 *   $Date: 2005/01/22 04:25:04 $
 *
 *
 ***************************************************************************/

/***************************************************************************
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 ***************************************************************************/

using System;
using System.IO;

namespace Server.Network
{
	/// <summary>
	/// Handles outgoing packet compression for the network.
	/// </summary>
	public class Compression
	{
		private static int[] m_Table = new int[514]
		{
			0x2, 0x000,	0x5, 0x01F,	0x6, 0x022,	0x7, 0x034,	0x7, 0x075,	0x6, 0x028,	0x6, 0x03B,	0x7, 0x032,
			0x8, 0x0E0,	0x8, 0x062,	0x7, 0x056,	0x8, 0x079,	0x9, 0x19D,	0x8, 0x097,	0x6, 0x02A,	0x7, 0x057,
			0x8, 0x071,	0x8, 0x05B,	0x9, 0x1CC,	0x8, 0x0A7,	0x7, 0x025,	0x7, 0x04F,	0x8, 0x066,	0x8, 0x07D,
			0x9, 0x191,	0x9, 0x1CE,	0x7, 0x03F,	0x9, 0x090,	0x8, 0x059,	0x8, 0x07B,	0x8, 0x091,	0x8, 0x0C6,
			0x6, 0x02D,	0x9, 0x186,	0x8, 0x06F,	0x9, 0x093,	0xA, 0x1CC,	0x8, 0x05A,	0xA, 0x1AE,	0xA, 0x1C0,
			0x9, 0x148,	0x9, 0x14A,	0x9, 0x082,	0xA, 0x19F,	0x9, 0x171,	0x9, 0x120,	0x9, 0x0E7,	0xA, 0x1F3,
			0x9, 0x14B,	0x9, 0x100,	0x9, 0x190,	0x6, 0x013,	0x9, 0x161,	0x9, 0x125,	0x9, 0x133,	0x9, 0x195,
			0x9, 0x173,	0x9, 0x1CA,	0x9, 0x086,	0x9, 0x1E9,	0x9, 0x0DB,	0x9, 0x1EC,	0x9, 0x08B,	0x9, 0x085,
			0x5, 0x00A,	0x8, 0x096,	0x8, 0x09C,	0x9, 0x1C3,	0x9, 0x19C,	0x9, 0x08F,	0x9, 0x18F,	0x9, 0x091,
			0x9, 0x087,	0x9, 0x0C6,	0x9, 0x177,	0x9, 0x089,	0x9, 0x0D6,	0x9, 0x08C,	0x9, 0x1EE,	0x9, 0x1EB,
			0x9, 0x084,	0x9, 0x164,	0x9, 0x175,	0x9, 0x1CD,	0x8, 0x05E,	0x9, 0x088,	0x9, 0x12B,	0x9, 0x172,
			0x9, 0x10A,	0x9, 0x08D,	0x9, 0x13A,	0x9, 0x11C,	0xA, 0x1E1,	0xA, 0x1E0,	0x9, 0x187,	0xA, 0x1DC,
			0xA, 0x1DF,	0x7, 0x074,	0x9, 0x19F,	0x8, 0x08D,	0x8, 0x0E4,	0x7, 0x079,	0x9, 0x0EA,	0x9, 0x0E1,
			0x8, 0x040,	0x7, 0x041,	0x9, 0x10B,	0x9, 0x0B0,	0x8, 0x06A,	0x8, 0x0C1,	0x7, 0x071,	0x7, 0x078,
			0x8, 0x0B1,	0x9, 0x14C,	0x7, 0x043,	0x8, 0x076,	0x7, 0x066,	0x7, 0x04D,	0x9, 0x08A,	0x6, 0x02F,
			0x8, 0x0C9,	0x9, 0x0CE,	0x9, 0x149,	0x9, 0x160,	0xA, 0x1BA,	0xA, 0x19E,	0xA, 0x39F,	0x9, 0x0E5,
			0x9, 0x194,	0x9, 0x184,	0x9, 0x126,	0x7, 0x030,	0x8, 0x06C,	0x9, 0x121,	0x9, 0x1E8,	0xA, 0x1C1,
			0xA, 0x11D,	0xA, 0x163,	0xA, 0x385,	0xA, 0x3DB,	0xA, 0x17D,	0xA, 0x106,	0xA, 0x397,	0xA, 0x24E,
			0x7, 0x02E,	0x8, 0x098,	0xA, 0x33C,	0xA, 0x32E,	0xA, 0x1E9,	0x9, 0x0BF,	0xA, 0x3DF,	0xA, 0x1DD,
			0xA, 0x32D,	0xA, 0x2ED,	0xA, 0x30B,	0xA, 0x107,	0xA, 0x2E8,	0xA, 0x3DE,	0xA, 0x125,	0xA, 0x1E8,
			0x9, 0x0E9,	0xA, 0x1CD,	0xA, 0x1B5,	0x9, 0x165,	0xA, 0x232,	0xA, 0x2E1,	0xB, 0x3AE,	0xB, 0x3C6,
			0xB, 0x3E2,	0xA, 0x205,	0xA, 0x29A,	0xA, 0x248,	0xA, 0x2CD,	0xA, 0x23B,	0xB, 0x3C5,	0xA, 0x251,
			0xA, 0x2E9,	0xA, 0x252,	0x9, 0x1EA,	0xB, 0x3A0,	0xB, 0x391,	0xA, 0x23C,	0xB, 0x392,	0xB, 0x3D5,
			0xA, 0x233,	0xA, 0x2CC,	0xB, 0x390,	0xA, 0x1BB,	0xB, 0x3A1,	0xB, 0x3C4,	0xA, 0x211,	0xA, 0x203,
			0x9, 0x12A,	0xA, 0x231,	0xB, 0x3E0,	0xA, 0x29B,	0xB, 0x3D7,	0xA, 0x202,	0xB, 0x3AD,	0xA, 0x213,
			0xA, 0x253,	0xA, 0x32C,	0xA, 0x23D,	0xA, 0x23F,	0xA, 0x32F,	0xA, 0x11C,	0xA, 0x384,	0xA, 0x31C,
			0xA, 0x17C,	0xA, 0x30A,	0xA, 0x2E0,	0xA, 0x276,	0xA, 0x250,	0xB, 0x3E3,	0xA, 0x396,	0xA, 0x18F,
			0xA, 0x204,	0xA, 0x206,	0xA, 0x230,	0xA, 0x265,	0xA, 0x212,	0xA, 0x23E,	0xB, 0x3AC,	0xB, 0x393,
			0xB, 0x3E1,	0xA, 0x1DE,	0xB, 0x3D6,	0xA, 0x31D,	0xB, 0x3E5,	0xB, 0x3E4,	0xA, 0x207,	0xB, 0x3C7,
			0xA, 0x277,	0xB, 0x3D4,	0x8, 0x0C0,	0xA, 0x162,	0xA, 0x3DA,	0xA, 0x124,	0xA, 0x1B4,	0xA, 0x264,
			0xA, 0x33D,	0xA, 0x1D1,	0xA, 0x1AF,	0xA, 0x39E,	0xA, 0x24F,	0xB, 0x373,	0xA, 0x249,	0xB, 0x372,
			0x9, 0x167,	0xA, 0x210,	0xA, 0x23A,	0xA, 0x1B8,	0xB, 0x3AF,	0xA, 0x18E,	0xA, 0x2EC,	0x7, 0x062,
			0x4, 0x00D
		};

		private static byte[] m_OutputBuffer = new byte[0x40000];
		private static object m_SyncRoot = new object();

		public unsafe static void Compress( byte[] input, int length, out byte[] output, out int outputLength )
		{
			lock ( m_SyncRoot )
			{
				int holdCount = 0;
				int holdValue = 0;

				int packCount = 0;
				int packValue = 0;

				int byteValue = 0;

				int inputLength = length;
				int inputIndex = 0;

				int outputCount = 0;

				fixed ( int *pTable = m_Table )
				{
					fixed ( byte *pOutputBuffer = m_OutputBuffer )
					{
						while ( inputIndex < inputLength )
						{
							byteValue = input[inputIndex++] << 1;

							packCount = pTable[byteValue];
							packValue = pTable[byteValue | 1];

							holdValue <<= packCount;
							holdValue  |= packValue;
							holdCount  += packCount;

							while ( holdCount >= 8 )
							{
								holdCount -= 8;

								pOutputBuffer[outputCount++] = (byte)(holdValue >> holdCount);
							}
						}

						packCount = pTable[0x200];
						packValue = pTable[0x201];

						holdValue <<= packCount;
						holdValue  |= packValue;
						holdCount  += packCount;

						while ( holdCount >= 8 )
						{
							holdCount -= 8;

							pOutputBuffer[outputCount++] = (byte)(holdValue >> holdCount);
						}

						if ( holdCount > 0 )
							pOutputBuffer[outputCount++] = (byte)(holdValue << (8 - holdCount));
					}
				}

				output = m_OutputBuffer;
				outputLength = outputCount;
			}
		}
	}
}
2005-5-17 16:46
0
riijj
雪    币： 2319
活跃值： (565)
能力值： (RANK：300 )
在线值：
发帖
回帖
粉丝
私信
3 楼
这个加压程序的使用形式 :

void Compress( byte[] input, int length, out byte[] output, out int outputLength )

使用者输入 input buffer 的位置，长度，和 output buffer 的位置，和 output 的长度变量的指针

以 C 语言理解为

void Compress( UCHAR *input, int length, UCHAR *output, int *outputLength )

现在大家需要写一个解压缩程序，格式跟原程序一样

以 C# 形式 :
void Decompress( byte[] input, int length, out byte[] output, out int outputLength )

以 C 形式 :
void Decompress( UCHAR *input, int length, UCHAR *output, int *outputLength )

如果大家有不明白的地方，可以在这里问

大家来试试吧  
2005-5-18 10:38
0
riijj
雪    币： 2319
活跃值： (565)
能力值： (RANK：300 )
在线值：
发帖
回帖
粉丝
私信
4 楼
没有人理会…  
2005-5-20 16:07
0
window
雪    币： 111
活跃值： (55)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
5 楼
关注中
2005-5-21 11:54
0
ls758
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
6 楼
对初学者太难咯
2005-5-22 15:00
0
lnn1123
雪    币： 234
活跃值： (370)
能力值： ( LV9，RANK：530 )
在线值：
发帖
回帖
粉丝
私信
7 楼
关注中！！！！！！！！
2005-5-29 06:56
0
小剑
雪    币： 110
活跃值： (13)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
8 楼
那感参与，惟有顶~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2005-5-30 10:46
0
江海笑笑生
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
9 楼
呵呵,没干过多少这样的事
2005-6-3 13:13
0
江海笑笑生
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
10 楼
明天有空,把程序写一下
2005-6-3 22:43
0
riijj
雪    币： 2319
活跃值： (565)
能力值： (RANK：300 )
在线值：
发帖
回帖
粉丝
私信
11 楼
加油  
2005-6-4 14:44
0
寒江雪
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
12 楼
初学者不会，高手不愿意花时间
2005-6-13 16:16
0
qxtianlong
雪    币： 253
活跃值： (10)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
13 楼
我搞到现在也没成功...
调试中...
2005-7-5 22:05
0
middlebeer
雪    币： 235
活跃值： (160)
能力值： ( LV9，RANK：210 )
在线值：
发帖
回帖
粉丝
私信
14 楼
唉，不懂C＃的说
2005-7-6 09:59
0
paragui
雪    币： 178
活跃值： (12)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
15 楼
这lock, fixed相当c++的什么,
代码粗看简单,
易搞定.
2005-7-22 23:31
0
江海笑笑生
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
16 楼
我写了一次,发觉必须建立一个4096的字符串,想了这么长时间,一直没想到简化的办法,
2005-7-30 15:47
0
riijj
雪    币： 2319
活跃值： (565)
能力值： (RANK：300 )
在线值：
发帖
回帖
粉丝
私信
17 楼
最初由 paragui 发布
这lock, fixed相当c++的什么,
代码粗看简单,
易搞定.


Lock 和 fixed 可以不理会
2005-7-30 21:44
0
henryouly
雪    币： 270
活跃值： (312)
能力值： ( LV9，RANK：330 )
在线值：
发帖
回帖
粉丝
私信
18 楼
我来献个丑

		private static int[] d_Table = new int[512] 
		{
			-1, -111,  0, -2,  -3, -38,  -4, -27,  -5, -21,
			-6, -13,  -7, -10,  104, -8,  42, -9,  141, 155,
			-11, -12,  80, 63,  58, 72,  -14, -17,  -15, -16,
			85, 75,  118, 62,  -18, -19,  77, 89,  -20, 69,
			205, 136,  -22, 51,  -23, 20,  -24, -25,  27, 71,
			-26, 35,  237, 158,  64, -28,  -29, -34,  -30, -33,
			-31, 28,  107, -32,  235, 137,  37, 17,  144, -35,
			84, -36,  -37, 149,  208, 140,  -39, -63,  -40, -49,
			-41, -45,  131, -42,  9, -43,  73, -44,  253, 215,
			7, -46,  22, -47,  121, -48,  125, 43,  -50, -54,
			3, -51,  108, -52,  76, -53,  38, 242,  -55, -58,
			132, -56,  -57, 60,  238, 162,  -59, 34,  -60, -62,
			251, -61,  247, 245,  124, 187,  -64, -89,  -65, -76,
			-66, -69,  -67, 16,  -68, 103,  39, 135,  -70, -74,
			-71, 127,  -72, -73,  186, 180,  182, 223,  -75, 46,
			36, 161,  -77, -85,  -78, -81,  -79, 160,  -80, 241,
			179, 188,  102, -82,  -83, -84,  222, 198,  166, 252,
			115, -86,  -87, -88,  95, 151,  225, 96,  -90, -103,
			-91, -97,  -92, 11,  -93, -94,  93, 92,  -95, -96,
			189, 174,  167, 231,  -98, 29,  -99, -100,  159, 148,
			-101, -102,  233, 183,  226, 196,  -104, 26,  -105, 23,
			-106, -109,  -107, -108,  194, 224,  168, 213,  -110, 47,
			229, 228,  -112, -199,  -113, -167,  -114, -141,  -115, -129,
			-116, -123,  -117, 105,  -118, -120,  49, -119,  197, 191,
			-121, -122,  216, 169,  217, 230,  -124, 114,  -125, -128,
			-126, -127,  249, 190,  220, 199,  88, 106,  2, -130,
			-131, -135,  -132, 99,  -133, -134,  218, 193,  164, 184,
			-136, -138,  91, -137,  250, 173,  -139, -140,  181, 202,
			221, 203,  -142, -158,  -143, -151,  -144, -146,  -145, 30,
			45, 133,  -147, -149,  -148, 53,  171, 246,  130, -150,
			143, 244,  -152, -157,  -153, -156,  -154, -155,  212, 175,
			177, 200,  192, 86,  65, 13,  -159, -163,  -160, 117,
			145, -161,  -162, 54,  239, 219,  -164, 21,  66, -165,
			90, -166,  211, 232,  -168, -179,  -169, -177,  5, -170,
			-171, -174,  -172, -173,  40, 122,  41, 48,  -175, 19,
			113, -176,  170, 195,  14, -178,  10, 15,  -180, -188,
			-181, 32,  -182, -184,  -183, 112,  123, 52,  -185, -186,
			81, 163,  -187, 248,  185, 172,  -189, 119,  -190, -194,
			-191, -193,  -192, 44,  210, 165,  87, 56,  -195, -197,
			-196, 82,  156, 176,  -198, 74,  254, 153,  -200, -227,
			-201, 256,  -202, -213,  -203, -209,  -204, -205,  234, 109,
			-206, -208,  129, -207,  209, 154,  33, 94,  255, -210,
			31, -211,  -212, 70,  207, 227,  -214, -222,  -215, -217,
			-216, 120,  50, 24,  -218, -219,  128, 55,  -220, -221,
			201, 152,  147, 204,  116, -223,  -224, -225,  68, 12,
			-226, 98,  146, 240,  -228, -244,  -229, -242,  -230, -234,
			-231, 110,  8, -232,  -233, 67,  206, 138,  -235, -238,
			100, -236,  57, -237,  214, 142,  -239, -240,  18, 83,
			25, -241,  243, 126,  -243, 6,  97, 4,  -245, 1,
			-246, -247,  111, 101,  -248, -251,  -249, -250,  134, 59,
			178, 79,  -252, -254,  61, -253,  236, 139,  78, -255,
			157, 150
		};

		public static void Decompress(byte[] input, int length, out byte[] output, out int outputLength) 
		{
			int bitmask, i;
			int outlen = 0;
			int f = 0;
			byte[] m_OutputBuffer = new byte[0x40000];
			for (i = 0; i < length; i++) 
			{
				for (bitmask = 1<<7; bitmask > 0; bitmask >>= 1) 
				{
					int offset = (-f) << 1;
					if ((bitmask & input[i]) == 0)
						f = d_Table[offset];
					else
						f = d_Table[offset | 1];
					if (f >= 0) 
					{
						m_OutputBuffer[outlen++] = (byte) f;
						f = 0;
					}
				}
			}
			output = m_OutputBuffer;
			outputLength = outlen;
		}


检验代码：
		static void Main(string[] args)
		{
			byte[] a, b, c;
			a = new byte[1024];
			int i;
			for (i = 0; i < 256; i++) a[i] = (byte) (i);
			int blen, clen;
			Compress(a,256, out b, out blen);
			//ConvertTree();
			Decompress(b, blen, out c, out clen);
			for (i = 0; i < 256; i++) 
			{
				if (c[i] != a[i]) Console.WriteLine("Decode Error! output is {0}, but should be {1}", c[i], a[i]);
				else Console.WriteLine("OK");
			}
		}


2005-7-31 12:38
0
henryouly
雪    币： 270
活跃值： (312)
能力值： ( LV9，RANK：330 )
在线值：
发帖
回帖
粉丝
私信
19 楼
ps

这个算法的时间复杂度是O(n)，n为待解码的byte stream的bit的数目，原子操作是数组寻址和赋值。
2005-7-31 13:04
0
riijj
雪    币： 2319
活跃值： (565)
能力值： (RANK：300 )
在线值：
发帖
回帖
粉丝
私信
20 楼
最初由 henryouly 发布
ps

这个算法的时间复杂度是O(n)，n为待解码的byte stream的bit的数目，原子操作是数组寻址和赋值。


还有 C# 的测试程序，很好
多谢参与  !

其他兄弟可以对代码给些意见，或是提出问题  
2005-8-1 01:18
0
henryouly
雪    币： 270
活跃值： (312)
能力值： ( LV9，RANK：330 )
在线值：
发帖
回帖
粉丝
私信
21 楼
嘿嘿，估计会问d_Table是怎么来的。算d_Table的代码可比decompress本身麻烦多了
2005-8-1 07:59
0
henryouly
雪    币： 270
活跃值： (312)
能力值： ( LV9，RANK：330 )
在线值：
发帖
回帖
粉丝
私信
22 楼
好像没什么人气，我直接做个解释好了

版主的题目上也说明了，这个是利用huffman编码进行的压缩算法。所以解压缩自然是用huffman树的性质，不熟悉这方面的reader可以先找huffman编码的相关资料看一下。我下面的说明是假设熟悉huffman算法的。

我程序中所用到的技巧是二叉树的数组表示法

d_Table保存的是一棵有256个叶子节点的满二叉树
每个节点用两个int来表示，分别表示左子树和右子树的信息
如果左（右）子树是叶子节点，那么用正值保存相应的未压缩的字符值
如果左（右）子树还是一棵树，那么用负值保存该树在d_Table的偏移
huffman的解码过程就是沿树行走的过程，从树根开始，遇到0就向左走，遇到1就向右走，碰到叶子就输出，回到树根。

d_Table的生成办法是先按照m_Table的信息，在内存中把huffman tree构造出来，然后再转换成d_Table。

发现crack个小软件不难，不过真正做到高手还需要对x86汇编、数据结构、密码学原理、高级编程语言等融会贯通啊，呵呵

因为随便写写，代码写的比较乱，见笑～

		//定义huffman tree的结点，我懒得去写property了，通通public member
		class Node 
		{
			public int val, pos, len;
			public Node left, right, parent;
		}

		//先构造huffman tree，然后转换成d_Table输出
		public static void ConvertTree() 
		{
			int i;
			root = new Node();
			root.val = -1;
			root.left = root.right = root.parent = null;
			for (i = 0; i < 257; i++) 
			{
				Node node = new Node();
				node.val = m_Table[i*2+1];
				node.len = m_Table[i*2];
				node.pos = i;
				node.left = node.right = node.parent = null;
				AddToTree(node);
			}

			visit(root);
			Console.WriteLine(seq);
			for (i = 0; i < seq; i++) 
			{
				Console.Write("{0}, {1},  ", d_Table[i*2], d_Table[i*2+1]);
				if (i % 5 == 4) Console.WriteLine();
			}
		}

		//向huffman树添加一个结点
		private static Node root;
		private static void AddToTree(Node node) 
		{
			Node parent = root, last;
			int bitmask = 1 << (node.len - 1);
			while (true) 
			{
				last = parent;
				if ((bitmask & node.val) == 0) 
				{
					parent = parent.left;
				} 
				else 
				{
					parent = parent.right;
				}

				if (parent == null) 
				{
					Node tmp = new Node();
					if (bitmask == 1) tmp = node;
					else 
					{
						tmp.left = tmp.right = null;
						tmp.parent = last;
						tmp.val = -1;
						tmp.len = 0;
					}
					if ((bitmask & node.val) == 0) 
					{
						last.left = tmp;
					} 
					else 
					{
						last.right = tmp;
					}
					parent = tmp;
				}
				bitmask >>= 1;
				if (bitmask == 0) break;
			}
		}

		//转换成d_Table的形式
		private static int seq=0;
		private static int visit(Node node) 
		{
			if (node.left == null && node.right == null) return -1;

			int save_seq = seq++;
			int t;
			t = visit(node.left);

			if (t == -1) 
			{
				d_Table[save_seq*2] = node.left.pos;
			} 
			else 
			{
				d_Table[save_seq*2] = -t;
			}

			t = visit(node.right);
			if (t == -1) 
			{
				d_Table[save_seq*2+1] = node.right.pos;
			} 
			else 
			{
				d_Table[save_seq*2+1] = -t;
			}

			return save_seq;
		}
2005-8-2 15:59
0
JackH
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
23 楼
最初由 寒江雪 发布
初学者不会，高手不愿意花时间

太对了！！！
2005-8-8 10:49
0
lnn1123
雪    币： 234
活跃值： (370)
能力值： ( LV9，RANK：530 )
在线值：
发帖
回帖
粉丝
私信
24 楼
henryouly 牛，我一看到数据结构头就昏，知道很重要，就是学的。。。。。。。。
2005-8-8 11:11
0
starluck
雪    币： 212
活跃值： (40)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
25 楼
看得不太明白
2005-8-11 13:04
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//