欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

stack、queue、list、bstree

程序员文章站 2024-01-16 23:08:58
...
#ifndef DATA_STRUCTURE_H
#define DATA_STRUCTURE_H
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
/***************************************************************
 * 栈的顺序存储结构声明
 */
typedef struct Stack_sx{
	int* arr;   //数组首地址
	size_t cap; //容量
	size_t top; //下标/栈顶
}STACK_SX;
//初始化栈
void stack_sx_init(STACK_SX* stack, size_t cap);
//释放化栈
void stack_sx_deinit(STACK_SX* stack);
//判断栈空
int stack_sx_empty(STACK_SX* stack);
//判断栈满
int stack_sx_full(STACK_SX* stack);
//入栈
void stack_sx_push(STACK_SX* stack, int data);
//出栈
int stack_sx_pop(STACK_SX* stack);
//查看栈顶
int stack_sx_top(STACK_SX* stack);
//元素数量
size_t stack_sx_size(STACK_SX* stack);
/***************************************************************
 *栈的链式存储结构声明
 */
typedef struct StackNode{	//节点结构
	int data;				//数据
	struct StackNode* next;	//指向下一个节点地址
}STACK_NODE;
typedef struct Stack_ls{	//栈结构
	STACK_NODE* top;		//栈顶节点指针
}STACK_LS;
//初始化栈
void stack_ls_init(STACK_LS* stack);
//释放化栈
void stack_ls_deinit(STACK_LS* stack);
//判断栈空
int stack_ls_empty(STACK_LS* stack);
//入栈
void stack_ls_push(STACK_LS* stack, int data);
//出栈
int stack_ls_pop(STACK_LS* stack);
//查看栈顶
int stack_ls_top(STACK_LS* stack);
//元素数量
size_t stack_ls_size(STACK_LS* stack);
/***************************************************************
 *队列的顺序存储结构(循环队列)声明
 */
typedef struct Queue_sx{
	int* arr;	   //数组首地址
	size_t cap;	   //容量
	size_t front;  //队首
	size_t rear;   //队尾
	size_t size;   //数量
}QUEUE_SX;
//初始化队列
void queue_sx_init(QUEUE_SX* queue, size_t cap);
//释放化队列
void queue_sx_deinit(QUEUE_SX* queue);
//判断队列空
int queue_sx_empty(QUEUE_SX* queue);
//判断队列满
int queue_sx_full(QUEUE_SX* queue);
//入队
void queue_sx_push(QUEUE_SX* queue, int data);
//出队
int queue_sx_pop(QUEUE_SX* queue);
//查看队首
int queue_sx_front(QUEUE_SX* queue);
//元素数量
size_t queue_sx_size(QUEUE_SX* queue);
/***************************************************************
 *队列的链式存储结构声明
 */
typedef struct QueueNode{	//节点结构
	int data;				//数据
	struct QueueNode* next;	//指向下一个节点地址
}QUEUE_NODE;
typedef struct Queue_ls{	//队结构
	QUEUE_NODE* front;		//队首节点指针
	QUEUE_NODE* rear;		//队尾节点指针
}QUEUE_LS;
//初始化队列
void queue_ls_init(QUEUE_LS* queue);
//释放化队列
void queue_ls_deinit(QUEUE_LS* queue);
//判断队列空
int queue_ls_empty(QUEUE_LS* queue);
//入队
void queue_ls_push(QUEUE_LS* queue, int data);
//出队
int queue_ls_pop(QUEUE_LS* queue);
//查看队首
int queue_ls_front(QUEUE_LS* queue);
//元素数量
size_t queue_ls_size(QUEUE_LS* queue);
/***************************************************************
 *单向链表声明
 */
//单项链表
typedef struct ListNode_d{  //节点结构
	int data;               //数据
	struct ListNode_d* next;//指向下一个节点地址
}LIST_NODE_D;
typedef struct List_d{  //链表结构
	LIST_NODE_D* head;  //头节点指针
	LIST_NODE_D* tail;  //尾节点指针
	LIST_NODE_D* frwd;  //应用于迭代
}LIST_D;

