/////////////////////////////////////////////////////////// 
//--------------------------------------------------------- 
//           链式存储结构线性表基本操作 
//--------------------------------------------------------- 
/////////////////////////////////////////////////////////// 

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

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

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

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

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

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

typedef struct{
	ElemType data;//节点存储的数据 
    struct LNode *next;
}LNode;

typedef struct{
	char name[20];//该结点指向链表数据的名称 
    struct LNode *head;// 该结点指向链表数据的地址 
}HNode;

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

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

///////////////////////////////////////
//函数名：DestroyList()
//参数：LNode *headp
//初始条件：线性表L已存在
//功能：销毁线性表
//返回值：headp==NULL:ERROR
//        headp!=NULL:OK
///////////////////////////////////////
Status DestroyList(LNode **headp)
{
	if(*headp==NULL)
		return ERROR;
	LNode *p=*headp,*nextp;
	while(p!=NULL){//依次释放存储空间 
		nextp=p->next;
		free(p);
		p=nextp;
	}
	*headp=NULL; 
	return OK;
}

///////////////////////////////////////
//函数名：ClearList()
//参数：LNode *headp
//初始条件：线性表L已存在
//功能：清空线性表
//返回值：headp:ERROR
//        headp!=NULL:OK
///////////////////////////////////////
Status ClearList(LNode *headp)
{
    if(headp==NULL)
		exit(OVERFLOW); 
	if(headp->next==NULL)
        exit(ERROR);
    LNode *p=headp->next,*nextp;
    while(p!=NULL){//依次释放存储空间 ，保留表头结点 
		nextp=p->next;
		free(p);
		p=nextp;
	}
	headp->next=NULL;
    return OK;
}

///////////////////////////////////////
//函数名：ListEmpty()
//参数：LNode *headp
//初始条件：线性表L已存在
//功能：判断线性表是否为空
//返回值：空：TRUE
//        非空：FALSE
///////////////////////////////////////
Status ListEmpty(LNode *headp)
{
	if(headp==NULL)
		exit(OVERFLOW);
	if(headp->next==NULL)
		return TRUE;
	else return FALSE;
}
///////////////////////////////////////
//函数名：ListLength()
//参数：LNode *headp
//初始条件：线性表L已存在
//功能：返回线性表长度
//返回值：线性表长度(length)
///////////////////////////////////////
int ListLength(LNode *headp)
{
	LNode *p=headp;
	int length=0;
	while(p->next!=NULL){
		length++;
		p=p->next;
	} 
    return length;
}

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

///////////////////////////////////////
//函数名：LocateElem()
//参数：LNode *headp,ElemType e
//初始条件：线性表L已存在
//功能：返回线性表L中第1个与e相等的元素的位序 
//返回值：若在L中存在与e相等的元素：其位序
//        若在L中不存在与e相等的元素：0
///////////////////////////////////////
int LocateElem(LNode *headp,ElemType e)
{
    int i=0;
    LNode *p=headp;
	while(p!=NULL){
		if(p->data==e)
			return i;
		p=p->next;
		i++;
	} 
    return 0;
}

///////////////////////////////////////
//函数名：PriorElem()
//参数：LNode *headp,ElemType cur_e,ElemType *pre_e
//初始条件：线性表L已存在
//功能：用pre_e返回线性表中cur_e的前驱
//返回值：cur_e或cur_e前驱不存在：FALSE
//        找到前驱：OK
///////////////////////////////////////
Status PriorElem(LNode *headp,ElemType cur_e,ElemType *pre_e)
{
	LNode *p,*pre_p;
	pre_p=headp;
	p=pre_p->next;
	while(p!=NULL){
		if(p->data==cur_e){
			*pre_e=pre_p->data;
			return OK;
		}
		pre_p=p;
		p=p->next;
	}
    return FALSE;
}

