[C语言][数据结构]双向链表源码

小可爱～

顺带问下, 现在这个时代 还要关注内存碎片么???
在服务器上面的程序不断  new delete malloc free 产生的内存碎片需要关注么??
服务器两个月重启一次的那种//头文件
//doublelist.h

[C] 纯文本查看 复制代码

#pragma once //doublelist.h
typedef void vDoubleList;

typedef struct _linux_list 
{
        struct _linux_list *pPre;
        struct _linux_list *pNext;
}DoubleListnode;

vDoubleList* DoubleList_Create();

void DoubleList_Destroy(vDoubleList* list);

void DoubleList_Clear(vDoubleList* list);

int DoubleList_Length(vDoubleList* list);

int DoubleList_Insert(vDoubleList* list, DoubleListnode* node, int pos);

DoubleListnode* DoubleList_Get(vDoubleList* list, int pos);

DoubleListnode* DoubleList_Delete(vDoubleList* list, int pos);


//add

DoubleListnode* DoubleList_DeleteNode(vDoubleList* list, DoubleListnode* node);

DoubleListnode *DoubleList_Pre(list);

DoubleListnode* DoubleList_Reset(vDoubleList* list);

DoubleListnode* DoubleList_Current(vDoubleList* list);

DoubleListnode* DoubleList_Next(vDoubleList* list);

//doublelist.c

[C] 纯文本查看 复制代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "doublelist.h"
//doublelist.c
typedef struct _tag_DoubleList
{
        DoubleListnode node;
        DoubleListnode *slider;
        int Length;
}TList;

vDoubleList* DoubleList_Create()
{
        TList *tList = (TList *)malloc(sizeof(TList));
        if (NULL == tList)
        {
                return NULL;
        }
        tList->Length = 0;
        tList->node.pNext = NULL;
        tList->node.pPre = NULL;
        tList->slider = NULL;
        return (vDoubleList*)tList;
}

void DoubleList_Destroy(vDoubleList* list)
{
        TList *tList = (TList *)list;
        if (NULL != tList)
        {
                free(tList);
        }
}

void DoubleList_Clear(vDoubleList* list)
{
        TList *tList = (TList *)list;
        if (NULL == tList)
        {
                return;
        }
        tList->Length = 0;
        tList->node.pNext = NULL;
        tList->node.pPre = NULL;
        tList->slider = NULL;
}

int DoubleList_Length(vDoubleList* list)
{
        TList *tList = (TList *)list;
        if (NULL == tList)
        {
                return -1;
        }
        return (tList->Length);
}

int DoubleList_Insert(vDoubleList* list, DoubleListnode* node, int pos)
{
        TList *tList = (TList *)list;
        DoubleListnode *Cur = (DoubleListnode *)list;
        DoubleListnode *Next = NULL;
        int ret = 0;
        int i = 0;
        if (NULL == tList || NULL == node || pos < 0)
        {
                return -1;
        }

        for (i = 0; i < pos && Cur->pNext != NULL; i++)
        {
                Cur = Cur->pNext;
        }
        Next = Cur->pNext;

        Cur->pNext = node;                        //pNext
        node->pNext = Cur->pNext;        //新数据的pNext
        node->pPre = Cur;                        //新数据的pPre
        if (NULL != Next)
        {
                Next->pPre = node;                //后一个数据pPre
        }
        if (0 == tList->Length)
        {
                tList->slider = node;
        }
        tList->Length++;
        if (Cur == (DoubleListnode *)tList)
        {
                DoubleListnode *last = DoubleList_Get(list, tList->Length - 1);
                last->pNext = Cur->pNext;
        }
        return 0;
}

DoubleListnode* DoubleList_Get(vDoubleList* list, int pos)
{
        TList *tList = (TList *)list;
        int i = 0;
        DoubleListnode *Cur = (DoubleListnode *)list;
        if (NULL == tList || pos < 0 || tList->Length < pos)
        {
                return NULL;
        }
        for (i = 0; i < pos && tList->Length > pos; i++)
        {
                Cur = Cur->pNext;
        }
        Cur = Cur->pNext;
        return (DoubleListnode*)Cur;
}

DoubleListnode* DoubleList_Delete(vDoubleList* list, int pos)
{
        int i = 0;
        if (list == NULL)
        {
                return NULL;
        }
        TList * tlist = (TList *)list;
        //位置判断
        if (pos<0 || pos > tlist->Length)
        {
                return NULL;
        }
        //普通情况处理
        //定义两个变量 
        DoubleListnode * pPrior = &tlist->node, *pCurrent = tlist->node.pNext, *pNext = NULL;
        for (i = 0; i < pos; i++)
        {
                pPrior = pCurrent;
                pCurrent = pCurrent->pNext;
        }
        pNext = pCurrent->pNext;
        pPrior->pNext = pNext;
        if (pNext != NULL)
        {
                pNext->pPre = pPrior;
                //判断删除的是否是第0个元素
                if (pPrior == &tlist->node)
                {
                        pNext->pPre = NULL;
                }
        }
        tlist->Length--;
        return pCurrent;
}

//add

