数据结构与算法——C语言描述

数据结构与算法

　　三大内容：逻辑结构+存储结构+数据操作+应用实践。

线性表

　　线性表是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性，数据元素可以看成是排列在一条线上或一个环上。

　　线性表分为静态线性表和动态线性表，常见的有顺序表(静态的)、单向链表(动态的)和双向链表(动态的)。

 

// 线性表的顺序存储结构的操作实现
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;       //定义元素类型
struct List                //定义单链表结点类型
{
    ElemType *list;//存储空间基址
    int size;      //当前长度
    int MaxSize;   //当前分配的存储容量，即存储线性表的最大长度
};

//1、初始化线性表L，即进行动态存储空间分配并置L为一个空表
void InitList(struct List *L, int ms)
{
    if (ms < 0) //检查ms是否有效
    {
        printf("ms值非法！\n");
        exit(1);
    }
    L->MaxSize = ms; //置线性表初始存储容量为ms
    L->list = (ElemType *)malloc(ms * sizeof(ElemType)); //动态存储空间分配
    if (!L->list)
    {
        printf("动态存储分配失败！\n");
        exit(1);
    }
    L->size = 0; //初始置线性表为空
}

//2、清除线性表L中的所有元素，释放动态存储空间，使之成为一个空表
void ClearList(struct List *L)
{
    if (L->list != NULL)
    {
        free(L->list);
        L->list = 0;
        L->size = L->MaxSize = 0;
    }
}

//3、返回线性表L的长度，若L为空则返回0
int SizeList(struct List *L)
{
    return L->size;
}

//4、判断线性表L是否为空，若为空则返回1，否则返回0
int EmptyList(struct List *L)
{
    if (L->size == 0)
        return 1;
    else
        return 0;
}

//5、返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行
ElemType GetElem(struct List *L, int pos)
{
    if (pos < 1 || pos > L->size)
    {
        printf("元素序号越界！\n");
        exit(1);
    }
    return L->list[pos - 1];
}

//6、顺序扫描（即遍历）输出线性表L中的每个元素
void TraverseList(struct List *L)
{
    int i;
    for (i = 0; i < L->size; i++)
        printf("%d,", L->list[i]);
    printf("\n");
}

//7、从线性表L中查找值与x相等的元素（第一个），若查找成功则返回其位置（下标），否则返回-1
int FindList(struct List *L, ElemType x)
{
    int i;
    for (i = 0; i < L->size; i++) //此处类型ElemType为整型，当为字符串类型（char *）时，
        if (L->list[i] == x)      //if语句应改为: if (strcmp(L->list[i], x) == 0)
            return i;
    return -1;
}

//8、把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0
int UpdatePosList(struct List *L, int pos, ElemType x)
{
    if (pos < 1 || pos > L->size)  //若pos越界则修改失败
        return 0;
    L->list[pos - 1] = x;
    return 1;
}

//9、向线性表L的表头插入元素x
//此时需要考虑到线性表存储空间已满的情况，则需要重新分配更大的动态存储空间，具体实现如下：
void againMalloc(struct List *L)
{
    ElemType *p = realloc(L->list, 2 * L->MaxSize * sizeof(ElemType));//此处重新分配的空间为原来的2倍
    if (!p)  //重新分配失败
    {
        printf("存储空间用完！\n");
        exit(1);
    }
    L->list = p;             //使list指向新线性表空间
    L->MaxSize = 2 * L->MaxSize;
    printf("存储空间已扩大为当前的2倍！\n");//输出提示已扩充空间
}

void InserFirstList(struct List *L, ElemType x) //表头插入元素
{
    int i;
    if (L->size == L->MaxSize) //存储空间已满
        againMalloc(L);        //重新分配更大空间
    for (i = L->size - 1; i >= 0; i--)
        L->list[i + 1] = L->list[i];
    L->list[0] = x;
    L->size++;
}

//10、向线性表L的表尾插入元素x
void InsertLastList(struct List *L, ElemType x)
{
    if (L->size == L->MaxSize)
        againMalloc(L);
    L->list[L->size] = x;
    L->size++;
}

//11、向线性表L中第pos个元素位置插入元素x，若插入成功返回1，否则返回0
int InsertPosList(struct List *L, int pos, ElemType x)
{
    int i;
    if (pos < 1 || pos > L->size + 1) //pos的合法位置是第一位到最后一位的后一位之间
        return 0;
    if (L->size == L->MaxSize)
        againMalloc(L);
    for (i = L->size - 1; i >= pos - 1; i--)
        L->list[i + 1] = L->list[i];
    L->list[pos - 1] = x;
    L->size++;
    return 1;
}

//12、向有序（递增）线性表L中插入元素x，使得插入后仍然有序
void InsertOrderList(struct List *L, ElemType x)
{
    int i, j;
    if (L->size == L->MaxSize)
        againMalloc(L);
    for (i = 0; i < L->size; i++)
        if (x < L->list[i])
            break;   //此时i的值即为要插入的位置。若x比所有元素都大，则i自增后的值为size，下面的for循环不执行。
    for (j = L->size - 1; j >= i; j--)
        L->list[j + 1] = L->list[j];
    L->list[i] = x;
    L->size++;
}

//13、从线性表L中删除表头元素并返回它，若删除失败则停止程序运行
ElemType DeleteFirstList(struct List *L)
{
    ElemType temp; //临时变量，用于存储表头元素
    int i;
    if (L->size == 0)
    {
        printf("线性表为空，不能删除！\n");
        exit(1);
    }
    temp = L->list[0];
    for (i = 1; i < L->size; i++)
        L->list[i - 1] = L->list[i];
    L->size--;
    return temp;
}

//14、从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行
ElemType DeleteLastList(struct List *L)
{
    if (L->size == 0)
    {
        printf("线性表为空，不能删除！\n");
        exit(1);
    }
    L->size--;
    return L->list[L->size];
}

//15、从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行
ElemType DeletePosList(struct List *L, int pos)
{
    ElemType temp;
    int i;
    if (pos < 1 || pos > L->size)
    {
        printf("pos值越界，不能删除！\n");
        exit(1);
    }
    temp = L->list[pos - 1];
    for (i = pos; i < L->size; i++)
        L->list[i - 1] = L->list[i];
    L->size--;
    return temp;
}

//16、从线性表L中删除值为x的第一个元素，若删除成功返回1否则返回0
int DeleteValueList(struct List *L, ElemType x)
{
    int i, j;
    for (i = 0; i < L->size; i++)
        if (L->list[i] == x)
            break; //此时的i即是要删除的位置,
    if (i == L->size)//若找不到，上面的i自增后为size
        return 0;
    for (j = i + 1; j < L->size; j++)
        L->list[j - 1] = L->list[j];
    L->size--;
    return 1;
}


