什么是抽象数据类型？
首先，这一概念是软件开发人员在力求编写的代码健壮、易维护且可以复用的过程中产生的。英文是AbstractData Type。有人将其比作“抽象”的墙壁，“它将接口和实现明确分开，所以用户只看到接口，因此不需要参与实现。”构建者则着力实现ADT接口。ADT成为了双方的契约，这使得代码更容易维护。接口：接口是把公共的方法和属性组合起来以封装特定功能的一个集合。
创建linked list.h头文件
1 #ifndef LIST_H_ 2 #define LIST_H_ 3 #include4 #define TSIZE 45 5 6 typedef struct book{ // 建立包含元素属性的item结构体 7 char title[TSIZE]; 8 int rating; 9 }Item;10 11 typedef struct node { // 链表的节点，包含item各项属性以及一个用来存放下一项地址的指针（链表链接的关键）12 Item item;13 struct node*next;14 }Node;15 typedef Node * List; 16 17 void InitList(List * plist);18 bool ListisEmpty(const List * plist);19 bool ListisFull(const List * plist);20 unsigned int ListItemCount(const List * plist);21 bool AddItem(Item item, List * plist);22 void Traverse(const List * plist, void(*pfun)(Item item));23 void EmptyTheList(List * plist);24 25 #endif
功能函数的定义
1 #include2 #include 3 #include "list.h" 4 static void CopyToNode(Item item, Node * pnode) // 拷贝数据 5 { 6 pnode->item = item; 7 } 8 void InitList(List * plist) // 初始化链表为空 9 {10 *plist = NULL;11 }12 13 bool ListisEmpty(const List * plist) // 检查链表是否为空14 {15 return *plist == NULL ? true : false;16 }17 bool ListisFull(const List * plist) // 检查链表是否已满18 {19 Node * pt;20 pt = (Node *)malloc(sizeof(Node));21 return pt == NULL ? true : false;22 }23 unsigned int ListItemCount(const List * plist)24 {25 unsigned int count = 0;26 Node * pnode = *plist;27 while (pnode != NULL)28 {29 ++count;30 pnode = pnode->next;31 }32 return count;33 }34 bool AddItem(Item item, List * plist) // 在链表结尾添加新的项35 {36 Node * pnew; // 申请一个新的节点37 Node * scan = *plist; 38 pnew = (Node *)malloc(sizeof(Node)); // 给新节点申请空间 39 if (pnew == NULL) return false; // 申请失败，返回false40 CopyToNode(item, pnew); // 把item的内容复制到新节点中41 pnew->next = NULL; // 将新节点的next指针设置为NULL，表示这一节点为当前的末尾项42 if (scan == NULL) // 如果当前是空表，则将新节点设置为表的首项43 *plist = pnew;44 else45 {46 while (scan->next != NULL) //找到当前表中的末尾节点47 scan = scan->next;48 scan->next = pnew; //将新节点的地址保存在末尾节点的next成员里（即给链表添加了一个新的项）49 }50 return true;51 }52 void Traverse(const List * plist, void(*pfun)(Item item)) // 将某函数作用于链表的每一节点53 {54 Node * pnode = *plist; // 将节点指向开头55 while (pnode != NULL) 56 {57 (*pfun)(pnode->item); 58 pnode = pnode->next;59 }60 }61 void EmptyTheList(List * plist) // 清空链表62 {63 Node * psave; // 用来保存当前清除项的下一节点的地址64 while (*plist != NULL)65 {66 psave = (*plist)->next;67 free(*plist);68 *plist = psave;69 }70 }
用户接口：
1 #include2 #include 3 #include 4 #include "list.h" 5 void showmovies(Item item); 6 char * s_gets(char * st, int n); 7 8 int main(void) 9 {10 List book;11 Item temp;12 13 InitList(&book);14 if (ListisFull(&book))15 {16 fprintf(stderr, "No memory available\n");17 exit(EXIT_FAILURE);18 }19 20 puts("Enter first book title:");21 while (s_gets(temp.title, TSIZE) != NULL&&22 temp.title[0] != '\0')23 {24 puts("Enter your rating<0-10>:");25 scanf("%d", &temp.rating);26 while (getchar() != '\n')27 continue;28 if (AddItem(temp, &book) == false)29 {30 fprintf(stderr, "Problem allocating memory\n");31 break;32 }33 if (ListisFull(&book))34 {35 puts("The list is now full.\n");36 break;37 }38 puts("Enter next book title(empty line to stop):");39 }40 41 if (ListisEmpty(&book))42 printf("No data entered.\n");43 else {44 printf("Here is the movies list:\n");45 Traverse(&book, showmovies);46 }47 printf("You entered %d movies.\n", ListItemCount(&book));48 49 EmptyTheList(&book);50 printf("Bye\n");51 52 return 0;53 }54 void showmovies(Item item)55 {56 printf("book: %s Rating:%d\n", item.title, item.rating);57 }58 char * s_gets(char * st, int n)59 {60 char * ret_val;61 char * find;62 ret_val = fgets(st, n, stdin);63 if (ret_val)64 {65 find = strchr(st, '\n');66 if (find)67 *find = '\0';68 else69 while (getchar() != '\n')70 continue;71 }72 return ret_val;73 }