线性表

顺序表

ArrayList.h

#ifndef _ArrayList_H_
#define _ArrayList_H_
#define MaxSize 10
typedef int DataType;
 
typedef struct ArrayList{
DataType *list;
int size;//已有数目
int maxSize;//可容纳的最大数量
}ArrayList;

void ArrayListInit(ArrayList *arrayList){
arrayList->maxSize=MaxSize;
arrayList->list=(DataType *)malloc(arrayList->maxSize*sizeof(DataType));
arrayList->size=0;
}

//获取元素(通过索引)
DataType GetElement(ArrayList *arrayList,int index){
//判断索引是否超过目前最大的数量
if(index>=arrayList->maxSize){
printf("error:over the maxsize of the list\n");//后续可以编写扩容函数替代
return (DataType)0;
}

return arrayList->list[index];
}

//扩容
void Enlarge(ArrayList *arrayList){
int i;
DataType *tempList;
tempList=arrayList->list;
arrayList->list=(DataType *)malloc(2*arrayList->maxSize*sizeof(DataType));
for(i=0;i<arrayList->maxSize;i++){
arrayList->list[i]=tempList[i];
}
arrayList->maxSize=2*arrayList->maxSize;
}

//插入元素
int InsertElement(ArrayList *arrayList,int index,DataType data){
//判断索引是否越界
if(index>arrayList->size){
printf("error:over the size of the list\n");
return 0;
}

//判断索引是否超过目前最大的数量
if(index>=arrayList->maxSize){
Enlarge(arrayList);
}

arrayList->list[index]=data;
(arrayList->size)++;
return 1;
}

//删除元素(通过索引)
int DeleteElement(ArrayList *arrayList,int index){
int i;
//判断索引是否超过目前最大的数量
if(index>=arrayList->size){
printf("error:over the maxsize of the list\n");
return 0;
}
for(i=index;i<arrayList->size;i++){
arrayList->list[i]=arrayList->list[i+1];
}
(arrayList->size)--;
return 1;
}
#endif

测试结果

链表

LinkedList.h

#ifndef _LinkedList_H_
#define _LinkedList_H_
typedef int DataType;
//节点
typedef struct Node{
DataType data;//数据域
struct Node *next;//下一个节点
}Node;


//初始化链表
void LinkedListInit(Node **head){
(*head)=(Node *)malloc(sizeof(Node));
(*head)->next=NULL;
}


//返回链表的大小
int Size(Node *headNode){
Node *tempNode=headNode;
int num=0;

while(tempNode->next){
tempNode=tempNode->next;
num++;
}

tempNode=NULL;

return num;
}


//删除节点1(通过索引)
int DeleteNode(Node *headNode,int index){
//判断索引是否越界
int num=Size(headNode);
if(num<index-1&&index<0){
printf("error:index over the range");
return 0;
}

Node *delNode,*tempNode=headNode;
for(int i=0;i<index-1;i++)
	tempNode=tempNode->next;
delNode=tempNode->next;
tempNode->next=delNode->next;

//释放资源和指针
free(delNode);
delNode=NULL;
tempNode=NULL;

return 1;
}


//在(末尾)增加节点
void AddNode(Node *headNode,DataType data){
Node *tempNode=headNode;
//创建插入的节点
Node *insertNode=(Node *)malloc(sizeof(Node));
insertNode->data=data;
insertNode->next=NULL;

while(tempNode->next){
tempNode=tempNode->next;
}
tempNode->next=insertNode;

//释放指针
tempNode=NULL;
insertNode=NULL;
}


//插入节点(通过索引),返回是否插入成功
int InsertNode(Node *headNode,int index,DataType data){
//判断索引是否越界
int num=Size(headNode);
if(num<index&&index<0){
printf("error:index over the range");
return 0;
}

Node *insertNextNode,*tempNode=headNode;

//创建插入的节点
Node *insertNode=(Node *)malloc(sizeof(Node));
insertNode->data=data;

for(int i=0;i<index-1;i++)
	tempNode=tempNode->next;
insertNextNode=tempNode->next;
tempNode->next=insertNode;
insertNode->next=insertNextNode;

//释放指针
tempNode=NULL;
insertNode=NULL;
insertNextNode=NULL;
}


