抽象数据类型(ADT)---链表

发表于 分类于 阅读次数：

抽象数据类型（Abstract Data Type，ADT）是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是描述数据结构的一种理论工具，其目的是使人们能够独立于程序的实现细节来理解数据结构的特性。抽象数据类型的定义取决于它的一组逻辑特性，而与计算机内部如何表示无关。

简介

  类型由什么组成？一个类型指定两类信息：一个属性集和一个操作集。比如，int类型的属性表示它是一个整数值，因为它是一个整数值，因此它拥有整数的属性。它允许的算数操作是改变一个int树的符号，两数相加减，两数相乘除等。又比如说，定义一个“学生”类型，姓名，性别，成绩都是它的属性集，而添加学生，删除学生就是操作集。
  那么如何创建一个新的类型呢？分3个步骤从抽象到具体的过程：

  1. 为类型的属性和可对类型的操作提供一个抽象的描述。
  2. 开发一个实现该ADT的编程接口。即说明如何存储数据并描述用于执行所需操作的函数集合。
  3. 编写代码来实现这个接口。

接下来以ADT的风格实现链表

链表

  链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

  为了使例子简单，用列表的形式描述抽象数据类型

类型名称 简单列表
类型属性： 可保存一个项目序列
类型操作： 把列表初始化为空列表
确定列表是否为空
确定列表是否已满
确定列表中项目的个数
向列表末尾添加项目
遍历列表中的每个项目
清空列表

定义接口

  简单列表的接口有两部分。第一部分是描述数据如何表示，第二部分描述实现ADT操作的函数。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
/* list.h 简单列表类型的头文件 */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h>   /* C99特性*/

/* 特定于程序的声明 */
#define TSIZE 45 /* 存放片名的数组大小 */
struct film
{
    char title[TSIZE];
    int rating;
};

/* 一般类型定义 */
typedef struct film Item;

typedef struct node
{
    Item item;     // 项目
    struct node * next;   // 存放下一个节点的地址
} Node;

typedef Node * List;   // List 就是 Node *

/* 函数原型*/
/* 操作： 初始化一个列表 */
/* 操作前： plist指向一个列表 */
/* 操作后： 该列表被初始化为一个空表 */
void InitializeList(List * plist); 

/* 操作： 确定列表是否为空 */
/* 操作前： plist指向一个已初始化列表 */
/* 操作后： 列表为空返回true， 反之，false */
bool ListIsEmpty(List * plist);

/* 操作： 确定列表是否已满 */
/* 操作前： plist指向一个已初始化列表 */
/* 操作后： 列表已满返回true， 反之，false */
bool ListIsFull(List * plist);

/* 操作： 确定列表中的项目个数 */
/* 操作前： plist指向一个已初始化列表 */
/* 操作后： 返回该列表中的项目个数 */
unsigned int ListItemCount(const List * plist);

/* 操作： 在列表尾部添加一个项目 */
/* 操作前： item是一个要被添加的项目，plist指向一个已初始化列表 */
/* 操作后： 操作成功返回true， 失败返回false */
bool AddItem(Item item, List * plist);

/* 操作： 把一个函数作用于列表的每个项目 */
/* 操作前： plist指向一个已初始化列表，pfun指向一个函数，该函数接收一个Item项目 */
/* 操作后： 指向的函数作用于每个项目 */
void Traverse(const List * plist, void (* pfun)(Item item));


/* 操作： 释放已分配的内存（如果有）*/
/* 操作前： plist指向一个已初始化列表 */
/* 操作后： 内存释放，列表被置为空表 */
void EmptyTheList(List * plist);

#endif

实现接口

需要实现的函数：

初始化

InitializeList()将列表初始化为空列表。只需将传入的List指针置为NULL;

判断链表是否为空

ListIsEmpty()函数实现简单，只要判断指针是否为NULL，正确返回true，反之false;

判断链表是否已满

ListIsFull()可以通过malloc()函数尝试给一个新项目分配内存，如果分配失败，说明链表已满。

确定列表中的项目个数

ListItemCount()函数使用常用的链表算法遍历链表，同时统计个数。
通过while循环，只要节点为空，说明遍历到链表末尾

1
2
3
4
5
6
7
8
9
10
11
12
unsigned int ListItemCount(const List * plist)
{
    unsigned int count = 0;
    Node * pnode = *plist; // 设置列表的开始处

    while(pnode != NULL)
    {
        ++count;
        pnode = pnode->next;  /* 设置下一个节点 */
    }
    return count;
}

在列表尾部添加一个项目

AddItem()函数是在这些函数中，做的最多的

  1. 尝试为新节点分配空间;
  2. 通过CopyToNode()把项目复制到新的节点，并把新节点的next置为null;
  3. 如果列表为空，新节点作为头节点
  4. 列表不为空，通过while循环，找到链表结尾，将新节点添加到结尾

