静态链表详解

 
            《 静态链表的创建、插入、删除、销毁代码实现》
 
序言：表的学习也没学习多久，对于我而言大部分都是研究别人的代码，取其精华取其糟粕。链表在学习计算机课程的时候，数据结构是一门基础课程，基础不代表不重要，相反是特别重要，就好比你想学习骑自行车，但是你连走路都不会，怎么会骑自行车呢？哈哈，学习数据结构的基本思路是:
顺序表，链表，静态链表、双链表，循环量表等 .
要求：c语言要懂一点。
接下来我们就一起分析下面一段代码吧！
#include
#include   //头函数就好比一个仓库,存储我们需要的基础函数,如printf 等
#include
#define AVAILABLE -1

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);                                //删除元素
 
//对于这个结构体的定义相信大家都应该很熟悉了吧，关键在这里typedef的应用

typedef struct _tag_StaticListNode
{
    unsigned int data;                    //存放和数据的地方
    int 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 = 0;
    
    if( capacity >= 0 )
   {                                                                /*申请内存大小capacity加一是因为头数据要算一个*/     
   ret = (TStaticList*)malloc(sizeof(TStaticList) + sizeof(TStaticListNode) * (capacity + 1));
    }
    
    if( ret != NULL )
    {
        ret->capacity = capacity;
        ret->header.data = 0;
        ret->header.next = 0;
        
        for(i=1; i<=capacity; i++)                    /*用来找出数组空闲的数据位置*/
        {
            ret->node[i].next = AVAILABLE;
        }
    }
    
    return ret;
}
 
 
/*销毁链表内存申请相当于调用了一个free函数*/
void StaticList_Destroy(StaticList* list) // O(1)
{
    free(list);
}
 
/*清除链表元素*/
void StaticList_Clear(StaticList* list) // O(n)
{
    TStaticList* sList = (TStaticList*)list;//ba void turn point 
    int i = 0;
    
    if( sList != NULL )
    {
        sList->header.data = 0;
        sList->header.next = 0;
        
        for(i=1; i<=slist->capacity; i++)/*清除后要定义为可用*/
        {
            sList->node[i].next = AVAILABLE;
        }
    }
}
 
/*获取数组元素个数*/
int StaticList_Length(StaticList* list) // O(1)
{
    TStaticList* sList = (TStaticList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->header.data;
    }
    
    return ret;
}
 /****获取内存容量***/
int StaticList_Capacity(StaticList* list) // O(1)
{
    TStaticList* sList = (TStaticList*)list;
    int ret = -1;
    
    if( sList != NULL )
    {
        ret = sList->capacity;
    }
    
    return ret;
}
 /****插入数据元素***/
int StaticList_Insert(StaticList* list, StaticListNode* node, int pos)  // O(n)
{                                                     /***参数1 链表头指针 参数2 具体数据地址 参数3 位置****/
    TStaticList* sList = (TStaticList*)list;
    int ret = (sList != NULL);
    int current = 0;
    int index = 0;
    int i = 0;
     /****判断位置是否有效***/
    ret = ret && (sList->header.data + 1 <= slist-="">capacity);
    ret = ret && (pos >=0) && (node != NULL);
    
    if( ret )
    {
        for(i=1; i<=slist->capacity; i++)
        {
            if( sList->node[i].next == AVAILABLE )
            {
                index = i;
                break; /****判断是否为可用位置***/
            }
        }
        
        sList->node[index].data = (unsigned int)node;
        
        sList->node[0] = sList->header;
        
        for(i=0; (inode[current].next != 0); i++)
        {
            current = sList->node[current].next;
        }
         /****下面两行代码是说明具体插入位置的算法实现***/
        sList->node[index].next = sList->node[current].next;
        sList->node[current].next = index;
        
        sList->node[0].data++;                     /****之后要data加以***/        
        sList->header = sList->node[0];      /***节点游标要回到初始位置****/
    }
    
    return ret;
}
 /****获取元素值***/
 
StaticListNode* StaticList_Get(StaticList* list, int pos)  // O(n)
{
    TStaticList* sList = (TStaticList*)list;
    StaticListNode* ret = NULL;
    int current = 0;
    int object = 0;
    int i = 0;
    
    if( (sList != NULL) && (0 <= pos) && (pos < sList->header.data) )
    {
        sList->node[0] = sList->header;
        
        for(i=0; inode[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 = 0;
    int object = 0;
    int i = 0;
    
    if( (sList != NULL) && (0 <= pos) && (pos < sList->header.data) )
    {
        sList->node[0] = sList->header;
        
        for(i=0; inode[current].next;
        }
        
        object = sList->node[current].next;
        
        sList->node[current].next = sList->node[object].next;
         /****主要区别还是上面两行代码进行插入实现***/
 
        sList->node[0].data--;
        
        sList->header = sList->node[0];
        
        sList->node[object].next = AVAILABLE;
        
        ret = (StaticListNode*)(sList->node[object].data);
    }
    
    return ret;
}
 
 
 /***主函数具体实现创建链表，插入、删除、销毁、获取元素、等操作****/
 
 
int main(int argc, char *argv[])
{
    StaticList* list = StaticList_Create(10);
    
    int index = 0;
    
    int i = 0;
    int j = 1;
    int k = 2;
    int x = 3;
    int y = 4;
    int z = 5;
    
    StaticList_Insert(list, &i, 1);
    StaticList_Insert(list, &j, 3);
    StaticList_Insert(list, &k, 2);
    StaticList_Insert(list, &x, 5);
    StaticList_Insert(list, &y, 4);    /****刚开始对于这个赋值没有理解后来明白了***/
    StaticList_Insert(list, &z, 6);   /****&i 也就是插入的元素的地址，这个地址是指向下一个元素的地址***/      
    for(index=0; index 0 )
    {
        int* p = (int*)StaticList_Delete(list, 0); /**删除数据
     **/        
        printf("%d\\n", *p);
    }
    
    printf("\\n");
    
   
StaticList_Insert(list, &x, 0);
    StaticList_Insert(list, &y, 0); /***插入元素****/
 
    StaticList_Insert(list, &z, 0);
    
    printf("Capacity: %d Length: %d\\n", StaticList_Capacity(list),  

  StaticList_Length(list));
    
    for(index=0; index
 
成都创新互联主要从事网站设计制作、网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务云县,10年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792
            
            
                        

            新闻标题：静态链表详解            

            标题路径：http://6mz.cn/article/jchgep.html