//获取链表元素（通过索引）
DataType GetElement(Node *headNode,int index){
//判断索引是否越界
int i;
DataType element;
Node *tempNode=headNode;
int num=Size(headNode);
if(num<index-1&&index<0){
printf("error:index over the range");
return (DataType)0;
}

for(i=0;i<index;i++){
tempNode=tempNode->next;
}

element=tempNode->data;
tempNode=NULL;
return element;
}


//输出链表
void Show(Node *headNode){
Node *tempNode=headNode;
while(tempNode->next){
tempNode=tempNode->next;
printf("%d\n",tempNode->data);
}

//释放指针
tempNode=NULL;
}
#endif

测试结果

栈和队列

栈

顺序表存储的栈

ArrayStack.h

#ifndef _ArrayStack_H_
#define _ArrayStack_H_
#define MaxSize 10  //初始最大数目
typedef int DataType;  //自定义数据类型

typedef struct ArrayStack{
DataType *array;
int size;//已有数目
int maxSize;//可容纳最大数目
}ArrayStack;

void ArrayStackInit(ArrayStack *arrayStack){
arrayStack->maxSize=MaxSize;
arrayStack->array=(DataType *)malloc(arrayStack->maxSize*sizeof(DataType));
arrayStack->size=0;
}


//判断栈是否为空
int IsEmpty(ArrayStack *arrayStack){
return arrayStack->size==0?1:0;
}


//弹出元素
DataType Pop(ArrayStack *arrayStack){
if(IsEmpty(arrayStack)){
printf("error:ArrayStack is NULL\n");
return (DataType)0;
}

arrayStack->size--;

return arrayStack->array[arrayStack->size];  
}


//扩容
void Enlarge(ArrayStack *arrayStack){
DataType *tempArray=arrayStack->array;
int i;

arrayStack->maxSize=2*arrayStack->maxSize;
arrayStack->array=(DataType *)malloc(2*arrayStack->maxSize*sizeof(DataType));
for(i=0;i<arrayStack->size;i++){
arrayStack->array[i]=tempArray[i];
}
arrayStack->size++;

//释放资源
free(tempArray);
tempArray=NULL;
}


//添加元素
void Push(ArrayStack *arrayStack,DataType data){
if(arrayStack->size==arrayStack->maxSize){
Enlarge(arrayStack);
}
arrayStack->array[arrayStack->size]=data;
arrayStack->size++;
}
#endif

测试结果

链表存储的栈

LinkedStack.h

#ifndef _LinkedStack_H_
#define _LinkedStack_H_

typedef int DataType;
//节点
typedef struct LSNode{
DataType data;//数据域
struct LSNode *next;//下一个节点
}LSNode;


void LinkedStackInit(LSNode **linkedStack){
(*linkedStack)=(LSNode *)malloc(sizeof(LSNode));
(*linkedStack)->next=NULL;
}


//判断是否为空
int IsEmpty(LSNode *linkedStack){
return linkedStack->next==NULL?1:0;
}


//获取元素数目
int Size(LSNode *linkedStack){
int num=0;
LSNode *tempLSNode=linkedStack;
while(tempLSNode->next!=NULL){
tempLSNode=tempLSNode->next;
num++;
return num;
}

tempLSNode=NULL;

return num;
}


//弹出元素
DataType Pop(LSNode *linkedStack){
LSNode *tempLSNode,*popNode;
DataType popData;

if(IsEmpty(linkedStack)){
printf("error:LinkedStack is NULL\n");
}

tempLSNode=linkedStack;
while((tempLSNode->next)->next!=NULL){
tempLSNode=tempLSNode->next;
}
popNode=tempLSNode->next;
popData=popNode->data;
tempLSNode->next=NULL;

//释放资源
tempLSNode=NULL;
free(popNode);
popNode=NULL;

return popData;
}


