/////////////////////////////////////////////////////////// 
//--------------------------------------------------------- 
//            顺序存储结构线性表基本操作 
//--------------------------------------------------------- 
/////////////////////////////////////////////////////////// 

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

//以下为函数运行结果状态代码 

#define TRUE 1
#define FALSE 0
#define OK 1 
#define ERROR 0 
#define INFEASIBLE -1 
#define OVERFLOW -2 

#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量 
#define LISTINCREMENT 1  //线性表存储空间分配增量 

typedef int Status; //函数类型，其值为为函数结果状态代码 

typedef int ElemType; //假设数据元素为整型 

typedef struct 
{ 
    ElemType *elem; //存储空间基址 
    int length; //当前长度 
    int listsize; //当前分配的存储容量 
}Sqlist; 
//实现线性表的顺序存储结构的类型定义

///////////////////////////////////////
//函数名：InitList()
//参数：SqList *L
//初始条件：无
//功能：构造一个空线性表
//返回值：存储分配失败：OVERFLOW
//        存储分配成功：OK
///////////////////////////////////////
Status InitList(Sqlist *L)
{
    L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(L->elem==NULL)
        exit(OVERFLOW);
    else
    {
        L->length=0;
        L->listsize=LIST_INIT_SIZE;
        return OK;
    }
}

///////////////////////////////////////
//函数名：DestroyList()
//参数：SqList *L
//初始条件：线性表L已存在
//功能：销毁线性表
//返回值：L->elem==NULL:ERROR
//        L->elem!=NULL:OK
///////////////////////////////////////
Status DestroyList(Sqlist *L)
{
	int i; 
    if(L->elem==NULL)
        return ERROR;
    else
        for(i=0;i<L->length;i++) 
			free(&L->elem[i]);//释放数据区域 
    free(L);//释放结构区域 
    return OK;
}

///////////////////////////////////////
//函数名：ClearList()
//参数：SqList *L
//初始条件：线性表L已存在
//功能：清空线性表
//返回值：L->elem==NULL:ERROR
//        L->elem!=NULL:OK
///////////////////////////////////////
Status ClearList(Sqlist *L)
{
    if(L->elem==NULL)
        exit(ERROR);
    int i;
    ElemType *p_elem=L->elem;
    for(i=0;i<L->length;i++)
    {
        *L->elem=NULL;
        L->elem++;
    }
    L->elem=p_elem;//指针指向首地址 
    L->length=0;
    return OK;
}

///////////////////////////////////////
//函数名：ListEmpty()
//参数：SqList L
//初始条件：线性表L已存在
//功能：判断线性表是否为空
//返回值：空：TRUE
//        非空：FALSE
///////////////////////////////////////
Status ListEmpty(Sqlist L)
{
    if (L.length==0) 
    	return TRUE;
    else return FALSE;
}
///////////////////////////////////////
//函数名：ListLength()
//参数：SqList L
//初始条件：线性表L已存在
//功能：返回线性表长度
//返回值：线性表长度(L.length)
///////////////////////////////////////
int ListLength(Sqlist L)
{
    return L.length;
}

///////////////////////////////////////
//函数名：GetElem()
//参数：SqList L,int i,ElemType *e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：用e返回线性表中第i个元素的值
//返回值：(i<1)||(i>ListLength(L))：OVERFLOW
//        1<=i<=ListLength(L)：OK
///////////////////////////////////////
Status GetElem(Sqlist L,int i,ElemType *e)
{
    if(i<1||i>L.length)
        return OVERFLOW;
    *e=*(L.elem+i-1);
    return OK;
}

///////////////////////////////////////
//函数名：LocateElem()
//参数：Sqlist L,ElemType e
//初始条件：线性表L已存在
//功能：返回顺序表L中第1个与e相等的元素
//返回值：若在L中存在于e相等的元素：其位序
//        若在L中不存在与e相等的元素：0
///////////////////////////////////////
int LocateElem(Sqlist L,ElemType e)
{
    int i;
    ElemType *p_elem=L.elem;
    for(i=1;i<=L.length;i++)
    {
        if(*L.elem==e)//值与目标值相等 
        {
            L.elem=p_elem;//指针指向首地址 
            return i;
        }
        else
            L.elem++;
    }
    return 0;
}

///////////////////////////////////////
//函数名：PriorElem()
//参数：Sqlist L,ElemType cur_e,ElemType *pre_e
//初始条件：线性表L已存在，i>1&&i<=L.length，LocationElem()存在
//功能：用pre_e返回线性表中cur_e的前驱
//返回值：i<=1||i>L.length：OVERFLOW
//        i>1&&i<=L.length：OK
///////////////////////////////////////
Status PriorElem(Sqlist L,ElemType cur_e,ElemType *pre_e)
{
    ElemType *p_elem=L.elem;
    int i;
    i=LocateElem(L,cur_e);//找到当前元素的位置 
    if(i<=1||i>L.length)
        exit(OVERFLOW);
    GetElem(L,i-1,pre_e);
    return OK;
}

