C-study(十七)

开始

程序设计：正确表示数据、对数据有效的操作

类型：属性、操作

设计一种数据类型：
1、设计如何存储该类型、eg:内置类型：变量、数组、指针、结构、联合
2、设计一系列管理数据的函数、eg:算法：操控数据的方法

抽象数据类型 ADT

1、抽象描述 ：类型属性+操作、不依赖实现和编程语言
2、声明：定义编程接口、如何存储数据、执行操作的函数、eg:结构定义和操控结构的函数原型
3、实现：实现接口、操控数据的接口、eg:函数实现、用户不需要了解

ANSI C库中提供多种扩展库：Windows图形接口、访问Macintosh工具箱的函数、Linux图形接口等等

结构数组

/*films1.c --使用一个结构数组、一年内看的所有电影*/
#include <stdio.h>
#include <stdlib.h>/*提供malloc()原型*/
#include <string.h>
#define TSIZE 45 /*储存片名的数组大小*/
#define FMAX 5   /*影片的最大数量、先指定数组大小：不灵活、多了内存限制、少了数据不够*/
struct film
{
    char title[TSIZE];
    int rating;
};
char *s_gets(char str[], int lim);
int main(void)
{
    struct film movies[FMAX];
    /*结构数组、自动存储类别、部分编译器会限制自动存储类别可用内存
    可声明为静态或外部数组、编译器设置更大的栈、动态数组
    int n;
    struct film *movies; 指向结构的指针、和数组名一样使用
    printf("Enter the maximum number of movies you'll enter : \n");
    scanf("%d", &n);推迟到程序运行时确定数组元素数量
    movies = (struct film *)malloc(n * sizeof(struct film));分配连续内存块、指向分配块中的第一个结构*/
    
    int i = 0;
    int j;
    puts("Enter first movie title: ");
    while (i < FMAX && s_gets(movies[i].title, TSIZE) != NULL && movies[i].title[0]!='\0')
    {//数据满、到达文件结尾、行开始处按下enter
        puts("Enter your rating <0-10>:");
        scanf("%d", &movies[i++].rating);//存放用户输入的数据
        while (getchar() != '\n')
            continue;
        puts("Enter next movie title (empty line to stop):");
    }
    if (i == 0)
        printf("No data entered. ");
    else
        printf("Here is the movie list : \n");
    for (j = 0; j < i; j++)
        printf("Movie: %s Rating: %d\n", movies[j].title, movies[j].rating);
    printf("Bye ! \n");
    return 0;
}
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)                // 如果地址不是NULL,
            *find = '\0'; // 在此处放置一个空字符
        else
            while (getchar() != '\n')
                continue; // 处理剩余输入行
    }
    return ret_val;
}

链表

不确定的添加数据、不指定要输入多少项、不分配多余空间
每次输入一项之后malloc分配一项的空间、单独分配、内存不连续、每个指针指向一个单独存储的结构

指针数组：大型指针数组、分配时给指针赋值、浪费空间、内存限制

链表：结构中加一个（跟踪下一项的）指针、每次malloc结构时、同时分配指针
头指针、单独的指针结构存储第一个结构的地址

1、分配空间、地址赋给头指针、tittle和rating赋值、next指针设为NULL（最后一个结构）

2、分配空间、地址赋给上一个结构的next指针、tittle和rating赋值、next指针设为NULL

#define TSIZE 45 /*储存片名的数组大小*/ 
#define FMAX 500 /*影片的最大数量*/ 
struct film {
char title[TSIZE];
int rating;};
struct film *movies[FMAX]; /*结构指针数组、固定大小、不灵活、多了内存限制、少了数据不够*/
int i;
movies[i] = (struct film *)malloc(sizeof(struct film));//分配之后给指针数组赋值


