文档章节

第17章 高级数据表示 17.2 从数组到链表

idreamo
 idreamo
发布于 2017/08/12 06:51
字数 3060
阅读 11
收藏 0

您可能会希望可以不确定的添加数据(或者不断添加数据,直到程序内存用完为止),而不用事先指定您会输入多少个项目,也不用让程序分配不必要的大块内存。这一点可以通过在输入每个项目之后调用malloc()分配大小合适的空间以保存新的数据项来做到。如果用户输入3部电影,程序就调用malloc()3次。如果用户输入300部电影,程序就调用malloc()函数300次。

这导致了一个新问题,为了发现这个问题是什么,试比较这两种情况:调用malloc()函数1次、请求保存300个film结构的空间,和调用malloc()300次、每次请求保存1个film结构的空间。第一种情况将分配一个连续的内存块,用以跟踪这些内容的只是一个指向struct film的指针变量,它指向块中的第一个结构。通过使用简单的数组符号,允许这个指针访问块中的每一个结构,如前面的代码段所示。第二种方法的问题是不能保证连续的malloc()调用产生相邻的内存块。这意味着这些结构不一定会被连续存储。因此,需要存储300个指针,其中每个指针指向一个独立存储的结构;而不是存储一个指向有300个结构的块的指针。

一种解决方法是创建一个大的指针数组,并在分配新的结构时逐个地对这些指针赋值,但我们不打算这么做:

#define TSIZE 45  /*存放片名的数组大小*/
#define FMAX 500  /*最多的影片数*/
struct film {
    char title[TSIZE];
    int rating;
};
...
struct film *movies[FMAX]; /*指向结构的指针的数组*/
int i;
...
movies[i]=(struct film *)malloc(sizeof(stuct film));

如果用户输入的项目个数小于500个,这种方法将节省大量的内存,因为500个指针数组比500个结构数组占用少得多的内存。但是,无用指针占用的空间仍然会被浪费掉,并且仍然有500个结构的限制。

有一种更好的办法,每次使用malloc()为新结构分配空间时,也为新指针分配空间。您可能会说“但是,然后我就需要另一个指针来跟踪新分配的指针,同时它本身也需要一个指针来跟踪,依此类推..."。避免这个潜在问题的方法是重新定义结构,使得每个结构包含一个指向下一结构的指针。然后,每次创建新的结构时,就可以在前一个结构中存储它的地址。简而言之,需要这样来定义新的film结构:

#define TSIZE 45 /*存放片名的数组的大小*/
struct film {
    char title[TSIZE];
    int rating;
    struct film *next;
}

是的, 结构本身不能含有同类型的结构,但是它可以含有指向同类型结构的指针这样的定义是定义一个链表的基础。链表是一个列表,其中的每一项都包含描述何处能找到下一项的信息

让我们先从概念上理解一个链表的实例。假设用户输入片名为Modern times、等级为10的一部电影。程序将为一个film结构分配空间,将Modern times字符串复制到title成员中,并将rating成员设置为10。为了说明这个结构后面没有别的结构,程序将把next成员指针设为NULL(NULL是在stdio.h文件中定义的符号常量,代表空指针)。显然需要跟踪第一个结构存储在哪里,可以将其地址赋给一个独立的称为头指针(head pointer)的指针。头指针指向数据链表中的第一项

struct film{
    char title[TSIZE];
    int rating;
    struct film *next;
};
struct film *head; 

现在假设用户输入第二部电影及其等级,例如Titanic 和8。程序为第二个film结构分配了空间,并在第一个结构的next成员中存储这个新结构的地址(覆盖先前存储于此的NULL),使得结构的next指针指向链表中的下一个结构。然后程序将Tatanic 和 8复制到新的结构中,并将它的next成员设为NULL,表示当前它是链表中最后一个结构。

每一部新电影都以同样的方式处理。其地址将被存储在前一个结构中,新信息存储在新的结构中,其next成员设为NULL,从而建立起一个链表

假设您想显示一个链表,每显示一个项目,您可以使用存储在相应结构中的地址定位要显示的下一个项目。但是要使这个方案能够工作,还需要一个指针来存储链表中第一个项目的地址,因为链表中没有一个项目存储第一个项目的地址。幸运的是,您已经用头指针完成了这个任务

