网站建设 >

查看其它板块

数据结构C语言描述-创新互联

高级数据结构 1顺序存储线性表

顺序存储线性表由数组来实现，就和java中的ArrayList一样

10年积累的网站设计、网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先做网站后付款的网站建设流程，更有龙陵免费网站建设让你可以放心的选择与我们合作。

头文件

#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");
}

2 单向链表 2.1 单向链表

头文件

#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;
}

2.2 单向循环链表

单向循环链表解决约瑟夫环问题

头文件

#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");
}

3 双向链表 3.1 用指针来存储data

头文件

#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;
}

3.2 用变长结构体来存储data

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;
}

3.3 面向对象封装

所谓的面向对象封装就是将针对链表的方法全部封装到结构体中去（函数指针），然后调用方法时就可以直接通过链表名来进行调用，修改后的头文件如下：

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;
}

4 栈 4.1 顺序存储栈

头文件

#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;
}

4.2 链式存储栈

头文件

#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);
}

4.3 栈应用——计算器的实现

两个栈，一个用来存储操作符，一个用来存储数据

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;
}

5 队列 5.1 顺序存储队列

头文件

#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;
}

5.2 链式存储队列

头文件

#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);
}

5.3 队列的应用——求中算法的实现

#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;
}

6 二叉树

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;
}

7 平衡二叉树

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;
}

8 树和广义表

#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;
}

9 字典树

头文件

#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语言描述-创新互联
文章转载：http://cdkjz.cn/article/dgdcsj.html

返回首页了解更多建站资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线成都：13518219792 座机：028-86922220

在线咨询提交需求

友情链接交换友情链接

中国电信西部信息中心机房新网创想四川国泰民安消防抖音代运营温江服务器托管成都网站推广网站设计光彩外墙景观成都导视系统设计都江堰做网站

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层建设咨询028-86922220

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图

网站建设

网站推广

案例

方案

电商网站开发

微信小程序

我们

联系

精准传达 • 有效沟通

查看其它板块

数据结构C语言描述-创新互联

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

大客户专线成都：13518219792 座机：028-86922220

友情链接交换友情链接

网络推广

Network promotion

网站方案

Solution

电商网站开发

E-commerce & System

我们

About Us

联系

Contact Us

精准传达 • 有效沟通

查看其它板块

数据结构C语言描述-创新互联

相关资讯

mclinux命令 linux mc命令

phppdo输出数据 php的输出方式有哪些

go语言学习线路掘金 go语言入门项目

mysql字段值怎么修改 mysql修改字段数值

go语言简洁 go语言写什么

php数据库取出数组中 php取数据库中某个字段的值

python线条函数 python绘制直线

mysql怎么把时间设短 mysql 时间字段

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

大客户专线 成都：13518219792 座机：028-86922220

友情链接 交换友情链接

大客户专线成都：13518219792 座机：028-86922220

友情链接交换友情链接