//主函数
void main()
{
    int a[10] = { 2,4,6,8,10,12,14,16,18,20 };
    int i;
    struct List L;
    InitList(&L, 5);                 //初始化分配线性表空间为5
    for (i = 0; i < 10; i++)
        InsertLastList(&L, a[i]);    //将数组中的元素依次插入线性表（空间不够，扩大2倍）
    InsertPosList(&L, 11, 48);       //在第11位插入48（空间不够，再次扩大2倍）
    InsertPosList(&L, 1, 64);        //在第1位插入64
    printf("%d\n", GetElem(&L, 4));  //输出第4个元素
    TraverseList(&L);                //遍历输出所有元素
    printf("%d\n", FindList(&L, 10));//查找输出数值为10的元素位置（下标）
    UpdatePosList(&L, 3, 20);        //把第三个元素修改为20
    DeleteFirstList(&L);             //删除表头元素
    DeleteFirstList(&L);
    DeleteLastList(&L);              //删除表尾元素
    DeleteLastList(&L);
    DeletePosList(&L, 5);            //删除第5个元素
    DeletePosList(&L, 7);            //删除第7个元素
    printf("%d\n", SizeList(&L));    //输出线性表长度
    printf("%d\n", EmptyList(&L));   //判断线性表是否为空
    TraverseList(&L);                //遍历输出所有元素
    ClearList(&L);                   //清空线性表，释放空间
}

链表

单链表

//线性表在单链表上的操作实现
#include<stdio.h>
#include<stdlib.h>
#define NN 12
#define MM 20
typedef int ElemType;  //定义元素类型
struct sNode           //定义单链表结点类型
{
    ElemType data;
    struct sNode* next;
};

//1、初始化线性表，即置单链表的表头指针为空
void InitList(struct sNode** HL)
{
    *HL = NULL;
}

//2、清除线性表L的所有元素，即释放单链表的所有结点，使之成为空表
void ClearList(struct sNode** HL)
{
    struct sNode *cp, *np;  //定义两个相邻结点的指针
    cp = *HL;               //头指针赋给cp
    while (cp != NULL)
    {
        np = cp->next;      //用np保存下一个结点的指针
        free(cp);           //释放cp指向的结点
        cp = np;            //使下一个结点成为当前结点
    }
    *HL = NULL;             //置单链表的表头指针为空
}

//3、返回单链表的长度
int SizeList(struct sNode* HL)
{
    int i = 0;
    while (HL != NULL)
    {
        i++;
        HL = HL->next;
    }
    return i;
}

//4、检查单链表是否为空，若为空则返回1否则返回0
int EmptyList(struct sNode* HL)
{
    if (HL == NULL)
        return 1;
    else
        return 0;
}

//5、返回单链表中第pos个结点的元素，若pos超出范围，则停止程序运行
ElemType GetElem(struct sNode* HL, int pos)
{
    int i = 0;
    if (pos < 1)
    {
        printf("pos值非法，退出运行！\n");
        exit(1);
    }
    while (HL != NULL)
    {
        i++;
        if (i == pos)
            break;
        HL = HL->next;
    }
    if (HL != NULL)
        return HL->data;
    else
    {
        printf("pos值非法，退出运行！\n");
        exit(1);
    }
}

//6、遍历一个单链表
void TraverseList(struct sNode* HL)
{
    while (HL != NULL)
    {
        printf("%d,", HL->data);
        HL = HL->next;
    }
    printf("\n");
}

//7、从单链表中查找具有给定值x的第一个元素的，成功返回结点data域的存储地址，否则返回NULL
ElemType* FindList(struct sNode* HL, ElemType x)
{
    while (HL != NULL)
    {
        if (HL->data == x)
            return &HL->data;
        else
            HL = HL->next;
    }
    return NULL;
}

//8、修改单链表中第pos个结点的值为x，成功返回1失败返回0
int UpdatePosList(struct sNode* HL, int pos, ElemType x)
{
    int i = 0;
    struct sNode* p = HL;
    while (p != NULL)
    {
        i++;
        if (pos == i)
            break;
        else
            p = p->next;
    }
    if (pos == i)
    {
        p->data = x;
        return 1;
    }
    else
        return 0;
}

//9、向单链表表头插入一个元素
void InsertFirstList(struct sNode** HL, ElemType x)
{
    struct sNode *newp;
    newp = malloc(sizeof(struct sNode));
    if (newp == NULL)
    {
        printf("内存动态空间用完，退出运行！\n");
        exit(1);
    }
    newp->data = x;
    newp->next = *HL;
    *HL = newp;          //把新节点作为新的表头结点
}

//10、向单链表的末尾添加一个元素
void InsertLastList(struct sNode** HL, ElemType x)
{
    struct sNode *newp;
    newp = malloc(sizeof(struct sNode));
    if (newp == NULL)
    {
        printf("动态内存空间用完，退出运行！\n");
        exit(1);
    }
    newp->data = x;
    newp->next = NULL;
    if (*HL == NULL)   //若原表为空
        *HL = newp;
    else
    {
        struct sNode* p = *HL;
        while (p->next != NULL)
            p = p->next;
        p->next = newp;
    }
}

//11、向单链表中第pos个结点位置插入元素x，成功返回1失败返回0
int InsertPosList(struct sNode** HL, int pos, ElemType x)
{
    int i = 0;
    struct sNode *newp;
    struct sNode *cp = *HL, *ap = NULL;
    if (pos <= 0)
    {
        printf("pos值不正确，返回0表示插入失败！\n");
        return 0;
    }
    while (cp != NULL)
    {
        i++;
        if (pos == i)
            break;
        else
        {
            ap = cp;
            cp = cp->next;
        }
    }
    newp = malloc(sizeof(struct sNode));
    if (newp == NULL)
    {
        printf("内存动态空间用完，无法插入！\n");
        return 0;
    }
    newp->data = x;
    if (ap == NULL)    //插入表头的情况
    {
        newp->next = cp;
        *HL = newp;
    }
    else              //插入到ap与cp之间的情况
    {
        newp->next = cp;
        ap->next = newp;
    }
    return 1;
}

//12、向有序单链表中插入元素x，使得插入之后仍然有序
void InsertOrderList(struct sNode** HL, ElemType x)
{
    struct sNode* cp = *HL, *ap = NULL;
    struct sNode *newp;
    newp = malloc(sizeof(struct sNode));
    if (newp == NULL)
    {
        printf("内存动态空间用完，退出运行！\n");
        exit(1);
    }
    newp->data = x;
    if (cp == NULL || x < cp->data)   //把新结点插入到表头
    {
        newp->next = cp;
        *HL = newp;
        return;
    }
    while (cp != NULL)
    {
        if (x < cp->data)
            break;
        else
        {
            ap = cp;
            cp = cp->next;
        }
    }
    newp->next = cp;  //把x结点插入到ap与cp之间
    ap->next = newp;
}

//13、从单链表中删除头结点，并返回结点值，失败则停止程序运行
ElemType DeleteFirstList(struct sNode** HL)
{
    ElemType temp;
    struct sNode* p = *HL;    //暂存表头结点指针
    if (*HL == NULL)
    {
        printf("单链表为空，无表头删除，退出运行！\n");
        exit(1);
    }
    *HL = (*HL)->next;
    temp = p->data;           //暂存表头元素
    free(p);
    return temp;
}

//14、从单链表中删除尾结点并返回它的值，失败则停止程序运行
ElemType DeleteLastList(struct sNode** HL)
{
    ElemType temp;
    struct sNode* cp = *HL;
    struct sNode* ap = NULL;
    if (cp == NULL)
    {
        printf("单链表为空，无表尾删除，退出运行！\n");
        exit(1);
    }
    while (cp->next != NULL)
    {
        ap = cp;
        cp = cp->next;
    }
    if (ap == NULL)  //若单链表只有一个结点
        *HL = (*HL)->next;
    else
        ap->next = NULL;
    temp = cp->data;
    free(cp);
    return temp; //把新节点作为新的表头结点
}

