第十章 基本数据结构 链表结构 栈结构 队列结构 主讲：李祥 时间：2015年10月.

Presentation on theme: "第十章 基本数据结构 链表结构 栈结构 队列结构 主讲：李祥 时间：2015年10月."— Presentation transcript:

1 第十章 基本数据结构 链表结构 栈结构 队列结构 主讲：李祥 时间：2015年10月

2 10.1 链表 10.2 栈 10.3 队列

3 10.1 链表 什么是链表 通过前面的讲解可以知道，用数组存放数据时，必须事先定义数组长度。但有时程序中存放数据的个数是无法确定的。例如用数组存放一个学校的所有学生信息，由于学生的人数无法确定，这时就不知道该定义多大的数组。这种情况可以通过定义一个足够大的数组来解决，但是这样难免会浪费内存，而且也无法明确到底多大的数组才足够。在C语言中存在一种特殊的数据结构——链表，链表存储的数据个数不固定，可以很好地解决上述问题。链表是一种重要的数据结构，它是由一系列节点（链表元素）组成，节点可以在运行时动态生成。链表结构可以充分利用计算机内存空间，灵活实现内存动态管理。

4 10.1 链表 什么是链表 链表根据其逻辑结构，通常被分为单链表、双向链表、环形链表等。由于单链表的结构最为简单，所以接下来以单链表为例讲解链表的一般组成部分以及逻辑结构，如图10-1所示。 图10-1 单链表

5 10.1 链表 什么是链表 在图10-1中，链表有一个“头指针”变量（head），它存放一个地址，该地址指向一个结构体变量。链表中每一个结构体变量称为节点，每一个节点都包括数据和指针两部分，其中，数据部分用于存储用户需要的实际数据，指针部分用于指向下一个节点的地址。直到最后一个元素，该元素不再指向其他元素，它就是“尾节点”。尾节点中的指针部分指向NULL（表示空地址），表示链表到此结束。

6 10.1 链表 什么是链表 从单链表的逻辑结构可以看出，在链表中要找某一个元素，必须通过它的上一个元素中指针指向的地址才能找到。如果不提供“头指针”，则整个链表都无法访问。这就好比，幼儿园的老师带领孩子出来散步，老师牵着第1个小孩的手，第1个小孩的另一只手牵着第2个孩子……这就是一个“链”，最后一个孩子有一只手空着，他是“尾节点”。要找到这个队伍，必须先找到老师，然后顺序找到每一个孩子。 需要注意的是，链表如同一条铁链一样，一环扣一环，中间是不能断开的。

7 10.1 链表 定义与初始化链表 在程序中，经常使用链表来实现数据线性存储效果。在使用链表时，首先要了解如何定义链表以及初始化链表。链表的定义分为链表节点和链表的整体结构两部分。由于链表节点和链表的整体结构都是由两个不同类型的数据组成，因此，可以利用结构体的特性来定义链表。

