请教一种基于字串插入的算法

只看该作者 · 2008-6-15 23:30

比如最初有一个32位的数据，需要往中间任意位置插入一个16位的数据而得到一个新的48位的数据。
然后再往这个48位的数据中任意位置插入一个16位的数据，获得一个新的64位数据…… 依此类推。

谢谢……

2万 · 2008-6-16 00:03

2万 · 2008-6-16 01:04

好像处理器支持这么长字长似的。
干吗不直接写多少字节？有什么特殊要求？

下面例子是插入 char 的, 改成 short 差不多就是你说的(只是不知道你的数据顺序)

// n = 串原长
// i = 插入位置, 从0开始
// s = 串(数组)指针, 保证空间足够
// c = 插入字符
void insert(int n, int i, char s[], char c)
{
    // 向后移动 i 后面的数据
    // 不可用 memcpy, 但可用支持覆盖的 copy 函数替换
    for(int j=n; j>i; --j)
        s[j] = s[j-1];
    // "插入"
    s = c;
}

只看该作者 · 2008-6-16 08:18

to赤涛：您给出的程序是基于字节插入的，而我需要的是按位来插入。所以不是我所描述的需求。xwj给的思路也至少需要基于字节来拷贝。

2万 · 2008-6-16 08:40

变字长的话，里怎么知道它在哪个位结束？？？

如果都是每次插入一字节，那么很简单：
插入点只有2种情况：要么整字节，要么是两个不完整字节
前者直接插入，后者分别移位、合并即可

后面的，先从后向前依次移动一字节即可

只看该作者 · 2008-6-16 08:49

其实，最后我需要得到一个96位的字串，这个96位字串是由一个32位数据经过4次随机插入16位字串而得到的。对于插入点为整字节比较好处理，关键就是非整字节的时候，比较不好判断了。

谢谢关注。

2万 · 2008-6-16 09:00

有一个办法就是先全转换成 0101 串(位->字节), 中间全用字节操作
全部完成后再转回整数 (字节->位)

直接用整数操作, 就需要移位, 没有哪个机器支持96位字长的, 多字移位就比较复杂了, 效率也不见得高

2万 · 2008-6-16 09:05

假设里传递的// i = 插入位置，i难道不知道吗？
知道i，那么i/8就是直接偏移，i%8就是位偏移，知道偏移还不会移位、合并？？？

只看该作者 · 2008-6-16 09:06

呵呵，看来还是需要先按7楼说的做了。先转字节，再转位…… 谢谢赤涛。

只看该作者 · 2008-6-16 09:14

算出来位偏移和直接偏移比较容易，关键有位偏移的情况下，对需要插入的16位数据进行处理以及对剩下的插入位置之后的数据处理现在还没理出个比较清晰的思路啦。

2万 · 2008-6-16 09:19

只看该作者 · 2008-6-16 09:28

确实还没转过这个弯，或许多转两下就能出来了，谢谢。

只看该作者 · 2008-6-16 09:45

只看该作者 · 2008-6-16 10:21

void BitCopy( char *pSource, unsigned char mSourceBitLogic, char *pDest, unsigned char mDestBitLogic, unsigned char mBitsLength )
{
    while( mBitsLength-- )
    {
        if( *pSource & mSourceBitLogic )
        {
            *pDest |= mDestBitLogic;
        }
        else {
            *pDest &= ~mDestBitLogic;
        }

        mDestBitLogic <<= 1;
        if( mDestBitLogic == 0 ){
            mDestBitLogic = 0x01;
            pDest++;
        }

        mSourceBitLogic <<= 1;
        if( mSourceBitLogic == 0 )
        {
            mSourceBitLogic = 0x1;
            pSource++;
        }
    }
}

void BitInsert( char *pBuffer, unsigned char mInsertBitLocation, char *pData, unsigned char mBitLength )
{
    char *p0, p1;
    unsigned char Logic0,Logic1;

     //首先将BUFFER插入位位置的数据复制到插入后的位置
         //计算指针位置，P0是准备插入的点
         p0 = pBuffer + mInsertBitLocation/8;
         Logic0 = LogicToBit( mInsertBitLocation%8 );   //LogicToBit：0-7转变为0x01-0x80表示的函数，自己写

         p1 = p0 + mBitLength/8;

         //开始拷贝
         BitCopy( p0, Logic0, p1, Logic0, mBitLength );

     //数据写入
     BitCopy( pData, 0x01, p0, Logic0, mBitLength );
}

只看该作者 · 2008-6-16 17:32

谢谢所长，谢谢xwj,多谢赤涛以及各位的关注，暂时采取赤涛说的先转字节，再转位处理。

//8位转8字节
static void bit2byte_cpy(u8_t src,u8_t *dest)
{
    u8_t i;

    for(i=0;i<8;i++,dest++)
        if(src & (1 << i))
            *dest = 1;
}

//字节数据转位（长度小于255即可）
static void byte2bit_cpy(u8_t *src, u8_t *dest,u8_t len)
{
    u8_t i,j;

    for(j=0;j<=len/8;j++)
    {
        *dest = 0;
        for(i=0;i<8;i++)
            if(*src++)
                *dest |= (1 << i);
        dest++;
    }
}

//字节插入函数
//往数组中插入num个字节
//相对赤涛的函数会更浪费内存，但意思更明了
static void byte_insert(u8_t *src,u8_t *dest,u8_t *insert,u8_t offset,u8_t num,u8_t total)
{
    u8_t i;

    for(i=0;i<offset;i++)
        *dest++ = *src++;
    for(i=0;i<num;i++)
        *dest++ = *insert++;
    for(i=0;i<(total - offset);i++)
        *dest++ = *src++;
}

……

请教一种基于字串插入的算法

相关下载

相关帖子

memcpy ＋ 插入

难道还要增长到128-bit……256-bit……

谢谢楼上两位

问题是：你的设计基础就不对

难道是我问题表述的不清楚？

sorry, 只看到16-bit, 没看到"随机位置"

唉，会有什么“不好判断”的？？？

就是被移位卡住了

to xwj

我说的很清楚了，不会这么笨吧？

不好意思

首先先写个位的拷贝函数。

：

暂时先结贴

精华达人奖章

欢快之小溪

伴坛终老

技术高手奖章

终身成就奖章

坚毅之洋流

技术领袖奖章

十世金身

核心会员奖章

沉静之湖泊

技术奇才奖章

经常做客

memcpy ＋插入