嵌入式学习笔记 D21：双向链表的基本操作

• 双向链表的定义与创建
• 双向链表的插入
• 双向链表的查找
• 双向链表的修改
• 双向链表的删除
• 双向链表的逆序
• MakeFile工具使用

一、双向链表的定义与创建

        1.双向链表的定义：

        双向链表是在单链表的每个结点中，再设置一个指向其前一个结点的指针域。

struct DOUNode
{struct DATATYPE data;struct DOUNode *prev;struct DOUNode *next;};

        2.双向链表的创建

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

二、双向链表的插入

        1.头插法：

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 DATATYPE));newnode->next = NULL;newnode->prev = NULL;newnode->next = dl->head;if(dl->head){dl->head->prev = newnode;}dl->head = newnode;dl->clen++;return 0;}

        2.尾插法：

int InsertTailDouLinkList(struct DOULinkList* dl, struct DATATYPE* data) 
{if(IsEmptyDouLinkList(dl)){return InsertHeadDouLinkList(dl,data);}else{struct DOUNode *tmp = dl->head; while(tmp->next){tmp = tmp->next;}struct DOUNode *newnode =(struct DOUNode *) malloc (sizeof(struct DOUNode));if (NULL == newnode) {fprintf(stderr, "InsertTailDouLinkList malloc");return 1;}// chu shi hua jie dianmemcpy(&newnode->data,data,sizeof(struct DATATYPE));newnode->next = NULL;newnode->prev = NULL;// lian jie lian biaonewnode->prev = tmp;tmp->next = newnode;dl->clen++;}return 0;
}

        3.按指定位置插入：

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(pos == len){return InsertTailDouLinkList(dl,data);}else {struct DOUNode *newnode =(struct DOUNode *) malloc (sizeof(struct DOUNode));if (NULL == newnode) {fprintf(stderr, "InsertPosDouLinkList malloc");return 1;}// chu shi hua jie dianmemcpy(&newnode->data,data,sizeof(struct DATATYPE));newnode->next = NULL;newnode->prev = NULL;struct DOUNode *tmp = dl->head; int i ;for( 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;
}

        4.链表的遍历：

int ShowDouLinkList(struct DOULinkList* dl, DIR dir) 
{struct DOUNode *tmp = dl->head;if(FORWADR == dir){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( BACKWADR == dir){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 IsEmptyDouLinkList(struct DOULinkList *dl)
{return 0 == dl->clen;
}

        6.获取链表的长度

int GetSizeDouLinkList(struct DOULinkList *dl)
{return dl->clen;
}

三、双向链表的查找

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

四、双向链表的修改

int ModifyDouLinkList(struct DOULinkList *dl,char *name, struct DATATYPE* data)
{struct DOUNode *tmp = FindDouLinkList(dl,name);if(NULL == tmp){return 1;}memcpy(&tmp->data, data, sizeof(struct DATATYPE));return 0;}

五、双向链表的删除

        1.链表的清空：

int DestoryDouLinkList(struct DOULinkList **dl)
{struct DOUNode *tmp = (*dl)->head;while(tmp){if(NULL == tmp){break;}(*dl)->head = (*dl)->head->next;free(tmp);tmp = (*dl)->head;}free(*dl);*dl = NULL;return 0;
}

        2.链表的删除：

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

六、双向链表的逆序

int InverseDouLinkList(struct DOULinkList *dl)
{if(IsEmptyDouLinkList(dl)){return 1;}int len = GetSizeDouLinkList(dl);if( 1 == len){return 0;}struct DOUNode *prev = NULL;struct DOUNode *tmp = dl->head;struct DOUNode *next = dl->head->next;while(1){tmp->next = prev;tmp->prev = next;prev = tmp;tmp = next;if(NULL == tmp){break;}next = next->next;}dl->head = prev;return 0;
}

七、MakeFile工具使用

        三个.c以上可以使用。

        1.方法一：

a.out（目标）:main.c ./doulink (依赖)gcc main.c doulink.c//前面空一个Tab键
clean:rm a.out

       在终端敲make，进行编译,若要指定makefile ，加-f再加指定makefile。

        2.方法二：

#代表源文件
SRC += main.c（变量名任取）//指定变量
SRC += doulink.c
DST = app(可执行文件)CC = gcc//编译器
FLAG = -g
LIB = -lm$(DST):$(SRC)$(CC) $(SRC) $(FLAG) $(LIB)-o(指定名字) $(DST)
clean:rm $(DST)