17.2.1  使用链表

现在让我们来实现链表的工作原理。程序清单17.2修改了程序清单17.1,这样使用一个链表而不是数组来存放电影信息。

程序清单17.2  film2.c程序

/*film2.c使用结构链表*/
#include <stdio.h>
#include <stdlib.h>    /*提供malloc()原型*/
#include <string.h>    /*提供strcpy()原型*/
#define TSIZE 45       /*存放片名的数组大小*/
struct film {
    char title[TSIZE];
    int rating;
    struct film *next;  /*指向链表的下一个结构*/
};

int main(void)
{
    struct film *head = NULL;
    struct film *prev,*current;
    char input[TSIZE];

    /*收集并存储信息*/
    puts("Enter first movie title: ");
    while(gets(input) != NULL && input[0] != '\0')
    {
        current = (struct film *)malloc(sizeof(struct film));
        if(head == NULL)  /*第一个结构*/
            head = current;
        else   /*后续结构*/
            prev->next = current;
        current->next = NULL;
        strcpy(current->title,input);
        puts("Enter your rating <0-10>: ");
        scanf("%d",&current->rating);
        while(getchar()!='\n')
            continue;
        puts("Enter next movie title (empty line to stop): ");
        prev = current;
    }
    /*给出电影列表*/
    if(head == NULL)
        printf("No data entered. ");
    else
        printf("Here is the movie list: \n");
    current = head;
    while(current != NULL)
    {
        printf("Movie: %s Rating: %d\n",current->title,current->rating);
        current = current->next;
    }
    /*任务已完成,因此释放所分配的内存*/
    current = head;
    while(current != NULL)
    {
        free(current);
        current = current->next;
    }
    printf("Bye!\n");

    return 0;
}

程序用链表完成两个任务。第一,构造列表并用输入的内容填充。第二,显示列表。显示列表的任务相对简单,所以我们先讨论它。

一、显示列表

显示列表的方法是开始时把一个指针(名为current)设置为指向第一个结构。因为头指针已经指向那里(名为head),所以下面这行代码可以完成这个任务:

current = head;

然后,可以用指针符号访问结构的成员

printf("Movie: %s Rating: %d\n",current->title,current->rating);

下一步是 重设current指针以指向列表中的下一个结构。这个信息存储在结构的next成员中,所以下面这行代码可以完成这个任务:

current = current->next;

完成这些以后,重复整个过程。显示列表中最后一项之后,current将被设置为NULL,因为这是最后一个结构的next成员的值。可以用这个事实来终止显示过程。下面是film2.c中用来显示列表的完整的代码:

while(current != NULL)
{
    printf("Movie: %s Rating: %d\n",current->title,current->rating);
    current = current->next;
}

为什么不使用head来遍历整个列表,而是创建一个新指针current?因为使用head会改变head的值,这样程序将不再能找到列表的开始处。

二、创建列表

创建列表包括三步:

1、使用malloc()函数为一个结构分配足够的空间;

2、存储这个结构的地址;

3、把正确的信息复制到这个结构;

如果不需要,就不应该创建结构,所以程序使用临时存储(input数组)来获取用户输入的片名。如果用户从键盘模拟了EOF,或者输入了空行,输入循环就会退出:

while(gets(input)!=NULL && input[0]!='\0')

如果有输入,程序就为一个结构请求空间,并将其地址赋给指针变量current:

current = (struct film *)malloc(sizeof(struct film));

第一个结构的地址必须保存在指针变量head中,后续每一个结构的地址都必须保存在前一结构的next成员中。因此,程序需要知道是否在处理第一个结构。一种简单的方法是在程序开始时将head指针初始为NULL。然后程序可以使用head的值来决定该如何做:

if(head == NULL)  /*第一个结构*/
    head=current;
else              /*后续结构*/
    prev->next = current;

在这段代码中,prev是指向前一个结构的指针 。

接下来,需要为结构成员设置合适的值。具体地,应将next成员设为NULL来表示当前结构是列表中的最后一个,将片名从input数组复制到title成员,并且要为rating成员获取一个值。下面的代码完成这些任务:

