高级数据结构 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://chengdu.cdxwcx.cn/article/dgdcsj.html