首页 > 资讯 > C++ > 正文

4--循环链表

16-04-20 来源：[db:作者]

收藏我要投稿

1、基本概念

循环链表的定义：将单链表中最后一个数据元素的next指针指向第一个元素

循环链表拥有单链表的所有操作:

创建链表

销毁链表

获取链表长度

清空链表

获取第pos个元素操作

插入元素到位置pos

删除位置pos处的元素

游标的定义

在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素。

循环链表新操作:

获取当前游标指向的数据元素

将游标重置指向链表中的第一个数据元素

将游标移动指向到链表中的下一个数据元素

直接指定删除链表中的某个数据元素

2、设计与实现

插入元素的分析

普通位置插入元素添加第一个元素（第一次插入元素）最后一个位置插入元素第一个位置插入元素(如图):

添加第一个元素如图：

在最后一个位置插入元素如图：

删除节点

3、优点和缺点

优点：功能强了。循环链表只是在单链表的基础上做了一个加强，循环链表可以完全取代单链表的使用，循环链表的Next和Current操作可以高效的遍历链表中的所有元素

缺点：代码复杂度提高了

约瑟夫问题-循环链表典型应用

n个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数，报到第m个人，令其出列。然后再从下一个人开始从1顺时针报数，报到第m个人，再令其出列，…，如此下去，求出列顺序。

CircleList.h 

#ifndef _CIRCLELIST_H_

#define _CIRCLELIST_H_

typedef void CircleList;

/*

typedef struct _tag_CircleListNode CircleListNode;

struct _tag_CircleListNode

{

CircleListNode* next;

};

*/

typedef struct _tag_CircleListNode

{

 struct _tag_CircleListNode * next;

}CircleListNode;

CircleList* CircleList_Create();

void CircleList_Destroy(CircleList* list);

void CircleList_Clear(CircleList* list);

int CircleList_Length(CircleList* list);

int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);

CircleListNode* CircleList_Get(CircleList* list, int pos);

CircleListNode* CircleList_Delete(CircleList* list, int pos);

//add

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);

CircleListNode* CircleList_Reset(CircleList* list);

CircleListNode* CircleList_Current(CircleList* list);

CircleListNode* CircleList_Next(CircleList* list);

#endif

CircleList.c

#include 

#include 

#include "CircleList.h"

typedef struct _tag_CircleList

{

 CircleListNode header;

 CircleListNode* slider;

 int length;

} TCircleList;

CircleList* CircleList_Create() // O(1)

{

 TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList));

 if (ret == NULL)

 {

  return NULL;

 }

 

 ret->length = 0;

 ret->header.next = NULL;

 ret->slider = NULL;

 return ret;

}

void CircleList_Destroy(CircleList* list) // O(1)

{

 if (list == NULL)

 {

  return ;

 }

 free(list);

}

void CircleList_Clear(CircleList* list) // O(1)

{

 TCircleList* sList = (TCircleList*)list;

 if (sList == NULL)

 {

  return ;

 }

 sList->length = 0;

 sList->header.next = NULL;

 sList->slider = NULL;

}

int CircleList_Length(CircleList* list) // O(1)

{

 TCircleList* sList = (TCircleList*)list;

 int ret = -1;

 if (list == NULL)

 {

  return ret;

 }

 ret = sList->length;

 return ret;

}

int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) // O(n)

{

 int ret = 0, i=0;

 TCircleList* sList = (TCircleList*)list;

 if (list == NULL || node== NULL || pos<0)

 {

  return -1;

 }

 //if( ret )

 {

  CircleListNode* current = (CircleListNode*)sList;

  for(i=0; (inext != NULL); i++)

  {

   current = current->next;

  }

  //current->next 0号节点的地址

  node->next = current->next; //1

  current->next = node; //2

  //若第一次插入节点

  if( sList->length == 0 )

  {

   sList->slider = node;

  }

  sList->length++;

  //若头插法

  if( current == (CircleListNode*)sList )

  {

   //获取最后一个元素

   CircleListNode* last = CircleList_Get(sList, sList->length - 1);

   last->next = current->next; //3

  }

 }

 return ret;

}

CircleListNode* CircleList_Get(CircleList* list, int pos) // O(n)

