求助，一道关于数据结构/算法的面试题

一般的应用网络协议数据由帧头和帧数据组成，帧头会描述帧数据的长度。
请使用已经实现的数据接收函数recvData 和帧数据处理函数 prosessFrame,完成连续接收数据并封装成帧数据进行处理函数 recvProcessFrame.

//数据帧头定义

Struct DataFrameHeader

{

Int size;

//其他头数据

};

//数据接收接口，buffer表是用来接收数据的缓冲，length是需要接收的长度，

返回实际接收到的数据的长度，如果接收失败返回-1；

实际接收到的数据长度不定，蛋肯定小于或等于需要接收的数据长度。

Int recvData( void *buffer, int length);

 
//处理帧数据接口，header是数据帧头数据指针，data是帧数据体指针。

Void processFrame( DataFrameHeader *header, void *data );

 
//连续接收数据并封装成帧数据进行处理，接收失败退出函数，否则继续接收并处理。

Void recvAndProcessFrame()

{

//你来实现

}

17 个解决方案

#1

Void recvAndProcessFrame()
{
	int length = sizeof(DataFrameHeader);
	char *buffer = new char[length];
	int count = 0;
	int itm = 0;
	int ret = 0j;
	DataFrameHeader *header = NULL;
	void *data = NULL;
	while(count < length)
	{
		ret = recvData(buffer + itm, length - count);
		if (ret < 0)
		{
			return;
		}
		count += ret;
		itm += count;
	}

	header = (DataFrameHeader *)buffer;
	length = header->size - sizeof(DataFrameHeader);
	buffer = new char[length];
	count = 0;
	itm = 0;
	while(count < length)
	{
		ret = recvData(buffer + itm, length - count);
		if (ret < 0)
		{
			return;
		}
		count += ret;
		itm += count;
	}
	data = buffer;
	processFrame(header, data);
	delete []header;
	delete []data;
}

#2

Void recvAndProcessFrame()
{
	int length = sizeof(DataFrameHeader);
	char *buffer = new char[length];
	int count = 0;
	int ret = 0j;
	DataFrameHeader *header = NULL;
	void *data = NULL;
	while(count < length)
	{
		ret = recvData(buffer + count, length - count);
		if (ret < 0)
		{
			return;
		}
		count += ret;
	}

	header = (DataFrameHeader *)buffer;
	length = header->size - sizeof(DataFrameHeader);
	buffer = new char[length];
	count = 0;
	while(count < length)
	{
		ret = recvData(buffer + count, length - count);
		if (ret < 0)
		{
			return;
		}
		count += ret;
	}
	data = buffer;
	processFrame(header, data);
	delete []header;
	delete []data;
}

#3

#2楼的。一楼的有一处笔误。

#4

引用 3 楼 u011391040 的回复:

#2楼的。一楼的有一处笔误。

那么现在问题来了，假如接收到的数据是被截断的数据流，也就是说刚开始接收的数据不一定是FrameHeader。
现在设每帧Frame以0x12 34 AB CD开头，后面跟的字节为数据长度（data length），然后跟数据（data），且每帧的数据长度不定。那怎么处理呢？

#5

Void recvAndProcessFrame()
{
	int length = sizeof(DataFrameHeader);
	char *buffer = NULL;
	DataFrameHeader *header = new char[length];
	void *data = NULL;
	int count = 0;
	int ret = 0;

	while(TRUE)
	{
		length =  sizeof(DataFrameHeader);
		count = 0;
		ret = 0;
		while(count < length)
		{
			ret = recvData(header + count, length - count);
			if (ret < 0)
			{
				return;
			}
			count += ret;
		}

		if (*((DWORD *)header) != 0x1234abcd)
		{
			continue;
		}

		length = header->size - sizeof(DataFrameHeader);
		buffer = new char[length];
		count = 0;
		while(count < length)
		{
			ret = recvData(buffer + count, length - count);
			if (ret < 0)
			{
				return;
			}
			count += ret;
		}
		data = buffer;
		processFrame(header, data);
		delete []data;
	}
	delete []header;
}

