C day18 高级数据表示（链表，队列）

系统管理员 2023-07-07 05:52 34阅读 0赞

这是C primer的最后一章了，前面已经学习了怎么创建变量，结构，数组，指针，会写函数，总之，把C作为**工具层面**的知识已经学完了，但是对于编程之路，这才算走完第一步，因为对于写程序最重要的是学习如何表示数据，在**数据的表示方**法上进一步下功夫，不能仅仅依靠那些简单变量，数组，结构，指针，还需要**更加灵活的表示方**法去解决之前编程时隐藏的问题，比如数组，分配的太大，可能很浪费，分配的太小，有时候又真的不够用，非常不灵活，这一章的内容就可以解决这些问题，使程序更加**灵活**，也可以让我们**从菜狗变成高手**。

这一章主要用**malloc函数**，因为要灵活嘛，那就只有**运行时**要用多少内存就分配多少内存咯，而不是**编译时**就分配好。

数据类型不仅要考虑怎么存储数据，还要考虑能对数据对象进行哪些操作，比如int类型可以加减乘除取余等等，指针类型虽然也是被存储为整数（地址实际上就是编号，当然是整数啦），但是指针类型很明显不可以乘除，加减也只能加减整数，还可以解引用，C语言为基本类型都定义了有效操作。

所以我们**自己设计数据类型**时，需要通过**函数**定义的方式给数据类型定义有效的**操作**。**设计数据类型就是把算法和数据表示匹配起来的过程**。**算法是操控数据的方法**。

### 文章目录 ###

*  从结构数组到链表
 *   *  示例1 结构数组
     *  示例2 动态分配结构数组的长度（灵活了一丁点）
     *  链表 进一步改进上面的程序
     *   *  示例3 链表
 *  程序“设计”，便于理解和更新
 *   *  抽象数据类型（定义新类型：以设计一个简单链表为例）
     *   *  第一步：建立抽象
         *  第二步：设计接口
         *  第三步：实现接口
 *  队列 （特殊的链表）
 *   *  队列模拟真实排队情况

# 从结构数组到链表 #

## 示例1 结构数组 ##

用一个结构存储一部电影的信息，包括片名，评分两个信息，然后要存储多部电影的信息，所以使用结构数组，这是我们之前惯用的方式，也是首先occur to mind的方式，但是，我们必须客观分析这种方式的局限：僵硬不灵活，浪费空间。

可以看到，我们用宏定义了电影片名为20个字符，但是从输出结果来看，不够用。用宏定义了最多存储10部电影，可是万一需要存更多呢？

#include <stdio.h>
    #include <string.h>
    #define TSIZE 20//电影片名
    #define NMAX 10//最大电影数目
    typedef struct films{ 
        char title[TSIZE];
        unsigned short rating;
    }film;
    void eatline();
    char *s_gets(char *st, int n);
    void show_list(film [], int);
    
    
    int main()
    { 
        film myfilm[NMAX];
        int i = 0;
    
        puts("Enter the movie title:");
        //不要写为s_gets(&myfilm[i].title, TSIZE)，因为myfilm[i].title是字符数组名，已经是指针啦！
        while(i<NMAX && s_gets(myfilm[i].title, TSIZE)!=NULL && myfilm[i].title[0]!='\0')
        { 
            puts("Enter your rating: <0-10>");
            scanf("%hu", &myfilm[i++].rating);
            eatline();
            puts("Enter another movie title:");
        }
        if(i==0)
            puts("No data entered!");
        else
            { 
                puts("Here is the film list:");
                show_list(myfilm, i);
            }
        return 0;
    }
    
    void eatline()
    { 
        while(getchar()!='\n')
            ;
    }
    
    void show_list(film ar[], int n)
    { 
        int i;
    
        for(i=0;i<n;i++)
            printf("Movie title: %20s Rating: %hu\n", ar[i].title, ar[i].rating);
    }
    
    char *s_gets(char *st, int n)
    { 
        char *ret_val, *find;
    
        ret_val = fgets(st, n, stdin);
        if(ret_val)
        { 
            find = strchr(st, '\n');
            if(find)
                *find = '\0';
            else
                eatline();
        }
    
        return ret_val;
    }

Enter the movie title:
    The Discreet Charm of the Bourgeoisie
    Enter your rating: <0-10>
    8
    Enter another movie title:
    The Dog Who Saved Hollywood
    Enter your rating: <0-10>
    10
    Enter another movie title:
    Gone With the Wind
    Enter your rating: <0-10>
    9
    Enter another movie title:
    
    Here is the film list:
    Movie title:  The Discreet Charm   Rating: 8
    Movie title:  The Dog Who Saved H  Rating: 10
    Movie title:   Gone With the Wind  Rating: 9

