#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#define NAME_SPACE 20

int cnt=0;

typedef struct _node{
	char *name;
	struct _node *next;
}linkedList;

typedef struct {
	linkedList *head;
}linkedList_h;

linkedList_h *createListHead(void);
void addLast(linkedList_h *L, char *str);
void addMidd(linkedList_h *L, char *str);
void searchList(linkedList_h *L);
void deleteNode(linkedList_h *L);
void printList(linkedList_h *L);
void freeLinkedList(linkedList_h *L)

linkedList_h *createListHead()
{
	linkedList_h *r; // 새 헤드 생성
	r=(linkedList_h*)malloc(sizeof(linkedList_h)); // 메모리 할당
	r->head=NULL; // 초기화
	return r; // 주소값 반환
}

void addSlct(linkedList_h *L){
	char str[NAME_SPACE];
	char slct[5];

	printf("삽입할 노드의 데이터 입력 : ");
	scanf("%s",&str);

	for(;;){
		printf("삽입할 위치 선택 : ");
		scanf("%s",&slct);
		if(!strcmp(slct,"No")){addLast(L, str);return;} // 위치선택 No 면 마지막 노드에 추가
		else if(!strcmp(slct,"Yes")){ // 위치 선택 Yes 면 인덱스값을 받고 그 위치에 추가
			addMidd(L, str);
			return;
		}
		else puts("잘못된 값 입력. (Yes or No)");
	}
}

void addLast(linkedList_h *L, char *str)
{
	linkedList *newNode;
	linkedList *p;
	newNode=(linkedList*)malloc(sizeof(linkedList));
	newNode->name=(char*)malloc(sizeof(char)*NAME_SPACE);
	strcpy(newNode->name,str);
	newNode->next=NULL;
	cnt++;

	if(L->head==NULL){
		L->head=newNode;
		printList(L); // 리스트 출력
		return;
	}
	p=L->head;
	while(p->next != NULL){
		p=p->next;
	}
	p->next=newNode;
	printList(L); // 리스트 출력
}

void addMidd(linkedList_h *L, char *str)
{
	linkedList *newNode;
	linkedList *p;
	newNode=(linkedList*)malloc(sizeof(linkedList));
	newNode->name=(char*)malloc(sizeof(char)*NAME_SPACE);
	strcpy(newNode->name,str);
	newNode->next=NULL;
	p=L->head;

	if(L->head==NULL){
		puts("헤드밖에 없습니다.");
		L->head=newNode;
		cnt++;
		printList(L); // 리스트 출력
		return;
	}

	char target[NAME_SPACE];
	printList(L); // 리스트 출력	
	printf("삽입할 데이터 입력 : ");
	scanf("%s",&target);

	while(strcmp(p->name,target)){
		p=p->next;
		if(p == NULL){
			puts("데이터가 존재하지 않습니다.");
			return;
		}
	}
	newNode->next=p->next;
	p->next=newNode;
	cnt++;
	printList(L); // 리스트 출력
}

void searchList(linkedList_h *L)
{
	int i=0, n=0;
	int *idx;
	char str[NAME_SPACE];
	idx=(int*)malloc(sizeof(int)*cnt);

	printf("검색할 데이터 입력 : ");
	scanf("%s",&str);

	linkedList *p;
	p=L->head;

	while(p != NULL){
		*(idx+i)=0;
		if(!strcmp(p->name, str)){
			n++;
			*(idx+i)=i+1;
		}
		p=p->next;
		i++;
	}
	if(n==0) puts("동일한 데이터를 가진 노드가 존재하지 않음");
	else{
		printf("%d개의 노드 중 %d개의 노드 데이터와 일치\n", cnt, n);
		for(i=0; i<cnt; i++){
			if(*(idx+i)){
				if(n==1)
					printf("%d ", *(idx+i));
				else{
					printf("%d, ", *(idx+i));
					n--;
				}
			}
		}
		printf("번째 데이터\n");
	}
}

void deleteNode(linkedList_h *L)
{
	linkedList *p;
	linkedList *t;
	linkedList *pre;
	p=L->head;
	t=L->head;

	if(p==NULL){
		puts("노드가 존재하지 않습니다.");
		return;
	}

	char str[NAME_SPACE];
	printf("삭제할 데이터 입력 : ");
	scanf("%s",&str);
	if(!strcmp(p->name, str)){
		L->head=p->next;
		free(p);
		cnt--;
		return;
	}

	while(p != NULL){
		if(!strcmp(p->name, str)){
			pre->next=p->next;
			free(p);
			cnt--;
			return;
		}
		pre=p;
		p=p->next;
	}
	puts("데이터가 존재하지 않습니다.");
}

void printList(linkedList_h *L)
{
	linkedList *p;
	p=L->head;

/* 리스트 카운터
	linkedList *pcnt;
	pcnt=L->head;
	int cnt=0;
	while(pcnt != NULL){ 
		++cnt;
		pcnt=pcnt->next;
	}
*/
	printf("리스트 출력(%d) : ",cnt);
	while(p != NULL){
		if(p->next==NULL)
			printf("%s",p->name);
		else
			printf("%s->",p->name);
		p=p->next;
	}
	puts("");
}

void freeLinkedList(linkedList_h *L)
{
	linkedList *p;
	while(L->head != NULL){
		p=L->head;
		L->head=L->head->next;
		free(p);
		p=NULL;
	}
}

int main(void){
	int slct;
	linkedList_h *L;
	L=createListHead();
	
	while(slct!=5)
	{
		puts("\n단순 연결 리스트 메뉴"); // 메뉴
		puts("=================");
		puts("1. 노드 삽입");
		puts("2. 노드 삭제");
		puts("3. 노드 검색");
		puts("4. 노드 출력");
		puts("5. 프로그램 종료");
		puts("=================");
		printf("메뉴 선택 : ");
		scanf("%d",&slct);

		switch(slct){
			case 1:
				addSlct(L); // 1. 노드 삽입
				break;
			case 2:
				deleteNode(L); // 2. 노드 삭제
				break;
			case 3:
				searchList(L); // 3. 노드 검색
				break;
			case 4:
				printList(L); // 4. 노드 출력
				break;
			case 5:
				break; // 5. 프로그램 종료
			default: 
				printf("잘못된 명령입니다.\n");
				break;
		}
	}
	freeLinkedList(L); // 링크드 리스트 L 해제

	return 0;
}