/*films2.c-- 使用结构链表 */
struct film
{
    char title[TSIZE];
    int rating;
    struct film *next; /*指向链表中的下一个结构*/
};
int main(void)
{
    struct film *head = NULL;//头指针、只包含第一个结构的地址、不用于移动
    struct film *prev, *current;//current当前项指针、用于存储信息和移动、prev保留上一项、用于设置上一项的指针
    char input[TSIZE]; //临时存储用户输入、确认需要再创建结构
    puts("Enter first movie title: ");
    /*收集并储存信息*/
    while (s_gets(input, TSIZE) != NULL && input[0] != '\0')
    {//EOF、空行
        current = (struct film *)malloc(sizeof(struct film));//1、分配一个结构空间、if(current)检查分配是否成功
        if (head == NULL) /*第1个结构、头指针赋值*/
            head = current;	//2、存储结构地址
        else /*后续的结构、地址存储在前一个结构的next中*/
            prev->next = current;
        current->next = NULL;//当前结构是链表最后一个
        strcpy(current->title, input);//3、拷贝信息
        puts("Enter your rating <0-10>: ");
        scanf("%d", &current->rating);
        while (getchar() != '\n')
            continue;
        puts("Enter next movie title (empty line to stop): ");
        prev = current;//prev指向当前结构、方便下一个结构地址赋值
    }

    /*显示链表*/
    if (head == NULL) //头指针为空时链表为空
        printf("No data entered. ");
    else
        printf("Here is the movie list : \n");
    current = head;//当前指针移动到第一个结构
    while (current != NULL)//链表最后一项时current == NULL
    {
        printf("Movie: %s Rating: %d\n", current->title, current->rating);
        current = current->next;//移动到下一指针
    }
    
    /*完成任务，释放已分配的内存*/
    current = head;
	while (current != NULL && head!=NULL)//head!=NULL避免head已经为空head = current->next;报错
    {
        current = head;
        head = current->next;
        free(current);//每个分配的结构都要free
    }
    printf("Bye ! \n");
    return 0;
}

链表ADT

隐藏数据表示和操作细节、调用接口、不需要涉及到内存和指针
list.h和list.c可复用、只需要重新定义item类型

抽象链表定义 理论

只定义属性和功能、不定义具体实现
类型名:简单链表
类型属性:可以储存一系列项
类型操作:
初始化链表为空
确定链表为空
确定链表已满
确定链表中的项数
在链表末尾添加项
遍历链表，处理链表中的项
清空链表

在链表的任意位置添加项;
移除项;
检索项（不改变链表);
用另一个项替换链表中的一个项;
搜索项。

抽象对应的接口 .h

描述数据、声明函数

/*list.h --简单链表类型的头文件、声明结构和接口*/
#ifndef LIST_H_//防止多次包含一个文件
#define LIST_H_
#include <stdbool.h>/*c99特性bool类型 
enum bool {false,true};把bool定义为类型，false和true是该类型的值*/
#define TSIZE 45 /*特定程序的声明、储存电影名的数组大小*/
struct film
{
    char title[TSIZE];
    int rating;
};
typedef struct film Item;//结构别名、通用Item类型、film需要修改时不会动到链表
typedef struct node
{
    Item item;
    struct node *next;
} Node;//结构别名、链表节点：链表内容+下一个节点的指针
typedef Node * List;
/*指向链表开始处的指针
List movies; 相当于Node * movies
初始化 movies=NULL;
typedef struct list
{
    Node * head;    //链表头文件
    int size;       //链表项数
}List;              //List的另一种定义
List movies; 相当于struct list movies
初始化 movies.next=NULL; movies.size=0;
*/

/*函数原型*/
/*操作:初始化一个链表*/
/*前提条件:plist指向一个链表*/
/*后置条件:链表初始化为空*/
void InitializeList(List *plist);

/*操作:确定链表是否为空定义，plist指向一个已初始化的链表*/
/*后置条件:如果链表为空，该函数返回true;否则返回false*/
bool ListIsEmpty(const List *plist);

/*操作:确定链表是否已满，plist指向一个已初始化的链表*/
/*后置条件:如果链表已满，该函数返回真;否则返回假*/
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类型的参数，且无返回值 void showmovies(Item item)
后置条件:pfun指向的函数作用于链表中的每一项一次*/
void Traverse(const List *plist, void (*pfun)(Item item));