//15、从单链表删除第pos个结点并返回它的值，失败则停止程序运行
ElemType DeletePosList(struct sNode** HL, int pos)
{
    int i = 0;
    ElemType temp;
    struct sNode* cp = *HL;
    struct sNode* ap = NULL;
    if (cp == NULL || pos <= 0)
    {
        printf("单链表为空或pos值不正确，退出运行！\n");
        exit(1);
    }
    while (cp != NULL)
    {
        i++;
        if (i == pos)
            break;
        ap = cp;
        cp = cp->next;
    }
    if (cp == NULL)    //单链表中没有第pos个结点
    {
        printf("pos值不正确，退出运行！\n");
        exit(1);
    }
    if (pos == 1)   //删除表头结点
        *HL = (*HL)->next;   //或：*HL = cp->next;
    else
        ap->next = cp->next;
    temp = cp->data;
    free(cp);
    return temp;
}

//16、从单链表中删除值为x的第一个结点，成功返回1失败返回0
int DeleteValueList(struct sNode** HL, ElemType x)
{
    struct sNode* cp = *HL;
    struct sNode* ap = NULL;
    while (cp != NULL)
    {
        if (cp->data == x)
            break;
        ap = cp;
        cp = cp->next;
    }
    if (cp == NULL)    //单链表中不存在值为x的结点
        return 0;
    if (ap == NULL)    //在表头位置
        *HL = (*HL)->next;   //或：*HL = cp->next;
    else
        ap->next = cp->next;
    free(cp);
    return 1;
}


//主函数
void main()
{
    int a[NN];
    int i;
    struct sNode *p, *h, *s;
    InitList(&p);                   //初始化，置单链表表头为空
    for (i = 0; i < NN; i++)        //产生12个随机数
        a[i] = rand() % MM;
    printf("随机数序列：");
    for (i = 0; i < NN; i++)
        printf("%d,", a[i]);
    printf("\n");
    printf("随机数逆序：");
    for (i = 0; i < NN; i++)
        InsertFirstList(&p, a[i]);  //将a[i]倒序插入单链表
    TraverseList(p);                //遍历
    printf("单链表长度：%d\n", SizeList(p)); //输出单链表长度
    for (h = p; h != NULL; h = h->next)      //每个元素循环与后面的元素进行比较，删除重复数
        while (DeleteValueList(&(h->next), h->data));
    printf("去除重复数：");
    TraverseList(p);                         //遍历
    printf("单链表长度：%d\n", SizeList(p)); //输出单链表长度
    h = NULL;
    for (s = p; s != NULL; s = s->next)//将上面的单链表的值依次插入新的一个空单链表，每步插入后都有序
        InsertOrderList(&h, s->data);
    printf("有序表序列：");
    TraverseList(h);                   //遍历
    ClearList(&p);                     //清除单链表
}

 

双链表

//dlist.h
#include <stdlib.h>
#ifndef __DLIST_H__
#define __DLIAT_H__

//用c语言的方式编译
#ifdef __cplusplus
extern "C"{
#endif /* _cplusplus */

//枚举，函数的返回值类型
typedef enum _DListRet
{
    DLIST_RET_OK,
    DLIST_RET_OOM,
    DLIST_RET_STOP,
    DLIST_RET_PARAMS,
    DLIST_RET_FAIL
}DListRet;

//DList用于描述整个链表，定义在dlist.cpp中
struct _DList;
typedef struct _DList DList;

//销毁节点的回调
typedef void (*DListDataDestroyFunc)(void* ctx, void* data);
//节点数据比较回调
typedef int (*DListDataCompareFunc)(void* ctx, void* data);
//遍历链表时的回调
typedef DListRet (*DListDataVisitFunc)(void* ctx, void* data);

//可供调用者使用的链表操作函数
DList* dlist_create(DListDataDestroyFunc data_destroy, void* data_destroy_ctx);
DListRet dlist_insert(DList* thiz, size_t index, void* data);
DListRet dlist_prepend(DList* thiz, void* data);
DListRet dlist_append(DList* thiz, void* data);
DListRet dlist_delete(DList* thiz, size_t index);
DListRet dlist_get_by_index(DList* thiz, size_t index, void** data);
DListRet dlist_set_by_index(DList* thiz, size_t index, void* data);
size_t dlist_length(DList* thiz);
int dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx);
DListRet dlist_foreach(DList* thiz, DListDataVisitFunc visit, void* ctx);
void dlist_destroy(DList* thiz);

#ifdef __cplusplus
}
#endif /* _cplusplus */

#endif /* __DLIST_H__ */

 

#include "dlist.h"

//链表节点描述
typedef struct _DListNode
{
    struct _DListNode* pre;
    struct _DListNode* next;

    void* data;
}DListNode;

//链表描述
struct _DList
{
    DListNode* first;
    DListDataDestroyFunc data_destroy;
    void* data_destroy_ctx;
};

/************************** 内部使用的函数 ****************************/
//销毁一个节点的data成员，调用回调函数销毁
static void _dlist_destroy_data(DList* thiz, void* data)
{
    if (thiz->data_destroy != NULL)
    {
        thiz->data_destroy(thiz->data_destroy_ctx, data);
    }

    return;
}

//产生一个节点
static DListNode* _dlist_create_node(DList* thiz, void* data)
{
    DListNode* node = malloc(sizeof(DListNode));

    if (node != NULL)
    {
        node->pre = NULL;
        node->next = NULL;
        node->data = data;
    }
    return node;
}

//通过index获取一个节点
static DListNode* _dlist_get_node(DList* thiz, size_t index, int fail_return_last)
{
    DListNode* iter = thiz->first;

    while (iter != NULL && iter->next != NULL && index > 0)
    {
        iter = iter->next;
        index--;
    }

    if (!fail_return_last)
    {
        iter = index > 0 ? NULL : iter;
    }

    return iter;
}

//销毁一个节点
static void _dlist_destroy_node(DList* thiz, DListNode* node)
{
    if (node != NULL)
    {
        node->next = NULL;
        node->pre = NULL;
        _dlist_destroy_data(thiz, node->data);
        free(node);
    }
    return;
}

/************************** 调用者可使用的函数 ****************************/
//链表生成，参数分别为销毁节点data的回调以及回调的参数
DList* dlist_create(DListDataDestroyFunc data_destroy, void* data_destroy_ctx)
{
    DList* thiz = malloc(sizeof(DList));

    if (thiz != NULL)
    {
        thiz->first = NULL;
        thiz->data_destroy = data_destroy;
        thiz->data_destroy_ctx = data_destroy_ctx;
    }
    return thiz;
}