DoubleListnode* DoubleList_DeleteNode(vDoubleList* list, DoubleListnode* node)
{
        int i = 0;
        if (list == NULL || node == NULL)
        {
                return NULL;
        }
        TList * tlist = (TList *)list;
        DoubleListnode * pCur = &tlist->node;
        for (i = 0; i < tlist->Length; i++)
        {
                pCur = pCur->pNext;
                if (pCur == node)
                {
                        break;
                }
        }
        return DoubleList_Delete(list, i);
}

DoubleListnode* DoubleList_Reset(vDoubleList* list)
{
        if (list == NULL)
        {
                return NULL;
        }
        TList * tlist = (TList *)list;
        tlist->slider = tlist->node.pNext;
        return tlist->slider;
}

DoubleListnode* DoubleList_Current(vDoubleList* list)
{
        if (list == NULL)
        {
                return NULL;
        }
        TList * tlist = (TList *)list;
        return tlist->slider;
}

DoubleListnode* DoubleList_Next(vDoubleList* list)
{
        if (list == NULL)
        {
                return NULL;
        }
        TList * tlist = (TList *)list;
        if (tlist->slider == NULL)
        {
                return NULL;
        }
        tlist->slider = tlist->slider->pNext;
        return tlist->slider;
}

DoubleListnode *DoubleList_Pre(vDoubleList *list)
{
        if (list == NULL)
        {
                return NULL;
        }
        TList * tlist = (TList *)list;
        if (tlist->slider == NULL)
        {
                return NULL;
        }
        tlist->slider = tlist->slider->pPre;
        return tlist->slider;
}

//测试

[C] 纯文本查看 复制代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "doublelist.h"

typedef struct _Teacher 
{
        DoubleListnode node;
        int age;
}Teacher;

int main()
{
        int ret = 0, i = 0;
        vDoubleList* list = DoubleList_Create();
        Teacher t1, t2, t3, t4, t5;
        Teacher *tmp = NULL;
        t1.age = 1, t2.age = 2, t3.age = 3, t4.age = 4, t5.age = 5;
        ret = DoubleList_Insert(list, (DoubleListnode*)&t1, DoubleList_Length(list));
        ret = DoubleList_Insert(list, (DoubleListnode*)&t2, DoubleList_Length(list));
        ret = DoubleList_Insert(list, (DoubleListnode*)&t3, DoubleList_Length(list));
        ret = DoubleList_Insert(list, (DoubleListnode*)&t4, DoubleList_Length(list));
        ret = DoubleList_Insert(list, (DoubleListnode*)&t5, DoubleList_Length(list));

        for (i = 0; i < DoubleList_Length(list); i++)
        {
                tmp = (Teacher *)DoubleList_Get(list, i);
                printf("DoubleList_Get tmp->age = %d\n", tmp->age);
        }
        puts("");

        DoubleList_Delete(list, DoubleList_Length(list) - 1);
        DoubleList_Delete(list, 0);
        for (i = 0; i < DoubleList_Length(list); i++)
        {
                tmp = (Teacher *)DoubleList_Get(list, i);
                printf("DoubleList_Delete 后 tmp->age = %d\n", tmp->age);
        }
        puts("");

        DoubleList_Reset(list);
        DoubleList_Next(list);
        tmp = (Teacher *)DoubleList_Current(list);
        printf("DoubleList_Current tmp->age = %d\n", tmp->age);
        DoubleList_DeleteNode(list, (DoubleListnode *)tmp);
        tmp = (Teacher *)DoubleList_Current(list);
        printf("DoubleList_DeleteNode tmp->age = %d\n", tmp->age);
        printf("DoubleList_Length = %d\n", DoubleList_Length(list));
        DoubleList_Destroy(list);
        system("pause");
        return 0;
}

小可爱～

下次写个双向循环链表出来,
是不是要设置个隐藏什么的, 要不又没人回复,
导致一直以为论坛的人都不学c/c++了

mjikop1231

STL大法好

小可爱～

mjikop1231 发表于 2017-2-13 22:13
STL大法好

好个屁, 有了stl数据结构都不想学了, 最近才捡回来学一点的

mjikop1231

小可爱～ 发表于 2017-2-13 22:15
好个屁, 有了stl数据结构都不想学了, 最近才捡回来学一点的

说真的比起双向链表我更喜欢去手写二叉树、线段树、哈弗曼树之类的。。。
原因就是。。。链表STL实现挺不错了。。。

小可爱～

mjikop1231 发表于 2017-2-13 22:18
说真的比起双向链表我更喜欢去手写二叉树、线段树、哈弗曼树之类的。。。
原因就是。。。链表STL实现挺 ...

还行吧用过但是忘记了

yysniper

最近也在学数据结构，看了大家推荐的严蔚敏的书，感觉不太通俗易懂啊

yysniper

还有一直很奇怪，论坛编程语言区尽然没有C/C++块。C/C++和VC又不是一个东西

流浪的野指针

严蔚敏的书，我感觉还行呀！

和泉纱雾

大佬们是真的强，我这种鶸搓个一般的线段树都会有bug