/*操作:释放已分配的内存（如果有的话)*/
/*plist指向一个已初始化的链表*/
/*后置条件:释放了为链表分配的所有内存，链表设置为空*/
void EmptyTheList(List *plist);
#endif

接口实现 .c

/*list.c-- 支持链表操作的函数 隐藏实现细节*/
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
/*局部函数原型、不作为外部接口*/
static void CopyToNode(Item item, Node *pnode);

/*接口函数
List plist; 相当于Node *
plist 链表头指针、存放链表首项地址
涉及到修改链表的InitializeList、AddItem、EmptyTheList需要传入指向头指针的指针
为形式一致、不涉及修改的、const修饰：可以避免指针被修改、无法跟踪数据；*plist =(*plist)->next;//如果*plist是const，不允许这样做
但无法避免数据被修改(*plist)->item.rating = 3;//即使*plist是const，也可以这样做
直接传参、只会操作副本*/

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

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

/*如果链表已满，返回true */
bool ListIsFull(const List *plist)
{
    Node *pt;
    bool full;
    pt = (Node *)malloc(sizeof(Node));
    if (pt == NULL)//还可以malloc空间
        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;
}

/*创建储存项的节点，并将其添加至由plist指向的链表末尾（较慢的实现）*/
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; /* pnew放在链表的开头*/
    else
    {
        while (scan->next != NULL)
            scan = scan->next; /*找到链表的末尾*/
        scan->next = pnew;     /*把pnew添加到链表的末尾*/
    }
    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 *psave;
    while (*plist != NULL)
    {
        psave = (*plist)->next; /*保存下一个节点的地址*/
        free(*plist);           /*释放当前节点*/
        *plist = psave;         /*前进至下一个节点*/
    }
}

/*局部函数定义 */
/*把一个项拷贝到节点中*/
static void CopyToNode(Item item, Node *pnode)
{
    pnode->item = item; /*拷贝结构*/
}

接口使用 main

/* films3.c --使用抽象数据类型(ADT）风格的链表*/
/*与list.c一起编译 */
#include <stdio.h>
#include <stdlib.h>/*提供exit()的原型*/
#include "list.h"  /*定义List、Item、只涉及接口、不涉及实现*/
#include <string.h>
void showmovies(Item item);
char *s_gets(char *st, int n);
int main(void)
{
    List movies; // 创建List变量
    Item temp;   // 创建 Item变量

    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;//丢弃剩余字符
        if (AddItem(temp, &movies) == false)//加节点
        {
            fprintf(stderr, "Problem allocating memory\n");
            break;
        }
        if (ListIsFull(&movies))//链表满
        {
            puts("The list is now full.");
            break;
        }
        puts("Enter next movie title (empty line to stop): ");
    }
    /*显示*/
    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);
}
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)                // 如果地址不是NULL，
            *find = '\0';        // 在此处放置一个空字符
        else
            while (getchar() != '\n')
                continue;// 处理输入行的剩余内容
    }
    return ret_val;
}

链表和数组

访问：
数组下标随机访问
链表首节点开始顺序访问

查找特定项：
顺序查找；
排序+顺序查找；
排序+二分查找；(链表不支持)

二叉查找树：频繁增删+频繁查找

插入

队列 ADT

理论

类型名:队列
类型属性:可以储存一系列项、先进先出的链表
类型操作:初始化队列为空
确定队列为空
确定队列已满
确定队列中的项数
在队列末尾添加项
在队列开头删除或恢复项
清空队列

数组队列



链表队列：删除首项时不必移动

.h

/*queue.h-- Queue的接口 */
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include <stdbool.h>//bool
// 在这里插入Item类型的定义，例如
// typedef int Item; // 用于use_q.c
// 或者 typedef struct item {int gumption; int charisma; } Item;
// 
typedef struct item{
long arrive;/*一位顾客加入队列的时间*/
int processtime; /*该顾客咨询时花费的时间*/
}Item;

