17.1 研究数据表示

在开始编写代码之前，要做很多程序设计方面的决定。

数组表示相对不灵活，在运行时确定所需内存量会更好。

假设要编写一个程序，让用户输入一年内看过的电影，存储影片的信息。可以使用结构储存电影，用结构数组存储多部电影。但给数组分配空间时，会出现分配空间过大浪费或者分配空间过小不够用的问题。使用动态内存(malloc)分配可以解决这个问题。

示例程序：

// films1.c -- 使用一个结构数组 
#include <stdio.h>
#include <string.h>#define TSIZE 45 // 储存片名的数组大小
#define FMAX 5   // 影片的最大数量struct film
{char title[TSIZE];int rating;
};char *s_gets(char str[], int lim);int main(void){struct film movies[FMAX];int i = 0;int j;puts("Enter first movie title:");while (i < FMAX && s_gets(movies[i].title, TSIZE) != NULL && movies[i].title[0] != '\0'){puts("Enter your rating <0-10>:");scanf("%d", &movies[i++].rating);while (getchar() != '\n')continue;puts("Enter next movie title (empty line to stop):");}if (i == 0)printf("No data entered. ");elseprintf("Here is the movie list:\n");for (j = 0; j < i; j++)printf("Movies: %s Rating: %d\n", movies[j].title, movies[j].rating);printf("Bye!\n");return 0;
}char *s_gets(char *st, int n)
{char *ret_val;char *find;ret_val = fgets(st, n, stdin);if (ret_val){find = strchr(st, '\n'); // 查找换行符if (find)                // 如果地址不是NULL*find = '\0';        // 在此处放置一个空字符 elsewhile (getchar() != '\n')continue; // 处理输入行的剩余字符 }return ret_val;
}

17.2 从数组到链表

结构声明中不能有与本身类型相同的结构，但是可以有指向同类型结构的指针。

链表是由一系列结构体构成，每个结构体都有一个指针，该指针指向下一个结构。最后一个成员中此指针的值是0。

为了访问链表，需要一个单独的指针存储第一个成员的地址。

把用户接口和代码细节分开的程序更容易理解和更新。

示例程序：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TSIZE 45 //片名大小struct film {char title[TSIZE];int rating;struct film * next; //指向链表的下一个结构
};char * s_gets(char * st, int n);int main(void)
{struct film * head = NULL;struct film * prev = NULL, *current = NULL;char input[TSIZE];puts("输入第一部电影的名字：");while (s_gets(input, TSIZE) != NULL && input[0] != '\0'){current = (struct film *) malloc(sizeof(struct film));if (head == NULL)head = current;elseprev->next = current;current->next = NULL;strcpy(current->title, input);puts("输入评分<0-10>:");scanf("%d", &current->rating);while (getchar() != '\n')continue;puts("输入下一部电影名字(直接回车可退出）");prev = current;}//显示电影if (head == NULL)printf("无数据.");else{printf("电影列表如下：\n");current = head;while (current != NULL){printf("电影:%s 评分:%d\n", current->title, current->rating);current = current->next;}}//释放内存current = head;while (head != NULL)  //此处和书不同，书上运行出错。我认为这里应该判断head是否NULL而不是current是否为NULL{current = head;head =head->next;free(current);}printf("BYE\n");return 0;
}char * s_gets(char * st, int n)
{char * ret_val;char * find;ret_val = fgets(st, n, stdin);if (ret_val){find = strchr(st, '\n');//查找换行符if (find)*find = '\0'; //将换行符换成'\0'elsewhile (getchar() != '\n')  //处理输入行剩余的字符continue;}return ret_val;
}

17.3 抽象数据类型（ADT）

类型特指两种信息：属性和操作。要定义一个新的数据类型，就必须提供存储数据的方法，还有操控数据的方法。

定义新类型的好方法是：先提供类型属性和相关操作的抽象描述。这些描述不依赖特定的实现，也不依赖特定的编程语言，称为抽象数据类型（ADT）。再开发一个实现ADT的编程接口，指明如何存储数据和执行所需操作的函数。最后编写代码实现接口。

C语言中通常的做法是，把类型定义和函数原型放在一个头文件中，该头文件提供信息。实现接口需要一个源文件，记录需要函数的细节。程序由头文件、包含处理此类型函数的源文件和主干操作的源文件组成。

对于大型项目而言，把实现和最终接口隔离的做法相当有用。

定义新类型的好方法：

1. 提供类型属性和相关操作的抽象描述。这些描述即不能依赖特定的实现，也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型（ADT）。
2. 开发一个实现 ADT 的编程接口。即指明如何存储数据和执行所需操作的函数。
3. 编写代码实现接口。

下面是链表的具体实现：

list.h：

//list.h
#pragma once 
#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;
typedef Node * List;/*函数原型*//*操作：   初始化一个链表   */
/*前提条件： plist指向一个链表 */
/*后置条件： 链表初始化为空   */
void InitializeList(List * plist);/*操作：   确定链表是否为空定义，plist指向一个已初始化的链表 */
/*后置条件： 如果链表为空，返回ture；否则返回false       */
bool ListIsEmpty(const List * plist);/*操作：   确定链表是否已满，plist指向一个已初始化的链表   */
/*后置条件： 如果链表已满，返回true；否则返回false       */
bool ListIsFull(const List * plist);/*操作：   确定链表中的项数，plist指向一个已初始化的链表   */
/*后置条件： 返回链表中的项数                  */
unsigned 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);