//初始化链表
void list_d_init(LIST_D* list);
//释放化链表
void list_d_deinit(LIST_D* list);
//判断链表空
int list_d_empty(LIST_D* list);
//追加元素
void list_d_append(LIST_D* list, int data);
//迭代
void list_d_iterative(LIST_D* list);
//元素数量
size_t list_d_size(LIST_D* list);
//正向打印
void list_d_print(LIST_D* list);
//反向打印(递归)
void list_d_rprint(LIST_D* list);
//逆转链表(递归)
void list_d_reverse(LIST_D* list);
//获取中间值
int list_d_mid(LIST_D* list);
/***************************************************************
 *双向链表声明
 */
//双向链表
typedef struct ListNode_s{  //节点结构
    int data;               //数据
    struct ListNode_s* next;//指向下一个节点地址
    struct ListNode_s* prev;//指向上一个节点地址
}LIST_NODE_S;
typedef struct List_s{  //链表结构
    LIST_NODE_S* head;  //头节点指针
    LIST_NODE_S* tail;  //尾节点指针
    LIST_NODE_S* frwd;  //应用于迭代
}LIST_S;
//初始化链表
void list_s_init(LIST_S* list);
//释放化链表
void list_s_deinit(LIST_S* list);
//判断链表空
int list_s_empty(LIST_S* list);
//追加元素
void list_s_append(LIST_S* list, int data);
//插入元素(位置按前插)
int list_s_insert(LIST_S* list, size_t pos, int data);
//删除元素(按位置删除)
int list_s_erase(LIST_S* list, size_t pos);
//删除元素(相同元素全删除)
void list_s_remove(LIST_S* list, int data);
//全删元素
void list_s_clear(LIST_S* list);
//查看元素(按位置取值)
int* list_s_at(LIST_S* list, size_t pos);
//元素数量
size_t list_s_size(LIST_S* list);
//正向迭代
void list_s_begin(LIST_S* list);
//向前迭
int* list_s_next(LIST_S* list);
//反向迭代
void list_s_reverse(LIST_S* list);
//向后迭
int* list_s_prev(LIST_S* list);
//当前迭代(当前值)
int* list_s_current(LIST_S* list);
//判断迭代结束
int list_s_end(LIST_S* list);
/***************************************************************
 *有序二叉树链式声明
 */
typedef struct BstreeNode{      //节点结构
    int data;                   //数据
    struct BstreeNode* left;    //左子节点
    struct BstreeNode* right;   //右子节点
}BSTREE_NODE;
typedef struct Bstree{  //树结构
    BSTREE_NODE* root;  //根节点
    size_t size;        //节点数量
}BSTREE;
//初始化二叉树
void bstree_init(BSTREE* bstree);
//释放化二叉树(递归)
void bstree_deinit(BSTREE* bstree);
//插入元素(递归)
void bstree_insert(BSTREE* bstree, int data);
//删除元素(递归)
int bstree_erase(BSTREE* bstree, int data);
//清空元素
void bstree_clear(BSTREE* bstree);
//修改元素
void bstree_update(BSTREE* bstree, int old, int New);
//查询元素(递归)
int bstree_exist(BSTREE* bstree, int data);
//中序遍历(递归)
void bstree_travel(BSTREE* bstree);
//元素数量
size_t bstree_size(BSTREE* bstree);
//树的层数(递归)
size_t bstree_height(BSTREE* bstree);

#endif 
#include "data_structure.h"
/***************************************************************
 * 栈的顺序存储结构定义
 */
//初始化栈
void stack_sx_init(STACK_SX* stack, size_t cap)
{
	stack->arr = malloc(cap * sizeof(int));
	stack->cap = cap;
	stack->top = 0;
}
//释放化栈
void stack_sx_deinit(STACK_SX* stack)
{
	free(stack->arr);
	stack->arr = NULL;
	stack->cap = 0;
	stack->top = 0;
}
//判断栈空
int stack_sx_empty(STACK_SX* stack)
{
	return !stack->top;
}
//判断栈满
int stack_sx_full(STACK_SX* stack)
{
	return stack->top >= stack->cap;
}
//入栈
void stack_sx_push(STACK_SX* stack, int data)
{
	stack->arr[stack->top++] = data;
}
//出栈
int stack_sx_pop(STACK_SX* stack)
{
	stack->top--;
	return stack->arr[stack->top];
}
//查看栈顶
int stack_sx_top(STACK_SX* stack)
{
	return stack->arr[stack->top-1];
}
//元素数量
size_t stack_sx_size(STACK_SX* stack)
{
	return stack->top;
}
/***************************************************************
 *栈的链式存储结构定义
 */
