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

//函數(shù)結(jié)果狀態(tài)字符
#define TRUE     1     //代碼中出現(xiàn)TRUE相當(dāng)于出現(xiàn)了1
#define FALSE    0     //出現(xiàn)FALSE相當(dāng)于出現(xiàn)了0
#define OK       1     //出現(xiàn)OK相當(dāng)于出現(xiàn)了1
#define ERROR    0     //出現(xiàn)ERROR相當(dāng)于出現(xiàn)了0
#define INFEASIBLE    -1
#define OVERFLOW      -2 .

typedef int Status;
typedef int ElemType;

#define LIST_INIT_SIZE    100     //線性表存儲(chǔ)空間的初始分配量 
#define LISTINCREMENT     10      //線性表存儲(chǔ)空間的分配增量 

typedef struct{
	ElemType *elem;          //存儲(chǔ)空間的基址
	int length;              //當(dāng)前線性表的長(zhǎng)度
	int listsize;            //當(dāng)前線性表的存儲(chǔ)容量
}SqList;

//構(gòu)造一個(gè)空的線性表
Status InitList_Sq(SqList &L){
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));      //L.elem為首元素的地址 
	if(!L.elem){            //如果存儲(chǔ)空間分配失敗，L.elem為NULL
	printf("存儲(chǔ)空間分配失敗\n");
	exit(OVERFLOW);
	}
	L.length = 0;            //當(dāng)前線性表為空表，即線性表長(zhǎng)度為0
	L.listsize = LIST_INIT_SIZE;           //給線性表分配初始容量
	printf("一個(gè)空的線性表已經(jīng)構(gòu)建成功\n");      //輸出空線性表構(gòu)建成功的提示消息 
	return OK; 
} 

Status ValueList_Sq(SqList &L){
	int i,j;
	printf("請(qǐng)輸入線性表元素的個(gè)數(shù)：");
	scanf("%d",&i);
	if(i > L.listsize)                     //如果當(dāng)要輸入的元素個(gè)數(shù)大于內(nèi)存大小時(shí) 
	{
		while(1)             //一直開(kāi)辟新空間，直到開(kāi)辟的空間大于需要的空間為止
		{
			if(i > L.listsize){
				L.elem = (ElemType *)realloc(L.elem,LISTINCREMENT * sizeof(ElemType));
				L.listsize += LISTINCREMENT;
			}
			else
			break;
		}
	}
	for(j = 0;j < i;j++){
		printf("請(qǐng)輸入第%d個(gè)元素：",j + 1);
	    scanf("%d",&L.elem[j]);
	} 
	L.length = i;          //賦值完成后，修改并保存線性表的長(zhǎng)度 
	printf("賦值成功\n");
	return OK;
}

Status DistoryList_Sq(SqList &L){
	if(!L.elem){ 
	  printf("您還未建立線性表，請(qǐng)先建立線性表\n");
	  return ERROR; 
	} 
	free(L.elem);            //使用free函數(shù)，將之前動(dòng)態(tài)分配的內(nèi)存還給系統(tǒng) 
	L.elem = NULL;           //重置elem的值為Null 
	L.length = 0;            //將線性表的元素個(gè)數(shù)重置為0
	L.listsize = 0;          //將線性表的存儲(chǔ)容量重置為0 
	printf("線性表已經(jīng)銷毀\n"); 
	return OK;
}

//對(duì)線性表進(jìn)行重置
Status ClearList_Sq(SqList &L){
	if(L.elem){                  //如果線性表存在 
	    L.length = 0;            //將線性表的元素個(gè)數(shù)重置為0
	    printf("線性表已重置\n");
	    return OK;
	}
	else 
	printf("線性表不存在，無(wú)法重置\n");
	return OK;
} 

//判斷線性表是否為空
Status ListEmpty_Sq(SqList L){
	if(L.elem){          //判斷線性表是否為空的前提是線性表存在，當(dāng)首元素地址即L.elem存在時(shí)說(shuō)明線性表存在 
		if(L.length != 0){               //如果線性表中元素為0，即L.length的值為0時(shí)說(shuō)明線性表是空表 
		       printf("線性表不是空表\n");
		       return FALSE;
			}
			else
			   printf("線性表是空表\n");
		return TRUE;
	}
	else
	printf("線性表不存在，無(wú)法判斷\n");
	return OK;
}