#6

引用 4 楼 zj0789 的回复:

Quote: 引用 3 楼 u011391040 的回复:

#2楼的。一楼的有一处笔误。

那么现在问题来了，假如接收到的数据是被截断的数据流，也就是说刚开始接收的数据不一定是FrameHeader。
现在设每帧Frame以0x12 34 AB CD开头，后面跟的字节为数据长度（data length），然后跟数据（data），且每帧的数据长度不定。那怎么处理呢？

这样就能持续接收处理了。

#7

引用 6 楼 u011391040 的回复:

这样就能持续接收处理了。

这样确实可以接收，若遇到下面这种情况：

假设刚开始接收的数据不是FrameHeader。
那么下面这一部分

length =  sizeof(DataFrameHeader);
        count = 0;
        ret = 0;
while(count < length)
        {
            ret = recvData(header + count, length - count);
            if (ret < 0)
            {
                return;
            }
            count += ret;
        }

至少要到下一帧才能碰到recv到的首地址是以0x12 34 AB CD开头的FrameHeader。
甚至，下一帧的FrameHeader 0x12 34 AB CD在recv的时候也会被截断。
那么要到若干帧之后，正好碰到recv到以0x12 34 AB CD开头的FrameHeader，这一帧 及 以后的帧才能正常接收。

现在想在接收到对齐数据之前，尽量减少丢失的数据。

#8

引用 7 楼 zj0789 的回复:

Quote: 引用 6 楼 u011391040 的回复:

这样就能持续接收处理了。

这样确实可以接收，若遇到下面这种情况：

假设刚开始接收的数据不是FrameHeader。
那么下面这一部分

length =  sizeof(DataFrameHeader);
        count = 0;
        ret = 0;
while(count < length)
        {
            ret = recvData(header + count, length - count);
            if (ret < 0)
            {
                return;
            }
            count += ret;
        }

至少要到下一帧才能碰到recv到的首地址是以0x12 34 AB CD开头的FrameHeader。
甚至，下一帧的FrameHeader 0x12 34 AB CD在recv的时候也会被截断。
那么要到若干帧之后，正好碰到recv到以0x12 34 AB CD开头的FrameHeader，这一帧 及 以后的帧才能正常接收。

现在想在接收到对齐数据之前，尽量减少丢失的数据。

你考虑的太多余了吧。。。 如果客户端发的包是对的，是不会出现脏数据上的。

#9

你说的情况是如果首个包不是FreamHeader并且在这个包里有FreamHeader要把这个包里的数据取出来对吧？ 如果客户端按协议发包是不会出现这种情况的。

#10

引用 7 楼 zj0789 的回复:

Quote: 引用 6 楼 u011391040 的回复:

这样就能持续接收处理了。

这样确实可以接收，若遇到下面这种情况：

假设刚开始接收的数据不是FrameHeader。
那么下面这一部分

length =  sizeof(DataFrameHeader);
        count = 0;
        ret = 0;
while(count < length)
        {
            ret = recvData(header + count, length - count);
            if (ret < 0)
            {
                return;
            }
            count += ret;
        }

至少要到下一帧才能碰到recv到的首地址是以0x12 34 AB CD开头的FrameHeader。
甚至，下一帧的FrameHeader 0x12 34 AB CD在recv的时候也会被截断。
那么要到若干帧之后，正好碰到recv到以0x12 34 AB CD开头的FrameHeader，这一帧 及 以后的帧才能正常接收。

现在想在接收到对齐数据之前，尽量减少丢失的数据。

并且如果考虑这种情况还会出现另外一种错误情况，比如某个包的开始不是FrameHeader,但是在这个包里有0x1234abcd这个数据那怎么知道这个包里有没有FrameHeader呢？

#11

引用 9 楼 u011391040 的回复:

你说的情况是如果首个包不是FreamHeader并且在这个包里有FreamHeader要把这个包里的数据取出来对吧？ 如果客户端按协议发包是不会出现这种情况的。

