第八章     结构和联合... 1
第九章     动态内存分配... 9
第十章     使用结构和指针（链表实现）... 14

第八章     结构和联合

在C中，使用结构可以把不同类型的值存储在一起。数组是通过下标访问，因为数组的元素长度相同，但是结构并不是这样，每个结构成员都有自己的名字，它们是通过名字来访问的。
 
结构变量属于标量类型，并不是指针类型，和其他任何标题一样，当结构名在表达式中作为右值使用时，它表示存储在结构中的值。当它作为左值使用时，它表示结构存储的内存位置。但是，当数组名在表达式中作为右值使用时，它的值是一个指向数组第一个元素的指针，由于它的值是一个常量指针，所以数组名不能作为左值使用。可以声明指向结构的指针与结构数组。
 

第一个声明会尝试递归下去，但最终结构的长度不能确定下来而编译时出错误；但第二个是一个指针，其在编译时能够确定结构体的长度，一般链表和树都是用这种技巧实现。
 
在位机上，一个指针通常占个字节，而不管它指向什么类型的变量，因为指针是用来存储存储地址的：
    char *p = NULL;
    printf("%d", sizeof(p));//4
    printf("%d", sizeof (char *));//4
 
书上说下面是非法的（原因就是类型名直到声明的末尾才定义，在结构声明的内部它尚定义），但实际上编译可以通过：
    typedefstruct {
       inta;
       struct SELF_REF3 *b;//合法
    } SELF_REF3;
    SELF_REF3 

如果编译器有成员对齐这一要求时，会按照最长类型来分配每一个成员，如上面的a成员，在整型类型长度为4字节的机器上，由于a是一个字符型，虽然本身只需一个字节，但也为a分配了4个字节，这将浪费3个字节的空间，c也是一样，此时需要总共12个字节的空间。如果将短的类型放在一起，这将会节约空间（此时只需要8个字节的空间）：
    typedefstruct ALIGN {
       intb;
       chara;
       char c;
    }ALIGN;
    printf("%d", offsetof(struct ALIGN,b));//0
    printf("%d", offsetof(struct ALIGN,a));//4
    printf("%d", offsetof(struct ALIGN,c));//5
    printf("%d", sizeof (struct ALIGN));//8 

下面与上面也是一样节约空间：
    typedefstruct ALIGN {
       chara;
       char c;
       int b;
    }ALIGN;
    printf("%d", offsetof(struct ALIGN,a));//0
    printf("%d", offsetof(struct ALIGN,c));//1
    printf("%d", offsetof(struct ALIGN,b));//4
    printf("%d", sizeof (struct ALIGN));//8
 
最后看看下面这个程序：
    typedefstruct ALIGN {
       chara;
       charc;
       chard;
       shorte;
       charf;
       charj;
       intb;
    }ALIGN;
    printf("%d", offsetof(struct ALIGN,a));//0
    printf("%d", offsetof(struct ALIGN,c));//1
    printf("%d", offsetof(struct ALIGN,d));//2
    printf("%d", offsetof(struct ALIGN,e));//4
    printf("%d", offsetof(struct ALIGN,f));//6
    printf("%d", offsetof(struct ALIGN,j));//7
    printf("%d", offsetof(struct ALIGN,b));//8
    printf("%d", sizeof (struct ALIGN));//12 
 
 
sizeof操作符能够得出一个结构体的整体长度，包括因边界对齐而路过的那些字节，如果想得到每个成员偏离结构首的字节数，则可以使用offsetof宏。
 
降序排列结构成员的声明可以最大限度地减少结构存储中浪费的内存空间。sizeof返回的值包含了结构中浪费的内存空间。
 
参数结构体
把结构体作为参数传递给一个函数是合法的，但这种做法效率低，因为在传递过程中需要复制整个结构体。
 
void print(registerstruct Trans const * const trans);
在许多的机器中，你可以把参数声明为寄存器变量，从而进一步提高指针传递方案的效率，这对于需要多次访问的变量有很大的效率提升。
 
位段
用signed或unsigned整数地声明位段是个好主意，如果只是声明为int类型，它究竟被解释为有符号数还是无符号数是由编译器决定的。
 
