C数据结构 : 线性表 与 链表

一、线性表

　　一般表现为数组，使用一组地址连续的存储单元依次存储数据元素，如图：

　　它具有如下特点：

• 长度固定，必须在分配内存之前确定数组的长度。
• 存储空间连续，即允许元素的随机访问。
• 存储密度大，内存中存储的全部是数据元素。
• 要访问特定元素，可以使用索引访问，时间复杂度为 。
• 要想在顺序表中插入或删除一个元素，都涉及到之后所有元素的移动，因此时间复杂度为O(n) 。

代码示例：

seqlist.c

#include <stdio.h>
#include <malloc.h>
#include "seqlist.h"

typedef unsigned int TSeqListNode; //数据元素类型用

typedef struct _tag_SeqList
{
    int capacity; //最大长度
    int length;   //当前长度
    TSeqListNode* node; //指针->数组
}TSeqList;

SeqList* SeqList_Create(int capacity) // O(1)
{
   TSeqList* ret = NULL; //真实线性表指针 

   if( capacity >= )
   {
     ret = (TSeqList*)malloc(sizeof(TSeqList) + sizeof(TSeqListNode)*capacity);
   }

   if(ret != NULL)
   {
      ret->capacity =  capacity;
      ret->length = ;
      ret->node = (TSeqListNode*)(ret+); //指向头后数据段
   }
  return ret;
}

void SeqList_Destroy(SeqList* list) // O(1)
{
    free(list);
}

void SeqList_Clear(SeqList* list) // O(1)
{
    TSeqList* sList = (TSeqList*)list;

    if( sList != NULL)
    {
        sList->length = ;
    }
}

int SeqList_Length(SeqList* list) // O(1)
{
  TSeqList* sList = (TSeqList*)list;
  int ret = -;

    if( sList != NULL)
    {
        ret = sList->length;
    }

   return ret;
}

int SeqList_Capacity(SeqList* list) // O(1)  获取最大容量
{
   TSeqList* sList = (TSeqList*)list;
   int ret = -;

    if( sList != NULL )
    {
        ret = sList->capacity;
    }  

   return ret;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos) // O(n)
{
    TSeqList* sList = (TSeqList*)list;
    int ret = (sList != NULL);
    int i = ;

    ret = ret && (sList->length +  <= sList->capacity);
    ret = ret && ( <= pos);

    if( ret )
    {
      if( pos >= sList->length ) //要插入的位置是否大于已存数据的长度
      {
        pos = sList->length;
      }

       for(i = sList->length; i>pos; i--) //数据后移
       {
         sList->node[i] = sList->node[i-];
       }
        sList->node[i] = (TSeqListNode)node;

        sList->length++;
    }

   return ret;
}

SeqListNode* SeqList_Get(SeqList* list, int pos) // O(1)
{
    TSeqList* sList = (TSeqList*)list;
    SeqListNode* ret = NULL;

    if((sList != NULL) && ( <= pos) && (pos < sList->length))
    {
        ret = (SeqListNode*)(sList->node[pos]);
    }
   return ret;
}

SeqListNode* SeqList_Delete(SeqList* list, int pos) // O(n)
{
    TSeqList* sList = (TSeqList*)list;
    SeqListNode* ret = SeqList_Get(list,pos);
    int i = ;

    if( ret != NULL)
    {
       for(i = pos+; i<sList->length; i++)
       {
         sList->node[i-] = sList->node[i];   //数据前移
       }
    }

    sList->length--;

    return ret;
}

seqlist.h

#ifndef _SEQLIST_H_
#define _SEQLIST_H_

typedef void SeqList;      //定义void 数据封装
typedef void SeqListNode;

SeqList* SeqList_Create(int capacity); //创建线性表

void SeqList_Destroy(SeqList* list); //销毁线性表 

void SeqList_Clear(SeqList* list); //清空线性表

int SeqList_Length(SeqList* list); //读取线性表长度

int SeqList_Capacity(SeqList* list); //读取线性表最大长度

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos); //插入新元素node

SeqListNode* SeqList_Get(SeqList* list, int pos); //获取pos位置处的元素

SeqListNode* SeqList_Delete(SeqList* list, int pos);//删除pos位置处的元素