///////////////////////////////////////
//函数名：NextElem()
//参数：LNode *headp,ElemType cur_e,ElemType *next_e
//初始条件：线性表已存在
//功能：用next_e返回线性表中cur_e的后继
//返回值：cur_e不存在或为最后一个元素：FALSE
//        找到后继：OK
///////////////////////////////////////
Status NextElem(LNode *headp,ElemType cur_e,ElemType *next_e)
{
	LNode *p=headp;
	while(p->next!=NULL){
		if(p->data==cur_e){
			p=p->next;
			*next_e=p->data;
			return OK;
		}
		p=p->next; 
	} 
	return FALSE;
}

///////////////////////////////////////
//函数名：ListInsert()
//参数：LNode *headp,int i,ElemType e
//初始条件：线性表L已存在，1<=i<=ListLength(headp)+1
//功能：在线性表中第i个数据元素之前插入数据元素e
//返回值：失败：ERROR
//        成功：OK
///////////////////////////////////////
Status ListInsert(LNode *headp,int i,ElemType e)
{
	if(i<1||i>ListLength(headp)+1)
		return ERROR;
	LNode *pa,*p;
	p=headp;
	pa=(LNode*)malloc(sizeof(LNode));
	if(pa==NULL)
		exit(OVERFLOW);
	pa->data=e;
	int j=1;
	for(;j<i;j++){
		p=p->next;
	}
	pa->next=p->next;
	p->next=pa;
	return OK;
}

///////////////////////////////////////
//函数名：ListDelete()
//参数：LNode *headp,int i,Elemtype *e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：将线性表L中第i个数据元素删除
//返回值：失败：ERROR
//        成功：OK
///////////////////////////////////////
Status ListDelet(LNode *headp,int i,ElemType *e)
{
    if(i<1||(i>ListLength(headp)))	//i值不合法 
        return ERROR;
    LNode *p=headp,*pp,*pq;
	int j=1;
	for(;j<i;j++){
		p=p->next;
	}
	pp=p->next;
	*e=pp->data;
	p->next=pp->next;
	free(pp);
    return OK;
}
///////////////////////////////////////
//函数名：ListTraverse()
//参数：LNode *headp
//初始条件：线性表已存在。
//功能：依次输出线性表的每个数据元素
//返回值：线性表为空表：0 
//		  线性表不为空表：OK 
///////////////////////////////////////
Status ListTrabverse(LNode *headp)
{
	if(headp->next==NULL)
		return 0;
	LNode *p=headp->next;
//    printf("\n-----------all elements -----------------------\n");
    while(p!=NULL){
    	printf("%d\t",p->data);
    	p=p->next;
    }
//    printf("\n------------------ end ------------------------\n");
    return OK;
}
///////////////////////////////////////
//函数名：ReadF()
//参数：LNode *headp,char *name
//初始条件：线性表L已存在。
//功能：给线性表赋值 
//返回值：失败：ERROR
//		  成功：OK 
///////////////////////////////////////
Status ReadF(LNode *headp,char *name)
{
	LNode *pd=headp,*s;
	FILE *fp;
	if ((fp=fopen(name,"r"))==NULL)
	{
	 printf("File open error\n ");
	 return ERROR;
	}
	
	while(!feof(fp)){
		s=(LNode*)malloc(sizeof(LNode));
		if(fread(s,sizeof(LNode),1,fp)!=1){
			free(s);
			break;
		}
		s->next=NULL;
		pd->next=s;
		pd=pd->next;
	}
		//这里从文件中逐个读取数据元素恢复顺序表
	fclose(fp);
	return OK;
}
///////////////////////////////////////
//函数名：AssignElem()
//参数：LNode *headp
//初始条件：线性表L已存在。
//功能：给线性表赋值 
//返回值：失败：ERROR
//		  成功：OK 
///////////////////////////////////////
Status AssignElem(LNode *headp)
{
	char con;
	int i=1; 
	ElemType el;
	LNode *p=headp,*pp;
loop:
	pp=(LNode *)malloc(sizeof(LNode));
	printf("请输入第%d个元素值",i);
	i++;
	scanf("%d",&el); 
	pp->data=el;
	p->next=pp;
	p=pp;
	pp->next=NULL;
	getchar();
	printf("继续输入？y/n\n");
	scanf("%c",&con);
	if(con=='Y'||con=='y')
	goto loop;
	return OK;
}
 
