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

// 定义链表的节点结构
struct Node {
    int data;
    struct Node* next;
};

// 初始化链表
void initialize(struct Node** head) {
    *head = NULL;
}

// 在链表末尾插入节点
void insert(struct Node** head, int value) {
    // 创建新节点
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    

    if (*head == NULL) {
        // 如果链表为空，将新节点设为头节点
        *head = newNode;
    } else {
        // 找到链表末尾节点并插入新节点
        struct Node* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }

    printf("节点插入成功！\n");
}

// 删除链表中指定值的节点
void removeNode(struct Node** head, int value) {
    struct Node* prev = NULL;
    struct Node* current = *head;

    while (current != NULL) {
        if (current->data == value) {
            // 找到要删除的节点
            if (prev == NULL) {
                // 如果是头节点，则更新头指针
                *head = current->next;
            } else {
                // 否则，修改前一个节点的指针
                prev->next = current->next;
            }

            // 释放内存
            free(current);
            printf("节点删除成功！\n");
            return;
        }

        prev = current;
        current = current->next;
    }

    printf("未找到要删除的节点！\n");
}

// 查找链表中指定值的节点
void search(struct Node* head, int value) {
    struct Node* current = head;
    int index = 0;
    int found = 0;

    while (current != NULL) {
        if (current->data == value) {
        	found = 1;
            index++;
            printf("找到节点：%d，位置：%d\n", value, index);
            
        }

        current = current->next;
        index++;
    }

    if (!found) {
        printf("未找到节点：%d\n", value);
    }
}

// 打印链表中的所有节点值
void printList(struct Node* head) {
    struct Node* current = head;

    if (current == NULL) {
        printf("链表为空！\n");
        return;
    }

    printf("链表中的节点值：");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 释放链表的内存
void freeList(struct Node** head) {
    struct Node* current = *head;
    struct Node* next = NULL;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }

    *head = NULL;
    printf("链表内存已释放！\n");
}

// 建立链表
void CreatList(struct Node** head)
{
	int a, b;
	printf("请输入要创建的链表节点个数：");
	scanf("%d", &a);
	int i;
	for (i = 1; i <= a; i++)
	{
		printf("请输入插入的第%d个节点的值：", i);
		while (scanf("%d", &b) != 1) {
		    printf("输入类型错误！\n");
		    clearInputBuffer(); // 清空输入缓冲区
		    printf("请重新输入第%d的值：", i);
		    }
	
		insert(head, b);
		printf("\n");
		
	}
}

// 清空输入缓冲区
void clearInputBuffer() {
    while (getchar() != '\n');
}

// 在链表指定位置插入节点
void insertAtPosition(struct Node** head, int value, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (position == 1) {
        // 如果要在头部插入节点
        newNode->next = *head;
        *head = newNode;
        printf("节点插入成功！\n");
        return;
    }

    struct Node* current = *head;
    int index = 1;

    while (current != NULL && index < position - 1) {
        current = current->next;
        index++;
    }

    if (current == NULL) {
        printf("指定位置超出链表范围，插入失败！\n");
    } else {
        newNode->next = current->next;
        current->next = newNode;
        printf("节点插入成功！\n");
    }
}

int main() {
    struct Node* head;
//    initialize(&head);

    int choice;
    int value;
    int position;

    do {
        printf("\n链表操作菜单：\n");
        printf("1. 初始化链表\n");
        printf("2. 建立链表\n");
        printf("3. 插入节点\n");
        printf("4. 删除节点\n");
        printf("5. 查找节点\n");
        printf("6. 打印链表\n");
        printf("7. 指定位置插入值\n");
        printf("8. 退出\n");
        printf("请输入您的选择：");
        scanf("%d", &choice);

        switch (choice) {
        	case 1:
        		initialize(&head);
        		printf("初始化成功！\n");
        		break;
        	case 2:
        		CreatList(&head);
			    break; 
            case 3:
                printf("请输入要插入的节点值：");
              
                
			    while (scanf("%d", &value) != 1) {
		        printf("输入类型错误！\n");
		        clearInputBuffer(); // 清空输入缓冲区
		        printf("请重新输入一个整数：");
		       }

                
                insert(&head, value);
                break;
            case 4:
                printf("请输入要删除的节点值：");
                scanf("%d", &value);
                removeNode(&head, value);
                break;
            case 5:
                printf("请输入要查找的节点值：");
                scanf("%d", &value);
                search(head, value);
                break;
            case 6:
                printList(head);
                break;

            case 7:
                
			// 获取要插入的节点值和位置
			    printf("请输入要插入的节点值：");
			    while (scanf("%d", &value) != 1) {
		            printf("输入类型错误！\n");
		            clearInputBuffer(); // 清空输入缓冲区
		            printf("请重新输入要插入的值：");
		        }
			
			    printf("请输入要插入的位置：");
			    while (scanf("%d", &position) != 1) {
		            printf("输入类型错误！\n");
		            clearInputBuffer(); // 清空输入缓冲区
		            printf("请重新输入要插入的位置：");
		        }
		        // 调用插入函数
    			insertAtPosition(&head, value, position);
            	break;
            case 8:
                freeList(&head);
                printf("程序已退出！\n");
                break;
            default:
                printf("无效的选择！\n");
                break;
        }
    } while (choice != 8);

    return 0;
}