C语言（Head First C）-7:数据结构与动态存储

 该系列文章系个人读书笔记及总结性内容，任何组织和个人不得转载进行商业活动！

7:数据结构与动态存储：

 

 一个结构根本不够！

 

 本章内容：

 1）如何用结构指针吧自定义数据类型连接成复杂的大型数据结构；通过创建链表探索其中的基本原理；

 2）通过在堆上动态分配空间来学习如何让数据结构处理可变数量的数据，并在完成后释放空间；（如果嫌清理麻烦，可以学习一下使用valgrind）

 

 保存可变数量的数据：

     为了保存可变数量的数据，需要一样比数组更灵活的东西，即链表；

     链表是一连串的数据；

     链表是一种抽象数据结构；它是通用的，可以用来保存很多不同类型的数据，所以被称为抽象数据结构；

     链表保存了一条数据和一个链向另一条数据的链接；

     要知道链表从哪里开始，就可以遍历链表，可以从一条数据跳到另一条，直到链表的尾部；

 （P1）

 

 在链表中的插入数据：

     相比于数组，链表插入非常快；如果想在数组中插入一个值，就不得不将插入点后所有的数据后移一个位置；

     我们可以用链表来保存可变数量的数据；

 （P2）

 

 如何在C语言中创建链表？

 

 创建递归结构：

     链表中每个结构都需要与下一个结构相连；

     如果一个结构包含一个链向同种结构的链接，这种结构就称为递归结构；

     递归结构中含有指向同种结构的指针；

 场景：

     太平洋上诸多岛屿之间的飞机航线，受天气原因可能会临时变化，存储的结构可以设计如下：

 （Code7_1）

/*
 *
 */

#include <stdio.h>

//island
typedef struct island{//必须为这个结构体命名 因为递归定义的额时候要用
    char * name;
    char * opens;//岛上机场的营业时间
    char * closes;
    struct island * next;//这里不能用别名 必须用结构体名
}island;

int main() {
    
    island island1 = {"A","09:00","17:00",NULL};
    island island2 = {"B","09:00","17:00",NULL};
    island island3 = {"C","09:00","17:00",NULL};
    island island4 = {"D","09:00","17:00",NULL};
    island island5 = {"E","09:00","17:00",NULL};
    
    island1.next = &island2;
    island2.next = &island3;
    island3.next = &island4;
    island4.next = &island5;
    
    //2、3之间插入一个岛
    island island_insert = {"E","09:00","17:00",NULL};
    
    island_insert.next = island2.next;
    island2.next = &island_insert;
    
    return 0;
}

 这里要小心：

     递归结构要有名字；

     在递归结构中，需要包含一个相同类型的指针，C语言的语法不允许用typedef别名声明它，因此必须为结构起一个名字；

 

 接下来，参看Code7_1中实现的飞机航线上诸岛的链表示例:

     初始island的next字段值都设为NULL；C语言中，NULL的值实际上为0，NULL专门用来把某个指针设为0；

     我们需要小心地将每一个island的next变量设为下一个island的地址；

 

 在链表中插入值：

     通过修改指针就可以实现插入island，参看Code7_1；

     这里在中间位置声明了要插入的变量，这在C99和C11标准是可以的，在ANSI C中，必须在函数的顶部声明局部变量；

 

 示例：

     打印链表-航线上岛屿的名字；

 （Code7_2）

/*
 *
 */

#include <stdio.h>

//island
typedef struct island{//必须为这个结构体命名 因为递归定义的额时候要用
    char * name;
    char * opens;//岛上机场的营业时间
    char * closes;
    struct island * next;//这里不能用别名 必须用结构体名
}island;

int display(island * start){
    island * il = start;
    int i;
    for (i = 0 ; il->next != NULL; il = il->next , i++) {
        printf("Island name:%s\nOpen-Close：%s-%s\n",il->name,il->opens,il->closes);
    }
    return i;
}