{

 TCircleList* sList = (TCircleList*)list;

 CircleListNode* ret = NULL;

 int i = 0;

 if (list==NULL || pos<0)

 {

  return NULL;

 }

 //if( (sList != NULL) && (pos >= 0) && (sList->length > 0) )

 {

  CircleListNode* current = (CircleListNode*)sList;

  for(i=0; inext;

  }

  ret = current->next;

 }

 return ret;

}

CircleListNode* CircleList_Delete(CircleList* list, int pos) // O(n)

{

 TCircleList* sList = (TCircleList*)list;

 CircleListNode* ret = NULL;

 int i = 0;

 if( (sList != NULL) && (pos >= 0) && (sList->length > 0) )

 {

  CircleListNode* current = (CircleListNode*)sList;

  CircleListNode* last = NULL;

  for(i=0; inext;

  }

  //若删除第一个元素

  if( current == (CircleListNode*)sList )

  {

   last = (CircleListNode*)CircleList_Get(sList, sList->length - 1);

  }

  //求要删除的元素

  ret = current->next;

  current->next = ret->next;

  sList->length--;

  //判断链表是否为空

  if( last != NULL )

  {

   sList->header.next = ret->next;

   last->next = ret->next;

  }

  //若删除的元素为游标所指的元素

  if( sList->slider == ret )

  {

   sList->slider = ret->next;

  }

  //若删除元素后，链表长度为0

  if( sList->length == 0 )

  {

   sList->header.next = NULL;

   sList->slider = NULL;

  }

 }

 return ret;

}

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) // O(n)

{

 TCircleList* sList = (TCircleList*)list;

 CircleListNode* ret = NULL;

 int i = 0;

 if( sList != NULL )

 {

  CircleListNode* current = (CircleListNode*)sList;

 

  //查找node在循环链表中的位置i

  for(i=0; ilength; i++)

  {

   if( current->next == node )

   {

    ret = current->next;

    break;

   }

   current = current->next;

  }

 

  //如果ret找到，根据i去删除

  if( ret != NULL )

  {

   CircleList_Delete(sList, i);

  }

 }

 return ret;

}

CircleListNode* CircleList_Reset(CircleList* list) // O(1)

{

 TCircleList* sList = (TCircleList*)list;

 CircleListNode* ret = NULL;

 if( sList != NULL )

 {

  sList->slider = sList->header.next;

  ret = sList->slider;

 }

 return ret;

}

CircleListNode* CircleList_Current(CircleList* list) // O(1)

{

 TCircleList* sList = (TCircleList*)list;

 CircleListNode* ret = NULL;

 if( sList != NULL )

 {

  ret = sList->slider;

 }

 return ret;

}

CircleListNode* CircleList_Next(CircleList* list) // O(1)

{

 TCircleList* sList = (TCircleList*)list;

 CircleListNode* ret = NULL;

 if( (sList != NULL) && (sList->slider != NULL) )

 {

  ret = sList->slider;

  sList->slider = ret->next;

 }

 return ret;

}

#include 

#include 

#include "CircleList.h"

struct Value

{

 CircleListNode header;

 int v;

};

void  main()

{

 int i = 0;

 CircleList* list = CircleList_Create();

 struct Value v1;

 struct Value v2;

 struct Value v3;

 struct Value v4;

 struct Value v5;

 struct Value v6;

 struct Value v7;

 struct Value v8;

 v1.v = 1;

 v2.v = 2;

 v3.v = 3;

 v4.v = 4;

 v5.v = 5;

 v6.v = 6;

 v7.v = 7;

 v8.v = 8;

 CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v5, 5);

 CircleList_Delete(list, 0);

 for(i=0; i<2*CircleList_Length(list); i++)

 {

  struct Value* pv = (struct Value*)CircleList_Get(list, i);

  printf("%d\n", pv->v);

 }

 printf("\n");

 while( CircleList_Length(list) > 0 )

 {

  struct Value* pv = (struct Value*)CircleList_Delete(list, 0);

  printf("%d\n", pv->v);

 }

 printf("\n");

 CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));

 CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));

 for(i=0; iv);

 }

 printf("\n");

 CircleList_Reset(list);

 while( CircleList_Length(list) > 0 )

 {

  struct Value* pv = NULL;

  for(i=1; i<3; i++)

  {

   CircleList_Next(list);

  }

  pv = (struct Value*)CircleList_Current(list);

  printf("%d\n", pv->v);

  CircleList_DeleteNode(list, (CircleListNode*)pv);

 }

 CircleList_Destroy(list);

 system("pause");

 return ;

}

点击复制链接与好友分享!回本站首页