#endif

Smain.c

int main(int argc, char *argv[])
{
  SeqList* list = SeqList_Create();

  int i = ;
  int j = ;
  int k = ;
  int x = ;
  int y = ;
  int z = ;
  int index = ;

  SeqList_Insert(list, &i, );
  SeqList_Insert(list, &j, );
  SeqList_Insert(list, &k, );
  SeqList_Insert(list, &x, );
  SeqList_Insert(list, &y, );
  SeqList_Insert(list, &z, );

  printf(" Length is :%d\n", SeqList_Length(list));

  SeqList_Delete(list,);

  printf("%d\n", SeqList_Get(list,));

  SeqList_Destroy(list);

    printf("Press enter to continue ...");
    getchar();
    return ;
}

二、静态链表
 　　在某些语言中指针是不被支持的,只能使用数组来模拟线性链表的结构.在数组中每个元素不但保存了当前元素的值,还保存了一个”伪指针域”,一般是int类型,用于指向下一个元素的内存地址.这种链表在初始时必须分配足够的空间, 也就是空间大小是静态的, 在进行插入和删除时则不需要移动元素, 修改指针域即可,所以仍然具有链表的主要优点(快速插入和删除).

代码示例：

StaticList.c

#include <stdio.h>
#include <malloc.h>
#include "StaticList.h"

#define AVAILABLE -1

typedef struct _tag_StaticListNode
{
    unsigned int data; //数据 复用length
    int next;          //数据元素下标，next是表示下一个节点在数组中存放的位置
} TStaticListNode;

typedef struct _tag_StaticList  //线性表结构体
{
    int capacity;
    TStaticListNode header; //头结点
    TStaticListNode node[]; //数据结点
} TStaticList;

StaticList* StaticList_Create(int capacity) // O(n)
{
    TStaticList* ret = NULL;
    int i = ;

    if( capacity >=  )
    {
        ret = (TStaticList*)malloc(sizeof(TStaticList) + sizeof(TStaticListNode) * (capacity + ));
    }

    if( ret != NULL )
    {
        ret->capacity = capacity;
        ret->header.data = ;
        ret->header.next = NULL;

        for(i=; i<=capacity; i++)
        {
            ret->node[i].next = AVAILABLE;
        }
    }

    return ret;
}

void StaticList_Destroy(StaticList* list) // O(1)
{
    free(list);
}

void StaticList_Clear(StaticList* list) // O(n)
{
    TStaticList* sList = (TStaticList*)list;
    int i = ;

    if( sList != NULL )
    {
        sList->header.data = ; //->长度为零
        sList->header.next = ; //->头结点next指针为零 

        for(i=; i<=sList->capacity; i++)  //初始化为空闲状态
        {
           sList->node[i].next = AVAILABLE;
        }
    }
}

int StaticList_Length(StaticList* list) // O(1)
{
    TStaticList* sList = (TStaticList*)list;
    int ret = -;

    if( sList != NULL )
    {
        ret = sList->header.data;
    }

    return ret;
}

int StaticList_Capacity(StaticList* list) // O(1)
{
    TStaticList* sList = (TStaticList*)list;
    int ret = -;

    if( sList != NULL )
    {
        ret = sList->capacity;
    }

    return ret;
}

int StaticList_Insert(StaticList* list, StaticListNode* node, int pos)  // O(n)
{
    TStaticList* sList = (TStaticList*)list;
    int ret = (sList != NULL);
    int current = ;
    int index = ;
    int i = ;

    ret = ret && (sList->header.data +  <= sList->capacity);
    ret = ret && (pos >=) && (node != NULL);

    if( ret ) //插入结点不能为空
    {
        for(i=; i<=sList->capacity; i++)
        {
            if( sList->node[i].next == AVAILABLE )
            {
                index = i; //未被使用节点的下标
                break;
            }
        }

        sList->node[index].data = *((unsigned int*)node); //保存数据 

        sList->node[] = sList->header; 

        for(i=; (i<pos) && (sList->node[current].next != ); i++)
        {
            current = sList->node[current].next; //若插入位置超过已存数据量，则放在后一位
        }

        sList->node[index].next = sList->node[current].next;
        sList->node[current].next = index;

        sList->node[].data++;  //队列头的data表示链表长度，后面则存储节点的数据 

        sList->header = sList->node[];
    }

    return ret;
}

