6.087 Practical Programming in C, lec6

User-defined datatypes, structs, unions, bitfields. Memory allocation. Linked lists, binary trees.

Structure

Definition: A structure is a collection of related variables (ofpossibly different types) grouped together under a single name.

• Variables can be declared like any other built in data-type.

struct point ptA;

• Initialization is done by specifying values of every member.

struct point ptA={10,20};

• Assignment operator copies every member of the structure (becareful with pointers).

Structure的功能是在已有数据类型的基础上定义一种新的数据类型，也就是说，Struct中的元素也可以是Struct。数据类型规定了其对象在内存中的值域范围和可以对其进行的操作。由此观之，Struct并不难实现，其内存大小就是定义Struct中各元素的大小之和，取值空间由其内部各子元素确定，操作符也只有sizeof等少数几个可以使用。实际上Struct占用内存空间的大小往往并不是简单的子元素大小相加，因为操作系统会为了实现优化而进行数据对齐，这样Struct所占用的空间会变大。

与面向对象中的类对象不同，struct的赋值不是传引用，而是直接赋值。当然类对象也是赋值，因为他们自身就是引用，说传引用是一种习惯吧，更大的可能是我弄错了，很久没看Java和C++，都有些遗忘了。

• Individual members can be accessedusing ’.’ operator.

struct point pt={10,20}; int x=pt.x; int y=pt.y;

• If structure is nested, multiple’.’ are required

struct rectangle

{

struct point tl;/∗ top left ∗/

struct point br; /∗ bot right ∗/

} ;

struct rectangle rect;

int tlx = rect.tl.x; /∗ nested ∗/

int tly = rect.tl.y ;

一个Struct至少要包含这些内容：首地址，struct的大小或尾地址，每个成员的类型，每个成员的首地址。”.”可以看作一个运算符，左侧是struct的名称，右侧是成员名称，使用这两个参数就可以找到子元素，如果结果仍为struct，那么就可以嵌套使用”.”，右侧添加个相应的子元素。

Structure pointers

• Structures are copied element wise.

• For large structures it is moreefficient to pass pointers.

void foo(struct point ∗ pp);

struct point pt;

foo(&pt) ;

• Members can be accesses fromstructure pointers using ’->’ operator.

struct point p = { 10, 20 };

struct point ∗ pp=&p;

pp−>x = 10; / ∗ changes p . x∗ /

int y = pp−>y ; /∗ same as y=p .y ∗/

Other ways to access structure members?

struct point p = { 10, 20 };

struct point ∗ pp=&p;

(∗pp).x = 10; /∗ changes p.x ∗/

int y = (∗pp).y; /∗ same as y=p.y ∗/

why is the () required?

最后那行的问题的答案我想是与执行顺序有关，”*”和”.”都是一目操作符，执行序为从右到左，因此需要用()来修正执行顺序。

Arrays of structures

• Declaring arrays of int: int x[10];

• Declaring arrays of structure:struct point p[10];

• Initializing arrays of int: int x[4]={0,20,10,2};

• Initializing arrays of structure:

struct point p[3]={0,1,10,20,30,12};

struct point p[3]={{0,1},{10,20},{30,12}};

我感觉struct的数组定义和系统自定义类型没什么区别，也应该是这样，因为他们的性质是一样的。

Size of structures

• The size of a structure is greaterthan or equal to the sum of the sizes of its members.

• Alignment

struc t{

char c ;

/ ∗ padding ∗/

int i ;

• Why is this an important issue?libraries, precompiled files, SIMD instructions.

• Members can be explicitly alignedusing compiler extensions.

__attribute__ (( aligned(x ))) /∗gcc∗/

__declspec((aligned(x))) /∗MSVC∗/

struct的体积等于或大于其所有元素体积之和，尤其是并行处理中，这样的安排使程序设计更为容易，好在编译器提供了相应的参数，可以使我们强行进行指令数据对齐，从而防止了二义性。

Union

A union is a variable that may holdobjects of different types/sizes in the same memory location.Example:

union data

{

int idata;

float fdata ;

char ∗ sdata ;

}d1, d2, d3;

d1.idata =10;

d1.fdata =3.14F ;

d1. sdata="hello world" ;

union有些像万能军刀，可以同时担任多种角色。union和struct的不同是C语言笔面试中常考的一道题目，虽然我觉得这种测试十分没有意义和无聊，但还是注意下吧，谁让咱没有足够强呢。union的体积与其元素中体积最大的相同，因为它要放下所有的类型。union实现起来应该和struct差不多，只需要将每个元素的首地址设为同一个，并在每次赋值时首先将内存清零就可以了。

Dynamic memory allocation

void∗ malloc(size_t n)

• malloc()allocates blocks of memory

• returns apointer to unitialized block of memory on success

• returns NULLon failure.

• the returnedvalue should be cast to appropriate type using ().

int∗ip=(int∗)malloc(sizeof(int)∗100)

void∗ calloc( size_t n,size_t size)

• allocates anarray of n elements each of which is ’size’ bytes.

• initializesmemory to 0

void free(void∗)

• Frees memoryallocated my malloc()

• Common error:accessing memory after calling free

使用malloc时要注意malloc分配的内存并没有初始化，即没有清0，而calloc则将内存初始化为0，不明白产生这种不同的原因四什么。

Linked list

Definition: A dynamic data structure that consists of a sequenceof records where each element contains a link to the next record inthe sequence.

• Linked lists can be singly linked, doubly linked or circular.

For now, we will focus on singlylinked list.

• Every node has a payload and a link to the next node in thelist.

• The start (head) of the list is maintained in a separatevariable.

• End of the list is indicated by NULL (sentinel).

数据结构的出现与struct是密不可分的，没有struct就不会有高效的数据结构。LinkedList的缺点是每个linkedlist只能是某一种类型。面向对象使用继承结构解决了这个问题，一个list中可以存放实际上不同的多种类型（他们的祖先类还是一样的），因此面向对象的list等结构可以叫容器了。

数据结构最强的一点是他们的概念模型很清晰，相当于又增加了一层抽象。从前听一位老师讲数据结构决定算法，一直不理解，这两个不是相辅相成的吗？现在发现那位老师讲的很有道理，因为相对于算法，数据结构是死的，图灵机的一维模型决定了数据结构不会有太多的花样，但算法是活的，算法的执行序可以跳来跳去，还可以利用多种数据结构同时计算。在实际项目中，数据结构一般都是死的，提前定义好的，因此算法往往要围着数据结构转。

Binary trees

• A binary tree is a dynamic data structure where each node hasat most two children. A binary search tree is a binary tree withordering among its children.

• Usually, all elements in the left subtree are assumed to be”less” than the root element and all elements in the rightsubtree are assumed to be "greater" than the root element.

二叉树是树结构中最精简的一种数据结构，容易使用。树在内存中也是线性存储的，之所以能形成树的这种结构，一个重要的原因就是递归的存在。我总感觉递归很magic，记得在数学上图灵机所能计算的全部都是递归函数，可惜我学业不精，过于懈怠，一直没有理解那些数学原理。