//创建节点(创建一个)
static STACK_NODE* create_stack_node(STACK_NODE* next, int data)
{
	STACK_NODE *node = malloc(sizeof(STACK_NODE));
	node->data = data;
	node->next = next;
	return node;
}
//销毁节点(销毁一个)
static STACK_NODE* destroy_stack_node(STACK_NODE* node)
{
	STACK_NODE* next = node->next;
	free(node);
	return next;
}
//初始化栈
void stack_ls_init(STACK_LS* stack)
{
	stack->top = NULL;
}
//释放化栈(释放空间)
void stack_ls_deinit(STACK_LS* stack)
{
	while(stack->top){
		stack->top = destroy_stack_node(stack->top);
	}
}
//判断栈空(没满)
int stack_ls_empty(STACK_LS* stack)
{
	return !stack->top;
}
//入栈
void stack_ls_push(STACK_LS* stack, int data)
{
	stack->top = create_stack_node(stack->top, data);
}
//出栈
int stack_ls_pop(STACK_LS* stack)
{
	int data = stack->top->data;
	stack->top = destroy_stack_node(stack->top);
	return data;
}
//查看栈顶
int stack_ls_top(STACK_LS* stack)
{
	return stack->top->data;
}
//元素数量
size_t stack_ls_size(STACK_LS* stack)
{
	size_t size = 0;
	STACK_NODE* node = stack->top;
	for(; node; node = node->next)size++;
	return size;
}
/***************************************************************
 *队列的顺序存储结构(循环队列)定义
 */
//初始化队列
void queue_sx_init(QUEUE_SX* queue, size_t cap)
{
	queue->arr = malloc(cap * sizeof(int));
	queue->cap = cap;
	queue->front = 0;
	queue->rear = 0;
	queue->size = 0;
}
//释放化队列
void queue_sx_deinit(QUEUE_SX* queue)
{
	free(queue->arr);
	queue->arr = NULL;
	queue->cap = 0;
	queue->front = 0;
	queue->rear = 0;
	queue->size = 0;
}
//判断队列空
int queue_sx_empty(QUEUE_SX* queue)
{
	return !queue->size;
}
//判断队列满
int queue_sx_full(QUEUE_SX* queue)
{
	return queue->size >= queue->cap;
}
//入队
void queue_sx_push(QUEUE_SX* queue, int data)
{
	if(queue->rear >= queue->cap){
		queue->rear = 0;
	}queue->size += 1;
	queue->arr[queue->rear++] = data;
}
//出队
int queue_sx_pop(QUEUE_SX* queue)
{
	if(queue->front >= queue->cap){
		queue->front = 0;
	}queue->size -= 1;
	return queue->arr[queue->front++];
}
//查看队首
int queue_sx_front(QUEUE_SX* queue)
{
	if(queue->front >= queue->cap){
		queue->front = 0;
	}return queue->arr[queue->front];
}
//元素数量
size_t queue_sx_size(QUEUE_SX* queue)
{
	return queue->size;
}
/***************************************************************
 *队列的链式存储结构定义
 */
//创建节点(创建一个)
static QUEUE_NODE* create_queue_node(int data)
{
	QUEUE_NODE* node = malloc(sizeof(QUEUE_NODE));
	node->data = data;
	node->next = NULL;
	return node;
}
//销毁节点(销毁一个)
static QUEUE_NODE* destroy_queue_node(QUEUE_NODE* node)
{
	QUEUE_NODE* next = node->next;
	free(node);
	return next;
}
//初始化队列
void queue_ls_init(QUEUE_LS* queue)
{
	queue->front = NULL;
	queue->rear = NULL;
}
//释放化队列(释放空间)
void queue_ls_deinit(QUEUE_LS* queue)
{
	while(queue->front){
		queue->front = destroy_queue_node(queue->front);
	}queue->rear = NULL;
}
//判断队列空(没满)
int queue_ls_empty(QUEUE_LS* queue)
{
	return !queue->front && !queue->rear;
}
//入队
void queue_ls_push(QUEUE_LS* queue, int data)
{
	QUEUE_NODE* rear = create_queue_node(data);
	if(queue->rear){
		queue->rear->next = rear;
	}else queue->front = rear;
	queue->rear = rear;
}
//出队
int queue_ls_pop(QUEUE_LS* queue)
{
	int data = queue->front->data;
	if(!(queue->front = destroy_queue_node(queue->front))){
		queue->rear = NULL;
	}return data;
}
//查看队首
int queue_ls_front(QUEUE_LS* queue)
{
	return queue->front->data;
}
//元素数量
size_t queue_ls_size(QUEUE_LS* queue)
{
    size_t size = 0;
	QUEUE_NODE* find = queue->front;
	for(; find; find = find->next)size++;
	return size;
}
/***************************************************************
 *单向链表定义
 */
