// ȫվ���ݽ���ѧϰ����ֹ��ԭ�Ļ��޸���ʽ����κ���ҵʹ�ã���׼�ء�һ������Ȩ��Э��
// ��Դ:totuma.cn
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
    int data;
    struct LNode *next;
} LNode, *LinkList;

// ��ʼ������
bool List_Init(LinkList &pHead)
{
    pHead = NULL;
    return true;
}

// �жϵ������Ƿ�Ϊ��
bool List_Empty(LinkList pHead)
{
    return pHead == NULL;
}

// ��ȡ��������Ч���ݽڵ����
int List_Length(LinkList pHead)
{
    int count = 0;
    for (LNode *p = pHead; p != NULL; p = p->next)
        count++;
    return count;
}

// totuma.cn
// ����������ͷ����Ϊ����
LinkList List_Create(LinkList &pHead)
{
    LNode *pTemp;
    int x;
    scanf("%d", &x);
    while (x != 999)
    {
        pTemp = (LNode *)malloc(sizeof(LNode));
        pTemp->data = x;
        pTemp->next = pHead;
        pHead = pTemp;
        scanf("%d", &x);
    }
    return pHead;
}

// totuma.cn
// ��λ����룬i=1���ڱ�ͷ��i=length+1���ڱ�β
bool List_Insert(LinkList &pHead, int i, int e)
{
    if (i < 1 || i > List_Length(pHead) + 1)
        return false;
    LNode *pTemp = (LNode *)malloc(sizeof(LNode));
    if (i == 1)
    { // �����1�����IJ���
        pTemp->data = e;
        pTemp->next = pHead;
        pHead = pTemp;
        return true;
    }
    LNode *p;  // ָ��pָ���Ϊ��ǰɨ�赽�Ľ��
    int j = 1; // ��ǰpָ����ǵڼ������
    p = pHead; // p ָ���1����㣨ע�⣺����ͷ�ڵ㣩
    while (p != NULL && j < i - 1)
    { // ѭ���ҵ�Ҫ����λ�õ�ǰ�����
        p = p->next;
        j++;
    }
    pTemp->data = e;
    pTemp->next = p->next;
    p->next = pTemp;
    return true;
}

// totuma.cn
// ͨ��ֵ��ȡ����λ��
LNode *List_Get_Elem(LinkList pHead, int e, int &i)
{
    i = 1;
    LNode *p = pHead;
    while (p != NULL && p->data != e)
    {
        p = p->next;
        i = i + 1;
    }
    return p;
}

// totuma.cn
// ��λ��ɾ����i=1ɾ��ͷ��i=lengthɾͷβ
bool List_Del(LinkList &pHead, int i)
{
    if (i < 1 || i > List_Length(pHead))
        return false;
    LNode *p = pHead; // p ָ���ͷ
    if (i == 1)
    { // ɾ����һ�����
        pHead = p->next;
        free(p);
        return true;
    }
    // �ҵ���ɾ��λ���ǰһλ��㣬i==1�Ѵ������ʴ�j=2��ʼ
    for (int j = 2; j < i; j++)
        p = p->next;
    LNode *q = p->next; // ��ɾ�����
    p->next = q->next;  // p->next q q->next ����q
    free(q);
    return true;
}

// totuma.cn
// ��ӡ��������ֵ
void List_Show(LinkList pHead)
{
    LNode *node = pHead;
    printf("����ֵ��");
    do
    {
        printf("%d��", node->data);
        node = node->next;
    } while (node != NULL);
    printf("\n");
}

int main()
{
    LinkList pHead;
    List_Init(pHead);
    printf("�����пգ�%s\n", List_Empty(pHead) ? "��" : "�ǿ�");
    List_Create(pHead);
    List_Show(pHead);
    printf("�������ȣ�%d\n\n", List_Length(pHead));

    printf("λ��Ϊ1(ͷ��)�����룺0\n");
    List_Insert(pHead, 1, 0);
    List_Show(pHead);
    printf("�������ȣ�%d\n\n", List_Length(pHead));

    printf("λ��Ϊ%d(β��)�����룺99\n", List_Length(pHead) + 1);
    List_Insert(pHead, List_Length(pHead) + 1, 99);
    List_Show(pHead);
    printf("�������ȣ�%d\n\n", List_Length(pHead));

    printf("ɾ��λ��Ϊ1(ͷɾ)\n");
    List_Del(pHead, 1);
    List_Show(pHead);
    printf("�������ȣ�%d\n\n", List_Length(pHead));

    printf("ɾ��λ��Ϊ%d(β��)\n", List_Length(pHead));
    List_Del(pHead, List_Length(pHead));
    List_Show(pHead);
    printf("�������ȣ�%d\n\n", List_Length(pHead));

    printf("��ȡֵΪ��5�Ľ��λ��\n");
    int i = -1; // -1 Ϊδ�ҵ�
    LNode *p5 = List_Get_Elem(pHead, 5, i);
    printf("ֵΪ5�Ľ��λ��Ϊ��%d\n\n", i);

    printf("�����пգ�%s\n", List_Empty(pHead) ? "��" : "�ǿ�");
    return 0;
}