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

mingcxx

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

//list.h -- 简单列表类型的头文件

#ifndef LIST_H_
#define LIST_H_

#include <stdbool.h>                //C99特性，兼容C++

//特定于程序的声明
#define TSIZE 45                        //存放影片名的数组大小

struct film
{
        char title[TSIZE];
        int rating;
};

//一般类型定义，根据实际需要修改Item
typedef struct film Item;

typedef struct node
{
        Item item;
        struct node * next;
} Node;

typedef Node * List;

//函数原型

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


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


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


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


/*操作：在列表尾部添加一个项目
操作前：Item是要被增加到列表的项目
                plist指向一个已初始化的列表
操作后：如果可能的话，在列表尾部添加
                一个新项目，函数返回true，
                否则返回false*/
bool AddItem(Item item, List * plist);


/*操作：把一个函数作用于列表中的每个项目
操作前：plist指向一个已初始化的列表，
                pfun指向一个函数，该函数接受
                一个Item参数并且无返回值
操作后：pfun指向个函数被作用到列表
                中的每个项目一次*/
void Traverse(const List * plist, void(*pfun)(Item item));


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


#endif // !LIST_H_

//list.c -- 支持链表操作的函数实现

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

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

//接口函数

/*把列表设置为空列表*/
void InitializeList(List * plist)
{
        *plist = NULL;
}

/*如果列表为空则返回真，否则返回假*/
bool ListIsEmpty(const List * plist)
{
        if (*plist == NULL)
        {
                return true;
        }
        else
        {
                return false;
        }
}

/*如果列表已满则返回真，否则返回假*/
bool ListIsFull(const List * plist)
{
        Node * pnode = (Node *)malloc(sizeof(Node));
        if (pnode == NULL)
        {
                return true;
        }
        else
        {
                free(pnode);
                return false;
        }
}

/*返回节点数*/
unsigned int ListItemCount(const List * plist)
{
        Node * pnode = *plist;
        unsigned int count = 0;

        while (pnode != NULL)
        {
                ++count;
                pnode = pnode->next;
        }

        return count;
}

/*创建存放项目的节点，并把它添加到
plist指向的列表的尾部（较慢的方法）*/
bool AddItem(Item item, List * plist)
{
        Node * pnode = (Node *)malloc(sizeof(Node));
        Node * scan = *plist;

        if (pnode == NULL)
        {
                return false;
        }

        CopyToNode(item, pnode);
        pnode->next = NULL;
        if (scan == NULL)
        {
                *plist = pnode;
        }
        else
        {
                while (scan->next != NULL)
                {
                        scan = scan->next;
                }
                scan->next = pnode;
        }


        return true;
}

/*访问每个节点并对它们分别执行pfun指向的函数*/
void Traverse(const List * plist, void(*pfun)(Item item))
{
        Node * pnode = *plist;

        while (pnode != NULL)
        {
                (*pfun)(pnode->item);
                pnode = pnode->next;
        }
}


/*释放由malloc()分配的内存
把列表指针设置为NULL*/
void EmptyTheList(List * plist)
{
        Node * tmp;

        while (*plist != NULL)
        {
                tmp = (*plist)->next;
                free(*plist);
                *plist = tmp;
        }
}


//局部函数定义

//把一个项目复制到一个节点中
static void CopyToNode(Item item, Node * pnode)
{
        pnode->item = item;
}