//创建节点
static LIST_NODE_D* create_list_node(int data)
{
	LIST_NODE_D* node = malloc(sizeof(LIST_NODE_D));
	node->data = data;
	node->next = NULL;
	return node;
}
//销毁节点
static LIST_NODE_D* destroy_list_node(LIST_NODE_D* node)
{
	LIST_NODE_D* next = node->next;
	free(node);
	return next;
}
//初始化
void list_d_init(LIST_D* list)
{
	list->head = NULL;
	list->tail = NULL;
	list->frwd = NULL;
}
//释放化
void list_d_deinit(LIST_D* list)
{
	while(list->head){
		list->head = destroy_list_node(list->head);
	}list->tail = NULL;
	list->frwd = NULL;
}
//判断空
int list_d_empty(LIST_D* list)
{
	return !list->head && !list->tail;
}
//追加
void list_d_append(LIST_D* list, int data)
{
	LIST_NODE_D* node = create_list_node(data);
	if(list->tail){
		list->tail->next = node;
	}else list->head = node;
	list->tail = node;
}
//迭代
void list_d_iterative(LIST_D* list)
{
	list->frwd = list->head;
}
//元素数量
size_t list_d_size(LIST_D* list)
{
	size_t size = 0;
	LIST_NODE_D* find = list->head;
	for(; find; find = find->next)size++;
	return size;
}
//正向打印
void list_d_print(LIST_D* list)
{
	LIST_NODE_D* node = list->frwd;
	for(; node; node = node->next){
		printf("%d\t", node->data);
	}printf("\n");
}
//反向打印-(递归)
void rprint(LIST_NODE_D* frwd)
{
	if(frwd){
		rprint(frwd->next);
		printf("%d\t", frwd->data);
	}
}
//反向打印(递归)
void list_d_rprint(LIST_D* list)
{
	rprint(list->frwd);
	printf("\n");
}
//逆转链表-(递归)
void reverse(LIST_NODE_D* head)
{
	if(head && head->next){
		reverse(head->next);
		head->next->next = head;
		head->next = NULL;
	}
}
//逆转链表(递归)
void list_d_reverse(LIST_D* list)
{
	reverse(list->head);
	LIST_NODE_D* temp = list->head;
	list->head = list->tail;
	list->tail = temp;
	list->frwd = list->head;
}
//获中间值
int list_d_mid(LIST_D* list)
{
	LIST_NODE_D *node = NULL, *mid = NULL;
	for(node = mid = list->frwd; node->next && node->next->next;
		mid = mid->next, node = node->next->next);
	return mid->data;
}
/***************************************************************
 *双向链表定义
 */
