#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;    //定義函數(shù)的返回狀態(tài) 
typedef int ElemType; 

typedef struct LNode{
	ElemType  data;               //數(shù)據(jù)域 
	struct LNode * next;          //指針域,指向一整個(gè)結(jié)點(diǎn)(結(jié)構(gòu)體,該結(jié)構(gòu)體中包含數(shù)據(jù)域和指針域) 
}LNode , * LinkList;        

//構(gòu)造一個(gè)空的頭結(jié)點(diǎn)
Status InitList_L(LinkList &L){     
	L = (LinkList)malloc(sizeof(LNode));      //產(chǎn)生頭結(jié)點(diǎn)，并使L指向該頭結(jié)點(diǎn)(L也稱頭指針)
	if(!L)  return ERROR;          //如果存儲(chǔ)空間分配失敗，返回ERROR
	L->next = NULL;                //將指針域賦值為NULL
	printf("空的頭結(jié)點(diǎn)創(chuàng)建成功\n");
	return OK; 
} 

//對(duì)線性表進(jìn)行賦值 
Status ValueList_L(LinkList &L,ElemType e){
	LinkList s,p;
	p = L;  
	while(p->next){
		p = p->next;
	}
	s = (LinkList)malloc(sizeof(LNode));       //生成一個(gè)新結(jié)點(diǎn) 
	s->data = e;                 //將e賦值給新結(jié)點(diǎn)的數(shù)據(jù)域 
	s->next = p->next;           //將新結(jié)點(diǎn)與后一個(gè)結(jié)點(diǎn)的地址連接
	p->next = s;
	return OK; 
}

	p = p->next;
}

//對(duì)線性表進(jìn)行銷毀
Status DistoryList_L(LinkList &L) { 
	if(!L){            //如果線性表不存在，返回ERROR 
		printf("線性表不存在\n");
		return ERROR;
	}
	LinkList q = L->next;    //使q指向單鏈表的首元結(jié)點(diǎn)  
	while(q != NULL){     //當(dāng)q結(jié)點(diǎn)不為空時(shí)一直進(jìn)入循環(huán) 
		free(L);          //釋放L結(jié)點(diǎn) 
		L = q;            //將q結(jié)點(diǎn)賦值給L結(jié)點(diǎn) 
		q = L->next;      //將q結(jié)點(diǎn)賦值給L結(jié)點(diǎn)以后使q結(jié)點(diǎn)指向L的下一個(gè)結(jié)點(diǎn) 
	} 
	free(L);    //此時(shí)q的值為NULL，L指向尾結(jié)點(diǎn)，將其釋放
	L = NULL;   
	printf("線性表已銷毀\n"); 
}

//對(duì)線性表進(jìn)行重置
Status ClearList_L(LinkList &L)
{
	if(!L->next){
		printf("線性表為空表，不需要重置\n");
		return ERROR;
	}
	LinkList p,q;
	p = L->next;          //將單鏈表的頭結(jié)點(diǎn)賦值給p
	while(p){
		q = p->next;      //將單鏈表的首元結(jié)點(diǎn)賦值給q
		free(p);
		p = q;
	} 
	L->next = NULL;     //將頭結(jié)點(diǎn)的指針域賦值為空 
	printf("線性表已重置\n");
	return OK;
} 

//判斷線性表是否為空
Status ListEmpty_L(LinkList L)
{
	if(L){
		if(L->next == NULL)       //如果首元結(jié)點(diǎn)不存在 
	    printf("線性表是空表\n");
	    else
	    printf("線性表不是空表\n");
	}
	else{
	printf("線性表不存在，無法判斷\n");	
	}
	return OK;
}

//獲取線性表的長(zhǎng)度
Status ListLength_L(LinkList L,int count)
{
	//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，count為計(jì)數(shù)器
	LinkList p = L->next;    //定義p為單鏈表L的指針域 
	while(p){
		p = p->next;
		count++;
	}
	return count;
}

//獲取線性表某一位置對(duì)應(yīng)的元素
Status GetElem_L(LinkList L,int index)
{
	LinkList p;
	p = L->next;       //使p指向L的首元結(jié)點(diǎn)
	int  count = 1;    //count為計(jì)數(shù)器 ，賦值等于1的原因是從首元結(jié)點(diǎn)開始計(jì)數(shù) 
	while(p && count < index){    //順著指針向后查找，直到p指向第index個(gè)元素或p為空 
		p = p->next;
		count++;        //此時(shí)p一直指向第count個(gè)元素 
	}
	if(!p || count > index){
		printf("當(dāng)前位置沒有元素\n");
		return ERROR;
	}
	printf("第%d個(gè)元素的值是：%d\n",index,p->data);
	return OK;
}

