C语言“难啃的硬骨头”之结构体，递归（三）

行者～ABC

2 @5 r- a! O3 j. ^7 [5 \% g
8 |, b! P$ t7 I. \: {

结构体，递归

很多在大学学习C语言的，很多课程都没学完，结构体都没学到，因为从章节的安排来看好像，结构体学习放在教材的后半部分了，弄得很多学生觉得结构体不重要，如果只是应付学校的考试，或者就是为了混个毕业证，的确学的意义不大。

如果想从事编程这个行业，对这个概念还不了解，基本上无法构造数据模型，没有一个业务体是完全使用原生数据类型来完成的，很多高手在设计数据模型的时候，一般先把头文件中的结构体数据整理出来。然后设计好功能函数的参数，以及名字，然后才真正开始写c源码。

* V* _' |) V4 t

如果从节省空间考虑结构体里面的数据放的顺序不一样在内存中占用的空间也不一样，结构体与结构体之间赋值，结构体存在指针那么赋值要特别注意，需要进行深度的赋值。

( j# C; `9 G: |& P7 T( b

递归一般用于从头到位统计或者罗列一些数据，在使用的时候很多初学者都觉得别扭，怎么还能自己调用自己？而且在使用的时候，一定设置好跳出的条件，不然无休止的进行下去，真就成无线死循环了。

对于结构体方面的知识，可以参见此前推送的文章《C语言结构体（struct）最全的讲解（万字干货）》。具体也可以参见大佬的经验：
  ]7 G) n3 s" }& C# O+ R相信大家对于结构体都不陌生。在此，分享出本人对C语言结构体的研究和学习的总结。如果你发现这个总结中有你以前所未掌握的，那本文也算是有点价值了。当然，水平有限，若发现不足之处恳请指出。代码文件test.c我放在下面。在此，我会围绕以下2个问题来分析和应用C语言结构体：

; t9 |6 @0 _# h& q4 S9 B
0 A% y+ a, t, I$ G6 U0 t- c4 ]; V1. C语言中的结构体有何作用2. 结构体成员变量内存对齐有何讲究(重点)

对于一些概念的说明，我就不把C语言教材上的定义搬上来。我们坐下来慢慢聊吧。
, w8 w5 z# I& i
1. 结构体有何作用
) P3 O+ ^/ F  @2 O6 u: x
! w% d! w1 D8 a$ @1 g! g三个月前，教研室里一个学长在华为南京研究院的面试中就遇到这个问题。当然，这只是面试中最基础的问题。如果问你你怎么回答？我的理解是这样的，C语言中结构体至少有以下三个作用：
) T3 h, D! H6 U) E
(1) 有机地组织了对象的属性。
% U! ~# w+ ?- _4 Z0 Y
比如，在STM32的RTC开发中，我们需要数据来表示日期和时间，这些数据通常是年、月、日、时、分、秒。如果我们不用结构体，那么就需要定义6个变量来表示。这样的话程序的数据结构是松散的，我们的数据结构最好是“高内聚，低耦合”的。所以，用一个结构体来表示更好，无论是从程序的可读性还是可移植性还是可维护性皆是：
) K& g9 v! _* H8 @# N; r, l3 X, T (2) 以修改结构体成员变量的方法代替了函数(入口参数)的重新定义。

如果说结构体有机地组织了对象的属性表示结构体“中看”，那么以修改结构体成员变量的方法代替函数(入口参数)的重新定义就表示了结构体“中用”。继续以上面的结构体为例子，我们来分析。假如现在我有如下函数来显示日期和时间：

那么我们只要将一个_calendar_obj这个结构体类型的变量作为实参调用DsipDateTime()即可，DsipDateTime()通过DateTimeVal的成变量来实现内容的显示。如果不用结构体，我们很可能需要写这样的一个函数：

显然这样的形参很不可观，数据结构管理起来也很繁琐。如果某个函数的返回值得是一个表示日期和时间的数据，那就更复杂了。这只是一方面。另一方面，如果用户需要表示日期和时间的数据中还要包含星期(周)，这个时候，如果之前没有用机构体，那么应该在DsipDateTime()函数中在增加一个形参vu8 week：
可见这种方法来传递参数非常繁琐。所以以结构体作为函数的入口参数的好处之一就是函数的声明void DsipDateTime( _calendar_obj DateTimeVal)不需要改变，只需要增加结构体的成员变量，然后在函数的内部实现上对calendar.week作相应的处理即可。这样，在程序的修改、维护方面作用显著。
+ q/ e5 d; C3 p7 @2 M% e6 u8 k
(3) 结构体的内存对齐原则可以提高CPU对内存的访问速度(以空间换取时间)。

# g( l' B6 u5 S% b7 I1 U0 {并且，结构体成员变量的地址可以根据基地址(以偏移量offset)计算。我们先来看看下面的一段简单的程序，对于此程序的分析会在第2部分结构体成员变量内存对齐中详细说明。