8 10.1 链表 10.1.2 定义与初始化链表 首先定义链表中的节点，示例代码如下：
上述代码定义了一个Node类型的结构体，该结构体表示这个链表中的节点。Node结构体中包含两个成员：一个成员是int类型的变量data，用于保存数据；第二个成员是一个指针next，它指向一个新的Node变量。 struct Node { int data; // 数据区域 struct Node *next; // 指针区域 };

9 10.1 链表 10.1.2 定义与初始化链表 然后定义链表的整体结构，示例代码如下：
上述代码定义了一个SimLink类型的结构体，该结构体表示这个链表的结构。它包含了两个成员，一个成员是int类型的变量length，用于表示整个链表的长度；第二个成员表示首节点的指针，用于指向链表中首节点后面的节点Node。整个链表从head开始指向链表的第一个Node，第一个Node指向第二个Node，以此类推。直到某一个Node的next指针为NULL时，链表终止。 struct SimLink { int length; // 链表长度 struct Node* head; // 首节点 };

10 10.1 链表 定义与初始化链表 上面的两段示例代码只是实现了链表结构的创建，在实际应用中，使用链表之前还需要对链表进行初始化。这时需要定义一个初始化链表的函数，示例代码如下： 上述代码中，initLink()函数的参数是一个指向SimLink类型结构体变量的指针，链表结构体指针的成员head被初始化为NULL，成员length被初始化为0，此时链表完成了初始化。 void initLink(struct SimLink *link) { link->head = NULL; // 初始化首节点为NULL link->length = 0; }

11 10.1 链表 链表的常用操作 链表这种数据结构在编写程序时应用非常广泛，因此熟练地使用链表对优化程序中的数据存储很重要。接下来将针对链表的获取表元、插入元素、删除元素等常见操作进行讲解。 1、获取表元 获取表元是指根据指定下标从链表中得到对应的数据。这和从数组中获得指定元素有些类似，在链表中节点的下标也是从0开始的，即head之后的第一个节点Node下标为0。整个链表中的元素下标范围是0到length-1。下面定义一个获取表元的函数，示例代码如下：

12 10.1 链表 链表的常用操作 struct Node *getElement(struct SimLink *link, int pos) { if (pos < 0 || pos > link->length) return NULL; } struct Node *p = link->head; int i = 0; while( i < pos ) p = p->next; i++; return p;

13 10.1 链表 链表的常用操作 在上述代码中，定义了一个getElement()函数用于获取下标为pos的节点，该函数有两个参数，分别为指向链表SimLink的指针link和节点的下标pos。getElement()函数返回一个Node类型的指针，如果参数pos不在0到length-1的范围之内，则返回NULL。 在获取表元时，首先初始化一个指针p，使它指向链表中下标为0的节点。然后使用while循环来寻找下标为pos的节点Node。在当前循环中，如果下标i小于下标pos，那么就将指针p更新到p的下一个节点，并将i的值加1，直到下标i等于下标pos为止。最后返回指向该节点的指针。

14 10.1 链表 链表的常用操作 2、插入元素 单链表中的每一个元素都通过指针来记住它的后一个元素，从而将所有的元素彼此连接起来。因此当插入一个新元素时，只需要修改元素之间的这种引用关系即可，非常方便。下面定义一个插入元素的函数，示例代码如下：

15 10.1 链表 链表的常用操作 int insert(struct SimLink* link, int pos, int val) { if (pos < 0 || pos > link->length ) return 0; //如果插入失败，则返回0 } //插入表头位置 if (pos == 0) struct Node* pNew = (struct Node*)malloc(sizeof(struct Node)); pNew->data = val; pNew->next = link->head; link->head = pNew; else //插入到非表头位置 //首先找到插入点的前驱 struct Node* priv = getElement(link, pos - 1); pNew->next = priv->next; priv->next = pNew; link->length++; //更新链表长度 return 1;

16 10.1 链表 链表的常用操作 在上述代码中，定义了一个insert()函数用于向链表中的指定位置插入新元素。该函数有三个参数，分别为链表参数、插入元素的位置和插入的元素值。如果成功插入元素则返回1，否则返回0。 在向链表中插入新元素时，如果pos超出了0到length-1的范围，就直接返回不做任何插入；否则，根据pos的值是否为0分别进行处理，如果pos为0，表示将新元素插入到head和第一个节点之间，head指针修改为指向新插入的元素，新元素指向第一个节点。如果pos不为0，首先使用getElement ()函数获得pos -1处的节点Node，然后修改该节点Node的next指针指向新插入的元素，新元素指向后面的节点。

17 10.1 链表 链表的常用操作 3、查找元素 上面讲解过如何通过下标来查找链表的元素，接下来讲解如何根据给定的值，从链表中找到第一个具有相同值的节点，示例代码如下：

18 10.1 链表 链表的常用操作 struct Node* find(struct SimLink* link, int value) { struct Node* cur = link->head; while (cur != NULL) //比较过程 if (cur->data == value) //检查当前节点的值是否匹配 return cur; } else { //如果不匹配，则移动到下一个节点 cur = cur->next; return NULL;

19 10.1 链表 链表的常用操作 在上述代码中，定义了一个find ()函数用于查找元素。该函数有两个参数，分别为链表指针和要查找的值。在查找过程中，首先通过循环遍历链表中的节点并判断该节点的值是否与传入的参数value相等，如果相同便返回此节点的指针。如果链表遍历完毕，都没有找到匹配的值，则返回一个空指针（NULL）。

20 10.1 链表 链表的常用操作 4、删除元素 由于单链表中元素是依靠指向下一个元素而连接在一起的，所以，想要删除一个元素只需要改变该元素前面节点的指针指向即可。定义一个删除链表中元素的函数，示例代码如下：

21 10.1 链表 10.1.3 链表的常用操作 void delete(struct SimLink* link, int pos) {
if (pos < 0 || pos > link->length - 1) return; } struct Node* del; //首节点的情况 if (pos == 0) del = link->head; link->head = del->next; free(del); else //非首节点的情况 struct Node* priv = find(link, pos - 1); //先找到被删除节点的前驱 del = priv->next; //定位要被删除的节点 priv->next = del->next; link->length--;

22 10.1 链表 链表的常用操作 在上述代码中，定义一个delete()函数，该函数和insert()函数的流程类似，都是首先判断下标pos是否在有效范围之内，再根据pos的值是否为0分情况讨论，如果为0，则直接从首节点head开始删除，否则就从pos-1的位置开始删除。需要注意的是，要求删除元素的下标必须在0到length-1的范围之内，否则不做处理。

23 10.1 链表 链表的常用操作 5、释放链表 因为链表会占用内存空间，使用完链表后，如果不释放的话，就会一直占用内存。在C语言程序中，因为我们使用了malloc来动态申请内存，所以链表使用完后是不会自动释放内存的，需要通过程序将其释放。定义一个释放链表的函数，示例代码如下：

24 10.1 链表 链表的常用操作 上述代码中，定义了一个freeLink()函数用于释放链表，其实现过程就是不断地删除链表的第一个节点Node，直到所有的节点Node都被删除为止。 void freeLink(struct SimLink* link) { struct Node* p = link->head->next; while (p) link->head->next = p->next; free(p); p = link->head->next; } link->length = 0;

25 10.1 链表 综合案例 前面几个小节已经详细地介绍了链表的结构特点、链表的创建方式以及定义了针对链表进行操作的函数。由于链表结构的重要性，同时为了让读者能够更好地掌握链表的使用，接下来通过一个综合案例来演示如何创建链表、如何向链表中添加元素、如何查找链表、如何删除链表中的元素以及如何释放链表所占的内存，具体如例10-1所示。

26 10.1 链表 10.1.4 综合案例 例10-1 1 //单链表节点 2 struct Node 3 {
1 //单链表节点 2 struct Node 3 { 4 int data; //数据区域 5 struct Node *next; //指针区域 6 }; 7 //链表结构 8 struct SimLink 9 { 10 struct Node* head; //首节点 11 int length; //链表长度 12 }; 13 //初始化 14 void initLink(struct SimLink *link) 15 { 16 link->head = NULL; //初始化首节点为NULL 17 link->length = 0; 18 }

27 10.1 链表 综合案例 19 //取表元 20 struct Node *getElement(struct SimLink *link, int pos) 21 { 22 if (pos < 0 || pos > link->length) 23 { 24 return NULL; 25 } 26 struct Node *p = link->head; 27 int i = 0; 28 while( i < pos ) 29 { 30 p = p->next; 31 i++; 32 } 33 return p; 34 }

28 10.1 链表 综合案例 35 //插入数据 36 int insert(struct SimLink* link, int pos, int val) 37 { 38 if (pos < 0 || pos > link->length) 39 { 40 return 0; //如果插入失败，则返回1 41 } 42 //插入表头位置 43 if (pos == 0) 44 { 45 struct Node* pNew = (struct Node*)malloc(sizeof(struct Node)); 46 pNew->data = val; 47 pNew->next = link->head; 48 link->head = pNew; 49 } 50 else //插入到非表头位置 51 { 52 //首先找到插入点的前驱 53 struct Node* priv = getElement(link, pos - 1); 54 struct Node* pNew = (struct Node*)malloc(sizeof(struct Node)); 55 pNew->data = val; 56 pNew->next = priv->next; 57 priv->next = pNew; 58 } 59 link->length++; //更新链表长度 60 return 1; 61 }

29 10.1 链表 综合案例 62 //查找数据 63 struct Node* find(struct SimLink* link, int value) 64 { 65 struct Node* cur = link->head; 66 while (cur != NULL) //比较过程 67 { 68 if (cur->data == value) //检查当前节点的值是否匹配 69 { 70 return cur; 71 } 72 else 73 { //如果不匹配，则移动到下一个节点 cur = cur->next; 75 } 76 } 77 return NULL; 78 }

30 10.1 链表 综合案例 79 //删除数据 80 void delete(struct SimLink* link, int pos) 81 { 82 if (pos < 0 || pos > link->length - 1) 83 { 84 return; 85 } 86 struct Node* del; 87 //首节点的情况 88 if (pos == 0) 89 { 90 del = link->head; 91 link->head = del->next; 92 free(del); 93 } 94 else 95 { 96 //非首节点的情况 97 struct Node* priv = find(link, pos - 1); //先找到被删除节点的前驱 98 del = priv->next; //定位要被删除的节点 99 priv->next = del->next; 100 free(del); 101 } 102 link->length--; 103 }

31 10.1 链表 10.1.4 综合案例 104 //释放链表 105 void freeLink(struct SimLink* link)
104 //释放链表 105 void freeLink(struct SimLink* link) 106 { 107 struct Node* p = link->head->next; 108 while (p) 109 { 110 link->head->next = p->next; 111 free(p); 112 p = link->head->next; 113 } 114 link->length = 0; 115 }

32 10.1 链表 综合案例 116 //显示链表内容 117 void printLink(struct SimLink* link) 118 { 119 struct Node* cur = link->head; 120 if (link->length == 0) 121 { 122 printf("空表 \n"); 123 return; 124 } 125 do 126 { 127 printf("[%d] ", cur->data); 128 cur = cur->next; 129 } while (cur->next != NULL); 130 printf("\n"); 131 }

33 10.1 链表 10.1.4 综合案例 131 void main(int argc, char** argv) 132 {
132 { 133 //使用链表 134 struct SimLink link; 135 initLink(&link); 136 //插入数据 137 int i; 138 for (i = 0; i < 7; i++) 139 { 140 //插入操作 141 insert(&link, i, i); 142 } 143 printLink(&link); 144 delete(&link, 3); 145 printLink(&link); 146 freeLink(&link); 147 }

34 10.1 链表 综合案例 运行结果如图10-2所示。 图10-2 运行结果

35 10.1 链表 综合案例 在例10-1中，定义了许多函数，这些函数的功能各不相同。其中，第20-34行代码定义的函数getElement()用于获取表元。第36-61行代码定义的函数insert()用于向链表的指定位置插入元素。第63-78行代码定义的函数find()用于根据传入的参数值查找匹配元素。第80-102行代码定义的函数delete()用于删除链表中的元素。第 行代码定义的函数 freeLink()用于释放链表所占的内存。第 行代码定义的函数printLink()用于输出链表中所有的元素。最后在main()函数中依次调用这些函数，从而实现对链表中的元素进行插入、删除和输出等操功能，图10-2显示的运行结果说明案例中的函数成功的定义了一个链表，并对链表中的元素进行操作。

36 10.2 栈 什么是栈 在刷盘子的时候，需要将刷好的盘子一个叠一个地摆放好。在用盘子的时候，会将盘子一个一个取下，通常来讲，摆放盘子的时候是从最下面的一个盘子开始由下而上依次摆放，而取盘子都是从最上面的一个盘子开始按照由上而下的顺序来取，这种现象我们称之为“后进先出”原则。在C语言中有一种数据结构便遵循这种“后进先出”原则，该数据结构就是栈。栈可以使用数组实现，也可以使用链表实现，本书中将用数组来模拟栈的操作。

37 10.2 栈 什么是栈 栈是一种限定只能在一端进行插入和删除操作的线性表，其中允许插入和删除操作的一端称为栈顶，不允许插入和删除操作的一端是封闭的，称为栈底。向一个栈中插入新元素又称为入栈，操作之后该元素被放到栈顶元素的上面，成为新的栈顶元素；从一个栈中删除元素又称为出栈，是把栈顶元素删除，使其下面的相邻元素成为新的栈顶元素。为了让读者更好地理解栈的概念，接下来通过一个图例来简单描述栈的工作原理，如图10-3所示。

38 10.2 栈 什么是栈 图10-3 栈的结构

39 10.2 栈 什么是栈 从图10-3可以看出，当执行入栈操作时，会先将元素插入到栈底，然后按照插入顺序，从下往上依次排列。而执行出栈操作时，栈顶的元素会被先弹出，接着按照先上后下的顺序将上面的元素弹出。如同向枪支的弹夹里装子弹一样，子弹被一个接一个地压入；而射击时，子弹从顶部一个接一个地被射出。由于栈遵循后进先出原则，因此又把栈称为后进先出表（Last In First Out，简称LIFO）。 需要注意的是，当栈中元素已满时，就不能继续执行入栈操作。同理，栈为空时，也不能继续执行出栈操作。

40 10.2 栈 定义与初始化栈 在程序中，为了让数据的存储和获取遵循“后进先出”原则，就需要使用栈数据结构。在使用栈时，首先要了解如何定义栈以及初始化栈。栈和链表的定义方式类似，都是使用struct来实现。下面通过一段代码来演示如何定义栈，示例代码如下： #define STACK_SIZE 20 // 定义栈的最大空间 struct Stack { int datas[STACK_SIZE]; // 栈数据保存区 int top; // 栈顶位置标识，空栈时top=-1 };

41 10.2 栈 定义与初始化栈 上述代码中，首先定义了宏STACK_SIZE，并将它的值定为20。然后定义了一个结构体Stack，它由一个整型数组datas[]和一个整型变量top组成，其中datas[]的长度为STACK_SIZE，是用来存储栈中元素的。top是用来标识栈顶的位置，也可以理解为datas[]的角标，当top=0时，表示栈底，当top=STACK_SIZE-1时，表示栈顶。

42 10.2 栈 定义与初始化栈 在程序中使用一个空栈之前，往往需要先对其进行初始化操作，此时，只需要将栈顶标识符指向-1即可，示例代码如下： 上述代码中，initStack()函数接收了一个Stack指针参数，指向被操作的栈stack。其中stack->top=-1；语句表示将stack的栈顶指针指向栈底元素的前面，此时栈完成了初始化。 //初始化栈 void initStack( struct Stack* stack ) { stack->top = -1; }

43 10.2 栈 栈的常用操作 栈在编写程序时应用非常广泛，灵活地使用栈对实际开发很重要。接下来就针对入栈、出栈、读栈、清空栈等栈的常见操作进行分别讲解。

44 10.2 栈 栈的常用操作 1、判断栈是否已满或为空 在进行入栈操作时，首先需要判断栈是否已满，如果栈已满，表示栈中元素已经达到栈顶，入栈就会失败。下面定义一个判断栈是否已满的函数，示例代码如下： 上述代码中，isFull()函数也接收了一个Stack指针参数，指向被操作的栈stack。当栈顶指针top指向栈顶时，即top的值为数组的最大下标（MAXSIZE – 1）时，返回1，表示栈为满；否则返回0，表示栈未满。 //isFull()函数用来判断栈是否已满 int isFull(struct Stack* stack) { return (stack->top == MAXSIZE - 1) ? 1 : 0; }

45 10.2 栈 栈的常用操作 在进行出栈操作时，首先需要判断栈是否为空，如果栈为空，表示栈中没有元素，出栈就会失败，下面定义一个判断栈是否为空的函数，示例代码如下： 上述代码中，isEmpty()函数接收一个Stack指针参数，指向被操作的栈stack。当栈顶指针top的值为-1时，返回1，表示栈为空；否则返回0，表示栈为非空。 //isEmpty()函数用来判断栈是否为空 int isEmpty(struct Stack* stack) { return (stack->top == -1) ? 1 : 0; }

46 10.2 栈 栈的常用操作 2、入栈操作 当栈中缺少元素时，就需要执行入栈操作，入栈操作实际上就是向栈顶添加一个元素。当然在实现入栈操作前，需要判断栈是否已满。下面定义一个入栈操作的函数，示例代码如下： int push(struct Stack* stack, int value) { //先判断是否栈满 if (isFull(stack)) return 0; } stack->datas[++stack->top] = value; //赋值之前将栈顶指针向上移动 return 1;

47 10.2 栈 栈的常用操作 上述代码中，push()函数接收一个Stack指针参数和整型变量，其中Stack指针指向被操作的栈stack，整型变量表示被插入到栈中的元素value。在加入新元素value之前，首先调用isFull()函数判断stack是否已满，如果栈已满，返回0，表示入栈失败。否则将栈顶指针向上移动，即新元素将要加入的位置，然后将value添加到新位置上，并返回1，表示入栈成功。

48 10.2 栈 栈的常用操作 3、出栈操作 当栈中包含多余的元素时，就需要执行出栈操作。出栈操作实际上是将栈顶元素弹出栈的过程。当然在实现出栈操作前，需要判断栈是否为空。下面定义一个出栈操作的函数，示例代码如下： int pop( struct Stack* stack, int* retValue ) { //先检查栈是否为空 if ( isEmpty(stack)) return 0; } *retValue = stack->datas[ stack->top--]; return 1;

49 10.2 栈 栈的常用操作 上述代码中，pop()函数接收一个Stack类型指针和整型指针变量，其中Stack指针指向被操作的栈stack，整型指针变量retValue用于得到栈顶元素的值。pop()函数的返回值为int类型，表示操作成功或失败的状态。在获取栈顶值之前，首先调用isEmpty()函数判断stack是否为空，当栈不为空时，获取栈顶元素的值，并将retValue指针指向出栈值的内存地址，最后top向栈底方向移动一个位置，指向新的栈顶位置。

50 10.2 栈 栈的常用操作 多学一招：读栈操作 在程序中有时只是想查看栈顶的元素，并根据查看的结果来决定是否需要将这个元素弹出栈。这时，就不需要移动top指针的位置。接下来通过一段示例代码演示如何实现读栈操作，具体代码如下： int getTop(struct Stack* stack, int* retValue ) { //先判断栈是否为空 if ( isEmpty(stack) ) return 0; } *retValue = stack->datas[ stack->top]; return 1;

51 10.2 栈 栈的常用操作 从上述代码中可以看出，getTop()函数获取栈顶元素的实现原理和pop()函数是一样的。仔细对比两个函数，会发现虽然两个函数返回的元素是一样的，但是pop()函数在返回栈顶元素的同时还修改了top的值，而getTop()函数仅仅返回栈顶元素，栈顶位置的元素并没有被修改。

52 10.2 栈 栈的常用操作 4、清空栈 当栈中的所有元素都没有意义时，为了防止数据泄露，就需要对栈中的数据进行清空操作。清空栈实际上是将栈内所有的元素都删除，这和初始化栈的原理是一样的。下面定义一个清空栈的函数，示例代码如下： void Empty(struct Stack* stack) { stack->top = -1; }

53 10.2 栈 栈的常用操作 上述代码中，Empty ()函数接收一个Stack指针参数，指向被操作的栈stack，然后通过将stack中的栈顶指针top设为-1实现栈的清空效果，它的实现原理和initStack()函数是一样的。 需要注意的是，清空一个栈并没有必要将栈中的所有元素一个一个弹出栈，或者将这些元素都设为0。只需要将栈顶标识符top移到栈底之前就可以了。

54 10.2 栈 综合案例 前面几个小节已经详细地讲解了栈的结构特点、栈的创建以及一些针对栈的相关函数。由于栈结构的重要性，同时为了让读者能够更好地掌握栈的使用，接下来通过一个综合案例来演示如何创建栈、如何向栈中添加和删除元素、如何判断栈是否为空或已满、如何清空栈以及如何读取栈中元素的值，具体如例10-2所示。

55 10.2 栈 10.2.4 综合案例 例10-2 1 #include <stdio.h>
2 #define STACK_SIZE 20 //定义栈的最大空间 3 struct Stack 4 { 5 int datas[STACK_SIZE]; //栈数据保存区 6 int top; //栈顶位置标识，空栈时top=-1 7 }; 8 //初始化栈 9 void initStack(struct Stack* stack) 10 { 11 stack->top = -1; 12 } 13 //清空栈 14 void Empty(struct Stack* stack) 15 { 16 stack->top = -1; 17 }

56 10.2 栈 10.2.4 综合案例 18 //判断栈空 19 int isEmpty(struct Stack* stack) 20 {
18 //判断栈空 19 int isEmpty(struct Stack* stack) 20 { 21 return (stack->top == -1) ? 1 : 0; 22 } 23 //判断栈满 24 int isFull(struct Stack* stack) 25 { 26 return (stack->top == STACK_SIZE - 1) ? 1 : 0; 27 } 28 //入栈操作 29 int push(struct Stack* stack, int value) 30 { 31 //先判断是否栈满 32 if (isFull(stack)) 33 { 34 return 0; 35 } 36 stack->datas[++stack->top] = value; 37 return 1; 38 }

57 10.2 栈 综合案例 39 //出栈操作 40 int pop(struct Stack* stack, int* retValue) 41 { 42 //先检查栈是否为空 43 if (isEmpty(stack)) 44 { 45 return 0; 46 } 47 *retValue = stack->datas[stack->top--]; 48 return 1; 49 } 50 //读栈操作 51 int getTop(struct Stack* stack, int* retValue) 52 { 53 //先判断栈是否为空 54 if (isEmpty(stack)) 55 { 56 return 0; 57 } 58 *retValue = stack->datas[stack->top]; 59 return 1; 60 }

58 10.2 栈 10.2.4 综合案例 61 //打印栈内容 62 void printStack(struct Stack* stack)
61 //打印栈内容 62 void printStack(struct Stack* stack) 63 { 64 if (isEmpty(stack)) 65 { 66 printf("空栈！\n"); 67 return; 68 } 69 printf("当前栈的内容：\n"); 70 int i; 71 for (i = stack->top; i > -1; i--) 72 { 73 printf("[%d]:%d \n", i, stack->datas[i]); 74 } 75 printf("-=END=-\n"); 76 }

59 10.2 栈 10.2.4 综合案例 77 void main(int argc, char** argv) 78 { 79 //初始化栈
78 { 79 //初始化栈 80 struct Stack stack; 81 initStack(&stack); 82 //压栈 83 int i; 84 for (i = 1; i <= 10; i++) 85 { 86 push(&stack, i * 10); //向栈中插入数据 87 } 88 printStack(&stack); 89 //出栈 90 int tmp; 91 for (i = 0; i < 3; i++) 92 { 93 pop(&stack, &tmp); 94 } 95 printStack(&stack); 96 }

60 10.2 栈 综合案例 运行结果如图10-4所示。 图10-4 运行结果

61 10.2 栈 综合案例 在例10-2中，定义了许多函数，这些函数的功能各不相同。其中，第8-16行代码定义的initStack()函数和Empty()函数分别用于初始化栈和清空栈，第18-26行代码定义的isEmpty()函数和isFull()函数分别用于判断栈是否为空或已满，第28-48行代码定义的push()函数和pop()函数分别用于向栈中插入元素和删除栈顶元素的操作，第50-75行代码定义的getTop()函数和printStack()函数分别用于读栈顶元素和打印栈中所有元素的操作。在main()函数中依次调用这些函数，从而实现入栈、出栈和清空栈等功能，图10-4中显示的运行结果说明案例中的函数成功的定义了一个栈，并对栈中的元素进行操作。

62 10.3 队列 什么是队列 在现实生活中，大家都有过排队买火车票的经历，在排队买票时，总是排在前面的人先买到票，然后买完票也是先离开排队的队伍。队列的存储结构就好像一支排队买票的队伍，队列就是一个线性表，元素是从表的一端进行插入，从表的另一端进行删除，它遵循的是“先进先出”的原则，因此也被称为先进先出表（First In First Out, 简称FIFO）。 和栈一样，队列也是运算受限的，其插入和删除操作被限定在表的两端。习惯上我们把向队列插入元素称为入队（put），删除队列元素称为出队（pop），插入端称为队尾（rear），删除端称为队头（front）。

63 10.3 队列 10.3.1 什么是队列 为了让读者更好地理解队列的概念，接下来通过一个示意图来演示入队、出队的过程，如图10-5所示。
图10-5 队列示意图 从图10-5可以看出，有一个队列，队列中元素分别为a1，a2，a3，…，an-1，an，其中a1端是队头，队列只能从队头一端出队，an端是队尾，队列只能从队尾一端出入队，并且先入队的a1也会先于其他队列元素而出队。

64 10.3 队列 定义与初始化队列 在使用队列时，首先需要定义队列和初始化队列。队列的定义方式与栈、链表的定义方式类似，也是使用struct关键字来实现。下面通过一段示例代码来演示如何定义队列，具体如下： #define QUEUE_SIZE 1000 //定义队列 struct Queue { int front; //头指针，队非空时指向队头元素 int rear; //尾指针，队非空时指向队尾元素的下一位置 int data[QUEUE_SIZE]; }

65 10.3 队列 定义与初始化队列 上述示例代码就是队列的定义，使用struct关键字声明了一个Queue类型的结构体，用于描述队列的数据结构，该结构体中包含三个成员，其中，front指向的是队头元素的位置，rear指向的是队尾元素的下一个位置，data[QUEUE_SIZE]用于存储队列中的元素，并且队列的长度为QUEUE_SIZE。 一个队列定义好后，就需要对其进行初始化才能使用。队列的初始化很简单，只需要将头指针front和尾指针rear的初始值置为0即可，示例代码如下：

66 10.3 队列 定义与初始化队列 上述示例代码中，initQueue()函数实现了初始化队列的功能，其中queue->front = 0表示将头指针初始值置为0，queue->rear = 0表示将尾指针初始值置为0。需要注意的是，初始化队列时，如果不将头指针和尾指针赋值为0，那么它们将变成空指针，此时使用这两个指针可能会导致不可预料的后果，甚至是系统崩溃。 //初始化队列 void initQueue(struct Queue* queue) { queue->front = 0; queue->rear = 0; }

67 10.3 队列 队列的常见操作 队列在编写程序时应用较为广泛，灵活地使用队列对实际开发很重要。接下来就针对判断队列空、判断队列满、入队、出队和清空队列等队列的常见操作分别讲解。 1、判断队列空与队列满 队列存在两种特殊的情况，即队列空和队列满。当队列中没有元素时为空队列，当队列中元素个数等于队列长度时为队列满。下面通过两段示例来演示如何判断队列为空和满的情况。

68 10.3 队列 10.3.3 队列的常见操作 判断队列是否为空的操作通常用于出队的前置判断条件。判断队列空的示例代码如下所示：
上述示例代码中，定义了一个isEmpty()函数，它可以接收队列指针实参，在该函数内部，当队列的队头指针与队尾指针指向同一个元素时，即可判断队列为空队列。 int isEmpty(struct Queue* queue) { return (queue->front == queue->rear) ? 1 : 0; }

69 10.3 队列 10.3.3 队列的常见操作 判断队列是否为满的操作通常用于入队的前置判断条件。判断队列满的示例代码如下所示：
上述示例代码中，定义了一个isFull()函数，它也可以接收队列指针实参，在该函数内部，通过队尾元素指针位置加1与队列长度求模，判断是否出现了队列溢出问题，出现溢出问题说明队列满，否则说明队列没有满。 int isFull(struct Queue* queue) { return ((queue->rear+1) % QUEUE_SIZE) == queue->front; }

70 10.3 队列 10.3.3 队列的常见操作 脚下留心：队列操作的溢出现象 在对队列进行操作时，可能会出现两种溢出现象，具体如下：
“下溢”现象。“下溢”是指当队列为空时，进行出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 “上溢”现象。“上溢”是指当队列满时，进行入队运算产生的溢出的现象。这是一种出错状态，应设法避免。 值得一提的是，由于入队和出队操作中，头尾指针只增加不减小，因此被删元素的空间永远无法重新被利用。当队列中实际的元素个数远远小于队列长度时，也可能由于尾指针已超越队列空间的上界而不能做入队操作。

71 10.3 队列 队列的常见操作 2、入队操作 入队操作实际上是将新元素插入rear所指的位置，然后将rear加1。入队操作的示例代码如下所示： int enQueue(struct Queue* queue, int element) { //判断队列是否已满 if (isFull(queue)) return 0; queue->data[queue->rear] = element; queue->rear = (queue->rear + 1) % QUEUE_SIZE; return 1; }

72 10.3 队列 队列的常见操作 上述示例代码中，enQueue()函数实现了向队列中加入一个元素的功能，在该函数内部，执行入队操作前首先进行了队列满的判断，当队列未满时再通过约定的规则进行入队操作。值得注意的是，如果队尾指针达到数组的最大下标，通过代码求模运算可将队尾指针“折返”至数组前端，可以继续使用队头释放的数组空间。

73 10.3 队列 队列的常见操作 3、出队操作 出队操作实际上是删去front所指的元素，然后将front加1并返回被删元素。出队操作的示例代码如下所示： 上述示例代码中，deQueue()函数实现了从队列中删除一个元素的功能，在该函数内部，执行出队操作前首先进行了队列空的判断，当队列不为空时再通过约定的规则进行出队操作。 int deQueue(struct Queue* queue, int* element) { //判断队列是否为空 if (isEmpty(queue)) return 0; *element = queue->data[queue->front]; queue->front = (queue->front + 1) % QUEUE_SIZE; return 1; }

74 10.3 队列 队列的常见操作 4、清空队列 在操作队列时，为了节约内存资源，最后还需要进行清空队列操作，清空队列实际上就是删除队列中所有的元素，这和队列的初始化操作一样，只需要将front和rear重新置为0即可。清空队列操作的示例代码如下所示： void cleanQueue(struct Queue* queue) { queue->front = 0; queue->rear = 0; }

75 10.3 队列 综合案例 前面讲解了定义队列、初始化队列以及队列相关的一些常见操作，为了让读者能更好地掌握这些知识，接下来通过一个具体的案例来演示如何定义队列、如何初始化队列、如何向队列中插入元素、如何删除队列中的元素以及如何清空队列中的元素，如例10-3所示。

76 10.3 队列 10.3.4 综合案例 例10-3 1 #include <stdio.h>
2 #define QUEUE_SIZE 1000 3 //定义结构体 4 struct Queue 5 { 6 int front; //头指针，队非空时指向队头元素 7 int rear; //尾指针，队非空时指向队尾元素的下一位置 8 int data[QUEUE_SIZE]; 9 }; 10 //初始化队列 11 void initQueue(struct Queue* queue) 12 { 13 queue->front = 0; 14 queue->rear = 0; 15 } 16 //判断队列空 17 int isEmpty(struct Queue* queue) 18 { 19 return (queue->front == queue->rear) ? 1 : 0; 20 }

77 10.3 队列 10.3.4 综合案例 21 //判断队列满 22 int isFull(struct Queue* queue) 23 {
21 //判断队列满 22 int isFull(struct Queue* queue) 23 { 24 //判断队列是否已满,这里我们牺牲一个空间 25 return ((queue->rear + 1) % QUEUE_SIZE) == queue->front; 26 } 27 //入队操作 28 int enQueue(struct Queue* queue, int element) 29 { 30 //判断队列是否已满 31 if (isFull(queue)) 32 return 0; 33 queue->data[queue->rear] = element; 34 queue->rear = (queue->rear + 1) % QUEUE_SIZE; 35 return 1; 36 }

78 10.3 队列 综合案例 37 //出队操作 38 int deQueue(struct Queue* queue, int* element) 39 { 40 //判断队列是否为空 41 if (isEmpty(queue)) 42 return 0; 43 *element = queue->data[queue->front]; 44 queue->front = (queue->front + 1) % QUEUE_SIZE; 45 return 1; 46 } 47 //清空队列 48 void cleanQueue(struct Queue* queue) 49 { 50 queue->front = 0; 51 queue->rear = 0; 52 } 53 //打印队列中的元素 54 void printQueue(struct Queue* queue) 55 { 56 int i; 57 for (i = queue->front; i % QUEUE_SIZE < queue->rear; i++) 58 { 59 printf("%d ", queue->data[i]); 60 } 61 printf("\n"); 62 }

79 10.3 队列 10.3.4 综合案例 63 //主函数 64 void main() 65 { 66 struct Queue que;
63 //主函数 64 void main() 65 { 66 struct Queue que; 67 int temp; 68 initQueue(&que); 69 printQueue(&que); 70 enQueue(&que,3); 71 enQueue(&que,5); 72 enQueue(&que,12); 73 printQueue(&que); 74 deQueue(&que, &temp); 75 printf("deQueue %d\n", temp); 76 printQueue(&que); 77 deQueue(&que, &temp); 78 printf("deQueue %d\n", temp); 79 printQueue(&que); cleanQueue(&que); 81 }

80 10.3 队列 综合案例 运行结果如图10-6所示。 图10-6 运行结果

81 10.3 队列 综合案例 在例10-3中，定义了许多函数，这些函数的功能各不相同。其中，第10~14行代码定义的initQueue()函数用于对该队列进行初始化，第27~35行代码定义的enQueue()函数用于向队列插入元素，第37~45行代码定义的deQueue()函数用于删除队列中指定元素，第47~51行代码定义的cleanQueue()函数用于清空队列中所有元素并释放所占资源，第53~61行代码定义的printQueue()函数用于打印队列中的所有元素。最后在main()函数中依次调用这些函数，从而实现初始化队列、向队列中插入元素、删除队列中指定元素以及清空队列中元素等功能，图10-6显示的运行结果说明定义队列成功，并对该队列成功地进行了各种操作。

82 本章主要讲解了C语言中的三种基本数据结构，分别是链表、栈和队列。通过本章的学习，读者应该能够掌握这三种数据结构的存储原理、定义以及常用操作。掌握本章的内容将有助于优化程序中的数据存储，提高程序的运行效率。