//獲取線性表的長(zhǎng)度
Status ListLength_Sq(SqList L){
	if(L.elem){              //判斷當(dāng)前線性表存在
		int K;
		K = L.length;        //將線性表的元素個(gè)數(shù)賦值給K
		printf("線性表長(zhǎng)度為%d\n",K);
		return OK;
	}
	else
		printf("線性表不存在，無(wú)法判斷\n");
	return OK;
}

//獲取線性表某一位置對(duì)應(yīng)的元素
Status GetElem_Sq(SqList L,int index){
	int Num;
	if(index <= 0 || index > L.length){              //如果要獲取元素的位置是否出界 
		printf("請(qǐng)輸入一個(gè)有效的數(shù)字\n");
		return ERROR;
	}
	else
	Num = L.elem[index - 1];
	printf("第%d個(gè)位置的元素為：%d\n",index,Num);
	return OK;
} 

//在線性表某一位置插入元素
Status ListInsert_Sq(SqList &L,int i,ElemType e){
	ElemType *newbase;
	int *q,*p; 
	if(i < 1 || i > L.length+1)         //判斷插入位置的index值是否合法
	    return ERROR;
	if(L.length >= L.listsize){         //如果當(dāng)前線性表存儲(chǔ)空間已滿，增加分配
		newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)  {                 //如果存儲(chǔ)空間分配失敗，則執(zhí)行異常退出
			printf("存儲(chǔ)空間分配失敗\n");
			exit(OVERFLOW);
		}
		L.elem = newbase;               //新的存儲(chǔ)空間基址
		L.listsize += LISTINCREMENT;
	}
	q = &(L.elem[i-1]);                 //L.elem[index-1]為數(shù)組中的最后一個(gè)元素，q為要插入的位置 
	for(p = &(L.elem[L.length - 1]);p >= q;--p)
	    *(p+1) = *p;                    //要插入位置以及之后的位置向后移 
	*q = e;                             //將e插入到想要插入的位置 
	++L.length;                         //插入新的元素之后表長(zhǎng)加1 
	printf("元素插入成功\n");
	return OK;
}

		printf("存儲(chǔ)空間分配失敗\n");
		exit(OVERFLOW);
	}
	L.elem = newbase;

//刪除線性表某一位置的元素
Status DeleteList_Sq(SqList &L,int i){
	int *p,*q;
	if(i < 1 || i > L.length){            //如果要?jiǎng)h除的位置不合法
		printf("請(qǐng)輸入一個(gè)有效數(shù)字\n");
		return ERROR;
	} 
	p = &(L.elem[i - 1]);                 //p為被刪除元素的位置
	q = L.elem + L.length - 1;            //將表尾元素的位置賦值給q
	for(++p;p <= q;p++)
	    *(p - 1) = *p;                    //被刪除的元素之后的元素全部左移 
	--L.length;                           //表長(zhǎng)減1 
	printf("第%d個(gè)元素刪除成功\n",i);
	return OK;
}

//求線性表某一元素的前驅(qū)
Status PriorElem_Sq(SqList L,int i){
	int K;
	if(L.elem){          //判斷線性表是否為空的前提是線性表存在，當(dāng)首元素地址即L.elem存在時(shí)說(shuō)明線性表存在
	    if(i <= 1 || i > L.length + 1)              //判斷輸入的i值是否合法 
	        printf("請(qǐng)輸入一個(gè)有效數(shù)字\n");
		K = L.elem[i - 2];        //將第i個(gè)元素的前一個(gè)元素賦值給K
		printf("第%d個(gè)位置的直接前驅(qū)為：%d\n",i,K); 
	}
	else
		printf("線性表不存在，無(wú)法判斷\n");
	return OK;
} 

//求線性表某一元素的后繼 
Status NextElem_Sq(SqList L,int i){
	int K;
	if(L.elem){          //判斷線性表是否為空的前提是線性表存在，當(dāng)首元素地址即L.elem存在時(shí)說(shuō)明線性表存在
	    if(i <= 1 || i > L.length - 1)              //判斷輸入的i值是否合法
	        printf("請(qǐng)輸入一個(gè)有效數(shù)字\n");
		K = L.elem[i];        //將第i個(gè)元素的后一個(gè)元素賦值給K
		printf("第%d個(gè)位置的直接后繼為：%d\n",i,K);
	}
	else
		printf("線性表不存在，無(wú)法判斷\n");
	return OK;
} 