StaticListNode* StaticList_Get(StaticList* list, int pos)  // O(n)
{
    TStaticList* sList = (TStaticList*)list;
    StaticListNode* ret = NULL; //判断是否插入成功
    int current = ;
    int object = ;
    int i = ;

    if( (sList != NULL) && ( <= pos) && (pos < sList->header.data) )
    {
       sList->node[] = sList->header;

        for(i=; i<pos; i++)
        {
            current = sList->node[current].next;
        }

        object = sList->node[current].next;

        ret = (StaticListNode*)(&sList->node[object].data);
    }

    return ret;
}

StaticListNode* StaticList_Delete(StaticList* list, int pos) // O(n)
{
    TStaticList* sList = (TStaticList*)list;
    StaticListNode* ret = NULL;
    int current = ;
    int object = ;
    int i = ;

    if( (sList != NULL) && ( <= pos) && (pos < sList->header.data) )
    {
        sList->node[] = sList->header;

        for(i=; i<pos; i++)
        {
            current = sList->node[current].next;
        }

        object = sList->node[current].next; //找到要删除元素的下标 :object 

        sList->node[current].next = sList->node[object].next;

        sList->node[].data--;

        sList->header = sList->node[];

        sList->node[object].next = AVAILABLE;

        ret = (StaticListNode*)(&sList->node[object].data);
    }

    return ret;
}

StaticList.h

#ifndef _STATICLIST_H_
#define _STATICLIST_H_

typedef void StaticList;
typedef void StaticListNode;

StaticList* StaticList_Create(int capacity);

void StaticList_Destroy(StaticList* list);

void StaticList_Clear(StaticList* list);

int StaticList_Length(StaticList* list);

int StaticList_Capacity(StaticList* list);

int StaticList_Insert(StaticList* list, StaticListNode* node, int pos);

StaticListNode* StaticList_Get(StaticList* list, int pos);

StaticListNode* StaticList_Delete(StaticList* list, int pos);

#endif

main

#include <stdio.h>
#include <stdlib.h>
#include "StaticList.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[])
{
    StaticList* list = StaticList_Create();

    int index = ;

    int i = ;
    int j = ;
    int k = ;
    int x = ;
    int y = ;
    int z = ;

    StaticList_Insert(list, &i, );
    StaticList_Insert(list, &j, );
    StaticList_Insert(list, &k, );

    for(index = ; index<StaticList_Length(list); index++)
    {
        int* p = (int*)StaticList_Get(list, index);
　　　　 printf("Get:%d\n", *p);
    }
    getchar();
    return ;
}

三、动态链表

　　 如果程序支持指针,则可按照我们的一般形式实现链表, 需要时分配,不需要时回收即可.

代码示例：

LinkList.c

#include <stdio.h>
#include <malloc.h>
#include "LinkList.h"

typedef struct _tag_LinkList
{
    LinkListNode header;
    int length;
} TLinkList;

LinkList* LinkList_Create() // O(1)
{
    TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));

    if( ret != NULL )
    {
        ret->length = ;
        ret->header.next = NULL;
    }

    return ret;
}

void LinkList_Destroy(LinkList* list) // O(1)
{
    free(list);
}

void LinkList_Clear(LinkList* list) // O(1)
{
    TLinkList* sList = (TLinkList*)list;

    if( sList != NULL )
    {
        sList->length = ;
        sList->header.next = NULL;
    }
}

int LinkList_Length(LinkList* list) // O(1)
{
    TLinkList* sList = (TLinkList*)list;
    int ret = -;

    if( sList != NULL )
    {
        ret = sList->length;
    }

    return ret;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) // O(n)
{
    TLinkList* sList = (TLinkList*)list;
    int ret = (sList != NULL) && (pos >= ) && (node != NULL);
    //int i = 0;

    if( ret )
    {
        LinkListNode* current = (LinkListNode*)sList;

        for(int i=; (i<pos) && (current->next != NULL); i++)
        {
            current = current->next;
        }

        node->next = current->next;
        current->next = node;

        sList->length++;
    }

    return ret;
}

