抽象数据类型之链表ADT接口包
本帖最后由 mingcxx 于 2016-9-6 00:50 编辑C的基础大致学完了，感觉几个ADT的接口包可能以后会用。所以先存到这里，方便找。
这是一个单项链表，也可以修改Item的结构类型，加入一个指向前一节点的指针，变成双向链表。
//list.h -- 简单列表类型的头文件
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h> //C99特性，兼容C++
//特定于程序的声明
#define TSIZE 45 //存放影片名的数组大小
struct film
{
char title;
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;
}
页:
[1]