///////////////////////////////////////
//函数名：SaveFile()
//参数：LNode *headp,char *name
//初始条件：线性表L已存在。
//功能：保存数据到文件 
//返回值：失败：ERROR
//		  成功：OK 
///////////////////////////////////////
Status SaveFile(LNode *headp,char *name)
{
	FILE *fp;
	LNode *p=headp;
	p=p->next;
	if((fp=fopen(name,"w"))==NULL){
		printf("File open error\n");
		return ERROR;
	}
	while(p!=NULL){
		fwrite(p,sizeof(LNode),1,fp);
		p=p->next;
	}
	fclose(fp);
	return OK; 
} 
/*--------------------------------------------*/
void main(void)
{	
Sqlist *L;/*最开头的结点，指向一条线性表（线性表的每个值均指向一条链式表）*/ 
L=(Sqlist*)malloc(sizeof(Sqlist));
L->length=3;
L->listsize=20;
HNode *hhp;
hhp=(HNode*)malloc(sizeof(HNode)*20);
L->elem=hhp;
strcpy(L->elem[0].name,"data0.dat");/*L指向的线性表每个结点的名称，也是保存的文件的名称*/ 
strcpy(L->elem[1].name,"data1.dat");
strcpy(L->elem[2].name,"data2.dat");
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. InputElem\n");
	printf("    	  7. LocateElem      14. ReadFile\n");
	printf("    	  15. SaveFile       0. Exit\n");
	printf("-------------------------------------------------\n");
	printf("    请选择你的操作[0~15]:");
	scanf("%d",&op);
    switch(op){
		case 1:
		{
			int i;
			for(i=0;i<3;i++)
			{
				if(InitList(&L->elem[i].head)==OK) printf("线性表%s创建成功！\n",L->elem[i].name);
				else printf("线性表%s创建失败！\n",L->elem[i].name);
			}
			getchar();getchar();
		}
			break;
		case 2:
		{
			int i;
			for(i=0;i<3;i++)
			{
				if(DestroyList(&L->elem[i].head)==OK) printf("线性表%s销毁成功！\n",L->elem[i].name);
				else printf("线性表%s销毁失败！\n",L->elem[i].name);
			}
			getchar();getchar();
		}
			break;
		case 3:
		{
			int i;
			for(i=0;i<3;i++)
			{
				if(ClearList(L->elem[i].head)==OK) printf("线性表%s清空成功！\n",L->elem[i].name);
				else printf("线性表%s清空失败！\n",L->elem[i].name);
			}
			getchar();getchar();
		}
			break;
		case 4:
		{
			int i;
			for(i=0;i<3;i++)
			{
				if(ListEmpty(L->elem[i].head)==OK) printf("线性表%s是空的！\n",L->elem[i].name);
				else printf("线性表%s不是空的！\n",L->elem[i].name);
			}
		 	getchar();getchar();
		}
		 	break;
		case 5:
	   	{
			int i;
			for(i=0;i<3;i++)
			{
			printf("线性表%s的长度为%d\n",L->elem[i].name,ListLength(L->elem[i].head));
			}
		 	getchar();getchar();
	   	}
			break;
		case 6:
		{
			int i,pos;
			ElemType value;
			printf("请输入要查找的链表序号和在该序号中的位置:");/*链表序号从0开始，位置从1开始*/
			scanf("%d %d",&i,&pos);
			GetElem(L->elem[i].head,pos,&value);
			printf("第%d条链表第%d位是%d",i,pos,value);   
			getchar();getchar();
	   	}
			break;
		case 7:
		{
			int i,j;
			ElemType valuee;
			printf("请输入要查找的数据元素值:");
			scanf("%d",&valuee);
			for(j=0;j<3;j++)
			{
				i=LocateElem(L->elem[j].head,valuee);
				if(i) break;
			}
			if(j==2&&i==0){
				printf("不存在数据元素%d\n",valuee);
			}
			else {
				printf("数据元素%d在第%d条链表第%d位\n",valuee,j,i);
			}
			getchar();getchar();
		}
		 	break;
		case 8:
		{ 
			int i,flag=0; 
			ElemType pur_e;
			printf("请输入要查找前驱的元素值：");
			scanf("%d",&pur_e);     
			for(i=0;i<3;i++)
			{
				if(PriorElem(L->elem[i].head,pur_e,&e)==OK){
					printf("数据元素%d的前驱是%d，在第%d条链中\n",pur_e,e,i);
					flag=1;
					break;
				}
			}			
			if(flag==0)
			printf("数据元素%d的前驱不存在\n");
			getchar();getchar();
	   	} 
			break;
		case 9:
	    { 
			int i,flag=0; 
			ElemType pur_e;
			printf("请输入要查找后继的元素值：");
			scanf("%d",&pur_e);     
			for(i=0;i<3;i++)
			{
				if(NextElem(L->elem[i].head,pur_e,&e)==OK){
					printf("数据元素%d的后继是%d，在第%d条链中\n",pur_e,e,i);
					flag=1;
					break;
				}
			}			
			if(flag==0)
			printf("数据元素%d的后继不存在\n");
			getchar();getchar();
	   	} 
			break;
		case 10:
		{
			printf("请依次输入要插入链序号，在该链中的位置和要插入的值：");
			int i,pos,el;
			scanf("%d %d %d",&i,&pos,&el);
			if(ListInsert(L->elem[i].head,pos,el)==OK) printf("元素插入成功！");
			else printf("元素插入失败！"); 
			getchar();getchar();
		}   
			break;
		case 11:
		{
			printf("请输入要删除的链序号和在该链中的位置");
			int i,pos;
			scanf("%d %d",&i,&pos);
			if(ListDelet(L->elem[i].head,pos,&e)==OK) printf("元素%d删除成功！",e);
			else printf("元素删除失败！"); 
			getchar();getchar();
		} 
			break;
		case 12:  
		{
			int i;
			for(i=0;i<3;i++)
			{
				printf("\n--------all elements of %s-----------\n",L->elem[i].name);
				if(!ListTrabverse(L->elem[i].head)) 
				printf("线性表%s是空表！\n",L->elem[i].name);
				printf("\n------------------ end ------------------------\n");
			}
			getchar();getchar();
		}   
			break;
		case 13:
		{
			int i;
			for(i=0;i<3;i++)
			{
				printf("正在为链表%s赋值…\n",L->elem[i].name);
				if(AssignElem(L->elem[i].head)){
					printf("赋值成功\n");
				}
				else printf("赋值失败");
			}
			getchar();getchar(); 
	   	}
			break;
		case 14:
		{
			int i;
			for(i=0;i<3;i++)
			{
				if(ReadF(L->elem[i].head,L->elem[i].name)) printf("文件%s打开成功！\n",L->elem[i].name);
				else printf("文件%s打开失败！\n",L->elem[i].name);
			}
			getchar();getchar(); 
	   	}
			break;
		case 15:
		{
			int i;
			for(i=0;i<3;i++)
			{
				if(SaveFile(L->elem[i].head,L->elem[i].name)) printf("文件%s保存成功！\n",L->elem[i].name);
				else printf("文件保存失败！");
			}
			getchar();getchar(); 
	   	}
			break;
		case 0:
    		break;
	}//end of switch
}//end of while
printf("欢迎下次再使用本系统！\n");
}//end of main()