【C Primer Plus第六版 学习笔记】 第十七章 高级数据表示

有基础，进阶用，个人查漏补缺

1. 链表：假设要编写一个程序，让用户输入一年内看过的所有电影，要储存每部影片的片名和评级。

   #include <stdio.h>
   #include <stdlib.h> /* 提供malloc()的原型 */
   #include <string.h>/* 提供strcpy()的原型 */
   #define TSIZE 45     /* 储存片名的数组大小 */struct film {char title[TSIZE];int rating;struct film * next;/*指向链表的下一个结构*/
   };
   char * s_gets(char str[], int n);
   int main(void)
   {struct film * head =NULL;struct film * prev, * current;char input[TSIZE];//使用临时存储区获取用户输入的电影名/*收集并储存信息*//*1. 创建链表：a. 使用malloc()为结构分配足够的空间b. 储存结构的地址c. 把当前信息拷贝到结构中*/puts("Enter first movie title:");//如果用户通过键盘模拟EOF或输入一行空行，将退出该while循环while (s_gets(input, TSIZE) != NULL && input[0] != '\0'){//如果用户进行输入，程序就分配一个结构的空间，并将其地址赋给指针变量current//链表中第1个结构的地址应储存在指针变量中head//随后每个结构的地址应储存在前一个结构的next成员中（prev->next）current = (struct film *) malloc(sizeof(struct film));//返回一个指针，返回已经分配大小的内存，分配失败则返回NULLif (head == NULL)//head初始化为NULL，本if即在最开始的时候给头指针分配空间（第1个结构）head = current;else					//后续的结构prev->next = current;//把next设置为NULL，表明当前结构是链表的最后一个结构current->next  = NULL;//由于s_gets()限制了只能输入TSIZE-1个字符，所以用strcpy()函数把input数组中的字符串拷贝到title成员很安全//strcpy()无法检查第一个数组是否能容纳第2个数组，可能导致溢出问题strcpy(current->title, input);//把input所指向的字符串复制到current->title，返回current->title地址puts("Enter your rating<1-10>:");scanf("%d", &current->rating);while(getchar() != '\n')continue;puts("Enter next movie title (empty line to stop):");//最后要为下一次输入做好准备，尤其是要设置prev指向当前结构，//因为在用户输入下一部电影且程序为新结构分配空间后，当前结构将成为新结构的上一个结构，//所以程序在循末尾应该这样设置指针:prev = current;}/*显示电影列表*//*2.显示链表*/if (head == NULL)printf("No data entered.");else printf("Here is the movie list:\n");/*显示链表从指向第一个结构的指针开始*/current = head;while (current != NULL){printf("Movie: %s Rating: %d\n", current->title, current->rating);//根据储存在该结构中next成员中的信息，重新设置current指针指向链表中的下一个结构//问：遍历链表时，为何不直接使用head指针，而要重新创立一个新指针current？//答：因为如果使用head，会改变head中的值，程序就找不到列链表的开始处current = current->next;}/*完成任务，释放已经分配的内存*//*3. 释放内存*/current = head;while (current != NULL){current = head;head = current->next;free(current);}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)*find = '\0';elsewhile(getchar() != '\n')continue;}return ret_val;
   }
   

   1. 创建链表：
      1. 使用malloc()为结构分配足够的空间
      2. 储存结构的地址
      3. 把当前信息拷贝到结构中
      4. 创建链表流程：

         1. 对头指针：
            
            
            
            
            

         2. 对接下来的指针：

   
   
   
   
   

   2. 显示链表

      
      