int main() {
    
    island island1 = {"A","09:00","17:00",NULL};
    island island2 = {"B","09:00","17:00",NULL};
    island island3 = {"C","09:00","17:00",NULL};
    island island4 = {"D","09:00","17:00",NULL};
    island island5 = {"E","09:00","17:00",NULL};
    
    island1.next = &island2;
    island2.next = &island3;
    island3.next = &island4;
    island4.next = &island5;
    
    printf("%i\n",display(&island1));
    
    return 0;
}

 log:

 Island name:A

 Open-Close：09:00-17:00

 Island name:B

 Open-Close：09:00-17:00

 Island name:C

 Open-Close：09:00-17:00

 Island name:D

 Open-Close：09:00-17:00

 4

 

 我们打印了该线路上所经过的岛屿，同时返回了岛屿的数量（没有打印出目的地岛屿，可以使用do-while打印）；

 

 注意：

     不同于J其他语言，如Java，它有内置链表；C语言没有内置数据结构，必须自己创建；

     链表想遍历只能从头开始；这一点不比数组；

     递归定义的结构中使用的是指向其他结构的指针，它不能换成一个递归定义的结构，因为结构在存储器中大小确定，如果递归地赋值自己，两条数据将不一样大；

 

 程序需要动态存储：

 场景：

     从一个不断更新的文件中读取各个岛的信息，比如一个每行只有一个 island name的文件；我们不知道这个文件有多大；

 

 分析：

     前面程序我们是为每个岛都声明了一个变量，但现在我们不知道文件大小，又怎么能知道有多少变量呢？

     我们需要在需要的时候分配新的存储空间；

 

 所以，需要以某种方法创建动态存储：

     到目前为止，我们写过的所有程序都使用静态存储；

     每当想保存一样东西，都在代码中添加一个变量，通常保存在栈中；（栈式存储器中专门用来保存局部变量的区域）

     如果编译时知道需要保存多少数据，那没问题，但程序在运行前往往不知道自己需要多少存储空间；

 

 用堆进行动态存储：

     程序运行时很难在栈上分配大量空间，所以需要堆；

     堆是程序中用来保存长期使用数据的地方；堆上的数据不会自动清除；是保存数据的好地方，比如保存我们的链表；

 

 首先，用malloc()获取空间：

     如果程序在运行时发现有大量数据要保存，要申请一个大容量的存储空间，可以用malloc()函数来申请；

     告诉malloc()需要多少个存储，他会要求操作系统在堆上分配空间；然后会返回一个指针，指向堆上新分配的空间；

     指针就好比这块存储空间的钥匙，可以用它来访问存储器，并跟踪这块区域的使用；

 

 有用有还：

     堆存储器的优点是可以占用很长时间，缺点同样是这个；

     使用栈的时候，无需操心归还存储器，因为这个过程是自动进行的；离开函数事，局部变量会从栈中清除；

     堆则不同，一旦申请就不能再分配，直到告诉C标准库，你已用完；

     堆的空间有限，不断堆积，会造成存储器泄漏，这种错误很常见，却也很难追踪；

 

 调用free()释放存储器：

     malloc()函数分配空间并给出一个指向这块空间的指针；你需要用这个指针访问数据，用完之后，需要用free()函数释放存储器；

 

 看看malloc()和free()如何工作：

 

 用malloc()申请存储器：

     memory allocation（存储器分配）的意思；

     malloc()接收一个参数：所需要的字节数；通常我们不知道确切的字节数，因此malloc()经常与sizeof运算符一起使用；

 像这样：

 #include <stdlib.h>//包含stdlib.h头文件，以使用malloc()和free()函数；

 ...

 malloc(sizeof(island));//表示“给我足够大的空间来保存island结构”

 

 siziof告知某种数据类型在系统中占了多少字节；这种数据类型可以是结构，也可以是int或double这样的基本数据类型；

 malloc()函数为你分配一块存储器，然后返回一个指针；指针中保存了存储器块的起始地址；malloc()返回的是通用指针，即void*类型的指针；

 

 用free()释放存储器：

     如果在一个地方用malloc()分配了存储器，就应该在后面用free()释放他；

     free()需要接收malloc()创建的存储器地址；只要告诉C标准库存储器块从哪里开始，他就能查阅记录，知道要释放多少存储器；

 island * p = malloc(sizeof(island));

 free(p);//表示释放分配的存储器，从堆地址p开始；

 （Code7_3）

