抽象数据类型ADT(abstract data type)
将一些基本的数据结构加上一些逻辑，可以封装成新的抽象的数据结构；这种新的抽象数据类型在处理大量数据时，比单一的数组或结构体类型要实用的多。
链表、队列、二叉树等都属于抽象数据类型；封装抽象数据类型可以分为以下三个步骤进行封装：
1)以抽象、通用的方式描述一个类型，包括该类型的操作；2)设计一个函数接口表示这个新类型；3)编写具体的代码实现这个接口。
1 链表
在使用结构体等存储数据的时候，需要先让编译器分配内存，于是在实际使用中就可能造成内存空间的浪费或不足；
那怎么办呢？是否有更加理想的内存分配模式，可以在使用过程中由于需求再不断分配内存呢？
并且在使用过程中不断分配的内存又该如何统一管理和存储呢？于是聪明的人们想到了一种办法：
定义一个结构，结构中包含需要存储的数据，以及一个指向自身结构类型的指针用来链接到下一个相同的结构对象；这种类型的结构人们将其形象的称为链表；
由于链表是抽象的结构，所以在使用之前我们先了解一下它的一些概念：
1)一个链表首先要有一个头指针phead，用来指向链表的第一个变量地址；
2)每个链表变量应该包含需要存储的数据以及指向下一个链表的指针pnext；
3)初始化链表数据的时候，需要两个指针辅助；pcurr用来存储当前操作的链表变量地址；ppre用来存储当前操作的链表变量地址供下一次操作使用；
3)链表的最后一个变量中，指向下一个链表的pnext指针设置为NULL，利用指针为NULL的特点可以用来判断该变量是否是链表结尾；
4)链表只能顺序查找；(所以链表效率比较低，不适合很多数据的查找；)
1.1 链表举例
1.1.1 链表结构存储数据举例
/*链表定义*/
struct files * phead=NULL; struct files *ppre , *pcurr; int Arrrate[10]= {1,2,3,4}; struct files { int rating ; struct files * pnext ; } /*使用Arrrate[10]来初始化链表；*/
for(int i=0;i<10;i++) { pcurr=(struct files *)malloc(sizeof(files)); if(phead==NULL) phead=pcurr; else ppre->pnext=pcurr; /*首先将当前结构体的地址放入上一个结构体的指针中*/ pcurr->rating= Arrrate[i]; pcurr->pnext=NULL; ppre=pcurr; /*存放当前结构体的地址，供下一个结构体的指针找到位置*/ }
1.1.2 链表结构取出数据举例
/*链表取出数据只能顺序取出；并且最后一个链表变量的pnext=NULL；*/
pcurr=phead; while(pcurr!=NULL) { printf("%d", pcurr->rating ); pcurr=pcurr->pnext; }
1.1.3 使用完后销毁链表内存
/*链表想要销毁内存也只能从phead开始顺序销毁；*/
pcurr=phead; while(pcurr != NULL) { phead=pcurr->pnext; free(pcurr); pcurr=phead; }
1.2 建立链表的抽象数据类型接口
目的：从用户的使用角度来对ADT数据类型进行封装，使得用户可以像调用普通接口的方式调用ADT数据类型；
以下例子只是举例如何对定义进行封装，进一步还需要提供封装后如何使用的函数声明以及函数定义；
typedef struct files { ... } Node; typedef Node * List; ... ... /*将前面的files结构体重新声明为Node，然后再将指向结构体的指针声明为List;*/ /*这样的话就将具体的代码抽象化了*/ /*然后利用这些抽象过的类型进行代码编写，有利于逻辑开发，也保护了代码的开发权限*/ /*List scores中的scores是地址来着，这样的话就将files结构体封装成了scores，使得用户直接操作scores就可以了*/
2 队列queue：
队列是一种简单的链表；称之为队列，是因为工作方式和排队相像；数据要求从队尾加入，队首离开(“先进先出”FIFO)；
以下给出一个队列定义的例子
2.1 队列：声明
#define MAXCNT 10
/*定义队列Queue；队列结构包含首节点，尾节点，节点项数*/ typedef struct queue{ struct Node * front; struct Node * rear; int itemsCnt; }Queue; /*定义节点Node；Item结构存储每个节点的数据，作为接口留给用户自定义；*/ typedef struct node{ Item item; struct node * next; }Node;
2.2 队列：简单使用函数
/*初始化函数；先建一个queue类型的空壳子；*/ void initQueue(Queue *pq ) { pq->front=NULL; pq->rear=NULL; pq->itemsCnt=0; } /*判断队列是否为空；*/ bool queueIsEmpty(const Queue * pq) { return pq->itemsCnt==0; } /*判断队列是否为满；*/ bool queueIsFull(const Queue * pq) { return pq->itemsCnt==MAXCNT; } /*判断队列当前的项数*/ int countQueue(const Queue * pq) { return pq->itemsCnt ; } /*清空队列*/ int emptyQueue(Queue *pq) { while(!queueIsEmpty(pq)) { delQueue(pq);//这是下面小节节点的删除函数； } }
2.3 队列：增加尾节点
正常步骤：新建一个节点，配置节点数据和节点next指针为NULL；
节点地址放入前一个节点中；把节点添加到队列尾端，并且项数加1；
注意事项：如果该节点是首项，front和rear是同一项，要配置front；由于队列的性质决定了加入的节点不是首节点就是尾节点；
/*item为需要增加的节点数据，pq为队列指针*/ int addQueue(Item item , Queue * pq) { Node * pnode; if(queueIsFull(pq)) return 0; pnode=(Node*)malloc(sizeof(Node)); if(pnote==NULL) return 0; else pnode->item=item; /*尾节点的数据*/ pnode->next = NULL; /*尾节点的next指针为NULL*/ if(queueIsEmpty(pq)) pq->front=pnode; /*如果是首项，front和rear是同一项；需要配置front的地址*/ else pq->rear->next=pnode; /*否则是尾项，需要将当前节点的地址放入前一个节点的指针中；*/ pq->rear=pnode; /*设置struct queue的rear*/ pq->itemsCnt++; /*设置struct queue的itemsCnt*/
return 1; }
2.4 队列：删除首节点
步骤：将首节点中存储的第二个节点的地址拿出来先，然后free首节点；重新配置首节点；
/*pq为指向队列的指针； */ int delQueue(Queue *pq) { if(queueIsEmpty(pq)) return 0; Node * pSecNode; pSecNode=pq->front->next; //将首节点中存储的后面一个节点的地址取出先； free(pq->front); //删除首节点 pq->front=pSecNode; //重新配置首节点 pq->itemsCnt--; //项数减1 if(pq->itemsCnt==0) pq->rear=NULL; return 1; }
1&2 小结：队列是一种简单的链表，所以相似的地方比较多；但是队列结构更规范些；
链表的phead，搬运数据的pcurr和ppre同普通变量定义相似，较为零散；而队列将这些指针放在结构体里，定义成了队列；
链表没有对数据的节点个数进行统计，队列结构体对数据的节点个数单独做了统计；
链表的变量是一些指针加一个数据结构体，而队列的变量是两个结构体；队列更加规范，符合逻辑性；
3 二叉树
二叉树的每个节点都包含一个项用来存储数据，以及两个指向其他子节点的指针用来链接结构；是一种二分查找的树形结构；
当数据按顺序排列时，使用二叉树从中间的节点开始查找，每次都能排除一半的数据量，效率较高；只是编程较为复杂。
3.1 定义：二叉查找树的每个节点都有两个子树，左子树的节点都在父节点的前面，右子树的节点都在父节点的后面，子树允许为空，但不允许相同；
/*tree.h文件，关于二叉树的定义部分*/ #ifndef _TREE_H_ #define _TREE_H_ #include<stdbool.h> #define MAXITEMS 10 #define SLEN 20 typedef struct item{ char name[SLEN]; char kind[SLEN]; }Item;
/********节点：********|********节点的数据项*********|*******************
**********************|**左子节点指针***右子节点指针**|******************/ typedef struct trenode{ Item item; /*节点的数据项*/ struct trenode * leftnode; /*指向左子节点的指针*/ struct trenode * rightnode; /*指向右子节点的指针*/ }Trenode; /*二叉查找树的节点定义*/ typedef struct tree{ struct trenode * root; /*根节点就可以确定二叉树的位置了*/ int size; }Tree; /*二叉树的定义*/
原文：https://www.cnblogs.com/caesura-k/p/12368258.html