CopyToNode()把项目复制到新的节点的项目中，它是实现的一部分但不是接口的一部分，通过tatic存储类限定词将其隐藏在listc文件中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool AddItem(Item item, List * plist)
{
    Node * pnew;
    Node * scan = *plist;

    pnew = (Node *)malloc(sizeof(Node));
    if(pnew == NULL)
        return false;
    
    CopyToNode(item, pnew);   // 把传入的item结构赋值到新节点的item中
    pnew->next = NULL;  // 指向空指针
    if(scan == NULL)
        *plist = pnew;
    else
    {
        while(scan->next != NULL)
            scan = scan->next;  // 找到列表结尾
        scan->next = pnew;    // 新节点加到结尾
    }
    return true;
}

项目操作

Traverse()把一个函数作用于列表的每个项目

1
2
3
4
5
6
7
8
9
void Traverse(const List * plist, void (* pfun)(Item item))
{
    Node * pnode = * plist;
    while(pnode != NULL)    // 遍历项目
    {
        (*pfun)(pnode->item);    // 调用函数
        pnode = pnode->next;
    }
}

清空列表

EmptyTheList()是清空列表，记得在释放节点前，保存以一个节点的地址

完整代码

实现的代码如下：

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
/* list.c*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list.h" 

// 局部函数原型
static void CopyToNode(Item item, Node * pnode);

void InitializeList(List * plist)
{
    * plist = NULL;
}

bool ListIsEmpty(List * plist)
{
    if (* plist == NULL)
        return true;
    else
        return false;
}

bool ListIsFull(List * plist)
{
    Node * pt;
    bool full;

    pt = (Node *)malloc(sizeof(Node));
    if (pt == NULL)   // 分配失败，返回false
        full = true;
    else
        full = false;
    free(pt);    // 将分配的内存释放
    return full;
}

unsigned int ListItemCount(const List * plist)
{
    unsigned int count = 0;
    Node * pnode = *plist; // 设置列表的开始处

    while(pnode != NULL)
    {
        ++count;
        pnode = pnode->next;  /* 设置下一个节点 */
    }
    return count;
}

bool AddItem(Item item, List * plist)
{
    Node * pnew;
    Node * scan = *plist;

    pnew = (Node *)malloc(sizeof(Node));
    if(pnew == NULL)
        return false;
    
    CopyToNode(item, pnew);   // 把传入的item结构赋值到新节点的item中
    pnew->next = NULL;  // 指向空指针
    if(scan == NULL)
        *plist = pnew;
    else
    {
        while(scan->next != NULL)
            scan = scan->next;  // 找到列表结尾
        scan->next = pnew;    // 新节点加到结尾
    }
    return true;
}

void Traverse(const List * plist, void (* pfun)(Item item))
{
    Node * pnode = * plist;
    while(pnode != NULL)
    {
        (*pfun)(pnode->item);    // 调用函数
        pnode = pnode->next;
    }
}

void EmptyTheList(List * plist)
{
    Node *psave;
    while(*plist != NULL)
    {
        psave = (*plist)->next;  // 保存下一个节点地址
        free(*plist);
        *plist = psave;    //前进到下一个节点
    }
}

// 局部函数定义
static void CopyToNode(Item item, Node * pnode)
{
    pnode->item = item;    // 结构复制
}

使用接口

  我们在使用这个接口编写程序不必知道太多的细节。比如不用知道函数是如何编写的。这里我们编写一个存储电影影片的程序。

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
/* firms.c -- 使用ADT风格的链表 */
/* 和listc 一同编译*/
#include <stdio.h>
#include <stdlib.h>  /* exit()原型 */
#include "list.h"    /* 定义List， Item */
void showmovies(Item item);

int main(void)
{
    List movies;
    Item temp;

    //初始化
    InitializeList(&movies);
    if (ListIsFull(&movies))
    {
        fprintf(stderr, "No memory available! Bye!\n");
        exit(1);
    }

    // 收集并存储
    puts("Enter first movie title: ");
    while(gets(temp.title) != NULL && temp.title[0] != '\0')
    {
        puts("Enter your rating <0-10>");
        scanf("%d", &temp.rating);
        while(getchar() != '\n')
            continue;
        if (AddItem(temp, &movies) == false)
        {
            fprintf(stderr, "Problem allocating memory");
            break;
        }
        if (ListIsFull(&movies))
        {
            puts("The list is noe full");
            break;
        }
        puts("Enter next movie title(empty line to quit)");
    }

    //显示
    if(ListIsEmpty(&movies))
        printf("No data entered. ");
    else
    {
        printf("Here is the movie list:\n");
        Traverse(&movies, showmovies);
    }
    printf("You entered %d movies.\n", ListItemCount(&movies));

    //清除
    EmptyTheList(&movies);
    printf("Bye!\n");
    return 0;
}

void showmovies(Item item)
{
    printf("Movie: %s Rating: %d\n", item.title, item.rating);
}

程序运行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Enter first movie title:
aaaa
Enter your rating <0-10>
8
Enter next movie title(empty line to quit)
bbbb
Enter your rating <0-10>
9
Enter next movie title(empty line to quit)
cccc
Enter your rating <0-10>
7
Enter next movie title(empty line to quit)

Here is the movie list:
Movie: aaaa Rating: 8
Movie: bbbb Rating: 9
Movie: cccc Rating: 7
You entered 3 movies.
Bye!