/*
 * 创建一条航线之后 打印输出
 */

#include <stdio.h>
#include <stdlib.h>//使用malloc()不要忘记导入头文件
#include <string.h>

//island
typedef struct island{//必须为这个结构体命名 因为递归定义的额时候要用
    char * name;
    char * opens;//岛上机场的营业时间
    char * closes;
    struct island * next;//这里不能用别名 必须用结构体名
}island;

int display(island * start){
    if (start == NULL) {
        return 0;
    }
    island * il = start;
    int i;
    for (i = 1 ; il->next != NULL; il = il->next , i++) {
        printf("Island name:%s  Open-Close：%s-%s\n",il->name,il->opens,il->closes);
    }
    printf("Island name:%s  Open-Close：%s-%s\n",il->name,il->opens,il->closes);
    return i;
}

island * create(char * name){
    island * i = malloc(sizeof(island));
    i->name = name;
    i->opens = "09:00";
    i->closes = "17:00";
    i->next = NULL;
    
    return i;
}

int main() {
    char name[80];
    island * start = NULL;
    island * current = NULL;
    
    puts("输入岛名：（输入S结束）");
    while (scanf("%79s",name) == 1) {
        if (strlen(name) == 1 && (name[0] - 'S' == 0)){
            break;
        }
        island * il = create(name);
        if (start == NULL) {
            start = il;
        }
        if (current != NULL) {
            current->next = il;
        }
        current = il;
        
        puts("输入岛名：");
    }
    
    printf("%i\n",display(start));
    
    //free all
    return 0;
}

 这个程序中，我们定义了一个结构；一个遍历的方法；一个生成的方法；并在main函数中循环输入直到输入S；

 log：

 输入岛名：

 a

 a-输入岛名：

 b

 b-输入岛名：

 c

 c-输入岛名：

 d

 d-输入岛名：

 e

 e-输入岛名：

 f

 f-输入岛名：

 S

 S-Island name:S  Open-Close：09:00-17:00

 Island name:S  Open-Close：09:00-17:00

 Island name:S  Open-Close：09:00-17:00

 Island name:S  Open-Close：09:00-17:00

 Island name:S  Open-Close：09:00-17:00

 Island name:S  Open-Close：09:00-17:00

 6

 

 奇怪的事情发生了，我们用来存储name的字符数组在最后接收字符“S”之后，前面所有的岛的名字全都被莫名的修改了！

 

 问题在于：

     当代码记录岛名字的时候，并没有接收一份完整的name字符，而是记录了name字符串在存储器中的地址；

     这也导致，所有创建的岛都共享了同一个name字符串；一旦局部变量name更新了，前面的岛的名字也就没了；

 

 聚焦字符串复制：

     string.h头文件中创建了一个叫strdup()的函数，可以将字符串的所有字符复制到堆上；

     strdup()函数能够计算出字符串的长度，然后调用malloc()函数在堆上分配相应的空间；

     然后，strdup()函数把所有字符串复制到堆上的新空间；

     因为strdup()是把新字符串放在堆上，所以千万记得要用free()函数释放空间；

 

 用strdup()修改代码：

     i->name = name;    =>     i->name = strdup(name);

     opens和closes只所以不用修改，是因为他们根本就不会变；

 （Code7_4）

/*
 * 创建一条航线之后 打印输出
 */

#include <stdio.h>
#include <stdlib.h>//使用malloc()不要忘记导入头文件
#include <string.h>

//island
typedef struct island{//必须为这个结构体命名 因为递归定义的额时候要用
    char * name;
    char * opens;//岛上机场的营业时间
    char * closes;
    struct island * next;//这里不能用别名 必须用结构体名
}island;

int display(island * start){
    if (start == NULL) {
        return 0;
    }
    island * il = start;
    int i;
    for (i = 1 ; il->next != NULL; il = il->next , i++) {
        printf("Island name:%s  Open-Close：%s-%s\n",il->name,il->opens,il->closes);
    }
    printf("Island name:%s  Open-Close：%s-%s\n",il->name,il->opens,il->closes);
    return i;
}

