#include <cstdio> 
#include <cstdlib>
#include <cstring>
using namespace std;
struct list* create();	/*新建链表*/ 
struct list* insert( struct list *head, struct list *temp );	/*插入*/ 
struct list *deletes( struct list *head, int num );	/*删除*/ 
void print( struct list *head );	/*遍历输出*/ 
typedef long long LL;	/*给予long long别名 LL*/ 
struct list{
	int num;
	char name[20];
	LL tel;		/*定义long long 的整型变量*/ 
	struct list *next;	/*嵌套定义，既是结构分量又是该结构指针*/ 
};
int main()
{
	struct list *head, *p; /*头结点和操作指针*/ 
	int num;
	char name[20];
	LL tel;
	int choice;
	int size = sizeof( struct list );
	
	do{
		printf("1: create\n2: insert\n3: delete\n4: print\n0: exit\n");
		scanf("%d", &choice );
		switch( choice ){
			case 1:
				head = create();
				break;
			case 2:
				printf("input num, name and tel: \n");
				scanf("%d%s%lld", &num, name, &tel );
				p = ( struct list * ) malloc( size );
				p->num = num;
				strcpy( p->name, name );
				p->tel = tel;
				head = insert( head, p );
				break;
			case 3:
				printf("input num:\n");
				scanf("%d", &num );
				head = deletes( head, num );
				break;
			case 4:
				print( head );
				 break;
			case 0:
				break;
		}
	}while( choice != 0 );
	
	return 0;
}

struct list* create()
{
	struct list *head, *p;	/*定义头结点和操作指针*/ 
	int num;
	char name[20];
	LL tel;
	int size = sizeof( struct list );
	
	head = NULL;	/*头结点初始为空指针*/ 
	printf("input num, name and tel:\n");
	scanf("%d%s%lld", &num, name, &tel );
	while( tel != 0 ){
		p = ( struct list * ) malloc( size );	/*动态分配存储空间*/ 
		p->num = num;
		strcpy( p->name, name );
		p->tel = tel;
		head = insert( head, p );	/*调用插入函数，插入一个结点*/ 
		scanf("%d%s%lld", &num, name, &tel );
	}
	return head;	/*返回头结点的地址*/ 
 }
 
 /*插入需要考虑插入的结点是不是在头结点之前，头结点为空怎么办，不为空又怎么班； 
  插入结点是不是在中间，还是在末尾*/ 
  /*查找插入结点的位置条件是什么*/ 
 struct list* insert( struct list *head, struct list *temp )
 {
 	/* ptr为带插入结点，ptr1是最后要插入结点的前一个结点
	 ptr2 是最后要插入结点的后一个结点*/ 
 	struct list *ptr, *ptr1, *ptr2;
 	
 	ptr2 = head;	/*初始ptr2 为头结点， 便于用循环查找要插入的位置*/ 
 	ptr = temp;		/*用ptr来保存要插入的结点*/ 
 	if( head == NULL ){	/*如果链表为空则直接在头结点插入*/ 
 		head = ptr;
 		head->next = NULL; /*初始头结点的下一个结点为空*/ 
	 }
	 else{
	 	/*用循环查找要插入的位置*/ 
	 	/*插入顺序为num的序号*/ 
	 	while( ( ptr->num > ptr2->num ) && ( ptr2->next != NULL ) ){
	 		ptr1 = ptr2;	/*ptr和ptr2逐个后移*/ 
	 		ptr2 = ptr2->next;
		 }
		 if( ptr->num <= ptr2->num ){	/*判断插入位置是不是链表末尾或头结点之前*/ 
		 	if( head == ptr2 )	/*如果要插入的结点在头结点之前*/ 
		 		head = ptr;		/*头结点为新的 头结点*/ 
		 	else
		 		ptr1->next = ptr;
		 	/*如果插入在头结点，则头结点后移，否则三个结点先断后连 */
		 	ptr->next = ptr2;
		 }
		 else{					/*插入在末尾， 这时ptr2为最后一个结点*/ 
		 	ptr2->next = ptr;
		 	ptr->next = NULL; 	/*初始尾结点的下一个结点为空*/ 
		 }
	 }
	 return head;
 }
 
 /*删除需要考虑删除的结点是不是头结点，如果不是查找删除结点的条件是什么,
 只删除遇到的指定num值的第一个还是所有*/ 
 struct list *deletes( struct list *head, int num )
 {
 	struct list *ptr1, *ptr2;
 	
 	/*如果要删除的结点为头结点 */
 	while( head != NULL && head->num == num ){
 		ptr2 = head;
 		head = head->next;	/*头结点后移*/ 
 		free( ptr2 );	/*释放之前的头结点*/ 
	 }
	 if( head == NULL )
	 	return NULL;
	ptr1 = head;		/*ptr1, ptr2, 一前一后*/ 
	ptr2 = head -> next;
	while( ptr2 != NULL ){	/*从头结点的下一个结点开始查找*/ 
		if( ptr2->num == num ){	/*如果找到*/ 
			ptr1->next = ptr2->next;	/*直接把要删除的结点的前后两个结点相连*/ 
			free( ptr2 );	/*释放要删除的结点*/ 
			//break			/*加上break只删除第一个num, 不加删除所有*/ 
		}
		else			/*如果没找到， ptr1和ptr2后移一个结点*/ 
			ptr1 = ptr2;
		ptr2 = ptr1->next;
	} 
	return head;
 }
 
 void print( struct list *head )
 {
 	struct list *ptr;
 	if( head == NULL ){
 		printf("\nNO Records\n");
 		return;
	 }
	 printf("num\t name\t tel\n");
	 for( ptr=head; ptr != NULL; ptr = ptr->next )	/*循环输出*/ 
	 	printf("%d\t %s\t %lld\n", ptr->num, ptr->name, ptr->tel );
 }