///////////////////////////////////////
//函数名：NextElem()
//参数：Sqlist L,ElemType cur_e,ElemType *next_e
//初始条件：线性表L已存在，i>=1&&i<L.length，LocationElem()存在
//功能：用next_e返回线性表中cur_e的后继
//返回值：i<1||i>=L.length：OVERFLOW
//        i>=1&&i<L.length：OK
///////////////////////////////////////
Status NextElem(Sqlist L,ElemType cur_e,ElemType *next_e)
{
    ElemType *p_elem;
    int i;
    i=LocateElem(L,cur_e);
    if(i<1||i>=L.length)
        exit(OVERFLOW);
    GetElem(L,i+1,next_e);
    return OK;
}

///////////////////////////////////////
//函数名：ListInsert()
//参数：SqList *L,int i,ElemType el
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1
//功能：在线性表中第i个数据元素之前插入数据元素e
//返回值：失败：ERROR
//        成功：OK
///////////////////////////////////////
Status ListInsert(Sqlist *L,int i,ElemType el)
{
    int *q=&(L->elem[i-1]);
    ElemType *newbase,*p;
    if(i<1||i>(L->length+1))
        return ERROR;
    if(L->length>=L->listsize)
    {
        newbase=(ElemType*)realloc(L->elem,L->listsize+LISTINCREMENT*sizeof(ElemType));
        if(newbase==NULL)//重新分配空间失败 
            exit(OVERFLOW);
        L->elem=newbase;
        L->listsize+=LISTINCREMENT;
    }
    for(p=&(L->elem[L->length-1]);p>=q;--p)
        *(p+1)=*p;
    *q=el;
    ++L->length;
    return OK;
}

