ADT

2023-06-08 in C

记录 C Prime Plus 关于数据结构的知识

学习笔记，仅供参考

参考：C Prime Plus - 十七章

ADT 抽象数据类型

学习计算机语言首先要学会如何使用工具（创建变量、结构、函数等），然而工具是次要的，真正的挑战是设计和创建一个项目。

程序开发最重要的部分是找到程序中表示数据的好方法。目前 C 语言内置类型有基本类型、数组、指针、结构和联合。然而找出正确的数据不仅仅是选择一种数据类型，还要考虑必须进行哪些操作，即确定如何存储数据，并为数据类型定义有效的操作。

简而言之，设计一种数据类型包含设计如何储存该数据类型（数据结构）和设计一系列管理该数据的方法（算法）

类型特指两类信息：属性和操作。如 int 类型的属性是它表示一个整数值，享有整数的属性。int 类型的操作，改变 int 值的符号，能让两个 int 值加减乘除等算数运算。

数据类型的抽象与具体实现，还以整数为例，数学家通过如下定义给出整数的抽象概念：假设 M 和 N 为整数，那么 M+N=N+M；假设 S 和 Q 也为整数，若 N+M=S，且 N+Q=S，则 M=Q。C 语言也实现了整数的这种算数运算。再如数学中的整数可以是无穷大，但 C 中会受到硬件的影响只能表示一定的范围内的整数。所以要清除抽象概念与实际实现。

下面用 3 个步骤完成从抽象到具体的过程：

提供类型属性和相关操作的抽象描述。这些描述既不依赖特定实现，也不依赖特定的编程语言。这种抽象描述被称为抽象数据类型（ADT）
开发一个实现 ADT 的编程接口，即指明如何储存数据和执行所需操作的函数。如 C 中，可提供结构定义和操控该结构的函数原型。这些作用于用户定义类型的函数相当于 C 基本类型的内置运算符，需使用该新类型的程序员可使用此接口进行编程

编写代码实现接口。使用者无需了解此新类型的具体实现细节

/* 以电影项目为例，采用简化链表作为 ADT */
// 1. 类型属性及操作
类型名：简单链表
类型属性：可存储一系列项
类型操作：初始化链表为空
    确定链表为空
    确定链表已满
    确定链表中的项数
    在链表末尾添加项
    遍历链表，处理链表中的项
    清空链表

// 2. 建立接口 - 表示数据及实现操作
/* list.h */
#ifndef __LIST_H_
#define __LIST_H_

#include <stdbool.h>

#define TSIZE       45

/* 定义电影数据类型 */
typedef struct film {
char title[TSIZE];      // 影片名
int rating;             // 排名
} Item;

/* 以链表储存数据类型 */
typedef struct node {
Item item;              // 数据项
struct node *next;      // 后驱指针
} Node;

typedef Node *List;

/* 函数原型声明 */
void InitializeList(List *plist);
bool ListIsEmpty(const List *plist);
bool ListIsFull(const List *plist);
unsigned int ListItemCount(const List *plist);
bool AddItem(Item item, List *plist);
void Traverse(const List *plist, void(*pfun)(Item item));
void EmptyTheList(List *plist);

#endif
/*********************************/

/* 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 *pt;
bool full;

pt = (Node *)malloc(sizeof(Node));
if (pt == NULL)
    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);
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;
}
/*******************************/

/* main.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

void showmovies(Item item);
char *s_gets(char *st, int n);

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 (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '\0') {
    puts("Enter your rating <0-10>:");
    scanf("%d", &temp.rating);
    while (getchar() != '\n')
        continue;
    printf("get Item OK\n");
    if (AddItem(temp, &movies) == false) {
        fprintf(stderr, "Problem allocating memory\n");
        break;
    }
    printf("add Item OK\n");
    if (ListIsFull(&movies)) {
        puts("The list is now full.");
        break;
    }
    puts("Enter next movies title (empty line to stop):");
}

/* 显示 */
if (ListIsEmpty(&movies))
    printf("No data entered.  ");
