/*	實驗內容
1．鏈表是有序的，現在刪除數據x，若x不存在，輸出一段提示信息。
（無頭結點）
2．線性表v的數據遞增有序，試將x插入表中并保持有序性
   (2)鏈表表示（無頭結點）
*/
#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct LNode)
//定義LNode結構體
struct LNode
{
	int data;
	LNode *next;
};
int n;

LNode *creatlist(void)//創建鏈表
{
	LNode *head,*p1,*p2;
	n=0;
	p1=p2=(LNode *)malloc(LEN);//生成一個結點，p1、p2都指向該結點
	scanf("%d",&p1->data);
	head=NULL;
	while(p1->data!=0)//這里0是結束標志
	{
		n=n+1;
		if(n==1)//如果只有一個結點，將head指針也指向該結點
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(LNode *) malloc(LEN);
		scanf("%d",&p1->data);
	}
	p2->next=NULL;
	return head;
}
void print(LNode *head)//輸出鏈表
{
	LNode *p;
	printf("\n輸入的%d個記錄為：\n",n);
	p=head;
    if(head!=NULL)//判斷鏈表是否為空
		do
		{
			printf("%d ",p->data);
			p=p->next;
		}while(p!=NULL);
}
LNode *del(LNode *head,int num)//刪除結點數據為num的數
{
	LNode *p1,*p2;
	if(head==NULL)
	{	printf("\n該鏈表為空！\n");}
	p1=head;
	while(num!=p1->data&&p1->next!=NULL)
	{    //從第一個結點開始，如果要刪除的數不等于該結點上的數，
		 //而且鏈表不止一個結點，那么繼續指向下一個結點，直到找到需要的數。
		p2=p1;
		p1=p1->next;
	}
	if(num==p1->data)//輸入的數據可以在鏈表中找到
	{
		if(p1==head)//如果只有一個結點的情況
			head=p1->next;
		else
			p2->next=p1->next;
		printf("\n刪除的結點為:%d\n",num);
		n=n-1;
	}
	else
	{	printf("\n沒找到要刪除的結點！\n");}
	return head;
}
LNode * insert(LNode *head,LNode *data)//將數據插到鏈表中第一個比它大的數據前
{
	LNode *p0,*p1,*p2;
	p1=head;
	p0=data;
	if(head==NULL)
	{
		head=p0;
		p0->next=NULL;
	}
	else//將插入的數與鏈表中的原數據進行比較，插在第一個比他打的數據前
	{
		while((p0->data>p1->data)&&(p1->next!=NULL))
		{//插入的數>p1指向的結點數據，而且不止一個結點，繼續尋找直到比他大的數據
			p2=p1;
			p1=p1->next;
		}
		if(p0->data<=p1->data)
		{//插入的數<=p1指向的結點數據，將數插入到p1結點之前
			if(head==p1)
				head=p0;
			else
				p2->next=p0;
		    	p0->next=p1;
		}
		else/*鏈表為空，插到最后的結點之后*/
		{
			p1->next=p0;
			p0->next=NULL;
		}
	}
	n=n+1;
	return head;
}
void main()
{
	LNode *head,*h;
	int del_num;
	int select;
	printf("請輸入一組有序數列(結束符：0)：\n");
	head=creatlist();
	print(head);
//clrscr();	
  do
  {     //操作選擇
   printf("\n1:插入一個數\n");
   printf("2:刪除一個數\n"); 
   printf("3:結束\n");     
   scanf("%d",&select); 
   switch(select)
   {
   case 1:
	printf("\n請輸入要插入的數new_num：\n");
    h=(LNode *)malloc(LEN);
	scanf("%d",&h->data);
	while(h->data!=0)
	{head=insert(head,h);
	 print(head);
     printf("\n請輸入要插入的數(輸入0可結束插入)new_num：\n");
     h=(LNode *)malloc(LEN);
	 scanf("%d",&h->data);}
	 break;
   case 2:
	printf("\n輸入要刪除的數del_num:\n");
	scanf("%d",&del_num);
	while(del_num!=0)
	{head=del(head,del_num);
	 print(head);
	 printf("\n輸入要刪除的數(輸入0可結束刪除)del_num:\n");
	 scanf("%d",&del_num);}
	break;
   case 3:
     printf("結束本程序！");   
     printf("\n");
     break;
	}
   }
   while(select!=3);
   
}