list.c：

//list.c
#include<stdio.h>
#include<stdlib.h>
#include"list.h"static void CopyToNode(Item item, Node * pnode);void InitializeList(List * plist)
{*plist = NULL;
}bool ListIsEmpty(const List * plist)
{if (*plist == NULL)return true;elsereturn  false;
}bool ListIsFull(const List * plist)
{Node * pt;bool full;pt = (Node *)malloc(sizeof(Node));if (pt == NULL)full = true;elsefull = false;free(pt);return full;
}unsigned int ListItemCount(const List * plist)
{unsigned int count = 0;Node * pnode = *plist;while (pnode != NULL){++count;pnode = pnode->next;}return count;
}bool AddItem(Item item, List * plist)
{Node * pnew;Node * scan = *plist;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;
}void Traverse(const List * plist, void(*pfun)(Item item)) 
{Node * pnode = *plist;while (pnode!= NULL){(*pfun)(pnode->item);pnode = pnode->next;}
}void EmptyTheList(List * plist)
{Node * psave;while (*plist != NULL){psave = (*plist)->next;free(*plist);*plist = psave;}
}
static void CopyToNode(Item item, Node * pnode)
{pnode->item = item;
}

示例程序：

/*film3.c            */
/*与list.c一起编译        */
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"list.h"
void showMovies(Item item);
char * s_gets(char * st, int n);
int main(void)
{List movies;Item temp;/*初始化 */InitializeList(&movies);if (ListIsFull(&movies)){fprintf(stderr, "无可用内存，告辞。\n");exit(1);}/*获取用户输入 并存储*/puts("输入第一个电影名称：");while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '\0'){puts("输入你的评分<0-10>:");scanf("%d", &temp.rating);while (getchar() != '\n')continue;if (AddItem(temp, &movies) == false){fprintf(stderr, "分配内存出错\n");break;}if (ListIsFull(&movies)){puts("列表满了.");break;}puts("输入下一步电影名称(回车结束程序)");}/*显示*/if (ListIsEmpty(&movies))printf("列表为空");else {printf("Here is the movie list:\n");Traverse(&movies, showMovies);}printf("你输入了%d个电影\n", ListItemCount(&movies));/*清理*/EmptyTheList(&movies);printf("再见\n");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;char * find;ret_val = fgets(st, n, stdin);if (ret_val){find = strchr(st, '\n');//查找换行符if (find)*find = '\0'; //将换行符换成'\0'elsewhile (getchar() != '\n')  //处理输入行剩余的字符continue;}return ret_val;
}

17.4 队列ADT

队列是具有一些特殊属性的链表，新项只能添加到链表的末尾，只能从链表的开头移除项。队列先进先出。

17.5 用队列进行模拟

队列特性：先进先出。

示例程序：

// mall.c -- 使用Queue接口
// 和queue.c一起编译
#include <stdio.h>
#include <stdlib.h>     // 提供rand()和srand()的原型 
#include <time.h>       // 提供time()的原型 
#include "17_6_queue.h" // 更改Item的typedef 
#define MIN_PER_HR 60.0bool newcustomer(double x);   // 是否有新顾客到来？
Item customertime(long when); // 设置顾客参数int main(void)
{Queue line;             // 新的顾客数据 Item temp;              // 模拟的小时数 int hours;              // 每小时平均多少位顾客 int perhour;            // 每小时平均多少位顾客long cycle, cyclelimit; // 循环计数器、计数器的上限long turnaways = 0;     // 因队列已满被拒的顾客数量 long customers = 0;     // 加入队列的顾客数量long served = 0;        // 在模拟期间咨询过Sigmund的顾客数量 long sum_line = 0;      // 累计的队列总长 long wait_time = 0;     // 从当前到Sigmund空闲所需的时间 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);cyclelimit = MIN_PER_HR * hours;puts("Enter the average number of customers per hour:");scanf("%d", &perhour);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)){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);}elseputs("No customers!");EmptyTheQueue(&line);return 0;
}
// x是顾客到来的平均时间（单位：分钟）
// 如果1分钟内有顾客到来，则返回true
bool newcustomer(double x)
{if (rand() * x / RAND_MAX < 1)return true;elsereturn false;
}
// when是顾客到来的时间
// 该函数返回一个Item结构，该顾客到达的时间设置为when
// 咨询时间设置为1~3的随机值
Item customertime(long when)
{Item cust;cust.processtime = rand() % 3 + 1;cust.arrive = when;return cust;
}