位段的声明与结构类似，但它的成员是一个或多个位的字段，这些不同长度的字段实际上个不同的字符值、64种不同的字段、524288种字体大小。成员size位段过于庞大，无法容纳于一个短整型中，但其他的位段成员又比一个字符还短，所以这里能够利用存储ch和font所剩余的位来用在size位段上，这样就可以使用一个32位的整数来存储整个内容了。上面程序在16位机上是非法的，因为最长的位段定义成了19，而最长也只可能为16，但在32位机上，这个声明将根据下面两种可能的方法创建ch1： 

位段的好处：它能够把长度不同的类型数据包装在一起，位整数的机器上的位段声明可能在16位整数的机器上无法运行，如unsignederror_code :32;  肯定是不能移植了。
3、  位段中的成员在内存中是从左向右分配的还是从右向左分配的。
 
联合
联合的所有成员引用的是内存中的相同位置，当你想在不同的时刻把不同的东西存储于一个位置时，就以使用联合。通过访问不同类型的联合成员时，内存中相同的位组合可以被解释为不同的东西。
 
union u_tag {
    inti;
    floatf;
    char *s;
} u;
int main(int argc, char * argv[]) {
    printf("%d\n", u.i);//0
    u.i=1;
    printf("%d\n", u.i);//1
    printf("%f\n", u.f);//0.000000
    u.f=1.1;
    printf("%f\n", u.f);//1.100000
    //打印的还是最后一次存储的内容
    printf("%f\n", u.i);//1.100000
    //float转换成int
    printf("%d\n", u.i);//1066192077
    return 0;
}
 
联合与结构可以相互嵌套。
 
实际上，联合就是一个结构，它的所有成员相对于基地址的偏移量都为0，此结构空间要大到足够容纳最“宽”的成员。
 
在一个成员长度不同的联合里，分配给联合的内存数量取决于它的最长成员的长度。如果成员的长度相关悬殊，会浪费很多的空间，在这种情况下，最好的方法是在联合中存储指向不同成员的指针而不是直接存储成员本身，因为个成员的类型，而且它必须位于一对花括号里：
    union {
       charc;
       inta;
       floatb;
    } x={'a'};
    printf("%c\n",x.c);//a
    printf("%d\n",x.a);//97

第九章     动态内存分配

当你声明数组时，你必须用一个编译时常量指定数组的长度，但是，数组的长度常常在运行时才知道，所以我们通常采用的方法是声明一个较大的数组，它可以容纳可能出现的最多元素。
 
malloc从内存池中提取一块合适的内存，并向程序返回一个指向这块内存的指针。分配与释放的函数原型如下：
void *malloc(size_t size);
void free(void *pointer);
size_t是一个无符号类型，定义于stdlib.h中，该参数指定了需要分配的内存字节数。
 
malloc所分配的是一块连续的内存。malloc实际分配的内存有可能比你请求的稍微多一点，这是由编译器定义的。
 
如果操作系统无法向malloc提供更多的内存，malloc就返回一个NULL指针。
 
malloc是不知道你所请求的内存是用来存储整数、浮点数、结构还是数组的，所以它返回的是一个类型为void*的指针，而这个类型的指针可以转换为其他任何类型的指针，在某些老式的编译器中，可能要求你在转换时使用强制类型转换。
 
另外还有两个内存分配函数，原型如下：
void *calloc(size_t num_elements, size_t element_size);
void realloc(void *ptr, size_t new_size);
calloc与malloc之间的主要区别是前者在返回指向内存的指针之前把，另一个区别是它们请求内存数量的方式不同，calloc的参数包括所需要元素的数量和每个元素的字节数，根据这些值，它能够计算出总共需要分配的内存。
 