* C7 I! b. ~  r& T$ |! E) q程序的运行结果如下(注意：括号内的数据是成员变量的地址的十进制形式)：

+ j7 s9 {3 h( K1 a: G

+ _* X2 f# R) ^+ C" L( J* f: b2. 结构体成员变量内存对齐

首先，我们来分析一下上面程序的运行结果。前三行说明在我的程序中，char型占1个字节，short型占2个字节，long型占4个字节。char_short_long、long_short_char和char_long_short是三个结构体成员相同但是成员变量的排列顺序不同。并且从程序的运行结果来看，
; b1 y4 E* E# @6 }+ N& g 并且，还要注意到，1 byte (char)+ 2 byte (short)+ 4 byte (long) = 7 byte，而不是8 byte。
* J8 c; w: t5 i7 I' O
所以，结构体成员变量的放置顺序影响着结构体所占的内存空间的大小。一个结构体变量所占内存的大小不一定等于其成员变量所占空间之和。如果一个用户程序或者操作系统(比如uC/OS-II)中存在大量结构体变量时，这种内存占用必须要进行优化，也就是说，结构体内部成员变量的排列次序是有讲究的。结构体成员变量到底是如何存放的呢？在这里，我就不卖关子了，直接给出如下结论，在没有#pragma pack宏的情况下：
原则1 结构（struct或联合union）的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小的整数倍开始（比如int在32位机为4字节，则要从4的整数倍地址开始存储）。
原则2 结构体的总大小，也就是sizeof的结果，必须是其内部最大成员的整数倍，不足的要补齐。
8 C1 E- [4 r+ j# R*原则3 结构体作为成员时，结构体成员要从其内部最大元素大小的整数倍地址开始存储。（struct a里存有struct b，b里有char，int，double等元素时，那么b应该从8的整数倍地址处开始存储，因为sizeof(double) = 8 bytes）
这里，我们结合上面的程序来分析(暂时不讨论原则3)。
$ d+ d2 ^9 V1 O/ k% B. E先看看char_short_long和long_short_char这两个结构体，从它们的成员变量的地址可以看出来，这两个结构体符合原则1和原则2。注意，在 char_short_long的成员变量的地址中，char_short_long.s的地址是1244994，也就是说，1244993是“空的”，只是被“占位”了！
再看看char_long_short这个结构体，char_long_short的地址分布情况如下表：
) }  g* e0 G/ m 首先，1244972能被1整除，所以char_long_short.c放在1244972处没有问题(其实，就char型成员变量自身来说，其放在任何地址单元处都没有问题)，根据原则1，在之后的1244973~1244975中都没有能被4(因为sizeof(long)=4bytes)整除的，1244976能被4整除，所以char_long_short.l应该放在1244976处，那么同理，最后一个.s(sizeof(short)=2 bytes)是应该放在1244980处。
+ V, \. {2 E, Y3 h$ ?6 o1 `
是不是这样就结束了？不是，还有原则2。根据原则2的要求，char_long_short这个结构体所占的空间大小应该是其占内存空间最大的成员变量的大小的整数倍。如果我们到此就结束了，那么char_long_short所占的内存空间是1244972~1244981共计10bytes，不符合原则2，所以，必须在最后补齐2个 bytes(1244982~1244983)。
至此，一个结构体的内存布局完成了。
$ L, M* ]! R% Q% ~' C: H" t; R: ^下面我们按照上述原则，来验证这样的分析是不是正确。按上面的分析，地址单元1244973、1244974、1244975以及1244982、1244983都是空的(至少char_long_short未用到，只是“占位”了)。如果我们的分析是正确的，那么，定义这样一个结构体，其所占内存也应该是12 bytes：
2 w7 e$ Z5 _; j
5 u" m& r* i. y7 w9 a* C$ \" [运行结果如下：
0 w3 ^7 u. w2 I; q" z
/ \9 |* ]( Y6 O4 ~* u- k

可见，我们的分析是正确的。至于原则3，大家可以自己编程验证，这里就不再讨论了。
所以，无论你是在VC6.0还是Keil C51，还是Keil MDK中，当你需要定义一个结构体时，只要你稍微留心结构体成员变量内存对齐这一现象，就可以在很大程度上节约mcu的RAM。这一点不仅仅应用于实际编程，在很多大型公司，比如IBM、微软、百度、华为的笔试和面试中，也是常见的。
% R; `6 T: ?- w1 r. b

这三大块硬骨头是学习C语言的绊脚石，下功夫拿掉基本上C语言的大动脉就打通了，那么再去学习别的内容就相对比较简单了。编程学习过程中越是痛苦的时候，学到的东西就会越多，克服过去就会自己的技能，放弃了前面的付出的时间都将清零。越是难学的语言在入门之后，在入门之后越觉得过瘾，而且还容易上瘾。你上瘾了没？还是放弃了？

- S$ z1 d/ s7 T7 ~0 I. k, }4 I
5 V; |) V* E# ~7 ?1 M

刘工在线

学习一下。

taoyulon

挺详细。。