## 示例2 动态分配结构数组的长度（灵活了一丁点） ##

这是对上面程序的一丁点改进，即不在编译时确定下来结构数组的长度，即最多存储电影的数目，而是在运行时让用户自己输入数组长度，然后再malloc分配内存给这个结构数组。于是就不会出现因为数组长度太大浪费空间和数组太短不够用的情况了。

但是这需要用户的参与，作为程序员，我们不该太信任用户，如果用户不能正确输入长度，就···

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>//malloc()原型
    #define TSIZE 20//电影片名
    //#define NMAX 10//最大电影数目
    typedef struct films{ 
        char title[TSIZE];
        unsigned short rating;
    }film;
    void eatline();
    char *s_gets(char *st, int n);
    void show_list(film *, int);
    
    
    int main()
    { 
        //film myfilm[NMAX];
        int i = 0;
        unsigned int max;
        film * movie, *movies;
    
        puts("Enter the maximum number of movies you'll enter:");
        scanf("%u", &max);
        eatline();
        movies = (film *)malloc(max * sizeof(film));
        movie = movies;
    
        puts("Enter the movie title:");
        while(i<max && s_gets(movie->title, TSIZE)!=NULL && movie->title[0]!='\0')
        { 
            puts("Enter your rating: <0-10>");
            scanf("%hu", &movie->rating);
            movie++;
            i++;
            eatline();
            puts("Enter another movie title:");
        }
        if(i==0)
            puts("No data entered!");
        else
            { 
                puts("Here is the film list:");
                show_list(movies, i);
            }
        return 0;
    }
    
    void eatline()
    { 
        while(getchar()!='\n')
            ;
    }
    
    void show_list(film *p, int n)
    { 
        int i;
    
        for(i=0;i<n;i++)
            printf("Movie title: %20s Rating: %hu\n", (*(p+i)).title, (*(p+i)).rating);
    }
    
    char *s_gets(char *st, int n)
    { 
        char *ret_val, *find;
    
        ret_val = fgets(st, n, stdin);
        if(ret_val)
        { 
            find = strchr(st, '\n');
            if(find)
                *find = '\0';
            else
                eatline();
        }
    
        return ret_val;
    }

Enter the maximum number of movies you'll enter:
    2
    Enter the movie title:
    Gone With the Wind
    Enter your rating: <0-10>
    9
    Enter another movie title:
    Bark Bark
    Enter your rating: <0-10>
    4
    Enter another movie title:
    Here is the film list:
    Movie title:   Gone With the Wind  Rating: 9
    Movie title:            Bark Bark  Rating: 4

## 链表 进一步改进上面的程序 ##

已经说了， 上面的程序虽然是动态分配的内存，但是需要用户指定项数，很不好。我们希望的理想状态是：输入一个结构，就分配一个结构的空间，再输入，再分配，而不用提前指定总的项数，这样可以允许用户自由添加任意项数。

即，输入1项，调用一次malloc,输入100项，调用100次malloc，输入1000项，则调用1000次malloc函数。但是我们知道，调用一次malloc会返回一个指针表示分配的内存的地址，那么调用这么多次，当然就会返回这么多个地址，所以我们必须把他们存起来，不然零散分配的内存块就找不到了，毕竟不是数组那样连续的内存。

我们首先想到的办法肯定是用一个指针数组把众多指针存起来，但是这并不是最好的办法，还是同样的原因，使用数组你就要分配一块固定内存，那分配多大呢，分配太小不够用，分配太多又浪费，分配的指针数组的长度就是前面让我们纠结不已的项数呀，如果用指针数组的话，不就又绕回去了吗？？

**链表**提供了一个聪明的解决办法:把每一个指针存储为结构体的一个成员。当前结构的一个成员存储了下一个结构的地址，最后一个结构的该成员存储空指针以表示链表的结束。即从链表的每一个c

这一实现的基础：  
![在这里插入图片描述][20200221222148176.png]

所以，链表比数组灵活，就是因为数组的不灵活才开发了链表这种数据形式，它依赖于结构和指针，还要依赖动态内存分配，但是可以解决掉数组带来的尴尬局面：不知道到底分配多大长度合适。