#define MAXQUEUE 10//队列最大长度
typedef struct node
{
    Item item;
    struct node *next;
} Node;//队列节点
typedef struct queue
{
    Node *front; /*指向队列首项的指针*/
    Node *rear;  /*指向队列尾项的指针*/
    int items;   /*队列中的项数 */
} Queue;//队列

/*操作:初始化队列
前提条件:pq指向一个队列、传地址：修改队列内容、快、节省内存
后置条件:队列被初始化为空*/
void InitializeQueue(Queue * pq) ;

/*操作:检查队列是否已满
前提条件:pq指向之前被初始化的队列、const地址不更改队列内容
后置条件:如果队列已满则返回true，否则返回false*/
bool QueueIsFull(const Queue *pg);

/*操作 : 检查队列是否为空
前提条件 : pq指向之前被初始化的队列
后置条件:如果队列为空则返回true，否则返回false*/
bool QueueIsEmpty(const Queue *pq);

/*操作:确定队列中的项数
前提条件 : pq指向之前被初始化的队列 
后置条件:返回队列中的项数*/
int QueueItemCount(const Queue *pq);

/*操作:在队列末尾添加项
前提条件:pq指向之前被初始化的队列
item是要被添加在队列末尾的项
后置条件:如果队列不为空，item将被添加在队列的末尾，
该函数返回true;否则，队列不改变，该函数返回false */
bool EnQueue(Item item, Queue *pq);

/*操作:从队列的开头删除项
前提条件:pq指向之前被初始化的队列
后置条件:如果队列不为空，队列首端的item 将被拷贝到*pitem中
并被删除，且函数返回true;
如果该操作使得队列为空，则重置队列为空
如果队列在操作前为空，该函数返回false
*/
bool DeQueue(Item *pitem, Queue *pq);

/*操作:清空队列
前提条件:pq指向之前被初始化的队列
后置条件:队列被清空*/
void EmptyTheQueue(Queue *pq);
#endif

.c

/*queue.c -- Queue类型的实现*/
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
/*局部函数*/
static void CopyToNode(Item item, Node *pn);
static void CopyToItem(Node *pn, Item *pi);
void InitializeQueue(Queue *pq)
{
    pq->front = pq->rear = NULL;
    pq->items = 0;
}
bool QueueIsFull(const Queue *pq) { return pq->items == MAXQUEUE; }
bool QueueIsEmpty(const Queue *pq) { return pq->items == 0; }
int QueueItemCount(const Queue *pq) { return pq->items; }
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;
}

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)//删除最后一项、首尾指针重置为NULL
        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