//添加元素
void Push(LSNode *linkedStack,DataType data){
LSNode *tempLSNode=linkedStack;

LSNode *pushLSNode=(LSNode *)malloc(sizeof(LSNode));
pushLSNode->data=data;
pushLSNode->next=NULL;

while(tempLSNode->next!=NULL){
tempLSNode=tempLSNode->next;
}

tempLSNode->next=pushLSNode;

//释放指针
tempLSNode=NULL;
pushLSNode=NULL;
}

#endif

测试结果

队列

顺序表存储的队列

ArrayQueue.h

#ifndef _ArrayStack_H_
#define _ArrayStack_H_
#define MaxSize 10  //初始最大数目
typedef int DataType;  //自定义数据类型

typedef struct ArrayQueue{
DataType *array;
int size;//已有数目
int maxSize;//可容纳最大数目
}ArrayQueue;


//初始化
void ArrayQueueInit(ArrayQueue *arrayQueue){
arrayQueue->maxSize=MaxSize;
arrayQueue->array=(DataType *)malloc(arrayQueue->maxSize*sizeof(DataType));
arrayQueue->size=0;
}


//判断元素是否为空
int IsEmpty(ArrayQueue *arrayQueue){
return arrayQueue->size==0?1:0;
}


//弹出元素
DataType Pop(ArrayQueue *arrayQueue){
DataType popData;
int i;
if(IsEmpty(arrayQueue)){
printf("error:ArrayQueue is NULL");
return (DataType)0;
}
popData=arrayQueue->array[0];
for(i=0;i<arrayQueue->size;i++){
arrayQueue->array[i]=arrayQueue->array[i+1];
}
arrayQueue->size--;
return popData;
}


//扩容
void Enlarge(ArrayQueue *arrayQueue){
int i;
DataType *tempArray=arrayQueue->array;
arrayQueue->maxSize=2*arrayQueue->maxSize;
arrayQueue->array=(DataType *)malloc(arrayQueue->maxSize*sizeof(DataType));

for(i=0;i<arrayQueue->size;i++){
arrayQueue->array[i]=tempArray[i];
}

//释放资源
free(tempArray);
tempArray=NULL;
}


//添加元素
void Push(ArrayQueue *arrayQueue,DataType data){
if(arrayQueue->size==arrayQueue->maxSize){
Enlarge(arrayQueue);
}

arrayQueue->array[arrayQueue->size]=data;
arrayQueue->size++;
}

#endif

测试结果

链表存储的队列

LinkedQueue.h

#ifndef _LinkedQueue_H_
#define _LinkedQueue_H_

typedef int DataType;
//节点
typedef struct LQNode{
DataType data;//数据域
struct LQNode *next;//下一个节点
}LQNode;


//初始化链表
void LinkedQueueInit(LQNode **linkedQueue){
(*linkedQueue)=(LQNode *)malloc(sizeof(LQNode));
(*linkedQueue)->next=NULL;
}


//元素数目
int Size(LQNode *linkedQueue){
int num;
LQNode *tempNode=linkedQueue;
while(tempNode->next!=NULL){
tempNode=tempNode->next;
num++;
}
return num;
}


//添加元素
void Push(LQNode *linkedQueue,DataType data){
LQNode *tempLQNode=linkedQueue;
LQNode *insertLQNode=(LQNode *)malloc(sizeof(LQNode));
insertLQNode->data=data;
insertLQNode->next=NULL;
while(tempLQNode->next!=NULL){
tempLQNode=tempLQNode->next;
}
tempLQNode->next=insertLQNode;

//释放指针
tempLQNode=NULL;
insertLQNode=NULL;
}


//弹出头节点
DataType Pop(LQNode *linkedQueue){
LQNode *tempLQNode=linkedQueue->next;
DataType deleteData=tempLQNode->data; 
linkedQueue->next=(linkedQueue->next)->next;

//释放资源
tempLQNode=NULL;
free(tempLQNode);
tempLQNode=NULL;
return deleteData;
}


//获取元素
DataType GetElement(LQNode *linkedQueue,int index){
if(Size(linkedQueue)<=index){
printf("erroe:index over the boundary of linkedQueue\n");
return (DataType)0;
}
LQNode *tempNode=linkedQueue;
int i;
DataType element;
for(i=0;i<index;i++){
tempNode=tempNode->next;
}
element=tempNode->data;
return element;
}

