数据结构 一 抽象数据类型ADT

抽象数据类型ADT

计算机科学领域已开发了一种定义新类型的好方法，用 3 个步骤完成从抽象到具体的过程。

1. 提供类型属性和相关操作的抽象描述。这些描述既不能依赖特定的实现，也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型 （ADT）。
2. 开发一个实现 ADT 的编程接口。也就是说，指明如何储存数据和执行所需操作的函数。例如在 C中，可以提供结构定义和操控该结构的函数原型。这些作用于用户定义类型的函数相当于作用于 C 基本类型的内置运算符。需要使用该新类型的程序员可以使用这个接口进行编程。
3. 编写代码实现接口。这一步至关重要，但是使用该新类型的程序员无需了解具体的实现细节。

建立ADT的步骤实践 以链表为例

建立抽象

链表应该实现以下功能。

1. 初始化一个空链表
2. 再链表结尾添加一个新的项
3. 判断链表是否为空
4. 判断链表是否已经满了
5. 确定链表中的元素个数
6. 访问链表中的项 例如数组的 [] 运算符和指针的 -> 运算符
7. 在链表中的任意位置添加一个项
8. 移除链表中的任意一项
9. 更替链表中的某一项
10. 在链表中搜索一个项 根据某个数据找到对应的项比如最大值

建立接口

数据隐藏是一种从编程的更高层次隐藏数据表示细节的艺术

#define TSIZE 100
struct film
{
    //电影标题
    char title[TSIZE];
    //电影评分
    int rating;
};
//定义 item 为链表中的项的类型 这样只要使用item就可以方便的确定链表的数据类型了，也很容易改变。
typedef struct film Item;

//现在必须确定如何在链表中存储这种数据类型 item
struct node
{
    Item item;
    struct node *next;
};
//定义一个结点数据类型
typedef struct node Node;
//定义一个抽象的链表数据类型
typedef struct node *List;
/*我们也可以这样定义，为链表添加一些信息
typedef struct list
{
    Node* head;
    Node* tail;
    int size;
    //更多的信息
}List;
*/

//函数原型

//操作： 初始化一个链表
//条件： plist指向一个链表
//结果： 链表初始化为空
void InitializeList(List *plist);

//操作： 判断链表是否为空
//条件： plist指向一个链表
//结果： 如果为空返回true,反之返回false
//说明： const限定是为了防止恶意修改链表
bool Empty(const List *plist);

//操作： 判断链表是否为满
//条件： plist指向一个链表
//结果： 如果为满返回true,反之返回false
//说明： const限定是为了防止恶意修改链表
bool Full(const List *plist);

//操作： 确定链表中的项数
//条件： plist指向一个链表
//结果： 返回链表中的项数
//说明： const限定是为了防止恶意修改链表
unsigned int Count(const List *plist);

//操作： 在链表的结尾添加一项
//条件： plist指向一个链表
//结果： 若添加成功返回true,失败则返回false
bool AddItem(Item item, List *plist);

//操作： 遍历链表，将函数作用于链表中的每一项
//条件： plist指向一个链表，pfun是一个无返回值的函数
//结果： 将函数作用于链表中的每一项
void Traverse(List *plist, void (*pfun)(Item item));

//操作： 清空链表并释放空间
//条件： plist指向一个链表
//结果： 若添加成功返回true,失败则返回false
bool Clear(List *plist);

实现接口

//函数实现

//操作： 初始化一个链表
//条件： plist指向一个链表
//结果： 链表初始化为空
void InitializeList(List *plist)
{
    *plist = NULL;
}

//操作： 判断链表是否为空
//条件： plist指向一个链表
//结果： 如果为空返回true,反之返回false
//说明： const限定是为了防止恶意修改链表
bool Empty(const List *plist)
{
    return (*plist == NULL);
}

//操作： 判断链表是否为满
//条件： plist指向一个链表
//结果： 如果为满返回true,反之返回false
//说明： const限定是为了防止恶意修改链表
bool Full(const List *plist)
{
    Node *pt;
    bool full;
    pt = (Node *)malloc(sizeof(Node));
    if (pt == NULL)
        full = true;
    else
        full = false;
    free(pt);
    return full;
}

//操作： 确定链表中的项数
//条件： plist指向一个链表
//结果： 返回链表中的项数
//说明： const限定是为了防止恶意修改链表
unsigned int Count(const List *plist)
{
    unsigned int count = 0;
    Node *pnode = *plist;
    while (pnode != NULL)
    {
        count++;
        pnode = pnode->next;
    }
    return count;
}

//操作： 在链表的结尾添加一项
//条件： plist指向一个链表
//结果： 若添加成功返回true,失败则返回false
bool AddItem(Item item, List *plist)
{
    Node *pnew;
    Node *scan = *plist;
    pnew = (Node *)malloc(sizeof(Node));
    if (pnew == NULL)
        return false;
    pnew->item = item;
    pnew->next = NULL;
    if (*plist == NULL)
        *plist = pnew;
    else
    {
        scan = *plist;
        while (scan->next != NULL)
        {
            scan = scan->next;
        }
        scan->next = pnew;
    }
    return true;
}

//操作： 遍历链表，将函数作用于链表中的每一项
//条件： plist指向一个链表，pfun是一个无返回值的函数
//结果： 将函数作用于链表中的每一项
void Traverse(List *plist, void (*pfun)(Item item))
{
    Node *scan = *plist;
    while (scan != NULL)
    {
        pfun(scan->item);
        scan = scan->next;
    }
}

//操作： 清空链表并释放空间
//条件： plist指向一个链表
//结果： 若添加成功返回true,失败则返回false
void Clear(List *plist)
{
    Node *scan = *plist;
    while (*plist != NULL)
    {
        *plist = scan->next;
        free(scan);
        scan = *plist;
    }
}

使用接口

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void pfun(Item Item)
{
    printf("%s %d\n", Item.title, Item.rating);
}

int main()
{
    List mylist;
    printf("初始化链表\n");
    InitializeList(&mylist);
    Item myitem;
    strcpy(myitem.title, "cuiwenyaono.1");
    myitem.rating = 100;

    printf("当前链表内的元素数量为%d\n", Count(&mylist));
    printf("添加项目\n");
    AddItem(myitem, &mylist);
    printf("当前链表内的元素数量为%d\n", Count(&mylist));
    if (Empty(&mylist))
        printf("当前链表为空\n");
    else
        printf("当前链表不空\n");
    if (Full(&mylist))
        printf("当前链表满了\n");
    else
        printf("当前链表不满\n");
    printf("打印链表\n");
    Traverse(&mylist, (*pfun));
    Clear(&mylist);
    if (Empty(&mylist))
        printf("当前链表为空\n");
    else
        printf("当前链表不空\n");
}