### 示例3 链表 ###

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>//malloc()原型
    #define TSIZE 20//电影片名
    //#define NMAX 10//最大电影数目
    typedef struct films{ 
        char title[TSIZE];
        unsigned short rating;
        struct films *next;
    }film;
    void eatline();
    char *s_gets(char *st, int n);
    void show_list(film *);
    
    
    int main()
    { 
        film * head = NULL;
        film * prev, *current;//不能动头指针，否则找不到链表开始处，所以只好定义一个current指针，从指向head到指向最后一个结构的空指针
        char input[TSIZE];//电影片名的缓冲
    
        puts("Enter the movie title:");
        while(s_gets(input, TSIZE)!=NULL && input[0]!='\0')
        { 
            current = (film *)malloc(sizeof(film));
            if(head == NULL)
                head = current;
            else
                prev->next = current;//给前一个结构的next存上当前分配的内存
            current->next = NULL;//必须把当前结构的next指针设置为NULL,表明这是链表的最后一项
            strcpy(current->title, input);
            puts("Enter your rating: <0-10>");
            scanf("%hu", &current->rating);
            eatline();
    
            puts("Enter another movie title:");
            prev = current;
        }
        if(head == NULL)
            puts("No data entered!");
        else
            { 
                puts("Here is the film list:");
                show_list(head);
            }
          //释放内存，不要忘记！！！
           current = head;
           while(head)
           { 
               current = head;
               head = current->next;
               free(current);
           }
           puts("Memory freed!");
        return 0;
    }
    
    void eatline()
    { 
        while(getchar()!='\n')
            ;
    }
    
    void show_list(film *p)
    { 
        while(p->next)
            { 
                printf("Movie title: %20s Rating: %hu\n", p->title, p->rating);
                p = p->next;
            }
        printf("Movie title: %20s Rating: %hu\n", p->title, p->rating);
    }
    
    char *s_gets(char *st, int n)
    { 
        char *ret_val, *find;
    
        ret_val = fgets(st, n, stdin);
        if(ret_val)
        { 
            find = strchr(st, '\n');
            if(find)
                *find = '\0';
            else
                eatline();
        }
    
        return ret_val;
    }

Enter the movie title:
    Mamamiya
    Enter your rating: <0-10>
    9
    Enter another movie title:
    Gone With the Wind
    Enter your rating: <0-10>
    8
    Enter another movie title:
    Bark
    Enter your rating: <0-10>
    4
    Enter another movie title:
    
    Here is the film list:
    Movie title:             Mamamiya  Rating: 9
    Movie title:   Gone With the Wind  Rating: 8
    Movie title:                 Bark  Rating: 4
    Memory freed!

# 程序“设计”，便于理解和更新 #

之前看到过很多次**程序设计**这个词，从来没明白过为什么程序也需要设计，设计什么。我一直还停留在写代码，**堆砌代码**的阶段，而不是进阶的程序设计，我的代码就普遍存在上面几个示例程序也存在的问题：拿到一个需求，就吭哧吭哧写代码，没有提前设计用户接口，甚至想都没想，只管能实现需求，写出一大坨代码，虽然符合了一些好的编程习惯，代码规范，代码逻辑也可以，但是仍然是一堆不整齐的代码，为什么呢？因为它们**把代码的实现细节放在最明显的位置**，比如分配内存和指针赋值，却没有把**用户接口**放在最明显的位置，这样的代码，只要再来一个需求，就需要大幅改动，而且很不好改，再来几个需求，程序员可能就要加班抓狂崩溃了。

如果你在做的是一个大的项目，可能面临不断的需求更迭，那么提前做一些设计是非常有好处和必要的。一个大的程序绝不是刚才那样来一个需求就加码，不断加码，而是很多个成功的短小程序的合作结晶。怎么做呢？关键就是要把每个小程序的接口突出出来，代码细节隐藏起来，做成一个个黑盒子，模块，要用这个功能就调用这个模块就行。

## 抽象数据类型（定义新类型：以设计一个简单链表为例） ##

除了之前的模块化编程之外，学习抽象数据类型ADT，也可以把用户接口和代码细节分开。  
![在这里插入图片描述][2020022212290317.png]![在这里插入图片描述][20200222123208359.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]  
这一节好难呀！大致扫视了一下，看不懂呢？？？  
涉及好几个不太理解的名词：接口，抽象  
是个难啃的硬骨头

如上图，定义新类型分为三步实现，这三步实际就是三个不同的抽象层次，第一步最抽象，不涉及任何细节；第二步，接口，抽象程度降低，细节增多。第三步，完整细节。

### 第一步：建立抽象 ###