DListRet dlist_insert(DList* thiz, size_t index, void* data)
{
    DListNode* node = NULL;
    DListNode* cursor = NULL;

    //构造节点
    if ((node = _dlist_create_node(thiz, data)) == NULL)
    {
        return DLIST_RET_OOM;
    }

    //第一个节点
    if (thiz->first == NULL)
    {
        thiz->first = node;

        return DLIST_RET_OK;
    }

    //获取目标节点位置，1表示若超过链表长度length，则插在最后
    cursor = _dlist_get_node(thiz, index, 1);

    //插入链表中间位置
    if (index < dlist_length(thiz))
    {
        //头插
        if (thiz->first == cursor)
        {
            thiz->first = node;
        }
        //插入数据中间
        else
        {
            node->pre = cursor->pre;
            cursor->pre->next = node;

        }
        node->next = cursor;
        cursor->pre = node; 
    }
    //尾插
    else 
    {
        cursor->next = node;
        node->pre = cursor;
    }
}

//头插
DListRet dlist_prepend(DList* thiz, void* data)
{
    return dlist_insert(thiz, 0, data);
}

//尾插
DListRet dlist_append(DList* thiz, void* data)
{
    return dlist_insert(thiz, -1, data);
}

//删除一个节点
DListRet dlist_delete(DList* thiz, size_t index)
{
    //获取目标节点位置，0表示index超过length就返回NULL
    DListNode* cursor = _dlist_get_node(thiz, index, 0);

    if (cursor != NULL)
    {
        if (cursor == thiz->first)
        {
            thiz->first = cursor->next;
        }

        if (cursor->next != NULL)
        {
            cursor->pre->next = cursor->next;
        }

        if (cursor->pre != NULL)
        {
            cursor->next->pre = cursor->pre;    
        }

        _dlist_destroy_node(thiz, cursor);
    }
    return DLIST_RET_OK;
}