LinkListNode* LinkList_Get(LinkList* list, int pos) // O(n)
{
    TLinkList* sList = (TLinkList*)list;
    LinkListNode* ret = NULL;  //
    int i = ;

    if( (sList != NULL) && ( <= pos) && (pos < sList->length) )
    {
        LinkListNode* current = (LinkListNode*)sList;

        for(i=; i<pos; i++)
        {
           current = current->next;
        }

        ret = current->next;
    }

    return ret;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos) // O(n)
{
    TLinkList* sList = (TLinkList*)list;
    LinkListNode* ret = NULL;
    int i = ;

    if( (sList != NULL) && ( <= pos) && (pos < sList->length) )
    {
        LinkListNode* current = (LinkListNode*)sList;

        for(i=; i<pos; i++)
        {
            current = current->next;
        }

        ret = current->next;
        current->next = ret->next;

        sList->length--;
    }

    return ret;
}

LinkList.h

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
    LinkListNode* next;
};

LinkList* LinkList_Create();

void LinkList_Destroy(LinkList* list);

void LinkList_Clear(LinkList* list);

int LinkList_Length(LinkList* list);

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

LinkListNode* LinkList_Get(LinkList* list, int pos);

LinkListNode* LinkList_Delete(LinkList* list, int pos);

#endif

lmain.c

#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

struct Value
{
    LinkListNode header;
    int v;
};