17.6 链表和数组

数组是C语言直接支持的，可以随机访问，但是数组在编译时就确定大小，插入和删除元素很麻烦。链表运行时确定大小，插入删除很方便，但是不能随机访问，开发难度大。

对于一个排序的列表，二分查找的效率比顺序查找要高得多。二分查找把所有元素分为一半，比中间的小就去前半部分，比中间元素大就去后半部分，与中间的相等就算找到了，进入前半或后半部分后以此类推。

如果经常使用增删操作，使用链表更好。如果经常查找，数组更好。

数组和链表优缺点：

17.7 二叉查找树

二叉树的每个节点有两个指针，这两个指针指向其他节点（分别称为左节点和右节点）。

一般左节点在的项在父节点前面，右节点的项在父节点后面。如果一侧没有子节点，则指向这一侧的指针为NULL。二叉树的顶端称为根。一个节点和它的所有节点构成子树。

用二叉树每次查找就会排除一半的节点，效率高，但是更复杂。

实现：

// tree.h -- 二叉查找树// 树种不允许有重复的项#ifndef _TREE_H_#define _TREE_H_#include <stdbool.h>// 根据具体情况重新定义Item#define SLEN 20typedef struct item
{char petname[SLEN];char petkind[SLEN];} Item;#define MAXITEMS 10typedef struct trnode{Item item;struct trnode *left; // 指向左分支的指针struct trnode *right; // 指向右分支的指针} Trnode;typedef struct tree{Trnode *root; // 指向根节点的指针int size; // 树的项数} Tree;// 函数原型// 操作： 把树初始化为空// 前提条件： ptree指向一个树// 后置条件： 树被初始化为空void InitializeTree(Tree *ptree);// 操作： 确定树是否为空// 前提条件： ptree指向一个树// 后置条件： 如果树为空，该函数返回true，否则返回falsebool TreeIsEmpty(const Tree *ptree);// 操作： 确定树是否已满// 前提条件： ptree指向一个树// 后置条件： 如果树已满，该函数返回true，否则返回falsebool TreeIsFull(const Tree *ptree);// 操作： 确定树的项数// 前提条件： ptree指向一个树// 后置条件： 返回树的项数int TreeItemCount(const Tree *ptree);// 操作： 在树中添加一个项// 前提条件： pi是待添加项的地址，ptree指向一个一初始化的树// 后置条件： 如果可以添加，该函数将在树中添加一个项并返回true，否则返回falsebool AddItem(const Item *pi, Tree *ptree);// 操作： 在树中查找一个项// 前提条件： pi指向一个项，ptree指向一个已初始化的树// 后置条件： 如果在树中添加一个项，该函数返回true，否则返回falsebool InTree(const Item *pi, const Tree *ptree);// 操作： 从树中删除一个项// 前提条件： pi是删除项的地址，ptree指向一个已初始化的树// 后置条件： 如果从树中成功删除一格项，该函数返回true，否则返回falsebool DeleteItem(const Item *pi, Tree *ptree);// 操作： 把函数应用到树中的每一项// 前提条件： ptree指向一个树，pfun指向一个函数，该函数接收一个Item类型的参数，并无返回值// 后置条件： pfun咋想的这个函数为树中的每一项执行一次void Traverse(const Tree *ptree, void (*pfun)(Item item));// 操作： 删除树中的所有内容// 前提条件： ptree指向一个已初始化的树// 后置条件： 树为空void DeleteAll(Tree *ptree);