实际中是会出现数据错位的，如果出现错位，就要求程序具备一定的容错能力，根据帧头将错位的数据对齐后接收。
而数据错位又分为很多种情况，所以这是一个很复杂的问题。

至于你说的第二种情况，数据中是不会出现帧头的。
既然考虑到帧头的特殊性，那么肯定要选择一个数据中不会出现的字节作为帧头。

#12

引用 9 楼 u011391040 的回复:

你说的情况是如果首个包不是FreamHeader并且在这个包里有FreamHeader要把这个包里的数据取出来对吧？ 如果客户端按协议发包是不会出现这种情况的。

错位的出现倒不是说发送方没有按协议发，而是发送方在发送的过程中，接收方从中途开始接收，这时就不一定首先接收到FrameHeader

#13

引用 11 楼 zj0789 的回复:

Quote: 引用 9 楼 u011391040 的回复:

你说的情况是如果首个包不是FreamHeader并且在这个包里有FreamHeader要把这个包里的数据取出来对吧？ 如果客户端按协议发包是不会出现这种情况的。

实际中是会出现数据错位的，如果出现错位，就要求程序具备一定的容错能力，根据帧头将错位的数据对齐后接收。
而数据错位又分为很多种情况，所以这是一个很复杂的问题。

至于你说的第二种情况，数据中是不会出现帧头的。
既然考虑到帧头的特殊性，那么肯定要选择一个数据中不会出现的字节作为帧头。

如果发的是文件或者是结构体等数据呢？

#14

引用 10 楼 u011391040 的回复:

Quote: 引用 7 楼 zj0789 的回复:

Quote: 引用 6 楼 u011391040 的回复:

这样就能持续接收处理了。

这样确实可以接收，若遇到下面这种情况：

假设刚开始接收的数据不是FrameHeader。
那么下面这一部分

length =  sizeof(DataFrameHeader);
        count = 0;
        ret = 0;
while(count < length)
        {
            ret = recvData(header + count, length - count);
            if (ret < 0)
            {
                return;
            }
            count += ret;
        }

至少要到下一帧才能碰到recv到的首地址是以0x12 34 AB CD开头的FrameHeader。
甚至，下一帧的FrameHeader 0x12 34 AB CD在recv的时候也会被截断。
那么要到若干帧之后，正好碰到recv到以0x12 34 AB CD开头的FrameHeader，这一帧 及 以后的帧才能正常接收。

现在想在接收到对齐数据之前，尽量减少丢失的数据。

并且如果考虑这种情况还会出现另外一种错误情况，比如某个包的开始不是FrameHeader,但是在这个包里有0x1234abcd这个数据那怎么知道这个包里有没有FrameHeader呢？

加包尾 FrameTail 如 0xcc333cc3 取头尾之间的数据分析之

#15

引用 12 楼 zj0789 的回复:

Quote: 引用 9 楼 u011391040 的回复:

你说的情况是如果首个包不是FreamHeader并且在这个包里有FreamHeader要把这个包里的数据取出来对吧？ 如果客户端按协议发包是不会出现这种情况的。

错位的出现倒不是说发送方没有按协议发，而是发送方在发送的过程中，接收方从中途开始接收，这时就不一定首先接收到FrameHeader

如果是从数据报中间收并且下一个完整的数据包和这个这个包同时发过来才可能出现部分有效数据丢失的情况，这是两个小概率事件。

#16

引用 14 楼 likfeng 的回复:

加包尾 FrameTail 如 0xcc333cc3 取头尾之间的数据分析之

针对错位的情况要怎么处理呢？

#17

引用 16 楼 zj0789 的回复:

Quote: 引用 14 楼 likfeng 的回复:

加包尾 FrameTail 如 0xcc333cc3 取头尾之间的数据分析之

针对错位的情况要怎么处理呢？

我的做法：
1.接收数据不断放入接收缓冲区；
2.扫描帧头，发现帧头后若数据部分满足，取相应长度的数据处理，数据部分不满足继续接收数据；
3.扫描到的缓冲区的开始部分不是帧头的话，扫秒数据直到找到帧头为止，帧头之前的残缺数据丢弃。
帧尾可以不要。