int main(int argc, char *argv[])
{
    LinkList* list = LinkList_Create();

    struct Value v1;
    struct Value v2;
    struct Value v3;
    struct Value v4;
    struct Value v5;

    v1.v = ;
    v2.v = ;
    v3.v = ;
    v4.v = ;
    v5.v = ;

    LinkList_Insert(list, (LinkListNode*)&v1, ); //头插法
    LinkList_Insert(list, (LinkListNode*)&v2, );
    LinkList_Insert(list, (LinkListNode*)&v3, LinkList_Length(list));//尾插法
    LinkList_Insert(list, (LinkListNode*)&v4, LinkList_Length(list));
    LinkList_Insert(list, (LinkListNode*)&v5, LinkList_Length(list));

    for(int i=; i<LinkList_Length(list); i++)
    {
        struct Value* pv = (struct Value*)LinkList_Get(list, i);

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

    while( LinkList_Length(list) >  )
    {
        struct Value* pv = (struct Value*)LinkList_Delete(list, );

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

    /*for(int i=0; i<LinkList_Length(list); i++)
    {
        struct Value* pv = (struct Value*)LinkList_Get(list, i);

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

    LinkList_Destroy(list);

    getchar();
    return ;
}

四、双向链表

　　相比单向链表有以下优势：

　　　　插入删除不需要移动元素外，可以原地插入删除。

　　　　可以双向遍历。

删除单个图示：

代码示例：

 DLinkList.c

#include <stdio.h>
#include <malloc.h>
#include "DLinkList.h"

typedef struct _tag_DLinkList
{
    DLinkListNode header;  //链表头
    DLinkListNode* slider; //游标记录当前节点位置
    int length;
} TDLinkList;

DLinkList* DLinkList_Create() // O(1)
{
    TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));

    if( ret != NULL )
    {
        ret->length = ;
        ret->header.next = NULL;
        ret->header.pre = NULL;
        ret->slider = NULL;
    }

    return ret;
}

void DLinkList_Destroy(DLinkList* list) // O(1)
{
    free(list);
}

void DLinkList_Clear(DLinkList* list) // O(1)
{
    TDLinkList* sList = (TDLinkList*)list;

    if( sList != NULL )
    {
        sList->length = ;
        sList->header.next = NULL;
        sList->header.pre = NULL;
        sList->slider = NULL;
    }
}

int DLinkList_Length(DLinkList* list) // O(1)
{
    TDLinkList* sList = (TDLinkList*)list;
    int ret = -;

    if( sList != NULL )
    {
        ret = sList->length;
    }

    return ret;
}

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) // O(n)
{
    TDLinkList* sList = (TDLinkList*)list;
    int ret = (sList != NULL) && (pos >= ) && (node != NULL);
    int i = ;

    if( ret )
    {
        DLinkListNode* current = (DLinkListNode*)sList;
        DLinkListNode* next = NULL;

        for(i=; (i<pos) && (current->next != NULL); i++) //指针移到要插入位置
        {
            current = current->next;
        }

        next = current->next; //保存原节点 

        current->next = node; //插入节点
        node->next = next;      //插入节点指向原节点
       if( next != NULL)
       {
         next->pre = node;   //如果原节点不为空，则原节点的pre指向刚插入节点
       }
        node->pre = current; //插入节点的pre指向原节点的pre 

       if( sList->length == )
       {
         sList->slider = node;  //node为第一个元素
       }

       if( current == (DLinkListNode*)sList)  //current指向表头
       {
              node->pre = NULL;
       }
      sList->length++;   //节点数加一
    }
    return ret;
}

DLinkListNode* DLinkList_Get(DLinkList* list, int pos) // O(n)
{
    TDLinkList* sList = (TDLinkList*)list;
    DLinkListNode* ret = NULL;
    int i = ;

    if( (sList != NULL) && ( <= pos) && (pos < sList->length) )
    {
        DLinkListNode* current = (DLinkListNode*)sList;

        for(i=; i<pos; i++)
        {
            current = current->next;
        }

        ret = current->next;
    }

    return ret;
}

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) // O(n)  根据位置删除节点
{
    TDLinkList* sList = (TDLinkList*)list;
    DLinkListNode* ret = NULL;
    int i = ;

    if( (sList != NULL) && ( <= pos) && (pos < sList->length) )
    {
        DLinkListNode* current = (DLinkListNode*)sList;
        DLinkListNode* next = NULL;

        for(i=; i<pos; i++)
        {
           current = current->next;
        }

        ret = current->next; //移到要删除节点
        next = ret->next;     //保存删除节点的下一个节点地址 

        current->next = next; //被删除节点的上一个节点的next,指向被删除节点的下一个节点地址 

        if( next != NULL)
        {
            next->pre = current;  //如果删除节点的下一个节点地址不为空，则pre指向被删除节点的上一个节点地址

            if( current == (DLinkListNode*)sList)
            {
                next->pre = NULL; //如被删除节点是第一个节点，则pre=NULL,即current指向表头
            }
        }

        if( sList->slider = ret)
        {
            sList->slider = next; //如当前游标指向要被删除的节点，则游标前移一位
        }

        sList->length--;  //节点数减一
    }

    return ret;
}

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node) //根据指定节点找到位置
{
    TDLinkList* sList = (TDLinkList*)list;
    DLinkListNode* ret = NULL;
    int i = ;

    if(sList != NULL)
    {
        DLinkListNode* current = (DLinkListNode*)sList;

        for(i=; i<sList->length; i++)
        {
            if(current->next == node)
            {
                ret = current->next;
                break;
            }

            current = current->next;
        }

        if( ret != NULL)
        {
            DLinkList_Delete(sList, i); //删除节点
        }
    }

}

DLinkListNode* DLinkList_Reset(DLinkList* list) //游标复位指向第一个节点
{
    TDLinkList* sList = (TDLinkList*)list;
    DLinkListNode* ret = NULL;

    if( sList != NULL)
    {
        sList->slider = sList->header.next;
        ret = sList->slider;
    }

    return ret;
} 

DLinkListNode* DLinkList_Current(DLinkList* list) //获取当前链表游标指向的位置
{
    TDLinkList* sList = (TDLinkList*)list;
    DLinkListNode* ret = NULL;

    if( sList != NULL)
    {
        ret = sList->slider;
    }

    return ret;
}

DLinkListNode* DLinkList_Next(DLinkList* list) //游标后移一位
{
   TDLinkList* sList = (TDLinkList*)list;
   DLinkListNode* ret = NULL;

  if((sList != NULL) && (sList->slider != NULL))
  {
        ret = sList->slider;
        sList->slider = ret->next;
  }

  return ret;
}

DLinkListNode* DLinkList_Pre(DLinkList* list) //游标前移一位
{
    TDLinkList* sList = (TDLinkList*)list;
   DLinkListNode* ret = NULL;

  if((sList != NULL) && (sList->slider != NULL))
  {
        ret = sList->slider;
        sList->slider = ret->pre;
  }

  return ret;

}

 DLinkList.h

#ifndef _DDLinkList_H_
#define _DDLinkList_H_

typedef void DLinkList;
typedef struct _tag_DLinkListNode DLinkListNode;
struct _tag_DLinkListNode
{
    DLinkListNode* next;
    DLinkListNode* pre;
};

DLinkList* DLinkList_Create();

void DLinkList_Destroy(DLinkList* list);

void DLinkList_Clear(DLinkList* list);

int DLinkList_Length(DLinkList* list);

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode* DLinkList_Reset(DLinkList* list);  //以下为游标设置 

DLinkListNode* DLinkList_Current(DLinkList* list);

DLinkListNode* DLinkList_Next(DLinkList* list);

DLinkListNode* DLinkList_Pre(DLinkList* list);

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include "DLinkList.h"

struct value
{
  DLinkListNode header;
  int v;
};

int main(int argc, char *argv[])
{
  int i = ;
  DLinkList* list = DLinkList_Create();
   struct value* pv = NULL;
  struct value v1;
  struct value v2;
  struct value v3;
  struct value v4;
  struct value v5;

  v1.v = ;
  v2.v = ;
  v3.v = ;
  v4.v = ;
  v5.v = ;

  DLinkList_Insert(list, (DLinkListNode*)&v1, DLinkList_Length(list));
  DLinkList_Insert(list, (DLinkListNode*)&v2, DLinkList_Length(list));
  DLinkList_Insert(list, (DLinkListNode*)&v3, DLinkList_Length(list));
  DLinkList_Insert(list, (DLinkListNode*)&v4, DLinkList_Length(list));
  DLinkList_Insert(list, (DLinkListNode*)&v5, DLinkList_Length(list));

  for(i=; i<DLinkList_Length(list); i++)
  {
      pv = (struct value*)DLinkList_Get(list,i);
        printf("%d\n", pv->v);
  }

  printf("\n");

  DLinkList_Delete(list, DLinkList_Length(list)-);
  DLinkList_Delete(list, );

  for(i=; i<DLinkList_Length(list); i++)
  {
      pv = (struct value*)DLinkList_Next(list);
      printf("%d\n", pv->v);
  }

  printf("\n");

  DLinkList_Reset(list);
  DLinkList_Next(list);

  pv = (struct value*)DLinkList_Current(list);
  printf("%d\n", pv->v);

  DLinkList_DeleteNode(list, (DLinkListNode*)pv);
  pv = (struct value*)DLinkList_Current(list); //获取游标指示的数据
  printf("%d\n", pv->v);

  DLinkList_Pre(list); //游标前移
  pv = (struct value*)DLinkList_Current(list); //获取游标指示的数据
  printf("%d\n", pv->v);

  DLinkList_Destroy(list);

  printf("Press enter to continue ...");
  getchar();
  return ;

}

五、循环单链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

代码示例：

DLinkList.c

#include <stdio.h>
#include <malloc.h>
#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 )
    {
        ret->length = ;
        ret->header.next = NULL;
        ret->slider = NULL;
    }

    return ret;
}

void CircleList_Destroy(CircleList* list) // O(1)
{
    free(list);
}

void CircleList_Clear(CircleList* list) // O(1)
{
    TCircleList* sList = (TCircleList*)list;

    if( sList != NULL )
    {
        sList->length = ;
        sList->header.next = NULL;
        sList->slider = NULL;
    }
}

int CircleList_Length(CircleList* list) // O(1)
{
    TCircleList* sList = (TCircleList*)list;
    int ret = -;

    if( sList != NULL )
    {
        ret = sList->length;
    }

    return ret;
}

int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) // O(n)
{
    TCircleList* sList = (TCircleList*)list;
    int ret = (sList != NULL) && (pos >= ) && (node != NULL);
    int i = ;

    if( ret )
    {
       CircleListNode* current = (CircleListNode*)sList;

        for(i=; (i<pos) && (current->next != NULL); i++)
        {
            current = current->next;
        }

        node->next = current->next; //插入节点next指向插入位置的next
        current->next = node;        //插入位置的next指向插入节点 

        if(sList->length == )  //如果是第一个插入节点
        {
           sList->slider = node; //光标指向插入的第一个节点
           node->next = node;    //插入节点next即指向自己
        }

        sList->length++; //链表长度加一
    }

    return ret;
}

CircleListNode* CircleList_Get(CircleList* list, int pos) // O(n)
{
    TCircleList* sList = (TCircleList*)list;
    CircleListNode* ret = NULL;
    int i = ;

    if((sList != NULL) && ( <= pos))
    {
        CircleListNode* current = (CircleListNode*)sList;

        for(i=; i<pos; i++)
        {
           current = current->next;
        }

        ret = current->next;
    }

    return ret;
}

CircleListNode* CircleList_Delete(CircleList* list, int pos) // O(n)
{
    TCircleList* sList = (TCircleList*)list;
    CircleListNode* ret = NULL;
    int i = ;

    if( (sList != NULL) && ( <= pos) )
    {
        CircleListNode* current = (CircleListNode*)sList;

        CircleListNode* first = sList->header.next;
        CircleListNode* last = (CircleListNode*)CircleList_Get(sList,sList->length-); 

        for(i=; i<pos; i++)
        {
            current = current->next;
        }

        ret = current->next;
        current->next = ret->next;

        sList->length--;

        if( first == ret )  //还剩头结点和一个数据结点
        {
           sList->header.next = ret->next;
           last->next = ret->next;
        }

        if( sList->slider == ret )
        {
           sList->slider = ret->next;
        }

        if( sList->length ==  )
        {
           sList->header.next = NULL;
        }
    }

    return ret;
}

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
{
    TCircleList* sList = (TCircleList*)list;
    CircleListNode* ret = NULL;
    int i = ;

    if( sList != NULL)
    {
       CircleListNode* current = (CircleListNode*)sList;

       for(i=; i<sList->length; i++)
       {
            if( current->next == node)
            {
                ret = current->next;
                break;
            }
            current = current->next;
       }
       if( ret != NULL)
       {
            CircleList_Delete(sList,i);
       }
    }

    return ret;
}

CircleListNode* CircleList_Reset(CircleList* list)
{
    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)
{
    TCircleList* sList = (TCircleList*)list;
    CircleListNode* ret = NULL;
    int i = ;

    if( sList != NULL)
    {
        ret = sList->slider;
    }

    return ret;
}

CircleListNode* CircleList_Next(CircleList* list)
{
    TCircleList* sList = (TCircleList*)list;
    CircleListNode* ret = NULL;

    if( (sList != NULL) && (sList->slider != NULL))
    {
        ret = sList->slider;
        sList->slider = ret->next;
    }

    return ret;
}

DLinkList.h

#ifndef _CIRCLELIST_H_
#define _CIRCLELIST_H_

typedef void CircleList;
typedef struct _tag_CircleListNode CircleListNode;

struct _tag_CircleListNode
{
    CircleListNode* next;
};

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

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

CircleListNode* CircleList_Reset(CircleList* list);

CircleListNode* CircleList_Current(CircleList* list);

CircleListNode* CircleList_Next(CircleList* list);

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include "CircleList.h"

struct Value
{
    CircleListNode header; //定义新变量时会被初始化
    int v;
};

int main(int argc, char *argv[])
{
    int i = ;
    CircleList* list = CircleList_Create(); 

    struct Value v1;
    struct Value v2;
    struct Value v3;
    struct Value v4;
    struct Value v5;
    struct Value v6;

    v1.v = ;
    v2.v = ;
    v3.v = ;
    v4.v = ;
    v5.v = ;
    v6.v = ;

    CircleList_Insert(list, (CircleListNode*)&v1, );//CircleList_Length(list)); //pos == 0
    //printf("Length is :%d\n",CircleList_Length(list));
    CircleList_Insert(list, (CircleListNode*)&v2, );//CircleList_Length(list));
    //CircleList_DeleteNode(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, );

      for(i = ; i<CircleList_Length(list); i++)
      {
          struct Value* pv = (struct Value*)CircleList_Get(list, i);
          printf("%d\n", pv->v);
      }

       printf("\n");

       while( CircleList_Length(list) > )
       {
            struct Value* pv = (struct Value*)CircleList_Delete(list,);

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

  printf("Press enter to continue ...");
  getchar();
  return ;

}

-end-