//打印線性表
Status PrintList_Sq(SqList L){
	printf("當(dāng)前線性表的元素為：");
	for(int K = 0;K < L.length;K++)      //遍歷當(dāng)前線性表
	    printf("  %d",L.elem[K]);
	printf("\n");                        //換行
	return OK;
} 

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

//函數(shù)結(jié)果狀態(tài)代碼 
#define TRUE     1     //代碼中出現(xiàn)TRUE相當(dāng)于出現(xiàn)了1
#define FALSE    0     //出現(xiàn)FALSE相當(dāng)于出現(xiàn)了0
#define OK       1     //出現(xiàn)OK相當(dāng)于出現(xiàn)了1
#define ERROR    0     //出現(xiàn)ERROR相當(dāng)于出現(xiàn)了0
#define INFEASIBLE    -1
#define OVERFLOW      -2

typedef int Status;
typedef int ElemType;

#define LIST_INIT_SIZE    100     //線性表存儲(chǔ)空間的初始分配量
#define LISTINCREMENT     10      //線性表存儲(chǔ)空間的分配增量

typedef struct{
	ElemType *elem;          //存儲(chǔ)空間的基址
	int length;              //當(dāng)前線性表的長(zhǎng)度
	int listsize;            //當(dāng)前線性表的存儲(chǔ)容量
}SqList;

//構(gòu)造一個(gè)空的線性表
Status InitList_Sq(SqList &L){
	L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));      //L.elem為首元素的地址 
	if(!L.elem){            //如果存儲(chǔ)空間分配失敗，L.elem為NULL
	printf("存儲(chǔ)空間分配失敗\n");
	exit(OVERFLOW);
	}
	L.length = 0;            //當(dāng)前線性表為空表，即線性表長(zhǎng)度為0
	L.listsize = LIST_INIT_SIZE;           //給線性表分配初始容量
	printf("一個(gè)空的線性表已經(jīng)構(gòu)建成功\n");      //輸出空線性表構(gòu)建成功的提示消息 
	return OK;
}

//對(duì)線性表進(jìn)行賦值
Status ValueList_Sq(SqList &L){
	int i,j;
	printf("請(qǐng)輸入線性表元素的個(gè)數(shù)：");
	scanf("%d",&i);
	if(i > L.listsize)                     //如果當(dāng)要輸入的元素個(gè)數(shù)大于內(nèi)存大小時(shí) 
	{
		while(1)             //一直開(kāi)辟新空間，直到開(kāi)辟的空間大于需要的空間為止
		{
			if(i > L.listsize){
				L.elem = (ElemType *)realloc(L.elem,LISTINCREMENT * sizeof(ElemType));
				L.listsize += LISTINCREMENT;
        /*realloc()函數(shù)：重新分配空間
		           參數(shù)：原空間基址，現(xiàn)需空間大小
		           返回：1.成功：新空間地址(本質(zhì)上是一個(gè)數(shù)值)
		                 2.失?。篘ull
	    */
			}
			else
			break;
		}
	}
	for(j = 0;j < i;j++){
		printf("請(qǐng)輸入第%d個(gè)元素：",j + 1);
	    scanf("%d",&L.elem[j]);
	} 
	L.length = i;          //賦值完成后，修改并保存線性表的長(zhǎng)度 
	printf("賦值成功\n");
	return OK;
}

//對(duì)線性表進(jìn)行銷毀
Status DistoryList_Sq(SqList &L){
	if(!L.elem){
	  printf("您還未建立線性表，請(qǐng)先建立線性表\n");
	  return ERROR;
	}
	free(L.elem);            //使用free函數(shù)，將之前動(dòng)態(tài)分配的內(nèi)存還給系統(tǒng) 
	L.elem = NULL;           //重置elem的值為Null 
	L.length = 0;            //將線性表的元素個(gè)數(shù)重置為0
	L.listsize = 0;          //將線性表的存儲(chǔ)容量重置為0 
	printf("線性表已經(jīng)銷毀\n"); 
	return OK;
}