// mall.c-- 使用Queue接口
// 和queue.c一起编译
#include <stdio.h>
#include <stdlib.h> // 提供 rand() 和srand() 的原型
#include <time.h>   // 提供 time() 的原型
#include "queue.h"  // 更改Item的 typedef
#define MIN_PER_HR 60.0
bool newcustomer(double x);   // 是否有新顾客到来 ?
Item customertime(long when); // 设置顾客参数
int main(void)
{ // 顾客排队
    Queue line;
    Item temp;              // 新的顾客数据
    int hours;              // 模拟的小时数
    int perhour;            // 每小时平均多少位顾客
    long cycle, cyclelimit; // 循环计数器、计数器的上限
    long turnaways = 0;     // 因队列已满被拒的顾客数量
    long customers = 0;     // 加入队列的顾客数量
    long served = 0;        // 在模拟期间咨询过Sigmund的顾客数量
    long sum_line = 0;      // 累计的队列总长
    int wait_time = 0;      // 从当前到sigmund空闲所需的时间
    double min_per_cust;    // 顾客到来的平均时间
    long line_wait = 0;     // 队列累计的等待时间

    InitializeQueue(&line);
    srand((unsigned int)time(0)); // rand() 随机初始化
    puts("case study: sigmund Lander's Advice Booth");
    puts("Enter the number of simulation hours: ");
    scanf("%d", &hours);
    cyclelimit = MIN_PER_HR * hours;
    puts("Enter the average number of customers per hour : ");
    scanf("%d", &perhour);
    min_per_cust = MIN_PER_HR / perhour;
    for (cycle = 0; cycle < cyclelimit; cycle++)
    { // 每分钟更新顾客数据
        if (newcustomer(min_per_cust))
        {                           // 新顾客
            if (QueueIsFull(&line)) // 队列满
                turnaways++;
            else
            { // 队列未满
                customers++;
                temp = customertime(cycle);
                EnQueue(temp, &line); // 把顾客到来的时间加入队列
            }
        }
        if (wait_time <= 0 && !QueueIsEmpty(&line))
        {                                 // 队列不为空且队首已结束
            DeQueue(&temp, &line);        // 删除队首
            wait_time = temp.processtime; // 获取新的等待时间
            line_wait += cycle - temp.arrive;
            served++;
        }
        if (wait_time > 0)
            wait_time--;
        sum_line += QueueItemCount(&line);
    }
    if (customers > 0)
    {
        printf("customers accepted: %ld\n", customers);
        printf("customers served: %ld\n", served);
        printf("turnaways:%ld\n", turnaways);
        printf("average queue size: %.2f\n", (double)sum_line / cyclelimit);
        printf("average wait time :8.2f minutes\n", (double)line_wait / served);
    }
    else
        puts("No customers ! ");
    EmptyTheQueue(&line);
    getchar();
    puts("Bye !");

    return 0;
}

// ×是顾客到来的平均时间（单位:分钟)
// 如果1分钟内有顾客到来，则返回true
bool newcustomer(double x)
{
    if (rand() * x / RAND_MAX < 1)
        return true;
    else
        return false;
}
// when是顾客到来的时间
// 该函数返回一个Item结构，该顾客到达的时间设置为when,
// 咨询时间设置为1~3的随机值
Item customertime(long when)
{

    Item cust;
    cust.processtime = rand() % 3 + 1;
    cust.arrive = when;
    return cust;
}

二叉查找树 ADT

理论

节点：项+两个指针（指向左右子节点）
顺序：左节点、父节点、右节点

树顶部称为根、每个节点是后代节点的根
根+左右节点->子树

满二叉树：每一层节点数都是上一层节点数的两倍

查找：判断根，选择左\右子树、每次比较排除半个树
在满员（平衡）时效率最高、不平衡的树查找速度不比链表快
AVL树：创建平衡二叉树的算法

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

.h

/*tree.h-- 二叉查找数 */
/*树中不允许有重复的项*/
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>
/*根据具体情况重新定义 Item*/
#define SLEN 20
typedef struct item
{
    char petname[SLEN];
    char petkind[SLEN];
} Item;
#define MAXITEMS 10
typedef struct trnode
{
    Item item;
    struct trnode *left;  /*指向左分支的指针*/
    struct trnode *right; /*指向右分支的指针*/
} Trnode;
typedef struct tree
{
    Trnode *root; /*指向根节点的指针*/
    int size;     /*树的项数*/
} Tree;
/*函数原型
操作:把树初始化为空
前提条件:ptree指向一个树
后置条件:树被初始化为空*/
void InitializeTree(Tree *ptree);
/*操作:确定树是否为空
前提条件:ptree指向一个树
后置条件:如果树为空，该函数返回true
否则，返回false*/
bool TreeIsEmpty(const Tree *ptree);
/*操作:确定树是否已满
前提条件:ptree指向一个树
后置条件:如果树已满，该函数返回true
否则，返回false*/
bool TreeIsFull(const Tree *ptree);
/*操作:确定树的项数
前提条件:ptree指向一个树
后置条件:返回树的项数*/
int TreeItemCount(const Tree *ptree);
/*加操作 : 在树中添加一个项
前提条件:pi是待添加项的地址
           ptree指向一个已初始化的树
后置条件:如果可以添加，该函数将在树中添加一个项
并返回true;否则，返回false
           */
