[数据结构]#3 循环链表/双向链表

循环链表
简单的来说，就是将原来单链表中最有一个元素的next指针指向第一个元素或头结点，链表就成了一个环，头尾相连，就成了循环链表——circultlar linker list。

注意非空表，和空表。多数会加入头结点。
原来结束的条件是：
p->next != NULL ——> p-next != Head 

我们再结合单向链表的结构，则可得到更加实用的双向链表——double link list。

其基本框架的搭建：

#include "DouLink.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>//创建双向链表
DouLinkList *CreateDouLinkList()
{DouLinkList *dl = malloc(sizeof(DouLinkList));if (NULL == dl){fprintf(stderr, "CreateDouLinkList malloc\n");return NULL;}dl->head = NULL;dl->clen = 0;return dl;
}//检查是否为空
int IsEmpytDouLinkList(DouLinkList *dl)
{return 0 == dl->clen;
}//打印
int ShowDouLinkList(DouLinkList *dl, SHOW_DIR dir)
{int size = GetSizeDouLinkList(dl);DouLinkNode *tmp = dl->head;if (DIR_FORWARD == dir){for (int i = 0; i < size; i++){printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex,tmp->data.age, tmp->data.score);tmp = tmp->next;}}else{while (tmp->next){tmp = tmp->next;}for (int i = 0; i < size; i++){printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex,tmp->data.age, tmp->data.score);tmp = tmp->prev;}}
}//有效元素个数
int GetSizeDouLinkList(DouLinkList *dl)
{return dl->clen;
}//释放内存
int DestroyDouLinkList(DouLinkList *dl)
{DouLinkNode *tmp = dl->head;int size = GetSizeDouLinkList(dl);for (int i = 0; i < size; i++){tmp = dl->head;dl->head = dl->head->next;free(tmp);}free(dl);return 0;
}

然后是双向链表的操作（增、删、改、查）：

//头插
int InsertHeadDouLinkList(DouLinkList *dl, DATATYPE *data)
{DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){fprintf(stderr, "InsertHeadDouLinkList malloc\n");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->prev = NULL;if (IsEmpytDouLinkList(dl)){dl->head = newnode;}else{newnode->next = dl->head;dl->head->prev = newnode;dl->head = newnode;}dl->clen++;return 0;
}//尾插
int InsertTailDouLinkList(DouLinkList *dl, DATATYPE *data)
{if (IsEmpytDouLinkList(dl)){return InsertHeadDouLinkList(dl, data);}DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){fprintf(stderr, "InsertTailDouLinkList malloc\n");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->prev = NULL;DouLinkNode *tmp = dl->head;while (tmp->next){tmp = tmp->next;}// init_nodenewnode->prev = tmp;tmp->next = newnode;dl->clen++;return 0;
}//按位置插入
int InsertPosDouLinkList(DouLinkList *dl, DATATYPE *data, int pos)
{int size = GetSizeDouLinkList(dl);if (pos < 0 || pos > size){return 1;}if (0 == pos)  // head{return InsertHeadDouLinkList(dl, data);}else if (pos == size)  // tail{return InsertTailDouLinkList(dl, data);}else  // mid{DouLinkNode *tmp = dl->head;for (int i = 0; i < pos - 1; i++){tmp = tmp->next;}// tmp at end node// init_node; malloc ,NULL,NULLDouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){fprintf(stderr, "InsertTailDouLinkList malloc\n");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->prev = NULL;newnode->next = tmp->next;newnode->prev = tmp;newnode->next->prev = newnode;tmp->next = newnode;dl->clen++;}return 0;
}//删除
int DeleteDouLinkList(DouLinkList *dl, char *name)
{DouLinkNode *tmp = FindDouLinkList(dl, name);if (NULL == tmp){printf("DeleteDouLinkList error\n");return 1;}if (tmp == dl->head){dl->head = dl->head->next;if (dl->head->prev){dl->head->prev = NULL;}}else  // mid end{if (tmp->next){tmp->next->prev = tmp->prev;}tmp->prev->next = tmp->next;}free(tmp);dl->clen--;return 0;
}//修改
int ModifyDouLinkList(DouLinkList *dl, char *name, DATATYPE *data)
{DouLinkNode *tmp = FindDouLinkList(dl, name);if (NULL == tmp){printf("modify failure...\n");return 1;}memcpy(&tmp->data, data, sizeof(DATATYPE));return 0;
}//查找
DouLinkNode *FindDouLinkList(DouLinkList *dl, char *name)
{DouLinkNode *tmp = dl->head;while (tmp){if (0 == strcmp(tmp->data.name, name)){return tmp;}tmp = tmp->next;}return NULL;
}