day21：零基础学嵌入式之数据结构

一、双向链表（doulinklist）

1.

2.创建

struct DouLinkList *CreateDouLinkList()
{
    struct DouLinkList *dl = malloc(sizeof(struct DouLinkList));
    if(NULL ==  dl)
    {
        fprintf(stderr, "CreateDouLinkLis malloc");
        return NULL;
    }
    dl->head = NULL;
    dl->clen = 0;
    return dl;
    
}

3.长度、判空、

//判空
int IsEmptyDouLinkList(struct DouLinkList *dl)
{
    return 0 == dl->clen;
}
//获得长度
int GETSizeDouLinkList(struct DouLinkList *dl)
{
    return dl->clen;
}

4.头插与显示

//头插
int InSertHeadDouLinkList(struct DouLinkList *dl,struct DATATYPE *data)
{
    struct DouNode *newnode = malloc(sizeof(struct DouNode));
    if( NULL == newnode)
    {
         fprintf(stderr, "InSertHeadDouLinkList malloc");
         return 1;
    }
    memcpy(&newnode->data,data, sizeof(struct DouNode));
    newnode->next = NULL;
    newnode->prev = NULL;
    newnode->next = dl->head;
    if(dl->head)
    {
        dl->head->prev = newnode;
    }
    dl->head = newnode;
    dl->clen ++;
    return 0;
}
//显示
int ShowDouLinkList(struct DouLinkList *dl,DIR dir)
{
    struct DouNode *tmp = dl->head;
    if(FORWAOR == dir)
    {
        struct DouNode *tmp = dl->head;
        while (tmp)
        {
            printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
            tmp = tmp->next;
        }
    }
    else if(BACKWAOR ==dir)
    {
        struct DouNode *tmp = dl->head;
        while (tmp->next)
        {
            tmp=tmp->next;
        }
        while(tmp)
        {
            printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);
            tmp = tmp->prev;
        }
    }
    return 0;
}

5.尾插

int InSertTailDouLinkList(struct DouLinkList *dl,struct DATATYPE *data)
{
    int len = GETSizeDouLinkList(dl);
    if(0 == len)
    {
        InSertHeadDouLinkList(dl, data);
    }
    else
    {
        struct DouNode *newnode = malloc(sizeof(struct DouNode));
        if(NULL == newnode)
        {
            fprintf(stderr, "InSertTailDouLinkList malloc");
           return 1;
        } 
        memcpy(&newnode->data, data ,sizeof(struct DATATYPE ));
        newnode->next = NULL;
        newnode->prev=NULL;
        struct DouNode *tmp = dl->head;
        while(tmp->next)
        {
            tmp = tmp->next;
        }
        newnode->prev = tmp;
        tmp->next = newnode;
        dl->clen ++;
    }
    return 0;
}

6.位置插

int InSertPosDouLinkList(struct DouLinkList *dl,struct DATATYPE *data,int pos)
{
    int len = GETSizeDouLinkList(dl);
    if(pos < 0 || pos >len)
    {
        return 1;
    }
    if(0 == pos)
    {
        return InSertHeadDouLinkList(dl, data);
    }
    else if(len ==pos)
    {
        return InSertTailDouLinkList(dl, data);
    }
    else
    {
        struct DouNode *newnode = malloc(sizeof(struct DouNode));
        if(NULL == newnode)
        {
            fprintf(stderr, "InSertPosDouLinkList malloc");
            return 1;
        }
        memcpy(&newnode->data, data, sizeof(struct DATATYPE));
        newnode->next =NULL;
        newnode->prev=NULL;
        struct DouNode *tmp = dl->head;
        for(int i = 0;i < pos;++i)
        {
            tmp = tmp->next;
        }
        newnode->next = tmp;
        newnode->prev =tmp->prev;
        tmp->prev = newnode;
        newnode->prev->next = newnode;
        dl->clen++;
        return 0;
    }

}

7.寻找

struct DouNode * FindDouLinkList(struct DouLinkList *dl,char *name)
{
    if(IsEmptyDouLinkList(dl))
    {
        return NULL;
    }
    struct DouNode *tmp = dl->head;
    while(tmp)
    {
        if(0 == strcmp(name,tmp->data.name))
        {
            return tmp;
        }
        tmp = tmp->next;
    }
    return NULL;


}

8.修改

int MdifyDouLinkList(struct DouLinkList *dl,char *name,struct DATATYPE *data)
{
    
    struct DouNode *tmp = FindDouLinkList(dl, name);
    if(NULL == tmp)
    {
        return 1;
    }
    memcpy(tmp, data, sizeof(struct DATATYPE));
    return 0;
}

9.Makefile/makefile

（1）工程管理工具，三个以上编译要写，如果在实际中.c比较多，改了其中的一个.c，只编译这一个.c；

（2）vi Makefile 

        进入之后

1）

目标  ：   依赖
a.out : main.c doulinklist.c//通过依赖文件可以产生目标；
    gcc main.c doulinklist.c //开头必须tab不能是几个空格，规则，打命令；

clean:               
    rm a.out//可以删目标文件、中间生成的文件，只留最后的需要文件；

        make 回车

如果想在没有改代码的前提下再次编译，先make clean ，再make

2）

//支持自定义变量
#代表源文件
SRC += main.c         //追加
SRC +=doulinklist.c   //追加
DST = app             //(all->app啥名字都可以),可执行文件

CC = gcc
FLAG = -g             //标志位 ，调试版本
LIB = -lm

#a.out:main.c./doulinklist.c
#   gcc main.c doulinklist.c


$（DST） :$(SRC)
    $(CC) $(SRC) $(FLAG) $(LIB) -o $(DST)


clean:
    rm $(DST)

:wqa

make (如果也要指定makefilr文件，就make -f Makefile2)

如果想在没有改代码的前提下再次编译，先make clean ，再make

10.销毁

int DestroyDouLinkList(struct DouLinkList **dl)
{
    struct DouNode *tmp = (*dl)->head;
    while (1)
    {
        struct DouNode *tmp = (*dl)->head;
        if(NULL == tmp )
        {
            break;
        }
        (*dl)->head = (*dl)->head->next;
        free(tmp);
    }
    free(*dl);
    dl = NULL;
    return 0;
}

11.删除

int DeleteDouLinkList(struct DouLinkList *dl,char *name)
{
    struct DouNode *tmp = FindDouLinkList(dl, name);
    if(NULL == tmp)
    {
        return 1;
    }
    if(dl->head == tmp)
    {
        dl->head=dl->head->next;
        tmp->next->prev = NULL;
        free(tmp);
        dl->clen--;
        return 0;
    }
    else if(NULL ==tmp->next)
    {
        tmp->prev->next = NULL;
        free(tmp);
        dl->clen--;
        return 0;
    }
    else
    {
        tmp->prev->next = tmp->next;
        tmp->next->prev = tmp->prev;
        free(tmp);
        dl->clen --;
        return 0;
    }
}

12.逆序

int ReverseDouLinkList(struct DouLinkList *dl)
{
    struct DouNode *prev = NULL;
    struct DouNode *tmp = dl->head;
    struct DouNode *last = tmp->next;
    int len = GETSizeDouLinkList(dl);
    if(len < 2)
    {
        return 1;
    }
    while(1)
    {
        tmp->next= prev;
        tmp->prev = last;
        prev = tmp;
        tmp = last;
        if(NULL == tmp)
        {
            break;
        }
        last = last->next;
    }
    dl->head = prev;
    return 0;
}