前言

ADT是一些操作的集合。用ADT风格，它侧重于问题的解决思路来表达程序，而不是将代码的细节暴露出来，不是将解决的工具来表达程序。所以，ADT风格的可读性更高，而且是解决问题中最关心的问题。
例如：表，集合，图都可以看作ADT。ADT需要拥有相关属性和操作。
定义ADT需要确定如何存储数据，以及管理该数据的函数
使用ADT应该用一般的语言来描述，不应该用某种特定的计算机语言来表示，且不应该具体的实现细节

定义ADT的步骤

  1. 定义接口（定义相关的函数原型）
  2. 实现接口（实现与函数原型相应的函数）
  3. 使用接口
  • 如果要使用一个简单的链表
    程序组成:
  1. list.h(提供数据类型和接口的原型(general type definitions + function prototypes))
  2. list.c(提供函数代码实现接口)
  3. test.c(应用于特定编程的问题)

示例

list.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/* list.h -- header file for a simple list type */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h>     /* C99 feature         */

/* program-specific declarations */

#define TSIZE      45    /* size of array to hold title  */
struct film
{
    
    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

list.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/* list.c -- functions supporting list operations */
#include <stdio.h>
#include <stdlib.h>
#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 */
}

test.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdlib.h>
#include<stdio.h>
#include "list.h"
int main()
{
    List L;
    Item temp;//创建一个临时的结构
    
    InitializeList(&L);
    if(ListIsFull(&L))
    {
        fprintf(stderr, "No memory available!");
        exit(1);
    }
    for(int i = 0; i < 4; i++)
    {
        temp.rating = i;    //给这个临时结构赋值
        if(AddItem(temp, &L) == false)//将整个项copy进新的项
        {
            fprintf(stderr, "Problem\n");
            break;
        }
        
    }

    while (L != NULL)
    {
        printf("%d ", L->item.rating);
        L = L->next;
    }

    return 0;
}