//對(duì)線性表進(jìn)行重置
Status ClearList_Sq(SqList &L){
	if(L.elem){                  //如果線性表存在 
	    L.length = 0;            //將線性表的元素個(gè)數(shù)重置為0
	    printf("線性表已重置\n");
	    return OK;
	}
	else
	printf("線性表不存在，無(wú)法重置\n");
	return OK;
}

//判斷線性表是否為空
Status ListEmpty_Sq(SqList L){
	if(L.elem){          //判斷線性表是否為空的前提是線性表存在，當(dāng)首元素地址即L.elem存在時(shí)說(shuō)明線性表存在
		if(L.length != 0){               //如果線性表中元素為0，即L.length的值為0時(shí)說(shuō)明線性表是空表
		       printf("線性表不是空表\n");
		       return FALSE; 
			}
			else
			   printf("線性表是空表\n");
		return TRUE;
	}
	else
	printf("線性表不存在，無(wú)法判斷\n");
	return OK; 
}

//獲取線性表的長(zhǎng)度
Status ListLength_Sq(SqList L){
	if(L.elem){              //判斷當(dāng)前線性表存在 
		int K;
		K = L.length;        //將線性表的元素個(gè)數(shù)賦值給K
		printf("線性表長(zhǎng)度為%d\n",K);
		return OK;
	}
	else
		printf("線性表不存在，無(wú)法判斷\n");
	return OK;
}

//獲取線性表某一位置對(duì)應(yīng)的元素
Status GetElem_Sq(SqList L,int index){
	int Num;
	if(index <= 0 || index > L.length){              //如果要獲取元素的位置是否出界 
		printf("請(qǐng)輸入一個(gè)有效的數(shù)字\n");
		return ERROR;
	}
	else
	Num = L.elem[index - 1];
	printf("第%d個(gè)位置的元素為：%d\n",index,Num);
	return OK;
} 

//在線性表某一位置插入元素
Status ListInsert_Sq(SqList &L,int i,ElemType e){
	ElemType *newbase;
	int *q,*p;
	if(i < 1 || i > L.length+1)         //判斷插入位置的index值是否合法
	    return ERROR;
	if(L.length >= L.listsize){         //如果當(dāng)前線性表存儲(chǔ)空間已滿，增加分配
		newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)  {                 //如果存儲(chǔ)空間分配失敗，則執(zhí)行異常退出
			printf("存儲(chǔ)空間分配失敗\n");
			exit(OVERFLOW);
		}
		L.elem = newbase;               //新的存儲(chǔ)空間基址
		L.listsize += LISTINCREMENT; 
	}
	q = &(L.elem[i-1]);                 //L.elem[index-1]為數(shù)組中的最后一個(gè)元素，q為要插入的位置
	for(p = &(L.elem[L.length - 1]);p >= q;--p)
	    *(p+1) = *p;                    //要插入位置以及之后的位置向后移
	*q = e;                             //將e插入到想要插入的位置
	++L.length;                         //插入新的元素之后表長(zhǎng)加1
	printf("元素插入成功\n");
	return OK;
}

//打印線性表
Status PrintList_Sq(SqList L){
	printf("當(dāng)前線性表的元素為：");
	for(int K = 0;K < L.length;K++)      //遍歷當(dāng)前線性表
	    printf("  %d",L.elem[K]);
	printf("\n");                        //換行
	return OK;
} 

//刪除線性表某一位置的元素
Status DeleteList_Sq(SqList &L,int i){
	int *p,*q;
	if(i < 1 || i > L.length){            //如果要?jiǎng)h除的位置不合法
		printf("請(qǐng)輸入一個(gè)有效數(shù)字\n"); 
		return ERROR;
	} 
	p = &(L.elem[i - 1]);                 //p為被刪除元素的位置
	q = L.elem + L.length - 1;            //將表尾元素的位置賦值給q
	for(++p;p <= q;p++)
	    *(p - 1) = *p;                    //被刪除的元素之后的元素全部左移
	--L.length;                           //表長(zhǎng)減1
	printf("第%d個(gè)元素刪除成功\n",i);
	return OK;
}