我感觉抽象就像是自然语言的伪代码，或者像是一条一条的把需要对这个数据类型（这个例子是链表）执行的操作都描述出来，有一种提前计划规划的感觉，即正式敲代码之前先在脑子里想清楚我要设计一个什么数据类型，它的属性，我可能对他作的操作。

由于我的计划全是自然语言写的，没有涉及任何怎么实现这些计划的细节，所以他们是抽象的，可以通过多种方式，使用多种基本类型去实现细节。

比如我想设计一个链表，首先我要思考我这个链表的属性是什么，我认为我的链表要能储存很多项数据。

操作呢？（操作才是大头啊）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]![在这里插入图片描述][20200222124924286.png]

看，上面这些设想的操作基本可以覆盖我使用这个数据类型的方方面面了，那么我在别的程序里使用这个数据类型就很轻松，不用再编写具体的实现代码了。  
![在这里插入图片描述][20200222125801889.png]

所以，建立抽象就是**脱离细节搞计划**，头脑风暴一般设想可能要对这个数据类型作的事情。磨刀不误砍柴工，这一步就是磨刀，程序员就是砍柴工。这一步也很像领导的任务，不指定这个不规定那个，尽量顶层，抽象，不涉及任何具体方案，不让下面的人束手束脚，让员工自由发挥，只要完成领导计划的这些事情就好。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]

### 第二步：设计接口 ###

这一层次的抽象程度降低了，我们在这一步要做的事情说白了，就是设计第一步计划的那些操作的函数原型。

上面说的每一个操作，在第三步会被代码实现出来。接口嘛，就是和外部通信的一个媒介，之前学的函数之间的通信，要么通过参数返回值，要么通过指针，实际上接口也一样，就是要描述这个函数的参数和返回值是啥，这样别人一看符合接口定义就可以调用这个函数。

当然这一步还是抽象的，体现在写函数原型时参数和返回值的类型不会写的很具体，比如int,double,而是一般用typedef定义一个通用数据类型，这样如果需要使用其他数据形式，就只需要重新定义这个通用数据类型，而不需要修改接口。

![在这里插入图片描述][20200222132122901.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]

太高深了，我有点晕，看看代码

### 第三步：实现接口 ###

#ifndef LIST_H_
    #define LIST_H_
    #include <stdio.h>
    #include <stdbool.h>
    
    #define TSIZE 45//电影片名
    struct film{ 
        char title[TSIZE];
        int rating;
    };
    
    typedef struct film Item;
    
    typedef struct node{ 
        Item item;
        //结构体的成员可以是指向自己的指针，但不能是自己类型
        struct node * next;
    }Node;//Node类型是链表
    typedef Node * List;//List是指向Node类型的指针
    
    /*函数原型*/
    
    /*操作：初始化一个链表*/
    /*前提条件：plist指向一个链表*/
    /*后置条件：链表初始化为空*/
    void InitializeList(List *plist);
    
    /*操作：确定链表是否为空定义，plist指向一个已初始化的链表*/
    /*前置条件：*/
    /*后置条件：若链表为空，则返回true；否则返回false*/
    bool ListIsEmpty(const List *plist);
    
    /*操作：确定链表是否已满，plist指向一个已初始化的链表*/
    /*后置条件：若链表已满，函数返回真；否则返回假*/
    bool ListIsFull(const List *plist);
    
    /*操作：确定链表中的项数，plist指向一个已初始化的链表*/
    /*后置条件：返回链表中的项数*/
    int ListItemCount(const List *plist);
    
    /*操作：在链表的末尾添加项*/
    /*前提条件：item是一个待添加至链表的项，plist指向一个已初始化的链表*/
    /*后置条件：如果可以添加，则在链表末尾添加一项，并返回true；否则返回false*/
    bool AddItem(Item item, List *plist);
    
    /*操作：把函数作用域链表的每一项*/
    /*前提条件：plist指向一个已初始化的链表，pfun指向一个函数，这个函数接受一个、 Item类型的参数，且无返回值*/
    /*后置条件：pfun指向的函数作用于链表的每一项一次*/
    void Traverse(const List *plist, void(*pfun)(Item item));
    
    
    /*操作：释放已分配的内存*/
    /*前提条件：plist指向一个已初始化的链表*/
    /*后置条件：释放了为链表分配的所有内存，链表设置为空*/
    void EmptyTheList(List *plist);
    #endif // LIST_H_

![在这里插入图片描述][20200222135520472.png]

