小可爱～ 发表于 2017-2-13 22:02

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

本帖最后由 小可爱～ 于 2017-2-13 22:06 编辑

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




//测试
#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;
}

小可爱～ 发表于 2017-2-13 22:03

本帖最后由 小可爱～ 于 2017-2-13 22:08 编辑

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

mjikop1231 发表于 2017-2-13 22:13

STL大法好

小可爱～ 发表于 2017-2-13 22:15

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

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

mjikop1231 发表于 2017-2-13 22:18

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

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

小可爱～ 发表于 2017-2-14 00:23

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

还行吧用过但是忘记了{:1_907:}

yysniper 发表于 2017-2-15 16:54

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

yysniper 发表于 2017-2-15 16:55

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

流浪的野指针 发表于 2018-9-6 21:55

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

和泉纱雾 发表于 2018-9-10 00:48

大佬们是真的强，我这种鶸搓个一般的线段树都会有bug
页: [1] 2
查看完整版本: [C语言][数据结构]双向链表源码


免责声明：
吾爱破解所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。本站信息来自网络，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑中彻底删除上述内容。如果您喜欢该程序，请支持正版软件，购买注册，得到更好的正版服务。如有侵权请邮件与我们联系处理。

Mail To:Service@52pojie.cn