//求線性表某一元素的前驅(qū)
Status PriorElem_Sq(SqList L,int i){
	int K;
	if(L.elem){          //判斷線性表是否為空的前提是線性表存在，當(dāng)首元素地址即L.elem存在時(shí)說(shuō)明線性表存在
	    if(i <= 1 || i > L.length + 1)              //判斷輸入的i值是否合法 
	        printf("請(qǐng)輸入一個(gè)有效數(shù)字\n");
		K = L.elem[i - 2];        //將第i個(gè)元素的前一個(gè)元素賦值給K
		printf("第%d個(gè)位置的直接前驅(qū)為：%d\n",i,K);
	}
	else
		printf("線性表不存在，無(wú)法判斷\n");
	return OK;
}

//求線性表某一元素的后繼
Status NextElem_Sq(SqList L,int i){
	int K;
	if(L.elem){          //判斷線性表是否為空的前提是線性表存在，當(dāng)首元素地址即L.elem存在時(shí)說(shuō)明線性表存在
	    if(i <= 1 || i > L.length - 1)              //判斷輸入的i值是否合法 
	        printf("請(qǐng)輸入一個(gè)有效數(shù)字\n");
		K = L.elem[i];        //將第i個(gè)元素的后一個(gè)元素賦值給K
		printf("第%d個(gè)位置的直接后繼為：%d\n",i,K);
	}
	else
		printf("線性表不存在，無(wú)法判斷\n");
	return OK;
} 

int main(){
	SetConsoleTitle("Dream_飛翔");
	SqList L;
	int choose,index,e;
	while(1){
		printf("*****************************************\n");
		printf("*                                       *\n");
		printf("*  線性表的順序表示和實(shí)現(xiàn)：             *\n");
		printf("*                                       *\n");
		printf("*    1.  構(gòu)造一個(gè)空的線性表             *\n");
		printf("*    2.  對(duì)線性表進(jìn)行賦值               *\n");
		printf("*    3.  對(duì)線性表進(jìn)行銷毀               *\n");
		printf("*    4.  對(duì)線性表進(jìn)行重置               *\n"); 
		printf("*    5.  判斷線性表是否為空             *\n");
		printf("*    6.  獲取線性表的長(zhǎng)度               *\n");
		printf("*    7.  獲取線性表某一位置對(duì)應(yīng)的元素   *\n");
		printf("*    8.  在線性表某一位置插入元素       *\n");
		printf("*    9.  刪除線性表某一位置的元素       *\n");
		printf("*    10. 求線性表某一元素的前驅(qū)         *\n");
		printf("*    11. 求線性表某一元素的后繼         *\n");
		printf("*    12. 打印線性表                     *\n");
		printf("*    13. 退出                           *\n");
		printf("*                                       *\n");
		printf("*****************************************\n");
		printf("請(qǐng)做出您的選擇：");
		scanf("%d",&choose);
		switch(choose){
			case 1:InitList_Sq(L);break;
			case 2:ValueList_Sq(L);break;
			case 3:DistoryList_Sq(L);break;
			case 4:ClearList_Sq(L);break;
			case 5:ListEmpty_Sq(L);break;
			case 6:ListLength_Sq(L);break;
			case 7:{
				printf("請(qǐng)輸入要獲取元素的位置：");
				scanf("%d",&index);
				GetElem_Sq(L,index);
			}
			break;
			case 8:{
				printf("請(qǐng)輸入要插入元素的位置：");
				scanf("%d",&index);
				printf("請(qǐng)輸入要插入的元素：");
				scanf("%d",&e);
				ListInsert_Sq(L,index,e);
			}
			break;
			case 9:{
				printf("請(qǐng)輸入要?jiǎng)h除元素的位置：");
				scanf("%d",&index);
				DeleteList_Sq(L,index);
			}
			break;
			case 10:{
				printf("請(qǐng)輸入想要查找哪一個(gè)元素的前驅(qū)：");
				scanf("%d",&index);
				PriorElem_Sq(L,index);
			}
			break;
			case 11:{
				printf("請(qǐng)輸入想要查找哪一個(gè)元素的后繼：");
				scanf("%d",&index);
				NextElem_Sq(L,index);
			}
			break; 
			case 12:PrintList_Sq(L);break;
			case 13:exit(0);
		}
	}
	return 0;
}