2. 抽象数据类型

   1. 抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。
   2. 如何理解？
      1. 抽象数据类型 = 逻辑结构+数据运算。逻辑结构不涉及数据在计算机中具体的实现和存储，这些操作是由存储结构决定的，这就是说，抽象数据类型只需考虑问题本身即可。
      2. 类型是指一类数据。基本数据类型一般就是整形、浮点型、以及字符型。抽象数据类型是由若干基本数据类型归并之后形成的一种新的数据类型，这种类型由用户定义，功能操作比基本数据类型更多，一般包括结构体和类。
      3. 抽象数据类型是在在不涉及具体的，和计算机系统相关的细节情况下，优先理解问题本身，在此基础上，实现用计算机求解问题的过程。这就是使用抽象数据类型的目的。
   3. 我自己的理解就是，全都用自定义的函数表示，不把其中实现的细节全都写出来，更注重实现的逻辑
   4. 注意保持纯正的ADT：定义ADT接口后，应该只使用接口函数处理数据类型
   5. 举例：建立抽象、建立接口（头文件声明函数）、使用接口（调用这些函数）、实现接口（函数具体实现代码）

      1. 建立抽象（以链表为例）

         类型名：链表
         类型属性：可以储存一系列项
         类型操作：初始化链表为空确定链表为空确定链表已满确定链表中的项数在链表末尾添加项遍历链表，处理链表中的项清空链表
         

      2. 建立接口（头文件）

         #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;/*函数原型*//*操作：		初始化一个链表*/
         /*前提条件：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 */
         

      3. 使用接口（调用这些函数）

         通过以下伪代码方案进行接口的使用。

         创建一个list类型的变量。
         创建一个item类型的变量。
         初始化链表为空。
         当链表未满且有输入时：把输入读取到item类型的变量中。在链表末尾添加项。
         访问链表中的每一个项，并显示它们。
         

         代码如下：

         /* films3.c -- using an ADT-style linked list */
         /* compile with list.c                        */
         #include <stdio.h>
         #include <stdlib.h>    /* prototype for exit() */
         #include "list.h"      /* defines List, Item   */
         void showmovies(Item item);
         char * s_gets(char * st, int n);
         int main(void)
         {List movies;Item temp;/* initialize       */InitializeList(&movies);if (ListIsFull(&movies)){fprintf(stderr,"No memory available! Bye!\n");exit(1);}/* gather and store */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):");}/* display          */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));/* clean up         */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');   // look for newlineif (find)                  // if the address is not NULL,*find = '\0';          // place a null character thereelsewhile (getchar() != '\n')continue;          // dispose of rest of line}return ret_val;
         }
         

      4. 实现接口（函数的具体实现代码）

         #include <stdio.h>
         #include <stdlib.h>
         #include "list.h"/*局部函数原型*/
         static void CopyToNode(Item item, Node *pnode);/*接口函数*//*操作：		初始化一个链表*/
         /*前提条件：plist指向一个链表*/
         /*后置条件：链表初始化为空	*/
         void InitializeList(List *plist)
         {*plist = NULL;
         }/*操作：	 确定链表是否为空定义，plist 指向一个已初始化的链表					*/
         /* 后置条件：	如果链表为空，该函数返回 true；否则返回 false						*/
         bool ListIsEmpty(const List * plist)
         {if(*plist == NULL)return true;elsereturn false;
         }**/*感觉这个函数有错*/**
         /* 操作：		确定链表是否已满，plist 指向一个已初始化的链表						*/
         /* 后置条件：	如果链表已满，该函数返回 true；否则返回 false						*/
         bool ListIsFull(const List * plist)
         {Node *pt;bool full;pt = (Node *)malloc(sizeof(Node));if (pt == NULL)full = true;elsefull = false;free(pt);return full;
         }/* 操作：		确定链表中的项数，plist 指向一个已初始化的链表						*/	
         /* 后置条件：	该函数返回链表的项数												*/
         unsigned int ListItemCount(const List * plist);
         {unsigned int count = 0;Node *pnode = *plist;//设置链表的开始while (pnode != NULL){++count;pnode = pnode->next;//设置下一个节点}return count;
         }/* 操作：		在链表的末尾添加项（较慢的实现）										*/	
         /* 前提条件：	Item 是一个待添加至链表的项，plist 指向一个已初始化的链表*/
         /* 后置条件：	如果可以，该函数在链表末尾添加一个项，且返回 true；否则返回 false*/
         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;}/* 操作：		把函数作用与链表的每一个项											*/	
         /*				plist 指向一个已初始化的链表										*/
         /*				pfun 指向一个函数，该函数接受一个 Item 类型的参数，且无返回值		*/	
         /* 后置条件：	pfun 指向的函数作用于链表中的每一项一次								*/
         void Traverse(const List * plist, void(*pfun)(Item item))
         {Node * pnode = *plist;//设置链表的开始while (pnode != NULL){(*pfun)(pnode->item);//把函数应用于链表中的项pnode = pnode->next;//前进到下一项}
         }/* 操作：		释放已分配的内存（如果有的话）										*/
         /*				plist 指向一个已初始化的链表										*/
         /* 后置条件：	释放了为链表分配的所有内存，链表设置为空							*/
         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;
         }
         

         提示：const的限制

         多个处理链表的函数，都把const List plist作为形参，表明这些函数不会更改链表。这里const确实提供了一些保护。它防止了plist（即plist所指向的量）被修改。在该程序中plist指向movies，所以const防止了这些函数修改movies。因此在ListItemCount()中不允许有类似以下的代码：

         *plist = (*plist)->next;
         

         (*plist)->next和plist->next的区别

         因为改变*plist就改变了movies，将导致程序无法跟踪数据。然而，plist和movies都被看作是const并不意味着plist或movies指向的数据是const。

         例如，可以编写下面的代码

         (*plist)->item.rating = 3;//即使*plist是const，也可以这样做
         

         因为上面的代码并未改变plist*，它改变的是*plist指向的数据。由此可见，不要指望const能捕获到意外修改数据的程序错误。

      5. 简而言之，上述程序是根据待解决的问题来表达程序，而不是根据解决问题所需的具体工具来表达程序。ADT版本可读性更高，而且针对的是最终的用户所关心的问题。

