#include<iostream.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct LNode{
   char data;
   LNode *next;
}LNode,*LinkList;



void showmenu(){   //功能列表      
cout<<endl <<"   **********功能**********"<<endl
<<"   * 1.輸出單鏈表的全部數據*"<<endl
<<"   * 2.查找鏈表元素      *"<<endl
<<"   * 3.鏈表插入元素      *"<<endl
<<"   * 4.鏈表刪除元素      *"<<endl
<<"   * 5.結束              *"<<endl
<<"   ************************"<<endl
<<"請輸入所需功能: ";
}

//*******查看輸入的全部數據*********   
void PrintList(LinkList L){
LinkList p;          
cout<<endl<<"你輸入的數據為: "; 
p=L->next;           //從頭結點開始掃描
while(p){     //順指針向后掃描，直到p->next為NULL或i=j為止
cout<<p->data;                        
p=p->next; }   
cout<<endl; }

//逆序輸入 n 個數據元素，建立帶頭結點的單鏈表
void CreateList_L(LinkList &L, int n) {
int i;
LinkList p;
L = new LNode;    
L->next = NULL;      // 先建立一個帶頭結點的單鏈表
cout<<"逆序輸入 n 個數據元素，建立帶頭結點的單鏈表"<<endl;
for (i = n; i > 0; --i) {
    p = new LNode;
    cin>>p->data;    // 輸入元素值
    p->next = L->next; L->next = p; // 插入
}
}

// L是帶頭結點的鏈表的頭指針，以 e 返回第 i 個元素
int GetElem_L(LinkList L, int i, char &e) {
int j;
LinkList p;
p = L->next;   j = 1; // p指向第一個結點，j為計數器
while (p && j<i) { p = p->next; ++j; }    // 順指針向后查找，直到 p 指向第 i 個元素或 p 為空
if ( !p || j>i )
    return ERROR;      // 第 i 個元素不存在
e = p->data;                 // 取得第 i 個元素
return OK;
}

// 本算法在鏈表中第i 個結點之前插入新的元素 e
int ListInsert_L(LinkList L, int i, ElemType e) {
int j;
LinkList p,s;
p = L;    j = 0;
while (p && j < i-1) 
     { p = p->next; ++j; }   // 尋找第 i-1 個結點
if (!p || j > i-1)
      return ERROR;      // i 大于表長或者小于1 
s = new LNode;      // 生成新結點
if ( s == NULL) return ERROR;
s->data = e; 
s->next = p->next;      p->next = s; // 插入
return OK;
}

int ListDelete_L(LinkList L, int i, char &e) 
{LinkList p,q;
int j;
p = L;    j = 0;
while (p->next && j < i-1) { p = p->next;   ++j; } 
                           // 尋找第 i 個結點，并令 p 指向其前趨

if (!(p->next) || j > i-1) 
    return ERROR; // 刪除位置不合理
q = p->next;   p->next = q->next; // 刪除并釋放結點
e = q->data;   free(q);
return OK;
}
void main()
{LinkList L;
int n,choice,i;
char e;

cout<<"請輸入鏈表中元素的個數";
cin>>n;
CreateList_L(L, n);
showmenu();   //功能列表   
cin>>choice;        
while(choice!=5)
{ //輸入時候退出程序
switch(choice){
    case 1:PrintList(L);break; //1.查看輸入的全部數據
    case 2:{
     cout<<"輸入你要查找的元素的位置： ";
           cin>>i;GetElem_L(L, i, e);
     cout<<"第"<<i<<"個元素的值是"<<e<<endl;
     break;} //2.查找鏈表元素         
    case 3:
     {cout<<"請輸入你要插入元素的位置i： ";
      cin>>i;
   cout<<endl<<"請輸入你要插入元素的值： ";
   cin>>e;
   ListInsert_L(L, i,e);
      break;}       //3.鏈表插入元素
    case 4:
    {cout<<"請輸入你要刪除元素的位置";
     cin>>i;
     ListDelete_L(L, i, e) ;
     break;} //4.鏈表刪除元素
    default:cout<<"輸入錯誤,請輸入-5,輸入重顯示功能表^_^ "<<endl;
}
cout<<endl<<"輸入功能序號:";    
cin>>choice;
}

}