realloc函数用于修改一个碑已经分配的内存块的大小，可以使用一块内存扩大或缩小。扩大时原先的内容依然保留，新增加的内存添加到原先内存块的后面，新内存并未以任何方法进行初始化。缩小时，该内存块尾的部分内存被拿掉，剩余部分内存的原先内容依然保留。如果原先的内存无法改变大小，realloc将分配另一块正确大小的内存，并把原先那块内存的内容复制到新的块上。因此，在使用realloc之后，你主不能再使用指向旧内存的指针，而是应该改用realloc所返回的新的指针。
 
    int i, *pi, *pi2;
    //这块内存将被当作25个整型元素的数组，
    //因为pi是一个指向整型的指针
    pi = malloc(25 * sizeof(int));
    if (pi == NULL) {
       printf("Out of memory!\n");
       exit(1);
    }
    pi2 = pi;
    for (i = 0; i < 25; i++) {
       *pi2++ = 0;
       //或者使用下标，当作数组来使用 pi[i]=*(pi + i)
       //pi[i]=0;
    }
 
常见的动态内存错误：对NULL指针进行解引用操作、对分配的内存进行操作时越过边界、释放并非动态分配的内存、试图释放一块动态分配的内存的一部分、一块动态内存被释放之后被继续使用。
 
使用MALLOC自定义宏来避免上面这些错误，下面程序由三部分组成：一个是定义接口alloc的头文件alloc.h，第二个是接口，第三个是使用接口：
/*
* 定义一个不易发生错误的内存分配器接口
*/
#include<stdlib.h>
#define malloc 不要直接调用malloc!
#define MALLOC(num,type) (type*)alloc((num) * sizeof(type))
externvoid * alloc(size_t size);//接口
                                                                 ——alloc.h
/*
* 实现
*/
#include<stdio.h>
#include"alloc.h"
#undef malloc
void * alloc(size_t size) {
    void * new_mem;
    //请求所需的内存，并检查确实分配成功
    new_mem = malloc(size);
    if (new_mem == NULL) {
       printf("Out of memory!\n");
       exit(1);
    }
    return new_mem;
}
                                                                 ——alloc.c
#include"alloc.h"
/*
* 使用
*/
void function() {
    int * new_memeory;
    //获取一串整型数的空间
    new_memeory = MALLOC(25,int);
}
                                                                 ——a_client.c
 
 
free的参数必须要么是NULL，要么是一个先前从malloc、calloc或realloc返回的值，向free传递一个NULL参数不会产生任何效果。free试图释放一块动态分配内存的一部分也有可能引起问题：
pi = malloc(25 * sizeof(int));
//下面会引发问题
free(pi +5);
释放一内存的一部分是不允许的，动态分配的内存必须整块一起释放。但是，realloc函数可以缩小一块动态分配的内存，有效地释放它尾部的内存。
 
不能访问已经被free函数释放了的内存。
 
分配内存但在使用完毕后不释放将引起内存泄漏
 
动态分配实例
动态分配最常见的一个应用就是为那些长度在运行时才知道的数组分配内存空间。下面是读取一列整数，并排序：
/*
** 读取、排序和打印一列整数.
*/
#include<stdlib.h>
#include<stdio.h>
 
/*
** 该函数由 qsort 用于比较整型值
*/
int compare_integers(voidconst *a, voidconst *b) {
    registerintconst *pa = a;
    registerintconst *pb = b;
 
    return *pa > *pb ? 1 : *pa < *pb ? -1 : 0;
}
 
int main() {
    int *array;
    int n_values;
    int i;
 
    /*
     ** 观察共有多少个值.
     */
    printf("How many values are there? ");
    if (scanf("%d", &n_values) != 1 || n_values <= 0) {
       printf("Illegal number of values.\n");
       exit(EXIT_FAILURE);
    }
 
    /*
     ** 分配内存，用于存储这些值.
     */
    array = malloc(n_values * sizeof(int));
    if (array == NULL) {
       printf("Can't get memory for that many values.\n");
       exit(EXIT_FAILURE);
    }
 
    /*
     ** 读取这些值.
     */
    for (i = 0; i < n_values; i += 1) {
       printf("? ");
       if (scanf("%d", array + i) != 1) {
           printf("Error reading value #%d\n", i);
           exit(EXIT_FAILURE);
       }
    }
 
    /*
     ** 调用库函数进行排序.
     */
    qsort(array, n_values, sizeof(int), compare_integers);
 
    /*
     ** 输出.
     */
    for (i = 0; i < n_values; i += 1)
       printf("%d\n", array[i]);
 
    /*
     ** 释放内存并且退出.
     */
    free(array);
    return EXIT_SUCCESS;
}
 
