抽象数据类型之链表ADT接口包

mingcxx

C的基础大致学完了，感觉几个ADT的接口包可能以后会用。所以先存到这里，方便找。
这是一个单项链表，也可以修改Item的结构类型，加入一个指向前一节点的指针，变成双向链表。

1. //list.h -- 简单列表类型的头文件
   
2. 
   
3. #ifndef LIST_H_
   
4. #define LIST_H_
   
5. 
   
6. #include <stdbool.h>                //C99特性，兼容C++
   
7. 
   
8. //特定于程序的声明
   
9. #define TSIZE 45                        //存放影片名的数组大小
   
10. 
    
11. struct film
    
12. {
    
13.         char title[TSIZE];
    
14.         int rating;
    
15. };
    
16. 
    
17. //一般类型定义，根据实际需要修改Item
    
18. typedef struct film Item;
    
19. 
    
20. typedef struct node
    
21. {
    
22.         Item item;
    
23.         struct node * next;
    
24. } Node;
    
25. 
    
26. typedef Node * List;
    
27. 
    
28. //函数原型
    
29. 
    
30. /*操作：初始化一个列表
    
31. 操作前：plist指向一个列表
    
32. 操作后：该列表被初始化为空列表*/
    
33. void InitializeList(List * plist);
    
34. 
    
35. 
    
36. /*操作：确定列表是否为空列表
    
37. 操作前：plist指向一个已初始化的列表
    
38. 操作后：如果该列表为空则返回true，
    
39.                 否则返回false*/
    
40. bool ListIsEmpty(const List * plist);
    
41. 
    
42. 
    
43. /*操作：确定列表是否已满
    
44. 操作前：plist指向一个已初始化的列表
    
45. 操作后：如果该列表已满则返回true，
    
46.                 否则返回false*/
    
47. bool ListIsFull(const List * plist);
    
48. 
    
49. 
    
50. /*操作：确定列表中的项目个数
    
51. 操作前：plist指向一个已初始化的列表
    
52. 操作后：返回该列表的项目个数*/
    
53. unsigned int ListItemCount(const List * plist);
    
54. 
    
55. 
    
56. /*操作：在列表尾部添加一个项目
    
57. 操作前：Item是要被增加到列表的项目
    
58.                 plist指向一个已初始化的列表
    
59. 操作后：如果可能的话，在列表尾部添加
    
60.                 一个新项目，函数返回true，
    
61.                 否则返回false*/
    
62. bool AddItem(Item item, List * plist);
    
63. 
    
64. 
    
65. /*操作：把一个函数作用于列表中的每个项目
    
66. 操作前：plist指向一个已初始化的列表，
    
67.                 pfun指向一个函数，该函数接受
    
68.                 一个Item参数并且无返回值
    
69. 操作后：pfun指向个函数被作用到列表
    
70.                 中的每个项目一次*/
    
71. void Traverse(const List * plist, void(*pfun)(Item item));
    
72. 
    
73. 
    
74. /*操作：释放已分配的内存
    
75. 操作前：plist指向一个已初始化的列表，
    
76. 操作后：为该列表分配的内存被释放，并
    
77.                 且该列表被置为空列表*/
    
78. void EmptyTheList(List * plist);
    
79. 
    
80. 
    
81. #endif // !LIST_H_
    

复制代码

1. //list.c -- 支持链表操作的函数实现
   
2. 
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. #include "list.h"
   
6. 
   
7. /*局部函数原型*/
   
8. static void CopyToNode(Item item, Node * pnode);
   
9. 
   
10. //接口函数
    
11. 
    
12. /*把列表设置为空列表*/
    
13. void InitializeList(List * plist)
    
14. {
    
15.         *plist = NULL;
    
16. }
    
17. 
    
18. /*如果列表为空则返回真，否则返回假*/
    
19. bool ListIsEmpty(const List * plist)
    
20. {
    
21.         if (*plist == NULL)
    
22.         {
    
23.                 return true;
    
24.         }
    
25.         else
    
26.         {
    
27.                 return false;
    
28.         }
    
29. }
    
30. 
    
31. /*如果列表已满则返回真，否则返回假*/
    
32. bool ListIsFull(const List * plist)
    
33. {
    
34.         Node * pnode = (Node *)malloc(sizeof(Node));
    
35.         if (pnode == NULL)
    
36.         {
    
37.                 return true;
    
38.         }
    
39.         else
    
40.         {
    
41.                 free(pnode);
    
42.                 return false;
    
43.         }
    
44. }
    
45. 
    
46. /*返回节点数*/
    
47. unsigned int ListItemCount(const List * plist)
    
48. {
    
49.         Node * pnode = *plist;
    
50.         unsigned int count = 0;
    
51. 
    
52.         while (pnode != NULL)
    
53.         {
    
54.                 ++count;
    
55.                 pnode = pnode->next;
    
56.         }
    
57. 
    
58.         return count;
    
59. }
    
60. 
    
61. /*创建存放项目的节点，并把它添加到
    
62. plist指向的列表的尾部（较慢的方法）*/
    
63. bool AddItem(Item item, List * plist)
    
64. {
    
65.         Node * pnode = (Node *)malloc(sizeof(Node));
    
66.         Node * scan = *plist;
    
67. 
    
68.         if (pnode == NULL)
    
69.         {
    
70.                 return false;
    
71.         }
    
72. 
    
73.         CopyToNode(item, pnode);
    
74.         pnode->next = NULL;
    
75.         if (scan == NULL)
    
76.         {
    
77.                 *plist = pnode;
    
78.         }
    
79.         else
    
80.         {
    
81.                 while (scan->next != NULL)
    
82.                 {
    
83.                         scan = scan->next;
    
84.                 }
    
85.                 scan->next = pnode;
    
86.         }
    
87. 
    
88. 
    
89.         return true;
    
90. }
    
91. 
    
92. /*访问每个节点并对它们分别执行pfun指向的函数*/
    
93. void Traverse(const List * plist, void(*pfun)(Item item))
    
94. {
    
95.         Node * pnode = *plist;
    
96. 
    
97.         while (pnode != NULL)
    
98.         {
    
99.                 (*pfun)(pnode->item);
    
100.                 pnode = pnode->next;
     
101.         }
     
102. }
     
103. 
     
104. 
     
105. /*释放由malloc()分配的内存
     
106. 把列表指针设置为NULL*/
     
107. void EmptyTheList(List * plist)
     
108. {
     
109.         Node * tmp;
     
110. 
     
111.         while (*plist != NULL)
     
112.         {
     
113.                 tmp = (*plist)->next;
     
114.                 free(*plist);
     
115.                 *plist = tmp;
     
116.         }
     
117. }
     
118. 
     
119. 
     
120. //局部函数定义
     
121. 
     
122. //把一个项目复制到一个节点中
     
123. static void CopyToNode(Item item, Node * pnode)
     
124. {
     
125.         pnode->item = item;
     
126. }

复制代码