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++stack与queue模拟实现详解
-
JDK容器类List,Set,Queue源码解读
-
C#队列学习笔记:队列(Queue)和堆栈(Stack)
-
C++学习笔记——STL常用容器——stack和queue
-
STL 源码剖析读书笔记四:序列式容器之 deque、stack、queue
-
JDK容器类List,Set,Queue源码解读
-
Java集合框架之Stack Queue Deque使用详解刨析
-
C++的面向对象和泛型编程思想——STL(标准模板库)常用容器之stack、queue容器(栈与队列)
-
adb shell am stack list命令调试查看ActivityManagerService相关属性详解