嵌入式学习——数据结构（双向无头无环链表）——day47

1. makefile——（注意：双向无头链表第一个节点的pre为空，最后一个节点的next为空）

                                        单向无头链表只能找到后一个节点、双向无头链表前后节点都能找到

OBJ:=doulink
OBJS+=main.c doublelink.c
CCl=gcc$(OBJ):$(OBJS)$(CC) $^ -o $@
.PHONY:
clean:rm $(OBJ)
test:valgrind --tool=memcheck --leak-check=full ./$(OBJ)

2. doublelink.h

#ifndef _DOUBLELINK_H_
#define _DOUBLELINK_H_typedef struct stu
{int id;char name[32];int score;
}DataType;typedef struct node
{DataType data;struct node *ppre;struct node *pnext;
}DouNode;typedef struct list
{DouNode *phead;int clen;
}DouList;extern DouList *create_dou_link();
extern int is_empty_dou_link(DouList *plist);
extern int push_head_dou_link(DouList *plist, DataType data);
extern void dou_link_for_each(DouList *plist, int dir);
extern int  push_tail_dou_link(DouList *plist, DataType data);
extern int pop_head_dou_link(DouList *plist);
extern int pop_tail_dou_link(DouList *plist);
extern DouNode *find_name(DouList *plist, char *pname);
extern int modify_score(DouList *plist, char *pname, int pscore);
extern void destory_dou_link(DouList *plist);#endif

3. doublelink.c

#include "doublelink.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>DouList *create_dou_link()//创建标签
{DouList *plist = NULL;plist = (DouList *)malloc(sizeof(DouList));if (NULL == plist){perror("fail to malloc");return NULL;}plist->phead = NULL;plist->clen = 0;return plist;
}int is_empty_dou_link(DouList *plist)//判断空链表
{if (NULL == plist->phead){return 1;}return 0;
}int push_head_dou_link(DouList *plist, DataType data)//头插
{DouNode *pnode = NULL;pnode = malloc(sizeof(DouNode));if (NULL == pnode){perror("fail to malloc");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if (is_empty_dou_link(plist))//空链表直接插{plist->phead = pnode;}else{pnode->pnext = plist->phead;plist->phead->ppre = pnode;plist->phead = pnode;}plist->clen++;return 0;
}void dou_link_for_each(DouList *plist, int dir)//两种方式遍历链表，1顺序遍历打印  0逆序遍历打印
{if (is_empty_dou_link(plist)){return;}DouNode *ptmp = plist->phead;if (dir)//顺序遍历打印{while (ptmp){printf("%d %s %d\n", ptmp->data.id, ptmp->data.name, ptmp->data.score);ptmp = ptmp->pnext;}}else//逆序遍历打印{while (ptmp->pnext)//走到末尾{ptmp = ptmp->pnext;}while (ptmp){printf("%d %s %d\n", ptmp->data.id, ptmp->data.name, ptmp->data.score);ptmp = ptmp->ppre;}}printf("\n");
}int push_tail_dou_link(DouList *plist, DataType data)//头插
{DouNode *p = NULL;DouNode *pnode = NULL;pnode = malloc(sizeof(DouNode));if (NULL == pnode){perror("fail to malloc");return -1;}pnode->data = data;pnode->ppre = NULL;pnode->pnext = NULL;if (is_empty_dou_link(plist))//空链表直接插{plist->phead = pnode;}else{   p = plist->phead;while (p->pnext != NULL){p = p->pnext;}p->pnext = pnode;pnode->ppre = p;}plist->clen++;return 0;
}int pop_head_dou_link(DouList *plist)//头删
{if (is_empty_dou_link(plist))//空链表直接结束程序{return -1;}DouNode *pfree = NULL;pfree = plist->phead;plist->phead = pfree->pnext;//标签指向第二个节点首地址if (plist->phead != NULL)//判断是否空链表{plist->phead->ppre = NULL;//将第二个节点的ppre变为NULL}free(pfree);plist->clen--;return 0;
}int pop_tail_dou_link(DouList *plist)//尾删
{if (is_empty_dou_link(plist))//空链表程序结束{return -1;}DouNode *pfree = NULL;pfree = plist->phead;while (pfree->pnext)//指针指向最后一个节点{pfree = pfree->pnext;}if (pfree->ppre != NULL)//链表有两个以上节点{pfree->ppre->pnext = NULL;}else //链表只有一个节点{plist->phead = NULL;}free(pfree);plist->clen--;return 0;
}DouNode *find_name(DouList *plist, char *pname)//寻找name
{DouNode *ptmp = NULL;ptmp = plist->phead;while (ptmp != NULL){if (!strcmp(pname, ptmp->data.name)){return ptmp;}ptmp = ptmp->pnext;}return NULL;
}int modify_score(DouList *plist, char *pname, int pscore)//修改分数
{DouNode *ptmp = NULL;ptmp = find_name(plist, pname);if (ptmp != NULL){ptmp->data.score = pscore;return 0;}return -1;
}void destory_dou_link(DouList *plist)//链表摧毁
{while (!is_empty_dou_link(plist)){pop_head_dou_link(plist);}free(plist);
}

4. main.c

#include <stdio.h>
#include <stdlib.h>
#include "doublelink.h"int main(void)
{DataType stus[] = {{1, "doinb", 100},{2, "lwx", 67},{3, "lqs", 99},{4, "tian", 98},{5, "gimgoon", 78},{6, "xinyi", 88},{7, "nuguri", 99},{8, "khan", 77},{9, "bo", 94},{10, "xiaolaohu", 60}};DouNode *ptmpnode = NULL;DouNode *pnamepnode = NULL;int ret_modify = 0;int i = 0;int new_score[] = {100, 99, 98, 97, 96, 95, 94, 93, 92, 91};DouList *plist = create_dou_link();//表头创建if (NULL == plist){return -1;}for (i = 0; i < sizeof(stus) / sizeof(stus[0]); i++)//给链表中插入结构体中的所有内容{push_tail_dou_link(plist, stus[i]);//尾插}dou_link_for_each(plist, 1);dou_link_for_each(plist, 0);#if 0for (i = 0; i < sizeof(stus)/sizeof(stus[0]); i++)//遍历查找{pnamepnode = find_name(plist, stus[i].name);if (pnamepnode != NULL){printf("find node ");printf("%d  ", pnamepnode->data.id);printf("%s  ", pnamepnode->data.name);printf("%d\n", pnamepnode->data.score);}else{printf("not find this node\n");}}
#endif#if 0for (i = 0; i < sizeof(stus)/sizeof(stus[0]); i++)//遍历修改{ret_modify = modify_score(plist, stus[i].name, new_score[i]);if (-1 == ret_modify){perror("fail to modify_score\n");}}dou_link_for_each(plist, 1);dou_link_for_each(plist, 0);
#endif#if 0for (i = 0; i < sizeof(stus) / sizeof(stus[0]); i++)//测试头删{pop_head_dou_link(plist);//尾删dou_link_for_each(plist, 1);dou_link_for_each(plist, 0);}
#endif destory_dou_link(plist);//销毁return 0;
}

2. 程序注意

        1. 指针遍历

        （1）操作此指针

    if (ptmp != NULL){ptmp = ptmp->pnext;}

        （2）指针指向链表节点末尾

    if (ptmp->pnext != NULL){ptmp = ptmp->pnext;}