//创建节点
static LIST_NODE_S* create_lists_node(int data, LIST_NODE_S* next, LIST_NODE_S* prev){
    LIST_NODE_S* node = malloc(sizeof(LIST_NODE_S));
    node->data = data;
    node->next = next;
    node->prev = prev;
    return node;
}
//销毁节点
static LIST_NODE_S* destroy_lists_node(LIST_NODE_S* node, LIST_NODE_S** prev){
    LIST_NODE_S* next = node->next;
    if(prev) *prev = node->prev;
    free(node);
    return next;
}
//初始化链表
void list_s_init(LIST_S* list){
    list->head = NULL;
    list->tail = NULL;
    list->frwd = NULL;
}
//释放化链表
void list_s_deinit(LIST_S* list){
    while(list->head){
        list->head = destroy_lists_node(list->head, NULL);
    }
    list->tail = NULL;
    list->frwd = NULL;
}
//判断链表空
int list_s_empty(LIST_S* list){
    return !list->head && !list->tail;
}
//追加元素
void list_s_append(LIST_S* list, int data){
    list->tail = create_lists_node(data, NULL, list->tail);
    if(list->tail->prev){
        list->tail->prev->next = list->tail;
    }else{
        list->head = list->tail;
    }
}
//插入元素(位置按前插)
int list_s_insert(LIST_S* list, size_t pos, int data){
    LIST_NODE_S* find = list->head;
    for(; find; find = find->next){
        if(!pos--){
            LIST_NODE_S* node = create_lists_node(data, find, find->prev);
            if(node->prev){
                node->prev->next = node;
            }else list->head = node;
            node->next->prev = node;
            return 1;
        }
    }
    return 0;
}
//删除元素(按位置删除)
int list_s_erase(LIST_S* list, size_t pos){
    LIST_NODE_S* find = list->head;
    for(; find; find = find->next){
        if(!pos--){
            LIST_NODE_S* prev = NULL;
            LIST_NODE_S* next = destroy_lists_node(find, &prev);
            if(prev){
                prev->next = next;
            }else list->head = next;
            if(next){
                next->prev = prev;
            }else list->tail = prev;
            return 1;
        }
    }
    return 0;
}
//删除元素(相同元素全删除)
void list_s_remove(LIST_S* list, int data){
    LIST_NODE_S* find = list->head;
    LIST_NODE_S* next = NULL;
    for(; find; find = next){
        next = find->next;
        if(find->data == data){
            LIST_NODE_S* prev = NULL;
            LIST_NODE_S* next = destroy_lists_node(find, &prev);
            if(prev){
                prev->next = next;
            }else list->head = next;
            if(next){
                next->prev = prev;
            }else list->tail = prev;
        }
    }
}
//全删元素
void list_s_clear(LIST_S* list){
    list_s_deinit(list);
}
//查看元素(按位置取值)
int* list_s_at(LIST_S* list, size_t pos){
    LIST_NODE_S* find = list->head;
    for(; find; find = find->next){
        if(!pos--) return &find->data;
    }
    return NULL;
}
//元素数量
size_t list_s_size(LIST_S* list){
    size_t size = 0;
    LIST_NODE_S* find = list->head;
    for(; find; find = find->next)size++;
    return size;
}
//正向迭代
void list_s_begin(LIST_S* list){
    list->frwd = list->head;
}
//向前迭
int* list_s_next(LIST_S* list){
    int* data = &list->frwd->data;
    list->frwd = list->frwd->next;
    return data;
}
//反向迭代
void list_s_reverse(LIST_S* list){
    list->frwd = list->tail;
}
//向后迭
int* list_s_prev(LIST_S* list){
    int* data = &list->frwd->data;
    list->frwd = list->frwd->prev;
    return data;
}
//当前迭代(当前值)
int* list_s_current(LIST_S* list){
    return &list->frwd->data;
}
//判断迭代结束
int list_s_end(LIST_S* list){
    return !list->frwd;
}
/***************************************************************
 *有序二叉树链式定义
 */
