静态链表

/*线性表的静态单链表存储结构*/
typedef struct _STATICLIST_
{
    ElemType data;//数据
    int cursor;//游标
}Component,StaticList[MAX_SIZE];

void InitSpace_SL(StaticList &space)
{
    for(int i = 0; i < MAX_SIZE - 1; i++)
    {
        space[i].cursor = i+1;
    }
    space[MAX_SIZE - 1].cursor = 0;
}

int Malloc_SL(StaticList &space)
{
    int i = space[0].cursor;
    if(i)//备用链表非空
    {
        space[0].cursor = space[i].cursor;
    }
    return i;
}

void Free_SL(StaticList &space,int i)
{
    //将下标为i的节点回收,放回备用链表
    space[i].cursor = space[0].cursor;
    space[0].cursor = i;
}

/***********************************************
    静态链表的实现
    by Rowandjj
    date 2014/3/28
***********************************************/
#include<iostream>
using namespace std;

#define MAX_SIZE 1000//静态链表最大长度

typedef int ElemType;
#define OK 1;
#define ERROR 0;
/*线性表的静态单链表存储结构*/
typedef struct _STATICLIST_
{
    ElemType data;//数据
    int cursor;//游标
}Component,StaticList[MAX_SIZE];

/*操作声明*/
void InitSpace_SL(StaticList&);//初始化备用链表
int Malloc_SL(StaticList&);//从备用链表上申请一个节点，成功则返会节点位置，否则返回0
void Free_SL(StaticList&,int);//释放指定位置的节点,并放回备用链表中
/////////////////////////////////
int InitList_SL(StaticList&);//初始化静态链表，
int ListLength_SL(StaticList&,int);//获取链表长度
int ListInsert_SL(StaticList&,int,int,ElemType);//插入节点
int ListDelete_SL(StaticList&,int,int,ElemType&);//删除节点
int ClearList_SL(StaticList&,int);//将静态链表重置，全部放回到备用链表上
int ListEmpty_SL(StaticList&,int);// 判断L中表头位序为n的链表是否空,若是空则是空表返回1;否则返回0  
int GetElem_SL(StaticList&,int,int,ElemType&);//获取特定位置上的节点的值
int LocateElem_SL(StaticList&,int,ElemType);//在静态链表中查找给定元素位置

int ListTraverse_SL(StaticList &L,int n,void(*vi)(ElemType));//遍历静态链表
void visit(ElemType);

/*具体实现*/
void InitSpace_SL(StaticList &space)
{
    for(int i = 0; i < MAX_SIZE - 1; i++)
    {
        space[i].cursor = i+1;
    }
    space[MAX_SIZE - 1].cursor = 0;
}
int Malloc_SL(StaticList &space)
{
    int i = space[0].cursor;
    if(i)//备用链表非空
    {
        space[0].cursor = space[i].cursor;
    }
    return i;
}
void Free_SL(StaticList &space,int i)
{
    //将下标为i的节点回收,放回备用链表
    space[i].cursor = space[0].cursor;
    space[0].cursor = i;
}

int InitList_SL(StaticList &L)
{
    // 构造一个空链表，返回值为空表在数组中的位序   
    int i = Malloc_SL(L);//从备用链表中获取一个节点
    L[i].cursor = 0;//指针域为0
    return OK;
}
int ListLength_SL(StaticList &L,int i)
{
    int j = L[i].cursor;
    int num = 0;
    while(j)
    {
        j = L[j].cursor;
        num++;
    }
    return num;
}
int ListInsert_SL(StaticList &L,int n,int i,ElemType e)
{
    // 在L中表头位序为n的链表的第i个元素之前插入新的数据元素e 
    //L代表备用链表，n代表当前链表的表头下标,i代表待插入的位置,e代表插入元素值
    int j,p = n;
    if(i<1 || i>ListLength_SL(L,n)+1)
    {
        return ERROR;
    }
    j = Malloc_SL(L);
    if(j)//节点申请成功
    {
        L[j].data = e;
        for(int m = 1; m < i;m++)//移到待插入位置的前一个位置
        {
            p = L[p].cursor;
        }
        //插入节点
        L[j].cursor = L[p].cursor;
        L[p].cursor = j;
        return OK;
    }
    return ERROR;
}
int ListDelete_SL(StaticList &L,int n,int i,ElemType &e)
{
    // 删除在L中表头位序为n的链表的第i个数据元素e，并返回其值
    if(i < 1 || i > ListLength_SL(L,n))
    {
        return ERROR;
    }
    int p = n;
    for(int m = 1; m < i;m++)//移到待删节点的前一个节点
    {
        p = L[p].cursor;
    }
    int q = L[p].cursor;
    e = L[q].data;
    L[p].cursor = L[q].cursor;
    Free_SL(L,q);
    
    return OK;
}
int ClearList_SL(StaticList &L,int n)//重置链表
{
    // 将此表重置为空表，即将这个链表转化为备用表的一部分  
    int p = L[n].cursor;//p指向当前链表的首节点
    L[n].cursor = 0;//将链表置空
    int k = L[0].cursor;//k指向备用链表首节点
    L[0].cursor = p;//将当前链表首节点备用链表头节点后
    while(L[p].cursor)
    {
        p = L[p].cursor;
    }
    L[p].cursor = k;//将备用链表首节点接到当前链表尾巴上
    return OK;
}
int ListEmpty_SL(StaticList &L,int n)// 判断L中表头位序为n的链表是否空,若是空则是空表返回1;否则返回0 
{
    return !L[n].cursor;//==0,true
}
int GetElem_SL(StaticList &L,int n,int i,ElemType &e)//用e返回L中表头位序为n的链表的第i个元素的值  
{
    int j,p = n;
    if(i < 1 || i > ListLength_SL(L,n))
    {
        return ERROR;
    }
    for(j = 1; j <= i;j++)
    {
        p = L[p].cursor;
    }
    e = L[p].data;
    return OK;
}
int LocateElem_SL(StaticList &L,int n,ElemType e)
{
    // 在L中表头位序为n的静态单链表中查找第1个值为e的元素。   
    // 若找到，则返回它在静态链表中的位序（而不是L的位序） 
    int p = L[n].cursor;
    int i = 1;
    while(p && L[p].data!=e)
    {
        p = L[p].cursor;
        i++;
    }
    return i;
}
int ListTraverse_SL(StaticList &L,int n,void(*vi)(ElemType))//遍历
{
    int p = L[n].cursor;
    while(p)
    {
        vi(L[p].data);
        p = L[p].cursor;
    }
    cout<<endl;
    return OK;
}
void visit(ElemType e)
{
    cout<<e<<" ";
}

int main(void)
{
    StaticList L;
    InitSpace_SL(L);//初始化备用链表
    int la = InitList_SL(L);//初始化静态链表，返回头节点位序
    int i,m = 0;
    int index;
    ElemType e;
    cin>>i;
    for(int j = 0; j < i;j++)
    {
        cin>>e;
        cin>>index;
        ListInsert_SL(L,la,index,e);
    }
    cout<<"traverse:";
    ListTraverse_SL(L,la,visit);
    cout<<"len:"<<ListLength_SL(L,la)<<endl;
    cout<<ListEmpty_SL(L,la)<<endl;
    while(m != -1)
    {    
        cin>>m;
        ListDelete_SL(L,la,m,e);
        cout<<"*****************"<<endl;
        cout<<"del :"<<e<<endl;
        ListTraverse_SL(L,la,visit);
        cout<<"len:"<<ListLength_SL(L,la)<<endl;
        cout<<"*****************"<<endl;
        cout<<ListEmpty_SL(L,la)<<endl;
    }
/*    while(m != -2)
    {
        cin>>m;
        GetElem_SL(L,la,m,e);
        cout<<"get elem :"<<e<<endl;
    }*/
    while(m != -3)
    {
        cin>>m;
        e = LocateElem_SL(L,la,m);
        cout<<"get elem :"<<e<<endl;
    }
/*    cout<<"已经清除链表..."<<endl;
    ClearList_SL(L,la);
    ListTraverse_SL(L,la,visit);
    cout<<"len:"<<ListLength_SL(L,la)<<endl;

        cin>>i;
    for( j = 0; j < i;j++)
    {
        cin>>e;
        cin>>index;
        ListInsert_SL(L,la,index,e);
    }
    cout<<"traverse:";
    ListTraverse_SL(L,la,visit);
    cout<<"len:"<<ListLength_SL(L,la)<<endl;

    while(m != -2)
    {    
        cin>>m;
        ListDelete_SL(L,la,m,e);
        cout<<"*****************"<<endl;
        cout<<"del :"<<e<<endl;
        ListTraverse_SL(L,la,visit);
        cout<<"len:"<<ListLength_SL(L,la)<<endl;
        cout<<"*****************"<<endl;
    }
    */
    return 0;
}