|
|
10月31日 因为录像状态一共分为4种 手动录像,计划录像,移动侦测录像,不录像
计划录像、与不录像3种状态是通过定时事件SCHEDULEVENT来进行触发的。在软件初始化时 启动定时事件SCHEDULEVENT,然后每隔一定时间就去检测ChannelInfo结构中的WeekData参数。WeekData参数记录了一周内的录像计划。
日常录像计划与假期录像计划都存储在数据库Sever.mdb中的表ChannelIfo中的WeekData1 WeekData2,WeekData3,WeekData4,WeekData5,WeekData6,WeekData7,HolidayData表项中在程序初始化时被读入到ChannelInfo结构的WeekData和HolidayData单元中。
10月30日 在设计播放器的时候,为了简单起见,可以同时打开一个多个窗口,使用了mutex来保持线程的同步。
1.CreateMutex 2.使用前先OpenMutex得到Mutex的句柄(其实CreateMutex也能完成这项任务,只不过很多时候
CreateMutex在InitialDlg中就使用了,呵呵VC中)
HANDLE OpenMutex( DWORD dwDesiredAccess, // access BOOL bInheritHandle, // inheritance option LPCTSTR lpName // object name ); 例如OpenMutex(MUTEX_ALL_ACCESS,FALSE,"Play")
MUTEX_ALL_ACCESS: Specifies all possible access flags for the mutex object. SYNCHRONIZE Windows NT/2000/XP: Enables use of the mutex handle in any of the wait functions to acquire ownership of the mutex, or in the ReleaseMutex function to release ownership.
3 然后WaitForSingleObject,个人感觉就是获得了该mutex的使用权
DWORD WaitForSingleObject( HANDLE hHandle, DWORD dwMilliseconds );
This function returns when the specified object is in the signaled state or when the time-out interval elapses.
4 如果建立了新的窗口,则应当AfxBeginThread 10月29日 又确认了一下H264的视频格式——H264支持4:2:0的连续或隔行视频的编码和解码
YUV(亦称YCrCb)是被欧洲电视系统所采用的一种颜色编码方法(属于PAL)。YUV主要用于优化彩色视频信号的传输,使其向后兼容老式黑白电视。与RGB视频信号传输相比,它最大的优点在于只需占用极少的带宽(RGB要求三个独立的视频信号同时传输)。其中“Y”表示明亮度(Luminance或Luma),也就是灰阶值;而“U”和“V”表示的则是色度(Chrominance或Chroma),作用是描述影像色彩及饱和度,用于指定像素的颜色。“亮度”是通过RGB输入信号来创建的,方法是将RGB信号的特定部分叠加到一起。“色度”则定义了颜色的两个方面—色调与饱和度,分别用Cr和CB来表示。其中,Cr反映了GB输入信号红色部分与RGB信号亮度值之间的差异。而CB反映的是RGB输入信号蓝色部分与RGB信号亮度值之同的差异。
补充一下场的概念——
场的概念不是从DV才开始有的,电视系统已经有了(当然,DV和电视的关系大家都知道)归根结底还是扫描的问题,具体到PAL制式是: 每秒25帧,每帧两场,扫描线(包括电视机的电子束)自上而下先扫描一场,然后再自上而下扫描第二场 之所以引入场的概念,我的理解是主要为了在有限的带宽和成本内使画面运动更加平滑和消除闪烁感。 这两个场的扫描线是一条一条互相间隔开的,比如说对于一个帧来讲,最上面一条线编号为0,紧挨着的是1,再下来是2,3,4,5,6。。。。那么第一场也许是0,2,4,6;也许是1,3,5,7——这就是隔行扫描 在逐行扫描模式下,就是扫描线按照0,1,2,3,4,5的顺序依次扫描,很明显,这时候就不存在场的概念了。
下面区分一下YUV和YCbCr
YUV色彩模型来源于RGB模型,
该模型的特点是将亮度和色度分离开,从而适合于图像处理领域。
应用:模拟领域
Y'= 0.299*R' + 0.587*G' + 0.114*B'
U'= -0.147*R' - 0.289*G' + 0.436*B' = 0.492*(B'- Y')
V'= 0.615*R' - 0.515*G' - 0.100*B' = 0.877*(R'- Y')
R' = Y' + 1.140*V'
G' = Y' - 0.394*U' - 0.581*V'
B' = Y' + 2.032*U'
YCbCr模型来源于YUV模型。YCbCr是 YUV 颜色空间的偏移版本.
应用:数字视频,ITU-R BT.601建议
Y’ = 0.257*R' + 0.504*G' + 0.098*B' + 16
Cb' = -0.148*R' - 0.291*G' + 0.439*B' + 128
Cr' = 0.439*R' - 0.368*G' - 0.071*B' + 128
R' = 1.164*(Y’-16) + 1.596*(Cr'-128)
G' = 1.164*(Y’-16) - 0.813*(Cr'-128) - 0.392*(Cb'-128)
B' = 1.164*(Y’-16) + 2.017*(Cb'-128)
PS: 上面各个符号都带了一撇,表示该符号在原值基础上进行了伽马校正,伽马校正有助于弥补在抗锯齿的过程中,线性分配伽马值所带来的细节损失,使图像细节更加丰富。在没有采用伽马校正的情况下,暗部细节不容易显现出来,而采用了这一图像增强技术以后,图像的层次更加明晰了。
所以说H264里面的YUV应属于YCbCr.
下面再仔细谈谈YUV格式, YUV格式通常有两大类:打包(packed)格式和平面(planar)格式。前者将YUV分量存放在同一个数组中,通常是几个相邻的像素组成一个宏像素(macro-pixel);而后者使用三个数组分开存放YUV三个分量,就像是一个三维平面一样。
我们常说得YUV420属于planar格式的YUV, 颜色比例如下:
Y0U0V0 Y1 Y2U2V2 Y3
Y4 Y5 Y6 Y7
Y8U8V8 Y9 Y10U10V10 Y11
Y12 Y13 Y14 Y15
其他格式YUV可以点这里查看详细内容, 而在YUV文件中YUV420又是怎么存储的呢? 在常见H264测试的YUV序列中,例如CIF图像大小的YUV序列(352*288),在文件开始并没有文件头,直接就是YUV数据,先存第一帧的Y信息,长度为352*288个byte, 然后是第一帧U信息长度是352*288/4个byte, 最后是第一帧的V信息,长度是352*288/4个byte, 因此可以算出第一帧数据总长度是352*288*1.5,即152064个byte, 如果这个序列是300帧的话, 那么序列总长度即为152064*300=44550KB,这也就是为什么常见的300帧CIF序列总是44M的原因.
4:4:4采样就是说三种元素Y,Cb,Cr有同样的分辨率,这样的话,在每一个像素点上都对这三种元素进行采样.数字4是指在水平方向上对于各种元素的采样率,比如说,每四个亮度采样点就有四个Cb的Cr采样值.4:4:4采样完整地保留了所有的信息值.4:2:2采样中(有时记为YUY2),色度元素在纵向与亮度值有同样的分辨率,而在横向则是亮度分辨率的一半(4:2:2表示每四个亮度值就有两个Cb和Cr采样.)4:2:2视频用来构造高品质的视频彩色信号.
在流行的4:2:0采样格式中(常记为YV12)Cb和Cr在水平和垂直方向上有Y分辨率的一半.4:2:0有些不同,因为它并不是指在实际采样中使用4:2:0,而是在编码史中定义这种编码方法是用来区别于4:4:4和4:2:2方法的).4:2:0采样被广泛地应用于消费应用中,比如视频会议,数字电视和DVD存储中。因为每个颜色差别元素中包含了四分之一的Y采样元素量,那么4:2:0YCbCr视频需要刚好4: 4:4或RGB视频中采样量的一半。
4:2:0采样有时被描述是一个"每像素12位"的方法。这么说的原因可以从对四个像素的采样中看出. 使用4:4:4采样,一共要进行12次采样,对每一个Y,Cb和Cr,就需要12*8=96位,平均下来要96/4=24位。使用4:2:0就需要6*8 =48位,平均每个像素48/4=12位。
在一个4:2:0隔行扫描的视频序列中,对应于一个完整的视频帧的Y,Cb,Cr采样分配到两个场中。可以得到,隔行扫描的总采样数跟渐进式扫描中使用的采样数目是相同的。
对比一下:
Y41P(和Y411)(packed格式)格式为每个像素保留Y分量,而UV分量在水平方向上每4个像素采样一次。一个宏像素为12个字节,实际表示8个像素。图像数据中YUV分量排列顺序如下: U0 Y0 V0 Y1 U4 Y2 V4 Y3 Y4 Y5 Y6 Y8 …
IYUV格式(planar)为每个像素都提取Y分量,而在UV分量的提取时,首先将图像分成若干个2 x 2的宏块,然后每个宏块提取一个U分量和一个V分量。YV12格式与IYUV类似,但仍然是平面模式。
YUV411、YUV420格式多见于DV数据中,前者用于NTSC制,后者用于PAL制。YUV411为每个像素都提取Y分量,而UV分量在水平方向上每4个像素采样一次。YUV420并非V分量采样为0,而是跟YUV411相比,在水平方向上提高一倍色差采样频率,在垂直方向上以U/V间隔的方式减小一半色差采样,如下图所示。
(好像显示不出来突下图像)
各种格式的具体使用位数的需求(使用4:2:0采样,对于每个元素用8个位大小表示):
格式: Sub-QCIF 亮度分辨率: 128*96 每帧使用的位: 147456 格式: QCIF 亮度分辨率: 176*144 每帧使用的位: 304128 格式: CIF 亮度分辨率: 352*288 每帧使用的位: 1216512 格式: 4CIF 亮度分辨率: 704*576 每帧使用的位: 4866048 10月28日 根据板卡api设计实现yuv420格式的视频播放器
打开*.mp4;*.264类型的文件,实现其播放。
使用的视频格式是YUV420格式
YUV格式通常有两大类:打包(packed)格式和平面(planar)格式。前者将YUV分量存放在同一个数组中,通常是几个相邻的像素组成一个宏像素(macro-pixel);而后者使用三个数组分开存放YUV三个分量,就像是一个三维平面一样。表2.3中的YUY2到Y211都是打包格式,而IF09到YVU9都是平面格式。(注意:在介绍各种具体格式时,YUV各分量都会带有下标,如Y0、U0、V0表示第一个像素的YUV分量,Y1、U1、V1表示第二个像素的YUV分量,以此类推。)
MEDIASUBTYPE_YUY2 YUY2格式,以4:2:2方式打包
MEDIASUBTYPE_YUYV YUYV格式(实际格式与YUY2相同)
MEDIASUBTYPE_YVYU YVYU格式,以4:2:2方式打包
MEDIASUBTYPE_UYVY UYVY格式,以4:2:2方式打包
MEDIASUBTYPE_AYUV 带Alpha通道的4:4:4 YUV格式
MEDIASUBTYPE_Y41P Y41P格式,以4:1:1方式打包
MEDIASUBTYPE_Y411 Y411格式(实际格式与Y41P相同)
MEDIASUBTYPE_Y211 Y211格式
MEDIASUBTYPE_IF09 IF09格式
MEDIASUBTYPE_IYUV IYUV格式
MEDIASUBTYPE_YV12 YV12格式
MEDIASUBTYPE_YVU9 YVU9格式
表2.3
YUV 采样
YUV 的优点之一是,色度频道的采样率可比 Y 频道低,同时不会明显降低视觉质量。有一种表示法可用来描述 U 和 V 与 Y 的采样频率比例,这个表示法称为 A:B:C 表示法:
| • |
4:4:4 表示色度频道没有下采样。 |
| • |
4:2:2 表示 2:1 的水平下采样,没有垂直下采样。对于每两个 U 样例或 V 样例,每个扫描行都包含四个 Y 样例。 |
| • |
4:2:0 表示 2:1 的水平下采样,2:1 的垂直下采样。 |
| • |
4:1:1 表示 4:1 的水平下采样,没有垂直下采样。对于每个 U 样例或 V 样例,每个扫描行都包含四个 Y 样例。与其他格式相比,4:1:1 采样不太常用,本文不对其进行详细讨论。 |
图 1 显示了 4:4:4 图片中使用的采样网格。灯光样例用叉来表示,色度样例则用圈表示。
图 1. YUV 4:4:4 样例位置
4:2:2 采样的这种主要形式在 ITU-R Recommendation BT.601 中进行了定义。图 2 显示了此标准定义的采样网格。
图 2. YUV 4:2:2 样例位置
4:2:0 采样有两种常见的变化形式。其中一种形式用于 MPEG-2 视频,另一种形式用于 MPEG-1 以及 ITU-T recommendations H.261 和 H.263。图 3 显示了 MPEG-1 方案中使用的采样网格,图 4 显示了 MPEG-2 方案中使用的采样网格。
图 3. YUV 4:2:0 样例位置(MPEG-1 方案)
图 4. YUV 4:2:0 样例位置(MPEG-2 方案)
与 MPEG-1 方案相比,在 MPEG-2 方案与为 4:2:2 和 4:4:4 格式定义的采样网格之间进行转换更简单一些。因此,在 Windows 中首选 MPEG-2 方案,应该考虑将其作为 4:2:0 格式的默认转换方案。
表面定义
本节讲述推荐用于视频呈现的 8 位 YUV 格式。这些格式可以分为几个类别:
| • |
4:4:4 格式,每像素 32 位 |
| • |
4:2:2 格式,每像素 16 位 |
| • |
4:2:0 格式,每像素 16 位 |
| • |
4:2:0 格式,每像素 12 位 |
首先,您应该理解下列概念,这样才能理解接下来的内容:
| • |
表面原点。对于本文讲述的 YUV 格式,原点 (0,0) 总是位于表面的左上角。 |
| • |
跨距。表面的跨距,有时也称为间距,指的是表面的宽度,以字节数表示。对于一个表面原点位于左上角的表面来说,跨距总是正数。 |
| • |
对齐。表面的对齐是根据图形显示驱动程序的不同而定的。表面始终应该 DWORD 对齐,就是说,表面中的各个行肯定都是从 32 位 (DWORD) 边界开始的。对齐可以大于 32 位,但具体取决于硬件的需求。 |
| • |
打包格式与平面格式。YUV 格式可以分为打包 格式和平面 格式。在打包格式中,Y、U 和 V 组件存储在一个数组中。像素被组织到了一些巨像素组中,巨像素组的布局取决于格式。在平面格式中,Y、U 和 V 组件作为三个单独的平面进行存储。 |
4:4:4 格式,每像素 32 位
推荐一个 4:4:4 格式,FOURCC 码为 AYUV。这是一个打包格式,其中每个像素都被编码为四个连续字节,其组织顺序如下所示。
图 5. AYUV 内存布局
标记了 A 的字节包含 alpha 的值。
4:2:2 格式,每像素 16 位
支持两个 4:2:2 格式,FOURCC 码如下:
两个都是打包格式,其中每个巨像素都是编码为四个连续字节的两个像素。这样会使得色度水平下采样乘以系数 2。
YUY2
在 YUY2 格式中,数据可被视为一个不带正负号的 char 值组成的数组,其中第一个字节包含第一个 Y 样例,第二个字节包含第一个 U (Cb) 样例,第三个字节包含第二个 Y 样例,第四个字节包含第一个 V (Cr) 样例,如图 6 所示。
图 6. YUY2 内存布局
如果该图像被看作由两个 little-endian WORD 值组成的数组,则第一个 WORD 在最低有效位 (LSB) 中包含 Y0,在最高有效位 (MSB) 中包含 U。第二个 WORD 在 LSB 中包含 Y1,在 MSB 中包含 V。
YUY2 是用于 Microsoft DirectX® Video Acceleration (DirectX VA) 的首选 4:2:2 像素格式。预期它会成为支持 4:2:2 视频的 DirectX VA 加速器的中期要求。
UYVY
此格式与 YUY2 相同,只是字节顺序是与之相反的 — 就是说,色度字节和灯光字节是翻转的(图 7)。如果该图像被看作由两个 little-endian WORD 值组成的数组,则第一个 WORD 在 LSB 中包含 U,在 MSB 中包含 Y0,第二个 WORD 在 LSB 中包含 V,在 MSB 中包含 Y1。
图 7. UYVY 内存布局
4:2:0 格式,每像素 16 位
推荐两个 4:2:0 每像素 16 位格式,FOURCC 码如下:
两个 FOURCC 码都是平面格式。色度频道在水平方向和垂直方向上都要以系数 2 来进行再次采样。
IMC1
所有 Y 样例都会作为不带正负号的 char 值组成的数组首先显示在内存中。后面跟着所有 V (Cr) 样例,然后是所有 U (Cb) 样例。V 和 U 平面与 Y 平面具有相同的跨距,从而生成如图 8 所示的内存的未使用区域。
图 8. IMC1 内存布局
IMC3
此格式与 IMC1 相同,只是 U 和 V 平面进行了交换:
图 9. IMC3 内存布局
4:2:0 格式,每像素 12 位
推荐四个 4:2:0 每像素 12 位格式,FOURCC 码如下:
| • |
IMC2 |
| • |
IMC4 |
| • |
YV12 |
| • |
NV12 |
在所有这些格式中,色度频道在水平方向和垂直方向上都要以系数 2 来进行再次采样。
IMC2
此格式与 IMC1 相同,只是 V (Cr) 和 U (Cb) 行在半跨距边界处进行了交错。换句话说,就是色度区域中的每个完整跨距行都以一行 V 样例开始,然后是一行在下一个半跨距边界处开始的 U 样例(图 10)。此布局与 IMC1 相比,能够更加高效地利用地址空间。它的色度地址空间缩小了一半,因此整体地址空间缩小了 25%。在各个 4:2:0 格式中,IMC2 是第二首选格式,排在 NV12 之后。
图 10. IMC2 内存布局
IMC4
此格式与 IMC2 相同,只是 U (Cb) 和 V (Cr) 行进行了交换:
图 11. IMC4 内存布局
YV12
所有 Y 样例都会作为不带正负号的 char 值组成的数组首先显示在内存中。此数组后面紧接着所有 V (Cr) 样例。V 平面的跨距为 Y 平面跨距的一半,V 平面包含的行为 Y 平面包含行的一半。V 平面后面紧接着所有 U (Cb) 样例,它的跨距和行数与 V 平面相同(图 12)。
图 12. YV12 内存布局
NV12
所有 Y 样例都会作为由不带正负号的 char 值组成的数组首先显示在内存中,并且行数为偶数。Y 平面后面紧接着一个由不带正负号的 char 值组成的数组,其中包含了打包的 U (Cb) 和 V (Cr) 样例,如图 13 所示。当组合的 U-V 数组被视为一个由 little-endian WORD 值组成的数组时,LSB 包含 U 值,MSB 包含 V 值。NV12 是用于 DirectX VA 的首选 4:2:0 像素格式。预期它会成为支持 4:2:0 视频的 DirectX VA 加速器的中期要求。
图 13. NV12 内存布局 视频监控软件利用海康DS4000系列视频采集卡作为主要的视频采集设备,
利用派尔高P 9600协议作为云台控制协议,因为大部分的快速球都内置
派尔高P、D系列的协议。这样软件的兼容性强一些。
|
|
摘要: 本文介绍了在Windows平台下串行通信的实现机制,讨论了根据不同的条件用Visual C++ 设计串行通信程序的三种方法,并结合实际,实现对温度数据的接收监控。
在实验室和工业应用中,串口是常用的计算机与外部串行设备之间的数据传输通道,由于串行通信方便易行,所以应用广泛。依据不同的条件实现对串口的灵活编程控制是我们所需要的。
在光学镜片镀膜工艺中,用单片机进行多路温度数据采集控制,采集结果以串行方式进入主机,每隔10S向主机发送一次采样数据,主机向单片机发送相关的控制命令,实现串行数据接收,处理,记录,显示,实时绘制曲线。串行通信程序开发环境为 VC++ 6.0。
Windows下串行通信
与以往DOS下串行通信程序不同的是,Windows不提倡应用程序直接控制硬件,而是通过Windows操作系统提供的设备驱动程序来进行数据传递。串行口在Win 32中是作为文件来进行处理的,而不是直接对端口进行操作,对于串行通信,Win 32 提供了相应的文件I/O函数与通信函数,通过了解这些函数的使用,可以编制出符合不同需要的通信程序。与通信设备相关的结构有COMMCONFIG ,COMMPROP,COMMTIMEOUTS,COMSTAT,DCB,MODEMDEVCAPS,MODEMSETTINGS共7个,与通信有关的 Windows API函数共有26个,详细说明可参考MSDN帮助文件。以下将结合实例,给出实现串行通信的三种方法。
实现串行通信的三种方法
方法一:使用VC++提供的串行通信控件MSComm
首先,在对话框中创建通信控件,若Control工具栏中缺少该控件,可通过菜单Project --> Add to Project --> Components and Control插入即可,再将该控件从工具箱中拉到对话框中。此时,你只需要关心控件提供的对 Windows 通讯驱动程序的 API 函数的接口。换句话说,只需要设置和监视MSComm控件的属性和事件。
在ClassWizard中为新创建的通信控件定义成员对象(CMSComm m_Serial),通过该对象便可以对串口属性进行设置,MSComm 控件共有27个属性,这里只介绍其中几个常用属性:
CommPort 设置并返回通讯端口号,缺省为COM1。
Settings 以字符串的形式设置并返回波特率、奇偶校验、数据位、停止位。
PortOpen 设置并返回通讯端口的状态,也可以打开和关闭端口。
Input 从接收缓冲区返回和删除字符。
Output 向发送缓冲区写一个字符串。
InputLen 设置每次Input读入的字符个数,缺省值为0,表明读取接收缓冲 区中的全部内容。
InBufferCount 返回接收缓冲区中已接收到的字符数,将其置0可以清除接收缓 冲区。
InputMode 定义Input属性获取数据的方式(为0:文本方式;为1:二进制方式)。
RThreshold 和 SThreshold 属性,表示在 OnComm 事件发生之前,接收缓冲区或发送缓冲区中可以接收的字符数。
以下是通过设置控件属性对串口进行初始化的实例:
BOOL CSampleDlg:: PortOpen() { BOOL m_Opened; ...... m_Serial.SetCommPort(2); // 指定串口号 m_Serial.SetSettings("4800,N,8,1"); // 通信参数设置 m_Serial.SetInBufferSize(1024); // 指定接收缓冲区大小 m_Serial.SetInBufferCount(0); // 清空接收缓冲区 m_Serial.InputMode(1); // 设置数据获取方式 m_Serial.SetInputLen(0); // 设置读取方式 m_Opened=m_Serail.SetPortOpen(1); // 打开指定的串口 return m_Opened; }
/*监控项目中
bool CVideoSeverDlg::InitQuickBall() {
if(m_ctrlComm.GetPortOpen()) m_ctrlComm.SetPortOpen(FALSE); m_ctrlComm.SetCommPort(1); //选择com1 if( !m_ctrlComm.GetPortOpen()) m_ctrlComm.SetPortOpen(TRUE); //打开串口 else AfxMessageBox("cannot open serial port"); m_ctrlComm.SetSettings("9600,n,8,1"); //波特率9600,无校验,8个数据位,1个停止位 m_ctrlComm.SetInputMode(1); //1:表示以二进制方式检取数据 m_ctrlComm.SetRThreshold(1); //参数1表示每当串口接收缓冲区中有多于或等于1个字符时将引发一个接收数据的OnComm事件 m_ctrlComm.SetInputLen(0); //设置当前接收区数据长度为0 m_ctrlComm.GetInput(); //先预读缓冲区以清除残留数据 MovFlag = FALSE; ZoomFlag = FALSE; IrisFlag = FALSE; FocusFlag = FALSE; return TRUE; }
*/
打开所需串口后,需要考虑串口通信的时机。在接收或发送数据过程中,可能需要监视并响应一些事件和错误,所以事件驱动是处理串行端口交互作用的一种非常有效的方法。使用 OnComm 事件和 CommEvent 属性捕捉并检查通讯事件和错误的值。发生通讯事件或错误时,将触发 OnComm 事件,CommEvent 属性的值将被改变,应用程序检查 CommEvent 属性值并作出相应的反应。在程序中用ClassWizard为CMSComm控件添加OnComm消息处理函数:
void CSampleDlg::OnComm() { ...... switch(m_Serial.GetCommEvent()) { case 2: // 串行口数据接收,处理; } }
/*
void CVideoSeverDlg::OnOnCommMscomm1() { // TODO: Add your control notification handler code here VARIANT variant_inp; //定义一个VARIANT函数 COleSafeArray safearray_inp; //定义一个COleSafeArray 函数 LONG len,k; //定义LONG 函数 BYTE rxdata[2048]; //设置BYTE数组 An 8-bit integerthat is not signed. CString strtemp; //定义一个Cstring临时函数
if(m_ctrlComm.GetCommEvent()==2) //事件值为2表示接收缓冲区内有字符 { ////以下你可以根据自己的通信协议加入处理代码 variant_inp=m_ctrlComm.GetInput(); //读缓冲区 safearray_inp=variant_inp; //VARIANT型变量转换为ColeSafeArray型变量 len=safearray_inp.GetOneDimSize(); //得到有效数据长度 for(k=0;k<len;k++) safearray_inp.GetElement(&k,rxdata+k);//转换为BYTE型数组 for(k=0;k<len;k++) //将数组转换为Cstring型变量 { BYTE bt=*(char*)(rxdata+k); //字符型 strtemp.Format("%c",bt); //将字符送入临时变量strtemp存放 // m_strRXData+=strtemp; //加入接收编辑框对应字符串 } } UpdateData(FALSE); //更新编辑框内容 }
*/
方法二:在单线程中实现自定义的串口通信类
控件简单易用,但由于必须拿到对话框中使用,在一些需要在线程中实现通信的应用场合,控件的使用显得捉襟见肘。此时,若能够按不同需要定制灵活的串口通信类将弥补控件的不足,以下将介绍如何在单线程中建立自定义的通信类。
该通信类CSimpleComm需手动加入头文件与源文件,其基类为CObject,大致建立步骤如下:
(1) 打开串口,获取串口资源句柄
通信程序从CreateFile处指定串口设备及相关的操作属性。再返回一个句柄,该句柄将被用于后续的通信操作,并贯穿整个通信过程。 CreateFile()函数中有几个值得注意的参数设置:串口共享方式应设为0,串口为不可共享设备;创建方式必须为OPEN_EXISTING,即打开已有的串口。对于dwFlagAndAttribute参数,对串口有意义的值是FILE_FLAG_OVERLAPPED,该标志表明串口采用异步通信模式,可进行重叠操作;若值为NULL,则为同步通信方式,在同步方式下,应用程序将始终控制程序流,直到程序结束,若遭遇通信故障等因素,将导致应用程序的永久等待,所以一般多采用异步通信。
(2)串口设置
串口打开后,其属性被设置为默认值,根据具体需要,通过调用GetCommState(hComm,&dcb)读取当前串口设备控制块 DCB(Device Control Block)设置,修改后通过SetCommState(hComm,&dcb)将其写入。再需注意异步读写的超时控制设置,通过COMMTIMEOUTS结构设置超时,调用SetCommTimeouts(hComm,&timeouts)将结果写入。以下是温度监控程序中串口初始化成员函数:
BOOL CSimpleComm::Open( ) { DCB dcb;
m_hIDComDev=CreateFile( "COM2", GENERIC_READ | GENERIC_WRITE, 0,NULL,OPEN_EXISTING,FILE_ATTRIBUTE_ NORMAL|FILE_FLAG_OVE RLAPPED, NULL ); // 打开串口,异步操作 if( m_hIDComDev == NULL ) return( FALSE );
dcb.DCBlength = sizeof( DCB ); GetCommState( m_hIDComDev, &dcb ); // 获得端口默认设置 dcb.BaudRate=CBR_4800; dcb.ByteSize=8; dcb.Parity= NOPARITY; dcb.StopBits=(BYTE) ONESTOPBIT; ...... }
(3)串口读写操作
主要运用ReadFile()与WriteFile()API函数,若为异步通信方式,两函数中最后一个参数为指向OVERLAPPED结构的非空指针,在读写函数返回值为FALSE的情况下,调用GetLastError()函数,返回值为ERROR_IO_PENDING,表明I/O操作悬挂,即操作转入后台继续执行。此时,可以用WaitForSingleObject()来等待结束信号并设置最长等待时间,举例如下:
BOOL bReadStatus; bReadStatus = ReadFile( m_hIDComDev, buffer, dwBytesRead, &dwBytesRead, &m_OverlappedRead ); if(!bReadStatus) { if(GetLastError()==ERROR_IO_PENDING) { WaitForSingleObject(m_OverlappedRead.hEvent,1000); return ((int)dwBytesRead); } return(0); } return ((int)dwBytesRead);
定义全局变量m_Serial作为新建通信类CSimpleComm的对象,通过调用类的成员函数即可实现所需串行通信功能。与方法一相比,方法二赋予串行通信程序设计较大的灵活性,端口的读写可选择较简单的查询式,或通过设置与外设数据发送时间间隔TimeCycle相同的定时器: SetTimer(1,TimeCycle,NULL),进行定时读取或发送。
CSampleView:: OnTimer(UINT nIDEvent) { char InputData[30]; m_Serial.ReadData(InputData,30); // 数据处理 }
若对端口数据的响应时间要求较严格,可采用事件驱动I/O读写,Windows定义了9种串口通信事件,较常用的有:
EV_RXCHAR: 接收到一个字节,并放入输入缓冲区。
EV_TXEMPTY: 输出缓冲区中的最后一个字符发送出去。
EV_RXFLAG: 接收到事件字符(DCB结构中EvtChar成员),放入输入缓冲区。
在用SetCommMask()指定了有用的事件后,应用程序可调用WaitCommEvent()来等待事件的发生。 SetCommMask(hComm,0)可使WaitCommEvent()中止。
方法三 多线程下实现串行通信
方法一,二适用于单线程通信。在很多工业控制系统中,常通过扩展串口连接多个外设,各外设发送数据的重复频率不同,要求后台实时无差错捕捉,采集,处理,记录各端口数据,这就需要在自定义的串行通信类中创建端口监视线程,以便在指定的事件发生时向相关的窗口发送通知消息。
线程的基本概念可详见VC++参考书目,Windows内部的抢先调度程序在活动的线程之间分配CPU时间,Win 32 区分两种不同类型的线程,一种是用户界面线程UI(User Interface Thread),它包含消息循环或消息泵,用于处理接收到的消息;另一种是工作线程(Work Thread),它没有消息循环,用于执行后台任务。用于监视串口事件的线程即为工作线程。
多线程通信类的编写在端口的配置,连接部分与单线程通信类相同,在端口配置完毕后,最重要的是根据实际情况,建立多线程之间的同步对象,如信号灯,临界区,事件等,相关细节可参考VC++ 中的同步类。
一切就绪后即可启动工作线程:
CWinThrea *CommThread = AfxBegin Thread(CommWatchThread, // 线程函数名 (LPVOID) m_pTTYInfo, // 传递的参数 THREAD_PRIORITY_ABOVE_NORMAL, // 设置线程优先级 (UINT) 0, // 最大堆栈大小 (DWORD) CREATE_SUSPENDED , // 创建标志 (LPSECURITY_ATTRIBUTES) NULL); // 安全性标志
同时,在串口事件监视线程中:
if(WaitCommEvent(pTTYInfo->idComDev,&dwEvtMask,NULL)) { if((dwEvtMask & pTTYInfo->dwEvtMask )== pTTYInfo->dwEvtMask) { WaitForSingleObject(pTTYInfo->hPostEvent,0xFFFFFFFF); ResetEvent(pTTYInfo->hPostEvent); // 置同步事件对象为非信号态 ::PostMessage(CSampleView,ID_COM1_DATA,0,0); // 发送通知消息 } }
用PostMessage()向指定窗口的消息队列发送通知消息,相应地,需要在该窗口建立消息与成员函数间的映射,用ON_MESSAGE将消息与成员函数名关联。
BEGIN_MESSAGE_MAP(CSampleView, CView) //{{AFX_MSG_MAP(CSampleView) ON_MESSAGE(ID_COM1_DATA, OnProcessCom1Data) ON_MESSAGE(ID_COM2_DATA, OnProcessCom2Data) ..... //}}AFX_MSG_MAP END_MESSAGE_MAP()
然后在各成员函数中完成对各串口数据的接收处理,但必须保证在下一次监测到有数据到来之前,能够完成所有的中间处理工作。否则将造成数据的捕捉错误。
多线程的实现可以使得各端口独立,准确地实现串行通信,使串口通信具有更广泛的灵活性与严格性,且充分利用了CPU时间。但在具体的实时监控系统中如何协调多个线程,线程之间以何种方式实现同步也是在多线程串行通信程序实现的难点。
以VC++ 6.0 为工具,实现串行通信的三种方法各有利弊,
根据不同需要,选择合适的方法,将达到事半功倍的效果。在温度监控系统中,笔者采用了方法二,在Window 98 ,Windows 95 上运行稳定,取得了良好的效果。
|
所谓的不可见,是指编译器不可预见. 具体实现包括中断例程,多线程都可以改变变量的值. 举个例子: volatile int v; void func() { int a,b; a=5*v; b=5*v; .... } 如果v是个普通的变量,编译器很可能会做这样的优化, 第一次计算出5*v的值后,先赋给a,然后直接又从寄存赋给b, 而不会重新计算5*v. 如果定义成volatile,编译器则不会做任何优化,每次都会 重新读取v的值.
一个变量可以同时被说明为const和volatile吗?可以。const修饰符的含义是变量的值不能被使用了const修饰符的那段代码修改,但这并不意味着它不能被这段代码以外的其它手段修改。例如,在2. 6的例子中,通过一个volatile const指针t来存取timer结构。函数time_addition()本身并不修改t->value的值,因此t->value被说明为const。不过,计算机的硬件会修改这个值,因此t->value又被说明为volatile。如果同时用const和volatile来说明一个变量,那么这两个修饰符随便哪个在先都行,
下面这个程序执行后会有什么错误或者效果: #define MAX 255 int main() { unsigned char A[MAX],i; for (i=0;i<=MAX;i++) A[i]=i; }
解答: MAX=255 数组A的下标范围为:0..MAX-1,这是其一.. 其二.当i循环到255时,循环内执行: A[255]=255; 这句本身没有问题..但是返回for (i=0;i<=MAX;i++)语句时, 由于unsigned char的取值范围在(0..255),i++以后i又为0了..无限循环下去. 注:char类型为一个字节,取值范围是[-128,127],unsigned char [0 ,255]
--------------------------------- 编写用C语言实现的求n阶阶乘问题的递归算法: int factor(int n) { if(n<0) { printf("error"); return 0; } if(n==0||n=1) return 1; else
return n*fact(n-1); }
-------------------------------- 二分查找算法: 1、递归方法实现: int BSearch(elemtype a[],elemtype x,int low,int high) /*在下届为low,上界为high的数组a中折半查找数据元素x*/ { int mid; if(low>high) return -1; mid=(low+high)/2; if(x==a[mid]) return mid; if(x<a[mid]) return(BSearch(a,x,low,mid-1)); else return(BSearch(a,x,mid+1,high)); }
2、非递归方法实现: int BSearch(elemtype a[],keytype key,int n) { int low,high,mid; low=0;high=n-1; while(low<=high) { mid=(low+high)/2; if(a[mid].key==key) return mid; else if(a[mid].key<key) low=mid+1; else high=mid-1; } return -1; }
-------------------------------- 非递归计算如下递归函数的值(斐波拉契): f(1)=1 f(2)=1 f(n)=f(n-1)+f(n-2) n>2
解: int f(int n) { int i,s,s1,s2; s1=1;/*s1用于保存f(n-1)的值*/ s2=1;/*s2用于保存f(n-2)的值*/ s=1; for(i=3;i<=n;i++) { s=s1+s2; s2=s1; s1=s; } return(s); }
------------------------------ Q1:请你分别划划OSI的七层网络结构图,和TCP/IP的五层结构图? 1、OSI每层功能及特点 a 物理层 为数据链路层提供物理连接,在其上串行传送比特流,即所传送数据的单位是比特。此外,该层中还具有确定连接设备的电气特性和物理特性等功能。 b 数据链路层 负责在网络节点间的线路上通过检测、流量控制和重发等手段,无差错地传送以帧为单位的数据。为做到这一点,在每一帧中必须同时带有同步、地址、差错控制及流量控制等控制信息。 c 网络层 为了将数据分组从源(源端系统)送到目的地(目标端系统),网络层的任务就是选择合适的路由和交换节点,使源的传输层传下来的分组信息能够正确无误地按照地址找到目的地,并交付给相应的传输层,即完成网络的寻址功能。 d 传输层 传输层是高低层之间衔接的接口层。数据传输的单位是报文,当报文较长时将它分割成若干分组,然后交给网络层进行传输。传输层是计算机网络协议分层中的最关键一层,该层以上各层将不再管理信息传输问题。 e 会话层 该层对传输的报文提供同步管理服务。在两个不同系统的互相通信的应用进程之间建立、组织和协调交互。例如,确定是双工还是半双工工作。 f 表示层 该层的主要任务是把所传送的数据的抽象语法变换为传送语法,即把不同计算机内部的不同表示形式转换成网络通信中的标准表示形式。此外,对传送的数据加密(或解密)、正文压缩(或还原)也是表示层的任务。 g 应用层 该层直接面向用户,是OSI中的最高层。它的主要任务是为用户提供应用的接口,即提供不同计算机间的文件传送、访问与管理,电子邮件的内容处理,不同计算机通过网络交互访问的虚拟终端功能等。
2、TCP/IP a 网络接口层 这是TCP/IP协议的最低一层,包括有多种逻辑链路控制和媒体访问协议。网络接口层的功能是接收IP数据报并通过特定的网络进行传输,或从网络上接收物理帧,抽取出IP数据报并转交给网际层。 b 网际网层(IP层) 该层包括以下协议:IP(网际协议)、ICMP(Internet Control Message Protocol,因特网控制报文协议)、ARP(Address Resolution Protocol,地址解析协议)、RARP(Reverse Address Resolution Protocol,反向地址解析协议)。该层负责相同或不同网络中计算机之间的通信,主要处理数据报和路由。在IP层中,ARP协议用于将IP地址转换成物理地址,RARP协议用于将物理地址转换成IP地址,ICMP协议用于报告差错和传送控制信息。IP协议在TCP/IP协议组中处于核心地位。 c 传输层 该层提供TCP(传输控制协议)和UDP(User Datagram Protocol,用户数据报协议)两个协议,它们都建立在IP协议的基础上,其中TCP提供可靠的面向连接服务,UDP提供简单的无连接服务。传输层提供端到端,即应用程序之间的通信,主要功能是数据格式化、数据确认和丢失重传等。 d 应用层 TCP/IP协议的应用层相当于OSI模型的会话层、表示层和应用层,它向用户提供一组常用的应用层协议,其中包括:Telnet、SMTP、DNS等。此外,在应用层中还包含有用户应用程序,它们均是建立在TCP/IP协议组之上的专用程序。
3、OSI参考模型和TCP/IP参考模型的区别: a OSI模型有7层,TCP/IP只有4层; b OSI先于协议出现,因此不会偏向于任何一组特定的协议,通用性更强,但有些功能不知该放哪一层上,因此不得不加入一些子层;TCP/IP后于协议出现,仅是将已有协议的一个描述,因此两者配合的非常好;但他不适合其他的协议栈,不容易描述其他非TCP/IP的网络; c OSI中网络层同时支持无连接和面向连接的通信,但在传输层上只支持面向连接的通信;TCP/IP中网络层只支持无连接通信,传输层同时支持两种通信; d 在技术发生变化时,OSI模型比TCP/IP模型中的协议更容易被替换。
---------------------------------------- Q2:请你详细的解释一下IP协议的定义,在哪个层上面,主要有什么作用? TCP与UDP呢? 解:与IP协议配套使用的还有三个协议: ARP-地址解析协议 RARP-逆地址解析协议 ICMP-因特网控制报文协议ICMP IP协议-网际协议 IP地址、IP包头
---------------------------------------- Q3:请问交换机和路由器分别的实现原理是什么?分别在哪个层次上面实现的? 将网络互相连接起来要使用一些中间设备(或中间系统),ISO的术语称之为中继(relay)系统。根据中继系统所在的层次,可以有以下五种中继系统: 1.物理层(即常说的第一层、层L1)中继系统,即转发器(repeater)。 2.数据链路层(即第二层,层L2),即网桥或桥接器(bridge)。 3.网络层(第三层,层L3)中继系统,即路由器(router)。 4.网桥和路由器的混合物桥路器(brouter)兼有网桥和路由器的功能。 5.在网络层以上的中继系统,即网关(gateway). 当中继系统是转发器时,一般不称之为网络互联,因为这仅仅是把一个网络扩大了,而这仍然是一个网络。高层网关由于比较复杂,目前使用得较少。因此一般讨论网络互连时都是指用交换机和路由器进行互联的网络。本文主要阐述交换机和路由器及其区别。
第二层交换机和路由器的区别: 传统交换机从网桥发展而来,属于OSI第二层即数据链路层设备。它根据MAC地址寻址,通过站表选择路由,站表的建立和维护由交换机自动进行。路由器属于OSI第三层即网络层设备,它根据IP地址进行寻址,通过路由表路由协议产生。因特网的路由选择协议:内部网关协议IGP和外部网关协议EGP
第三层交换机和路由器的区别: 在第三层交换技术出现之前,几乎没有必要将路由功能器件和路由器区别开来,他们完全是相同的:提供路由功能正在路由器的工作,然而,现在第三层交换机完全能够执行传统路由器的大多数功能。
综上所述,交换机一般用于LAN-WAN的连接,交换机归于网桥,是数据链路层的设备,有些交换机也可实现第三层的交换。路由器用于WAN-WAN之间的连接,可以解决异性网络之间转发分组,作用于网络层。他们只是从一条线路上接受输入分组,然后向另一条线路转发。这两条线路可能分属于不同的网络,并采用不同协议。相比较而言,路由器的功能较交换机要强大,但速度相对也慢,价格昂贵,第三层交换机既有交换机线速转发报文能力,又有路由器良好的控制功能,因此得以广播应用。 ----------------------------------------------- Q4:请问C++的类和C里面的struct有什么区别? c++中的类具有成员保护功能,并且具有继承,多态这类oo特点,而c里的struct没有 ----------------------------------------------- Q5:请讲一讲析构函数和虚函数的用法和作用? 析构函数也是特殊的类成员函数,它没有返回类型,没有参数,不能随意调用,也没有重载。知识在类对象生命期结束的时候,由系统自动调用释放在构造函数中分配的资源。
这种在运行时,能依据其类型确认调用那个函数的能力称为多态性,或称迟后联编。
另: 析构函数一般在对象撤消前做收尾工作,比如回收内存等工作,虚拟函数的功能是使子类可以用同
名的函数对父类函数进行重载,并且在调用时自动调用子类重载函数,如果是纯虚函数,则纯粹是为了
在子类重载时有个统一的命名而已。
----------------------------------------------- Q6:全局变量和局部变量有什么区别?实怎么实现的?操作系统和编译器是怎么知道的? 全局变量的生命周期是整个程序运行的时间,而局部变量的生命周期则是局部函数或过程调用的时
间段。其实现是由编译器在编译时采用不同内存分配方法。全局变量在main函数调用后,就开始分配,
如果是静态变量则是在main函数前就已经初始化了。而局部变量则是在用户栈中动态分配的(还是建议
看编译原理中的活动记录这一块) ---------------------------------------------- Q7:一些寄存器的题目,主要是寻址和内存管理等一些知识。 。。。 -------------------------------------------- Q8:8086是多少尉的系统?在数据总线上是怎么实现的? 8086系统是16位系统,其数据总线是20位
-------------------------------------- -------------------------------------- C++
一、请填写BOOL , float, 指针变量 与“零值”比较的 if 语句。(10 分) 请写出 BOOL flag 与“零值”比较的 if 语句。(3 分) 标准答案: if ( flag ) if ( !flag ) 如下写法均属不良风格,不得分。 if (flag == TRUE) if (flag == 1 ) if (flag == FALSE) if (flag == 0) 请写出 float x 与“零值”比较的 if 语句。(4 分) 标准答案示例: const float EPSINON = 0.00001; if ((x >= - EPSINON) && (x <= EPSINON) 不可将浮点变量用“==”或“!=”与数字 比较,应该设法转化成“>=”或“<=”此 类形式。 如下是错误的写法,不得分。 if (x == 0.0) if (x != 0.0) 请写出 char *p 与“零值”比较的 if 语句。(3 分) 标准答案: if (p == NULL) if (p != NULL) 如下写法均属不良风格,不得分。 if (p == 0) if (p != 0) if (p) if (!)
二、以下为Windows NT 下的32 位C++程序,请计算sizeof 的值(10 分) void Func ( char str[100]) { 请计算 sizeof( str ) = 4 (2 分) } char str[] = “Hello” ; char *p = str ; int n = 10; 请计算 sizeof (str ) = 6 (2 分) sizeof ( p ) = 4 (2 分) sizeof ( n ) = 4 (2 分) void *p = malloc( 100 ); 请计算 sizeof ( p ) = 4 (2 分)
三、简答题(25 分) 1、头文件中的 ifndef/define/endif 干什么用?(5 分) 答:防止该头文件被重复引用。 2、#include <filename.h> 和 #include “filename.h” 有什么区别?(5 分) 答:对于#include <filename.h> ,编译器从标准库路径开始搜索 filename.h 对于#include “filename.h” ,编译器从用户的工作路径开始搜索 filename.h 3、const 有什么用途?(请至少说明两种)(5 分) 答:(1)可以定义 const 常量 (2)const 可以修饰函数的参数、返回值,甚至函数的定义体。被const 修饰的东 西都受到强制保护,可以预防意外的变动,能提高程序的健壮性。
4、在C++ 程序中调用被 C 编译器编译后的函数,为什么要加 extern “C”? (5 分) 答:C++语言支持函数重载,C 语言不支持函数重载。函数被C++编译后在库中的名字 与C 语言的不同。假设某个函数的原型为: void foo(int x, int y); 该函数被C 编译器编译后在库中的名字为_foo , 而C++编译器则会产生像 _foo_int_int 之类的名字。 C++提供了C 连接交换指定符号extern“C”来解决名字匹配问题。
5、请简述以下两个for 循环的优缺点(5 分) for (i=0; i<N; i++) { if (condition) DoSomething(); else DoOtherthing(); } if (condition) { for (i=0; i<N; i++) DoSomething(); } else { for (i=0; i<N; i++) DoOtherthing(); } 优点:程序简洁 缺点:多执行了N-1 次逻辑判断,并且 打断了循环“流水线”作业,使得编译 器不能对循环进行优化处理,降低了效 率。 优点:循环的效率高 缺点:程序不简洁
四、有关内存的思考题(每小题5 分,共20 分) void GetMemory(char *p) { p = (char *)malloc(100); } void Test(void) { char *str = NULL; GetMemory(str); strcpy(str, "hello world"); printf(str); } 请问运行Test 函数会有什么样的结果? 答:程序崩溃。 因为GetMemory 并不能传递动态内存, Test 函数中的 str 一直都是 NULL。 strcpy(str, "hello world");将使程序崩 溃。
char *GetMemory(void) { char p[] = "hello world"; return p; } void Test(void) { char *str = NULL; str = GetMemory(); printf(str); } 请问运行Test 函数会有什么样的结果? 答:可能是乱码。 因为GetMemory 返回的是指向“栈内存” 的指针,该指针的地址不是 NULL,但其原 现的内容已经被清除,新内容不可知。
void GetMemory2(char **p, int num) { *p = (char *)malloc(num); } void Test(void) { char *str = NULL; GetMemory(&str, 100); strcpy(str, "hello"); printf(str); } 请问运行Test 函数会有什么样的结果? 答: (1)能够输出hello (2)内存泄漏 void Test(void) { char *str = (char *) malloc(100); strcpy(str, “hello”); free(str); if(str != NULL) { strcpy(str, “world”); printf(str); } } 请问运行Test 函数会有什么样的结果? 答:篡改动态内存区的内容,后果难以预 料,非常危险。 因为free(str);之后,str 成为野指针, if(str != NULL)语句不起作用。
五、编写strcpy 函数(10 分) 已知strcpy 函数的原型是 char *strcpy(char *strDest, const char *strSrc); 其中strDest 是目的字符串,strSrc 是源字符串。 (1)不调用C++/C 的字符串库函数,请编写函数 strcpy char *strcpy(char *strDest, const char *strSrc); { assert((strDest!=NULL) && (strSrc !=NULL)); // 2分 char *address = strDest; // 2分 while( (*strDest++ = * strSrc++) != ‘\0’ ) // 2分 NULL ; return address ; // 2分 }
(2)strcpy 能把strSrc 的内容复制到strDest,为什么还要char * 类型的返回值? 答:为了实现链式表达式。 // 2 分 例如 int length = strlen( strcpy( strDest, “hello world”) );
六、编写类String 的构造函数、析构函数和赋值函数(25 分) 已知类String 的原型为: class String { public: String(const char *str = NULL); // 普通构造函数 String(const String &other); // 拷贝构造函数 ~ String(void); // 析构函数 String & operate =(const String &other); // 赋值函数 private: char *m_data; // 用于保存字符串 }; 请编写String 的上述4 个函数。 标准答案: // String 的析构函数 String::~String(void) // 3 分 { delete [] m_data; // 由于m_data 是内部数据类型,也可以写成 delete m_data; } // String 的普通构造函数 String::String(const char *str) // 6 分 { if(str==NULL) { m_data = new char[1]; // 若能加 NULL 判断则更好 *m_data = ‘\0’; } else { int length = strlen(str); m_data = new char[length+1]; // 若能加 NULL 判断则更好 strcpy(m_data, str); } } // 拷贝构造函数 String::String(const String &other) // 3 分 { int length = strlen(other.m_data); m_data = new char[length+1]; // 若能加 NULL 判断则更好 strcpy(m_data, other.m_data); } // 赋值函数 String & String::operate =(const String &other) // 13 分 { // (1) 检查自赋值 // 4 分 if(this == &other) return *this; // (2) 释放原有的内存资源 // 3 分 delete [] m_data; // (3)分配新的内存资源,并复制内容 // 3 分 int length = strlen(other.m_data); m_data = new char[length+1]; // 若能加 NULL 判断则更好 strcpy(m_data, other.m_data); // (4)返回本对象的引用 // 3 分 return *this; }
以上内容,大多选自林锐的高质量c++/c编程。
补充一个:a+++b,结果为什么?
就近原则,与编译器无关,很容易记的。 相当于(a++)+b;
------------------------------- winsocket编程
#include <Winsock2.h> #include <stdio.h>
void main() { WORDwVersionRequested; WSADATA wsaData; int err; wVersionRequested = MAKEWORD(1,1); err = WSAStartup(wVersionRequested,&wsaData); if( err != 0){ return; } if(LOBYTE( wsaData.wVersion ) != 1|| HIBYTE( wsaData.wVersion) != 1){ WSACleanup(); return; } SOCKET sockSrv=socket(AF_INET,SOCK_STREAM,0); SOCKADDR_IN addrSrv; addrSrv.sin_addr.S_un.S_addr=htonl(INADDR_ANY); addrSrv.sin_family=AF_INET; addrSrv.sin_port=htons(6000);
bind(sockSrv,(SOCKADDR*)&addrSrv,sizeof(SOCKADDR));
listen(sockSrv,5); SOCKADDR_IN addrClient; int len=sizeof(SOCKADDR);
while(1) { SOCKET sockConn=accept(sockSrv,(SOCKADDR*)&addrClient,&len); char sendBuf[100]; sprint(sendBuf,"Welcome %s to http://www.sunxin.org", inet_ntoa(addrClient.sin_addr)); send(sockConn,sendBuf,strlen(sendBuf)+1,0); char recvBuf[100]; recv(sockConn,recvBuf); printf("%s\n",recvBuf); closesocket(sockConn); WSACleanup(); }
} 注:这是Server端;File->New->Win32 Console Application,工程名:TcpSrv;然后,File->New->C++ Source File,文件名:TcpSrv;在该工程的Setting的Link的Object/library modules项要加入ws2_32.lib
-------------------------------------------
#include <Winsock2.h> #include <stdio.h>
void main() { WORDwVersionRequested; WSADATA wsaData; int err; wVersionRequested = MAKEWORD(1,1); err = WSAStartup(wVersionRequested,&wsaData); if( err != 0){ return; } if(LOBYTE( wsaData.wVersion ) != 1|| HIBYTE( wsaData.wVersion) != 1){ WSACleanup(); return; } SOCKET sockClient=socket(AF_INET,SOCK_STREAM,0);
SOCKADDR_IN addrSrv; addrSrv.sin_addr.S_un.S_addr=inet_addr("127.0.0.1"); addrSrv.sin_family=AF_INET; addrSrv.sin_porthtons(6000); connect(sockClient,(SOCKADDR*)&addrSrv,sizeof(SOCKADDR)); char recvBuf[100]; recv(sockClient,recvBuf,100,0); printf("%s\n",recvBuf); send(sockClient,"This is zhangsan",strlen("This is zhangsan")+1,0);
closesocket(sockClient); WSACleanup();
}
注:这是Client端;File->New->Win32 Console Application,工程名:TcpClient;然后,File->New->C++ Source File,文件名:TcpClient;同理,在该工程的Setting的Link的Object/library modules项要加入ws2_32.lib
-------------------------------------------- C++
#include <iostream.h>
class human { public: human(){ human_num++;}; static int human_num; ~human(){ human_num--; print(); } void print() { cout<<"human num is: "<<human_num<<endl; } protected: private: }; int human::human_num = 0;
human f1(human x) { x.print(); return x; }
int main(int argc, char* argv[]) { human h1; h1.print(); human h2 = f1(h1); h2.print();
return 0; } 输出:
1
1
0
0
-1
-2
----------------------------
分析:
human h1; //调用构造函数,---hum_num = 1; h1.print(); //输出:"human is 1" human h2 = f1(h1); //再调用f1(h1)的过程中,由于函数参数是按值传递对象,调用默认的复制构造函数,它并没有对hum_num++,所以hum_num 仍= 1,所以x.print()输出:"human is 1"; 在推出f1函数时,要销毁X,调用析构函数(human_num--),输出:"human is 0"(,由于该函数返回一个human 对象,所以又调用默认构造函数,创建一个临时对象(human_num = 0;),把临时对象赋给h2,又调用默认构造函数( human_num = 0); h2.print(); //输出: human is 0;
//在退出main()函数是,先销毁h2,调用析构函数(human_num--),输出 "human_num is -1" 然后销毁h1,调用析构函数(--),输出"human_num is -2"
------------------------------- c语言 文件读写
#include "stdio.h" main() { FILE *fp; char ch,filename[10]; scanf("%s",filename); if((fp=fopen(filename,"w")==NULL) { printf("cann't open file\n"); exit(0); } ch=getchar(); while(ch!='#') { fputc(ch,fp); putchar(ch); ch=getchar(); } fclose(fp); } ----------------------------------- c指针 int *p[n];-----指针数组,每个元素均为指向整型数据的指针。 int (*)p[n];------p为指向一维数组的指针,这个一维数组有n个整型数据。 int *p();----------函数带回指针,指针指向返回的值。 int (*)p();------p为指向函数的指针。
----------------------------------- Windows的消息机制1 Windows是一个消息(Message)驱动系统。Windows的消息提供了应用程序之间、应用程序与Windows系统之间进行通信的手段。应用程序想要实现的功能由消息来触发,并且靠对消息的响应和处理来完成。
Windows系统中有两种消息队列:系统消息队列和应用程序消息队列。计算机的所有输入设备由Windows监控。当一个事件发生时,Windows先将输入的消息放入系统消息队列中,再将消息拷贝到相应的应用程序消息队列中。应用程序的消息处理程序将反复检测消息队列,并把检测到的每个消息发送到相应的窗口函数中。这便是一个事件从发生至到达窗口函数必须经历的过程。
必须注意的是,消息并非是抢占性的,无论事件的缓急,总是按照到达的先后派对,依次处理(一些系统消息除外),这样可能使一些实时外部事件得不到及时处理。
----------------------------------- Windows的消息机制2
Windows 中的消息是放在对应的进程的消息队列里的。可以通过GetMessage取得,并且对于一般的消息,此函数返回非零值,但是对于WM_QUIT消息,返回零。可以通过这个特征,结束程序。当取得消息之后,应该先转换消息,再分发消息。所谓转换,就是把键盘码的转换,所谓分发,就是把消息分发给对应的窗口,由对应的窗口处理消息,这样对应窗体的消息处理函数就会被调用。两个函数可以实现这两个功能:TranslateMessage和 DispatchMessage。
另外,需要注意,当我们点击窗口的关闭按钮关闭窗口时,程序并没有自动退出,而是向程序发送了一个 WM_DESTROY消息(其实过程是这样的,首先向程序发送WM_CLOSE消息,默认的处理程序是调用DestroyWindow销毁窗体,从而引发 WM_DESTROY消息),此时在窗体中我们要响应这个消息,如果需要退出程序,那么就要向程序发送WM_QUIT消息(通过 PostQuitMessage实现)。
一个窗体如果想要调用自己的消息处理函数,可以使用SendMessage向自己发消息。
如上所述,大部分(注意是大部分)的消息是这样传递的:首先放到进程的消息队列中,之后由GetMessage取出,转换后,分发给对应的窗口。这种消息成为存储式消息。存储式消息基本上是使用者输入的结果,以击键(如WM_KEYDOWN和WM_KEYUP讯息)、击键产生的字符(WM_CHAR)、鼠标移动(WM_MOUSEMOVE)和鼠标按钮(WM_LBUTTONDOWN)的形式给出。存储式消息还包含时钟消息(WM_TIMER)、更新消息(WM_PAINT)和退出消息(WM_QUIT)。
但是也有的消息是直接发送给窗口的,它们被称为非存储式消息。例如,当WinMain 调用CreateWindow时,Windows将建立窗口并在处理中给窗口消息处理函数发送一个WM_CREATE消息。当WinMain调用 ShowWindow时,Windows将给窗口消息处理函数发送WM_SIZE和WM_SHOWWINDOW消息。当WinMain调用 UpdateWindow时,Windows将给窗口消息处理函数发送WM_PAINT消息。
----------------------------------- Windows的消息机制3 --------------------------------- C++:memset ,memcpy 和strcpy 的根本区别? #include "memory.h"
memset用来对一段内存空间全部设置为某个字符,一般用在对定义的字符串进行初始化为‘ '或‘\0';例:char a[100];memset(a, '\0', sizeof(a)); memcpy用来做内存拷贝,你可以拿它拷贝任何数据类型的对象,可以指定拷贝的数据长度;例:char a[100],b[50]; memcpy(b, a, sizeof(b));注意如用sizeof(a),会造成b的内存地址溢出。
strcpy就只能拷贝字符串了,它遇到'\0'就结束拷贝;例:char a[100],b[50];strcpy(a,b);如用strcpy(b,a),要注意a中的字符串长度(第一个‘\0'之前)是否超过50位,如超过,则会造成b的内存地址溢出。
strcpy 原型:extern char *strcpy(char *dest,char *src); 用法:#include 功能:把src所指由NULL结束的字符串复制到dest所指的数组中。 说明:src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。 返回指向dest的指针。 memcpy 原型:extern void *memcpy(void *dest, void *src, unsigned int count); 用法:#include 功能:由src所指内存区域复制count个字节到dest所指内存区域。 说明:src和dest所指内存区域不能重叠,函数返回指向dest的指针。 memset 原型:extern void *memset(void *buffer, char c, int count); 用法:#include 功能:把buffer所指内存区域的前count个字节设置成字符c。 说明:返回指向buffer的指针。
ASSERT()是干什么用的
ASSERT ()是一个调试程序时经常使用的宏,在程序运行时它计算括号内的表达式,如果表达式为FALSE (0), 程序将报告错误,并终止执行。如果表达式不为0,则继续执行后面的语句。这个宏通常原来判断程序中是否出现了明显非法的数据,如果出现了终止程序以免导致严重后果,同时也便于查找错误。例如,变量n在程序中不应该为0,如果为0可能导致错误,你可以这样写程序: ...... ASSERT( n != 0); k = 10/ n; ...... ASSERT只有在Debug版本中才有效,如果编译为Release版本则被忽略。 assert()的功能类似,它是ANSI C标准中规定的函数,它与ASSERT的一个重要区别是可以用在Release版本中。
system("pause"); 系统的暂停程序,按任意键继续,屏幕会打印,"按任意键继续。。。。。" 省去了使用getchar();
指针参数是如何传递内存的? 如果 函数的参数是一个指针, 不要指望用该指针去申请动态内存。示例7-4-1 中, Test 函数的语句GetMemory(str, 200)并没有使str 获得期望的内存,str 依旧是NULL, 为什么? void GetMemory(char *p, int num) { p = (char *)malloc(sizeof(char) * num); } void Test(void) { char *str = NULL; GetMemory(str, 100); // str 仍然为 NULL strcpy(str, "hello"); // 运行错误 } 示例7-4-1 试图用指针参数申请动态内存
毛病出在函数GetMemory 中。编译器总是要为函数的每个参数制作临时副本,指针 参数p 的副本是 _p,编译器使 _p = p。如果函数体内的程序修改了_p 的内容,就导致 参数p 的内容作相应的修改。这就是指针可以用作输出参数的原因。在本例中,_p 申请 了新的内存,只是把_p 所指的内存地址改变了,但是p 所指的内存地址丝毫未变。(不会执行p =_p)所以函数GetMemory并不能输出任何东西。事实上,每执行一次GetMemory 就会泄露一块内存,因为没有用free 释放内存。 如果非得要用指针参数去申请内存,那么应该改用“指向指针的指针”,见示例7-4-2。 void GetMemory2(char **p, int num) { *p = (char *)malloc(sizeof(char) * num); } void Test2(void) { char *str = NULL; GetMemory2(&str, 100); // 注意参数是 &str,而不是str strcpy(str, "hello"); cout<< str << endl; free(str); } 示例7-4-2 用指向指针的指针申请动态内存 由于“指向指针的指针”这个概念不容易理解,我们可以用函数返回值来传递动态 内存。(很好的方法,可借鉴)这种方法更加简单,见示例7-4-3。 char *GetMemory3(int num) { char *p = (char *)malloc(sizeof(char) * num); return p; } void Test3(void) { char *str = NULL; str = GetMemory3(100); strcpy(str, "hello"); cout<< str << endl; free(str); } 示例7-4-3 用函数返回值来传递动态内存
用函数返回值来传递动态内存这种方法虽然好用,但是常常有人把return 语句用错 了。这里强调不要用return 语句返回指向“栈内存”的指针(多用指向堆指针,记得要free),因为该内存在函数结束时自动消亡,见示例7-4-4。 char *GetString(void) { char p[] = "hello world"; return p; // 编译器将提出警告 } void Test4(void) { char *str = NULL; str = GetString(); // str 的内容是垃圾 cout<< str << endl; } 示例7-4-4 return 语句返回指向“栈内存”的指针用调试器逐步跟踪Test4,发现执行str = GetString 语句后str 不再是NULL 指针,但是str 的内容不是“hello world”而是垃圾。 如果把示例7-4-4 改写成示例7-4-5,会怎么样? char *GetString2(void) { char *p = "hello world"; return p; } void Test5(void) { char *str = NULL; str = GetString2(); cout<< str << endl; } 示例7-4-5 return 语句返回常量字符串 函数Test5 运行虽然不会出错,但是函数GetString2 的设计概念却是错误的。因 为GetString2 内的“hello world”是常量字符串,位于静态存储区,它在程序生命期 内恒定不变。无论什么时候调用GetString2,它返回的始终是同一个“只读”的内存块。
补充一下:
常见的内存错误及其对策 发生内存错误是件非常麻烦的事情。编译器不能自动发现这些错误,通常是在程序 运行时才能捕捉到。而这些错误大多没有明显的症状,时隐时现,增加了改错的难度。 有时用户怒气冲冲地把你找来,程序却没有发生任何问题,你一走,错误又发作了。 常见的内存错误及其对策如下: 内存分配未成功,却使用了它。 编程新手常犯这种错误,因为他们没有意识到内存分配会不成功。常用解决办法是, 在使用内存之前检查指针是否为NULL。如果指针p 是函数的参数,那么在函数的入口 处用assert(p!=NULL)进行检查。如果是用malloc 或new 来申请内存,应该用if(p==NULL) 或if(p!=NULL)进行防错处理。(注:非常重要) 内存分配虽然成功,但是尚未初始化就引用它。 犯这种错误主要有两个起因:一是没有初始化的观念;二是误以为内存的缺省初值 全为零,导致引用初值错误(例如数组)。 内存的缺省初值究竟是什么并没有统一的标准,尽管有些时候为零值,我们宁可信
其无不可信其有。所以无论用何种方式创建数组,都别忘了赋初值,即便是赋零值也不 可省略,不要嫌麻烦。 .. 内存分配成功并且已经初始化,但操作越过了内存的边界。 例如在使用数组时经常发生下标“多1”或者“少1”的操作。特别是在for 循环语 句中,循环次数很容易搞错,导致数组操作越界。 .. 忘记了释放内存,造成内存泄露。 含有这种错误的函数每被调用一次就丢失一块内存。刚开始时系统的内存充足,你 看不到错误。终有一次程序突然死掉,系统出现提示:内存耗尽。 动态内存的申请与释放必须配对,程序中malloc 与free 的使用次数一定要相同, 否则肯定有错误(new/delete 同理)。 .. 释放了内存却继续使用它。 有三种情况: (1)程序中的对象调用关系过于复杂,实在难以搞清楚某个对象究竟是否已经释放了 内存,此时应该重新设计数据结构,从根本上解决对象管理的混乱局面。 (2)函数的return 语句写错了,注意不要返回指向“栈内存”的“指针”或者“引用”, 因为该内存在函数体结束时被自动销毁。 (3)使用free 或delete 释放了内存后,没有将指针设置为NULL。导致产生“野指针”。 .. 【规则7-2-1】用malloc 或new 申请内存之后,应该立即检查指针值是否为NULL。 防止使用指针值为NULL 的内存。 .. 【规则7-2-2】不要忘记为数组和动态内存赋初值。防止将未被初始化的内存作为右 值使用。 .. 【规则7-2-3】避免数组或指针的下标越界,特别要当心发生“多1”或者“少1” 操作。 .. 【规则7-2-4】动态内存的申请与释放必须配对,防止内存泄漏。 .. 【规则7-2-5】用free 或delete 释放了内存之后,立即将指针设置为NULL,防止 产生“野指针”。
内存分配方式有三种: (1) 从静态存储区域分配。内存在程序编译的时候就已经分配好,这块内存在程序的 整个运行期间都存在。例如全局变量,static 变量。 (2) 在栈上创建。在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函 数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集 中,效率很高,但是分配的内存容量有限。 (3) 从堆上分配,亦称动态内存分配。程序在运行的时候用malloc 或new 申请任意 多少的内存,程序员自己负责在何时用free 或delete 释放内存。动态内存的生存 期由我们决定,使用非常灵活,但问题也最多。 常用算法复杂度:
冒泡法,交换法,插入法O(n*n), 快速排序,堆排序O(log2(n)*n),
按照算法的复杂度,从简单到难来分析算法。 第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有 使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种 算法因为涉及树与堆的概念,所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是算法本身比较 奇特,值得参考(编程的角度)。同时也可以让我们从另外的角度来认识这个问题。 第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数 可以对任何数据类型排序。 一、简单排序算法 由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境 下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么 问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。
1.冒泡法: 这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡: #include <iostream.h>
void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i<Count;i++) { for(int j=Count-1;j>=i;j--) { if(pData[j]<pData[j-1]) { iTemp = pData[j-1]; pData[j-1] = pData[j]; pData[j] = iTemp; } } } }
void main() { int data[] = {10,9,8,7,6,5,4}; BubbleSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; }
倒序(最糟情况) 第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次
其他: 第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次
上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换, 显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意,我们给出O方法的定义:
若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没 学好数学呀,对于编程数学是非常重要的!!!)
现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的 有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换), 复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的 原因,我们通常都是通过循环次数来对比算法。
2.交换法: 交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。 #include <iostream.h> void ExchangeSort(int* pData,int Count) { int iTemp; for(int i=0;i<Count-1;i++) { for(int j=i+1;j<Count;j++) { if(pData[j]<pData[i]) { iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; } } } }
void main() { int data[] = {10,9,8,7,6,5,4}; ExchangeSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次
其他: 第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次
从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样 也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以 只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。
3.选择法——交换法的小小变形 现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下) 这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中 选择最小的与第二个交换,这样往复下去。 #include <iostream.h> void SelectSort(int* pData,int Count) { int iTemp; int iPos; for(int i=0;i<Count-1;i++) { iTemp = pData[i]; iPos = i; for(int j=i+1;j<Count;j++) { if(pData[j]<iTemp) { iTemp = pData[j]; iPos = j; } } pData[iPos] = pData[i]; pData[i] = iTemp; } }
void main() { int data[] = {10,9,8,7,6,5,4}; SelectSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次) 第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次) 循环次数:6次 交换次数:2次
其他: 第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。
4.插入法: (稍作了解即可) 插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张 #include <iostream.h> void InsertSort(int* pData,int Count) { int iTemp; int iPos; for(int i=1;i<Count;i++) { iTemp = pData[i]; iPos = i-1; while((iPos>=0) && (iTemp<pData[iPos])) { pData[iPos+1] = pData[iPos]; iPos--; } pData[iPos+1] = iTemp; } }
void main() { int data[] = {10,9,8,7,6,5,4}; InsertSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; }
倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次) 第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次) 第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次) 循环次数:6次 交换次数:3次
其他: 第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次) 第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次) 第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次) 循环次数:4次 交换次数:2次
上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是, 因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单 排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似 选择法),但我们每次要进行与内层循环相同次数的‘='操作。正常的一次交换我们需要三次‘=' 而这里显然多了一些,所以我们浪费了时间。
最终,我个人认为,在简单排序算法中,选择法是最好的。
二、高级排序算法: 高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。 它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后 把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使 用这个过程(最容易的方法——递归)。
1.快速排序: #include <iostream.h>
void run(int* pData,int left,int right) { int i,j; int middle,iTemp; i = left; j = right; middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)
//当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); }
void QuickSort(int* pData,int Count) { run(pData,0,Count-1); }
void main() { int data[] = {10,9,8,7,6,5,4}; QuickSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; }
这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况 1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。 2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。 第一层递归,循环n次,第二层循环2*(n/2)...... 所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变 成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大??呵呵,你完全 不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。 如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢 于快速排序(因为要重组堆)。
三、其他排序 1.双向冒泡:(了解即可) 通常的冒泡是单向的,而这里是双向的,也就是说还要进行反向的工作。 代码看起来复杂,仔细理一下就明白了,是一个来回震荡的方式。 写这段代码的作者认为这样可以在冒泡的基础上减少一些交换(我不这么认为,也许我错了)。 反正我认为这是一段有趣的代码,值得一看。 #include <iostream.h> void Bubble2Sort(int* pData,int Count) { int iTemp; int left = 1; int right =Count -1; int t; do { //正向的部分 for(int i=right;i>=left;i--) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } left = t+1;
//反向的部分 for(i=left;i<right+1;i++) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } right = t-1; }while(left<=right); }
void main() { int data[] = {10,9,8,7,6,5,4}; Bubble2Sort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; }
2.SHELL排序——在cpl中看过了,挺好的算法 这个排序非常复杂,看了程序就知道了。 首先需要一个递减的步长,这里我们使用的是9、5、3、1(最后的步长必须是1)。 工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元素的排序 以次类推。 #include <iostream.h> void ShellSort(int* pData,int Count) { int step[4]; step[0] = 9; step[1] = 5; step[2] = 3; step[3] = 1;
int iTemp; int k,s,w; for(int i=0;i<4;i++) { k = step[i]; s = -k; for(int j=k;j<Count;j++) { iTemp = pData[j]; w = j-k;//求上step个元素的下标 if(s ==0) { s = -k; s++; pData[s] = iTemp; } while((iTemp<pData[w]) && (w>=0) && (w<=Count)) { pData[w+k] = pData[w]; w = w-k; } pData[w+k] = iTemp; } } }
void main() { int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1}; ShellSort(data,12); for (int i=0;i<12;i++) cout<<data[i]<<" "; cout<<"\n"; } 呵呵,程序看起来有些头疼。不过也不是很难,把s==0的块去掉就轻松多了,这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。 这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法:“由于复杂的数学原因 避免使用2的幂次步长,它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并 “超出本书讨论范围”的原因(我也不知道过程),我们只有结果了。
四、基于模板的通用排序: 这个程序我想就没有分析的必要了,大家看一下就可以了。不明白可以在论坛上问。 MyData.h文件 /////////////////////////////////////////////////////// class CMyData { public: CMyData(int Index,char* strData); CMyData(); virtual ~CMyData();
int m_iIndex; int GetDataSize(){ return m_iDataSize; }; const char* GetData(){ return m_strDatamember; }; //这里重载了操作符: CMyData& operator =(CMyData &SrcData); bool operator <(CMyData& data ); bool operator >(CMyData& data );
private: char* m_strDatamember; int m_iDataSize; }; ////////////////////////////////////////////////////////
MyData.cpp文件 //////////////////////////////////////////////////////// CMyData::CMyData(): m_iIndex(0), m_iDataSize(0), m_strDatamember(NULL) { }
CMyData::~CMyData() { if(m_strDatamember != NULL) delete[] m_strDatamember; m_strDatamember = NULL; }
CMyData::CMyData(int Index,char* strData): m_iIndex(Index), m_iDataSize(0), m_strDatamember(NULL) { m_iDataSize = strlen(strData); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,strData); }
CMyData& CMyData::operator =(CMyData &SrcData) { m_iIndex = SrcData.m_iIndex; m_iDataSize = SrcData.GetDataSize(); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,SrcData.GetData()); return *this; }
bool CMyData::operator <(CMyData& data ) { return m_iIndex<data.m_iIndex; }
bool CMyData::operator >(CMyData& data ) { return m_iIndex>data.m_iIndex; } ///////////////////////////////////////////////////////////
////////////////////////////////////////////////////////// //主程序部分 #include <iostream.h> #include "MyData.h"
template <class T> void run(T* pData,int left,int right) { int i,j; T middle,iTemp; i = left; j = right; //下面的比较都调用我们重载的操作符函数 middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)
//当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); }
template <class T> void QuickSort(T* pData,int Count) { run(pData,0,Count-1); }
void main() { CMyData data[] = { CMyData(8,"xulion"), CMyData(7,"sanzoo"), CMyData(6,"wangjun"), CMyData(5,"VCKBASE"), CMyData(4,"jacky2000"), CMyData(3,"cwally"), CMyData(2,"VCUSER"), CMyData(1,"isdong") }; QuickSort(data,8); for (int i=0;i<8;i++) cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n"; cout<<"\n";
10月25日 TCP连接的建立可以简单的称为三次握手,而连接的中止则可以叫做四次握手。
TCP中消息流量通过滑动窗口来控制。
滑动窗口本质上是描述接受方的TCP数据报缓冲区大小的数据,发送方根据这个数据来计算自己最多能发送多长的数据。如果发送方收到接受方的窗口大小为0的TCP数据报,那么发送方将停止发送数据,等到接受方发送窗口大小不为0的数据报的到来。 void converse(LinkList *head) { LinkList *p,*q; p=head->next; head->next=NULL; while(p!=NULL) { q=p->next; p->next=head->next; head->next=p; p=q; }
} 模式匹配的KMP算法详解
这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道,是个比较难理解的算法,今天特把它搞个彻彻底底明明白白。
注意到这是一个改进的算法,所以有必要把原来的模式匹配算法拿出来,其实理解的关键就在这里,一般的匹配算法:
int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; }
匹配的过程非常清晰,关键是当‘失配’的时候程序是如何处理的?回溯,没错,注意到(1)句,为什么要回溯,看下面的例子:
S:aaaaabababcaaa T:ababc
aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc
为什么会发生这样的情况?这是由T串本身的性质决定的,是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的,大没有回溯的必要。
改进的地方也就是这里,我们从T串本身出发,事先就找准了T自身前后部分匹配的位置,那就可以改进算法。
如果不用回溯,那T串下一个位置从哪里开始呢?
还是上面那个例子,T为ababc,如果c失配,那就可以往前移到aba最后一个a的位置,像这样: ...ababd... ababc ->ababc
这样i不用回溯,j跳到前2个位置,继续匹配的过程,这就是KMP算法所在。这个当T[j]失配后,j应该往前跳的值就是j的next值,它是由T串本身固有决定的,与S串无关。
《数据结构》上给了next值的定义: 0 如果j=1 next[j]={Max{k|1<k<j且'p1...pk-1'='pj-k+1...pj-1' 1 其它情况
我当初看到这个头就晕了,其实它就是描述的我前面表述的情况,关于next[1]=0是规定的,这样规定可以使程序简单一些,如果非要定为其它的值只要不和后面的值冲突也是可以的;而那个Max是什么意思,举个例子:
T:aaab
...aaaab... aaab ->aaab ->aaab ->aaab
像这样的T,前面自身部分匹配的部分不止两个,那应该往前跳到第几个呢?最近的一个,也就是说尽可能的向右滑移最短的长度。
OK,了解到这里,就看清了KMP的大部分内容,然后关键的问题是如何求next值?先不管它,先看如何用它来进行匹配操作,也就是说先假设已经有了next值。
将最前面的程序改写成:
int Index_KMP(String S,String T,int pos) { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(j==0 || S[i]==T[j]){++i;++j;} //注意到这里的j==0,和++j的作用就知道为什么规定next[1]=0的好处了 else j=next[j];//i不变(不回溯),j跳动 } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; }
OK,是不是非常简单?还有更简单的,求next值,这也是整个算法成功的关键,从next值的定义来求太恐怖了,怎么求?前面说过了,next值表达的就是T串的自身部分匹配的性质,那么,我只要将T串和T串自身来一次匹配就可以求出来了,这里的匹配过程不是从头一个一个匹配,而是从T[1]和T[2]开始匹配,给出算法如下:
void get_next(String T,int &next[]) { i=1;j=0;next[1]=0; while(i<=T.Length) { if(j==0 || T[i]==T[j]){++i;++j; next[i]=j;/**********(2)*/} else j=next[j]; } }
看这个函数是不是非常像KMP匹配的函数,没错,它就是这么干的!注意到(2)语句逻辑覆盖的时候是T[i]==T[j]以及i前面的、j前面的都匹配的情况下,于是先自增,然后记下来next[i]=j,这样每当i有自增就会求得一个next[i],而j一定会小于等于i,于是对于已经求出来的next,可以继续求后面的next,而next[1]=0是已知,所以整个就这样递推的求出来了,方法非常巧妙。
这样的改进已经是很不错了,但算法还可以改进,注意到下面的匹配情况:
...aaac... aaaa. T串中的'a'和S串中的'c'失配,而'a'的next值指的还是'a',那同样的比较还是会失配,而这样的比较是多余的,如果我事先知道,当T[i]==T[j],那next[i]就设为next[j],在求next值的时候就已经比较了,这样就可以去掉这样的多余的比较。于是稍加改进得到:
void get_nextval(String T,int &next[]) { i=1;j=0;next[1]=0; while(i<=T.Length) { if(j==0 || T[i]==T[j]) { ++i;++j; if(T[i]!=T[j]) next[i]=j; else next[i]=next[j];//消去多余的可能的比较,next再向前跳 } else j=next[j]; } }
匹配算法不变。 KMP算法的时间复杂度为O(n+m)。 中断响应过程: 1.由中断源提出中断请求 2.保护中断现场:标志寄存器FLAGS入栈,当前CS入栈,当前IP入栈; 3.当有多个中断源同时向CPU提出中断请求时,要进行优先级分析; 4.中断源识别,要找到中断服务程序首地址送到CS:IP中; 5.执行中断服务; 6.中断返回. 中断源识别过程: 1.CPU获取中断类型码;//如何获的中断类型码,最重要的你忽略了 2.将中断类型玛乘4得到相应的中断向量; 3.查询中断向量表; 4.找到中断服务程序的首地址送到CS:IP中; 5.转入中断服务程序
1.const的用法: 为什么使用const? 采用符号常量写出的代码更容易维护;指针常常是边读边移动,而不是边写边移动;许多函数参数是只读不写的。const最常见用途是作为数组的界和switch分情况标号(也可以用枚举符代替)
用法1:常量 取代了C中的宏定义,声明时必须进行初始化。const限制了常量的使用方式,并没有描述常量应该如何分配。如果编译器知道了某const的所有使用,它甚至可以不为该const分配空间。最简单的常见情况就是常量的值在编译时已知,而且不需要分配存储。―《C++ Program Language》 用const声明的变量虽然增加了分配空间,但是可以保证类型安全。 C标准中,const定义的常量是全局的,C++中视声明位置而定。
用法2:指针和常量 使用指针时涉及到两个对象:该指针本身和被它所指的对象。将一个指针的声明用const“预先固定”将使那个对象而不是使这个指针成为常量。要将指针本身而不是被指对象声明为常量,必须使用声明运算符*const。 所以出现在 * 之前的const是作为基础类型的一部分: char *const cp; //到char的const指针 char const *pc1; //到const char的指针 const char *pc2; //到const char的指针(后两个声明是等同的) 从右向左读的记忆方式: cp is a const pointer to char. pc2 is a pointer to const char.
用法3:const修饰函数传入参数 将函数传入参数声明为const,以指明使用这种参数仅仅是为了效率的原因,而不是想让调用函数能够修改对象的值。同理,将指针参数声明为const,函数将不修改由这个参数所指的对象。 通常修饰指针参数和引用参数: void Fun( const A *in); //修饰指针型传入参数 void Fun(const A &in); //修饰引用型传入参数
用法4:修饰函数返回值 可以阻止用户修改返回值。返回值也要相应的付给一个常量或常指针。
用法5:const修饰成员函数 const对象只能访问const成员函数,而非const对象可以访问任意的成员函数,包括const成员函数; const对象的成员是不能修改的,而通过指针维护的对象确实可以修改的; const成员函数不可以修改对象的数据,不管对象是否具有const性质。编译时以是否修改成员数据为依据进行检查。
2.static的用法: 静态变量作用范围在一个文件内,程序开始时分配空间,结束时释放空间,默认初始化为0,使用时可以改变其值。 静态变量或静态函数只有本文件内的代码才能访问它,它的名字在其它文件中不可见。 用法1:函数内部声明的static变量,可作为对象间的一种通信机制 如果一局部变量被声明为static,那么将只有唯一的一个静态分配的对象,它被用于在该函数的所有调用中表示这个变量。这个对象将只在执行线程第一次到达它的定义使初始化。 用法2:局部静态对象 对于局部静态对象,构造函数是在控制线程第一次通过该对象的定义时调用。在程序结束时,局部静态对象的析构函数将按照他们被构造的相反顺序逐一调用,没有规定确切时间。 用法3:静态成员和静态成员函数 如果一个变量是类的一部分,但却不是该类的各个对象的一部分,它就被成为是一个static静态成员。一个static成员只有唯一的一份副本,而不像常 规的非static成员那样在每个对象里各有一份副本。同理,一个需要访问类成员,而不需要针对特定对象去调用的函数,也被称为一个static成员函 数。 类的静态成员函数只能访问类的静态成员(变量或函数)。
3.extern的用法: extern可以声明其他文件内定义的变量。在一个程序里,一个对象只能定义一次,它可以有多个声明,但类型必须完全一样。如果定义在全局作用域或者名字空间作用域里某一个变量没有初始化,它会被按照默认方式初始化。 将变量或函数声明成外部链接,即该变量或函数名在其它函数中可见。被其修饰的变量(外部变量)是静态分配空间的,即程序开始时分配,结束时释放。 在C++中,还可以指定使用另一语言链接,需要与特定的转换符一起使用。 extern “C” 声明语句 extern “C” { 声明语句块 }
4.volatile的用法: 类型修正符(type-modifier),限定一个对象可被外部进程(操作系统、硬件或并发进程等)改变。volatile与变量连用,可以让变量被不同的线程访问和修改。声明时语法: int volatile vInt; 常用于像中断处理程序之类的异步进程进行内存单元访问。 除了基本类型外,对用户定义类型也可以用volatile类型进行修饰。 注意:可以把一个非volatile int赋给volatile int,但是不能把非volatile对象赋给一个volatile对象。 一个有volatile标识符的类只能访问它接口的子集,一个由类的实现者控制的子集。用户只能用const_cast来获得对类型接口的完全访问。此外,volatile向const一样会从类传递到它的成员。 define是一个宏定义,它不仅可以定义一个常量,还可以定义一段函数体,在编译时直接用所定义的内容替代被定义的宏;
在定义常量方面:
const常量有数据类型,而宏常量没有数据类型。编译器可以对前者进行类型安全检查。而对后者只进行字符替换,没有类型安全检查,并且在字符替换可能会产生意料不到的错误(边际效应)。 用宏定义的常量是要直接替换到程序中去的,所以每用到一次,就要替换一次。如果这个常量比较大,而且又多次使用,就会占用很大的程序空间。而const定义的常量是放在一个固定地址上的,每次使用时只调用其地址即可。
10月24日 几个容易混淆的概念,自己整理了一下
重载是相同范围内,函数名相同,参数不同;
覆盖不同范围内(派生类和基类),函数名相同,参数也相同,基类函数必须有virtual关键字;
重载的意义在于针对同一函数调用提供了多种可选版本; 而覆盖一般是指派生类的成员函数去覆盖基类的(同名)成员函数,使在派生类的作用域内只有派生类自己那个成员函数可见,而要调用基类的同名函数,则需提供显示的域解析符:: 多态是指用指向基类指针调用虚函数时,总能调用到正确的版本。也就是说,如果基类指针实际指向的是某个派生类对象,而这个派生类又覆盖了基类中定义的相应的虚函数,那么通过这个指针调用的成员函数,就是(所期望的)派生类自己定义的那个成员函数。
自己写了一个多态的例子
#include <iostream.h> #include <memory.h>
class CA { int k; public: void f() {cout << "CA::f" << endl; } virtual void f1(){ cout << "CA::f1" << endl;} virtual void f2(){cout << "CA::f2" << endl;} };
class CB : virtual public CA { public: void f1(){ cout << "CB::f1" << endl;} };
class CC : virtual public CA { public: void f2(){ cout << "CC::f2" << endl;} };
class CD : public CB, public CC { public: void f1(){ cout << "CD::f1" << endl;} void f2(){ cout << "CD::f2" << endl;} };
void main() {
CA* aa=new CA; CA* ab=new CB; CA* ac=new CC; CA* ad=new CD;
aa->f1(); aa->f2();
ab->f1(); ac->f2();
ad->f1(); ad->f2(); }
结果: CA::f1
CA::f2
CB::f1
CC::f2
CD::f1
CD::f2
补充一下,刚看到一个隐藏的概念,跟覆盖区别一下
令人迷惑的隐藏规则 本来仅仅区别重载与覆盖并不算困难,但是C++的隐藏规则使问题复杂性陡然增加。 这里“隐藏”是指派生类的函数屏蔽了与其同名的基类函数,规则如下: (1)如果派生类的函数与基类的函数同名,但是参数不同。此时,不论有无virtual 关键字,基类的函数将被隐藏(注意别与重载混淆)。 (2)如果派生类的函数与基类的函数同名,并且参数也相同,但是基类函数没有virtual 关键字。此时,基类的函数被隐藏(注意别与覆盖混淆)。 在CPL书中看到dynamic_cast的用法有些糊涂,在网上看了半天,发现一篇写得还比较不错的文章。
C++通过引进四个新的类型转换操作符克服了C风格类型转换的缺点, 这四个操作符是, static_cast, const_cast, dynamic_cast, 和reinterpret_cast。
1: static_cast
原来你习惯于这样写,
(type) expression
而现在你总应该这样:
static_cast<type>(expression)
例如 int firstNumber, secondNumber; double result = ((double)firstNumber)/secondNumber; 如果用上述新的类型转换方法,你应该这样写: double result = static_cast < double > (firstNumber)/secondNumber; 但是它也有一些限制.例如不能把struct转换成int类型或者把double类型转换成指针类型,
2: const_cast
它用来转换掉对象的const属性. 例如: 如果函数f接受一个int* 参数. 但你想给它传递的是const int * f ( const_cast<int*>( px ) );
3: dynamic_cast
它被用于安全地沿着类的继承关系向下进行类型转换。 你能用dynamic_cast把指向基类的指针或引用转换成指向其派生类或其兄弟类的指针或引用, 而且你能知道转换是否成功。失败的转换将返回空指针(当对指针进行类型转换时)或者抛 出异常(当对引用进行类型转换时). 例如: Bace * pb = new A (); ....... dynamic_cast<A*>(pb) 就将pb转换为其派生类 A 的指针.如果转换失败返回空指针. //或者 dynamic_cast<A&>(*pb) //把*pb的引用转换为A型引用返回. 如果转换失败则抛异常.
但是要注意.这样的转换只能在有虚函数的类之间进行.
4: reinterpret_cast--不推荐
因为函数指针类型之间是不能转换的. 所以你没办法把 一个函数的指针转换 为void *. 在这种情况下可以用reinterpret_cast 来试试. 但除非万不得已 不要这么做. 因为这样的转换指针类型的代码在有些机器上是不行的. 这就是说 它没有可移植性.
篇二 C++风格的类型转换的用法
这是More Effecitve C++里的第二条对类型转换讲的很好,也很基础好懂。 Item M2:尽量使用C++风格的类型转换 仔细想想地位卑贱的类型转换功能(cast),其在程序设计中的地位就象goto语句一样令人鄙视。但是它还不是无法令人忍受,因为当在某些紧要的关头,类型转换还是必需的,这时它是一个必需品。 不过C风格的类型转换并不代表所有的类型转换功能。 一来它们过于粗鲁,能允许你在任何类型之间进行转换。不过如果要进行更精确的类型转换,这会是一个优点。在这些类型转换中存在着巨大的不同,例如把一个指向 const对象的指针(pointer-to-const-object)转换成指向非const对象的指针(pointer-to-non -const -object)(即一个仅仅去除const的类型转换),把一个指向基类的指针转换成指向子类的指针(即完全改变对象类型)。传统的C风格的类型转换不对上述两种转换进行区分。(这一点也不令人惊讶,因为C风格的类型转换是为C语言设计的,而不是为C++语言设计的)。 二来C风格的类型转换在程序语句中难以识别。在语法上,类型转换由圆括号和标识符组成,而这些可以用在C++中的任何地方。这使得回答象这样一个最基本的有关类型转换的问题变得很困难:“在这个程序中是否使用了类型转换?”。这是因为人工阅读很可能忽略了类型转换的语句,而利用象grep的工具程序也不能从语句构成上区分出它们来。 C++通过引进四个新的类型转换操作符克服了C风格类型转换的缺点,这四个操作符是, static_cast, const_cast, dynamic_cast, 和reinterpret_cast。在大多数情况下,对于这些操作符你只需要知道原来你习惯于这样写, (type) expression 而现在你总应该这样写: static_cast < type > (expression) 例如,假设你想把一个int转换成double,以便让包含int类型变量的表达式产生出浮点数值的结果。如果用C风格的类型转换,你能这样写: int firstNumber, secondNumber;
 double result = ((double)firstNumber)/secondNumber; 如果用上述新的类型转换方法,你应该这样写: double result = static_cast < double > (firstNumber)/secondNumber; 这样的类型转换不论是对人工还是对程序都很容易识别。 static_cast 在功能上基本上与C风格的类型转换一样强大,含义也一样。它也有功能上限制。例如,你不能用static_cast象用C风格的类型转换一样把 struct转换成int类型或者把double类型转换成指针类型,另外,static_cast不能从表达式中去除const属性,因为另一个新的类型转换操作符const_cast有这样的功能。 其它新的C++类型转换操作符被用在需要更多限制的地方。const_cast用于类型转换掉表达式的const或volatileness属性。通过使用const_cast,你向人们和编译器强调你通过类型转换想做的只是改变一些东西的 constness或者volatileness属性。这个含义被编译器所约束。如果你试图使用const_cast来完成修改 constness 或者volatileness属性之外的事情,你的类型转换将被拒绝。下面是一些例子: class Widget { }; class SpecialWidget: public Widget { }; void update(SpecialWidget *psw); SpecialWidget sw; // sw 是一个非const 对象。 const SpecialWidget& csw = sw; // csw 是sw的一个引用 // 它是一个const 对象 update( &csw ); // 错误!不能传递一个const SpecialWidget* 变量 // 给一个处理SpecialWidget*类型变量的函数 update(const_cast < SpecialWidget * > ( &csw )); // 正确,csw的const被显示地转换掉( // csw和sw两个变量值在update //函数中能被更新) update((SpecialWidget*) &csw ); // 同上,但用了一个更难识别 //的C风格的类型转换 Widget *pw = new SpecialWidget; update(pw); // 错误!pw的类型是Widget*,但是 // update函数处理的是SpecialWidget*类型 update(const_cast < SpecialWidget * > (pw)); // 错误!const_cast仅能被用在影响 // constness or volatileness的地方上。, // 不能用在向继承子类进行类型转换。 到目前为止,const_cast最普通的用途就是转换掉对象的const属性。 第二种特殊的类型转换符是dynamic_cast,它被用于安全地沿着类的继承关系向下进行类型转换。这就是说,你能用dynamic_cast把指向基类的指针或引用转换成指向其派生类或其兄弟类的指针或引用,而且你能知道转换是否成功。失败的转换将返回空指针(当对指针进行类型转换时)或者抛出异常(当对引用进行类型转换时): Widget *pw;
 update(dynamic_cast < SpecialWidget * > (pw)); // 正确,传递给update函数一个指针 // 是指向变量类型为SpecialWidget的pw的指针 // 如果pw确实指向一个对象, // 否则传递过去的将使空指针。 void updateViaRef(SpecialWidget& rsw); updateViaRef(dynamic_cast < SpecialWidget & > (*pw)); //正确。传递给updateViaRef函数 // SpecialWidget pw 指针,如果pw // 确实指向了某个对象 // 否则将抛出异常 dynamic_casts在帮助你浏览继承层次上是有限制的。它不能被用于缺乏虚函数的类型上(参见条款M24),也不能用它来转换掉constness: int firstNumber, secondNumber;
 double result = dynamic_cast < double > (firstNumber)/secondNumber; // 错误!没有继承关系 const SpecialWidget sw;
 update(dynamic_cast < SpecialWidget * > ( &sw )); // 错误! dynamic_cast不能转换 // 掉const。 如你想在没有继承关系的类型中进行转换,你可能想到static_cast。如果是为了去除const,你总得用const_cast。 这四个类型转换符中的最后一个是reinterpret_cast。使用这个操作符的类型转换,其的转换结果几乎都是执行期定义(implementation-defined)。因此,使用reinterpret_casts的代码很难移植。 reinterpret_casts的最普通的用途就是在函数指针类型之间进行转换。例如,假设你有一个函数指针数组: typedef void (*FuncPtr)(); // FuncPtr is 一个指向函数 // 的指针,该函数没有参数 // 返回值类型为void FuncPtr funcPtrArray[10]; // funcPtrArray 是一个能容纳 // 10个FuncPtrs指针的数组 让我们假设你希望(因为某些莫名其妙的原因)把一个指向下面函数的指针存入funcPtrArray数组: int doSomething(); 你不能不经过类型转换而直接去做,因为doSomething函数对于funcPtrArray数组来说有一个错误的类型。在FuncPtrArray数组里的函数返回值是void类型,而doSomething函数返回值是int类型。 funcPtrArray[0] = &doSomething; // 错误!类型不匹配 reinterpret_cast可以让你迫使编译�
10月23日 例1
class a {}; class b:public a {}; class c:public a {}; class d:public b,c {}; d x; 这时x会有a的两份拷贝,浪费空间,也存在二义性 此时b,c要这样声明: class b:virtual public a {}; class c:virtual public b {}; 代价就是不能用基类对象的指针指向虚拟继承类的对象.
例2
#include <iostream.h> #include <memory.h>
class CA { int k; public: void f() {cout << "CA::f" << endl;} };
class CB : virtual public CA { };
class CC : virtual public CA { };
class CD : public CB, public CC { };
void main() {
CD d; CB d1; d.f(); d1.f(); cout<<sizeof(d)<<" "<<sizeof(d1)<<endl; }
结果
CA::f
CA::f
12 8
此时,当编译器确定d.f()调用的具体含义时,将生成如下的CD结构: ---- |CB| |CC| |CA| ---- 同时,在CB、CC中都分别包含了一个指向CA的vbptr(virtual base table pointer),其中记录的是从CB、CC的元素到CA的元素之间的偏移量。此时,不会生成各子类的函数f标识,除非子类重载了该函数,从而达到“共享”的目的。 也正因此,此时的sizeof(CD) = 12(两个vbptr + sizoef(int)); 所有这一切都是编译期间决定的,只是编译器为了提供这样一个新的语法功能为我们多作了一些事情而已。
如果CA中定义个int aa;则输出16 12;如果CB,CC中个定义一个int变量,则输出24 16
小注:
如若CA中添加一个virtual void f1(){},sizeof(CD) = 16(两个vbptr + sizoef(int)+vptr);
再添加virtual void f2(){},sizeof(CD) = 16不变。原因如下所示。
虚函数的类的程度:不带虚函数的普通类,对象的长度恰好就是所期望的。而带有单个虚函数的对象的长度是普通变量的长度加上一个v o i d指针的长度。它反映出,如果有一个或多个虚函数,编译器在这个结构中插入一个指针( V P T R)。类中有几个虚函数长度之间没有区别,这是因为V P T R指向一个存放地址的表,只需要一个指针,因为所有虚函数地址都包含在这个表中。
在基类中加入最少一个纯虚函数(pure virtual function),可以使基类成为抽象(abstract)类,纯虚函数使用关键字virtual,并在其后
面加上=0。
纯虚函数防止产生VTABLE,但这并不意味着我们不希望对其他函数产生函数体。我们常常希望调用一个函数的基类版本,即便它是虚拟的。把公共
代码放在尽可能靠近我们的类层次根的地方,这是很好的想法。这不仅节省了代码空间,而且能允许使改变的传播变得容易
上述试题的一句话感悟
1 应该知道链式操作,即返回目的地址。assert判断要处理的指针是否非空。
2 对一段new的内存delete以后,要给首地址赋值为NULL,否则会成为“野”指针
3 字符串都以'\0'结尾,字符数组不用,所以用字符串给字符数组赋值时要注意越界问题。
4 unite是所有成员共用一块内存,一个联合变量的长度等于各成员中最长的长度
一个unite例子
[例7.15]设有一个教师与学生通用的表格,教师数据有姓名,年龄,职业,教研室四项。学生有姓名,年龄,职业,班级四项。 编程输入人员数据, 再以表格输出。
main() { struct { char name[10]; int age; char job; union { int class; char office[10]; } depa; }body[2]; int n,i; for(i=0;i<2;i++) { printf("input name,age,job and department/n"); scanf("%s %d %c",body[i].name,&body[i].age,&body[i].job); if(body[i].job=='s') scanf("%d",&body[i].depa.class); else scanf("%s",body[i].depa.office); } printf("name/tage job class/office/n"); for(i=0;i<2;i++) { if(body[i].job=='s') printf("%s/t%3d %3c %d/n",body[i].name,body[i].age,body[i].job,body[i].depa.class); else printf("%s/t%3d %3c %s/n",body[i].name,body[i].age, body[i].job,body[i].depa.office); } }
1.引言
本文的写作目的并不在于提供C/C++程序员求职面试指导,而旨在从技术上分析面试题的内涵。文中的大多数面试题来自各大论坛,部分试题解答也参考了网友的意见。
许多面试题看似简单,却需要深厚的基本功才能给出完美的解答。企业要求面试者写一个最简单的strcpy函数都可看出面试者在技术上究竟达到了怎样的程度,我们能真正写好一个strcpy函数吗?我们都觉得自己能,可是我们写出的strcpy很可能只能拿到10分中的2分。读者可从本文看到strcpy函数从2分到10分解答的例子,看看自己属于什么样的层次。此外,还有一些面试题考查面试者敏捷的思维能力。
分析这些面试题,本身包含很强的趣味性;而作为一名研发人员,通过对这些面试题的深入剖析则可进一步增强自身的内功。
2.找错题
试题1:
void test1() { char string[10]; char* str1 = "0123456789"; strcpy( string, str1 ); } |
试题2:
void test2() { char string[10], str1[10]; int i; for(i=0; i<10; i++) { str1[i] = 'a'; } strcpy( string, str1 ); } |
试题3:
void test3(char* str1) { char string[10]; if( strlen( str1 ) <= 10 ) { strcpy( string, str1 ); } } |
解答:
试题1字符串str1需要11个字节才能存放下(包括末尾的’\0’),而string只有10个字节的空间,strcpy会导致数组越界;
对试题2,如果面试者指出字符数组str1不能在数组内结束可以给3分;如果面试者指出strcpy(string, str1)调用使得从str1内存起复制到string内存起所复制的字节数具有不确定性可以给7分,在此基础上指出库函数strcpy工作方式的给10分;
对试题3,if(strlen(str1) <= 10)应改为if(strlen(str1) < 10),因为strlen的结果未统计’\0’所占用的1个字节。
剖析:
考查对基本功的掌握:
(1)字符串以’\0’结尾;
(2)对数组越界把握的敏感度;
(3)库函数strcpy的工作方式,如果编写一个标准strcpy函数的总分值为10,下面给出几个不同得分的答案:
2分
void strcpy( char *strDest, char *strSrc ) { while( (*strDest++ = * strSrc++) != ‘\0’ ); } |
4分
void strcpy( char *strDest, const char *strSrc ) //将源字符串加const,表明其为输入参数,加2分 { while( (*strDest++ = * strSrc++) != ‘\0’ ); } |
7分
void strcpy(char *strDest, const char *strSrc) { //对源地址和目的地址加非0断言,加3分 assert( (strDest != NULL) && (strSrc != NULL) ); while( (*strDest++ = * strSrc++) != ‘\0’ ); } |
10分
//为了实现链式操作,将目的地址返回,加3分!
char * strcpy( char *strDest, const char *strSrc ) { assert( (strDest != NULL) && (strSrc != NULL) ); char *address = strDest; while( (*strDest++ = * strSrc++) != ‘\0’ ); return address; } |
从2分到10分的几个答案我们可以清楚的看到,小小的strcpy竟然暗藏着这么多玄机,真不是盖的!需要多么扎实的基本功才能写一个完美的strcpy啊!
(4)对strlen的掌握,它没有包括字符串末尾的'\0'。
读者看了不同分值的strcpy版本,应该也可以写出一个10分的strlen函数了,完美的版本为: int strlen( const char *str ) //输入参数const
试题4:
void GetMemory( char *p ) { p = (char *) malloc( 100 ); }
void Test( void ) { char *str = NULL; GetMemory( str ); strcpy( str, "hello world" ); printf( str ); } | 试题5:
char *GetMemory( void ) { char p[] = "hello world"; return p; }
void Test( void ) { char *str = NULL; str = GetMemory(); printf( str ); } | 试题6:
void GetMemory( char **p, int num ) { *p = (char *) malloc( num ); }
void Test( void ) { char *str = NULL; GetMemory( &str, 100 ); strcpy( str, "hello" ); printf( str ); } | 试题7:
void Test( void ) { char *str = (char *) malloc( 100 ); strcpy( str, "hello" ); free( str ); ... //省略的其它语句 } | 解答: 试题4传入中GetMemory( char *p )函数的形参为字符串指针,在函数内部修改形参并不能真正的改变传入形参的值,执行完
char *str = NULL; GetMemory( str ); | 后的str仍然为NULL; 试题5中
char p[] = "hello world"; return p; | 的p[]数组为函数内的局部自动变量,在函数返回后,内存已经被释放。这是许多程序员常犯的错误,其根源在于不理解变量的生存期。 试题6的GetMemory避免了试题4的问题,传入GetMemory的参数为字符串指针的指针,但是在GetMemory中执行 申请内存及赋值语句
| *p = (char *) malloc( num ); | 后未判断内存是否申请成功,应加上:
if ( *p == NULL ) { ...//进行申请内存失败处理 } | 试题7存在与试题6同样的问题,在执行
| char *str = (char *) malloc(100); | 后未进行内存是否申请成功的判断;另外,在free(str)后未置str为空,导致可能变成一个“野”指针,应加上:
试题6的Test函数中也未对malloc的内存进行释放。 剖析: 试题4~7考查面试者对内存操作的理解程度,基本功扎实的面试者一般都能正确的回答其中50~60的错误。但是要完全解答正确,却也绝非易事。 对内存操作的考查主要集中在: (1)指针的理解; (2)变量的生存期及作用范围; (3)良好的动态内存申请和释放习惯。 再看看下面的一段程序有什么错误:
swap( int* p1,int* p2 ) { int *p; *p = *p1; *p1 = *p2; *p2 = *p; } | 在swap函数中,p是一个“野”指针,有可能指向系统区,导致程序运行的崩溃。在VC++中DEBUG运行时提示错误“Access Violation”。该程序应该改为:
swap( int* p1,int* p2 ) { int p; p = *p1; *p1 = *p2; *p2 = p; } | 3.内功题
试题1:分别给出BOOL,int,float,指针变量 与“零值”比较的 if 语句(假设变量名为var)
解答: BOOL型变量:if(!var) int型变量: if(var==0) float型变量: const float EPSINON = 0.00001; if ((x >= - EPSINON) && (x <= EPSINON) 指针变量: if(var==NULL) 剖析: 考查对0值判断的“内功”,BOOL型变量的0判断完全可以写成if(var==0),而int型变量也可以写成if(!var),指针变量的判断也可以写成if(!var),上述写法虽然程序都能正确运行,但是未能清晰地表达程序的意思。 一般的,如果想让if判断一个变量的“真”、“假”,应直接使用if(var)、if(!var),表明其为“逻辑”判断;如果用if判断一个数值型变量(short、int、long等),应该用if(var==0),表明是与0进行“数值”上的比较;而判断指针则适宜用if(var==NULL),这是一种很好的编程习惯。 浮点型变量并不精确,所以不可将float变量用“==”或“!=”与数字比较,应该设法转化成“>=”或“<=”形式。如果写成if (x == 0.0),则判为错,得0分。 试题2:以下为Windows NT下的32位C++程序,请计算sizeof的值
void Func ( char str[100] ) { sizeof( str ) = ? }
void *p = malloc( 100 ); sizeof ( p ) = ? | 解答:
sizeof( str ) = 4 sizeof ( p ) = 4 | 剖析: Func ( char str[100] )函数中数组名作为函数形参时,在函数体内,数组名失去了本身的内涵,仅仅只是一个指针;在失去其内涵的同时,它还失去了其常量特性,可以作自增、自减等操作,可以被修改。 数组名的本质如下: (1)数组名指代一种数据结构,这种数据结构就是数组; 例如:
char str[10]; cout << sizeof(str) << endl; | 输出结果为10,str指代数据结构char[10]。 (2)数组名可以转换为指向其指代实体的指针,而且是一个指针常量,不能作自增、自减等操作,不能被修改;
char str[10]; str++; //编译出错,提示str不是左值 | (3)数组名作为函数形参时,沦为普通指针。 Windows NT 32位平台下,指针的长度(占用内存的大小)为4字节,故sizeof( str ) 、sizeof ( p ) 都为4。 试题3:写一个“标准”宏MIN,这个宏输入两个参数并返回较小的一个。另外,当你写下面的代码时会发生什么事?
解答:
| #define MIN(A,B) ((A) <= (B) ? (A) : (B)) | MIN(*p++, b)会产生宏的副作用 剖析: 这个面试题主要考查面试者对宏定义的使用,宏定义可以实现类似于函数的功能,但是它终归不是函数,而宏定义中括弧中的“参数”也不是真的参数,在宏展开的时候对“参数”进行的是一对一的替换。 程序员对宏定义的使用要非常小心,特别要注意两个问题: (1)谨慎地将宏定义中的“参数”和整个宏用用括弧括起来。所以,严格地讲,下述解答:
#define MIN(A,B) (A) <= (B) ? (A) : (B) #define MIN(A,B) (A <= B ? A : B ) | 都应判0分; (2)防止宏的副作用。 宏定义#define MIN(A,B) ((A) <= (B) ? (A) : (B))对MIN(*p++, b)的作用结果是: ((*p++) <= (b) ? (*p++) : (*p++)) 这个表达式会产生副作用,指针p会作三次++自增操作。 除此之外,另一个应该判0分的解答是:
| #define MIN(A,B) ((A) <= (B) ? (A) : (B)); | 这个解答在宏定义的后面加“;”,显示编写者对宏的概念模糊不清,只能被无情地判0分并被面试官淘汰。
试题4:为什么标准头文件都有类似以下的结构?
#ifndef __INCvxWorksh #define __INCvxWorksh #ifdef __cplusplus
extern "C" { #endif /*...*/ #ifdef __cplusplus }
#endif #endif /* __INCvxWorksh */ |
解答:
头文件中的编译宏
#ifndef __INCvxWorksh #define __INCvxWorksh #endif |
的作用是防止被重复引用。
作为一种面向对象的语言,C++支持函数重载,而过程式语言C则不支持。函数被C++编译后在symbol库中的名字与C语言的不同。例如,假设某个函数的原型为:
该函数被C编译器编译后在symbol库中的名字为_foo,而C++编译器则会产生像_foo_int_int之类的名字。_foo_int_int这样的名字包含了函数名和函数参数数量及类型信息,C++就是考这种机制来实现函数重载的。
为了实现C和C++的混合编程,C++提供了C连接交换指定符号extern "C"来解决名字匹配问题,函数声明前加上extern "C"后,则编译器就会按照C语言的方式将该函数编译为_foo,这样C语言中就可以调用C++的函数了。
试题5:编写一个函数,作用是把一个char组成的字符串循环右移n个。比如原来是“abcdefghi”如果n=2,移位后应该是“hiabcdefgh”
函数头是这样的:
//pStr是指向以'\0'结尾的字符串的指针 //steps是要求移动的n
void LoopMove ( char * pStr, int steps ) { //请填充... } |
解答:
正确解答1:
void LoopMove ( char *pStr, int steps ) { int n = strlen( pStr ) - steps; char tmp[MAX_LEN]; strcpy ( tmp, pStr + n ); strcpy ( tmp + steps, pStr); *( tmp + strlen ( pStr ) ) = '\0'; strcpy( pStr, tmp ); } |
正确解答2:
void LoopMove ( char *pStr, int steps ) { int n = strlen( pStr ) - steps; char tmp[MAX_LEN]; memcpy( tmp, pStr + n, steps ); memcpy(pStr + steps, pStr, n ); memcpy(pStr, tmp, steps ); } |
剖析:
这个试题主要考查面试者对标准库函数的熟练程度,在需要的时候引用库函数可以很大程度上简化程序编写的工作量。
最频繁被使用的库函数包括:
(1) strcpy:Copy a string. headfile <string.h>
char *strcpy( char *strDestination, const char *strSource );
(2) memcpy: Copies characters between buffers,headfile <memory.h> or
<string.h>,void *memcpy( void *dest, const void *src, size_t count );
(3) memset: Sets buffers to a specified character,headfile <memory.h> or
<string.h>, void *memset( void *dest, int c, size_t count );
试题6:已知WAV文件格式如下表,打开一个WAV文件,以适当的数据结构组织WAV文件头并解析WAV格式的各项信息。
WAVE文件格式说明表
|
|
偏移地址 |
字节数 |
数据类型 |
内 容 |
| 文件头
|
00H |
4 |
Char |
"RIFF"标志 |
| 04H |
4 |
int32 |
文件长度 |
| 08H |
4 |
Char |
"WAVE"标志 |
| 0CH |
4 |
Char |
"fmt"标志 |
| 10H |
4 |
|
过渡字节(不定) |
| 14H |
2 |
int16 |
格式类别 |
| 16H |
2 |
int16 |
通道数 |
| 18H |
2 |
int16 |
采样率(每秒样本数),表示每个通道的播放速度 |
| 1CH |
4 |
int32 |
波形音频数据传送速率 |
| 20H |
2 |
int16 |
数据块的调整数(按字节算的) |
| 22H |
2 |
|
每样本的数据位数 |
| 24H |
4 |
Char |
数据标记符"data" |
| 28H |
4 |
int32 |
语音数据的长度 | 解答: 将WAV文件格式定义为结构体WAVEFORMAT:
typedef struct tagWaveFormat { char cRiffFlag[4]; UIN32 nFileLen; char cWaveFlag[4]; char cFmtFlag[4]; char cTransition[4]; UIN16 nFormatTag ; UIN16 nChannels; UIN16 nSamplesPerSec; UIN32 nAvgBytesperSec; UIN16 nBlockAlign; UIN16 nBitNumPerSample; char cDataFlag[4]; UIN16 nAudioLength;
} WAVEFORMAT; | 假设WAV文件内容读出后存放在指针buffer开始的内存单元内,则分析文件格式的代码很简单,为:
WAVEFORMAT waveFormat; memcpy( &waveFormat, buffer,sizeof( WAVEFORMAT ) ); | 直接通过访问waveFormat的成员,就可以获得特定WAV文件的各项格式信息。 剖析: 试题6考查面试者组织数据结构的能力,有经验的程序设计者将属于一个整体的数据成员组织为一个结构体,利用指针类型转换,可以将memcpy、memset等函数直接用于结构体地址,进行结构体的整体操作。 透过这个题可以看出面试者的程序设计经验是否丰富。 试题7:编写类String的构造函数、析构函数和赋值函数,已知类String的原型为:
class String { public: String(const char *str = NULL); // 普通构造函数 String(const String &other); // 拷贝构造函数 ~ String(void); // 析构函数 String & operate =(const String &other); // 赋值函数 private: char *m_data; // 用于保存字符串 }; | 解答:
//普通构造函数
String::String(const char *str) { if(str==NULL) { m_data = new char[1]; // 得分点:对空字符串自动申请存放结束标志'\0'的空 //加分点:对m_data加NULL 判断 *m_data = '\0'; } else { int length = strlen(str); m_data = new char[length+1]; // 若能加 NULL 判断则更好 strcpy(m_data, str); } }
// String的析构函数
String::~String(void) { delete [] m_data; // 或delete m_data; }
//拷贝构造函数
String::String(const String &other) // 得分点:输入参数为const型 { int length = strlen(other.m_data); m_data = new char[length+1]; //加分点:对m_data加NULL 判断 strcpy(m_data, other.m_data); }
//赋值函数
String & String::operate =(const String &other) // 得分点:输入参数为const型 { if(this == &other) //得分点:检查自赋值 return *this; delete [] m_data; //得分点:释放原有的内存资源 int length = strlen( other.m_data ); m_data = new char[length+1]; //加分点:对m_data加NULL 判断 strcpy( m_data, other.m_data ); return *this; //得分点:返回本对象的引用 } | 剖析: 能够准确无误地编写出String类的构造函数、拷贝构造函数、赋值函数和析构函数的面试者至少已经具备了C++基本功的60%以上! 在这个类中包括了指针类成员变量m_data,当类中包括指针类成员变量时,一定要重载其拷贝构造函数、赋值函数和析构函数,这既是对C++程序员的基本要求,也是《Effective C++》中特别强调的条款。 仔细学习这个类,特别注意加注释的得分点和加分点的意义,这样就具备了60%以上的C++基本功!
试题8:请说出static和const关键字尽可能多的作用
解答:
static关键字至少有下列n个作用:
(1)函数体内static变量的作用范围为该函数体,不同于auto变量,该变量的内存只被分配一次,因此其值在下次调用时仍维持上次的值;
(2)在模块内的static全局变量可以被模块内所用函数访问,但不能被模块外其它函数访问;
(3)在模块内的static函数只可被这一模块内的其它函数调用,这个函数的使用范围被限制在声明它的模块内;
(4)在类中的static成员变量属于整个类所拥有,对类的所有对象只有一份拷贝;
(5)在类中的static成员函数属于整个类所拥有,这个函数不接收this指针,因而只能访问类的static成员变量。
const关键字至少有下列n个作用:
(1)欲阻止一个变量被改变,可以使用const关键字。在定义该const变量时,通常需要对它进行初始化,因为以后就没有机会再去改变它了;
(2)对指针来说,可以指定指针本身为const,也可以指定指针所指的数据为const,或二者同时指定为const;
(3)在一个函数声明中,const可以修饰形参,表明它是一个输入参数,在函数内部不能改变其值;
(4)对于类的成员函数,若指定其为const类型,则表明其是一个常函数,不能修改类的成员变量;
(5)对于类的成员函数,有时候必须指定其返回值为const类型,以使得其返回值不为“左值”。例如:
| const classA operator*(const classA& a1,const classA& a2); |
operator*的返回结果必须是一个const对象。如果不是,这样的变态代码也不会编译出错:
classA a, b, c; (a * b) = c; // 对a*b的结果赋值 |
操作(a * b) = c显然不符合编程者的初衷,也没有任何意义。
剖析:
惊讶吗?小小的static和const居然有这么多功能,我们能回答几个?如果只能回答1~2个,那还真得闭关再好好修炼修炼。
这个题可以考查面试者对程序设计知识的掌握程度是初级、中级还是比较深入,没有一定的知识广度和深度,不可能对这个问题给出全面的解答。大多数人只能回答出static和const关键字的部分功能。
4.技巧题
试题1:请写一个C函数,若处理器是Big_endian的,则返回0;若是Little_endian的,则返回1
解答:
int checkCPU() { { union w { int a; char b; } c; c.a = 1; return (c.b == 1); } } |
剖析:
嵌入式系统开发者应该对Little-endian和Big-endian模式非常了解。采用Little-endian模式的CPU对操作数的存放方式是从低字节到高字节,而Big-endian模式对操作数的存放方式是从高字节到低字节。例如,16bit宽的数0x1234在Little-endian模式CPU内存中的存放方式(假设从地址0x4000开始存放)为:
| 内存地址 |
存放内容 |
| 0x4000 |
0x34 |
| 0x4001 |
0x12 |
而在Big-endian模式CPU内存中的存放方式则为:
| 内存地址 |
存放内容 |
| 0x4000 |
0x12 |
| 0x4001 |
0x34 |
32bit宽的数0x12345678在Little-endian模式CPU内存中的存放方式(假设从地址0x4000开始存放)为:
| 内存地址 |
存放内容 |
| 0x4000 |
0x78 |
| 0x4001 |
0x56 |
| 0x4002 |
0x34 |
| 0x4003 |
0x12 |
而在Big-endian模式CPU内存中的存放方式则为:
| 内存地址 |
存放内容 |
| 0x4000 |
0x12 |
| 0x4001 |
0x34 |
| 0x4002 |
0x56 |
| 0x4003 |
0x78 |
联合体union的存放顺序是所有成员都从低地址开始存放,面试者的解答利用该特性,轻松地获得了CPU对内存采用Little-endian还是Big-endian模式读写。如果谁能当场给出这个解答,那简直就是一个天才的程序员。
试题2:写一个函数返回1+2+3+…+n的值(假定结果不会超过长整型变量的范围)
解答:
int Sum( int n ) { return ( (long)1 + n) * n / 2; //或return (1l + n) * n / 2; } |
剖析: 对于这个题,只能说,也许最简单的答案就是最好的答案。下面的解答,或者基于下面的解答思路去优化,不管怎么“折腾”,其效率也不可能与直接return ( 1 l + n ) * n / 2相比!
int Sum( int n ) { long sum = 0; for( int i=1; i<=n; i++ ) { sum += i; } return sum; } |
所以程序员们需要敏感地将数学等知识用在程序设计中。
|