//films.c//使用抽象数据类型风格的链表
    #include "list.h"
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void showmovies(Item item);
    char * s_gets(char *st, int n);
    void eatline();
    
    int main()
    { 
        List movies;
        Item temp;//作为输入缓冲
    
        /*初始化*/
        InitializeList(&movies);//movies被初始化为空指针，movies是头指针
        if(ListIsFull(&movies))
        { 
            fprintf(stderr, "No memory available! Bye!\n");
            exit(1);
        }
        /*获取用户输入并储存*/
        puts("Enter first movie title:(empty line to stop)");
        while(s_gets(temp.title, TSIZE)!=NULL && temp.title[0]!='\0')
        { 
            puts("Enter your rating:<0-10>");
            scanf("%d", &temp.rating);
            eatline();
            if(AddItem(temp, &movies)==false)
            { 
                fprintf(stderr, "Problem allocating memory!\n");
                break;
            }
            if(ListIsFull(&movies))
            { 
                puts("The list is now full.");
                break;
            }
            puts("Enter next movie title.(empty line to stop)");
        }
    
        /*显示*/
        if(ListIsEmpty(&movies))
            puts("No data entered.");
        else
        { 
            puts("Here is the movie list:");
            Traverse(&movies, showmovies);
        }
        printf("You have entered %u movies.\n", ListItemCount(&movies));
    
        /*清理，释放内存*/
        EmptyTheList(&movies);
        puts("Bye!");
    
        return 0;
    }
    
    void showmovies(Item item)
    { 
        printf("Movie: %s Rating: %d\n", item.title, item.rating);
    }
    char *s_gets(char *st, int n)
    { 
        char *ret_val, *find;
    
        ret_val = fgets(st, n, stdin);
        if(ret_val)
        { 
            find = strchr(st, '\n');
            if(find)
                *find = '\0';
            else
                eatline();
        }
    
        return ret_val;
    }
    
    void eatline()
    { 
        while(getchar()!='\n')
            ;
    }

实现接口函数

/*链表操作的函数*/
    #include "list.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    /*局部函数原型*/
    static void CopyToNode(Item item, Node * pnode);
    
    /*接口函数*/
    /*初始化链表为空，即把指向链表的指针设置为空指针*/
    void InitializeList(List *plist)
    { 
        *plist = NULL;//plist指向的是链表的头指针
    }
    
    /*如果链表为空，返回true*/
    bool ListIsEmpty(const List *plist)
    { 
        if(*plist == NULL)
            return true;
        else
            return false;
    }
    
    /*如果链表已满，返回true(链表已满即再用\ malloc分配内存具分配不到了，返回空指针，所以要用malloc测试一下)*/
    bool ListIsFull(const List *plist)
    { 
        Node *pt;//指向链表的指针
        bool full;
    
        pt = (Node *)malloc(sizeof(Node));
        if(pt)
            full = false;
        else
            full = true;
        free(pt);//释放这块内存，因为只是测试一下
    
        return full;
    }
    /*返回节点的数量*/
    unsigned int ListItemCount(const List * plist)
    { 
        unsigned int count = 0;
        Node *pnode = *plist;//*plist是链表的头指针
    
        while(pnode!=NULL)
        { 
            count++;
            pnode = pnode->next;
        }
        return count;
    }
    
    /*创建储存项的节点，并将其添加到plist指向的链表的末尾(较慢的实现)*/
    bool AddItem(Item item, List *plist)
    { 
        Node * pnew;//创建新指针，后面把给新项分配的内存地址给它
        Node *scan = *plist;//scan初始化为头指针
    
        pnew = (Node *)malloc(sizeof(Node));
        if(pnew == NULL)
            return false;//内存分配失败
        CopyToNode(item, pnew);
        pnew->next = NULL;
        if(scan == NULL)
            *plist = pnew;//如果是空链表，就把新项的指针给头指针
        else
        { 
            while(scan->next != NULL)
                scan = scan->next;
            scan->next = pnew;
        }
        return true;
    }
    
    /*访问每个节点，并执行pfun指向的函数*/
    void Traverse(const List *plist, void (*pfun)(Item item))
    { 
        Node *pnode = *plist;
    
        //遍历
        while(pnode!=NULL)
        { 
            (*pfun)(pnode->item);
            pnode = pnode->next;
        }
    
    }
    
    /*释放malloc分配的内存*/
    void EmptyTheList(List *plist)
    { 
        Node *psave;
    
        //从头指针开始，一个一个的free
        while(*plist != NULL)
        { 
            psave = (*plist)->next;
            free(*plist);
            *plist = psave;
            //头指针释放掉，把头指针后面这个指针作为头指针，再释放，以此类推·····
        }
    }
    
    
    /*局部函数定义*/
    /*把一个项拷贝到节点中，由于这个函数是实现的一部分，而不是接口的一部分，所以我们用static存储类别说明符把它隐藏为list.c文件可见*/
    static void CopyToNode(Item item, Node *pnode)
    { 
        pnode->item = item;
    }

