#include<iostream.h>
#include<stdio.h>
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode, *LinkList;                 //線(xiàn)性單鏈表的存儲(chǔ)結(jié)構(gòu)



int ListInsert_L(LinkList &L,int i,int e)   //在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元素e
{LinkList p,s;
p=L; int j=0;
cout<<"請(qǐng)輸入您想要插入的整數(shù)元素:";
cin>>e;
cout<<"請(qǐng)輸入您想要插入的位置";
cin>>i;
while(p&&j<i-1){p=p->next;++j;}        //尋找第i-1個(gè)結(jié)點(diǎn)
if(!p||j>i-1)                          //i小于1或者大于表長(zhǎng)+1
{cout<<"插入的位置不合適，請(qǐng)重新輸入";} 
else 
{s=(LinkList)new int(sizeof(LNode));    //生成新結(jié)點(diǎn)
s->data=e; s->next=p->next;            //插入L中
p->next=s;
cout<<"經(jīng)插入后現(xiàn)在鏈表中的元素為:";
for(p=L->next;p!=NULL;p=p->next)
cout<<p->data<<"  ";}
cout<<endl<<endl<<endl;
return L,i,e;}




int ListLocate_L(LinkList L,int x)      //在帶頭結(jié)點(diǎn)的單鏈表L中查找與x相等的所有元素的位序
{int i,count=0; LinkList p;
p=L->next; i=1;                    //i的初值為第一個(gè)元素的位序
                                   //p的初值為第一個(gè)結(jié)點(diǎn)的位序
cout<<"請(qǐng)輸入您想要查找的整數(shù)元素的值:"<<endl;
cin>>x;

while(p!=NULL&&p->data!=x)         //尋找數(shù)據(jù)域的值為x的結(jié)點(diǎn)
{p=p->next; i++;}
if(!p){cout<<"Not Found!"<<endl;}  //沒(méi)有找到，顯示NOT FOUND
else
{for(p;p!=NULL;p=p->next)        //從找到的第一個(gè)滿(mǎn)足要求的結(jié)點(diǎn)起，繼續(xù)往后進(jìn)行尋找滿(mǎn)足要求的其他結(jié)點(diǎn)
if(p->data==x)
{cout<<"您要查找的元素存在！它在鏈表中的位置是:"<<i<<endl<<endl<<endl;i++;count++;}
else i++;
cout<<"您查找到的滿(mǎn)足要求的元素一共有"<<count<<"個(gè)"<<endl<<endl<<endl;
}//所有與x相等的元素都已經(jīng)找到，顯示其所有結(jié)點(diǎn)所在的鏈表中的位置


return L,x;
}



int ListDelete_L(LinkList &L, int i, int &e)   //在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個(gè)元素，并由e返回其值
{LinkList p,q; int j=0;
p=L;
cout<<"請(qǐng)輸入您想要?jiǎng)h除的元素的位置:";
cin>>i;
while(p->next&&j<i-1)                     //尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū)
{p=p->next; ++j;}
if(!(p->next)||j>i-1)
cout<<"您輸入的位置有誤，請(qǐng)重新輸入";        //刪除的位置不合理
else
{q=p->next; p->next=q->next; e=q->data; delete(q);   //刪除并釋放結(jié)點(diǎn)
 cout<<"刪除已經(jīng)完成！現(xiàn)在鏈表中的元素為:";
for(p=L->next;p!=NULL;p=p->next)
cout<<p->data<<"  ";}               //顯示刪除完畢后的單鏈表
cout<<endl<<endl<<endl;
return L,i,e;
}




main()                 //順位序輸入10個(gè)元素的值，建立帶表頭結(jié)點(diǎn)的單鏈線(xiàn)性表L
{
	LinkList L;
	LinkList p;
	LinkList q;
	int e,x;
	L=(LinkList)new int(sizeof(LNode));
	L->next=NULL;                //先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表
	q=L;
	cout<<"請(qǐng)輸入任意10個(gè)整數(shù):"<<endl; 
	for(int i=0;i<10;i++) 
	{p=(LinkList)new int(sizeof(LNode));  //生成10個(gè)新結(jié)點(diǎn)
	cin>>p->data;                       //輸入元素的值
	p->next=q->next;                    //插入結(jié)點(diǎn)
	q->next=p;q=p;}
	cout<<"單鏈表已經(jīng)建立成功，現(xiàn)在表中的10個(gè)數(shù)據(jù)分別是:";
	for(p=L->next;p!=NULL;p=p->next)
	{cout<<p->data<<"  ";}          //輸出建立成功后的單鏈表
	cout<<endl;
    while(L->next!=NULL)           //L不為空時(shí)，可執(zhí)行以下操作
	{cout<<"請(qǐng)選擇1、2、3、4四個(gè)數(shù)字選擇您想要執(zhí)行的操作:"<<endl<<"1、查找" <<endl<<"2、插入"<<endl<<"3、刪除"<<endl<<"4、不需要再進(jìn)行操作，退出程序"<<endl;
	cout<<"請(qǐng)選擇:";
	int n;                         //根據(jù)選擇，對(duì)單鏈表進(jìn)行查找、插入和刪除操作
	cin>>n;                        
	if(n==1)
	ListLocate_L(L,x);             //對(duì)單鏈表執(zhí)行查找操作
	if(n==2)                       
	ListInsert_L(L,i,e);           //對(duì)單鏈表執(zhí)行插入操作
	if(n==3)
	ListDelete_L(L,i,e);           //對(duì)單鏈表執(zhí)行刪除操作
	if(n==4)                       //不對(duì)單鏈表執(zhí)行任何操作
	return 0; }
	cout<<"該鏈表中的元素已經(jīng)都被刪除完，不再執(zhí)行任何操作！"<<endl;
}