静态链表实现（国嵌学习笔记）

静态链表的定义

    顺序表数组中的元素由两个数据域组成：data和next；data域用于存储数据；next域用于存储下一个元素在数组中的下标。静态链表是在顺序表的基础上利用数组实现单链表。

静态链表的相关定义

结点结构体定义：

typedef struct _tag_StaticListNode

{

    unsigned int data;

    int next;

}TStaticListNode;

静态链表结构体定义：

typedef struct _tag_StaticList

{

    int capacity;

    TStaticListNode header;

    TStaticListNode node[];

}TstaticList;

静态链表操作

获取第pos个元素操作：

    判断线性表是否合法；

    判断位置是否合法；

    由表头开始通过next域移动pos次后，当前元素的next域即要获取元素在数组中的下标

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

for( i=0; i

{

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

}

object = sList->node[current].next

插入元素到位置pos的算法：

    判断线性表是否合法；

    判断插入位置是否合法；

    在数组中查找空闲位置index；

    由表头开始通过next域移动pos次后，当前元素的next域为要插入的位置；

    将新元素插入；

    线性表长度加1；

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;

删除第pos个元素的算法：

    判断线性表是否合法；

    判断删除位置是否合法；

    获取第pos个元素；

    将第pos个元素删除；

    线性表长度减1；

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

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

/*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_Capacity(StaticList* list);

int StaticList_Length(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

/*StaticList.c*/

************************************************************************************************

#include

#include

#include "StaticList.h"

#define AVAILABLE -1

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 )

    {

        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;

}

void StaticList_Destroy(StaticList* list)

{

free(list);

}

void StaticList_Clear(StaticList* list)

{

TStaticList* sList = (TStaticList*)list;

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)

{

TStaticList* sList = (TStaticList*)list;

int ret = -1;

if( sList != NULL)

{

ret = sList->capacity;

}

return ret;

}

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

{

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; icapacity;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++;

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

}

return ret;

}

StaticListNode* StaticList_Get(StaticList* list, int pos)

{

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; 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 = 0;

    int object = 0;

    int i = 0;

    

    if( (sList != NULL) && (0 <= pos) && (pos < sList->header.data) )

    {

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

        

        for(i=0; i

        {

            current = sList->node[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;

}

/*main.c*/

***********************************************************************

#include

#include

#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(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, 0);

    StaticList_Insert(list, &j, 0);

    StaticList_Insert(list, &k, 0);

    

    for(index=0; index

    {

        int* p = (int*)StaticList_Get(list, index);

        

        printf("%d\n", *p);

    }

    

    printf("\n");

    

   while( StaticList_Length(list) > 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

    {

        int* p = (int*)StaticList_Get(list, index);

        

        printf("%d\n", *p);

    }

    

    StaticList_Destroy(list);

    

return 0;

}

阅读(3438) | 评论(0) | 转发(1) |

0

上一篇：线性表的实现(国嵌学习笔记)

下一篇：内核开发基础（国嵌学习笔记）