输出

Enter first movie title:(empty line to stop)
    a
    Enter your rating:<0-10>
    2
    Enter next movie title.(empty line to stop)
    b
    Enter your rating:<0-10>
    6
    Enter next movie title.(empty line to stop)
    f
    Enter your rating:<0-10>
    8
    Enter next movie title.(empty line to stop)
    
    Here is the movie list:
    Movie: a  Rating: 2
    Movie: b  Rating: 6
    Movie: f  Rating: 8
    You have entered 3 movies.
    Bye!

终于写出来了，花了三个小时····，费劲

# 队列 （特殊的链表） #

queue，跟排队一样，先进先出 FIRST IN FIRST OUT

队列是特殊的链表：

*  1.队列只能把新项添加到队列的末尾。
 *  2.队列只能从队首删除项。

第一步：建立抽象  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 6]  
第二步：定义接口

/*用链表实现队列（其实也可以用数组实现环形队列哦）*/
    #ifndef _QUEUE_H_
    #define _QUEUE_H_
    #include <stdbool.h>
    
    typedef struct item{ 
        int gumption;//进取心
        int charisma;//魅力
    }Item;
    #define MAXQUEUE 10
    
    typedef struct node{ 
        Item item;
        struct node * next;
    }Node;
    
    //队列用结构实现，成员是指向队列首尾的指针和队列项数
    typedef struct queue{ 
        Node * front;
        Node * rear;
        int items;
    }Queue;
    
    /*操作；初始化队列*/
    /*前提条件：pq指向一个队列*/
    /*后置条件：队列被初始化为空*/
    void InitializeQueue(Queue *pq);
    
    /*操作：检查队列是否已满*/
    /*前提条件：pq指向之前被初始化的队列*/
    /*后置条件：如果队列已满则返回true，否则返回false*/
    bool QueueIsFull(const Queue * pq);
    
    /*操作：检查队列是否为空*/
    /*前提条件：pq指向之前被初始化的队列*/
    /*后置条件：如果队列为空则返回true，否则返回false*/
    bool QueueIsEmpty(const Queue *pq);
    
    
    /*操作：确定队列中的项数*/
    /*前提条件：pq指向之前被初始化的队列*/
    /*后置条件：返回队列中的项数*/
    int QueueItemCount(const Queue *pq);
    
    /*操作：在队列末尾添加项*/
    /*前提条件：pq指向之前被初始化的队列，item是要被添加在队列末尾的项*/
    /*后置条件：如果队列不为空，item将被添加在队列的末尾，该函数返回true，否则队列不变并返回false*/
    bool EnQueue(Item item, Queue *pq);
    
    /*操作：在队列开头删除项*/
    /*前提条件：pq指向被初始化的队列*/
    /*后置条件：如果队列不为空，则首端的item被拷贝到*pitem中并被删除，函数返回true\ 如果此操作使队列为空则重置队列为空\ 如果队列在操作前为空，则返回false*/
    bool DeQueue(Item *pitem, Queue *pq);
    
    /*操作：清空队列*/
    /*前提条件：pq指向之前被初始化的队列*/
    /*后置条件：队列被清空*/
    void EmptyTheQueue(Queue *pq);
    #endif // _QUEUE_H_

第三步，具体实现接口函数

