数据结构C语言描述-创新互联
高级数据结构
1顺序存储线性表
当前标题：数据结构C语言描述-创新互联
URL标题：http://pwwzsj.com/article/dgdcsj.html
顺序存储线性表由数组来实现，就和java中的ArrayList一样
头文件
#ifndef REMOTE_SERVER_SQLIST_H
#define REMOTE_SERVER_SQLIST_H
#endif //REMOTE_SERVER_SQLIST_H
#define DATASIZE 1024
typedef int datatype;
typedef struct {datatype data[DATASIZE];
int last;
} sqlist;
//初始化列表
sqlist * sqlist_create();
void sqlist_create1(sqlist **);
//增加数据
datatype sqlist_insert(sqlist *, datatype *, int idx);
//删除数据
datatype sqlist_delete(sqlist *, int idx);
//查询数据,返回下标
int sqlist_find(sqlist *, datatype *);
//线性表是否清空
int sqlist_isEmpty(sqlist *);实现
#include "sqlist.h"
#include#include//初始化列表
sqlist * sqlist_create() {sqlist * lst = malloc(sizeof (sqlist));
if (lst == NULL) {return NULL;
}
lst->last = -1;
return lst;
}
void sqlist_create1(sqlist **lst) {*lst = malloc(sizeof (sqlist));
if (*lst == NULL) return;
(*lst)->last = -1;
return;
}
//增加数据
datatype sqlist_insert(sqlist * lst, datatype * data, int idx) {if (lst == NULL) return -1;
if (lst->last == DATASIZE - 1) return -1;
if (idx< 0 || idx >lst->last + 1) return -1;
for (int i = lst->last + 1; i >= idx + 1; i--) {lst->data[i] = lst->data[i - 1];
}
lst->data[idx] = *data;
lst->last++;
return *data;
}
//删除数据
datatype sqlist_delete(sqlist * lst, int idx) {if (lst == NULL || idx< 0 || idx >lst->last) return -1;
datatype tmp = lst->data[idx];
for (int i = idx; i< lst->last; i++) {lst->data[i] = lst->data[i + 1];
}
lst->data[lst->last] = 0;
lst->last--;
return tmp;
};
//查询数据,返回下标
int sqlist_find(sqlist * lst, datatype * data) {if (lst == NULL) return -1;
for (int i = 0; i<= lst->last; i++) {if (lst->data[i] == *data) {return i;
}
}
return -1;
}
//线性表是否清空
int sqlist_isEmpty(sqlist * lst) {if (lst == NULL || lst->last == -1) return 1;
return 0;
}
//将线性表清空
int sqlist_setEmpty(sqlist * lst) {if (lst == NULL) return -1;
for (int i = 0; i<= lst->last; i++) lst->data[i] = 0;
lst->last = -1;
return 0;
}
//查询元素数量
int sqlist_size(sqlist * lst) {if (lst == NULL) return 0;
return lst->last + 1;
}
//合并线性表
int sqlist_union(sqlist * dest, const sqlist * src) {if (dest->last + src->last + 2 >DATASIZE) return -1;
for (int i = dest->last + 1; i< dest->last + src->last + 2; i++) {dest->data[i] = src->data[i - dest->last - 1];
}
dest->last += src->last + 1;
return 0;
}
//销毁列表
int sqlist_destroy(sqlist * lst) {free(lst);
}
//遍历输出列表
void sqlist_display(sqlist * lst) {for (int i = 0; i<= lst->last; i++) {printf("%d ", lst->data[i]);
}
printf("\n");
} 头文件
#ifndef REMOTE_SERVER_LINKEDLIST_H
#define REMOTE_SERVER_LINKEDLIST_H
#endif //REMOTE_SERVER_LINKEDLIST_H
typedef int datatype;
typedef struct ListNode{datatype data;
struct ListNode * next;
} ListNode;
typedef struct {ListNode * head;
int size;
} LinkedList;
//初始化链表
LinkedList * list_create();
//链表中指定位置插入节点
int list_insert_at(LinkedList *, int idx, datatype *);
//按序插入
int list_order_insert(LinkedList *, datatype *);
//删除指定位置节点
datatype list_delete_at(LinkedList *, int idx);
//删除某个值
datatype list_delete(LinkedList *, datatype *);
//判断是否为空
int list_isEmpty(LinkedList *);
//返回链表的大小
int list_size(LinkedList *);
//打印整个链表
void list_display(LinkedList *);
//销毁链表
void list_destory(LinkedList **);实现
#include "linkedList.h"
#include#include//初始化链表
LinkedList * list_create() {LinkedList * lst = malloc(sizeof (LinkedList));
if (lst == NULL) return NULL;
lst->size = 0;
lst->head = malloc(sizeof (ListNode));
lst->head->next = NULL;
return lst;
}
//链表中指定位置插入节点
int list_insert_at(LinkedList * lst, int idx, datatype * data) {if (idx< 0 || idx >lst->size) return -1;
ListNode * pre = lst->head;
ListNode * cur = lst->head->next;
ListNode * node = malloc(sizeof (ListNode));
if (node == NULL) return -1;
node->next = NULL;
node->data = *data;
for (int i = 0; i< idx; i++) {pre = cur;
cur = cur->next;
}
pre->next = node;
node->next = cur;
lst->size++;
return 0;
}
//按序插入
int list_order_insert(LinkedList * lst, datatype * data) {return list_insert_at(lst, lst->size, data);
}
//删除指定位置节点
datatype list_delete_at(LinkedList * lst, int idx) {if (idx< 0 || idx >= lst->size) return -1;
ListNode * pre = lst->head;
ListNode * cur = lst->head->next;
for (int i = 0; i< idx; i++) {pre = cur;
cur = cur->next;
}
pre->next = cur->next;
datatype ret = cur->data;
free(cur);
cur = NULL;
lst->size--;
return ret;
}
//删除某个值
datatype list_delete(LinkedList * lst, datatype * data) {ListNode * pre = lst->head;
ListNode * cur = lst->head->next;
while (cur != NULL) {if (cur->data == *data) {pre->next = cur->next;
free(cur);
lst->size--;
cur = pre->next;
} else {pre = cur;
cur = cur->next;
}
}
return *data;
}
//判断是否为空
int list_isEmpty(LinkedList * lst) {if (lst == NULL) return 1;
return lst->size == 0;
}
//返回链表的大小
int list_size(LinkedList * lst) {if (lst == NULL) return 0;
return lst->size;
}
//打印整个链表
void list_display(LinkedList * lst) {ListNode * cur = lst->head->next;
while (cur != NULL) {printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//销毁链表
void list_destory(LinkedList ** lst) {ListNode * cur = (*lst)->head;
while (cur != NULL) {ListNode * tmp = cur->next;
free(cur);
cur = tmp;
}
free(*lst);
*lst = NULL;
} 单向循环链表解决约瑟夫环问题
头文件
#ifndef REMOTE_SERVER_LIST_H
#define REMOTE_SERVER_LIST_H
typedef int datatype;
typedef struct ListNode {datatype data;
struct ListNode * next;
} Node;
typedef struct {int size;
Node * head;
} LoopList;
//初始化单向循环链表
LoopList * looplist_create();
//在链表的第i个节点后插入节点
int looplist_insert_at(LoopList ** lst, datatype * data, int idx);
//删除链表的第i个节点
datatype looplist_deleteat(LoopList ** lst, int idx);
//返回链表中的元素个数
int looplist_size(LoopList * lst);
//判断链表是否为空
int looplist_isEmpty(LoopList * lst);
//打印链表
void looplist_show(LoopList * lst);
#endif //REMOTE_SERVER_LIST_H实现
#include#include#include "list.h"
//初始化单向循环链表
LoopList * looplist_create() {LoopList * lst = NULL;
lst = malloc(sizeof (LoopList));
if (lst == NULL) return NULL;
lst->size = 0;
lst->head = NULL;
return lst;
}
//在链表的第i个节点后插入节点
int looplist_insert_at(LoopList ** lst, datatype * data, int idx) {Node * node = malloc(sizeof (Node));
node->data = *data;
if ((*lst)->head == NULL && idx == 0) {(*lst)->head = node;
node->next = node;
(*lst)->size++;
return 0;
}
if (idx< 0 || idx >= (*lst)->size) return -1;
Node * cur = (*lst)->head;
for (int i = 0; i< idx; i++) {cur = cur->next;
}
Node * tmp = cur->next;
cur->next = node;
node->next = tmp;
(*lst)->size++;
return 0;
}
//删除当前链表的往后i个节点
datatype looplist_deleteat(LoopList ** lst, int i) {if (i< 0) return -1;
Node * pre = NULL;
Node * cur = (*lst)->head;
datatype ret;
if (cur->next == cur) {ret = cur->data;
free(cur);
cur = NULL;
(*lst)->size--;
(*lst)->head = NULL;
return ret;
}
if (i == 0) i = (*lst)->size;
for (int j = 0; j< i; j++) {pre = cur;
cur = cur->next;
}
ret = cur->data;
Node * tmp = cur->next;
pre->next = tmp;
free(cur);
cur = NULL;
(*lst)->head = tmp;
(*lst)->size--;
return ret;
}
//返回链表中的元素个数
int looplist_size(LoopList * lst) {if (lst == NULL) return 0;
return lst->size;
}
//判断链表是否为空
int looplist_isEmpty(LoopList * lst) {if (lst == NULL) return 1;
return lst->size == 0;
}
//打印链表
void looplist_show(LoopList * lst) {if (lst == NULL || lst->head == NULL) return;
Node * cur = lst->head;
do {printf("%d ", cur->data);
cur = cur->next;
} while (cur != lst->head);
printf("\n");
} 头文件
#ifndef REMOTE_SERVER_DEQUE_H
#define REMOTE_SERVER_DEQUE_H
#define LLIST_FORWARD 1
#define LLIST_BACKWARD 2
typedef void llist_op(const void *);//回调函数，打印data用
typedef int llist_cmp(const void *, const void *);//用户数据的比较的回调函数
typedef struct llist_node_st {void * data;
struct llist_node_st *prev;
struct llist_node_st *next;
} deListNode;
typedef struct llist_head {deListNode *head;
int size;//size指定存储数据的大小
int cnt;//记录链表的大小
} deList;
//创建链表
deList * llist_create(int initsize);
//插入数据
int llist_insert(deList *lst, const void *data, int mode);
//查找数据
void * llist_find(deList *lst, const void *key, llist_cmp *);
//删除数据
int llist_delete(deList *list, const void *key, llist_cmp *);
//将某个节点脱链并将数据返回到data中
int llist_fetch(deList *list, const void *key, llist_cmp *, void * data);
//链表是否为空
int llist_isEmpty(deList * lst);
//链表的大小
int llist_size(deList * lst);
//打印链表
void llist_show(deList *lst, llist_op *);
//销毁链表
void llist_destroy(deList **);
#endif //REMOTE_SERVER_DEQUE_H实现
#include "deque.h"
#include#include#include//创建链表
deList * llist_create(int initsize) {deList * lst = NULL;
lst = malloc(sizeof (deList));
if (lst == NULL) return NULL;
lst->size = initsize;
lst->cnt = 0;
lst->head = malloc(sizeof (deListNode));
lst->head->data = NULL;
lst->head->next = lst->head;
lst->head->prev = lst->head;
return lst;
}
//插入数据
int llist_insert(deList *lst, const void *data, int mode) {deListNode *node = malloc(sizeof (deListNode));
if (node == NULL) return -1;
node->data = malloc(lst->size);
if (node->data == NULL) return -2;
memcpy(node->data, data, lst->size);
if (mode == LLIST_FORWARD) {node->prev = lst->head;
node->next = lst->head->next;
} else if (mode == LLIST_BACKWARD){node->next = lst->head;
node->prev = lst->head->prev;
} else {return -3;
}
node->prev->next = node;
node->next->prev = node;
lst->cnt++;
return 0;
}
//返回头结点则说明没找到
static deListNode * find_(deList *lst, const void * key, llist_cmp *cmp) {deListNode * cur = lst->head->next;
while (cur != lst->head) {if (cmp(key, cur->data) == 0) {break;
}
cur = cur->next;
}
return cur;
}
//查找数据，找不到则返回的是头结点的data(NULL)
void * llist_find(deList *lst, const void * key, llist_cmp *cmp) {return find_(lst, key, cmp)->data;
}
//删除数据
int llist_delete(deList *list, const void *key, llist_cmp *cmp) {deListNode *node = find_(list, key, cmp);
if (node == list->head) return -1;
node->prev->next = node->next;
node->next->prev = node->prev;
free(node->data);
free(node);
list->cnt--;
return 0;
}
//将某个节点脱链
int llist_fetch(deList *list, const void *key, llist_cmp *cmp, void *data) {deListNode *node = find_(list, key, cmp);
if (node == list->head) return -1;
node->prev->next = node->next;
node->next->prev = node->prev;
if (data != NULL) {memcpy(data, node->data, list->size);
}
free(node->data);
free(node);
list->cnt--;
return 0;
}
//链表是否为空
int llist_isEmpty(deList * lst) {if (lst == NULL) return 1;
return lst->cnt == 0;
}
//链表的大小
int llist_size(deList * lst) {return lst->cnt;
}
//打印链表
void llist_show(deList *lst, llist_op *p) {deListNode *cur = lst->head->next;
while (cur != lst->head) {p(cur->data);
cur = cur->next;
}
}
//销毁链表
void llist_destroy(deList **lst) {deListNode *cur = (*lst)->head->next;
deListNode *tmp;
while (cur != (*lst)->head) {tmp = cur->next;
free(cur->data);
free(cur);
cur = tmp;
}
free((*lst)->head);
free(*lst);
*lst = NULL;
} 测试代码
#include#include#include "dataTool/double_list/deque.h"
#define NAMESIZE 32
typedef struct{int id;
char name[NAMESIZE];
int math;
int chinese;
} score;
void print_s(const void *r) {const score *p = r;
printf("id=%d;name=%s;math=%d;chinese=%d\n", p->id, p->name, p->math, p->chinese);
}
int id_cmp(const void *key, const void *record) {const int *k = key;
const score *r = record;
return *k - r->id;
}
int main() {deList *lst = NULL;
score tmp;
int ret;
lst = llist_create(sizeof (score));
for (int i = 0; i< 7; i++) {tmp.id = i;
snprintf(tmp.name, NAMESIZE, "std%d", i);
tmp.math = rand() % 100;
tmp.chinese = rand() % 100;
ret = llist_insert(lst, &tmp, LLIST_BACKWARD);
if (ret) exit(1);
}
printf("cnt=%d\n", lst->cnt);
llist_show(lst, print_s);
printf("\n");
int id = 3;
score *data = llist_find(lst, &id, id_cmp);
if (data == NULL) {printf("404\n");
}
print_s(data);
printf("\n");
score * fc = malloc(sizeof (score));
llist_fetch(lst, &id, id_cmp, fc);
print_s(fc);
printf("\n");
llist_show(lst, print_s);
printf("cnt=%d\n", lst->cnt);
llist_destroy(&lst);
return 0;
} 11.3.1中的实现变为如下形式
其中data就是一个占位符，在最开始申请deListNode的时候就申请相应的大小，deListNode结构体的大小变大了，这样就可以省去许多的free(node->data)，方便进行内存管理
deListNode结构体变为：
typedef struct llist_node_st {struct llist_node_st *prev;
struct llist_node_st *next;
char data[0];//变长结构体
} deListNode;#include "deque.h"
#include#include#include//创建链表
deList * llist_create(int initsize) {deList * lst = NULL;
lst = malloc(sizeof (deList));
if (lst == NULL) return NULL;
lst->size = initsize;
lst->cnt = 0;
lst->head = malloc(sizeof (deListNode));//这里的head是没有data的，只有前驱和后驱指针
lst->head->next = lst->head;
lst->head->prev = lst->head;
return lst;
}
//插入数据
int llist_insert(deList *lst, const void *data, int mode) {deListNode *node = malloc(sizeof (deListNode) + lst->size);
if (node == NULL) return -1;
memcpy(node->data, data, lst->size);
if (mode == LLIST_FORWARD) {node->prev = lst->head;
node->next = lst->head->next;
} else if (mode == LLIST_BACKWARD){node->next = lst->head;
node->prev = lst->head->prev;
} else {return -3;
}
node->prev->next = node;
node->next->prev = node;
lst->cnt++;
return 0;
}
//返回头结点则说明没找到
static deListNode * find_(deList *lst, const void * key, llist_cmp *cmp) {deListNode * cur = lst->head->next;
while (cur != lst->head) {if (cmp(key, cur->data) == 0) {break;
}
cur = cur->next;
}
return cur;
}
//查找数据，找不到则返回的是头结点的data(NULL)
void * llist_find(deList *lst, const void * key, llist_cmp *cmp) {deListNode * node;
node = find_(lst, key, cmp);
if (node == lst->head) {return NULL;
}
return node->data;
}
//删除数据
int llist_delete(deList *list, const void *key, llist_cmp *cmp) {deListNode *node = find_(list, key, cmp);
if (node == list->head) return -1;
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
list->cnt--;
return 0;
}
//将某个节点脱链
int llist_fetch(deList *list, const void *key, llist_cmp *cmp, void *data) {deListNode *node = find_(list, key, cmp);
if (node == list->head) return -1;
node->prev->next = node->next;
node->next->prev = node->prev;
if (data != NULL) {memcpy(data, node->data, list->size);
}
free(node);
list->cnt--;
return 0;
}
//链表是否为空
int llist_isEmpty(deList * lst) {if (lst == NULL) return 1;
return lst->cnt == 0;
}
//链表的大小
int llist_size(deList * lst) {return lst->cnt;
}
//打印链表
void llist_show(deList *lst, llist_op *p) {deListNode *cur = lst->head->next;
while (cur != lst->head) {p(cur->data);
cur = cur->next;
}
}
//销毁链表
void llist_destroy(deList **lst) {deListNode *cur = (*lst)->head->next;
deListNode *tmp;
while (cur != (*lst)->head) {tmp = cur->next;
free(cur);
cur = tmp;
}
free((*lst)->head);
free(*lst);
*lst = NULL;
} 所谓的面向对象封装就是将针对链表的方法全部封装到结构体中去（函数指针），然后调用方法时就可以直接通过链表名来进行调用，修改后的头文件如下：
typedef void llist_op(const void *);//回调函数，打印data用
typedef int llist_cmp(const void *, const void *);//用户数据的比较的回调函数
typedef struct llist_node_st {struct llist_node_st *prev;
struct llist_node_st *next;
char data[0];
} deListNode;
typedef struct llist_head {deListNode *head;
int size;//size指定存储数据的大小
int cnt;//记录链表的大小
int (*insert)(struct llist_head *lst, const void *data, int mode);
void * (*find)(struct llist_head *lst, const void *key, llist_cmp *);
int (*delete)(struct llist_head *list, const void *key, llist_cmp *);
int (*fetch)(struct llist_head *list, const void *key, llist_cmp *, void * data);
int (*isEmpty)(struct llist_head * lst);
int (*getSize)(struct llist_head* lst);
void (*show)(struct llist_head *lst, llist_op *);
} deList;
//创建链表
deList * llist_create(int initsize);
//销毁链表
void llist_destroy(deList **);
#endif //REMOTE_SERVER_DEQUE_H修改后需要在链表的初始化方法中对这些函数指针进行初始化
//创建链表
deList * llist_create(int initsize) {deList * lst = NULL;
lst = malloc(sizeof (deList));
if (lst == NULL) return NULL;
lst->size = initsize;
lst->cnt = 0;
lst->head = malloc(sizeof (deListNode));
lst->head->next = lst->head;
lst->head->prev = lst->head;
lst->insert = llist_insert;
lst->delete = llist_delete;
lst->fetch = llist_fetch;
lst->find = llist_find;
lst->getSize = llist_size;
lst->isEmpty = llist_isEmpty;
lst->show = llist_show;
return lst;
}头文件
#ifndef REMOTE_SERVER_SQSTACK_H
#define REMOTE_SERVER_SQSTACK_H
#define MAXSIZE 5
typedef int datatype;
typedef struct {int top;
datatype data[MAXSIZE];
} stack;
//创建栈
stack * st_create();
//压栈
int st_push(stack *, datatype *);
//出栈
int st_pop(stack *, datatype *);
//取栈顶元素
int st_top(stack *, datatype *);
//判断栈是否为空
int st_isEmpty(stack *);
//返回栈中元素个数
int st_size(stack *);
//打印栈
void st_show(stack *);
//销毁栈
void st_destroy(stack **);
#endif //REMOTE_SERVER_SQSTACK_H实现
#include "sqStack.h"
#include#include//创建栈
stack * st_create() {stack * st = NULL;
st = malloc(sizeof (*st));
if (st == NULL) return NULL;
st->top = -1;
return st;
}
//压栈
int st_push(stack *st, datatype *p) {if (st->top == MAXSIZE - 1) return -1;
st->data[++st->top] = *p;
return 0;
}
//出栈
int st_pop(stack *st, datatype *p) {if (st == NULL || st->top == -1) return -1;
*p = st->data[st->top--];
return 0;
}
//取栈顶元素
int st_top(stack *st, datatype *p) {if (st == NULL || st->top == -1) return -1;
*p = st->data[st->top];
return 0;
}
//判断栈是否为空
int st_isEmpty(stack *st) {if (st == NULL) return 1;
return st->top == -1;
}
//返回栈中元素个数
int st_size(stack * st) {if (st == NULL) return 0;
return st->top + 1;
}
//打印栈
void st_show(stack * st) {for (int i = st->top; i >= 0; i--) {printf("%d ", st->data[i]);
}
printf("\n");
}
//销毁栈
void st_destroy(stack **st) {free(*st);
*st = NULL;
} 头文件
#ifndef REMOTE_SERVER_STACK_H
#define REMOTE_SERVER_STACK_H
#include "../double_list/deque.h"
typedef deList Stack;
//创建栈
Stack * stack_create(int);
//压栈
int stack_push(Stack *, const void *);
//出栈
int stack_pop(Stack *, void *);
//销毁栈
void stack_destroy(Stack *);
#endif //REMOTE_SERVER_STACK_H实现
#include "stack.h"
#include//这里我们自己定义一个比较函数始终返回0，这样当我们调用deque的find方法的时候每次都是在第一个节点的时候
//就直接返回，即链表头是栈顶
int always_match(const void *p, const void *r) {return 0;
}
//创建栈
Stack * stack_create(int initsize) {return llist_create(initsize);
}
//压栈
int stack_push(Stack *p, const void *data) {return p->insert(p, data, LLIST_FORWARD);
}
//出栈
int stack_pop(Stack *p, void *data) {p->fetch(p, (void *)0, always_match, data);
}
//销毁栈
void stack_destroy(Stack *p) {llist_destroy(p);
} 两个栈，一个用来存储操作符，一个用来存储数据
static int cal(int n1, int n2, char c) {if (c == '+') return n1 + n2;
if (c == '-') return n2 - n1;
if (c == '*') return n1 * n2;
if (c == '/') return n2 / n1;
}
int main() {char str[] = "((11+3)*2-5)*2+(10*5+1)";
datatype i = 0, ret = 0, n1 = 0, n2 = 0;
char c;
stack *num = st_create();
stack *op = st_create();
while (str[i] != '\0') {if (str[i] >= '0' && str[i]<= '9') {int n = 0;
for (; str[i] != '\0' && (str[i] >= '0' && str[i]<= '9'); i++) {n = n * 10 + (str[i] - '0');
}
st_push(num, &n);
i--;
} else if (str[i] == '(') {st_push(op, &str[i]);
} else if (str[i] == ')'){st_pop(op, &c);
while (c != '(') {st_pop(num, &n1);
st_pop(num, &n2);
ret = cal(n1, n2, c);
st_push(num, &ret);
st_pop(op, &c);
}
} else {if (st_isEmpty(op) || str[i] == '*' || str[i] == '/') st_push(op, &str[i]);
else {st_top(op, &c);
while (c == '*' || c == '/') {st_pop(num, &n1);
st_pop(num, &n2);
ret = cal(n1, n2, c);
st_push(num, &ret);
st_pop(op, &c);
if (st_isEmpty(op)) break;
st_top(op, &c);
}
st_push(op, &str[i]);
}
}
i++;
}
while (!st_isEmpty(op)) {st_pop(op, &c);
st_pop(num, &n1);
st_pop(num, &n2);
ret = cal(n1, n2, c);
st_push(num, &ret);
}
st_pop(num, &ret);
printf("%d\n", ret);
st_destroy(&num);
st_destroy(&op);
return 0;
}头文件
#ifndef REMOTE_SERVER_ARR_QUE_H
#define REMOTE_SERVER_ARR_QUE_H
#define MAXSIZE 6
typedef int datatype;
typedef struct {datatype data[MAXSIZE];
int head;
int tail;
int size;
} ArrayQue;
//创建队列
ArrayQue * ArrayQue_create();
//队列是否为空
int ArrayQue_isEMpty(ArrayQue *);
//入队
int ArrayQue_enter(ArrayQue *, datatype *);
//出队
int ArrayQue_deq(ArrayQue *, datatype *);
//打印队列
void ArrayQue_show(ArrayQue *);
//清空队列
int ArrayQue_clear(ArrayQue *);
//返回队列中的元素个数
int ArrayQue_size(ArrayQue *);
//销毁队列
void ArrayQue_destroy(ArrayQue **);
#endif //REMOTE_SERVER_ARR_QUE_H实现
#include "arr_que.h"
#include#include//创建队列
ArrayQue * ArrayQue_create() {ArrayQue *que = NULL;
que = malloc(sizeof (*que));
if (que == NULL) return NULL;
que->head = 0;
que->tail = 0;
que->size = 0;
return que;
}
//队列是否为空
int ArrayQue_isEMpty(ArrayQue *que) {return que->size == 0;
}
//入队
int ArrayQue_enter(ArrayQue *que, datatype *x) {if ((que->tail + 1) % MAXSIZE == que->head) return -1;
que->tail = (que->tail + 1) % MAXSIZE;
que->data[que->tail] = *x;
que->size++;
return 0;
}
//出队
int ArrayQue_deq(ArrayQue *que, datatype *x) {if (que->head == que->tail) return -1;
que->head = (que->head + 1) % MAXSIZE;
que->size--;
return 0;
}
//打印队列
void ArrayQue_show(ArrayQue *que) {if (que->head == que->tail) return;
int i = (que->head + 1) % MAXSIZE;
while (i != (que->tail + 1) % MAXSIZE) {printf("%d ", que->data[i]);
i = (i + 1) % MAXSIZE;
}
printf("\n");
}
//清空队列
int ArrayQue_clear(ArrayQue *que) {que->size = 0;
que->head = 0;
que->tail = 0;
return 0;
}
//返回队列中的元素个数
int ArrayQue_size(ArrayQue *que) {return que->size;
}
//销毁队列
void ArrayQue_destroy(ArrayQue **que) {free(*que);
*que = NULL;
} 头文件
#ifndef REMOTE_SERVER_QUEUE_H
#define REMOTE_SERVER_QUEUE_H
#include "../double_list/deque.h"
typedef deList Queue;
//创建队列
Queue * queue_create(int initsize);
//入队
int queue_en(Queue *, const void *);
//出队
int queue_de(Queue *, void *);
//销毁队列
void queue_destroy(Queue * que);
#endif //REMOTE_SERVER_QUEUE_H实现
#include#include "queue.h"
static int a_match(const void *p, const void *q) {return 0;
}
//创建队列
Queue * queue_create(int initsize) {Queue * que = llist_create(initsize);
return que;
}
//入队
int queue_en(Queue *que, const void *data) {return que->insert(que, data, LLIST_BACKWARD);
}
//出队
int queue_de(Queue *que, void *data) {return que->fetch(que, (void *) 0, a_match, data);
}
//销毁队列
void queue_destroy(Queue *que) {llist_destroy(&que);
} #define NR_BALL 27
static int check(ArrayQue *que) {int i = (que->head + 1) % SIZE;
while (i != que->tail) {if (que->data[i] >que->data[(i + 1) % SIZE]) return 0;
i = (i + 1) % SIZE;
}
return 1;
}
int main() {ArrayQue *que = ArrayQue_create();
stack *st_min = st_create();
stack *st_5min = st_create();
stack *st_h = st_create();
for (int i = 1; i<= NR_BALL; i++) {ArrayQue_enter(que, &i);
}
ArrayQue_show(que);
int t = 0, k = 0;
int time = 0;
while (1) {ArrayQue_deq(que, &t);
time++;
if (st_min->top != 3) {st_push(st_min, &t);
} else {while (!st_isEmpty(st_min)) {st_pop(st_min, &k);
ArrayQue_enter(que, &k);
}
if (st_5min->top != 10) {st_push(st_5min, &t);
} else {while (!st_isEmpty(st_5min)) {st_pop(st_5min, &k);
ArrayQue_enter(que, &k);
}
if (st_h->top != 10) {st_push(st_h, &t);
} else {while (!st_isEmpty(st_h)) {st_pop(st_h, &k);
ArrayQue_enter(que, &k);
}
ArrayQue_enter(que, &t);
if (check(que)) break;
}
}
}
}
printf("time = %d\n", time);
ArrayQue_show(que);
ArrayQue_destroy((&que));
st_destroy(&st_min);
st_destroy(&st_5min);
st_destroy(&st_h);
return 0;
}typedef struct node {int val;
struct ndoe *left, *right;
} TreeNode;
//插入元素，大的节点放右节点，小的节点放左节点，即二叉搜索树
TreeNode * insert(TreeNode *root, int val) {if (root == NULL) {TreeNode *node = malloc(sizeof (*node));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
if (val >root->val) {root->right = insert(root->right, val);
} else {root->left = insert(root->left, val);
}
return root;
}
//中序遍历
void inorder(TreeNode *root) {if (root == NULL) return;
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
//打印树
void draw(TreeNode *root, int level) {if (root == NULL) return;
draw(root->right, level + 1);
for (int i = 0; i< level; i++) {printf(" ");
}
printf("%d\n", root->val);
draw(root->left, level + 1);
}
int main() {TreeNode *root = NULL;
int arr[] = {2, 1, 4, 5, 8, 12, 9};
for (int i = 0; i< sizeof (arr) / sizeof (*arr); i++) {root = insert(root, arr[i]);
}
inorder(root);
printf("\n");
draw(root, 0);
return 0;
}11.6中二叉树的代码中加入如下balance代码就可以得到平衡二叉树的代码，这里定义平衡二叉树是左右子树中的节点数之差小于等于1
//获取树的元素个数
static int get_depth(TreeNode *root) {if (root == NULL) return 0;
return get_depth(root->left) + get_depth(root->right) + 1;
}
//左旋
static TreeNode * find_min(TreeNode *root) {if (root->left == NULL) return root;
return find_min(root->left);
}
static void turn_left(TreeNode **root) {TreeNode *cur = *root;
*root = cur->right;
cur->right = NULL;
find_min(*root)->left = cur;
}
//右旋
static TreeNode * find_max(TreeNode *root) {if (root->right == NULL) return root;
return find_max(root->right);
}
static void turn_right(TreeNode **root) {TreeNode *cur = *root;
*root = cur->left;
cur->left = NULL;
find_max(*root)->right = cur;
}
//平衡树
void balance(TreeNode **root) {if (*root == NULL) return;
int sub = 0;
while (1) {sub = get_depth((*root)->left) - get_depth((*root)->right);
if (sub >= -1 && sub<= 1) break;
if (sub< -1) {turn_left(root);
} else {turn_right(root);
}
}
balance(&(*root)->left);
balance(&(*root)->right);
}
//删除树中的一个节点
TreeNode * delete(TreeNode *root, int val) {if (root == NULL) return NULL;
if(root->val >val) root->left = delete(root->left, val);
else if(root->val< val) root->right = delete(root->right, val);
else {TreeNode *cur = NULL;
if (root->left == NULL || root->right == NULL) {cur = root->left == NULL ? root->right : root->left;
} else {*cur = root->right;
root->right = NULL;
find_min(cur)->left = root->left;
}
free(root);
return cur;
}
return root;
}#include#includetypedef struct node {int val;
struct ndoe *left, *right;
} TreeNode;
//插入元素，大的节点放右节点，小的节点放左节点，即二叉搜索树
TreeNode * insert(TreeNode *root, int val) {if (root == NULL) {TreeNode *node = malloc(sizeof (*node));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
if (val >root->val) {root->right = insert(root->right, val);
} else {root->left = insert(root->left, val);
}
return root;
}
//打印树
void draw(TreeNode *root, int level) {if (root == NULL) return;
draw(root->right, level + 1);
for (int i = 0; i< level; i++) {printf(" ");
}
printf("%d\n", root->val);
draw(root->left, level + 1);
}
//树转换为广义表
void travel(TreeNode *root) {printf("(");
if (root == NULL) {printf(")");
return;
}
printf("%d", root->val);
travel(root->left);
travel(root->right);
printf(")");
}
//广义表转换为树
TreeNode * transfer(const char *str) {static int idx = 0;
if (str[idx] == '(') idx++;
if (str[idx] == ')') {idx++;
return NULL;
}
TreeNode *root = malloc(sizeof (TreeNode));
root->val = str[idx] - '0';
idx++;
root->left = transfer(str);
root->right = transfer(str);
idx++; //读完一个支路后要idx++跳过和之前'('相应的')'
return root;
}
int main() {TreeNode *root = NULL;
int arr[] = {2, 1, 4, 5, 7, 8, 9};
for (int i = 0; i< sizeof (arr) / sizeof (*arr); i++) {root = insert(root, arr[i]);
}
draw(root, 0);
printf("\n");
travel(root);
printf("\n");
char *str = "(2(1()())(4()(5()(7()(8(9()())())))))";//树的广义表表示
root = transfer(str);
draw(root, 0);
printf("\n");
return 0;
} 头文件
#ifndef REMOTE_SERVER_TRIE_H
#define REMOTE_SERVER_TRIE_H
#include#include#includetypedef struct node{struct node *next[26];
bool isEnd;
} Trie;
Trie* trieCreate() ;
void trieInsert(Trie* obj, char * word) ;
bool trieSearch(Trie* obj, char * word) ;
bool trieStartsWith(Trie* obj, char * prefix) ;
void trieFree(Trie* obj) ;
#endif //REMOTE_SERVER_TRIE_H 实现
#include "trie.h"
#include#include#includeTrie* trieCreate() {Trie *root = malloc(sizeof (*root));
root->isEnd = false;
if (root == NULL) return NULL;
return root;
}
void trieInsert(Trie* obj, char * word) {int len = strlen(word);
int i;
char c;
Trie *cur = obj;
for (i = 0; i< len; i++) {c = word[i];
if (cur->next[c - 'a'] == NULL) {cur->next[c - 'a'] = malloc(sizeof (Trie));
cur->next[c - 'a']->isEnd = false;
}
cur = cur->next[c - 'a'];
}
cur->isEnd = true;
}
bool trieSearch(Trie* obj, char * word) {int len = strlen(word);
int i;
char c;
Trie *cur = obj;
for (i = 0; i< len; i++) {c = word[i];
if (cur->next[c - 'a'] == NULL) return false;
cur = cur->next[c -'a'];
}
return cur->isEnd;
}
bool trieStartsWith(Trie* obj, char * prefix) {int len = strlen(prefix);
int i;
char c;
Trie *cur = obj;
for (i = 0; i< len; i++) {c = prefix[i];
if (cur->next[c - 'a'] == NULL) return false;
cur = cur->next[c -'a'];
}
return true;
}
void trieFree(Trie* obj) {Trie *cur = obj;
int i;
for (i = 0; i< sizeof (obj->next) / sizeof (Trie*); i++) {cur = obj->next[i];
if (cur == NULL) continue;
trieFree(cur);
free(cur);
cur = NULL;
}
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：数据结构C语言描述-创新互联
URL标题：http://pwwzsj.com/article/dgdcsj.html