// tree.c -- 树的支持函数#include <string.h>#include <stdio.h>#include <stdlib.h>#include "17_10_tree.h"// 局部数据类型typedef struct pair
{Trnode *parent;Trnode *child;} Pair;// 局部函数的原型static Trnode *MakeNode(const Item *pi);static bool ToLeft(const Item *i1, const Item *i2);static bool ToRight(const Item *i1, const Item *i2);static void AddNode(Trnode *new_node, Trnode *root);static void InOrder(const Trnode *root, void (*pfun)(Item item));static Pair SeekItem(const Item *pi, const Tree *ptree);static void DeleteNode(Trnode **ptr);static void DeleteAllNodes(Trnode *ptr);// 函数定义void InitializeTree(Tree *ptree){ptree->root = NULL;ptree->size = 0;
}bool TreeIsEmpty(const Tree *ptree){if (ptree->root == NULL)return true;elsereturn false;
}bool TreeIsFull(const Tree *ptree){if (ptree->root == NULL)return true;elsereturn false;
}int TreeItemCount(const Tree *ptree){if (ptree->size == MAXITEMS)return true;elsereturn false;
}bool AddItem(const Item *pi, Tree *ptree){Trnode *new_node;if (TreeIsFull(ptree)){fprintf(stderr, "Tree is full\n");return false; // 提前返回}if (SeekItem(pi, ptree).child != NULL){fprintf(stderr, "Attempted to add duplicate item\n");return false; // 提前返回}new_node = MakeNode(pi); // 指向新节点if (new_node == NULL){fprintf(stderr, "Couldn't create node\n");return false; // 提前返回}// 成功创建了一个新节点ptree->size++;if (ptree->root == NULL) // 情况1：树为空ptree->root = new_node; // 新节点为树的根节点else // 情况2：树不为空AddNode(new_node, ptree->root); // 在树中添加新节点return true; // 成功返回
}bool InTree(const Item *pi, const Tree *ptree){return (SeekItem(pi, ptree).child == NULL) ? false : true;
}bool DeleteItem(const Item *pi, Tree *ptree){Pair look;look = SeekItem(pi, ptree);if (look.child == NULL)return false;if (look.parent == NULL) // 删除根节点项DeleteNode(&ptree->root);else if (look.parent->left == look.child)DeleteNode(&look.parent->left);elseDeleteNode(&look.parent->right);ptree->size--;return true;
}void Traverse(const Tree *ptree, void (*pfun)(Item item)){if (ptree != NULL)InOrder(ptree->root, pfun);
}void DeleteAll(Tree *ptree){if (ptree != NULL)DeleteAllNodes(ptree->root);ptree->root = NULL;ptree->size = 0;
}// 局部函数static void InOrder(const Trnode *root, void (*pfun)(Item item)){if (root != NULL){InOrder(root->left, pfun);(*pfun)(root->item);InOrder(root->right, pfun);}
}static void DeleteAllNodes(Trnode *root){Trnode *pright;if (root != NULL){pright = root->right;DeleteAllNodes(root->left);free(root);DeleteAllNodes(pright);}
}static void AddNode(Trnode *new_node, Trnode *root){if (ToLeft(&new_node->item, &root->item)){if (root->left == NULL) // 空子树root->left = new_node; // 把结点添加到此处elseAddNode(new_node, root->left); // 否则处理该子树}else if (ToRight(&new_node->item, &root->item)){if (root->right == NULL) // 空子树root->right = new_node; // 把结点添加到此处elseAddNode(new_node, root->right); // 否则处理该子树}else // 不允许有重复项{fprintf(stderr, "location error in AddNode()\n");exit(1);}
}static bool ToLeft(const Item *i1, const Item *i2){int comp1;if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)return true;else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0)return true;elsereturn false;
}static bool ToRight(const Item *i1, const Item *i2){int comp1;if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)return true;else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0)return true;elsereturn false;
}static Trnode *MakeNode(const Item *pi){Trnode *new_node;new_node = (Trnode *)malloc(sizeof(Trnode));if (new_node != NULL){new_node->item = *pi;new_node->left = NULL;new_node->right = NULL;}return new_node;
}static Pair SeekItem(const Item *pi, const Tree *ptree){Pair look;look.parent = NULL;look.child = ptree->root;if (look.child == NULL)return look; // 提前返回while (look.child == NULL){if (ToLeft(pi, &(look.child->item))){look.parent = look.child;look.child = look.child->left;}else if (ToRight(pi, &(look.child->item))){look.parent = look.child;look.child = look.child->right;}else // 如果前两种情况都不满足，则必定是相等的情况break; // look.child目标项的结点}return look; // 成功返回
}static void DeleteNode(Trnode **ptr) // ptr是指向目标节点的父节点指针成员的地址{Trnode *temp;if ((*ptr)->left == NULL){temp = *ptr;*ptr = (*ptr)->right;free(temp);}else if ((*ptr)->right == NULL){temp = *ptr;*ptr = (*ptr)->left;free(temp);}else // 被删除的结点有两个子节点{// 找到重新连接右子树的位置for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)continue;temp->right = (*ptr)->right;temp = *ptr;*ptr = (*ptr)->left;free(temp);}
}

17.8 其他说明

花时间查看你的系统提供什么。如果没有你想要的工具，就自己编写函数，这是 C 的一部分。如果认为自己能编写一个更好的，那就去做！随着你不断练习并提高自己的编程技术，会从一名新手称为经验丰富的资深程序员。