//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :2  (2_2)                   *
//*PROGRAM          :鏈式結構的線性表           *
//*CONTENT          :生成,插入,刪除,定位,查找   *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <conio.h>
#include <dos.h>
#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(LNode)  //定義LEN為一個節點的長度
enum BOOL{False,True};  //定義BOOL型
typedef struct node
{char data;    //數據域
 struct node *next;//指向下一個節點的指針
}LNode,*LinkList;
void CreatList(LinkList &,int);   //生成一個單鏈表
BOOL ListInsert(LinkList &,int,char); //在單鏈表中插入一個元素
BOOL ListDelete(LinkList &,int,char &); //在單鏈表中刪除一個元素
BOOL ListFind_keyword(LinkList,char,int &); //按關鍵字查找一個元素
BOOL ListFind_order(LinkList,char &,int);  //按序號查找一個元素
void ListPrint(LinkList);      //顯示單鏈表所有元素
void main()
{LinkList L;
 BOOL temp;
 int num,loc,flag=1;
 char j,ch;
 textbackground(3); //設置屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------程序解說-----------------------
 printf("本程序實現鏈式結構的線性表的操作。\n");
 printf("可以進行插入，刪除，定位，查找等操作。\n");
 //----------------------------------------------------
 printf("請輸入初始時鏈表長度:"); //輸入生成單鏈表時的元素個數
 scanf("%d",&num);
 CreatList(L,num);      //生成單鏈表
 ListPrint(L);          
 while(flag)
    { printf("請選擇:\n");
      printf("1.顯示所有元素\n");  //顯示鏈表元素
      printf("2.插入一個元素\n");  //插入鏈表元素
      printf("3.刪除一個元素\n");  //刪除鏈表元素
      printf("4.按關鍵字查找元素\n");  //按關鍵字查找
      printf("5.按序號查找元素\n"); //按序號查找
      printf("6.退出程序      \n");  //退出
      scanf(" %c",&j);
      switch(j)
	{case '1':ListPrint(L); break;
	 case '2':{printf("請輸入元素(一個字符)和要插入的位置:\n");
		   printf("格式:字符，位置；例如:a,3\n");
		   scanf(" %c,%d",&ch,&loc);       //輸入要插入的元素和要插入的位置
		   temp=ListInsert(L,loc,ch);      //插入
		   if(temp==False) printf("插入失敗!\n"); //插入失敗
		   else printf("插入成功!\n"); //成功插入
		   ListPrint(L);
		   break;
		  }
	 case '3':printf("請輸入要刪除的元素所在位置:");
		  scanf("%d",&loc);              //輸入要刪除的節點的位置
		  temp=ListDelete(L,loc,ch);    //刪除
		  if(temp==False) printf("刪除失敗!\n"); //刪除失敗
		  else printf("成功刪除了一個元素:%c\n",ch);   //刪除成功，顯示該元素
		  ListPrint(L);
		  break;
	 case '4':if(L->next==NULL)                   //鏈表為空
		     printf("鏈表為空!\n");
		  else{printf("請輸入要查找的元素(一個字符):");
		       scanf(" %c",&ch);                //輸入要查找的元素
		       temp=ListFind_keyword(L,ch,loc); //按關鍵字查找
		       if(temp==False) printf("沒有找到該元素!\n"); //查找失敗
		       else printf("該元素在鏈表的第%d個位置。\n",loc); 
                                           //成功查找，顯示該元素位置
		      }
		  break;
	 case '5':if(L->next==NULL)                   //鏈表為空
		     printf("鏈表為空!\n");
		  else{printf("請輸入要查找的位置:");
		       scanf("%d",&loc);    //輸入要查找的元素的位置
		       temp=ListFind_order(L,ch,loc); //按序號查找
		       if(temp==False) printf("該位置不存在!\n"); //查找失敗
		       else printf("第%d個元素是：%c\n",loc,ch);
                                //成功查找，顯示該元素
		      }
		  break;
	 default:flag=0;printf("程序結束，按任意鍵退出!\n");
	}
    }
getch();
}
void CreatList(LinkList &v,int n)
{//生成一個帶頭結點的有n個元素的單鏈表 
 int i;
 LinkList p;
 v=(LinkList)malloc(LEN); //生成頭結點
 v->next=NULL;
 printf("請輸入%d個字符：例如：abcdefg\n",n);
 getchar();
 for(i=n;i>0;--i)
    {p=(LinkList)malloc(LEN); //生成新結點
     scanf("%c",&p->data);
     p->next=v->next;
     v->next=p;
    }
}
BOOL ListInsert(LinkList &v,int i,char e)
{//在單鏈表的第i各位置插入元素e，成功返回True，失敗返回False
 LinkList p,s;
 int j=0;
 p=v;
 while(p&&j<i-1) {p=p->next;++j;} //查找第i-1個元素的位置
 if(!p||j>i-1) return False;  //沒有找到
 s=(LinkList)malloc(LEN);     //生成一個新結點     
 s->data=e;            
 s->next=p->next;        //將新結點插入到單鏈表中 
 p->next=s;
 return True;
}

BOOL ListDelete(LinkList &v,int i,char &e)
{//在單鏈表中刪除第i個元素，成功刪除返回True，并用e返回該元素值，失敗返回False
 LinkList p,q;
 int j=0;
 p=v;
 while(p->next&&j<i-1)  //查找第i-1個元素位置
    {p=p->next;++j;}
 if(!(p->next)||j>i-1) return False; //查找失敗
 q=p->next;p->next=q->next; //刪除該元素    
 e=q->data;         //e取得該元素值
 free(q);           //釋放該元素空間
 return True;
}

BOOL ListFind_keyword(LinkList v,char e,int &i)
{//在單鏈表中查找關鍵字為e的元素，成功返回True,并用i返回該元素位置，
 //失敗返回False
 i=1;
 LinkList p;
 p=v->next;
 while((p->data!=e)&&(p->next!=NULL))//p指針指向下一個，直到
    {p=p->next;  i++;}                        //找到或到鏈表尾為止
 if(p->data!=e)                      //該元素在鏈表中不存在
     return False;
 else return True;
}

BOOL ListFind_order(LinkList v,char &e,int i)
{//在單鏈表中查找第i個元素，成功返回True，并用e返回該元素值，
 //失敗返回False
 LinkList p;
 int j=0;
 p=v;
 while(p->next&&j<i)  //移動指針，直到找到第i個元素
    {p=p->next;++j;}
 if(j!=i) return False; //查找失敗
 else {e=p->data;       //查找成功，用e取得該元素值
       return True;
      }
}
void ListPrint(LinkList v)   
{//顯示鏈表所有元素
 LinkList q;
 q=v->next;
 printf("鏈表所有元素:");
 while(q!=NULL)
   {printf("%c ",q->data);q=q->next;}
 printf("\n");
}