跳转至

线性表

结点

小结点和业务结点的首地址重合

链表的算法和链表具体业务结点分离：业务结点的第一个域（第一个元素） 放上链表node结点即可。结点重合，省去求偏移。

  • 传统链表 next指针指向下一个数据域的地址。 业务结点不同，链表next也要变，不好。

  • linux内核链表 大千世界包含结点

  • 表头节点：

链表都有一个表头，不是第一个结点 而是链表的头部。根据表头得到开始的位置，然后插入删除节点的时候，需要从表头指针跳位置。 2. 数据结点： 链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息 3. 尾结点： 链表中的最后一个数据结点，其下一元素指针为空，表示无后继

循环链表

在普通链表的基础上增加下面新操作：

  1. 将游标重置指向链表中的第一个数据元素
  2. 获取当前游标指向的数据元素
  3. 将游标移动指向到链表中的下一个数据元素
  4. 直接指定删除链表中的某个数据元素
#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 List_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_Reset(CircleList* list);

//获取当前游标指向的数据元素
CircleListNode* CircleList_Current(CircleList* list);

//将游标移动指向到链表中的下一个数据元素
CircleListNode* CircleList_Next(CircleList* list);

//直接指定删除链表中的某个数据元素
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);

#endif

插入元素的分析：

  1. 普通插入元素（中间位置）

和单向链表是一样

  1. 尾插法

和单链表是一样的，单链表的写法支持尾插法；

因：辅助指针向后跳length次，指向最后面那个元素

  1. 头插法 要连成一个环（添加处理）

要进行头插法，需要求出尾节点，和单链表不一样的地方，保证是循环链表

  1. 第一次插入元素时，让游标指向0号结点

尾插法和普通链表一样。

插入第一个元素 相当于头插法和尾插法重叠。

#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)
    {
        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; (i<pos) && (current->next != 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++;

        //若头插法 current仍然指向头部
        //（原因是：跳0步，没有跳走）
        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; 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 = 0;

    if( (sList != NULL) && (pos >= 0) && (sList->length > 0) )
    {
        CircleListNode* current = (CircleListNode*)sList;
        CircleListNode* last = NULL;

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

        //若删除第一个元素（头结点）
        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; i<sList->length; 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;
}