网站建设销售实习,成品网站nike源码免费,网站怎么容易被百度收录,网站怎么做看起来好看有基础#xff0c;进阶用#xff0c;个人查漏补缺 链表#xff1a;假设要编写一个程序#xff0c;让用户输入一年内看过的所有电影#xff0c;要储存每部影片的片名和评级。 #include stdio.h
#include stdlib.h /* 提供malloc()的原型 */
#include s…有基础进阶用个人查漏补缺 链表假设要编写一个程序让用户输入一年内看过的所有电影要储存每部影片的片名和评级。 #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-nextcurrent (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 rating1-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;
}创建链表 使用malloc()为结构分配足够的空间储存结构的地址把当前信息拷贝到结构中创建链表流程 对头指针 对接下来的指针 显示链表 抽象数据类型 抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型需要通过固有数据类型高级编程语言中已实现的数据类型来实现。对一个抽象数据类型进行定义时必须给出它的名字及各运算的运算符名即函数名并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现程序设计中就可以像使用基本数据类型那样十分方便地使用抽象数据类型。如何理解 抽象数据类型 逻辑结构数据运算。逻辑结构不涉及数据在计算机中具体的实现和存储这些操作是由存储结构决定的这就是说抽象数据类型只需考虑问题本身即可。类型是指一类数据。基本数据类型一般就是整形、浮点型、以及字符型。抽象数据类型是由若干基本数据类型归并之后形成的一种新的数据类型这种类型由用户定义功能操作比基本数据类型更多一般包括结构体和类。抽象数据类型是在在不涉及具体的和计算机系统相关的细节情况下优先理解问题本身在此基础上实现用计算机求解问题的过程。这就是使用抽象数据类型的目的。 我自己的理解就是全都用自定义的函数表示不把其中实现的细节全都写出来更注重实现的逻辑注意保持纯正的ADT定义ADT接口后应该只使用接口函数处理数据类型举例建立抽象、建立接口头文件声明函数、使用接口调用这些函数、实现接口函数具体实现代码 建立抽象以链表为例 类型名链表
类型属性可以储存一系列项
类型操作初始化链表为空确定链表为空确定链表已满确定链表中的项数在链表末尾添加项遍历链表处理链表中的项清空链表建立接口头文件 #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 */使用接口调用这些函数 通过以下伪代码方案进行接口的使用。 创建一个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;
}实现接口函数的具体实现代码 #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能捕获到意外修改数据的程序错误。 简而言之上述程序是根据待解决的问题来表达程序而不是根据解决问题所需的具体工具来表达程序。ADT版本可读性更高而且针对的是最终的用户所关心的问题。 队列ADT 队列( queue是具有两个特殊属性的链表 新项只能添加到链表的末尾。从这方面看队列与简单链表类似只能从链表的开头移除项。可以把队列想象成排队买票的人。你从队尾加入队列买完票后从队首离开。队列是一种“先进先出”( first in , first out缩写为FIFO的数据形式就像排队买票的队伍一样前提是没有人插队)。 定义队列抽象类型 类型名: 队列
类型属性:可以储存一系列项
类型操作:初始化队列为空确定队列为空确定队列已满确定队列中的项数在队列末尾添加项在队列开头删除或恢复项清空队列定义接口queue.h 现在假定已经使用c的typedef 工具创建两个类型名: Item和 Queue这些类型着重考虑函数的原型。 首先考虑初始化 这涉及改变Queue类型所以该函数应该以Queue的地址作为参数 void InitializeQueue (Queue * pq);接下来确定队列是否为空或已满的函数应返回真或假值 由于该函数不更改队列所以接受Queue类型的参数。 但是传递Queue的地址更快更节省内存这取决于Queue类型的对象大小。这样做的好处是所有的函数都以地址作为参数而不像List 示例那样。 为了表明这些函数不更改队列可以且应该使用const限定符 bool QueueIsFull(const Queue * pq);
bool QueueIsEmpty (const Queue * pq);指针pq指向Queue数据对象不能通过pq这个代理更改数据。可以定义一个类似该函数的原型返回队列的项数 int QueueItemCount (const Queue * pq);在队列末尾添加项涉及标识项和队列 这次要更改队列所以必须使用指针。该函数的返回类型可以是void或者通过返回值来表示是否成功添加项 bool EnQueue (Item item, Queue * pq) ;最后删除项有多种方法 如果把项定义为结构或一种基本类型可以通过函数返回待删除的项。函数的参数可以是Queue类型或指向Queue 的指针。 因此可能是下面这样的原型: Item DeQueue (Queue q);然而下面的原型会更合适一些 bool DeQueue (Item * pitem, Queue * pq) ;从队列中待删除的项储存在pitem 指针指向的位置函数的返回值表明是否删除成功 清空队列的函数所需的唯一参数是队列的地址可以使用下面的函数原型 void EmptyTheQueue (Queue * pq);在队列末尾添加项涉及标识项和队列 这次要更改队列所以必须使用指针 该函数的返回类型可以是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实现接口数据表示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 测试队列 /* 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;
}链表和数组 比较数组和链表 数据形式优点缺点数组C直接支持提供随机访问在编译时确定大小插入和删除元素很费时链表运行时确定大小快速插入和删除元素不能随机访问用户必须提供编程支持 如何访问元素 对数组而言可以使用数组下标直接访问该数组中的任意元素这叫做随机访问random access)。对链表而言必须从链表首节点开始逐个节点移动到要访问的节点这叫做顺序访问( sequential access)。当然也可以顺序访问数组。只需按顺序递增数组下标即可。假设要查找链表中的特定项。一种算法是从列表的开头开始按顺序查找这叫做顺序查找(sequentialsearch)。如果项并未按某种顺序排列则只能顺序查找。如果待查找的项不在链表里必须查找完所有的项才知道该项不在链表中在这种情况下可以使用并发编程同时查找列表中的不同部分)。 总结 如果因频繁地插入和删除项导致经常调整大小而且不需要经常查找——链表如果只是偶尔插入或删除项但是经常进行查找——数组 二叉查找树如果需要一种既支持频繁插入和删除项又支持频繁查找的数据形式数组和链表都无法胜任。这种情况下应该选择二叉查找树。 二叉树ADT 非正式的树定义 类型名:二叉查找树
类型属性:二叉树要么是空节点的集合空树)要么是有一个根节点的节点集合每个节点都有两个子树叫做左子树和右子树每个子树本身也是一个二叉树也有可能是空树二叉查找树是一个**有序**的二叉树每个节点包含一个项**左子树**的所有项都在根节点项的**前面****右子树**的所有项都在根节点项的**后面**
类型操作:初始化树为空确定树是否为空确定树是否已满确定树中的项数在树中添加一个项在树中删除一个项在树中查找一个项在树中访问一个项清空树接口头文件 原则上可以用多种方法实现二叉查找树甚至可以通过操控数组下标用数组来实现。 但是实现二叉查找树最直接的方法是通过指针动态分配链式节点。 因此我们这样定义 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结构重命名为Treetree结构就是一个树**//建立接口第二步描述实现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接口实现 注释来自https://blog.csdn.net/m0_46655998/article/details/105227533 前面的函数比较简单 #includestdio.h//包含fprintf函数的头文件
#includestdlib.h//包含malloc函数、free函数和exit函数的头文件
#includestring.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;//返回树的项数
}着重介绍下面的函数 添加项 AddItem(const Item * pi, Tree * ptree) 在树中添加一个项首先要检查该树是否有空间放得下一个项——TreeIsFull()由于我们定义二叉树时规定其中的项不能重复所以接下来要检查树中是否有该项——SeekItem()通过这两步检查后便可创建一个新节点把待添加项拷贝到该节点中并设置节点的左指针和右指针都为NULL。这表明该节点没有子节点。然后更新Tree结构的size成员统计新增了一项。接下来必须找出应该把这个新节点放在树中的哪个位置。如果树为空则应设置根节点指针指向该新节点。否则遍历树找到合适的位置放置该节点。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, Couldnt 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成员作比较如果返回为truenew_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成员作比较如果返回为truenew_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);}
}
