#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int datatype;

typedef struct linknode{
	datatype data;
	struct linknode *next;//指向下一个节点的指针 
}list;
//list为struct linknode的别名 

list *init_list()
{
	list *head; 
	head = (list*)malloc(sizeof(list));//申请变量 
	head->next = NULL;	//将表头的指针初始化 
	return head; 
}

//头插法 
void create_list1(list *head, int n)
{
	list *s;
	printf("请输入%d个整数\n",n);
	for(int i = 0;i < n; i++)
	{
		s = (list*)malloc(sizeof(list));
		scanf("%d",&s->data);
		s->next = head->next;
		head->next = s;
	}
	printf("建立链表成功！\n"); 
}

//尾插法 
void create_list2(list *head, int n)
{
	list *s;
	list *last;
	last = head;
	printf("请输入%d个整数\n",n);
	for(int i = 0; i < n; i++)
	{
		s = (list *)malloc(sizeof(list));
		scanf("%d",&s->data);
		s->next = NULL;
		last->next = s;
		last = s;
	}
	printf("建立链表成功！\n");
}

//求链表长度 
int length(list *head)
{
	list *p = head->next;
	int j = 0;
	while(p != NULL)
	{
		p=p->next;
		j++;
	}
	return j;
}

//按值查找 
void find_num(list *head,datatype x)
{
	int j = 1;
	list *p;
	p = head->next;
	while(p != NULL && p->data != x)
	{
		p = p->next;
		j++;
	}
	if(p != NULL)
	{
		printf("在表的第%d位找到了值为%d的节点\n", j, x);
	}
	else
	{
		printf("未找到值为%d的节点\n",x);
	}
}

//按序号查找 
void find_serial_num(list *head,int i)
{
	list *p;
	int j = 0;
	p=head;
	if(i > length(head))
	{
		printf("位置错误！\n");
	}
	while(p->next != NULL && j < i)
	{
		p = p->next;
		j++ ;
	}
	if(j==i)
	{
		printf("在第%d位上的元素值为%d!\n", i, p->data);
	}
}

//插入,第i位 
void insert(list *head, int i, datatype x)
{
	int j = 0;
	list *p;
	list *s;
	p = head;
	while(p->next != NULL && j < i-1)
	{
		p = p->next;
		j++;
	}
	if(p != NULL)
	{
		s = (list *)malloc(sizeof(list));
		s->data = x;
		s->next = p->next;
		p->next = s;
		printf("插入元素成功！\n"); 
		
	}
	else
	{
		printf("插入元素失败！\n");
	}
	
}

//按位置删除节点 
void delete(list *head, int i)
{
	int j = 0;
	datatype x;
	list *p =head;
	list *s;
	while(p->next != NULL && j<i-1)
	{
		p = p->next;
		j++;
	}
	if(p->next != NULL && j == i-1)
	{
		s = p->next;
		x = s->data;
		p->next = s->next;
		free(s);
		printf("删除第%d位上的元素%d成功！\n",i,x);
	}
	else
	{
		printf("删除失败\n");
	}
}

//输出链表 
void output(list *head)
{
	list *p;
	p = head->next;
	while(p != NULL)
	{
		printf("%5d",p->data);
		p = p->next;
	}
} 

void menu()
{
	printf("1.头插法建立链表\n"
		   "2.尾插法建立链表\n"
		   "3.查看链表\n"
		   "4.插入元素\n"
		   "5.删除元素\n"
		   "6.按位置查找元素\n"
		   "7.按数字查找元素\n"
		   "8.退出\n");
	 printf("请输入序号：");
}

int main()
{
	list head;
	head = *init_list();
	datatype x;//需要插入的值 
	bool create = false;//判断是否创建链表 
	system("mode con cols=60 lines=20");
	while(1)
	{
		system("cls");
		menu();
		char a = 0;
		scanf("%c",&a);
		switch(a)
		{
			case '1':
				if(!create)
				{
					int a= 0;
					printf("\n创建时需要加入多少个数据?\n");
					scanf("%d",&a);
					create_list1(&head, a);//头插法
					create = true;
				}
				else
				{
					printf("链表已存在，请勿重复创建\n"); 
					
				}
				system("pause");
				getchar();//吸收回车 
				break;
			case '2':
				if(!create)
				{
					int a= 0;
					printf("\n创建时需要加入多少个数据?\n");
					scanf("%d",&a);
					create_list2(&head, a);//尾插法
					create = true;
				}
				else
				{
					printf("链表已存在，请勿重复创建\n"); 
				}
				system("pause");
				getchar();
				break;
			case '3':
				if(create)
				{
					output(&head);	
				}
				else
				{
					printf("链表不存在,请先创建链表\n");
				}
				printf("\n");
				system("pause");
				getchar();
				break;
			case '4':
				if(create)
				{
					int a = 0;
					datatype b = 0;
					printf("\n需要在哪个位置插入？\n");
					scanf("%d",&a); 
					printf("\n请输入插入的数值\n");
					scanf("%d",&b);
					insert(&head, a, b);
				}
				else
				{
					printf("链表不存在,请先创建链表\n");
				}
				system("pause");
				getchar();
				break;
			case '5':
				if(create)
				{
					int a = 0;
					printf("请输入需要删除的值的位置\n");
					scanf("%d",&a);
					delete(&head,a);
				}
				else
				{
					printf("链表不存在,请先创建链表\n");
				}
				system("pause");
				getchar();
				break;
			case '6':
				if(create)
				{
					int a = 0; 
					printf("请输入需要查找的数据的位置\n");
					scanf("%d",&a);
					find_serial_num(&head,a);
				}
				else
				{
					printf("链表不存在,请先创建链表\n");
				}
				system("pause");
				getchar();
				break;
			case '7':
				if(create)
				{
					int a = 0;
					printf("请输入需要查找的数据大小\n");
					scanf("%d",&a);
					find_num(&head,a);
				}
				else
				{
					printf("链表不存在,请先创建链表\n");
				}
				system("pause");
				getchar();
				break;
			case '8':
				return 0;
			default:
				printf("请输入1-8\n");
				system("pause");
				break; 
		}
		
	}
	
}