#include <malloc.h>
#include <stdio.h>
#include <string.h>
typedef int DataType;   /*定义DataType为int类型*/
typedef struct linknode /*单链表存储类型*/
{
    DataType data;         /*定义结点的数据域*/
    struct linknode* next; /*定义结点的指针域*/
} LinkList;

LinkList* InitList() //初始化函数//
{
    LinkList* head;
    head = (LinkList*)malloc(sizeof(LinkList)); //动态分配一个结点空间
    head->next = NULL;
    return head; //头节点L指针域为空，表示空链表
}

void CreateListH(LinkList* head, int n) //头插法建立链表函数//
{
    LinkList* s;
    int i;
    printf("请输入%d个整数:", n);
    for (i = 0; i < n; i++) {
        s = (LinkList*)malloc(sizeof(LinkList)); //生成新节点
        scanf("%d", &s->data);
        s->next = head->next; //将新节点的指针域存放头节点的指针域
        head->next = s;       //姜新节点插入头节点之后
    }
    printf("建立链表操作成功！");
}

void CreateListL(LinkList* head, int n) //尾插法建立链表函数//
{
    LinkList *s, *last;
    int i;
    last = head; // last始终指向尾节点，开始时指向头节点
    printf("请输入%d个整数:", n);
    for (i = 0; i < n; i++) {
        s = (LinkList*)malloc(sizeof(LinkList)); //生成新节点
        scanf("%d", &s->data);
        s->next = NULL; //将新节点的指针域为空;
        last->next = s; //将新结点插入表尾
        last = s;
    }
    printf("建立链表成功！");
}

int LengthList(LinkList* head) //求链表长度函数
{
    LinkList* p = head->next;
    int j = 0;
    while (p != NULL) //当p不指向链表尾时
    {
        p = p->next;
        j++;
    }
    return j;
}
void Locate(LinkList* head, DataType x) //在链表中查找值为x的元素位置//
{
    int j = 1; // 计数器
    LinkList* p;
    p = head->next;
    while (p != NULL && p->data != x) //查找及定位
    {
        p = p->next;
        j++;
    }
    if (p != NULL)
        printf("在表的第%d位找到值为%d的结点！", j, x);
    else
        printf("未找到值为%d的结点！", x);
}

void SearchList(LinkList* head, int i) //在链表中按位置查找的元素位置//
                                       //  head接收已存在的链表的头指针
//  i 接收要查找的结点的位置
//从头结点开始顺链扫描
{
    LinkList* p; //用指针 p 指向当前扫描到的结点。
    int j = 1; //用 j 作统计已扫描结点数的计数器，j 的初值为 1 。
    p = head->next; // p 的初值指链表中的第一个元素.

    printf("\n\t\t请输入要查找的结点的位置，并按回车：\n");
    scanf("\n%d", &i);

    while (p->next != NULL && j < i) {
        p = p->next;
        j++; //当 p 扫描下一个结点时，j 自动加 1
    }
    if (j == i) //当 j=i时，指针 p 所指的结点就是第 i 个结点
    {
        printf("\n\t\t查找的此结点所在位置的值为：%d", p->data);
    }

    else {
        printf("\n\t\t未找到此节点，请确认输入是否正确!!");
    }
}

void InsList(LinkList* head, int i, DataType x) //按位置插入元素函数//
{
    int j = 0;
    LinkList *p, *s;
    p = head;
    while (p->next != NULL && j < i - 1) //定点插入点
    {
        p = p->next;
        j++;
    }
    if (p != NULL) // p不为空则将新节点插到p后
    {
        s = (LinkList*)malloc(sizeof(LinkList)); //生成新节点s
        s->data = x;       //将数据x放入4新节点的数据域
        s->next = p->next; //将新结点s的指针域与p结点后面元素相连
        p->next = s;       //将p与新节点s链接
        printf("插入元素成功！");
    } else
        printf("插入元素失败！");
}

void DelList(LinkList* head, int i) //按位置删除链表中元素函数//
{
    int j = 0;
    DataType x;
    LinkList *p = head, *s;
    while (p->next != NULL && j < i - 1) //定点插入点
    {
        p = p->next;
        j++;
    }
    if (p->next != NULL && j == i - 1) {
        s = p->next;       // q为要删除结点
        x = s->data;       //将要删除的数据放入指针变量x中
        p->next = s->next; //将p结点的指针域与q结点后面元素相连
        free(s);
        printf("删除第%d位上的元素%d成功！", i, x);
    } else
        printf("删除结点位置错误，删除失败败！");
}

void DispList(LinkList* head) //显示输出链表函数
{
    LinkList* p;
    p = head->next;
    while (p != NULL) {
        printf("%5d", p->data);
        p = p->next;
    }
}

void MenuLine() { /*显示菜单子函数*/
    printf("\n                  线性表子系统");
    printf("\n* * * * * * * * * * * * * * * * * * * * * * * * *");
    printf("\n*                  1——建立                      *");
    printf("\n*                  2——插入                      *");
    printf("\n*                  3——删除                      *");
    printf("\n*                  4——按位置查找                *");
    printf("\n*                  5——按元素值查找              *");
    printf("\n*                  6——求表长                    *");
    printf("\n*                  0——返回                      *");
    printf("\n* * * * * * * * * * * * * * * * * * * * * * * * *");
    printf("\n请输入菜单号（0-6）:");
}

int main() {
    LinkList* head;
    DataType x;
    int i, n;
    char ch1, ch2, a;
    ch1 = 'y';

    while (ch1 == 'y' || ch1 == 'Y') {
        MenuLine();
        scanf("%c", &ch2);
        getchar();
        switch (ch2) {
        case '1':
            head = InitList();
            printf("请输入要建立线性表的长度：");
            scanf("%d", &n);
            CreateListL(head, n); /*如改为CreateListH(L);则用头插法建立链表*/
            printf("建立后的线性表为：\n");
            DispList(head);
            break;
        case '2':
            printf("请输入要插入的元素位置：");
            scanf("%d", &i);
            getchar();
            printf("请输入要插入的元素值：");
            scanf("%d", &x);
            InsList(head, i, x);
            printf("插入元素%d后的线性表为：\n", x);
            DispList(head);
            break;
        case '3':
            printf("请输入要删除的元素位置：");
            scanf("%d", &i);
            DelList(head, i);
            printf("删除第%d位的元素后的线性表为：\n", i);
            DispList(head);
            break;
        case '4':
            SearchList(head, i);
            break;
        case '5':
            printf("请输入查找的整数：");
            scanf("%d", &x);
            Locate(head, x);
            break;
        case '6':
            printf("该线性表的长度为%d！", LengthList(head));
            break;
        case '0':
            ch1 = 'n';
            break;
        default:
            printf("输入有误，请输入0-6进行选择！");
        }
        if (ch2 != '0') {
            printf("\n按回车键继续，按任意键返回主菜单！\n");
            a = getchar();
            if (a != '\xA') {
                getchar();
                ch1 = 'n';
            }
        }
    }
}