else {
    printf("Here is the movies 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("Movies: %s  Rating: %d\n", item.title, item.rating);
}

char *s_gets(char *st, int n)
{
char *ret_val;
char *find;

ret_val = fgets(st, n, stdin);
if (ret_val) {
    find = strchr(st, '\n');    // 查找换行符
    if (find)
        *find = '\0';
    else
        while (getchar() != '\n')
            continue;
}

return ret_val;
}

接着再看看队列，它是具有两个特殊属性的链表。第一，新项只能从链表末尾添加；第二，只能从链表开头移出项。队列是一种“先进先出”的数据形式，像排队买票的队伍一样

/* 建立非正式的抽象定义 */
类型名：队列
类型属性：可储存一系列项
类型操作：初始化队列为空
         确定队列为空
         确定队列已满
         确定队列中的项数
         在队列末尾添加项
         在队列开头删除或恢复项
         清空队列

/* 简单队列的数据定义及接口实现 */
/* queue.h */
#ifndef __DATATYPE_H_
#define __DATATYPE_H_

#include <stdbool.h>

#define MAXQUEUE    10

typedef int Item;
typedef struct node {
    Item item;          /* 数据项 */
    struct node *next;  /* 后驱指针 */
} Node;

typedef struct queue {
    Node *front;        /* 队列首指针 */
    Node *rear;         /* 队列尾指针 */
    int items;          /* 队列项数 */
} Queue;

void InitializeQueue(Queue *pq);
bool QueueIsFull(const Queue *pq);
bool QueueIsEmpty(const Queue *pq);
int QueueItemCount(const Queue *pq);
bool EnQueue(Item item, Queue *pq);
bool DeQueue(Item *pitem, Queue *pq);
void EmptyTheQueue(Queue *pq);

#endif
/****************************************************/

/* queue.c */
#include <stdio.h>
#include <stdlib.h>

#include "datatype.h"

static void CopyToNode(Item item, Node *pn);
static void CopyToItem(Node *pn, Item *pi);

/**
 * @brief 初始化队列
 * @param pq 要初始化的队列
 * @retval null
*/
void InitializeQueue(Queue *pq)
{
    pq->front = pq->rear = NULL;
    pq->items = 0;
}

/**
 * @brief 队列是否已满
 * @param pq 所检查的队列
 * @retval true or false
*/
bool QueueIsFull(const Queue *pq)
{
    return pq->items == MAXQUEUE;
}

/**
 * @brief 队列是否为空
 * @param pq 所检查的队列
 * @retval true or false
*/
bool QueueIsEmpty(const Queue *pq)
{
    return pq->items == 0;
}

/**
 * @brief 获取队列项数
 * @param pq 目标队列
 * @retval 该队列项数
*/
int QueueItemCount(const Queue *pq)
{
    return pq->items;
}

/**
 * @brief 在队列尾端添加项
 * @param item 要添加的项
 * @param pq 队列
 * @retval true or false
*/
bool EnQueue(Item item, Queue *pq)
{
    Node *pnew;

    if (QueueIsFull(pq))    /* 队列已满，添加失败 */
        return false;

    pnew = (Node *)malloc(sizeof(Node));
    if (pnew == NULL) {
        fprintf(stderr, "Unable to allocate memory!\n");
        exit(1);
    }

    CopyToNode(item, pnew);
    pnew->next = NULL;

    if (QueueIsEmpty(pq))
        pq->front = pnew;       /* 队列为空，项位与队列首端 */
    else
        pq->rear->next = pnew;  /* 链接到队列尾端 */
    
    pq->rear = pnew;        /* 队列尾指针更新 */
    pq->items++;            /* 队列项数加 1 */
    
    return true;
}


/**
 * @brief 在队列首端删除项
 * @param item 删除的项
 * @param pq 队列
 * @retval true or false
*/
bool DeQueue(Item *pitem, Queue *pq)
{
    Node *pt;

    if (QueueIsEmpty(pq))
        return false;

    CopyToItem(pq->front, pitem);
    pt = pq->front;
    pq->front = pq->front->next;
    free(pt);
    pq->items--;

    if (pq->items == 0)
        pq->rear = NULL;

    return true;
}

void EmptyTheQueue(Queue *pq)
{
    Item dummy;

    while (!QueueIsEmpty(pq))
        DeQueue(&dummy, pq);
}

static void CopyToNode(Item item, Node *pn)
{
    pn->item = item;
}

static void CopyToItem(Node *pn, Item *pi)
{
    *pi = pn->item;
}
/****************************************************/

/* main.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "datatype.h"

int main(void)
{
    Queue line;
    Item temp;
    char ch;
    InitializeQueue(&line);
    
    puts("Testing the Queue interface. Type a to add a value,");
    puts("type d to delete a value, and type q to quit.");
    while ((ch = getchar()) != 'q') {
        if (ch != 'a' && ch != 'd')
            continue;

        if (ch == 'a') {
            printf("Interger to add: ");
            scanf("%d", &temp);
            if (!QueueIsFull(&line)) {
                printf("Putting %d into queue\n", temp);
                EnQueue(temp, &line);
            } else {
                puts("Queue is full!");
            }
        } else {
            if (QueueIsEmpty(&line)) {
                puts("Nothing to delete!");
            } else {
                DeQueue(&temp, &line);
                printf("Removing %d from queue\n", temp);
            }
        }

        printf("%d items in queue\n", QueueItemCount(&line));
        puts("Type a to add, d to delete, q to quit:");
    }

    EmptyTheQueue(&line);
    puts("Bye!");

    return 0;
}
/****************************************************/

链表与数组

许多编程问题，如创建简单链表或队列，都可用链表（动态分配的序列链）或数组来处理。下面是两者的优缺点：

数组：优点-C 直接支持；提供随机访问 | 缺点-在编译时确定大小；插入删除元素很费时

链表：优点-运行时确定大小；快速插入删除元素 | 缺点-不能随机访问；用户必须提供编程支持

当需向数组或链表中插入数据时，数组就需将附近的元素搬移以便腾出空间存储要插入的项；而链表只需修改插入位置前后节点的指针即可，删除亦如此。当要在数组或队列中查找某一元素是否存在时，数组可以使用顺序查找或二分查找（数组已排序），而链表只能用顺序查找。所以选择何种数据类型取决于具体问题，若需频繁增删数据而不怎么查找数据的情况下，应选择链表；若只偶尔增删数据，但要经常进行查找，应选用数组。要是需要既能支持频繁增删数据也能支持频繁查找的数据类型时，则要选择下面介绍的二叉查找树

二叉查找树

二叉查找树是一种结合了二分查找策略的链接结构。二叉树的每个节点都含有一个项和两个节点指针，分别指向左节点和右节点。并且节点有顺序规则：左节点的项在父节点项的前面，右节点的项在父节点项的后面。这种数据结构类似于自然界中的树形结构，因此以‘树’来代指这一结构。树顶被称为根，树具有分层组织或等级，每级都有上一级和下一级。若二叉树是满的，那么每一级的节点数是上一级节点数的两倍。

二叉查找树的每个节点是其后代节点的根，该节点与其后代节点构成的树称为一个子树。二叉树查找目标项：若目标项在根节点项的前面，则只需查找左子树；若在根节点项的后面，则只需查找右子树。二叉查找树在链式结构中结合了二分查找的效率，但所带来的代价是编程时要构建一个二叉树比创建一个链表跟复杂

/* 二叉树的 ADT */
类型名：二叉查找树
类型属性：二叉树要么是空节点的集合（空树），要么是有一个根节点的节点集合
         每个节点都有两个子树，称左子树和右子树
         每个子树本身也是一个二叉树，抑或是空树
         二叉查找树是一个有序的二叉树，每个节点包含一个项
         左子树的所有项都在根节点项的前面，右子树的所有项都在根节点项的后面
类型操作：初始化树为空
         确定树是否为空
         确定树是否已满
         在树中添加一个项
         在树中删除一个项
         在树中查找一个项
         在树中访问一个项
         清空树

/* 二叉查找树的定义及接口实现 */
/* tree.h */
#ifndef __DATATYPE_H_
#define __DATATYPE_H_

#include <stdbool.h>

#define SLEN        20
#define MAXITEMS    10

typedef struct item {       /* 定义数据项 */
    char petname[SLEN];
    char petkind[SLEN];
} Item;

typedef struct trnode {     /* 定义树形节点 */
    Item item;
    struct trnode *left;    /* 左节点指针 */
    struct trnode *right;   /* 右节点指针 */
} Trnode;

typedef struct tree {
    Trnode *root;           /* 根节点指针 */
    int size;               /* 树的项数 */
} Tree;

void InitializeTree(Tree *ptree);
bool TreeIsEmpty(const Tree *ptree);
bool TreeIsFull(const Tree *ptree);
int TreeItemCount(const Tree *ptree);
bool AddItem(const Item *pi, Tree *ptree);
bool InTree(const Item *pi, const Tree *ptree);
bool DeleteItem(const Item *pi, Tree *ptree);
void Traverse(const Tree *ptree, void(*pfun)(Item item));
void DeleteAll(Tree *ptree);

#endif
/*****************************************************/

/* tree.c */
#include <stdio.h>
#include <stdlib.h>

#include "datatype.h"

/* 局部数据类型 */
typedef struct pair {
    Trnode *parent;
    Trnode *child;
} Pair;

/* 局部函数原型 */
static Trnode *MakeNode(const Item *pi);
static bool ToLeft(const Item *i1, const Item *i2);
static bool ToRight(const Item *i1, const Item *i2);
static void AddNode(Trnode *new_node, Trnode *root);
static void InOrder(const Trnode *root, void(*pfun)(Item item));
static Pair SeekItem(const Item *pi, const Tree *ptree);
static void DeleteNode(Trnode **ptr);
static void DeleteAllNodes(Trnode *ptr);

void InitializeTree(Tree *ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

bool TreeIsEmpty(const Tree *ptree)
{
    if (ptree->root == NULL)
        return true;
    else
        return false;
}

bool TreeIsFull(const Tree *ptree)
{
    if (ptree->size == MAXITEMS)
        return true;
    else
        return false;
}

int TreeItemCount(const Tree *ptree)
{
    return ptree->size;
}

/**
 * @brief 向树中添加新项
 * @param pi 要添加的新项
 * @param ptree 树形结构指针
 * @retval true or false
*/
bool AddItem(const Item *pi, Tree *ptree)
{
    Trnode *new_node;

    if (TreeIsFull(ptree)) {                    /* 检查树是否已满 */
        fprintf(stderr, "Tree is full\n");
        return false;
    }

    if (SeekItem(pi, ptree).child != NULL) {    /* 检查树中是否已存在新项 */
        fprintf(stderr, "Attempted to add duplicate item\n");
        return false;
    }

    new_node = MakeNode(pi);    /* 指向新节点 */
    if (new_node == NULL) {
        fprintf(stderr, "Couldn't create node\n");
        return false;
    }

    /* 成功创建一个新节点 */
    ptree->size++;
    if (ptree->root == NULL)        /* 情况1：树为空 */
        ptree->root = new_node;     /* 新节点为树根节点 */
    else                            /* 情况2：树非空 */
        AddNode(new_node, ptree->root); /* 在树中添加一个节点 */

    return true;
}

bool InTree(const Item *pi, const Tree *ptree)
{
    return (SeekItem(pi, ptree).child == NULL) ? false : true;
}

bool DeleteItem(const Item *pi, Tree *ptree)
{
    Pair look;

    look = SeekItem(pi, ptree);
    if (look.child == NULL)
        return false;

    if (look.parent == NULL)        /* 删除根节点项 */
        DeleteNode(&ptree->root);
    else if (look.parent->left == look.child)   /* 删除左节点 */
        DeleteNode(&look.parent->left);
    else                                        /* 删除右节点 */
        DeleteNode(&look.parent->right);
    
    ptree->size--;

    return true;
}

void Traverse(const Tree *ptree, void(*pfun)(Item item))
{
    if (ptree != NULL)
        InOrder(ptree->root, pfun);
}

void DeleteAll(Tree *ptree)
{
    if (ptree != NULL)
        DeleteAllNodes(ptree->root);

    ptree->root = NULL;
    ptree->size = 0;
}

/**
 * @brief 动态分配树形节点，并初始化项及左右指针
 * @param pi 所要初始化的项
 * @retval 成功创建后的树节点指针
*/
static Trnode *MakeNode(const Item *pi)
{
    Trnode *new_node;

    new_node = (Trnode *)malloc(sizeof(Trnode));
    if (new_node != NULL) {
        new_node->item = *pi;
        new_node->left = NULL;
        new_node->right = NULL;
    }

    return new_node;
}
static bool ToLeft(const Item *i1, const Item *i2)
{
    int comp1;

    if ((comp1 = strcmp(i1->petname, i2->petname)) < 0) /* 目标名称在前 */
        return true;
    else if (comp1 == 0 && 
             strcmp(i1->petkind, i2->petkind) < 0)      /* 名称相同，目标种类在前 */
        return true;
    
    return false;
}

static bool ToRight(const Item *i1, const Item *i2)
{
    int comp1;

    if ((comp1 = strcmp(i1->petname, i2->petname)) > 0) /* 目标名称在后 */
        return true;
    else if (comp1 == 0 && 
             strcmp(i1->petkind, i2->petkind) > 0)      /* 名称相同，目标种类在后 */
        return true;
    
    return false;
}

static void AddNode(Trnode *new_node, Trnode *root)
{
    if (ToLeft(&new_node->item, &root->item)) { /* 判断在根节点左边 */
        if (root->left == NULL)         /* 空子树，此处添加节点 */
            root->left = new_node;
        else                            /* 否则，递归处理左子树 */
            AddNode(new_node, root->left);
    } else if (ToRight(&new_node->item, &root->item)) { /* 判断在根节点右边 */
        if (root->right == NULL)
            root->right = new_node;
        else
            AddNode(new_node, root->right);
    } else {     /* 与根节点项相同，不允许重复 */
        fprintf(stderr, "location error in AddNode()\n");
        exit(1);
    }
}

static void InOrder(const Trnode *root, void(*pfun)(Item item))
{
    if (root != NULL) {
        InOrder(root->left, pfun);
        (*pfun)(root->item);
        InOrder(root->right, pfun);
    }
}

/**
 * @brief 检查目标项 pi 是否已存在于树中
 * @param pi 目标项
 * @param ptree 树形指针
 * @retval look.child 为 NULL 则目标项不在树中，否则在树中
*/
static Pair SeekItem(const Item *pi, const Tree *ptree)
{
    Pair look;

    look.parent = NULL;
    look.child = ptree->root;
    if (look.child == NULL)     /* 空树 */
        return look;
    
    while (look.child != NULL) {
        if (ToLeft(pi, &look.child->item)) {    /* 从左子树查 */
            look.parent = look.child;
            look.child = look.child->left;
        } else if (ToRight(pi, &look.child->item)) {    /* 从右子树查 */
            look.parent = look.child;
            look.child = look.child->right;
        } else                          /* 相等情况 */
            break;      /* look.child 为目标项节点 */
    }

    return look;
}
static void DeleteNode(Trnode **ptr)
{
    /* ptr 是指向目标节点的父节点指针成员的地址 */
    Trnode *temp;

    if ((*ptr)->left == NULL) {     /* 左节点为 NULL，释放根节点并将右节点作为根节点 */
        temp = *ptr;
        *ptr = (*ptr)->right;
        free(temp);
    } else if ((*ptr)->right == NULL) { /* 左非 NULL，右为 NULL，释放根并将左节点作为根节点 */
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    } else {    /* 左右非 NULL，先找出左子树的最大（即最右叶节点 X），再将右子树节点链接到 X 的右节点，根节点指针偏移到左节点，删除根节点*/
        for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)
            continue;
        temp->right = (*ptr)->right;
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
}

static void DeleteAllNodes(Trnode *root)
{
    Trnode *pright;

    if (root != NULL) {
        pright = root->right;
        DeleteAllNodes(root->left); /* 删除根节点左子树 */
        free(root);                 /* 删除根节点 */
        DeleteAllNodes(pright);     /* 删除根节点右子树 */
    }
}
/*****************************************************/

/* main.c */
/**
 * @file 该程序以菜单的形式提供选择：向俱乐部成员花名册添加宠物、显示成员列表、
 *       报告成员数量、核实成员及退出。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "datatype.h"

char menu(void);
void addpet(Tree *pt);
void droppet(Tree *pt);
void showpets(const Tree *pt);
void findpet(const Tree *pt);
void printitem(Item item);
void uppercase(char *str);
char *s_gets(char *st, int n);

int main(void)
{
    Tree pets;
    char choice;

    InitializeTree(&pets);
    while ((choice = menu()) != 'q') {
        switch (choice) {
            case 'a':
                addpet(&pets);
                break;
            case 'l':
                showpets(&pets);
                break;
            case 'f':
                findpet(&pets);
                break;
            case 'n':
                printf("%d pets in club\n", TreeItemCount(&pets));
                break;
            case 'd':
                droppet(&pets);
                break;
            default:
                puts("Switching error");
                break;
        }
    }
    DeleteAll(&pets);
    puts("Bye.");

    return 0;
}

char menu(void)
{
    int ch;

    puts("Nerfville Pet Club Membership Program");
    puts("Enter the letter corresponding to your choice:");
    puts("a) add a pet          l) show list of pets");
    puts("n) number of pets     f) find pets");
    puts("d)delete a pet        q) quit");

    while ((ch = getchar()) != EOF) {
        while (getchar() != '\n')
            continue;
        if (strchr("alrfndq", ch) == NULL)
            puts("Please enter an a, l, n, f, d or q:");
        else
            break;
    }

    if (ch == EOF)  /* 使程序退出 */
        ch = 'q';
        
    return ch;
}

void addpet(Tree *pt)
{
    Item temp;

    if (TreeIsFull(pt))
        puts("No room in the club!");
    else {
        puts("Please enter name of pet:");
        s_gets(temp.petname, SLEN);
        puts("Please enter pet kind:");
        s_gets(temp.petkind, SLEN);
        uppercase(temp.petname);
        uppercase(temp.petkind);
        AddItem(&temp, pt);
    } 
}

void droppet(Tree *pt)
{
    Item temp;

    if (TreeIsEmpty(pt)) {
        puts("No entries!");
        return;
    }

    puts("Please enter name of pet you wish to delete:");
    s_gets(temp.petname, SLEN);
    puts("Please enter pet kind:");
    s_gets(temp.petkind, SLEN);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s the %s ", temp.petname, temp.petkind);

    if (DeleteItem(&temp, pt))
        printf("is dropped from the club.\n");
    else 
        printf("is not a member.\n");
}

void findpet(const Tree *pt)
{
    Item temp;

    if (TreeIsEmpty(pt)) {
        puts("No entries!");
        return;
    }

    puts("Please enter name of pet you wish to find:");
    s_gets(temp.petname, SLEN);
    puts("Please enter pet kind:");
    s_gets(temp.petkind, SLEN);
    uppercase(temp.petname);
    uppercase(temp.petkind);
    printf("%s the %s ", temp.petname, temp.petkind);

    if (InTree(&temp, pt))
        printf("is a member.\n");
    else   
        printf("is not a member.\n");
}

void showpets(const Tree *pt)
{
    if (TreeIsEmpty(pt))
        puts("No entries!");
    else
        Traverse(pt, printitem);
}
void printitem(Item item)
{
    printf("Pet: %-19s Kind: %-19s\n", item.petname, item.petkind);
}

void uppercase(char *str)
{
    while (*str) {
        *str = toupper(*str);
        str++;
    }
}


char *s_gets(char *st, int n)
{
    char *ret_val;
    char *find;

    ret_val = fgets(st, n, stdin);
    if (ret_val) {
        find = strchr(st, '\n');    // 查找换行符
        if (find)
            *find = '\0';
        else
            while (getchar() != '\n')
                continue;
    }

    return ret_val;
}
/*****************************************************/

二叉查找树在编程实现重要部分是节点的添加与删除，添加要判断是在根节点的左边还是右边，如此递归直到满足条件；删除要看是删除叶节点、带有单个子树的节点或是具有左右子树的节点，特别是最后一种要考虑删除之后左右节点如何拼接，另外删除节点时要以左节点-根节点-右节点的顺序删除。同时 tree.c 中局部函数也至关重要，它们是对增删细节操作的封装。在查找时根据根节点作为判断标准，将查找范围缩小到左边或是右边，其中实现涉及到递归以简化这种重复操作。

树的思想

二叉查找树的缺点，只有在满员（或平衡）时效率最高。当后续节点都挂到父节点的右节点上，这就构成不平衡的树。对于这种不平衡的串形树，需重新排列节点使之恢复平衡。俄国数学家 Adel’son-Vel’skii 和 Landis 发明一种算法解决不平衡的问题，根据这种算法所创建的树称为 AVL 树。

要徒手实现一个链表或数这种 ADT 比较困难，很容易犯错，而插件库则提供了一种可选方法。通过本章的学习，能更好地认识这样的数据类型的实现。