【ADT】链表的基本C语言实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

什么是抽象数据类型？
首先，这一概念是软件开发人员在力求编写的代码健壮、易维护且可以复用的过程中产生的。
英文是AbstractData Type。有人将其比作“抽象”的墙壁，“它将接口和实现明确分开，所以用户只看到接口，因此不需要参与实现。”构建者则着力实现ADT接口。ADT成为了双方的契约，这使得代码更容易维护。

接口：接口是把公共的方法和属性组合起来以封装特定功能的一个集合。

创建linked list.h头文件

 1 #ifndef LIST_H_
 2 #define LIST_H_
 3 #include <stdbool.h>
 4 #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 #include <stdio.h>
 2 #include <stdlib.h>
 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; // 申请失败，返回false
40     CopyToNode(item, pnew); // 把item的内容复制到新节点中
41     pnew->next = NULL; // 将新节点的next指针设置为NULL，表示这一节点为当前的末尾项
42     if (scan == NULL) // 如果当前是空表，则将新节点设置为表的首项
43         *plist = pnew;
44     else
45     {
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 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 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         else
69             while (getchar() != '\n')
70                 continue;
71     }
72     return ret_val;
73 }