高級(jí)數(shù)據(jù)結(jié)構(gòu) 1順序存儲(chǔ)線性表

順序存儲(chǔ)線性表由數(shù)組來實(shí)現(xiàn)，就和java中的ArrayList一樣

10年積累的網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先做網(wǎng)站后付款的網(wǎng)站建設(shè)流程，更有龍陵免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

頭文件

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

//增加數(shù)據(jù)
datatype sqlist_insert(sqlist *, datatype *, int idx);

//刪除數(shù)據(jù)
datatype sqlist_delete(sqlist *, int idx);

//查詢數(shù)據(jù),返回下標(biāo)
int sqlist_find(sqlist *, datatype *);

//線性表是否清空
int sqlist_isEmpty(sqlist *);

實(shí)現(xiàn)

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

//增加數(shù)據(jù)
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;
}

//刪除數(shù)據(jù)
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;
};

//查詢數(shù)據(jù),返回下標(biāo)
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;
}

//查詢?cè)財(cái)?shù)量
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();

//鏈表中指定位置插入節(jié)點(diǎn)
int list_insert_at(LinkedList *, int idx, datatype *);

//按序插入
int list_order_insert(LinkedList *, datatype *);

//刪除指定位置節(jié)點(diǎn)
datatype list_delete_at(LinkedList *, int idx);

//刪除某個(gè)值
datatype list_delete(LinkedList *, datatype *);

//判斷是否為空
int list_isEmpty(LinkedList *);

//返回鏈表的大小
int list_size(LinkedList *);

//打印整個(gè)鏈表
void list_display(LinkedList *);

//銷毀鏈表
void list_destory(LinkedList **);

實(shí)現(xiàn)

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

//鏈表中指定位置插入節(jié)點(diǎn)
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);
}

//刪除指定位置節(jié)點(diǎn)
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;
}

//刪除某個(gè)值
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;
}

//打印整個(gè)鏈表
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 單向循環(huán)鏈表

單向循環(huán)鏈表解決約瑟夫環(huán)問題

頭文件

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

//初始化單向循環(huán)鏈表
LoopList * looplist_create();

//在鏈表的第i個(gè)節(jié)點(diǎn)后插入節(jié)點(diǎn)
int looplist_insert_at(LoopList ** lst, datatype * data, int idx);

//刪除鏈表的第i個(gè)節(jié)點(diǎn)
datatype looplist_deleteat(LoopList ** lst, int idx);

//返回鏈表中的元素個(gè)數(shù)
int looplist_size(LoopList * lst);

//判斷鏈表是否為空
int looplist_isEmpty(LoopList * lst);

//打印鏈表
void looplist_show(LoopList * lst);

#endif //REMOTE_SERVER_LIST_H

實(shí)現(xiàn)

#include#include#include "list.h"

//初始化單向循環(huán)鏈表
LoopList * looplist_create() {LoopList * lst = NULL;
    lst = malloc(sizeof (LoopList));
    if (lst == NULL) return NULL;
    lst->size = 0;
    lst->head = NULL;
    return lst;
}

//在鏈表的第i個(gè)節(jié)點(diǎn)后插入節(jié)點(diǎn)
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;
}

//刪除當(dāng)前鏈表的往后i個(gè)節(jié)點(diǎn)
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;
}

//返回鏈表中的元素個(gè)數(shù)
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 用指針來存儲(chǔ)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 *);//回調(diào)函數(shù)，打印data用
typedef int llist_cmp(const void *, const void *);//用戶數(shù)據(jù)的比較的回調(diào)函數(shù)

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指定存儲(chǔ)數(shù)據(jù)的大小
    int cnt;//記錄鏈表的大小
} deList;

//創(chuàng)建鏈表
deList * llist_create(int initsize);

//插入數(shù)據(jù)
int llist_insert(deList *lst, const void *data, int mode);

//查找數(shù)據(jù)
void * llist_find(deList *lst, const void *key, llist_cmp *);

//刪除數(shù)據(jù)
int llist_delete(deList *list, const void *key, llist_cmp *);

//將某個(gè)節(jié)點(diǎn)脫鏈并將數(shù)據(jù)返回到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

實(shí)現(xiàn)

#include "deque.h"
#include#include#include//創(chuàng)建鏈表
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;
}

//插入數(shù)據(jù)
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;
}

//返回頭結(jié)點(diǎn)則說明沒找到
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;
}

//查找數(shù)據(jù)，找不到則返回的是頭結(jié)點(diǎn)的data(NULL)
void * llist_find(deList *lst, const void * key, llist_cmp *cmp) {return find_(lst, key, cmp)->data;
}

