程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 4--循環鏈表

4--循環鏈表

編輯:C++入門知識

4--循環鏈表


1、基本概念

循環鏈表的定義:將單鏈表中最後一個數據元素的next指針指向第一個元素

\

循環鏈表擁有單鏈表的所有操作:

 

創建鏈表

銷毀鏈表

獲取鏈表長度

清空鏈表

獲取第pos個元素操作

插入元素到位置pos

刪除位置pos處的元素

游標的定義

在循環鏈表中可以定義一個“當前”指針,這個指針通常稱為游標,可以通過這個游標來遍歷鏈表中的所有元素。

\

循環鏈表新操作:

獲取當前游標指向的數據元素

將游標重置指向鏈表中的第一個數據元素

將游標移動指向到鏈表中的下一個數據元素

直接指定刪除鏈表中的某個數據元素

2、設計與實現

插入元素的分析

  1. 普通位置插入元素添加第一個元素(第一次插入元素)最後一個位置插入元素第一個位置插入元素(如圖):

    添加第一個元素如圖:\

    \

    在最後一個位置插入元素如圖:\

    刪除節點\

     

    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 ;
    
    }


     

     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved