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

#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define MAX_SIZE 100
    
typedef int Status;
typedef int ElementType;

typedef struct StaticLinkList
{
 ElementType data;
 int cur;
}component,SLinkList[MAX_SIZE];

int Malloc(SLinkList space);
void Free(SLinkList space,int k);
void initList(SLinkList l);
void ClearList(SLinkList l);
Status GetElement(SLinkList l,int i,ElementType *e);
int LocateElement(SLinkList l,ElementType e);
Status PriorElement(SLinkList l,ElementType cur_e,ElementType *pre_e);
Status NextElement(SLinkList l,ElementType cur_e,ElementType *next_e);
Status ListInsert(SLinkList l,int i,ElementType e);
Status ListDelete(SLinkList l,int i,ElementType *e);
void ListTraverse(SLinkList l, void (*visit)(ElementType));
void print1(ElementType e);

#include <stdio.h>
#include "staticlink.h"
//备用链表不为空返回分配的结点下标
int Malloc(SLinkList space)
{
 int i = space[0].cur;
 if(i)
   space[0].cur = space[i].cur;//备用链表的头结点指向原备用链表的第二个空闲结点
 return i;
}

//将下标为k的结点回收到备用链表中
void Free(SLinkList space,int k)
{
 space[k].cur = space[0].cur;//回收结点游标指向备用链表的第一个结点
 space[0].cur = k;//备用链表的头结点指向新回收的结点
}

/*构造一个空的链表l，表头为l，最后一个单元l[MAX_SIZE - 1]，其他单元链成一个备用
 链表，表头为l的第一个单元l[0],"0" 表示空指针
*/
void initList(SLinkList l)
{
 int i;
 l[MAX_SIZE - 1].cur = 0;//最后一个单元为空链表的表头
 //其他单元链接成以l[0]为表头的备用链表
 for(i = 0; i < MAX_SIZE - 2;i++) 
 {
   l[i].cur = i+1;  

 }

}

//清空链表
void ClearList(SLinkList l)
{
 int j,k,i=l[MAX_SIZE-1].cur;//i指向链表的第一个结点
 l[MAX_SIZE-1].cur=0;//第一个结点为头结点表示链表为空
 k=l[0].cur;//备用链表第一个结点的位置即第一个空闲结点的位置
 l[0].cur = i;
 while(i){
  j = i;
  i=l[i].cur;
 }
l[j].cur = k;

}

Status ListEmpty(SLinkList l)  
{
 if(l[MAX_SIZE-1].cur == 0)
   return TRUE;
 else 
   return FALSE;
}

int ListLength(SLinkList l)
{
 int j = 0,i=l[MAX_SIZE -1].cur;
 while(i)
 {
  i = l[i].cur;
  j++;  

 }

return j;
}

Status GetElement(SLinkList l,int i,ElementType *e)
{
 int m,k=MAX_SIZE-1;
 if(i<1||i>ListLength(l))
  return ERROR;
 for(m=1;m<=i;m++) 
   k=l[k].cur;
*e = l[k].data;
return OK;
}

int LocateElement(SLinkList l,ElementType e){
int i = l[MAX_SIZE-1].cur;
 while(i && l[i].data !=e)
  i = l[i].cur;
return i;

}

Status PriorElement(SLinkList l,ElementType cur_e,ElementType *pre_e){
 int j,i=l[MAX_SIZE -1].cur;
 do{
  j = i;
  i = l[i].cur;
  
  }while(i && cur_e!=l[i].data);
if(i)
{
 *pre_e=l[j].data;
 return OK;

}else
 return ERROR;

}

Status NextElement(SLinkList l,ElementType cur_e,ElementType *next_e){
 int j,i=LocateElement(l,cur_e);
 if(i)
{
 j=l[i].cur;
 if(j)
 {
  *next_e=l[j].data;
  return OK;

 }

}
return ERROR;

}

Status ListInsert(SLinkList l,int i,ElementType e){
int m,j,k=MAX_SIZE-1;
if(i < 1 || i > ListLength(l) + 1 )
 return ERROR;
j=Malloc(l);
if(j)
{
  l[j].data = e;
  for(m =1;m<i;m++)
   k=l[k].cur;
 l[j].cur=l[k].cur;
 l[k].cur = j;
 return OK;

}
return ERROR;
}

Status ListDelete(SLinkList l,int i,ElementType *e){
int j,k=MAX_SIZE-1;
if(i < 1||i> ListLength(l))
 return ERROR;
for(j =1;j<i;j++)
 k=l[k].cur;
j=l[k].cur;
l[k].cur=l[j].cur;
*e=l[j].data;
Free(l,j);
return OK;
}

void print1(ElementType e){
printf("%3d",e);
}

void ListTraverse(SLinkList l, void (*visit)(ElementType)){
int i = l[MAX_SIZE -1].cur;
while(i){
visit(l[i].data);
i=l[i].cur;
}
printf("\n");


}

#include <stdio.h>
#include "staticlink.h"

int main(void){
SLinkList l;
int i,k,j;
ElementType e0,e1,e;
initList(l);
for(i=1;i<=5;i++)
 ListInsert(l,i,i);
k=ListEmpty(l);
printf("表为空?k=%d(1:是0:否)",k);
printf("\n");
ListTraverse(l,print1);
printf("链表的长度%d",ListLength(l));
printf("\n");
printf("清空链表\n");
ClearList(l);
printf("清空后");
ListTraverse(l,print1);
printf("再次判断是否为空\n");
k=ListEmpty(l);
printf("表为空?k=%d(1:是0:否)",k);
printf("\n");
printf("再次插入元素\n");
for(i=1;i<=10;i++)
 ListInsert(l,i,i);
ListTraverse(l,print1);
printf("链表的长度%d",ListLength(l));
printf("\n");

printf("前驱判断\n");
for(i=1;i<=10;i++){
GetElement(l,i,&e0);
k=PriorElement(l,e0,&e1);
if(k==ERROR)
  printf("元素%d无前驱\n",e0);
else
 printf("元素%d的前驱是%d\n",e0,e1);

}

  printf("\n");
  printf("\n");
  
  printf("后继判断\n");


for(i=1;i<=10;i++)
  { GetElement(l,i,&e0);//把L中的第i个元素的值赋给e0
    k=NextElement(l,e0,&e1);//求e0的前驱，成功的话赋给e1
 if(k==ERROR)
  printf("元素%d无后继\n",e0);
    else
  printf("元素%d的后继%d\n",e0,e1);
  }

  printf("\n删除元素\n");
  k=ListLength(l);
  for(j=k+1;j>0;j--)
  { i=ListDelete(l,j,&e);//删除第j个元素
    if(i==ERROR)
  printf("删除第%d个元素失败\n",j);
 else
  printf("删除第%d个元素成功,其值为%d\n",j,e);
  }

return 0;
}