///////////////////////////////////////
//函数名：ListDelete()
//参数：SqList L,int i,Elemtype e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：将线性表L中第i个数据元素删除
//返回值：失败：ERROR
//        成功：OK
///////////////////////////////////////
Status ListDelet(Sqlist *L,int i,ElemType *e)
{
    if(i<1||(i>L->length))			//i值不合法 
        return ERROR;
    ElemType *p,*q;
    p=&(L->elem[i-1]);
    *e=*p;
    q=L->elem+L->length-1;
    for(++p;p<=q;++p)
        *(p-1)=*p;
    --L->length;
    return OK;
}
///////////////////////////////////////
//函数名：ListTraverse()
//参数：Sqlist L
//初始条件：线性表L已存在。
//功能：依次输出线性表L的每个数据元素
//返回值：失败：ERROR
//		  成功：OK 
///////////////////////////////////////
Status ListTrabverse(Sqlist L){
   int i;
   printf("\n-----------all elements -----------------------\n");
   for(i=0;i<L.length;i++) printf("%d ",L.elem[i]);
   printf("\n------------------ end ------------------------\n");
   return L.length;
}
///////////////////////////////////////
//函数名：AssignElem()
//参数：Sqlist *L
//初始条件：线性表L已存在。
//功能：给线性表赋值 
//返回值：失败：ERROR
//		  成功：OK 
///////////////////////////////////////
Status AssignElem(Sqlist *L){
	int ops;
	printf("请选择赋值方法：\n"); 
	printf("1.手动赋值      2.从文件读取\n"); 
	scanf("%d",&ops); 
	switch(ops){
		case 1:
			{
				int i;
				for(i=0;i<4;i++){
					printf("请输入第%d个元素的值：\n",i);
					scanf("%d",&(L->elem[i]));
				}
				L->length=4;
				printf("已成功为%d个元素赋值",i);
				return OK;
			}
			break;
		case 2:
			{
				FILE *fp;
				L->length=0;
				if ((fp=fopen("data.dat","r"))==NULL)
				{
				 printf("File open erroe\n ");
				 return ERROR;
				}
				while(fread(&L->elem[L->length],sizeof(ElemType),1,fp))
				   L->length++;
					//这里从文件中逐个读取数据元素恢复顺序表
				fclose(fp);
				return OK;
			}
			break;
	}
} 
///////////////////////////////////////
//函数名：SaveFile()
//参数：Sqlist *L
//初始条件：线性表L已存在。
//功能：保存数据到文件 
//返回值：失败：ERROR
//		  成功：OK 
///////////////////////////////////////
Status SaveFile(Sqlist *L){
	FILE *fp;
	if((fp=fopen("data.dat","w"))==NULL){
		printf("File open error\n");
		return ERROR;
	}
	fwrite(L->elem,sizeof(ElemType),L->length,fp);
	fclose(fp);
	return OK; 
} 
/*--------------------------------------------*/
void main(void){
  Sqlist *L=(Sqlist*)malloc(sizeof(Sqlist));
  ElemType e;
  int op=1;
  while(op){
	system("cls");
	printf("\n\n");
	printf("      Menu for Linear Table On Sequence Structure \n");
	printf("-------------------------------------------------\n");
	printf("    	  1. IntiaList       8. PriorElem\n");
	printf("    	  2. DestroyList     9. NextElem \n");
	printf("    	  3. ClearList       10. ListInsert\n");
	printf("    	  4. ListEmpty       11. ListDelete\n");
	printf("    	  5. ListLength      12. ListTrabverse\n");
	printf("    	  6. GetElem         13. AssignElem\n");
	printf("    	  7. LocateElem      14. SaveFile\n");
	printf("    	  0. Exit\n");
	printf("-------------------------------------------------\n");
	printf("    请选择你的操作[0~14]:");
	scanf("%d",&op);
    switch(op){
	   case 1:
	   	{
		 if(InitList(L)==OK) printf("线性表创建成功！\n");
		     else printf("线性表创建失败！\n");
		 getchar();getchar();
	   	}
		 break;
	   case 2:
		 if(DestroyList(L)==OK) printf("线性表销毁成功！\n");
		     else printf("线性表销毁失败！\n");
		 getchar();getchar();
		 break;
	   case 3:
		 if(ClearList(L)==OK) printf("线性表清空成功！\n");
		     else printf("线性表清空失败！\n");     
		 getchar();getchar();
		 break;
	   case 4:
		 if(ListEmpty(*L)) printf("线性表是空的\n");
		 else printf("线性表不是空的\n");
		 getchar();getchar();
		 break;
	   case 5:
	   	{
		 printf("线性表长度为%d\n",ListLength(*L));
		 getchar();getchar();
	   	}
		 break;
	   case 6:
	   	{
	   	int pos;
//	   	ElemType value;
	   	printf("请输入要查找的位置:");
	   	scanf("%d",&pos);
	   	GetElem(*L,pos,&e);
	   	printf("第%d位是%d",pos,e);   
		 getchar();getchar();
	   	}
		 break;
	   case 7:
	   	{
	   	int i;
//	   	ElemType valuee;
	   	printf("请输入要查找的数据元素值:");
		 scanf("%d",&e);
		 i=LocateElem(*L,e);
		 if(i){
		 	printf("数据元素%d在第%d位\n",e,i);
		 }
		 else{
		 	printf("不存在数据元素%d\n",e);
		 }  
		 getchar();getchar();
	   	}
		 break;
	   case 8:
	    { 
	    ElemType pur_e;
		printf("请输入要查找前驱的元素值：");
		 scanf("%d",&pur_e);     
		 if(PriorElem(*L,pur_e,&e)==OK) printf("数据元素%d的前驱是%d\n",pur_e,e);
		 else printf("数据元素%d的前驱不存在\n");
		 getchar();getchar();
	   	} 
		 break;
	   case 9:
	    { 
	    ElemType pur_e;
		printf("请输入要查找后继的元素值：");
		 scanf("%d",&pur_e);     
		 if(NextElem(*L,pur_e,&e)==OK) printf("数据元素%d的后继是%d\n",pur_e,e);
		 else printf("数据元素%d的后继不存在\n");
		 getchar();getchar();
	   	} 
		 break;
	   case 10:
	   	{
		printf("请输入要插入的位置和要插入的值：");
		int pos,el;
		scanf("%d %d",&pos,&el);
		if(ListInsert(L,pos,el)==OK) printf("元素插入成功！");
		else printf("元素插入失败！"); 
		getchar();getchar();
		}   
		 break;
	   case 11:
	   	{
		printf("请输入要删除的位置");
		int pos;
		scanf("%d",&pos);
		if(ListDelet(L,pos,&e)==OK) printf("元素%d删除成功！",e);
		else printf("元素删除失败！"); 
		getchar();getchar();
		} 
		 break;
	   case 12:     
		 if(!ListTrabverse(*L)) printf("线性表是空表！\n");
		 getchar();getchar();
		 break;
	   case 13:
	   	{
	   		if(AssignElem(L)){
	   			printf("赋值成功\n");
	   		}
	   		else printf("赋值失败");
			 getchar();getchar(); 
	   	}
	   	break;
	   case 14:
	   	{
	   		if(SaveFile(L)) printf("文件保存成功！\n");
	   		else printf("文件保存失败！");
	   		getchar();
	   	}
	   case 0:
         break;
	}//end of switch
  }//end of while
  printf("欢迎下次再使用本系统！\n");
}//end of main()