动态复制字符串：
/*
** 用动态分配内存制作一个字符串的一份拷贝。注意：
** 调用程序应该负责检查这块内存是否成功分配!这样
** 做允许调用程序以任何它所希望的方式对错误作出反应
*/
#include<stdlib.h>
#include<string.h>
 
char *strdup(charconst *string) {
    char *new_string;
    /*
     ** 请求足够长度的内存，用于存储字符串和它的结尾NUL字节.
     */
    new_string = malloc(strlen(string) + 1);
    /*
     ** 如果我们得到内存，就复制字符串.
     */
    if (new_string != NULL)
       strcpy(new_string, string);
    return new_string;
}
该程序将输入的字符串存储到缓冲区，每次读取一行。调用此函数时才可以确定字符串的长度，然后就分配内存用于存储字符串，最后字符串被复制到新内存，这样缓冲区又可以用于读取下一个输入行。这个函数非常方便，也非常有用，尽管标准没有提及，但许多环境都把它作为函数库的一部分。
 
有些C编译器提供了一个称为alloca的函数，它与malloc函数不现是在于它在栈上分配内存，而malloc是在堆上分配内存。在栈上分配内存的主要优点是当分配内存的返回时，这块内存会被自动释放，这是由栈的工作方式决定的，它可以保证不会出现内存泄漏，但这种方式存在缺点，由于函数返回时被分配的内存将消失，所以它不能用于存储那些回传给调用程序的数据。

第十章     使用结构和指针（链表实现）

单链表
/*
** 单链表的插入，链表为升序
*/
#include<stdlib.h>
#include<stdio.h>
typedefstruct NODE {
    struct NODE *link;
    intvalue;
} Node;
 
#define    FALSE  0
#define TRUE  1
 
/*
* 如果节点插在最前面，则需要使用根指针的值，
* 所以这里使用了二级指针将根指针的地址也传递
* 过去，这样便于修改根指针的指向
*/
int sll_insert(Node **rootp, int new_value) {
    /*
     * 前驱节点，会成为新节点的前驱节点，也可能为NULL
     */
    Node *previous;
    /*
     * next节点，即第一个大于或等于新节点的节点，最后会
     * 成会新节点的后继节点，可能为NULL
     */
    Node *next;
    Node *new;//新节点
    previous = NULL;//刚开始时前驱节点指针指向NULL
//初始化后继节点，刚开始时与根节点一样指向第一个节点
    next = *rootp;
 
    /*
     ** 如果没有到达链尾，且没有找到一个大于或等于新节点
     ** 的节点时，继续往下找
     */
    while (next != NULL && next->value < new_value) {
       previous = next;
       next = next->link;
    }
 
    //动态创建新的节点
    new = (Node *) malloc(sizeof(Node));
    if (new == NULL)
       return FALSE;
    new->value = new_value;
 
    //设定next域，让next节点成为新节点的下一节点
    new->link = next;
   
    //如果需要在最前面插入时
    if (previous == NULL)
       //此时需要修改根节点的指向，让它指向新的节点
       *rootp = new;
    else//如果插入是在链表的中间或者末尾时
       previous->link = new;
    return TRUE;
}
int main(int argc, char **argv) {
    Node *root = NULL;
    Node **rootp = &root;
    sll_insert(rootp, 2);
    sll_insert(rootp, 5);
    sll_insert(rootp, 3);
    sll_insert(rootp, 0);
    sll_insert(rootp, 1);
    sll_insert(rootp, 4);
    while (root != NULL) {
       printf("%d", root->value);//012345
       root = root->link;
    }
}

 
单链表的优化插入操作
看上去，把一个节点插入到链表的起始位置必须作为一种特殊情况进行处理，因为此时插入新节点需要修改的是指针是根指针，而对于其他任何节点，修改的是前一个节点（previous）的link字段，这两个看上去不同的操作实际上是一样的。
消除这种特殊情况的关键在于：我们必须认识到，链表中的每个节点都有一个指向它的指针。对于第1个节点，这个指针是根指针；对于其他节点，这个指针是前一节点的link字段，相同点是每个节点都有一个指针指向它，至于该指针是不是位于一个节点内部则不重要，我们个节点和指向它的指针：