current->next = NULL;
strcpy(current->title,input);
puts("Enter your rating <0-10>: ">;
scanf("%d",&current->rating);

最后,需要让程序准备接受下一轮输入。具体地,需要将prev设置为指向当前结构,因为在键入下一个片名和分配下一个结构之后,当前结构将成为上一个结构。程序在循环的结尾处设置这个指针:

prev = current;

下面是一个运行示例:

Enter first movie title:
Spirited Away
Enter your rating <0-10>:
8
Enter next movie title <empty line to stop>:
The Duelists
Enter your rating <0-10>:
7
Enter next movie title <empty line to stop>:
Devil Dog:The Mound of Hound
Enter your rating <0-10>:
1
Enter next movie title <empty line to stop>:

Here is the movie list :
Movie: Spirited Away Rating: 8
Movie: The Duelists Rating: 7
Movie: Devil Dog: The Mound of Hound Rating: 1
Bye!

三、清理列表

程序在终止时会自动释放由malloc()分配的内存,但最好是养成调用free()来释放由malloc()分配的内存的习惯。因此, 程序通过对每一个已分配的结构应用free()函数来清理其内存:
 

current = head;

while(current != NULL)
{
    free(current);
    current = current->next;
}

17.2.2 反思

film2.c程序有一些不足。比如,它没有检查malloc()是否找到需要的内存,并且它不提供删除列表中的项目的功能。但是这些不足是可以解决的。比如可以添加检查malloc()的返回值是否为NULL(表示它无法获得所需内存)的代码。如果需要程序删除项目,需要编写更多的代码来实现 。

这种用特定方法解决特定问题,并在需要时添加功能的编程方式通常不是最好的。另一方面,通常无法预料到程序要完成哪些任务。随着程序编制工程规模的扩大,一个程序员或一个编程团队事先做好一切计划的模式显得越来越不现实。可以看到很多成功的大型程序往往是由一些成功的小型程序一步步发展而来的。

如果稍后需要修改程序 ,那么以简化修改过程的方式开发最初的设想是个好主意。程序清单17.2中的示例程序没有遵循这个原则。具体地,它把编码细节和概念模型混合在一起。比如,在示例程序中,概念模型是向一个列表中添加项目。但程序将malloc()和current->next之类的代码置于显著的位置,因而模糊了这个接口。更好的方法是:明确地表明您在向一个列表中添加项目,并隐藏那些细节性的动作,比如调用内存管理函数和设置指针等。将细节和用户接口分开将使程序更易理解和升级。通过开始编程时就使用新的方法,您可以实现这些目标。让我们来看看应该如何去做(17.3)

© 著作权归作者所有

idreamo
粉丝 18
博文 139
码字总数 224743
作品 0
青岛
产品经理
私信 提问
《java数据结构和算法》读书笔记

《Java多线程编程核心技术》读书笔记 常用数据结构 第2章 数组 最简单的数据结构,在查找上比链表有优势,但是在插入与删除上比不上链表。 Java中的数组有长度限制,为int值。在内存模型中,...

刀狂剑痴
2016/05/27
229
0
转行程序员?你可能忽略了一件事。

     程序 = 数据结构 + 算法   ——图灵奖得主,计算机科学家N.Wirth(沃斯)      作为程序员,我们做机器学习也好,做python开发也好,java开发也好。   有一种对所有程序员无一...

java进阶架构师
2018/10/25
0
0
python算法-1.简介/2.选择排序

第一章、 算法简介 一些常见的大O运行时间 》 ,也叫对数时间,这样的算法包括二分查找。 》 ,也叫线性时间,这样的算法包括简单查找。 》 ,这样的算法包括第4章将介绍的快速排序——一种速...

时间之友
2017/12/15
0
0
新书推荐 |《PostgreSQL实战》出版

很高兴《PostgreSQL实战》一书终于出版,本书大体上系统总结了笔者 PostgreSQL DBA 职业生涯的经验总结,本书的另一位作者张文升拥有丰富的PostgreSQL运维经验,目前就职于探探科技任首席Pos...

francs.tan
2018/08/12
0
0
关东升的《从零开始学Swift》第2版已经出版

关东升的《从零开始学Swift》第2版已经出版 大家好: 苹果2015WWDC大会发布了Swift2.0,它较之前的版本Swift1.x有很大的变化,所以我即将出版《从零开始学Swift》 《从零开始学Swift》将在《...

tony关东升
2016/02/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
5
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部