//刪除數(shù)據(jù)
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;
}

//將某個(gè)節(jié)點(diǎn)脫鏈
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 用變長結(jié)構(gòu)體來存儲(chǔ)data

11.3.1中的實(shí)現(xiàn)變?yōu)槿缦滦问?/p>

其中data就是一個(gè)占位符，在最開始申請(qǐng)deListNode的時(shí)候就申請(qǐng)相應(yīng)的大小，deListNode結(jié)構(gòu)體的大小變大了，這樣就可以省去許多的free(node->data)，方便進(jìn)行內(nèi)存管理

deListNode結(jié)構(gòu)體變?yōu)椋?/p>

typedef struct llist_node_st {struct llist_node_st *prev;
    struct llist_node_st *next;
    char data[0];//變長結(jié)構(gòu)體
} deListNode;

#include "deque.h"
#include#include#include//創(chuàng)建鏈表
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的，只有前驅(qū)和后驅(qū)指針
    lst->head->next = lst->head;
    lst->head->prev = lst->head;
    return lst;
}

//插入數(shù)據(jù)
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;
}

//返回頭結(jié)點(diǎn)則說明沒找到
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;
}

//查找數(shù)據(jù)，找不到則返回的是頭結(jié)點(diǎn)的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;
}

//刪除數(shù)據(jù)
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;
}

//將某個(gè)節(jié)點(diǎn)脫鏈
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 面向?qū)ο蠓庋b

所謂的面向?qū)ο蠓庋b就是將針對(duì)鏈表的方法全部封裝到結(jié)構(gòu)體中去（函數(shù)指針），然后調(diào)用方法時(shí)就可以直接通過鏈表名來進(jìn)行調(diào)用，修改后的頭文件如下：

typedef void llist_op(const void *);//回調(diào)函數(shù)，打印data用
typedef int llist_cmp(const void *, const void *);//用戶數(shù)據(jù)的比較的回調(diào)函數(shù)

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指定存儲(chǔ)數(shù)據(jù)的大小
    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;

//創(chuàng)建鏈表
deList * llist_create(int initsize);

//銷毀鏈表
void llist_destroy(deList **);

#endif //REMOTE_SERVER_DEQUE_H

修改后需要在鏈表的初始化方法中對(duì)這些函數(shù)指針進(jìn)行初始化

//創(chuàng)建鏈表
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 順序存儲(chǔ)棧

頭文件

#ifndef REMOTE_SERVER_SQSTACK_H
#define REMOTE_SERVER_SQSTACK_H
#define MAXSIZE 5

typedef int datatype;

typedef struct {int top;
    datatype data[MAXSIZE];
} stack;

//創(chuàng)建棧
stack * st_create();

//壓棧
int st_push(stack *, datatype *);

//出棧
int st_pop(stack *, datatype *);

//取棧頂元素
int st_top(stack *, datatype *);

//判斷棧是否為空
int st_isEmpty(stack *);

//返回棧中元素個(gè)數(shù)
int st_size(stack *);

//打印棧
void st_show(stack *);

//銷毀棧
void st_destroy(stack **);

#endif //REMOTE_SERVER_SQSTACK_H

實(shí)現(xiàn)

#include "sqStack.h"
#include#include//創(chuàng)建棧
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;
}

//返回棧中元素個(gè)數(shù)
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 鏈?zhǔn)酱鎯?chǔ)棧

頭文件

#ifndef REMOTE_SERVER_STACK_H
#define REMOTE_SERVER_STACK_H
#include "../double_list/deque.h"

typedef deList Stack;

//創(chuàng)建棧
Stack * stack_create(int);

//壓棧
int stack_push(Stack *, const void *);

//出棧
int stack_pop(Stack *, void *);

//銷毀棧
void stack_destroy(Stack *);

#endif //REMOTE_SERVER_STACK_H

實(shí)現(xiàn)

#include "stack.h"
#include//這里我們自己定義一個(gè)比較函數(shù)始終返回0，這樣當(dāng)我們調(diào)用deque的find方法的時(shí)候每次都是在第一個(gè)節(jié)點(diǎn)的時(shí)候
//就直接返回，即鏈表頭是棧頂
int always_match(const void *p, const void *r) {return 0;
}

//創(chuàng)建棧
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 棧應(yīng)用——計(jì)算器的實(shí)現(xiàn)