#endif

测试结果

二叉树

普通的二叉树

	一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左
子树和右子树的二叉树组成。二叉树的特点：
	1.每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
	2.二叉树的子树有左右之分，其子树的次序不能颠倒

BinaryTree.h

#ifndef _BinaryTree_H_
#define _BinaryTree_H_
typedef int DataType;

typedef struct BTNode{
DataType data;
struct BTNode *rightNode;
struct BTNode *leftNode;
}BTNode;


//初始化
void BinaryTreeInit(BTNode **binaryTree,DataType data){
(*binaryTree)=(BTNode *)malloc(sizeof(BTNode));
(*binaryTree)->data=data;
(*binaryTree)->rightNode=NULL;
(*binaryTree)->leftNode=NULL;
}


//计算树的深度
int Depth(BTNode *headNode){
if(headNode==NULL){
return 0;
}

if(headNode->leftNode==NULL&&headNode->rightNode==NULL){
return 1;
}

return Depth(headNode->leftNode)+1>=Depth(headNode->rightNode)+1?Depth(headNode->leftNode)+1:Depth(headNode->rightNode)+1;
}



//插入当前节点的左子树上
void InsertLeftTree(BTNode *currentBTNode,DataType data){
BTNode *tempBTNode=currentBTNode;

BTNode *insertBTNode=(BTNode *)malloc(sizeof(BTNode));
insertBTNode->data=data;
insertBTNode->leftNode=NULL;
insertBTNode->rightNode=NULL;

while(tempBTNode->leftNode!=NULL){
tempBTNode=tempBTNode->leftNode;
}

tempBTNode->leftNode=insertBTNode;

//释放指针
tempBTNode=NULL;
insertBTNode=NULL;
}


//插入当前节点的右子树上
void InsertRightTree(BTNode *currentBTNode,DataType data){
BTNode *tempBTNode=currentBTNode;

BTNode *insertBTNode=(BTNode *)malloc(sizeof(BTNode));
insertBTNode->data=data;
insertBTNode->leftNode=NULL;
insertBTNode->rightNode=NULL;

while(tempBTNode->rightNode!=NULL){
tempBTNode=tempBTNode->rightNode;
}

tempBTNode->rightNode=insertBTNode;

//释放指针
tempBTNode=NULL;
insertBTNode=NULL;
}


// 先序遍历
void PreSearch(BTNode *binaryTree){
printf("%d\n",binaryTree->data);

if(binaryTree->leftNode!=NULL){
PreSearch(binaryTree->leftNode);
}

if(binaryTree->rightNode!=NULL){
PreSearch(binaryTree->rightNode);
}

}


// 中序遍历
void MidSearch(BTNode *binaryTree){
if(binaryTree->leftNode!=NULL){
MidSearch(binaryTree->leftNode);
}

printf("%d\n",binaryTree->data);

if(binaryTree->rightNode!=NULL){
MidSearch(binaryTree->rightNode);
}
}

// 后序遍历
void PostSearch(BTNode *binaryTree){
if(binaryTree->leftNode!=NULL){
PostSearch(binaryTree->leftNode);
}

if(binaryTree->rightNode!=NULL){
PostSearch(binaryTree->rightNode);
}

printf("%d\n",binaryTree->data);

}

#endif

测试结果

二叉搜索树

若是二叉搜索树，则满足一下条件：
	1.是二叉树
	2.每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
	3.每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

BinarySearchTree.h

#ifndef _BinarySearchTree_H_
#define _BinarySearchTree_H_
typedef int DataType;

typedef struct BSTNode{
DataType data;
struct BSTNode *rightNode;
struct BSTNode *leftNode;
}BSTNode;


//初始化
void BinarySearchTreeInit(BSTNode **binarySearchTree,DataType data){
(*binarySearchTree)=(BSTNode *)malloc(sizeof(BSTNode));
(*binarySearchTree)->data=data;
(*binarySearchTree)->rightNode=NULL;
(*binarySearchTree)->leftNode=NULL;
}