3. 队列ADT

   • 队列( queue）是具有两个特殊属性的链表
     1. 新项只能添加到链表的末尾。从这方面看，队列与简单链表类似
     2. 只能从链表的开头移除项。可以把队列想象成排队买票的人。你从队尾加入队列，买完票后从队首离开。队列是一种“先进先出”( first in , first out，缩写为FIFO）的数据形式，就像排队买票的队伍一样（前提是没有人插队)。

   1. 定义队列抽象类型

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

   2. 定义接口（queue.h）

      现在假定已经使用c的typedef 工具创建两个类型名: Item和 Queue这些类型，着重考虑函数的原型。

      1. 首先，考虑初始化

         这涉及改变Queue类型，所以该函数应该以Queue的地址作为参数

         void InitializeQueue (Queue * pq);
         

      2. 接下来，确定队列是否为空或已满的函数，应返回真或假值

         由于该函数不更改队列，所以接受Queue类型的参数。

         但是，传递Queue的地址更快，更节省内存，这取决于Queue类型的对象大小。这样做的好处是，所有的函数都以地址作为参数，而不像List 示例那样。

         为了表明这些函数不更改队列，可以且应该使用const限定符：

         bool QueueIsFull(const Queue * pq);
         bool QueueIsEmpty (const Queue * pq);
         

      3. 指针pq指向Queue数据对象，不能通过pq这个代理更改数据。可以定义一个类似该函数的原型，返回队列的项数：

         int QueueItemCount (const Queue * pq);
         

      4. 在队列末尾添加项涉及标识项和队列

         这次要更改队列，所以必须使用指针。该函数的返回类型可以是void，或者通过返回值来表示是否成功添加项：

         bool EnQueue (Item item, Queue * pq) ;
         

      5. 最后，删除项有多种方法

         如果把项定义为结构或一种基本类型，可以通过函数返回待删除的项。函数的参数可以是Queue类型或指向Queue 的指针。

         因此，可能是下面这样的原型:

         Item DeQueue (Queue q);
         

         然而，下面的原型会更合适一些：

         bool DeQueue (Item * pitem, Queue * pq) ;
         

         从队列中待删除的项储存在pitem 指针指向的位置，函数的返回值表明是否删除成功

      6. 清空队列的函数所需的唯一参数是队列的地址，可以使用下面的函数原型：

         void EmptyTheQueue (Queue * pq);
         

      7. 在队列末尾添加项，涉及标识项和队列

         这次要更改队列，所以必须使用指针

         该函数的返回类型可以是void，或者通过返回值来表示是否成功添加项

         bool EnQueue (Item item, Queue * pq) ;
         

      总代码

      #ifndef _QUEUE_H_
      #define _QUEUE_H_
      #include <stdbool.h>//在这里插入Item类型的定义，例如
      typedef int Item;  //用于use_q.c
      //或者
      //typedef struct item {int gumption; int charisma;} Item;#define MAXQUEUE 10typedef struct node
      {Item item;struct node * next;
      } Node;typedef struct queue
      {Node * front;  /* 指向队列首项的指针 */Node * rear;   /* 指向队列尾项的指针 */int items;     /* 队列中的项数 */
      } Queue;/*操作:初始化队列*/
      /*前提条件:pq指向一个队列*/
      /*后置条件:队列被初始化为空*/
      void InitializeQueue (queue * pq);/*操作:检查队列是否已满*/
      /*前提条件:pq指向之前被初始化的队列*/
      /*后置条件:如果队列已满则返回true，否则返回false*/
      bool QueueIsFul1(const Queue * pq);/*操作:检查队列是否为空*/
      /*前提条件:pq指向之前被初始化的队列*/
      /*后置条件:如果队列为空则返回true，否则返回false*/
      bool QueueIsErmpty (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
      

   3. 实现接口数据表示（queue.c）

      #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;
      }/*把项添加到队列中，包括以下几个步骤:
      （1）创建一个新节点;
      （2）把项拷贝到节点中;
      （3）设置节点的next指针为NULL，表明该节点是最后一个节点;
      （4）设置当前尾节点的next指针指向新节点，把新节点链接到队列中;
      （5）把rear指针指向新节点，以便找到最后的节点;
      （6）项数加1。
      函数还要处理两种特殊情况。
      （1）如果队列为空，应该把front指针攻置为指问新节点。因为如果队列中只有一个节点，那么这个节点既是首节点也是尾节点。
      （2）如果函数不能为节点分配所需内存，则必须执行一些动作。因为大多数情况下我们都使用小型队列，这种情况很少发生。所以，如果程序运行的内存不足，我们只是通过函数终止程序。*/
      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;//设置节点的next指针为NULL，表明该节点是最后一个节点if (QueueIsEmpty(pq))pq->front = pnew;           /* 项位于队列顶端*/else//设置当前尾节点的next指针指向新节点，把新节点链接到队列中pq->rear->next = pnew; //把rear指针指向新节点，以便找到最后的节点 pq->rear = pnew;                /* 记录队列尾端的位置 */pq->items++;                    /* 队列项数+1 */return true;
      }/*从队列的首端删除项，涉及以下几个步骤:
      （1）把项拷贝到给定的变量中;
      （2）释放空出的节点使用的内存空间;
      （3）重置首指针指向队列中的下一个项;
      （4）项数减1;
      （5）如果删除最后一项，把首指针和尾指针都重置为NULL。
      注意：
      （1）删除最后一项时，代码中并未显式设置front 指针为NULL，因为已经设置front 指针指向被删除节点的next指针。如果该节点不是最后一个节点，那么它的next 指针就为NULL。
      （2）代码使用临时指针(pt)储存待删除节点的位置。因为指向首节点的正式指针(pt->front)被重置为指向下一个节点，所以如果没有临时指针，程序就不知道该释放哪块内存。
      */
      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--;//项数减1if (pq->items == 0)pq->rear = NULL;//如果删除最后一项，把首指针和尾指针都重置为NULLreturn true;
      }/* empty the queue                */
      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;
      }
      

      【C语言】pq-＞rear-＞next = pnew与pq-＞rear = pnew

   4. 测试队列

      /* use_q.c -- driver testing the Queue interface */
      /* compile with queue.c                          */
      #include <stdio.h>
      #include "queue.h"  /* defines Queue, Item       */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')   /* ignore other input */continue;if ( ch == 'a'){printf("Integer to add: ");scanf("%d", &temp);if (!QueueIsFull(&line)){printf("Putting %d into queue\n", temp);EnQueue(temp,&line);}elseputs("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;
      }
      

