Chinaunix首页 | 论坛 | 博客
  • 博客访问: 186145
  • 博文数量: 89
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 828
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-08 10:44
文章分类
文章存档

2014年(9)

2013年(80)

我的朋友

分类: C/C++

2013-11-13 16:00:05

双向循环链表功能强大,本文件是双向循环链表的实现函数,包括链表创建,删除,清空,获取链表长度, 获取链表结点,删除链表结点,适用于任意类型的数据结点,链表逆序操作在双向循环链表中的意义和作用不大,故不用实现,使用时传入数据结点指针,及其他参数即可
本代码支持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;  
}  
阅读(583) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~