//通过index获取一个节点的data
DListRet dlist_get_by_index(DList* thiz, size_t index, void** data)
{
    DListNode *cursor = _dlist_get_node(thiz, index, 0);

    if (cursor != NULL)
    {
        *data = cursor->data;
    }

    return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

//通过index设置一个节点的data
DListRet dlist_set_by_index(DList* thiz, size_t index, void* data)
{
    DListNode *cursor = _dlist_get_node(thiz, index, 0);

    if (cursor != NULL)
    {
        cursor->data = data;
    }

    return cursor != NULL ? DLIST_RET_OK : DLIST_RET_FAIL;
}

//获取链表的长度
size_t dlist_length(DList* thiz)
{
    size_t length = 0;
    DListNode* iter = thiz->first;

    while (iter != NULL)
    {
        length++;
        iter = iter->next;
    }

    return length;
}

//插摘目标数据所在的节点，比较函数采用回调的方法
int dlist_find(DList* thiz, DListDataCompareFunc cmp, void* ctx)
{
    int i = 0;
    DListNode* iter = thiz->first;

    while (iter != NULL)
    {
        if (cmp(ctx, iter->data) == 0)
        {
            break;
        }
        i++;
        iter = iter->next;
    }

    return i;
}

//遍历链表，并调用回调函数
DListRet dlist_foreach(DList* thiz, DListDataVisitFunc visit, void* ctx)
{
    DListRet ret = DLIST_RET_OK;
    DListNode* iter = thiz->first;

    while (iter != NULL && ret != DLIST_RET_STOP)
    {
        ret = visit(ctx, iter->data);
        iter = iter->next;
    }

    return ret;
}

//销毁整个链表
void dlist_destroy(DList* thiz)
{
    DListNode* iter = thiz->first;
    DListNode* next = NULL;

    while (iter != NULL)
    {
        next = iter->next;
        _dlist_destroy_node(thiz, iter);
        iter = next;
    }
    thiz->first = NULL;
    free(thiz);

    return;
}

 

//main.c
#include "dlist.h"
#include <stdio.h>

DListRet print(void* ctx, void* data)
{
    printf("%c ", *(int*)data);

    return DLIST_RET_OK;
}

static void dlist_temp(void)
{
    int char_arr[] = {\'a\', \'b\', \'c\', \'d\', \'e\'};
    int i;
    char tmpc = \'A\';
    char *tmppc = &tmpc;

    DList* dlist = dlist_create(NULL, NULL);

    for (i = 0; i < 5; i++)
    {
        dlist_append(dlist, &char_arr[i]);
    }

    dlist_foreach(dlist, print, NULL);
    printf("\n");

    dlist_insert(dlist, 0, &tmpc);

    dlist_foreach(dlist, print, NULL);
    printf("\n");

    dlist_prepend(dlist, &tmpc);
    dlist_foreach(dlist, print, NULL);
    printf("\n");

    dlist_append(dlist, &tmpc);
    dlist_foreach(dlist, print, NULL);
    printf("\n");

    dlist_delete(dlist, 2);
    dlist_foreach(dlist, print, NULL);
    printf("\n");

    dlist_get_by_index(dlist, 4, (void**)&tmppc);
    printf("**tmppc = %c\n", *(char*)tmppc);
}

int main(int argc, char* argv[])
{
    dlist_temp();
    return 0;
}

队列

 

//Queue.h
#ifndef QUEUE_H
#define QUEUE_H
typedef int DataType;
 
//-----------------------单链表队列节点（QNode）------------------------------//
 
typedef struct QNode{
    
    DataType data;//存放数据的数据域
    QNode *next;//存放数据间关系的指针域next 指向下一节点
 
}QNode;
 
//-----------------------单链表队列--------队列的链式存储结构----------------//
typedef struct LinkQueue{
    QNode *front;//队头指针指向队头
    QNode *rear;//队尾指针，指向队尾
    QNode *head;//队列头节点指针，数据域为空，指针域指向数据的第一个数据元素节点（首元节点），
//当队列为空时（front == rear == head）设置此节点为了方便队列的各种操作
 
}LinkQueue;
 
//-----------------------单链表队列的基本操作-----------为了插入方便设置了头节点------//
//构造队列：init_queue(LinkQueue *queue):分配内存，初始化队列
bool  init_queue(LinkQueue *queue);
 
//队列判空：is_queue_empty(const LinkQueue * const queue):判断队列是否为空，front == rear == head;
bool is_queue_empty(const LinkQueue * const queue);
 
//队列长度：queue_length( const LinkQueue * const queue);
int queue_length( const LinkQueue * const queue);
 
//从队尾进行插入; queue_insert( LinkQueue *queue , const DataType data)
bool queue_insert( LinkQueue *queue, const DataType data);
 
//遍历队列,访问队列中的所有节点的数据域: bool queue_traverse(const LinkQueue * const queue)
bool queue_traverse(const LinkQueue * const queue);
 
 
//获取队头数据元素  front_data( const LinkQueue * const queue, DataType *data )
DataType front_data( const  LinkQueue* const queue);
 
//从队列中删除队头 delete_queue_front( LinkQueue *queue);
bool delete_queue_front( LinkQueue *queue);
 
//将队列清空 clear_queue( LinkQueue *queue);将队列中所有数据元素都清除，直到队列为空
bool clear_queue( LinkQueue *queue);
 
//销毁队列:destroy_queue(LinkQueue *queue);队列将不存在，从头到尾删除队列中的节点释放队列所指的内存
//bool destroy_queue(LinkQueue *queue);
 bool destroy_queue(LinkQueue *queue);
 
#endif

 

//---------------------------队列基本操作算法描述(c语言实现)------------------//
#include"Queue.h"
#include<stdlib.h>
#include<stdio.h>
 
//--------------构造队列：init_queue(LinkQueue *queue):分配内存，初始化队列--------------//
//功能：构造一个空队列queue
//函数参数：queue 为指向队列的指针
//返回值：构造成功 返回true(1),构造失败 返回false(0)
//时间复杂度:O(1)
//测试用例{queue == NULL ,queuef != NULL}
 
bool  init_queue(LinkQueue *queue){
 
    if( queue == NULL)//当参数为指针时要判空
        exit(-1);//为空，进程结束，异常退出
 
    //生成一个QNode 类型的头节点（此节点数据域data不包含任何数据，指针域next指向队列的第一个节点，
    //当队列为空时（是指队列任何已经存在，但队列中没有任何数据）queue->rear == queue->front == head;
    
    queue->head =(QNode*)malloc(sizeof(QNode));//为队列生成一个头节点（方便插入和删除）
    queue->head->data = 0;
    queue->head->next = NULL;//节点必须初始化 
 
    if( queue->head == NULL )//内存分配失败，进程异常退出
        exit(-1);
 
    else{
        queue->front = queue->rear = queue -> head;//构造了一个空队列
        return true;
    }
 
}
 
 
 
//------------------队列判空：is_queue_empty(const LinkQueue * const queue):判断队列是否为空，front == rear == head;----------//
//算法说明：判断队列是否为空，为空的条件是( queue->front == queue->head) && (queue->rear == queue ->head)
//参数说明：queue 为LinkQueue类型的常指针，因为在判断过程中 ，不会修改队列
//返回值：true(1)队列为空，false(0)队列不为空
//时间复杂度：O（1）
//测试用例,1.{queue == NULL} 2.queue != NULL 队列中元素的个数0，1，2，3....多个
 
bool is_queue_empty(const LinkQueue * const queue){
 
    if( queue == NULL)//当传入参数是指针时，必须判空
        exit(-1);//返回给系统进程异常结束
 
    if( (queue->front == queue->head) && (queue->rear == queue->head) )//队列为空
        return true ;
 
    else//队列非空
        return false;
 
 
}
 
//---------------------队列长度：queue_length( const LinkQueue * const queue);-------------------//
//函数说明：求取队列的长度，因为队列是以单链表的形式存在，并且在数据结构中，增加了头节点，所以队列的
//长度是从头节点的下一节点开始计算 一直到队尾（包括队尾），终止条件是 遍历指针指向NULL
//参数说明：因为求队列的长度只是对队列的遍历，没有改变队列的任何值，所以应该声明为const 指针
//返回值：返回队列中的元素个数
//时间复杂度：O（n），需要遍历整个队列
//测试用例1.queue == NULL ,2.queue != NULL 队列中 有0，1，2，3....个数据元素
int queue_length( const LinkQueue * const queue){
   
        if( queue == NULL)//当传入参数为指针，必须判空
            exit(-1);//进程异常结束
        unsigned int length = 0;
 
        if( is_queue_empty(queue) == true )//队列为空，调用已有的函数来判断
        { 
            length = 0;
        
        }
        else
        {        
            QNode* search_node  = queue->head ->next;//定义一个遍历节点指针，用来遍历整个队列，
                  while( search_node != NULL )       //因为头节点不包含任何数据成员，所以队列的长度
                  {
                      ++length;                        //应该从头节点下一结点开始算，直到节点为空   
                      search_node = search_node->next;
                  }             
        }
 
        return length;
 
}
 
 
//----------------------获取队头数据元素  front_data( const LinkQueue * const queue, DataType *data )-------------------------------//
//函数说明：因为队列是从队头删除数据，在很多情况下，我们有必要知道出队的数据元素是什么
//函数参数：因为只是取队头元素，而不是把队头元素从队列中删除（出队），此操作中队列并没有改变队列，所以应该用const 加以修饰
//返回值：获取的队头元素 当队列为空时，异常退出
//时间复杂度：O(1)头节点的下一节点的数据域就是队头数据元素了，并不要遍历整个队列
//测试用例说明：queue == NULL, queue != NULL (1)队列为空（2）队列非空（有1，2，3....个数据元素）
DataType front_data( const  LinkQueue* const queue){
    //1.参数检测2.空队列 3.非空队列
    if( queue == NULL)//当参数为指针类型时，得判空
        exit(-1);//进程异常退出
 
    if(is_queue_empty(queue))//队列为空，退出
        exit(-2);
    else       //队列非空，队首元素为头节点的下一结点的数据域中存储的元素
    {
        
        return(queue->head->next->data);//头节点的下一结点的数据域中存储的元素
    }
 
}
 
 
//-----------队尾进行插入（入队）; queue_insert( LinkQueue *queue , const DataType data)-------------//
//函数说明：队列是只能在队头进行删除，在队尾进行插入，具有先进先出的特性，数据元素进入队列是从队尾进入的
//参数说明：插入DataType 类型的数据 data ，因为要改变队列 所以队列queue不能用const修饰，而不能对数据data，
//进行改变，所以数据data 要用const 修饰如果数据是用户自定义的结构体，为了效率可以考虑传指针的方式传递数据data
//返回值：成功插入;返回true(1),插入失败 返回 false(0);
//时间复杂度：O（1）因为是链式队列，且有队尾指针，并且是在队尾插入，所以时间复杂度为常数O（1）
//测试用例：queue == NULL ,queue != NULL 时已经有0，1，2，3...个数据元素
bool queue_insert( LinkQueue *queue, const DataType data){
    //1.参数检测2.分配内存，3.封装4.插入4.有哪些改变
    if( queue == NULL )//当传入参数为指针变量时，必须得判空
        exit(-1); //异常退出
    QNode *new_node = (QNode*)malloc(sizeof(QNode));//为新节点分配内存
    if( new_node == NULL )//内存分配失败，进程异常退出
        exit(-1);
    else
    { 
        //将传入的数据封装为队列节点
        new_node->data = data;//数据域 
        new_node ->next = NULL;
 
        if(is_queue_empty(queue) )//队列为空
        {
            new_node->next = queue->head->next;
            queue->head->next = new_node;//队列为空时，头指针的next需要改变
            queue->rear = new_node;//将尾指针指向新的尾部
        }
        else//队列不为空
        {
            new_node->next = queue->rear->next;
            queue->rear->next = new_node;//将新的节点new_node 插入队尾
            queue->rear = new_node;//尾指针rear指向新的尾部
        }
 
        return true;
    }
    
}
 
 
//-------访问节点的数据域,并显示在屏幕上void visit(const QNode * const node)—————————————————————---//
//函数说明：访问队列节点中的数据域，并且在屏幕上显示数据域中的值
//参数说明：传递一个QNode类型的指针变量，node 因为只是对节点进行访问，而并没有改变节点所以得用const修饰
//返回值：void
//时间复杂度;O(1)
void visit(const QNode* const node){
    //1.判空2.显示
    if( node == NULL )//当参数为指针时，必须得判空
        exit(-1);
    DataType data = node->data;//声明一个DataType类型的变量 data 来保存节点node数据域中的数据
    printf("%d  ",data);
}
 
//-----------遍历队列 bool queue_traverse(const LinkQueue * const queue)--------访问队列中的所有节点的数据域--------------//
//函数说明：访问从头节点的下一结点（也就是队列的首员节点）的数据域
//参数：因为没对队列进行改变，所有queue应该用const 修饰
//返回值：成功返回 true(1)失败 返回false(0)
//时间复杂度：O(n） 因为要对从头到尾访问队列中的每个节点
bool queue_traverse(const LinkQueue * const queue){
    //1.参数检测(空)2.目前节点3.遍历4.节点访问函数（尽量把功能和显示函数分离）
    if( queue == NULL )//当传入参数为指针时，判空
        exit(-1);//异常退出
 
    if( is_queue_empty(queue))//队列为空，无法遍历
        exit(-2);
    else     //队列非空,从首元节点开始逐个访问
    {
 
    QNode *now_node = queue->head->next;//首元节点
    while(now_node != NULL)
    {
        visit(now_node);
        now_node = now_node->next;
    }
 
    return true;
    }
}
 
 
 
//-------------------从队列中删除队头 delete_queue_front( LinkQueue *queue)------------------------//
//函数说明：队列是一种只能在表尾进行插入（入队），在表头进行删除的（出队）线性表，所以队列进行删除时，队尾不需要改变，
//当队列中只有一个数据元素时，队头和队尾都需要改变
//参数说明：queue不能为空，当删除空队列时，进程异常退出 exit(-2)
//返回值：成功删除队头（出队）返回true(1),否则返回false
//时间复杂度：O(1)
//测试用例 queue == NULL ,queue != NULL (1)队列为空，异常退出exit(-2)(2)队列只有一个数据元素rear ，
//head 都要改变（3）队列有多个数据元素 改变front ,尾指针rear不需要改变
bool delete_queue_front( LinkQueue *queue){
    //1.参数检测 2.队空 3.队非空（1.只有一个数据元素，2.有多个数据元素）4.释放节点所分配的内存
    if( queue == NULL )
        exit(-1);
 
    if(is_queue_empty(queue))//队列为空，异常退出exit(-2)
        exit(-2);
    else           //队列非空
    {
        QNode *old_node = queue->head->next;//指向要出队的节点
        if( (queue_length(queue) == 1) )//队列只有一个数据元素 front ,rear,head 都需改
        {
            queue->head->next == NULL;//队列为空，front == rear ==head
            queue->front = queue->head;
            queue->rear = queue->head;
 
        }
        else
        {
            queue->head->next = old_node->next;
        }
 
        free(old_node);//释放出队元素的所占有的内存，防止内存泄露
        return true;
    }
}
 
 
//将队列清空------------------clear_queue( LinkQueue *queue);将队列中所有数据元素都清除，直到队列为空-----------//
//函数说明：将队列的所有数据元素节点都释放 （也就是说，队列还存在，但已经为空）
//参数：指向队列的指针queue,queue != NULL
//返回值：当队列为空时 返回true(1)，否则为false(0) 
//时间复杂度：O(n),得遍历整个队列
//测试用例 queue == NULL ,queue ！= NULL 1.队列为空， 2.队列不为空
bool clear_queue( LinkQueue *queue){
    //1.判参 2.队列为空3队列不为空（遍历，删除节点，释放内存）
    if( queue == NULL )//当参数为指针时，必须得判空
        exit(-1);//进程结束 ，异常退出
    
    //队列非空时
        while(is_queue_empty(queue) == false)//调用出队操作，清空队列
            delete_queue_front( queue);//出队操作
 
    //此时队列已经清空了（不管是当初是空队列，还是非空队列）
        return true;    
 
}
 
//销毁队列:destroy_queue(LinkQueue *queue);队列将不存在，从头到尾删除队列中的节点释放队列所指的内存
//函数说明：销毁队列，回收内存，通过调用clear_queue（queue）来实现
//参数说明：queue != NULL
//时间复杂度：O（n），必须释放队列中每个元素节点和头节点的内存空间
//测试用例：queue == NULL ,queue != NULL
bool destroy_queue(LinkQueue *queue){
    //1.判空2.清空队列.3.释放头节点
   if( queue == NULL )//当传入参数为指针时，必须判空
       exit(-1);//进程异常退出
 
   clear_queue(queue);//清空队列
   free(queue->head);//这里注意了，free()只能释放malloc所分配的内存空，否则会引发错误
   return true;
}

 

//---------------------main.cpp----测试队列的基本操作---------------------------------//
#include"Queue.h"
#include<stdlib.h>
#include<stdio.h>
 
int main(void){
 
    LinkQueue queue1;//声明一个LinkQueue 变量 queue1
    LinkQueue *pqueue1 = &queue1;//声明一个LinkQueue 指针变量 指向queue1
    LinkQueue *pqueue2 = NULL;
    int data[4]={1,2,3,4};//测试数据 将要入队的数据
 
 
//----------------------测试初始化函数init_queue(LinkQueue *queue):分配内存，初始化队列-----------------------//
    //测试用例{queue == NULL, queue != NULL}
 
    bool is_init = false;// 定义一个bool量，来判断队列初始化成功 true(1),失败 false 或异常退出
    //is_init = init_queue(pqueue2);// queue == NULL 异常退出： Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    is_init = init_queue(pqueue1);// queue == pqueue1 == &queue != NULL 
    printf("队列已经初始化？%d\n",is_init);
    printf("\n");
 
 
//------------------测试队列判空函数：is_queue_empty(const LinkQueue * const queue);------------------------//
//测试用例,1.{queue == NULL} 2.queue != NULL 队列中元素的个数0，1，2，3....多个
 
    bool is_empty = false;//定义一个bool量，判断队列是否为空，为空 is_empty == true(1) ,不为空 is_empty == false(0)
    //is_empty = is_queue_empty(pqueue2);//测试： queue == NULL 结果：Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 0 个 结果：is_empty == 1;
    printf("队列为空吗：%d\n",is_empty);
    printf("\n");
 
    
//---------------------测试队列长度：queue_length( const LinkQueue * const queue);-------------------//
//测试用例1.queue == NULL ,2.queue != NULL 队列中 有0，1，2，3....个数据元素
 
    unsigned int length;//定义一个无符号整形变量 length来记录队列的长度
    //length = queue_length(pqueue2);//测试：queue == NULL 结果：程序“[5352] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有0个数据元素 结果：length == 0;
    printf("队列长度为%d\n",length);
    printf("\n");
 
 
//----------------------测试获取队头数据元素  front_data( const LinkQueue * const queue, DataType *data )-------------------------------//
//测试用例说明：queue == NULL, queue != NULL (1)队列为空（2）队列非空（有1，2，3....个数据元素）当数据入队时再测试
    DataType queue_head ;//定义一个DataType类型变量 queue_head 来显示队头数据元素
    //queue_head = front_data(pqueue2);//测试queue == NULL 结果为：程序异常退出：程序“[3108] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    //queue_head = front_data(pqueue1);//测试queue != NULL （1）队列为空 结果为：程序异常退出 程序“[5592] 
//Queue.exe: 本机”已退出，返回值为 -2 (0xfffffffe)。
 
 
 
 
//---------------测试（入队）; queue_insert( LinkQueue *queue , const DataType data)-------------//
//测试用例：queue == NULL ,queue != NULL 时已经有0，1，2，3...个数据元素
    bool is_insert = false;//定义一个bool量来判断是否已经将数据入队
    //is_insert = queue_insert(pqueue2,data[0]);//测试：queue == NULL 结果：程序“[2232] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
 
    //1入队
    is_insert = queue_insert(pqueue1,data[0]);//测试：queue != NULL 队列为空，数据1入队
    printf("%d 入队了吗? %d\n",data[0],is_insert);
 
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 1个 结果：is_empty == 0;
    printf("队列为空吗：%d\n",is_empty);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有0个数据元素 结果：length == 0;
    printf("队列长度为%d\n",length);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有1个数据 结果：
    printf("这次的队头为:%d\n",queue_head);
    printf("\n");
 
 
    //2入队
    is_insert = queue_insert(pqueue1,data[1]);//测试：queue != NULL 队列为空,数据2入队
    printf("%d 入队了吗? %d\n",data[1],is_insert);
 
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 2个 结果：is_empty == 0;
    printf("队列为空吗：%d\n",is_empty);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 2;
    printf("队列长度为%d\n",length);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有2个数据 结果：
    printf("这次的队头为:%d\n",queue_head);
    printf("\n");
 
 
    //3入队
    is_insert = queue_insert(pqueue1,data[2]);//测试：queue != NULL 队列非空 数据3入队
    printf("%d 入队了吗? %d\n",data[2],is_insert);
 
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 3个 结果：is_empty == 0;
    printf("队列为空吗：%d\n",is_empty);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有3个数据元素 结果：length == 3;
    printf("队列长度为%d\n",length);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有3个数据 结果：
    printf("这次的队头为:%d\n",queue_head);
    printf("\n");
 
 
    //4入队
    is_insert = queue_insert(pqueue1,data[3]);//测试：queue != NULL 队列非空，数据元素4入队
    printf("%d 入队了吗? %d\n",data[3],is_insert);
 
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("队列为空吗：%d\n",is_empty);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("队列长度为%d\n",length);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    printf("这次的队头为:%d\n",queue_head);
    printf("\n");
    printf("\n");
    printf("\n");
 
 
//---------测试---遍历队列 bool queue_traverse(const LinkQueue * const queue)--------访问队列中的所有节点的数据域--------------//
//测试用例：queue == NULL, queue != NULL (1)队列为空（2）队列非空
    int is_traverse = false;//用来判断是否遍历完队列 为 true（1）遍历完，否则为false
    printf("队列中从头到尾的数据元素依次为：");
    //is_traverse = queue_traverse(pqueue2);
//测试：queue == NULL 结果：程序“[4872] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
    is_traverse = queue_traverse(pqueue1);//测试 queue != NULL (2)队列非空
    printf("\n");
    printf("队列是否遍历完？ %d\n",is_traverse);
    printf("\n");
    printf("\n");
    printf("\n");
 
    
//---------测试将队列清空------------------clear_queue( LinkQueue *queue);将队列中所有数据元素都清除，直到队列为空-----------//
//测试用例 queue == NULL ,queue ！= NULL 1.队列为空， 2.队列不为空
    
    bool is_clear = false;//当队列清空后为true(1),队列没有清空为false(0)
    //clear_queue(pqueue2);//测试 queue == NULL,测试结果：程序“[1180] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
 
    //is_clear = clear_queue(pqueue1);//测试 queue != NULL 2.队列不为空
    //printf("队列清空了吗？ %d\n",is_clear);
 
    
    //is_traverse = queue_traverse(pqueue1);

//测试遍历 queue != NULL (2)队列为空 测试结果：程序“[4212] Queue.exe: 本机”已退出，返回值为 -2 (0xfffffffe)。
    //printf("\n");
 
 
//销毁队列:destroy_queue(LinkQueue *queue);队列将不存在，从头到尾删除队列中的节点释放队列所指的内存
//测试用例：queue == NULL ,queue != NULL
 
      bool is_destroy = false;//队列销毁为true（1），否则为 false(0)
     // is_destroy =destroy_queue( pqueue2);;

//测试 queue == NULL 测试结果：程序“[4044] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)。
 
    //  is_destroy  = destroy_queue(pqueue1);

//测试queue != NULL，队列非空
    
//-------------------测试从队列中删除队头（出队） delete_queue_front( LinkQueue *queue)------------------------//
//测试用例 queue == NULL ,queue != NULL (1)队列为空，异常退出exit(-2)(2)队列只有一个数据元素，出队后为空（3）队列有多个数据元素 
 
    bool is_out = false;//定义一个bool 量is_out 判断队列是否出队，成功出队 返回true
    //delete_queue_front(pqueue2);

//测试 queue == NULL 结果：程序“[5284] Queue.exe: 本机”已退出，返回值为 -1 (0xffffffff)
 
    //1.队空 2.队长 3.队头元素 4.出队后 5.队头元素 6.队长7.队空
    //1出队
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("出队前队列为空吗：%d\n",is_empty);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("出队前队列长度为%d\n",length);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    printf("出队前的队头为:%d\n",queue_head);
 
    is_out = delete_queue_front(pqueue1);//出队
    printf("出队成功？ %d\n",is_out);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    printf("出队后的队头为:%d\n",queue_head);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("出队后队列长度为%d\n",length);
 
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("出队后队列为空吗：%d\n",is_empty);
 
    printf("\n");
    printf("\n");
 
 
    //2出队
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("出队前队列为空吗：%d\n",is_empty);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("出队前队列长度为%d\n",length);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    printf("出队前的队头为:%d\n",queue_head);
 
    is_out = delete_queue_front(pqueue1);//出队
    printf("出队成功？ %d\n",is_out);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    printf("出队后的队头为:%d\n",queue_head);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("出队后队列长度为%d\n",length);
 
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("出队后队列为空吗：%d\n",is_empty);
 
    printf("\n");
 
 
    //3出队
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("出队前队列为空吗：%d\n",is_empty);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("出队前队列长度为%d\n",length);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    printf("出队前的队头为:%d\n",queue_head);
 
    is_out = delete_queue_front(pqueue1);//出队
    printf("出队成功？ %d\n",is_out);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    printf("出队后的队头为:%d\n",queue_head);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("出队后队列长度为%d\n",length);
 
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("出队后队列为空吗：%d\n",is_empty);
 
    printf("\n");
 
    //4出队
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("出队前队列为空吗：%d\n",is_empty);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("出队前队列长度为%d\n",length);
 
    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
    printf("出队前的队头为:%d\n",queue_head);
 
    is_out = delete_queue_front(pqueue1);//出队
    printf("出队成功？ %d\n",is_out);
 
//    queue_head = front_data(pqueue1);//测试：queue != NULL （2）队列非空 有4个数据 结果：
//    printf("出队后的队头为:%d\n",queue_head);
 
    length = queue_length(pqueue1);//测试：queue != NULL  队列中有2个数据元素 结果：length == 4;
    printf("出队后队列长度为%d\n",length);
 
    is_empty = is_queue_empty(pqueue1);//测试： queue != NULL ,队列中元素为 4个 结果：is_empty == 0;
    printf("出队后队列为空吗：%d\n",is_empty);
 
    printf("\n");
 

    is_destroy  = destroy_queue(pqueue1);//测试queue != NULL，队列为空
    printf("队列，代表地球消灭你,嘿嘿！！！！\n");
 
    return 0;
}

 栈

　　栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

　　栈的特点是先入后出。符合这个特征的数据才可以在栈中存储。

 

//  stack.h
 
#ifndef  __STACK_H__
#define  __STACK_H__
 
typedef int DataType;
typedef struct node{
    DataType data;
    struct node * next;
}Stack;
 
Stack* CreateStack();   //创建栈
void StackEmpty(Stack* );  //清空栈
void DestoryStack(Stack*); //撤销(删除)栈
int IsEmpty(Stack*);    //判空
int PushStack(Stack*, DataType);    //入栈
int PopStack(Stack*);   //出栈
DataType GetTopElement(Stack*); //取栈顶元素
 
 
#endif

 

// stack.c
 
/*
    一个基于链表实现的栈的简单例子，没有做逆向增长，固定长度等限制。此外，利用数组等也可实现栈。
    仅用来演示栈先进后出的原理。第一个元素存储在 stack->next 中
*/
 
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
 
//创建栈，此时栈中没有任何元素
Stack* CreateStack()
{
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    if(NULL != stack)
    {
       stack->next = NULL;
       return stack;
    }
    printf("out of place.\n");
    return NULL;
}
 
//清空栈
void StackEmpty(Stack* stack)
{
    while(!IsEmpty(stack))
    {
        PopStack(stack);
    }
    printf("now stack is empty. \n");
}
 
//撤销栈
void DestoryStack(Stack* stack)
{
    free(stack);
    printf("now stack is destoryed. \n");
    exit(0);
}
 
int IsEmpty(Stack* stack)
{
    return (stack->next == NULL);
}
 
//入栈，成功返回1，失败返回0， 把元素 data 存入 栈 stack 中
int PushStack(Stack* stack, DataType data)
{
    Stack* newst = (Stack*)malloc(sizeof(Stack));
    if(NULL != newst)
    {
        newst->data = data;
        newst->next = stack->next;  //s->next = NULL;
        stack->next = newst;
        return 1;
    }
    printf("out of place PushStack.\n");
    return 0;
}
 
/*
    出栈，成功返回1，失败返回0，出栈不取出元素值，只是删除栈顶元素。
    如出栈要实现，取出元素值，并释放空间，可结合取栈顶元素函数做修改，这里不再给出。
 */
 
int PopStack(Stack* stack)
{
    Stack* tmpst;
    if(!IsEmpty(stack))
    {
        tmpst = stack->next;
        stack->next = tmpst->next;
        free(tmpst);
        return 1;
    }
    return 0;
}
 
//取栈顶元素，仅取出栈顶元素的值，取出之后，该元素，任然存在栈中。成功返回元素值，失败输出提示信息，并返回 -1
DataType GetTopElement(Stack* stack)
{
    if(!IsEmpty(stack))
    {
        return stack->next->data;
    }
    printf("stack is empty GetTopElement.\n");
    return -1;
}

 

// main.c
 
#include <stdio.h>
#include "stack.h"
 
int main()
{
    //测试创建栈函数
    Stack* stack = CreateStack();
    printf("StackTopElement =  %d \n",GetTopElement(stack));
 
    //测试入栈函数
    PushStack(stack,5); 
    printf("StackTopElement =  %d \n",GetTopElement(stack));
 
    PushStack(stack,6);
    printf("StackTopElement =  %d \n",GetTopElement(stack));
 
    PushStack(stack,7);
    printf("StackTopElement =  %d \n",GetTopElement(stack));
 
    //测试出栈函数
    PopStack(stack);
    printf("StackTopElement =  %d \n",GetTopElement(stack));
    PopStack(stack);
    printf("StackTopElement =  %d \n",GetTopElement(stack));
 
    //测试清空栈函数
    StackEmpty(stack);
    printf("StackTopElement =  %d \n",GetTopElement(stack));
 
    //测试撤销栈函数
    DestoryStack(stack);
 
    return 0;
}
 

 

树

二叉树的存储结构

// 存储结构
typedef int ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

 

二叉树遍历

void PreOrder(BiTree T) {
    // 先序遍历
    if (T != NULL) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
void InOrder(BiTree T) {
    // 中序遍历
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}
void PostOrder(BiTree T) {
    // 后序遍历
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

 

中序遍历非递归算法

 

 

 

 

层次遍历

 

 

 

 由遍历序列构造二叉树

 

 

 

 线索二叉树

 

 

 

 

图

 

 

图是一种较线性表和树更为复杂的数据结构。在图形中，结点之间的关系可以是任意的，图中任何两个数据元素之间都可能相交。

(1) 线性表中将数据元素叫元素，树中将数据元素叫结点，图中将数据元素称为顶点。
(2) 线性表中可以没有数据元素，称为空表。树中可以没有结点，称为空树。在图中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。
(3) 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻的两层结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边表示，边集可以是空的。

 

图的存储结构

 

#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef struct MGraph {
    VertexType Vex[MaxVertexNum]; // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵，边表
    int vexnum, arcnum; // 图的顶点和边的数量
}MGraph;

 

 

 

 

 

 

#define MaxVertexNum 100 // 图中顶点数目的最大值
typedef struct ArcNode {  // 边表结点
    int adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *next; // 指向下一条弧的指针
}ArcNode;
typedef struct VNode { // 顶点表结点
    VertexType data; // 顶点信息
    ArcNode *first; // 指向第一条依附该顶点的弧的指针
}VNode, AdjList[MaxVertexNum];
typedef struct ALGraph {
    AdjList vertices; // 领接表
    int vexnum, arcnum; // 图的顶点数和弧数
}ALGraph; // ALGraph是以领接表存储的图类型

 

 

 

 

 

 

图的遍历（traversing graph）

深搜(Depth_First_search)

广搜(Breadth_First_Search)

 

 

 

查找算法

1. 顺序查找

//时间复杂度为O(n)。顺序查找C语言实现
//基本思路：用顺序结构存储数据（数组、链表），从前到后依次查询目标值，
//如果发现则返回查找到的值，否则返回0.
#include<stdio.h>

int FindBySeq(int *ListSeq, int ListLength, int KeyData);

int main(){
    int TestData[5] = { 34, 35, 26, 89, 56 };
    int retData = FindBySeq(TestData, 5, 89);
    printf("retData: %d\n", retData);
    return 0;
}

int FindBySeq(int *ListSeq, int ListLength, int KeyData){
    int tmp = 0;
    int length = ListLength;
    for (int i = 0; i < ListLength; i++)    {
        if (ListSeq[i] == KeyData)
            return i;
    }
    return 0;
}
 

 

2. 二分查找

有序查找，用给定值k先与中间结点的关键字比较，相等代表查找成功；不相等，在子表中继续查找。

 

int BinarySearch(int A[], value, n){
    int high, middle, low;
    low = 0;
    high = n - 1;
    while (low <= high){
        middle = (high + low) / 2;
        if (A[middle] = value)
            return middle;
        if (A[middle] > value)
            high = middle - 1;
        if (A[middle] < value)
            low = middle + 1;
    }
    return -1;
}

 

 

 

 

 

 

3. 插值查找

 

4. 斐波那契查找

 

5. 树表查找

 

6. 分块查找

　　先对索引表（各块中的关键字构成的）进行二分查找或顺序查找，在已确定的块中用顺序法进行查找。

 

 

7. 哈希查找

 

排序算法

1.冒泡排序

 

2.选择排序

 

3.插入排序

 

4.希尔排序

 

5.快速排序

 

6.归并排序

 

7.堆排序