//queue.c//接口函数
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include "queue.h"
    
    /*局部函数*/
    static void CopyToNode(Item item, Node *pn);
    static void CopyToItem(Node *pn, Item *pi);
    
    /*初始化队列就是把队列的首尾指针设为空指针，并把队列项数设为0*/
    void InitializeQueue(Queue *pq)
    { 
        pq->front = pq->rear = NULL;
        pq->items = 0;
    }
    
    bool QueueIsEmpty(const Queue *pq)//忘记写const，和原型不一致，报错
    { 
        return pq->items==0;
    }
    
    bool QueueIsFull(const Queue *pq)//忘记写const，和原型不一致，报错
    { 
        return pq->items==MAXQUEUE;
    }
    
    int QueueItemCount(const Queue *pq)//忘记写const，和原型不一致，报错
    { 
        return pq->items;//队列有items这个成员好方便啊
        //之前链表还需要遍历才能确定项数
    }
    
    bool EnQueue(Item item, Queue *pq)
    { 
        Node *pnew;
    
        if(QueueIsFull(pq))
            return false;
        //如果真满了就直接return了，所以不用写else
        pnew = (Node *)malloc(sizeof(Node));
        if(pnew==NULL)
        { 
            fprintf(stderr, "Unable to allocate memory!\n");
            exit(1);
        }
        //如果没分到内存也就退出了，所以不用写else
        CopyToNode(item, pnew);
        pnew->next = NULL;//这一步很容易忘记
        if(QueueIsEmpty(pq))//这一步也易忘
            pq->front = pnew;
        else
            //如果队列非空，则要把pnew赋给当前尾指针指向的next成员
            pq->rear->next = pnew;
    
        //队列空不空都要把pnew给尾指针
        pq->rear = pnew;
        pq->items++;//间接成员运算符优先级高于++
        return true;
    }
    
    /*删除只能从队列首端删，且注意一定要释放内存，items要减小*/
    bool DeQueue(Item *pitem, Queue *pq)
    { 
        Node *pt;
    
        if(QueueIsEmpty(pq))
            return false;
        pt = pq->front;//如果不是空队列，则把头指针赋给pt
        //删除头指针指向的项
        CopyToItem(pq->front, pitem);//把头指针指向的内容复制出来
        pq->front = pq->front->next;//改变头指针
        free(pt);//释放头指针指向的内存
        pq->items--;
        if(pq->items==0)
            pq->rear = NULL;
        return true;
    }
    
    /*清空列表*/
    void EmptyTheQueue(Queue *pq)
    { 
        Item dummy;
        while(!QueueIsEmpty(pq))
            DeQueue(&dummy, pq);
    }
    
    /*局部函数*/
    static void CopyToNode(Item item, Node *pn)
    { 
        pn->item = item;
    }
    
    static void CopyToItem(Node *pn, Item *pi)
    { 
        *pi = pn->item;
    }

测试函数

#include <stdio.h>
    #include "queue.h"
    void eatline();
    
    int main()
    { 
        Queue line;
        Item temp;
        char ch;
    
        InitializeQueue(&line);
        puts("Testing the Queue interface. Type a to add a value, "
             "type d to delete a value, and type q to quit.");
             while((ch = getchar())!='q')
             { 
                 if(ch != 'a' && ch != 'd')//我写成或了！！！
                    continue;
                 if(ch == 'a')
                  { 
                      puts("Integer to add:");
                      scanf("%d", &(temp.gumption));
                      eatline();
                      if(QueueIsFull(&line))
                        puts("Queue is full!");
                      else
                      { 
                          printf("putting %d into the queue...\n", temp);
                          EnQueue(temp, &line);
                      }
                  }
                  else
                  { 
                      //输入的字符是d
                      if(QueueIsEmpty(&line))
                            puts("Nothing to delete!");
                      else
                      { 
                            DeQueue(&temp, &line);
                            printf("removing %d from queue...\n", temp);
                      }
    
                  }
                  printf("%d items in queue\n", QueueItemCount(&line));
                  puts("Type a to add, d to delete, q to quit:");
             }
             EmptyTheQueue(&line);
             puts("The queue has been emptied.");
    
    
        return 0;
    }
    
    void eatline()
    { 
        while(getchar()!='\n')
            ;
    }

输出

Testing the Queue interface. Type a to add a value, type d to delete a value, and type q to quit.
    a
    Integer to add:
    2
    putting 2 into the queue...
    1 items in queue
    Type a to add, d to delete, q to quit:
    a
    Integer to add:
    4
    putting 4 into the queue...
    2 items in queue
    Type a to add, d to delete, q to quit:
    a
    Integer to add:
    6
    putting 6 into the queue...
    3 items in queue
    Type a to add, d to delete, q to quit:
    d
    removing 2 from queue...
    2 items in queue
    Type a to add, d to delete, q to quit:
    d
    removing 4 from queue...
    1 items in queue
    Type a to add, d to delete, q to quit:
    d
    removing 6 from queue...
    0 items in queue
    Type a to add, d to delete, q to quit:
    d
    Nothing to delete!
    0 items in queue
    Type a to add, d to delete, q to quit:
    q
    The queue has been emptied.

## 队列模拟真实排队情况 ##