//在線性表某一位置插入元素
Status ListInsert_L(LinkList &L,int index,ElemType e)
{
	LinkList p,q;
	p = L;      //將線性表的頭結(jié)點(diǎn)賦值給p
	int count = 0;    //count為計(jì)數(shù)器 
	while(p && count < index - 1){      //尋找第index-1個(gè)結(jié)點(diǎn) 
		p = p->next;         //此時(shí)的p結(jié)點(diǎn)指向第index-1個(gè)結(jié)點(diǎn) 
		count++; 
	}
	if(!p || count > index -1){        //越界判斷,index小于1或是index大于表長(zhǎng)加1 
		printf("當(dāng)前結(jié)點(diǎn)無法插入元素\n");
		return ERROR;
	}
	q = (LinkList)malloc(sizeof(LNode));
	q->data = e;            //將e賦值到q的數(shù)據(jù)域當(dāng)中
	q->next = p->next;
	p->next = q;
	printf("元素插入成功\n");
	return OK; 
}

//刪除線性表某一位置的元素
Status DeleteList_L(LinkList &L,int index)
{
	LinkList p,q;
	p = L;           //將線性表的頭結(jié)點(diǎn)賦值給p
	int count = 0;   //計(jì)數(shù)器
	while(p->next && count < index - 1){
		p = p->next;
		count++;            //此時(shí)p一直指向第count個(gè)結(jié)點(diǎn) 
	}
	if(!(p->next) || count > index - 1){     //越界判斷 
		printf("當(dāng)前位置無法刪除元素\n");
		return ERROR;
	}
	q = p->next;
	p->next = q->next;
	free(q);
	q = NULL;
	printf("當(dāng)前位置元素已刪除\n");
	return OK;
} 

//求線性表某一元素的前驅(qū) 
Status PriorElem_L(LinkList L,int index)
{
	LinkList p;
	int count = 0;       //count為計(jì)數(shù)器 
	p = L;
	while(p->next && count < index - 1){       //尋找第index-1個(gè)結(jié)點(diǎn) 
		p = p->next;            //p一直指向第count個(gè)結(jié)點(diǎn) 
		count++;
	}
	if(!(p->next) || count > index - 1){       //越界判斷 
		printf("當(dāng)前位置無法求該元素的前驅(qū)\n"); 
		return ERROR;
	}
	if(p != L)            //如果要獲取第一個(gè)元素的前驅(qū)，就是獲取頭結(jié)點(diǎn)數(shù)據(jù)域的值 
	printf("該元素的前驅(qū)為：%d\n",p->data);
	else
	printf("該位置的前驅(qū)是頭結(jié)點(diǎn)\n頭結(jié)點(diǎn)的數(shù)據(jù)域中存儲(chǔ)的值為：%d\n",p->data);
	return OK;
}

//求線性表某一元素的后繼 
Status NextElem_L(LinkList L,int index)
{
	LinkList p;
	int count = 0;
	p = L->next;
	while(p && count < index){        //不斷遍歷尋找第index之后的結(jié)點(diǎn) 
		p = p->next;      //p一直指向index-1的后一個(gè)結(jié)點(diǎn) 
		count++;
	}
	//!p的目的是為了確保i不大于表長(zhǎng)-1，count>index的目的是為了確保index不小于0 
	if(!p || count > index){          //越界判斷
		printf("當(dāng)前位置無法求該元素的后繼\n"); 
		return ERROR;
	}
	printf("該元素的后繼為：%d\n",p->data);
}