兩個(gè)棧，一個(gè)用來存儲(chǔ)操作符，一個(gè)用來存儲(chǔ)數(shù)據(jù)

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 隊(duì)列 5.1 順序存儲(chǔ)隊(duì)列

頭文件

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

//創(chuàng)建隊(duì)列
ArrayQue * ArrayQue_create();

//隊(duì)列是否為空
int ArrayQue_isEMpty(ArrayQue *);

//入隊(duì)
int ArrayQue_enter(ArrayQue *, datatype *);

//出隊(duì)
int ArrayQue_deq(ArrayQue *, datatype *);

//打印隊(duì)列
void ArrayQue_show(ArrayQue *);

//清空隊(duì)列
int ArrayQue_clear(ArrayQue *);

//返回隊(duì)列中的元素個(gè)數(shù)
int ArrayQue_size(ArrayQue *);

//銷毀隊(duì)列
void ArrayQue_destroy(ArrayQue **);
#endif //REMOTE_SERVER_ARR_QUE_H

實(shí)現(xiàn)

#include "arr_que.h"
#include#include//創(chuàng)建隊(duì)列
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;
}

//隊(duì)列是否為空
int ArrayQue_isEMpty(ArrayQue *que) {return que->size == 0;
}

//入隊(duì)
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;
}

//出隊(duì)
int ArrayQue_deq(ArrayQue *que, datatype *x) {if (que->head == que->tail) return -1;
    que->head = (que->head + 1) % MAXSIZE;
    que->size--;
    return 0;
}

//打印隊(duì)列
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");
}

//清空隊(duì)列
int ArrayQue_clear(ArrayQue *que) {que->size = 0;
    que->head = 0;
    que->tail = 0;
    return 0;
}

//返回隊(duì)列中的元素個(gè)數(shù)
int ArrayQue_size(ArrayQue *que) {return que->size;
}

//銷毀隊(duì)列
void ArrayQue_destroy(ArrayQue **que) {free(*que);
    *que = NULL;
}

5.2 鏈?zhǔn)酱鎯?chǔ)隊(duì)列

頭文件

#ifndef REMOTE_SERVER_QUEUE_H
#define REMOTE_SERVER_QUEUE_H

#include "../double_list/deque.h"
typedef deList Queue;

//創(chuàng)建隊(duì)列
Queue * queue_create(int initsize);

//入隊(duì)
int queue_en(Queue *, const void *);

//出隊(duì)
int queue_de(Queue *, void *);

//銷毀隊(duì)列
void queue_destroy(Queue * que);

#endif //REMOTE_SERVER_QUEUE_H

實(shí)現(xiàn)

#include#include "queue.h"

static int a_match(const void *p, const void *q) {return 0;
}

//創(chuàng)建隊(duì)列
Queue * queue_create(int initsize) {Queue * que = llist_create(initsize);
    return que;
}

//入隊(duì)
int queue_en(Queue *que, const void *data) {return que->insert(que, data, LLIST_BACKWARD);
}

//出隊(duì)
int queue_de(Queue *que, void *data) {return que->fetch(que, (void *) 0, a_match, data);
}

//銷毀隊(duì)列
void queue_destroy(Queue *que) {llist_destroy(&que);
}

5.3 隊(duì)列的應(yīng)用——求中算法的實(shí)現(xiàn)

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

//插入元素，大的節(jié)點(diǎn)放右節(jié)點(diǎn)，小的節(jié)點(diǎn)放左節(jié)點(diǎn)，即二叉搜索樹
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代碼就可以得到平衡二叉樹的代碼，這里定義平衡二叉樹是左右子樹中的節(jié)點(diǎn)數(shù)之差小于等于1

//獲取樹的元素個(gè)數(shù)
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);
}

//刪除樹中的一個(gè)節(jié)點(diǎn)
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;

//插入元素，大的節(jié)點(diǎn)放右節(jié)點(diǎn)，小的節(jié)點(diǎn)放左節(jié)點(diǎn)，即二叉搜索樹
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);
}

//樹轉(zhuǎn)換為廣義表
void travel(TreeNode *root) {printf("(");
    if (root == NULL) {printf(")");
        return;
    }
    printf("%d", root->val);
    travel(root->left);
    travel(root->right);
    printf(")");
}

//廣義表轉(zhuǎn)換為樹
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++; //讀完一個(gè)支路后要idx++跳過和之前'('相應(yīng)的')'
    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

實(shí)現(xiàn)

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

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：數(shù)據(jù)結(jié)構(gòu)C語言描述-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接：http://weahome.cn/article/dgdcsj.html