bool AddItem(const Item *pi, Tree *ptree);
/*操作:在树中查找一个项
前提条件:pi指向一个项
ptree指向一个已初始化的树
后置条件:如果在树中添加一个项，该函数返回true
否则，返回false
*/
bool InTree(const Item *pi, const Tree *ptree);
/*操作:从树中删除一个项
前提条件:pi是删除项的地址
ptree指向一个已初始化的树
后置条件:如果从树中成功删除一个项，该函数返回true
否则，返回false
*/
bool DeleteItem(const Item *pi, Tree *ptree);
/*操作:把函数应用于树中的每一项
前提条件 : ptree指向一个树
pfun指向一个函数，
该函数接受一个Item类型的参数，并无返回值
后置条件:pfun指向的这个函数为树中的每一项执行一次*/
void Traverse(const Tree *ptree, void (*pfun)(Item item));
/*操作:删除树中的所有内容
前提条件 : ptree指向一个已初始化的树
后置条件:树为空*/
void DeleteAll(Tree *ptree);
#endif

.c

删除节点：
关联项和节点DeleteItem+删除节点DeleteNode
1、待删除节点没有子节点：父节点的对应指针重置为NULL、free

2、待删除节点带有一个子节点：父节点的对应指针更新为（待删除节点的）子节点的地址

3、待删除节点带有两个子节点：一个子树（左）连接在被删除节点的位置、另一个（右）子树沿着（左）子树的（右）分支向下找空位

/*tree.c-- 树的支持函数 */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "tree.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;
}
bool InTree(const Item *pi, const Tree *ptree)
{
    return (SeekItem(pi, ptree).child == NULL) ? false : true; // 返回结构、直接.访问成员
}
void Traverse(const Tree *ptree, void (*pfun)(Item item))
{
    if (ptree != NULL)
        Inorder(ptree->root, pfun);
}
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 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 DeleteAll(Tree *ptree)
{//删节点+删树
    if (ptree != NULL)
        DeleteAllNodes(ptree->root);//删节点
    ptree->root = NULL;//删树
    ptree->size = 0;
}


/*局部函数*/
static void Inorder(const Trnode *root, void (*pfun)(Item item))
{ // 左根右递归遍历树
    if (root != NULL)
    {
        Inorder(root->left, pfun);
        (*pfun)(root->item);
        Inorder(root->right, pfun);
    }
}
static bool ToLeft(const Item *i1, const Item *i2)
{
    int comp1;//compl会报错com1不会
    if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
        return true;
    else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0)
        return true;
    else
        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;
    else
        return false;
}
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 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 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 DeleteNode(Trnode **ptr)
{ /* 涉及到修改父节点的左右子树、传递（（指向目标节点的）父节点指针成员的）地址
        *ptr:父节点指针成员 Trnode *
   eg:删除根节点的左节点 传参ptr=*(root->left)、*ptr=root->left、(*ptr)->right=(root->left)->right
   */
    Trnode *temp;
    if ((*ptr)->left == NULL)
    { // 没有左子树

        temp = *ptr; // 记录被删除节点的地址、防止父节点重置后找不到无法free
        *ptr = (*ptr)->right;
        free(temp);
    }
    else if ((*ptr)->right == NULL)
    { // 没有右子树

        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
    else /*被删除的节点有两个子节点*/
    {    /*找到重新连接右子树的位置*/
        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

/*petclub.c --使用二叉查找数*/
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.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");
        }
    }
    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 \nl) show list of pets");
    puts("n) number of pets \nf)find pets");
    puts("d)delete a pet \nq)quit");
    while ((ch = getchar()) != EOF)
    {
        while (getchar() != '\n') /*处理输入行的剩余内容*/
            continue;
        ch = tolower(ch);
        if (strchr("alrfndq", ch) == NULL)
            puts("Please enter an a, l,f, n, 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 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 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 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. in");
}
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)                // 如果地址不是NULL，
            *find = '\0';        // 在此处放置一个空字符
        else
            while (getchar() != '\n')
                continue; // 处理输入行的剩余内容)
    }
    return ret_val;
}