//打印線性表
Status PrintList_L(LinkList L)
{
	if(!L){            //如果線性表不存在，返回ERROR 
		printf("線性表不存在，無法打印\n");
		return ERROR;
	}
	LinkList p;
	p = L->next;    //將L的首元結(jié)點(diǎn)賦值給p ,為了不將頭結(jié)點(diǎn)打印出來 
	while(p){
		printf(" %d",p->data);   //將p結(jié)點(diǎn)的數(shù)據(jù)域輸出 
		p = p->next;    //結(jié)點(diǎn)不斷的向后移動(dòng) 
	}
	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;    //定義函數(shù)的返回狀態(tài) 
typedef int ElemType; 

typedef struct LNode{
	ElemType  data;               //數(shù)據(jù)域 
	struct LNode * next;          //指針域,指向一整個(gè)結(jié)點(diǎn)(結(jié)構(gòu)體,該結(jié)構(gòu)體中包含數(shù)據(jù)域和指針域) 
}LNode , * LinkList;        //* LinkList是結(jié)點(diǎn)的類型，在之后的代碼中出現(xiàn)了它就相當(dāng)于出現(xiàn)了指向這個(gè)結(jié)點(diǎn)的指針 

//構(gòu)造一個(gè)空的頭結(jié)點(diǎn) 
Status InitList_L(LinkList &L){     //之前因?yàn)闆]有輸入"&"符號(hào),沒有使用引用傳遞也就意味著沒有開辟了新的內(nèi)存空間，所以在之后賦值的時(shí)候會(huì)出現(xiàn)無法賦值的情況 
	L = (LinkList)malloc(sizeof(LNode));      //產(chǎn)生頭結(jié)點(diǎn)，并使L指向該頭結(jié)點(diǎn)(L也稱頭指針)
	if(!L)  return ERROR;          //如果存儲(chǔ)空間分配失敗，返回ERROR
	L->next = NULL;                //將指針域賦值為NULL,在這里要強(qiáng)調(diào)一點(diǎn)："->"是一個(gè)整體，它是用于指向結(jié)構(gòu)體子數(shù)據(jù)的指針 
	printf("空的頭結(jié)點(diǎn)創(chuàng)建成功\n");
	return OK; 
} 

//對(duì)線性表進(jìn)行賦值 
Status ValueList_L(LinkList &L,ElemType e){
	LinkList s,p;
	p = L;  
	while(p->next){
		p = p->next;
	}
	s = (LinkList)malloc(sizeof(LNode));       //生成一個(gè)新結(jié)點(diǎn) 
	s->data = e;                 //將e賦值給新結(jié)點(diǎn)的數(shù)據(jù)域 
	s->next = p->next;           //將新結(jié)點(diǎn)與后一個(gè)結(jié)點(diǎn)的地址連接
	p->next = s;
	return OK; 
} 

//對(duì)線性表進(jìn)行銷毀
Status DistoryList_L(LinkList &L) {
/*從頭結(jié)點(diǎn)開始逐一釋放，釋放前使p指向頭結(jié)點(diǎn)，q指向開始釋放的結(jié)點(diǎn)
  當(dāng)開始結(jié)點(diǎn)不為空時(shí)，執(zhí)行釋放過程
  先釋放頭結(jié)點(diǎn)，然后將p，q都向后移，依次釋放
  因?yàn)閝始終是p的后繼，所以最后一定是p留到最后，最后釋放p
*/ 
	if(!L){            //如果線性表不存在，返回ERROR 
		printf("線性表不存在\n");
		return ERROR;
	}
	LinkList q = L->next;    //使q指向單鏈表的首元結(jié)點(diǎn)  
	while(q != NULL){     //當(dāng)q結(jié)點(diǎn)不為空時(shí)一直進(jìn)入循環(huán) 
		free(L);          //釋放L結(jié)點(diǎn) 
		L = q;            //將q結(jié)點(diǎn)賦值給L結(jié)點(diǎn) 
		q = L->next;      //將q結(jié)點(diǎn)賦值給L結(jié)點(diǎn)以后使q結(jié)點(diǎn)指向L的下一個(gè)結(jié)點(diǎn) 
	} 
	free(L);    //此時(shí)q的值為NULL，L指向尾結(jié)點(diǎn)，將其釋放
	L = NULL;   //free函數(shù)只是將之前動(dòng)態(tài)分配給L的內(nèi)存歸還給系統(tǒng)，但是指針類型的結(jié)點(diǎn)L仍然存在
	//為了防止之后發(fā)生野指針訪問，將L賦值為NULL 
	printf("線性表已銷毀\n"); 
}

//對(duì)線性表進(jìn)行重置
Status ClearList_L(LinkList &L)
{
	if(!L->next){
		printf("線性表為空表，不需要重置\n");
		return ERROR;
	}
	LinkList p,q;
	p = L->next;          //將單鏈表的頭結(jié)點(diǎn)賦值給p
	while(p){
		q = p->next;      //將單鏈表的首元結(jié)點(diǎn)賦值給q
		free(p);
		p = q;
	} 
	L->next = NULL;     //將頭結(jié)點(diǎn)的指針域賦值為空 
	printf("線性表已重置\n");
	return OK;
} 
 
//判斷線性表是否為空
Status ListEmpty_L(LinkList L)
{
	if(L){
		if(L->next == NULL)       //如果首元結(jié)點(diǎn)不存在 
	    printf("線性表是空表\n");
	    else
	    printf("線性表不是空表\n");
	}
	else{
	printf("線性表不存在，無法判斷\n");	
	}
	return OK;
} 

//獲取線性表的長(zhǎng)度
Status ListLength_L(LinkList L,int count)
{
	//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，count為計(jì)數(shù)器
	LinkList p = L->next;    //定義p為單鏈表L的指針域 
	while(p){
		p = p->next;
		count++;
	}
	return count;
}	

//獲取線性表某一位置對(duì)應(yīng)的元素
Status GetElem_L(LinkList L,int index)
{
	LinkList p;
	p = L->next;       //使p指向L的首元結(jié)點(diǎn)
	int  count = 1;    //count為計(jì)數(shù)器 ，賦值等于1的原因是從首元結(jié)點(diǎn)開始計(jì)數(shù) 
	while(p && count < index){    //順著指針向后查找，直到p指向第index個(gè)元素或p為空 
		p = p->next;
		count++;        //此時(shí)p一直指向第count個(gè)元素 
	}
	if(!p || count > index){
		printf("當(dāng)前位置沒有元素\n");
		return ERROR;
	}
	printf("第%d個(gè)元素的值是：%d\n",index,p->data);
	return OK;
} 

//在線性表某一位置插入元素
Status ListInsert_L(LinkList &L,int index,ElemType e)
{
	LinkList p,q;
	p = L;      //將線性表的頭結(jié)點(diǎn)賦值給p
	int count = 0;    //count為計(jì)數(shù)器 
	while(p && count < index - 1){      //尋找第index-1個(gè)結(jié)點(diǎn) 
		p = p->next;         //此時(shí)的p結(jié)點(diǎn)指向第index-1個(gè)結(jié)點(diǎn) 
		count++; 
	}
	if(!p || count > index -1){        //越界判斷,index小于1或是index大于表長(zhǎng)加1 
		printf("當(dāng)前結(jié)點(diǎn)無法插入元素\n");
		return ERROR;
	}
	q = (LinkList)malloc(sizeof(LNode));
	q->data = e;            //將e賦值到q的數(shù)據(jù)域當(dāng)中
	q->next = p->next;
	p->next = q;
	printf("元素插入成功\n");
	return OK; 
}

//刪除線性表某一位置的元素
Status DeleteList_L(LinkList &L,int index)
{
	LinkList p,q;
	p = L;           //將線性表的頭結(jié)點(diǎn)賦值給p
	int count = 0;   //計(jì)數(shù)器
	while(p->next && count < index - 1){
		p = p->next;
		count++;            //此時(shí)p一直指向第count個(gè)結(jié)點(diǎn) 
	}
	if(!(p->next) || count > index - 1){     //越界判斷 
		printf("當(dāng)前位置無法刪除元素\n");
		return ERROR;
	}
	q = p->next;
	p->next = q->next;
	free(q);
	q = NULL;
	printf("當(dāng)前位置元素已刪除\n");
	return OK;
} 

//求線性表某一元素的前驅(qū) 
Status PriorElem_L(LinkList L,int index)
{
	LinkList p;
	int count = 0;       //count為計(jì)數(shù)器 
	p = L;
	while(p->next && count < index - 1){       //尋找第index-1個(gè)結(jié)點(diǎn) 
		p = p->next;            //p一直指向第count個(gè)結(jié)點(diǎn) 
		count++;
	}
	if(!(p->next) || count > index - 1){       //越界判斷 
		printf("當(dāng)前位置無法求該元素的前驅(qū)\n"); 
		return ERROR;
	}
	if(p != L)            //如果要獲取第一個(gè)元素的前驅(qū)，就是獲取頭結(jié)點(diǎn)數(shù)據(jù)域的值 
	printf("該元素的前驅(qū)為：%d\n",p->data);
	else
	printf("該位置的前驅(qū)是頭結(jié)點(diǎn)\n頭結(jié)點(diǎn)的數(shù)據(jù)域中存儲(chǔ)的值為：%d\n",p->data);
	return OK;
}

//求線性表某一元素的后繼 
Status NextElem_L(LinkList L,int index)
{
	LinkList p;
	int count = 0;
	p = L->next;
	while(p && count < index){        //不斷遍歷尋找第index之后的結(jié)點(diǎn) 
		p = p->next;      //p一直指向index-1的后一個(gè)結(jié)點(diǎn) 
		count++;
	}
	//!p的目的是為了確保i不大于表長(zhǎng)-1，count>index的目的是為了確保index不小于0 
	if(!p || count > index){          //越界判斷
		printf("當(dāng)前位置無法求該元素的后繼\n"); 
		return ERROR;
	}
	printf("該元素的后繼為：%d\n",p->data);
}

//打印線性表
Status PrintList_L(LinkList L)
{
	if(!L){            //如果線性表不存在，返回ERROR 
		printf("線性表不存在，無法打印\n");
		return ERROR;
	}
	LinkList p;
	p = L->next;    //將L的首元結(jié)點(diǎn)賦值給p ,為了不將頭結(jié)點(diǎn)打印出來 
	while(p){
		printf(" %d",p->data);   //將p結(jié)點(diǎn)的數(shù)據(jù)域輸出 
		p = p->next;    //結(jié)點(diǎn)不斷的向后移動(dòng) 
	}
	printf("\n");
	return OK;
}

int main(){
	SetConsoleTitle("Dream_飛翔");              //控制windows終端控制臺(tái)的名稱 
    //system("mode con cols=60 lines=30");        這條語(yǔ)句可以控制windows終端控制臺(tái)的大小 
	LinkList L = NULL;               //聲明線性表的頭結(jié)點(diǎn)，但是并未進(jìn)行初始化 
	int choose,index,e,Num,Value,k;
	while(1){
		printf("*****************************************\n");
		printf("*                                       *\n");
		printf("*  線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)：             *\n");
		printf("*                                       *\n");
		printf("*    1.  構(gòu)造一個(gè)空的頭結(jié)點(diǎn)             *\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_L(L);break;
			case 2:{
				if(L){      //對(duì)線性表賦值的前提是線性表的頭結(jié)點(diǎn)存在 
					printf("請(qǐng)輸入線性表元素的個(gè)數(shù)：");
					scanf("%d",&Num);
					if(Num > 0){
						for(int i = 1;i <= Num;i++){
						printf("請(qǐng)輸入第%d個(gè)元素的值：",i);
						scanf("%d",&Value);
						ValueList_L(L,Value);
						}
					printf("線性表賦值成功\n");
					}
					else
					printf("請(qǐng)輸入一個(gè)有效數(shù)字\n");
				}
				else
				printf("線性表不存在，無法賦值\n"); 
				}
			break;
			case 3:DistoryList_L(L);break;
			case 4:ClearList_L(L);break;
			case 5:ListEmpty_L(L);break;
			case 6:{
				int count = ListLength_L(L,1);
				printf("線性表的長(zhǎng)度為：%d\n",count-1);
			};break;
			case 7:{ 
				printf("請(qǐng)輸入要獲取元素的位置：");
				scanf("%d",&index);
				GetElem_L(L,index); 
			}
			break;
			case 8:{
				printf("請(qǐng)輸入插入元素的位置：");
				scanf("%d",&index);
				printf("請(qǐng)輸入插入元素的值：");
				scanf("%d",&e);
				ListInsert_L(L,index,e);
			}
			break;
			case 9:{
				printf("請(qǐng)輸入要?jiǎng)h除元素的位置：");
				scanf("%d",&index);
				DeleteList_L(L,index);
			}
			break;
			case 10:{
				if(L){
					printf("請(qǐng)輸入想要查找哪一個(gè)元素的前驅(qū)：");
					scanf("%d",&index);
					PriorElem_L(L,index);
				}
				else
				printf("線性表不存在，無法獲取其中元素的前驅(qū)\n");
			}
			break;
			case 11:{
				if(L){
					printf("請(qǐng)輸入想要查找哪一個(gè)元素的后繼：");
					scanf("%d",&index);
					NextElem_L(L,index);
				}
				else
				printf("線性表不存在，無法獲取其中元素的后繼\n");
			}
			break; 
			case 12:PrintList_L(L);break;
			case 13:exit(0);
		}
	}
	return 0;
}