#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <io.h>
#include <math.h>
#include <sys/timeb.h>
#include <stdarg.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;
typedef int Boolean;
typedef int ElemTtpe;
//typedef ElemType * Triplet;
/c2-3.h线性表的静态单链表存储结构。
#define MAX_SIZE 100
typedef struct
{  
ElemType data;
int cur;
}component,SLinkList[MAX_SIZE];
/bo2-5.h 静态链表(数据结构由c2-3.h定义)的基本操作(13个)
#define DestroyList ClearList//DestroyList()和ClearList()的操作是一样的
int Malloc(SLinkList space)
{ //备用链表非空,则返回分配的结点下标(备用链表的第一个结点);否则返回0
int i=space[0].cur;//备用链表第一个结点的位置
if(i)
space[0].cur=space[i].cur;
return i;
}
void Free(SLinkList space,int k)

//将下标为k的空闲结点回收到备用链表中(成为备用链表的第一个结点)
space[k].cur=space[0].cur;
space[0].cur=k;
}
void InitList(SLinkList L)
{  
//构造一个空的链表L,表头为L的最后一个单元L[MAX_SIZE-1],其余单元链成
//一个备用链表,表头为L的第一个单元L[0],"0"表示空指针。
int i;
L[MAX_SIZE-1].cur=0;
for(i=0;i<MAX_SIZE-2;i++)
L[i].cur=i+1;
L[MAX_SIZE-2].cur=0;
}
void ClearList(SLinkList L)
{  
   //初始条件:线性表已存在。操作结果:将L重置为空表
int j,i=L[0].cur;
while(i)

j=i;
i=L[i].cur;
}
L[j].cur=L[MAX_SIZE-1].cur;
L[MAX_SIZE-1].cur=0;
}
Status ListEmpty(SLinkList L)
{  
//若L是空表,则返回TRUE;否则返回FALSE
if(L[MAX_SIZE-1].cur==0)
return TRUE;
else
return FALSE;
}
int ListLength(SLinkList L)
{  
//返回L中数据元素的个数
int j=0,i=L[MAX_SIZE-1].cur;
while(i)
{  
i=L[i].cur;
j++;
}
return j;
}
Status GetElem(SLinkList L,int i,ElemType &e)
{  
//用e返回L中第i个元素的值
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 LocateElem(SLinkList L,ElemType e)
{  
//在静态单链线性表L中查找第一个值为e的元素。若找到,则返回它在L中的位序;否则返回0
//(与其他LocateElem()的定义不同)
int i=L[MAX_SIZE-1].cur;
while(i && L[i].data!=e)
i=L[i].cur;
return i;
}
Status PriorElem(SLinkList L,ElemType cur_e,ElemType &pre_e)
{  
//初始条件:线性表L存在
//操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱;
//  否则操作失败,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;
} return ERROR;
}
Status NextElem(SLinkList L,ElemType cur_e,ElemType &next_e)
{  
//初始条件:线性表L已存在
//操作结果:若cur_e是数据L的数据元素,且不是最后一个,则用next_e返回它的后继;
// 否则操作失败,next_e无定义
int j,i=LocateElem(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,ElemType e)
{  
//在L中第i元素之前插入新的数据元素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,ElemType &e)
{  
//删除在l中第i个数居元素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 ListTraverse(SLinkList L,void(*visit)(ElemType))
{  
//初始条件:线性表L存在。操作结果:依次对L的每个数据元素调用函数visit()
int i=L[MAX_SIZE-1].cur;
while(i)
{  
visit(L[i].data);
i=L[i].cur;
}
printf("\n");
}
Status equal(ElemType c1,ElemType c2)
{
//判断是否相等的函数
if(c1==c2)
return TRUE;
else
return FALSE;
}
int comp(ElemType a,ElemType b)
{
//根据a<、=或>b,分别返回-1、0或1
if(a==b)
return 0;
else
return(a-b)/abs(a-b);
}
void print(ElemType c)
{
    printf(" %d ",c);
}
void print1(ElemType &c)
{
//以十进制整型的格式输出元素的值
printf(" %d ",c);
}
void print2(ElemType c)
{
  //以字符型的格式输出元素的值
printf(" %c ",c);
}// func2-3.h检验单链表基本操作的主函数
//main2-2.cpp、main2-3.cpp.main2-4.cpp和main2-5.cpp调用
int main(void)
{
LinkList L;
ElemType e, e0;
Status i;
int j,k;
InitList(L);
for(j=1;j<=5;j++)
i=ListInsert(L,1,j);
printf("在L的表头依次插入1—5后,L=");
ListTraverse(L,print);
i=ListEmpty(L);
printf("L是否空?i=%d(1:是 0:否),表L的长度=%d\n",i,ListLength(L));
ClearList(L);
//printf("%d\n",ListLength(L));
printf("清空L后,L=");
ListTraverse(L,print); i=ListEmpty(L);
printf("L是否为空?i=%d(1: 是 0:否),表L的长度=%d\n",i,ListLength(L));
for(j=1;j<=10;j++)
ListInsert(L,j,j);
printf("在L的表尾依次1—10后,L=");
ListTraverse(L,print);
for(j=0;j<=1;j++)
{
#ifdef SLL//仅用于静态链表
k=LocateElem(L,j);
if(k)
printf("值为%d的元素的位序为%d\n",k,j);
#else
k=LocateElem(L,j,equal);
if(k)
printf("第%d个元素的值为%d\n",k,j);
#endif
else
printf("没有值为%d的元素,",j);
}
for(j=1;j<=2;j++)
{
GetElem(L,j,e0);
i=PriorElem(L,e0,e);
if(i==ERROR)
printf("元素%d无前驱,",e0);
else
printf("元素%d的前驱为%d\n",e0,e);
}
for(j=ListLength(L)-1;j<=ListLength(L);j++)
{ GetElem(L,j,e0);
 i=NextElem(L,e0,e);
 if(i==ERROR)
 printf("元素%d无后继\n",e0);
 else
printf("元素%d的后继为%d",e0,e);
}
k=ListLength(L);
for(k=k+1;j>=k;j--)
{
i=ListDelete(L,j,e);
if(i==ERROR)
printf("删除第%d个元素失败(存在此元素)。",j);
else
printf("删除第%d个元素成功,其值为%d\n",j,e);
}
printf("依次输出L的元素: ");
ListTraverse(L,print);
DestroyList(L);
#ifndef SLL
printf("销毁L后,L=%u\n",L);
# endif
return 0;
}
//main2-4.cpp检验bo2-5.h的主程序
#include"c1.h"
typedef int ElemType;//定义ElemType为整型
#include"c2-3.h" //静态单链表的存储结构
#include"bo2-5.h"//静态单链表的基本操作(13个)
#include"func2-2.h"//包括equal()、comp()、print()、print1()和print2()函数
typedef SLinkList LinkList; //定义func2-3.h中的LinkList类型为SLinkList类型
#define SLL//定义了SLL(静态链表标志),使func2-3.h选择执行静态链表特头的函数
#include"func2-3.h"//主