island * create(char * name){
    island * i = malloc(sizeof(island));
    i->name = strdup(name);
    i->opens = "09:00";
    i->closes = "17:00";
    i->next = NULL;
    
    return i;
}

void release(island * start) {
    island * i = start;
    island * next = NULL;
    for (; i != NULL; i = next) {
        next = i->next;
        free(i->name);//首先需要释放strdup()创建的name字符串
        free(i);
    }
    
}

int main() {
    char name[80];
    island * start = NULL;
    island * current = NULL;
    
    puts("输入岛名：（输入S结束）");
    while (scanf("%79s",name) == 1) {
        if (strlen(name) == 1 && (name[0] - 'S' == 0)){
            break;
        }
        island * il = create(name);
        if (start == NULL) {
            start = il;
        }
        if (current != NULL) {
            current->next = il;
        }
        current = il;
        
        puts("输入岛名：");
    }
    
    printf("%i\n",display(start));
    
    //free all
    release(start);
    
    return 0;
}

 log:

 输入岛名：（输入S结束）

 a

 输入岛名：

 b

 输入岛名：

 c

 输入岛名：

 d

 输入岛名：

 e

 输入岛名：

 f

 输入岛名：

 S

 Island name:a  Open-Close：09:00-17:00

 Island name:b  Open-Close：09:00-17:00

 Island name:c  Open-Close：09:00-17:00

 Island name:d  Open-Close：09:00-17:00

 Island name:e  Open-Close：09:00-17:00

 Island name:f  Open-Close：09:00-17:00

 6

 

 上述示例中：

     使用字符指针相比于字符数组更好，因为字符数组需要提前决定字符串的长度；

 值得注意的是：

     我们添加了一个新的函数release()，用于链表的释放；

     其中，需要释放使用strdup()函数创建的name字符串；

     之后，再释放相应节点的结构；

     用完后调用释放存储器调用release(start);即可；

 

 有了动态分配存储器，就能在运行时创建需要的存储器，使用malloc()和free()，可以访问动态堆存储器；

 

 小结：

     堆之所以叫堆，因为计算机不会自动组织它，他只是一大堆数据而已；

     垃圾收集：一些语言会跟踪你在堆上分配的数据，当不再使用时，就释放它们；C语言是没有的；

     虽然操作系统会在程序结束时回收所有存储器，但最后显示的释放自己创建的每样东西；

 

 要点：

 -可以用动态数据结构保存可变数量的数据项；

 -可以很方便地在链表这种数据结构中插入数据项；

 -在C语言中，动态数据结构通常用递归结构来定义；

 -递归结构中有一个或多个指向相同结构的指针；

 -栈用来保存局部变量，他由计算机管理；

 -堆用来保存长期使用的数据，可以用malloc()分配堆空间；

 -sizeof运算符告诉你一个结构需要多少空间；

 -数据会一直留在堆上，直到用free()释放它；

 

 使用结构我们还可以创建很多其他形式的数据结构：

 （P3）

 

 数据结构很有用，但要小心使用：

     当用C语言创建这些数据结构时需要非常小心，如果没有记录好保存的数据，就可能把不同的数据留在堆上；时间久了，会消耗存储器，程序也会因为存储器错误而崩溃；

     我们可以使用valgrind工具追查代码中的存储器泄露：

         gcc -g xxx.c ... //-g开关会告诉编译器要记录要编译代码的行数

         valgrind --leak-check=full ./xxx

 

 C语言工具箱：

 -链表比数组更容易扩展；

 -在链表中插入数据很方便；

 -链表是动态数据结构；

 -动态数据结构使用递归结构；

 -递归结构包含一个或多个链向相同结构数据的链接；

 -malloc()在堆上分配存储器；

 -free()释放堆上的存储器；

 -与栈不同堆存储器不会自动释放；

 -栈用来保存局部变量；

 -strdup()会把字符串复制到堆上；

 -存储器内存泄漏是指存储器分配出去以后，你再也访问不到；

 -valgrind可以帮助跟踪存储器泄露；（可自行查阅）