//计算树的深度
int Depth(BSTNode *headNode){
if(headNode==NULL){
return 0;
}

if(headNode->leftNode==NULL&&headNode->rightNode==NULL){
return 1;
}

return Depth(headNode->leftNode)+1>=Depth(headNode->rightNode)+1?Depth(headNode->leftNode)+1:Depth(headNode->rightNode)+1;
}



//插入节点
void InsertNode(BSTNode *binarySearchTree,DataType data){
BSTNode *tempBSTNode=binarySearchTree;
BSTNode *insertBSTNode=(BSTNode *)malloc(sizeof(BSTNode));
insertBSTNode->data=data;
insertBSTNode->rightNode=NULL;
insertBSTNode->leftNode=NULL;

while((tempBSTNode->rightNode!=NULL&&data>=tempBSTNode->data)||(tempBSTNode->leftNode!=NULL&&data<tempBSTNode->data)){
if(data>=tempBSTNode->data){
tempBSTNode=tempBSTNode->rightNode;
}else{
tempBSTNode=tempBSTNode->leftNode;
}
}

if(data>=tempBSTNode->data){
tempBSTNode->rightNode=insertBSTNode;
}else{
tempBSTNode->leftNode=insertBSTNode;
}

//释放指针
tempBSTNode=NULL;
insertBSTNode=NULL;
}


// 先序遍历
void PreSearch(BSTNode *binarySearchTree){
printf("%d\n",binarySearchTree->data);

if(binarySearchTree->leftNode!=NULL){
PreSearch(binarySearchTree->leftNode);
}

if(binarySearchTree->rightNode!=NULL){
PreSearch(binarySearchTree->rightNode);
}
}


// 中序遍历
void MidSearch(BSTNode *binarySearchTree){
if(binarySearchTree->leftNode!=NULL){
MidSearch(binarySearchTree->leftNode);
}

printf("%d\n",binarySearchTree->data);

if(binarySearchTree->rightNode!=NULL){
MidSearch(binarySearchTree->rightNode);
}
}


// 后序遍历
void PostSearch(BSTNode *binarySearchTree){
if(binarySearchTree->leftNode!=NULL){
PostSearch(binarySearchTree->leftNode);
}

if(binarySearchTree->rightNode!=NULL){
PostSearch(binarySearchTree->rightNode);
}

printf("%d\n",binarySearchTree->data);

}

#endif

测试结果

二叉平衡树（改了许多遍才成功）

若是二叉平衡树，则满足一下条件：
	1.是二叉搜索树
	2.每个节点中的左右子树深度差都不超过1

AVLTree.h

#ifndef _AVLTree_H_
#define _AVLTree_H_
typedef int DataType;


typedef struct AVLTNode{
DataType data;
struct AVLTNode *rightNode;
struct AVLTNode *leftNode;
}AVLTNode;


//初始化
void AVLTreeInit(AVLTNode **balanceTree,DataType data){
(*balanceTree)=(AVLTNode *)malloc(sizeof(AVLTNode));
(*balanceTree)->data=data;
(*balanceTree)->rightNode=NULL;
(*balanceTree)->leftNode=NULL;
}


//计算树的深度
int Depth(AVLTNode *headNode){
if(headNode==NULL){
return 0;
}

if(headNode->leftNode==NULL&&headNode->rightNode==NULL){
return 1;
}

return Depth(headNode->leftNode)+1>=Depth(headNode->rightNode)+1?Depth(headNode->leftNode)+1:Depth(headNode->rightNode)+1;
}


//左旋转
AVLTNode *LLRotate(AVLTNode **balanceTree){
AVLTNode *tempNode=(*balanceTree);
//把原来头结点的右节点转换成头结点
(*balanceTree)=(*balanceTree)->rightNode;
if((*balanceTree)->leftNode!=NULL){
//把头结点的右节点原有的左结点 给到 原头结点的右节点
tempNode->rightNode=(*balanceTree)->leftNode;
}else{
tempNode->rightNode=NULL;
}
(*balanceTree)->leftNode=tempNode;

//释放指针
tempNode=NULL;
return (*balanceTree);
}


