在编程时，应该根据编程问题匹配合适的数据类型。例如，用int类型代表你有多少双鞋，用float或double类型代表每双鞋的价格。在前面的电影示例中，数据构成了链表，每个链表项由电影名（C字符串）和评级（一个int类型值）。C中没有与之匹配的基本类型，所以我们定义了一个结构代表单独的项，然后设计了一些方法把一系列结构构成一个链表。本质上，我们使用C语言的功能设计了一种符合程序要求的新数据类型。但是，我们的做法并不系统。现在，我们用更系统的方法来定义数据类型。 什么是类型？类型特指两类信息：属性和操作。例如，int类型的属性是它代表一个整数值，因此它共享整数的属性。允许对int类型进行的算术操作有：改变int类型值的符号、两个int类型值相加、相减、相乘、相除、求模。当声明一个int类型的变量时，就表明了只能对该变量进行这些操作。
注意
整数属性C的int类型背后是一个更抽象的整数概念。数学家已经用正式的抽象方式定义了整数的属性。例如，假设N和M是整数，那么N+M=M+N；假设S、Q也是整数，如果N+M=S，而且N+Q=S，那么M=Q。可以认为数学家提供了整数的抽象概念，而C则实现了这一抽象概念。注意，实现整数的算术运算是表示整数必不可少的部分。如果只是存储值，并未在算术表达式中使用，int类型就没那么有用了。还要注意的是，C并未很好地实现整数。例如，整数是无穷大的数，但是2字节的int类型只能表示65536个整数。因此，不要混淆抽象概念和具体的实现。
假设要定义一个新的数据类型。首先，必须提供存储数据的方法，例如设计一个结构。其次，必须提供操控数据的方法。例如，考虑films2.c程序（程序清单17.2）。该程序用链接的结构来存储信息，而且通过代码实现了如何添加和显示信息。尽管如此，该程序并未清楚地表明正在创建一个新类型。我们应该怎么做？ 计算机科学领域已开发了一种定义新类型的好方法，用3个步骤完成从抽象到具体的过程。 1．提供类型属性和相关操作的抽象描述。这些描述既不能依赖特定的实现，也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型（ADT）。 2．开发一个实现ADT的编程接口。也就是说，指明如何存储数据和执行所需操作的函数。例如在C中，可以提供结构定义和操控该结构的函数原型。这些 作用于用户定义类型的函数相当于作用于C基本类型的内置运算符。需要使用该新类型的程序员可以使用这个接口进行编程。 3．编写代码实现接口。这一步至关重要，但是使用该新类型的程序员无需了解具体的实现细节。我们再次以前面的电影项目为例来熟悉这个过程，并用新方法重新完成这个示例。
从根本上看，电影项目所需的是一个项链表。每一项包含电影名和评级。你所需的操作是把新项添加到链表的末尾和显示链表中的内容。我们把需要处理这些需求的抽象类型叫作链表。链表具有哪些属性？首先，链表应该能存储一系列的项。也就是说，链表能存储多个项，而且这些项以某种方式排列，这样才能描述链表的第1项、第2项或最后一项。其次，链表类型应该提供一些操作，如在链表中添加新项。下面是链表的一些有用的操作：
对该电影项目而言，暂时不需要其他操作。但是一般的链表还应包含以下操作：
非正式但抽象的链表定义是：链表是一个能存储一系列项且可以对其进行所需操作的数据对象。该定义既未说明链表中可以存储什么项，也未指定是用数组、结构还是其他数据形式来存储项，而且并未规定用什么方法来实现操作（如，查找链表中元素的个数）。这些细节都留给实现完成。 为了让示例尽量简单，我们采用一种简化的链表作为抽象数据类型。它只包含电影项目中的所需属性。该类型总结如下：
下一步是为简单链表ADT开发一个C接口。
这个简单链表的接口有两个部分。第1部分是描述如何表示数据，第2部分是描述实现ADT操作的函数。例如，要设计在链表中添加项的函数和报告链表中项数的函数。接口设计应尽量与ADT的描述保持一致。因此，应该用某种通用的Item类型而不是一些特殊类型，如int或struct film。可以用C的typedef功能来定义所需的Item类型：
#define TSIZE 45 /* size of array to hold title */
struct film
{
char title[TSIZE];
int rating;
};
typedef struct film Item;然后，就可以在定义的其余部分使用Item类型。如果以后需要其他数据形式的链表，可以重新定义Item类型，不必更改其余的接口定义。 定义了Item之后，现在必须确定如何存储这种类型的项。实际上这一步属于实现步骤，但是现在决定好可以让示例更简单些。在films2.c程序中用链式结构处理得很好，所以，我们在这里也采用相同的方法：
typedef struct node
{
Item item;
struct node * next;
} Node;
typedef Node * List;在链表的实现中，每一个链节叫作节点（node）。每个节点包含形成链表内容的信息和指向下一个节点的指针。为了强调这个术语，我们把node作为节点结构的标记名，并使用typedef把Node作为struct node结构的类型名。最后，为了管理链表，还需要一个指向链表开始处的指针，我们使用typedef把List作为该类型的指针名。因此，下面的声明：
List movies;创建了该链表所需类型的指针movies。这是否是定义List类型的唯一方法？不是。例如，还可以添加一个变量记录项数：
typedef struct list
{
Node * head; /* pointer to head of list */
int size; /* number of entries in list */
} List; /* alternative definition of list */
可以像稍后的程序示例中那样，添加第2个指针存储链表的末尾。现在，我们还是使用List类型的第1种定义。这里要着重理解下面的声明创建了一个链表，而不是一个指向节点的指针或一个结构：
List movies;movies代表的确切数据应该是接口层次不可见的实现细节。例如，程序启动后应把头指针初始化为NULL。但是，不要使用下面这样的代码：
movies = NULL;为什么？因为稍后你会发现List类型的结构实现更好，所以应这样初始化：
movies.next = NULL;
movies.size = 0;使用List的人都不用担心这些细节，只要能使用下面的代码就行：
InitializeList(movies);使用该类型的程序员只需知道用InitializeList()函数来初始化链表，不必了解List类型变量的实现细节。这是数据隐藏的一个示例，数据隐藏是一种从编程的更高层次隐藏数据表示细节的艺术。 为了指导用户使用，可以在函数原型前面提供以下注释：
/* operation: initialize a list */
/* preconditions: plist points to a list */
/* postconditions: the list is initialized to empty */
void InitializeList(List * plist);这里要注意3点。第1，注释中的“前提条件”（precondition）是调用该函数前应具备的条件。例如，需要一个待初始化的链表。第2，注释中的“后置条件”（postcondition）是执行完该函数后的情况。第3，该函数的参数是一个指向链表的指针，而不是一个链表。所以应该这样调用该函数：
InitializeList(&movies);由于按值传递参数，所以该函数只能通过指向该变量的指针才能更改主调程序传入的变量。这里，由于语言的限制使得接口和抽象描述略有区别。 C语言把所有类型和函数的信息集合成一个软件包的方法是：把类型定义和函数原型（包括前提条件和后置条件注释）放在一个头文件中。该文件应该提供程序员使用该类型所需的所有信息。程序list.h 给出了一个简单链表类型的头文件。该程序定义了一个特定的结构作为Item类型，然后根据Item定义了Node，再根据Node定义了List。然后，把表示链表操作的函数设计为接受Item类型和List类型的参数。如果函数要修改一个参数，那么该参数的类型应是指向相应类型的指针，而不是该类型。在头文件中，把组成函数名的每个单词的首字母大写，以这种方式表明这些函数是接口包的一部分。另外，该文件使用的#ifndef指令，防止多次包含一个头文件。如果编译器不支持C99的bool类型，可以用下面的代码：
#include /* C99 feature */ 替换下面的头文件：
enum bool {false, true}; /* define bool as type, false, true as values */The list.h Interface Header File
/* list.h -- header file for a simple list type */
#ifndef LIST_H_
#define LIST_H_
#include /* C99 feature */
/* program-specific declarations */
#define TSIZE 45 /* size of array to hold title */
struct film
{
char title[TSIZE];
int rating;
};
/* general type definitions */
typedef struct film Item;
typedef struct node
{
Item item;
struct node * next;
} Node;
typedef Node * List;
/* function prototypes */
/* operation: initialize a list */
/* preconditions: plist points to a list */
/* postconditions: the list is initialized to empty */
void InitializeList(List * plist);
/* operation: determine if list is empty */
/* plist points to an initialized list */
/* postconditions: function returns True if list is empty */
/* and returns False otherwise */
bool ListIsEmpty(const List *plist);
/* operation: determine if list is full */
/* plist points to an initialized list */
/* postconditions: function returns True if list is full */
/* and returns False otherwise */
bool ListIsFull(const List *plist);
/* operation: determine number of items in list */
/* plist points to an initialized list */
/* postconditions: function returns number of items in list */
unsigned int ListItemCount(const List *plist);
/* operation: add item to end of list */
/* preconditions: item is an item to be added to list */
/* plist points to an initialized list */
/* postconditions: if possible, function adds item to end */
/* of list and returns True; otherwise the */
/* function returns False */
bool AddItem(Item item, List * plist);
/* operation: apply a function to each item in list */
/* plist points to an initialized list */
/* pfun points to a function that takes an */
/* Item argument and has no return value */
/* postcondition: the function pointed to by pfun is */
/* executed once for each item in the list */
void Traverse (const List *plist, void (* pfun)(Item item) );
/* operation: free allocated memory, if any */
/* plist points to an initialized list */
/* postconditions: any memory allocated for the list is freed */
/* and the list is set to empty */
void EmptyTheList(List * plist);
#endif 只有InitializeList()、AddItem()和EmptyTheList()函数要修改链表，因此从技术角度看，这些函数需要一个指针参数。然而，如果某些函数接受List类型的变量作为参数，而其他函数却接受List类型的地址作为参数，用户会很困惑。因此，为了减轻用户的负担，所有的函数均使用指针参数。头文件中的一个函数原型比其他原型复杂：
* operation: apply a function to each item in list * * plist points to an initialized list * * pfun points to a function that takes an * * Item argument and has no return value * * postcondition: the function pointed to by pfun is * * executed once for each item in the list * void Traverse (const List plist, void ( pfun)(Item item) );
参数pfun是一个指向函数的指针，它指向的函数接受item值且无返回值。第14章中介绍过，可以把函数指针作为参数传递给另一个函数，然后该函数就可以使用这个被指针指向的函数。例如，该例中可以让pfun指向显示链表项的函数。然后把Traverse()函数把该函数作用于链表中的每一项，显示链表中的内容。
我们的目标是，使用这个接口编写程序，但是不必知道具体的实现细节（如，不知道函数的实现细节）。在编写具体函数之前，我们先编写电影程序的一个新版本。由于接口要使用List和Item类型，所以该程序也应使用这些类型。下面是编写该程序的一个伪代码方案。
Create a List variable. Create an Item variable. Initialize the list to empty. While the list isn't full and while there's more input: Read the input into the Item variable. Add the item to the end of the list. Visit each item in the list and display it.
程序films3.c中的程序按照以上伪代码来编写，其中还加入了一些错误检查。注意该程序利用了list.h（程序films3.c）中描述的接口。另外，还需注意，链表中含有showmovies()函数的代码，它与Traverse()所要求的原型一致。因此，程序可以把指针showmovies传递给Traverse()，这样Traverse()可以把showmovies()函数应用于链表中的每一项（回忆一下，函数名是指向该函数的指针）。
Listing 17.4 The films3.c Program
/* films3.c -- using an ADT-style linked list */
/* compile with list.c */
#include
#include /* prototype for exit() */
#include "list.h" /* defines List, Item */
void showmovies(Item item);
char * s_gets(char * st, int n);
int main(void)
{
List movies;
Item temp;
/* initialize */
InitializeList(&movies);
if (ListIsFull(&movies))
{
fprintf(stderr,"No memory available! Bye!n");
exit(1);
}
/* gather and store */
puts("Enter first movie title:");
while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '0')
{
puts("Enter your rating <0-10>:");
scanf("%d", &temp.rating);
while(getchar() != 'n')
continue;
if (AddItem(temp, &movies)==false)
{
fprintf(stderr,"Problem allocating memoryn");
break;
}
if (ListIsFull(&movies))
{
puts("The list is now full.");
break;
}
puts("Enter next movie title (empty line to stop):");
}
/* display */
if (ListIsEmpty(&movies))
printf("No data entered. ");
else
{
printf ("Here is the movie list:n");
Traverse(&movies, showmovies);
}
printf("You entered %d movies.n", ListItemCount(&movies));
/* clean up */
EmptyTheList(&movies);
printf("Bye!n");
return 0;
}
void showmovies(Item item)
{
printf("Movie: %s Rating: %dn", 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'); // look for newline
if (find) // if the address is not NULL,
*find = '0'; // place a null character there
else
while (getchar() != 'n')
continue; // dispose of rest of line
}
return ret_val;
} 当然，我们还是必须实现List接口。C方法是把函数定义统一放在list.c文件中。然后，整个程序由list.h（定义数据结构和提供用户接口的原型）、list.c（提供函数代码实现接口）和films3.c（把链表接口应用于特定编程问题的源代码文件）组成。程序清单17.5演示了list.c的一种实现。要运行该程序，必须把films3.c和list.c一起编译和链接（可以复习一下第9章关于编译多文件程序的内容）。list.h、list.c和films3.c组成了整个程。
Figure 17.5 The three parts of a program package.
The list.c Implementation File
/* list.c -- functions supporting list operations */
#include
#include
#include "list.h"
/* local function prototype */
static void CopyToNode(Item item, Node * pnode);
/* interface functions */
/* set the list to empty */
void InitializeList(List * plist)
{
* plist = NULL;
}
/* returns true if list is empty */
bool ListIsEmpty(const List * plist)
{
if (*plist == NULL)
return true;
else
return false;
}
/* returns true if list is full */
bool ListIsFull(const List * plist)
{
Node * pt;
bool full;
pt = (Node *) malloc(sizeof(Node));
if (pt == NULL)
full = true;
else
full = false;
free(pt);
return full;
}
/* returns number of nodes */
unsigned int ListItemCount(const List * plist)
{
unsigned int count = 0;
Node * pnode = *plist; /* set to start of list */
while (pnode != NULL)
{
++count;
pnode = pnode->next; /* set to next node */
}
return count;
}
/* creates node to hold item and adds it to the end of */
/* the list pointed to by plist (slow implementation) */
bool AddItem(Item item, List * plist)
{
Node * pnew;
Node * scan = *plist;
pnew = (Node *) malloc(sizeof(Node));
if (pnew == NULL)
return false; /* quit function on failure */
CopyToNode(item, pnew);
pnew->next = NULL;
if (scan == NULL) /* empty list, so place */
*plist = pnew; /* pnew at head of list */
else
{
while (scan->next != NULL)
scan = scan->next; /* find end of list */
scan->next = pnew; /* add pnew to end */
}
return true;
}
/* visit each node and execute function pointed to by pfun */
void Traverse (const List * plist, void (* pfun)(Item item) )
{
Node * pnode = *plist; /* set to start of list */
while (pnode != NULL)
{
(*pfun)(pnode->item); /* apply function to item */
pnode = pnode->next; /* advance to next item */
}
}
/* free memory allocated by malloc() */
/* set list pointer to NULL */
void EmptyTheList(List * plist)
{
Node * psave;
while (*plist != NULL)
{
psave = (*plist)->next; /* save address of next node */
free(*plist); /* free current node */
*plist = psave; /* advance to next node */
}
}
/* local function definition */
/* copies an item into a node */
static void CopyToNode(Item item, Node * pnode)
{
pnode->item = item; /* structure copy */
}
list.c文件有几个需要注意的地方。首先，该文件演示了什么情况下使用内部链接函数。如第12章所述，具有内部链接的函数只能在其声明所在的文件夹可见。在实现接口时，有时编写一个辅助函数（不作为正式接口的一部分）很方便。例如，使用CopyToNode()函数把一个Item类型的值拷贝到Item类型的变量中。由于该函数是实现的一部分，但不是接口的一部分，所以我们使用static存储类别说明符把它隐藏在list.c文件中。接下来，讨论其他函数。 InitializeList()函数将链表初始化为空。在我们的实现中，这意味着把List类型的变量设置为NULL。前面提到过，这要求把指向List类型变量的指针传递给该函数。
InitializeList()函数将链表初始化为空。在我们的实现中，这意味着把List类型的变量设置为NULL。前面提到过，这要求把指向List类型变量的指针传递给该函数。ListIsEmpty()函数很简单，但是它的前提条件是，当链表为空时，链表变量被设置为NULL。因此，在首次调用ListIsEmpty()函数之前初始化链表非常重要。另外，如果要扩展接口添加删除项的功能，那么当最后一个项被删除时，应该确保该删除函数重置链表为空。对链表而言，链表的大小取决于可用内存量。ListIsFull()函数尝试为新项分配空间。如果分配失败，说明链表已满；如果分配成功，则必须释放刚才分配的内存供真正的项所用。 ListItemCount()函数使用常用的链表算法遍历链表，同时统计链表中的项：
unsigned int ListItemCount(const List * plist)
{
unsigned int count = 0;
Node * pnode = *plist; /* set to start of list */
while (pnode != NULL)
{
++count;
pnode = pnode->next; /* set to next node */
}
return count;
}AddItem()函数是这些函数中最复杂的：
bool AddItem(Item item, List * plist)
{
Node * pnew;
Node * scan = *plist;
pnew = (Node *) malloc(sizeof(Node));
if (pnew == NULL)
return false; /* quit function on failure */
CopyToNode(item, pnew);
pnew->next = NULL;
if (scan == NULL) /* empty list, so place */
*plist = pnew; /* pnew at head of list */
else
{
while (scan->next != NULL)
scan = scan->next; /* find end of list */
scan->next = pnew; /* add pnew to end */
}
return true;
}AddItem()函数首先为新节点分配空间。如果分配成功，该函数使用CopyToNode()把项拷贝到新节点中。然后把该节点的next成员设置为NULL。这表明该节点是链表中的最后一个节点。最后，完成创建节点并为其成员赋正确的值之后，该函数把该节点添加到链表的末尾。如果该项是添加到链表的第1个项，需要把头指针设置为指向第1项（记住，头指针的地址是传递给AddItem()函数的第2个参数，所以*plist就是头指针的值）。否则，代码继续在链表中前进，直到发现被设置为NULL的next成员。此时，该节点就是当前的最后一个节点，所以，函数重置它的next成员指向新节点。 要养成良好的编程习惯，给链表添加项之前应调用ListIsFull()函数。但是，用户可能并未这样做，所以在AddItem()函数内部检查malloc()是否分配成功。而且，用户还可能在调用ListIsFull()和调用AddItem()函数之间做其他事情分配了内存，所以最好还是检查malloc()是否分配成功。 Traverse()函数与ListItemCount()函数类似，不过它还把一个指针函数作用于链表中的每一项。
void Traverse (const List * plist, void (* pfun)(Item item) )
{
Node * pnode = *plist; /* set to start of list */
while (pnode != NULL)
{
(*pfun)(pnode->item); /* apply function to item */
pnode = pnode->next; /* advance to next item */
}
}pnode->item代表存储在节点中的数据，pnode->next标识链表中的下一个节点。如下函数调用：
Traverse(movies, showmovies);把showmovies()函数应用于链表中的每一项。最后，EmptyTheList()函数释放了之前malloc()分配的内存：
void EmptyTheList(List * plist)
{
Node * psave;
while (*plist != NULL)
{
psave = (*plist)->next; /* save address of next node */
free(*plist); /* free current node */
*plist = psave; /* advance to next node */
}
}该函数的实现通过把List类型的变量设置为NULL来表明一个空链表。因此，要把List类型变量的地址传递给该函数，以便函数重置。由于List已经是一个指针，所以plist是一个指向指针的指针。因此，在上面的代码中，*plist是指向Node的指针。当到达链表末尾时，*plist为NULL，表明原始的实际参数现在被设置为NULL。 代码中要保存下一节点的地址，因为原则上调用了free()会使当前节点（即*plist指向的节点）的内容不可用。
提示 const的限制 多个处理链表的函数都把const List * plist作为形参，表明这些函数不会更改链表。这里，const确实提供了一些保护。它防止了*plist（即plist所指向的量）被修改。在该程序中，plist指向movies，所以const防止了这些函数修改movies。因此，在ListItemCount()中，不允许有类似下面的代码：
*plist = (*plist)->next; // not allowed if *plist is const因为改变*plist就改变了movies，将导致程序无法跟踪数据。然而，*plist和movies都被看作是const并不意味着*plist或movies指向的数据是const。例如，可以编写下面的代码：
(*plist)->item.rating = 3; // allowed even if *plist is const因为上面的代码并未改变*plist，它改变的是*plist指向的数据。由此可见，不要指望const能捕获到意外修改数据的程序错误。
现在花点时间来评估ADT方法做了什么。首先，比较程序清单17.2和程序清单17.4。这两个程序都使用相同的内存分配方法（动态分配链接的结构）解决电影链表的问题，但是程序清单17.2暴露了所有的编程细节，把malloc()和prev->next这样的代码都公之于众。而程序清单17.4隐藏了这些细节，并用与任务直接相关的方式表达程序。也就是说，该程序讨论的是创建链表和向链表中添加项，而不是调用内存函数或重置指针。简而言之，程序清单17.4是根据待解决的问题来表达程序，而不是根据解决问题所需的具体工具来表达程序。ADT版本可读性更高，而且针对的是最终的用户所关心的问题。 其次，list.h和list.c文件一起组成了可复用的资源。如果需要另一个简单的链表，也可以使用这些文件。假设你需要存储亲戚的一些信息：姓名、关系、地址和电话号码，那么先要在list.h文件中重新定义Item类型：
typedef struct itemtag
{
char fname[14];
char lname [24];
char relationship[36];
char address [60];
char phonenum[20];
} Item;然后……只需要做这些就行了。因为所有处理简单链表的函数都与Item类型有关。根据不同的情况，有时还要重新定义CopyToNode()函数。例如，当项是一个数组时，就不能通过赋值来拷贝。 另一个要点是，用户接口是根据抽象链表操作定义的，不是根据某些特定的数据表示和算法来定义。这样，不用重写最后的程序就能随意修改实现。例如，当前使用的AddItem()函数效率不高，因为它总是从链表第1个项开始，然后搜索至链表末尾。可以通过保存链表结尾处的地址来解决这个问题。例如，可以这样重新定义List类型：
typedef struct list
{
Node * head; /* points to head of list */
Node * end; /* points to end of list */
} List;当然，还要根据新的定义重写处理链表的函数，但是不用修改程序清单17.4中的内容。对大型编程项目而言，这种把实现和最终接口隔离的做法相当有用。这称为数据隐藏，因为对终端用户隐藏了数据表示的细节。 注意，这种特殊的ADT甚至不要求以链表的方式实现简单列表。下面是另一种方法：
#define MAXSIZE 100
typedef struct list
{
Item entries[MAXSIZE]; /* array of items */
int items; /* number of items in list */
} List;这样做也需要重写list.c文件，但是使用list的程序不用修改。 最后，考虑这种方法给程序开发过程带来了哪些好处。如果程序运行出现问题，可以把问题定位到具体的函数上。如果想用更好的方法来完成某个任务（如，添加项），只需重写相应的函数即可。如果需要新功能，可以添加一个新的函数。如果觉得数组或双向链表更好，可以重写实现的代码，不用修改使用实现的程序。
页面更新：2024-05-04
本站资料均由网友自行发布提供，仅用于学习交流。如有版权问题，请与我联系，QQ：4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号