//mall.c --使用Queue接口
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include "queue.h"
    #define MIN_PER_HR 60.0
    
    bool newcustomer(double x);//是否有新顾客到来
    Item customertime(long when);//设置顾客参数
    void eatline();
    
    int main()
    { 
        Queue line;
        Item temp; //新顾客的数据
        int hours; //队列模拟多少个小时
        int perhour; //每小时平均多少顾客
        long cycle, cyclelimit; //循环计数器，循环计数器的上限
        long turnaways = 0; //因队列已满被拒的顾客数
        long customers = 0; //加入队列的顾客数量
        long served = 0; //模拟队列期间咨询过的顾客数量
        long sum_line = 0;//累计队列总长
        int wait_time = 0;//从当前到获得服务的时间
        double min_per_cust; //每个顾客平均花几分钟到来，即顾客到来的平均时间
        long line_wait = 0;//队列累计等待时间
    
        InitializeQueue(&line);
        srand((unsigned int) time(0));//给rand()随机初始化，以程序运行时系统时间为种子
        puts("Case Study: Sigmund Lander's Advice Booth");
        puts("Enter the number of simulation hours:");
        scanf("%d", &hours);
        eatline();
        cyclelimit = MIN_PER_HR * hours;//循环计数器计时上限
        puts("Enter the average number of customers per hour:");
        scanf("%d", &perhour);
        eatline();
        min_per_cust = MIN_PER_HR / perhour;
    
        for(cycle = 0;cycle < cyclelimit; cycle++)
        { 
            if(newcustomer(min_per_cust))
            { 
                if(QueueIsFull(&line))
                    turnaways++;
                else
                { 
                    customers++;
                    temp = customertime(cycle);
                    EnQueue(temp, &line);
    
                }
            }
            if(wait_time <= 0 && !QueueIsEmpty(&line))
            { 
                //等待时间为0，但队列不为空，说明此人是正在接受服务
                DeQueue(&temp, &line);
                wait_time = temp.processtime;
                line_wait += cycle - temp.arrive;
                served++;
            }
            if(wait_time > 0)
                wait_time--;
            sum_line += QueueItemCount(&line);
        }
    
        if(customers > 0)
        { 
            printf("Customers accepted: %ld\n", customers);
            printf(" Customers served: %ld\n", served);
            printf(" turnaways: %ld\n", turnaways);
            printf("average queue size: %.2f\n", (double)sum_line / cyclelimit);
            printf(" average wait time: %.2f minutes\n", (double) line_wait / served);
    
        }
        else
            puts("No customers!");
        EmptyTheQueue(&line);
        puts("Bye!");
        return 0;
    }
    
    /*如果1分钟内有顾客到来，则返回true，x是顾客到来的平均时间*/
    bool newcustomer(double x)
    { 
        if(rand() * x /RAND_MAX < 1)//rand()产生一个0-RAND_MAX之间的整数
            return true;//x小于1
        else
            return false;//x大于等于1
    }
    
    /*该函数返回一个结构，里面描述了该顾客的信息*/
    Item customertime(long when)
    { 
        Item cust;
    
        cust.processtime = rand() % 3 + 1;//1,2,3
        cust.arrive = when;
    
        return cust;
    }
    
    void eatline()
    { 
        while(getchar()!='\n')
            ;
    }

头文件中只需要改Item:

typedef struct item{ 
        long arrive;//顾客加入队列的时间，注意时间在计算机里用长整型存储的
        int processtime;//顾客咨询花费的时间
    }Item;

Case Study: Sigmund Lander's Advice Booth
    Enter the number of simulation hours:
    2
    Enter the average number of customers per hour:
    30
    Customers accepted: 52
      Customers served: 52
             turnaways: 0
    average queue size: 0.62
     average wait time: 1.42 minutes
    Bye!

[20200221222148176.png]: https://img-blog.csdnimg.cn/20200221222148176.png
[2020022212290317.png]: https://img-blog.csdnimg.cn/2020022212290317.png
[20200222123208359.png]: https://img-blog.csdnimg.cn/20200222123208359.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200222123558783.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200222124906410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200222124915486.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200222124924286.png]: https://img-blog.csdnimg.cn/20200222124924286.png
[20200222125801889.png]: https://img-blog.csdnimg.cn/20200222125801889.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200222130018260.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200222132122901.png]: https://img-blog.csdnimg.cn/20200222132122901.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200222132209282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200222132558584.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70
[20200222135520472.png]: https://img-blog.csdnimg.cn/20200222135520472.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/2020022220243879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjA3ODk0,size_16,color_FFFFFF,t_70