如果新值插入到第1个节点之前，这个指针就必须进行修改。下面是第2个节点和指向它的指针：

如果新值需要插入到第2个节点之前，那么前一节点的link指针必须进行修改。

现在我们只需要拥有一个指向插入位置的下一节点的指针（next），以及一个“指向next节点的link字段”的指针（linkp），除此外，我们就不再需要一个用来保存指向插入位置的前一节点的指针（previous），下面是赋值语句（next = *linkp）执行后的各变量情况：

当移动到下一个节点时，我们保存一个“指向next节点的link字段的”指针（linkp），而不是保存一个指向前一个节点的指针（previous）：

注，个节点，根节点的个节点的；如果内存不
** 足，返回-1；如果插入成功，函数返回1。
*/
#include<stdlib.h>
#include<stdio.h>
 
typedefstruct NODE {
    struct NODE *fwd;
    struct NODE *bwd;
    intvalue;
} Node;
 
int dll_insert(Node *rootp, int value) {
    Node *previous;//指向待插入位置的前一节点，
    Node *next;//指向待插入位置的后一节点，
    Node *new;//指向新的节点
 
    previous = rootp;//初始化时指向根节点
    //previous不能为NULL，rootp不能传递为NULL
    next = previous->fwd;//初始化时指向第一个节点或NULL
    /*
     * 如果没有达到链尾，且新的值比next值大时继续向后找
     */
    while (next != NULL && next->value < value) {
       //查看value是否已经存在于链表中，如果是就返回
       if (next->value == value) {
           return 0;
       }
       previous = next;
       next = previous->fwd;
    }
 
    new = (Node *) malloc(sizeof(Node));
    if (new == NULL) {
       return -1;
    }
    new->value = value;
 
    if (rootp->fwd == NULL && rootp->bwd == NULL) {//如果链表为空
       new->fwd = NULL;
       rootp->fwd = new;
       new->bwd = NULL;
       rootp->bwd = new;
    } elseif (previous == rootp) {//如果插入位置为链表首时
       new->fwd = next;
       rootp->fwd = new;
       new->bwd = NULL;
       next->bwd = new;
    } elseif (next == NULL) {//如果插入位置为链表尾时
       new->fwd = NULL;
       previous->fwd = new;
       new->bwd = previous;
       rootp->bwd = new;
    } else {
       //如果插入位置为链表中间时
       new->fwd = next;
       previous->fwd = new;
       new->bwd = previous;
       next->bwd = new;
    }
    return 1;
}
 
int main(int argc, char **argv) {
    //  Node root = { NULL, NULL, 0 };
 
    /*
     * 为了节省空间，root的值成员是多余的，
     * 可以使用动态分配出来
     *
     * 如果不是动态分配出来的，则可以使用如
     * 下结构来实现：
     * struct DLL_NODE;
     * struct DLL_POINTERS{//根节点结构
     *      struct DLL_NODE * fwd;
     *      struct DLL_NODE * bwd;
     * };
     * struct DLL_NODE{//节点
     *      struct DLL_POINTERS pointers;
     *      int value;
     * };
     *
     */
    Node* root2 = malloc(sizeof(Node) - sizeof(int));
    root2->bwd = NULL;
    root2->fwd = NULL;
    dll_insert(root2, 2);
    dll_insert(root2, 5);
    dll_insert(root2, 3);
    dll_insert(root2, 0);
    dll_insert(root2, 1);
    dll_insert(root2, 4);
    //从前向后遍历
    Node* tmp = root2->fwd;
    while (tmp != NULL) {
       printf("%d", tmp->value);//012345
       tmp = tmp->fwd;
    }
    //从后向前遍历
    tmp = root2->bwd;
    while (tmp != NULL) {
       printf("%d", tmp->value);//543210
       tmp = tmp->bwd;
    }
}