//创建节点
static BSTREE_NODE* create_bstree_node(int data){
    BSTREE_NODE* node = malloc(sizeof(BSTREE_NODE));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
//销毁节点
static void destroy_bstree_node(BSTREE_NODE* node){
    free(node);//销毁的是叶节点
}
/*______________________________________________________________
递归函数区*/
//释放化二叉树递归
static void clear(BSTREE_NODE** root){
    if(*root){
    //销毁:左子树->右子树->节点
        clear(&(*root)->left);
        clear(&(*root)->right);
        destroy_bstree_node(*root);
        *root = NULL;
    }
}
//插入元素递归
static void insert(BSTREE_NODE* node, BSTREE_NODE** root){
    if(! *root) *root = node;
    else if(node){
        if(node->data < (*root)->data)
            insert(node, &(*root)->left);
        else insert(node, &(*root)->right);
    }
}
//查找元素—辅助删除/查找递归
static BSTREE_NODE** find(int data, BSTREE_NODE** root){
    if(! *root) return root;
    else{
        if(data == (*root)->data) return root;
        else if(data < (*root)->data)
            return find(data, &(*root)->left);
        else return find(data, &(*root)->right);
    }
}
//中序遍历递归
static void travel(BSTREE_NODE* root){
    if(root){
        travel(root->left);//L
        printf("%d ", root->data);//D
        travel(root->right);//R
    }
}
//树的层数递归
static size_t height(BSTREE_NODE* root){
    if(root){
        size_t left = height(root->left);
        size_t right = height(root->right);
        return (left > right ? left : right) + 1;
    }
    return 0;
}
//______________________________________________________________
//初始化二叉树
void bstree_init(BSTREE* bstree){
    bstree->root = NULL;
    bstree->size = 0;
}
//释放化二叉树(递归)
void bstree_deinit(BSTREE* bstree){
    clear(&bstree->root);
    bstree->size = 0;
}
//插入元素(递归)
void bstree_insert(BSTREE* bstree, int data){
    insert(create_bstree_node(data), &bstree->root);
    bstree->size++;
}
//删除元素(递归)
int bstree_erase(BSTREE* bstree, int data){
    BSTREE_NODE** node = find(data, &bstree->root);
    if(*node){
    //删除:左插入右->替换掉父节点->删除
        insert((*node)->left, &(*node)->right);
        BSTREE_NODE* temp = *node;
        *node = (*node)->right;
        destroy_bstree_node(temp);
        bstree->size--;
        return 1;
    }
    return 0;
}
//清空元素
void bstree_clear(BSTREE* bstree){
    bstree_deinit(bstree);
}
//修改元素
void bstree_update(BSTREE* bstree, int old, int New){
    while(bstree_erase(bstree, old))
        bstree_insert(bstree, New);
}
//查询元素(递归)
int bstree_exist(BSTREE* bstree, int data){
    return *find(data, &bstree->root) != NULL;
}
//中序遍历(递归)
void bstree_travel(BSTREE* bstree){
    travel(bstree->root);
    printf("\n");
}
//元素数量
size_t bstree_size(BSTREE* bstree){
    return bstree->size;
}
//树的层数(递归)
size_t bstree_height(BSTREE* bstree){
    return height(bstree->root);
}

#include "data_structure.h"
/**
 *C实现:实现函数测试
 */
//栈的顺序存储结构测试
void test_stack_sx(void) {
	int i;
	STACK_SX stack_sx;
	stack_sx_init(&stack_sx, 5); //初始
	for(i = 0; !stack_sx_full(&stack_sx); i++){ //判断满后退出
		stack_sx_push(&stack_sx, i+1); //入栈
	}
	printf("栈顶=%d\n", stack_sx_top(&stack_sx)); //栈顶
	printf("数量=%d\n", stack_sx_size(&stack_sx)); //数量
	while(!stack_sx_empty(&stack_sx)){ //判断空后,不在出栈
		printf("%d\n", stack_sx_pop(&stack_sx)); //出栈
	}
	stack_sx_deinit(&stack_sx); //释放
}
//栈的链式存储结构测试
void test_stack_ls(void) {
	int i;
	STACK_LS stack_ls;
	stack_ls_init(&stack_ls); //初始
	for(i = 0; i < 5; i++){
		stack_ls_push(&stack_ls, i+1); //入栈
	}
	printf("栈顶=%d\n", stack_ls_top(&stack_ls)); //栈顶
	printf("数量=%d\n", stack_ls_size(&stack_ls)); //数量
	while(!stack_ls_empty(&stack_ls)){ //判断空,不在出栈
		printf("%d\n", stack_ls_pop(&stack_ls)); //出栈
	}
	stack_ls_deinit(&stack_ls); //释放
}
//队列的顺序存储结构测试
void test_queue_sx(void) {
	int i;
	QUEUE_SX queue_sx;
	queue_sx_init(&queue_sx, 5);//初始
	for(i = 0; !queue_sx_full(&queue_sx); i++){//判断满后退出
		queue_sx_push(&queue_sx, i+1);//入队
	}
	printf("队首=%d\n", queue_sx_front(&queue_sx));//队首
	printf("数量=%d\n", queue_sx_size(&queue_sx));//数量
	while(!queue_sx_empty(&queue_sx)){//判断空后,不再出队
		printf("%d\n", queue_sx_pop(&queue_sx));//出队
	}
	queue_sx_deinit(&queue_sx);//释放
}
//队列的链式存储结构测试
void test_queue_ls(void) {
	int i;
	QUEUE_LS queue_ls;
	queue_ls_init(&queue_ls);//初始
	for(i = 0; i < 5; i++){
		queue_ls_push(&queue_ls, i+1);//入队
	}
	printf("队首=%d\n", queue_ls_front(&queue_ls));//队首
	printf("数量=%d\n", queue_ls_size(&queue_ls));//数量
	while(!queue_ls_empty(&queue_ls)){//判断空,不再出队
		printf("%d\n", queue_ls_pop(&queue_ls));//出队
	}
	queue_ls_deinit(&queue_ls);//释放
}
//单向链表的测试
void test_list_d(void) {
	int i;
	LIST_D list_d;
	list_d_init(&list_d);//初始
	for(i = 0; i < 5; i++){
		list_d_append(&list_d, i+1);//追加元素
	}
	list_d_iterative(&list_d);//迭代
	printf("正向打印:\n");
	list_d_print(&list_d);//正向打印
	printf("反向打印:\n");
	list_d_rprint(&list_d);//反向打印
	printf("逆转链表,正向打印:\n");
	list_d_reverse(&list_d); list_d_print(&list_d);
	printf("中间值mid = %d\n", list_d_mid(&list_d));
	list_d_deinit(&list_d);//释放
}
//双向链表的测试
void test_list_s(void) {
    int i;
	LIST_S lists;
    list_s_init(&lists);//初始
    for(i = 0; i < 10; i++){
        list_s_append(&lists, (i+1)*10);//追加
    }
    list_s_insert(&lists, 2, 25);//前插(2的位置是30前插)
    list_s_erase(&lists, 3);//位置删除(3的位置还是30将删)
    //追加(为了测相同数据删除)
	list_s_append(&lists, 25);
    //相同数据删除(2的位置25删除)与(后面追加的25删除)
	list_s_remove(&lists, 25);
	//位置取数据,(2的位置当前是40)
    printf("取2位置=%d\n", *list_s_at(&lists, 2));
    //正向遍历
	list_s_begin(&lists);
    //返回frwd(返回当前是否是头数据)
	printf("frwd头数据=%d\n", *list_s_current(&lists));
    while(!list_s_end(&lists)){//判断结束frwd迭代
        printf("%d\n", *list_s_next(&lists));//向前迭代观察数据
    }
	printf("数量=%d\n", list_s_size(&lists));//元素数量
	//全销毁数据(就是调用list_s_deinit)
    list_s_clear(&lists);
    printf("数据为空%d\n", !list_s_empty(&lists));//为空0
	printf("数量=%d\n", list_s_size(&lists));//元素数量
    list_s_deinit(&lists);//释放
}
//有序二叉树的测试
void test_bstree(void) {
    BSTREE bstree;  bstree_init(&bstree);//初始化有序二叉树
    bstree_insert(&bstree, 50);//插入元素
    bstree_insert(&bstree, 70);
    bstree_insert(&bstree, 20);
    bstree_insert(&bstree, 60);
    bstree_insert(&bstree, 40);
    bstree_insert(&bstree, 30);
    bstree_insert(&bstree, 10);
    bstree_insert(&bstree, 90);
    bstree_insert(&bstree, 80);
    bstree_travel(&bstree);//中序遍历
    printf("元素=%d, 层数=%d\n", bstree_size(&bstree), bstree_height(&bstree));
    bstree_erase(&bstree, 60);//删除元素
    bstree_travel(&bstree);
    printf("元素=%d, 层数=%d\n", bstree_size(&bstree), bstree_height(&bstree));
    bstree_update(&bstree, 70, 77);//修改所有相同70的数变成77
    bstree_travel(&bstree);
    printf("元素=%d, 层数=%d, 查找=%d\n", bstree_size(&bstree), bstree_height(&bstree), bstree_exist(&bstree, 70));
    bstree_deinit(&bstree);//释放化有序二叉树
    bstree_travel(&bstree);
    printf("元素=%d, 层数=%d\n", bstree_size(&bstree), bstree_height(&bstree));
}

int main()
{
    test_stack_sx(); //栈的顺序存储结构测试
    test_stack_ls(); //栈的链式存储结构测试
    test_queue_sx(); //队列的顺序存储结构测试
    test_queue_ls(); //队列的链式存储结构测试
    test_list_d(); //单向链表的测试
    test_list_s(); //双向链表的测试
    test_bstree(); //有序二叉树的测试
    return 0;
}

测试结果

stack、queue、list、bstree

相关标签: C数据结构