双向循环链表功能强大，本文件是双向循环链表的实现函数，包括链表创建，删除，清空，获取链表长度， 获取链表结点，删除链表结点，适用于任意类型的数据结点，链表逆序操作在双向循环链表中的意义和作用不大，故不用实现，使用时传入数据结点指针，及其他参数即可
本代码支持DEBUG调试
/********************************************************************************************************************************************
file DbCircleList.h
[cpp] view plaincopyprint?
#ifndef _DBCIRCLELIST_H_
#define _DBCIRCLELIST_H_
typedef void DbCircleList;
typedef void DbCircleListNode;
extern DbCircleList* DbCircleList_Create();
extern void DbCircleList_Destroy(DbCircleList* list);
extern void DbCircleList_Clear(DbCircleList* list);
extern int DbCircleList_Length(DbCircleList* list);
extern int DbCircleList_Insert(DbCircleList* list, DbCircleListNode* node, int pos);
extern DbCircleListNode* DbCircleList_Get(DbCircleList* list, int pos);
extern DbCircleListNode* DbCircleList_Delete(DbCircleList* list, int pos);
extern void DbCircleList_Reverse(DbCircleList* list);
#endif
/********************************************************************************************************************************************
file DbCircleList.c
[cpp] view plaincopyprint?
/**************************************************************************
* 文件名 ： DbCircleList.c
* 文件说明 ：本文件是双向循环链表的实现函数，包括链表创建，删除，清空，获取链表长度，
* 获取链表结点，删除链表结点，适用于任意类型的数据结点，链表逆序操作在双
* 向循环链表中的意义和作用不大，故不用实现，使用时传入数据结点指针，及其
* 他参数即可
**************************************************************************/
//库文件包含
#include
#include
//本地头文件包含
#include "DbCircleList.h"
//调试开关
#define DEBUG
//结构体定义
//封装数据结点定义
typedef struct _tag_TDbCircleListNode TDbCircleListNode;
struct _tag_TDbCircleListNode
{
unsigned int addr; //数据结点地址保存区
TDbCircleListNode* prior; //链表指针
TDbCircleListNode* next; //链表指针
};
//封装链表头结点
typedef struct _tag_TDbCircleList
{
int length; //链表长度
TDbCircleListNode* header; //链表头指针
}TDbCircleList;
//函数实现
/*********************************************************************************
* 函数原型：DbCircleList* DbCircleList_Create()
* 函数说明：创建循环链表
* 参数说明：输入参数：无
* 输出参数：无
* 返回值：DbCircleList* 循环链表指针
*********************************************************************************/
DbCircleList* DbCircleList_Create()
{
//申请头结点空间
TDbCircleList* ret = (TDbCircleList*)malloc(sizeof(TDbCircleList));
#ifdef DEBUG
printf("DbCircleList_Create...");
#endif
if(ret != NULL)
{
ret->length = 0; //循环链表长度初始化
ret->header = NULL; //循环链表头结点指针初始化
}
#ifdef DEBUG
(ret == NULL) ? printf(" Failed.\n") : printf(" Successful.\n");
#endif
return (DbCircleList*)ret; //返回循环链表指针
}
/*********************************************************************************
* 函数原型：void DbCircleList_Destroy(DbCircleList* list)
* 函数说明：删除循环链表
* 参数说明：输入参数：DbCircleList* list 循环链表指针
* 输出参数：无
* 返回值：无
*********************************************************************************/
void DbCircleList_Destroy(DbCircleList* list)
{
#ifdef DEBUG
printf("DbCircleList_Destroy...\n");
#endif
DbCircleList_Clear(list); //清空循环链表
free((TDbCircleList*)list); //释放头结点空间
list = NULL; //清空链表指针
#ifdef DEBUG
printf("DbCircleList_Destroy...Complete.\n");
#endif
}
/*********************************************************************************
* 函数原型：void DbCircleList_Clear(DbCircleList* list)
* 函数说明：循环链表清空
* 参数说明：输入参数：DbCircleList* list 循环链表指针
* 输出参数：无
* 返回值：无
*********************************************************************************/
void DbCircleList_Clear(DbCircleList* list)
{
TDbCircleList* sList = (TDbCircleList*)list;
#ifdef DEBUG
printf("DbCircleList_Clear...\n");
#endif
//链表指针非空且链表有数据结点才可清空
if(sList != NULL && sList->header != NULL)
{
//从编号为0（编号从0开始）的结点开始删除
while(sList->header != sList->header->next)
{
TDbCircleListNode* pNode = sList->header;
sList->header->prior->next = pNode->next;
sList->header->next->prior = pNode->prior;
sList->header = sList->header->next;
#ifdef DEBUG
printf("Clear Node %d .\n", pNode->addr);
#endif
free(pNode);
sList->length--;
}
//删除剩余的编号为0的结点
#ifdef DEBUG
printf("Clear Header Node %d .\n", sList->header->addr);
#endif
free(sList->header);
sList->header = NULL;
sList->length--;
}
#ifdef DEBUG
printf("DbCircleList_Clear...Complete.\n");
#endif
}
/*********************************************************************************
* 函数原型：int DbCircleList_Length(DbCircleList* list)
* 函数说明：获取单链表长度
* 参数说明：输入参数：DbCircleList* list 循环链表指针
* 输出参数：无
* 返回值：获取失败返回-1
* 获取成功返回非负数（单链表当前长度）
************************************************************************/
int DbCircleList_Length(DbCircleList* list)
{
int ret = -1;
TDbCircleList* sList = (TDbCircleList*)list;
#ifdef DEBUG
printf("DbCircleList_Length...");
#endif
if(sList != NULL)
{
ret = sList->length;
}
#ifdef DEBUG
(ret == -1) ? printf(" list is NULL.\n") : printf(" %d\n", ret);
#endif
return ret;
}
/*********************************************************************************
* 函数原型：int DbCircleList_Insert(DbCircleList* list, DbCircleListNode* node, int pos)
* 函数说明：向循环链表中插入结点
* 参数说明：输入参数：DbCircleList* list 循环链表指针
* DbCircleListNode* node 待插入链表数据地址
* int pos 插入位置，从0开始
* 输出参数：无
* 返回值：获取失败返回假（0）
* 获取成功返回真（1）
*********************************************************************************/
int DbCircleList_Insert(DbCircleList* list, DbCircleListNode* node, int pos)
{
TDbCircleList* sList = (TDbCircleList*)list;
int ret = (sList != NULL) && (node != NULL); //检查链表
#ifdef DEBUG
printf("DbCircleList_Insert...");
#endif
if(ret)
{
//申请数据结点空间
TDbCircleListNode* pNew = (TDbCircleListNode*)malloc(sizeof(TDbCircleListNode));
if(pNew != NULL)
{
//保存数据
pNew->addr = (unsigned int)node;
#ifdef DEBUG
printf("Insert Node data %d ", pNew->addr);
#endif
//链表为空时默认插入0号位置
if(sList->header == NULL)
{
pNew->next = pNew;
pNew->prior = pNew;
sList->header = pNew;
sList->length++;
#ifdef DEBUG
printf(" In Header Node\n");
#endif
}
else
{//链表不为空时
int index = (pos >= 0) ? (1) : (-1);
int halfLength = (sList->length + 1) / 2;
//修正插入位置
pos = index * pos;
pos = pos % (sList->length + 1);
pos = (pos < halfLength) ? (pos) : (-(sList->length - pos));
pos = index * pos;
if(pos == 0)
{//插入0位置
pNew->next = sList->header;
sList->header->prior->next = pNew;
pNew->prior = sList->header->prior;
sList->header->prior = pNew;
sList->header = pNew;
}
else
{//插入其他位置：将新结点插入到pos编号结点的前面
//寻找插入位置
TDbCircleListNode* current = sList->header;
if(pos > 0)
{
for(index = 0; index < pos; index ++)
{
current = current->next;
}
}
else
{
for(index = -1; index > pos; index --)
{
current = current->prior;
}
}
//插入数据节点到pos编号结点的前面
pNew->next = current->prior->next;
current->prior->next = pNew;
pNew->prior = current->prior;
current->prior = pNew;
}
sList->length++;
#ifdef DEBUG
printf(" In %d Node\n", pos);
#endif
}
}
else
{
ret = 0;
}
}
#ifdef DEBUG
if(ret == 0)
printf(" Failed.\n");
#endif
return ret;
}
/*********************************************************************************
* 函数原型：DbCircleListNode* DbCircleList_Get(DbCircleList* list, int pos)
* 函数说明：获取链表中编号为pos的数据
* 参数说明：输入参数：DbCircleList* list 循环链表指针
* int pos 获取编号，从0开始
* 输出参数：无
* 返回值：DbCircleListNode* 链表数据地址，为空表示获取失败
*********************************************************************************/
DbCircleListNode* DbCircleList_Get(DbCircleList* list, int pos)
{
TDbCircleList* sList = (TDbCircleList*)list;
DbCircleListNode* ret = NULL;
#ifdef DEBUG
printf("DbCircleList_Get...");
#endif
//判断链表是否合法，判断获取位置是否合法
if( (sList != NULL) && (0 <= pos) )
{
int index = (pos >= 0) ? (1) : (-1);
int halfLength = (sList->length + 1) / 2;
TDbCircleListNode* current = sList->header;
//修正获取位置编号
pos = index * pos;
pos = pos % (sList->length + 1);
pos = (pos < halfLength) ? (pos) : (-(sList->length - pos));
pos = index * pos;
//查找获取位置
if(pos >= 0)
{
for(index = 0; index < pos; index ++)
{
current = current->next;
}
}
else
{
for(index = -1; index > pos; index --)
{
current = current->prior;
}
}
#ifdef DEBUG
printf(" From %d Node", pos);
#endif
ret = (DbCircleListNode*)(current->addr);
}
#ifdef DEBUG
(ret == NULL) ? printf(" Failed.\n") : printf(" %d .\n", (int)ret);
#endif
return ret;
}
/*********************************************************************************
* 函数原型：DbCircleListNode* DbCircleList_Delete(DbCircleList* list, int pos)
* 函数说明：删除链表中编号为pos的数据，并将其返回
* 参数说明：输入参数：DbCircleList* list 循环链表指针
* int pos 获取编号，从0开始
* 输出参数：无
* 返回值：DbCircleListNode* 链表数据地址，为空表示删除失败
*********************************************************************************/
DbCircleListNode* DbCircleList_Delete(DbCircleList* list, int pos)
{
TDbCircleList* sList = (TDbCircleList*)list;
DbCircleListNode* ret = NULL;
#ifdef DEBUG
printf("DbCircleList_Delete...");
#endif
//判断链表是否合法，判断获取位置是否合法
if( (sList != NULL) && (0 <= pos) )
{
int index = (pos >= 0) ? (1) : (-1);
int halfLength = (sList->length + 1) / 2;
TDbCircleListNode* current = sList->header;
//修正删除位置编号
pos = index * pos;
pos = pos % (sList->length + 1);
pos = (pos < halfLength) ? (pos) : (-(sList->length - pos));
pos = index * pos;
//查找删除位置
if(pos >= 0)
{
for(index = 0; index < pos; index ++)
{
current = current->next;
}
}
else
{
for(index = -1; index > pos; index --)
{
current = current->prior;
}
}
//保存删除数据
ret = (DbCircleListNode*)(current->addr);
#ifdef DEBUG
printf(" From %d Node", pos);
#endif
//若删除的是编号为0的结点，先修改头指针
if(pos == 0)
{
sList->header = sList->header->next;
}
//删除结点
current->prior->next = current->next;
current->next->prior = current->prior;
free(current);
sList->length--;
//若删除完后，链表长度为0，复位链表
if(sList->length == 0)
{
sList->header = NULL;
}
}
#ifdef DEBUG
(ret == NULL) ? printf(" Failed.\n") : printf(" %d .\n", (int)ret);
#endif
return ret;
}
/********************************************************************************************************************************************
file main.c
[cpp] view plaincopyprint?
#include
#include
#include "DbCircleList.h"
#define TEST_NUM 10
char Test_Data[10] = {'0','1','2','3','4','5','6','7','8','9'};
int main(int argc, char *argv[])
{
int index = 0;
DbCircleList* list = DbCircleList_Create();
printf(" Length Before Insert = %d\n", DbCircleList_Length(list));
for(index = 0; index < TEST_NUM - 2; index ++)
{
DbCircleList_Insert(list, Test_Data+index, 0);
}
printf(" Length After Insert and Before Clear = %d\n", DbCircleList_Length(list));
DbCircleList_Clear(list);
printf(" Length After Clear and Before Insert again = %d\n", DbCircleList_Length(list));
for(index = 0; index < TEST_NUM; index ++)
{
DbCircleList_Insert(list, Test_Data+index, -7);
}
printf(" Length After Insert again and Before Delete = %d\n", DbCircleList_Length(list));
for(index = 0; index < DbCircleList_Length(list); index ++)
{
printf("%c\n", *(char *)DbCircleList_Get(list, index));
}
printf("Delete:\n");
for(index = 0; index < TEST_NUM/2; index ++)
{
printf("%c\n", *(char *)DbCircleList_Delete(list, 0));
}
printf("After Delete:\n");
for(index = 0; index < DbCircleList_Length(list); index ++)
{
printf("%c\n", *(char *)DbCircleList_Get(list, index));
}
printf("Destroy:\n");
DbCircleList_Destroy(list);
printf("Test Complete.\nPlease Input a char to Quit :");
Test_Data[0] = getchar();
return 0;
}
阅读(549) | 评论(0) | 转发(0) |