//右旋转
AVLTNode *RRRotate(AVLTNode **balanceTree){
AVLTNode *tempNode=(*balanceTree);
//把原来头结点的左节点转换成头结点
(*balanceTree)=(*balanceTree)->leftNode;
if((*balanceTree)->rightNode!=NULL){
//把头结点的左节点原有的右结点 给到 原头结点的左节点
tempNode->leftNode=(*balanceTree)->rightNode;
}else{
tempNode->leftNode=NULL;
}
(*balanceTree)->rightNode=tempNode;

//释放指针
tempNode=NULL;
return (*balanceTree);
}


//左右旋转
void LRRotate(AVLTNode **balanceTree){
(*balanceTree)->leftNode=LLRotate(&((*balanceTree)->leftNode));
RRRotate(balanceTree);
}


//右左旋转
void RLRotate(AVLTNode **balanceTree){
(*balanceTree)->rightNode=RRRotate(&((*balanceTree)->rightNode));
LLRotate(balanceTree);
}


//通过旋转使树变成二叉平衡树
AVLTNode *ToBalance(AVLTNode **balanceTree){
//递归是每个子树变成平衡二叉树
if((*balanceTree)->leftNode!=NULL){
(*balanceTree)->leftNode=ToBalance(&((*balanceTree)->leftNode));
}

if((*balanceTree)->rightNode!=NULL){
(*balanceTree)->rightNode=ToBalance(&((*balanceTree)->rightNode));
}

if(Depth((*balanceTree)->leftNode)>Depth((*balanceTree)->rightNode)+1){
if(Depth(((*balanceTree)->leftNode)->leftNode)>=Depth(((*balanceTree)->leftNode)->rightNode)){
RRRotate(balanceTree);
}else{
LRRotate(balanceTree);
}
}

if(Depth((*balanceTree)->leftNode)<Depth((*balanceTree)->rightNode)-1){
if(Depth(((*balanceTree)->rightNode)->rightNode)>=Depth(((*balanceTree)->rightNode)->leftNode)){
LLRotate(balanceTree);
}else{
RLRotate(balanceTree);
}
}

return (*balanceTree);
}


//插入节点
void InsertNode(AVLTNode **balanceTree,DataType data){
AVLTNode *tempAVLTNode=(*balanceTree);
AVLTNode *insertAVLTNode=(AVLTNode *)malloc(sizeof(AVLTNode));
insertAVLTNode->data=data;
insertAVLTNode->rightNode=NULL;
insertAVLTNode->leftNode=NULL;

while((tempAVLTNode->rightNode!=NULL&&data>=tempAVLTNode->data)||(tempAVLTNode->leftNode!=NULL&&data<tempAVLTNode->data)){
if(data>=tempAVLTNode->data){
tempAVLTNode=tempAVLTNode->rightNode;
}else{
tempAVLTNode=tempAVLTNode->leftNode;
}
}

if(data>=tempAVLTNode->data){
tempAVLTNode->rightNode=insertAVLTNode;
}else{
tempAVLTNode->leftNode=insertAVLTNode;
}

//通过旋转使树变成二叉平衡树
ToBalance(balanceTree);
//释放指针
tempAVLTNode=NULL;
insertAVLTNode=NULL;
}


// 先序遍历
void PreSearch(AVLTNode *balanceTree){
printf("%d\n",balanceTree->data);

if(balanceTree->leftNode!=NULL){
PreSearch(balanceTree->leftNode);
}

if(balanceTree->rightNode!=NULL){
PreSearch(balanceTree->rightNode);
}

}


// 中序遍历
void MidSearch(AVLTNode *balanceTree){
if(balanceTree->leftNode!=NULL){
MidSearch(balanceTree->leftNode);
}

printf("%d\n",balanceTree->data);

if(balanceTree->rightNode!=NULL){
MidSearch(balanceTree->rightNode);
}
}


// 后序遍历
void PostSearch(AVLTNode *balanceTree){
if(balanceTree->leftNode!=NULL){
PostSearch(balanceTree->leftNode);
}

if(balanceTree->rightNode!=NULL){
PostSearch(balanceTree->rightNode);
}

printf("%d\n",balanceTree->data);

}

#endif

测试结果