4. 链表和数组

   1. 比较数组和链表

      数据形式	优点	缺点
      数组	C直接支持
      提供随机访问	在编译时确定大小
      插入和删除元素很费时
      链表	运行时确定大小
      快速插入和删除元素	不能随机访问
      用户必须提供编程支持

      
      

   2. 如何访问元素

      1. 对数组而言，可以使用数组下标直接访问该数组中的任意元素，这叫做随机访问（random access)。
      2. 对链表而言，必须从链表首节点开始，逐个节点移动到要访问的节点，这叫做顺序访问( sequential access)。
      3. 当然，也可以顺序访问数组。只需按顺序递增数组下标即可。
      4. 假设要查找链表中的特定项。一种算法是从列表的开头开始按顺序查找，这叫做顺序查找(sequentialsearch)。如果项并未按某种顺序排列，则只能顺序查找。如果待查找的项不在链表里，必须查找完所有的项才知道该项不在链表中（在这种情况下可以使用并发编程，同时查找列表中的不同部分)。

   3. 总结：

      1. 如果因频繁地插入和删除项导致经常调整大小，而且不需要经常查找——链表
      2. 如果只是偶尔插入或删除项，但是经常进行查找——数组

5. 二叉查找树：如果需要一种既支持频繁插入和删除项，又支持频繁查找的数据形式，数组和链表都无法胜任。这种情况下应该选择二叉查找树。

