//* * * * * * * * * * * * * * * * * * * * * * *
//CHAPTER      :2 (2-1)                       *
//PROGRAM NAME :順序結構的線性表              *
//CONTENT      :插入,刪除,查找                *
//* * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#define MAX 30    //定義線性表的最大長度
enum BOOL{False,True};  //定義BOOL型
typedef struct{
   char elem[MAX];       //線性表
   int last;             //last指示當前線性表的長度
}sqlisttp;               
void initial(sqlisttp &);    //初始化線性表
BOOL insert(sqlisttp &,int,char); //在線性表中插入元素
BOOL del(sqlisttp&,int,char &);   //在線性表中刪除元素
int locate(sqlisttp,char);        //在線性表中定位元素
void print(sqlisttp);             //顯示線性表中所有元素
void main()
{sqlisttp S;      //S為一線性表
 int loc,flag=1;
 char j,ch;
 BOOL temp;
 textbackground(3);  //設置屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------------程序解說--------------------------
 printf("本程序用來實現順序結構的線性表。\n");
 printf("可以實現查找、插入、刪除等操作。\n");
 //-------------------------------------------------------------
 initial(S);         //初始化線性表
 while(flag)
    { printf("請選擇:\n");
      printf("1.顯示所有元素\n");
      printf("2.插入一個元素\n");
      printf("3.刪除一個元素\n");
      printf("4.查找一個元素\n");
      printf("5.退出程序    \n");
      scanf(" %c",&j);
      switch(j)
	{case '1':print(S); break; //顯示所有元素
	 case '2':{printf("請輸入要插入的元素(一個字符)和插入位置:\n");
		   printf("格式：字符，位置；例如:a,2\n");
		   scanf(" %c,%d",&ch,&loc);  //輸入要插入的元素和插入的位置
		   temp=insert(S,loc,ch);     //插入
		   if(temp==False)  printf("插入失敗!\n");  //插入失敗
                   else  {printf("插入成功!\n");   print(S);} //插入成功
		   break;
		  }
	 case '3':{printf("請輸入要刪除元素的位置:");
		   scanf("%d",&loc);    //輸入要刪除的元素的位置
		   temp=del(S,loc,ch);  //刪除
		   if(temp==True) printf("刪除了一個元素:%c\n",ch); //刪除成功
		   else printf("該元素不存在!\n");  //刪除失敗
		   print(S);
		   break;
		  }
	 case '4':{printf("請輸入要查找的元素:");
		   scanf(" %c",&ch);      //輸入要查找的元素
		   loc=locate(S,ch);      //定位
		   if(loc!=-1) printf("該元素所在位置:%d\n",loc+1); //顯示該元素位置
		   else    printf("%c 不存在!\n",ch);//當前元素不存在
		   break;
		  }
	 default:flag=0;printf("程序結束，按任意鍵退出!\n");
	}
    }
 getch();
}
void initial(sqlisttp &v)
{//初始化線性表
 int i;
 printf("請輸入初始線性表長度：n="); //輸入線性表初始化時的長度
 scanf("%d",&v.last);
 printf("請輸入從1到%d的各元素(字符)，例如:abcdefg\n",v.last);
 getchar();
 for(i=0;i<v.last;i++) scanf("%c",&v.elem[i]); //輸入線性表的各元素
}

BOOL insert(sqlisttp &v,int loc,char ch)        
{//插入一個元素，成功返回True，失敗返回False
 int i;
 if((loc<1)||(loc>v.last+1))
   {printf("插入位置不合理!\n");  //位置不合理
    return False;
   }
 else if(v.last>=MAX)         //線性表已滿
     {printf("線性表已滿!\n");
      return False;
     }
 else {for(i=v.last-1;i>=loc-1;i--) v.elem[i+1]=v.elem[i];//其后元素依次后移
       v.elem[loc-1]=ch;     //插入元素
       v.last++;                      //線性表長度加一
       return True;
     }
}

BOOL del(sqlisttp &v,int loc,char &ch)           
{//刪除一個元素，成功返回True，并用ch返回該元素值，失敗返回False
 int j;
 if(loc<1||loc>v.last)    //刪除位置不合理
    return False;
 else {ch=v.elem[loc-1];  //ch取得該元素值
       for(j=loc-1;j<v.last-1;j++) v.elem[j]=v.elem[j+1];   //其后元素依次前移
       v.last--;       //線性表長度減一
       return True;
      }
}

int locate(sqlisttp v,char ch)
{//在線性表中查找ch的位置，成功返回其位置，失敗返回-1
 int i=0;
 while(i<v.last&&v.elem[i]!=ch) i++;  //當前位置后移，直到找到為止
 if(v.elem[i]==ch)               //找到當前元素
    return i;
 else  return(-1);
}
void print(sqlisttp v)          //顯示當前線性表所有元素
{int i;
 for(i=0;i<v.last;i++) printf("%c ",v.elem[i]);
 printf("\n");
}