6. 二叉树ADT

   1. 非正式的树定义

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

   2. 接口（头文件）

      原则上，可以用多种方法实现二叉查找树，甚至可以通过操控数组下标用数组来实现。

      但是，实现二叉查找树最直接的方法是通过指针动态分配链式节点。

      因此我们这样定义：

      typedef SOMETHING Item;
      typedef struct trnode{Item item;struct trnode * left;struct trnode * right;
      }Trn;typedef struct tree(Trnode * root;int size;
      }Tree;
      

      tree.h

      #ifndef _TREE_H_
      #define _TREE_H_
      #include <stdbool.h>**//建立接口第一步：描述如何表示数据**
      #define SLEN 20
      typedef struct item {char petname[SLEN];//宠物名char petkind[SLEN];//宠物种类
      } Item;//将item结构重命名为Item#define MAXITEMS 10//最大项数
      typedef struct trnode {Item item;//包含一个item结构struct trnode * left;//指向左子树的指针struct trnode * right;//指向右子树的指针
      } Trnode;//将trnode结构重命名为Trnodetypedef struct tree {Trnode * root;//指向根的指针int size;//树的项数
      } Tree;//将tree结构重命名为Tree，tree结构就是一个树**//建立接口第二步：描述实现ADT操作的函数**/*操作：把树初始化为空前提条件：ptree指向一个树后置条件：树被初始化为空*/
      void InitializeTree(Tree * ptree);/*操作：确定树是否已满前提条件：ptree指向一个已初始化的树后置条件：如果树已满，函数返回true，否则函数返回false*/
      bool TreeIsFull(const Tree * ptree);/*操作：确定树是否为空前提条件：ptree指向一个已初始化的树后置条件：如果树为空，函数返回true，否则函数返回false*/
      bool TreeIsEmpty(const Tree * ptree);/*操作：确定树的项数前提条件：ptree指向一个已初始化的树后置条件：返回树的项数*/
      int TreeItemCount(const Tree * ptree);/*操作：在树中添加一个项前提条件：ptree指向一个已初始化的树，pi是待添加项的地址后置条件：如果可以添加，该函数将在树中添加一个项，并返回true，否则返回false*/
      bool AddItem(const Item * pi, Tree * ptree);/*操作：在树中查找一个项前提条件：ptree指向一个已初始化的树，pi指向一个项后置条件：如果在树中找到该项，函数返回true，否则函数返回false*/
      bool InTree(const Item * pi, const Tree * ptree);/*操作：在树中删除一个项前提条件：ptree指向一个已初始化的树，pi是删除项的地址后置条件：如果从树中成功删除一个项，函数返回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
      

   3. 接口实现

      注释来自https://blog.csdn.net/m0_46655998/article/details/105227533

      前面的函数比较简单

      #include<stdio.h>//包含fprintf函数的头文件
      #include<stdlib.h>//包含malloc函数、free函数和exit函数的头文件
      #include<string.h>//包含strcmp函数的头文件
      #include "tree.h"//包含外部定义头文件typedef struct pair {Trnode * parent;//指向父节点的指针Trnode * child;//指向子节点的指针
      } Pair;//将pair结构重命名为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 Pair SeekItem(const Item * pi, const Tree * ptree);
      static void DeleteNode(Trnode ** ptr);
      static void InOrder(const Trnode * root, void (*pfun) (Item item));
      static void DeleteAllNode(Trnode * root);//接口函数，供外部调用
      void InitializeTree(Tree * ptree)//传入指向树的指针
      {ptree -> root = NULL;//将指向根的指针初始化为NULLptree -> size = 0;//将树的项数初始化为0
      }bool TreeIsFull(const Tree * ptree)
      {return ptree -> size == MAXITEMS;//当树的项数等于最大值时返回true
      }bool TreeIsEmpty(const Tree * ptree)
      {return ptree -> size == 0;//当树的项数等于0时返回true
      }int TreeItemCount(const Tree * ptree)
      {return ptree -> size;//返回树的项数
      }
      

      着重介绍下面的函数

      1. 添加项 AddItem(const Item * pi, Tree * ptree)
         1. 在树中添加一个项，首先要检查该树是否有空间放得下一个项——TreeIsFull()
         2. 由于我们定义二叉树时规定其中的项不能重复，所以接下来要检查树中是否有该项——SeekItem()
         3. 通过这两步检查后，便可创建一个新节点，把待添加项拷贝到该节点中，并设置节点的左指针和右指针都为NULL。这表明该节点没有子节点。
         4. 然后，更新Tree结构的size成员，统计新增了一项。
         5. 接下来，必须找出应该把这个新节点放在树中的哪个位置。如果树为空，则应设置根节点指针指向该新节点。否则，遍历树找到合适的位置放置该节点。
         6. AddItem ()函数就根据这个思路来实现，并把一些工作交给几个尚未定义的函数: SeekItem ()、MakeNode ()和AddNode ( )。

      bool AddItem(const Item * pi, Tree * ptree)//指向item结构的指针和指向树的指针
      {Trnode * new_node;//定义一个trnode结构变量if(TreeIsFull(ptree))//当树的项数已满时无法添加新项{//fprintf()函数的作用是将格式化的数据打印到流中//stdout是标准的输出流，而stderr是标准的错误输出流//stdout和stderr的类型都是FILE*，在stdio.h中定义//默认情况下，stdout和stderr中的数据都会被打印到屏幕上fprintf(stderr, "Tree is full\n");//报告错误return false;}if(SeekItem(pi, ptree).child != NULL)//如果树中已经存在此项时{fprintf(stderr, "Attempted to add duplicate item\n");//报告错误return false;//返回false，因为树中不能包含重复的项}new_node = MakeNode(pi);//为新项分配内存if(new_node == NULL)//如果分配内存失败，报告错误，返回false{fprintf(stderr, "Couldn't create node\n");return false;}ptree -> size++;//项数+1if(ptree -> root == NULL)//如果根节点为空，将新项作为根节点ptree -> root = new_node;elseAddNode(new_node, ptree -> root);//否则，将新项添加到合适的位置return true;
      }//pi指向待查找项，ptree指向二叉树
      static Pair SeekItem(const Item * pi, const Tree * ptree)
      {Pair look;//定义一个包含指向父节点和子节点的指针的结构look.parent = NULL;//将父节点赋值为NULLlook.child = ptree -> root;//子节点指向树的根节点if(look.child == NULL)//如果子节点为NULL，说明树的根节点为空，返回falsereturn look;while(look.child != NULL)//循环直到节点后无子节点{//比较child所指节点的item成员和待查找的item结构，如果待查找项在该节点左边if(ToLeft(pi, &(look.child -> item))){look.parent = look.child;//将子节点的指针赋给父节点look.child = look.child -> left;//子节点指向其左子树}else if(ToRight(pi, &(look.child -> item)))//比较child所指节点的item成员和待查找的item结构，如果待查找项在该节点右边{look.parent = look.child;//将子节点的指针赋给父节点look.child = look.child -> right;//子节点的指针指向其右子树}else//如果待查找项和child所指节点的item成员相同，跳出循环，此时look.parent指向待查找项所在节点的父节点，look.child指向待查找项所在节点break;}return look;//返回look结构
      }//子节点是否排在父节点左边
      static bool ToLeft(const Item * i1, const Item * i2)
      {int comp1;//根据strcmp函数的机制，如果字符串1在字符串2前面，函数返回负数，否则返回正数，//也就是说当子节点应排在父节点左边时，ToLeft函数返回trueif((comp1 = strcmp(i1 -> petname, i2 -> petname)) < 0)return true;//当名字相同时，比较种类，当i1的种类名应排在i2种类名之前时，返回trueelse if(comp1 == 0 && strcmp(i1 -> petkind, i2 -> petkind) < 0)return true;elsereturn false;//其余情况，返回false
      }//子节点是否排在父节点右边
      static bool ToRight(const Item * i1, const Item * i2)
      {int comp1;//当字符串1在字符串2后面时，strcmp函数返回正数，//即子节点应排在父节点右边时，ToRight函数返回trueif((comp1 = strcmp(i1 -> petname, i2 -> petname)) > 0)return true;//当名字相同时，比较种类，当i1的种类名应排在i2种类名之后时，返回trueelse if(comp1 == 0 && strcmp(i1 -> petkind, i2 -> petkind) > 0)return true;elsereturn false;//其余情况，返回false
      }static Trnode * MakeNode(const Item * pi)Trnode * new_node;new_node = (Trnode *) malloc(sizeof(Trnode));//请求系统分配一个trnode结构的内存if(new_node != NULL)//如果分配内存成功{new_node -> item = *pi;//将pi所指向的item结构的数据赋给trnode结构成员itemnew_node -> left = NULL;//将结构成员left和right赋值为NULL，表示其后没有子节点new_node -> right = NULL;}return new_node;//返回该trnode结构的地址
      }static void AddNode(Trnode * new_node, Trnode * root)//传入两个指向trnode结构的指针，new_node指向待添加的项，root指向二叉树中本来的项（即一个节点）
      {if(ToLeft(&new_node -> item, &root -> item))//将new_node所指结构的item成员与root所指节点的item成员作比较，如果返回为true，new_node所指结构应属于root所指节点的左子树{if(root -> left == NULL)//如果root所指节点没有左子树，那么就将new_node所指结构作为root所指节点的左子节点root -> left = new_node;else//如果root所指节点有左子节点AddNode(new_node, root -> left);//递归调用，传入new_node和指向root所指节点的左子节点的指针，直到最后root -> left == NULL或者root -> right == NULL}else if(ToRight(&new_node -> item, &root -> item))//将new_node所指结构的item成员与root所指节点的item成员作比较，如果返回为true，new_node所指结构应属于root所指节点的右子树{if(root -> right == NULL)//如果root所指节点没有右子树，那么就将new_node所指结构作为root所指节点的右子节点root -> right = new_node;else//如果root所指节点有右子节点AddNode(new_node, root -> right);//递归调用，传入new_node和指向root所指节点的右子节点的指针，直到最后root -> left == NULL或者root -> right == NULL}else//当以上两种情况都不符合时，说明new_node所指结构的item成员和root所指节点的item成员相同，程序报告错误，并退出{fprintf(stderr, "location error in Addnode()\n");exit(1);}
      }//查找树中是否包含此项，如果包含，SeekItem(pi, ptree).child != NULL，返回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)//没有找到，返回falsereturn false;if(look.parent == NULL)//如果look.parent == NULL，说明项在根节点，删除根节点DeleteNode(&ptree -> root);else if(look.parent -> left == look.child)//如果待删除的项是其父节点的左子节点DeleteNode(&look.parent -> left);//传入的是待删除节点的父节点的left指针的地址，简单来说就是传入指向待删除节点的指针的地址elseDeleteNode(&look.parent -> right);//如果待删除的项是其父节点的右子节点ptree -> size--;//项数-1return true;
      }static void DeleteNode(Trnode ** ptr)//传入的是指向指针（该指针指向一个trnode结构，即一个节点，该节点为待删除节点）的指针
      {Trnode * temp;//定义一个指向trnode结构的指针if((*ptr) -> left == NULL)//如果待删除节点没有左子节点{temp = *ptr;//将待删除节点的地址保存到临时指针temp中*ptr = (*ptr) -> right;//将待删除节点的rignt赋给指向待删除节点的指针，现在*ptr指向待删除节点的右子节点free(temp);//释放待删除节点的内存}else if((*ptr) -> right == NULL)//如果待删除节点没有右子节点{temp = *ptr;//将待删除节点的地址保存到临时指针temp中*ptr = (*ptr) -> left;//将待删除节点的left成员赋给指向待删除节点的指针，现在*ptr指向待删除节点的左子节点free(temp);//释放待删除节点的内存}//当待删除节点既没有左子节点，又没有右子节点时，首先判断其没有左子节点，然后将*ptr指向待删除节点的右子节点，由于待删除节点的right为NULL//所以指向待删除节点的指针变为NULLelse//当待删除节点左右两个子节点都有时{for(temp = (*ptr) -> left; temp -> right != NULL; temp = temp -> right)//初始化条件为temp指向待删除节点的左子节点，更新循环时每循环一次temp就指向其所指节点的//右子节点，测试条件为temp所指节点后无右子节点continue;//当退出for循环时，temp指向的是待删除节点的左子树中最右侧的子节点temp -> right = (*ptr) -> right;//将待删除节点的右子树移动到temp节点的右子节点（注意是将整个右子树移动）temp = *ptr;//将待删除节点的数据保存到temp中*ptr = (*ptr) -> left;//将待删除节点的左子节点移动到待删除节点的位置，也就是说原本指向待删除节点的指针现在指向待删除节点的左子节点free(temp);//释放待删除节点的内存}
      }void Traverse(const Tree * ptree, void (*pfun) (Item item))
      {if(ptree != NULL)//树不是空树InOrder(ptree -> root, pfun);//传入指向根节点的指针，按照顺序打印节点信息
      }static void InOrder(const Trnode * root, void (*pfun) (Item item))//传入指向节点的指针，以及一个函数指针，该函数接受一个item结构，无返回
      {if(root != NULL)//指向节点的指针不为NULL，即节点存在，不为空{InOrder(root -> left, pfun);//递归1(*pfun)(root -> item);InOrder(root -> right, pfun);//递归2//上面三条语句包含2个递归调用，其原理为递归1语句逐步递进，直到最左端的左子节点，其后无左子节点，条件不符合，逐步向根节点回归，回归归过程中(*pfun)(root -> item)//打印每个节点的信息，而递归2语句在递归1回归过程中递进，判断每个节点后是否有右子节点，如果有，递归1递进，判断该右子节点其后是否有左子节点，如果没有，//递归1回归，打印右子节点的信息，就这样逐步返回到根节点，同样，根节点的右子树也是这样操作，先打印右子树的所有左子节点，再打印右子节点}
      }void DeleteAll(Tree * ptree)
      {if(ptree != NULL)//树不是空树DeleteAllNode(ptree -> root);//按顺序删除节点ptree -> root = NULL;//将指向树根节点的指针赋值为NULL，表明是空树ptree -> size = 0;//树的项数变为0
      }static void DeleteAllNode(Trnode * root)//传入指向节点的指针
      {Trnode * pright;//指向trnode结构的指针if(root != NULL)//节点不为空{pright = root -> right;//这段代码和递归调用类似，//也是从最底端的节点开始释放，坚持先左节点后右节点的原则DeleteAllNode(root -> left);free(root);DeleteAllNode(pright);}
      }