线性表的表现与实现

#include<iostream>
using namespace std;

typedef int ElemType;

struct  LNode
{
    ElemType data;
    LNode *next;
};

struct LinkList
{
    LNode *head;

    void Init();
    void Create(int n);
    void Clear();
    int Locate(ElemType e);
    void InsertBefore(int i, ElemType e);
    void Delete(int i, ElemType &e);
    void Traverse();
    bool Empty();
};



int main()
{
    int m, n;
    LinkList L;

    L.Init();

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        L.InsertBefore(i + 1, t);
    }

    L.Traverse();

    cout << L.Locate(5) << endl;

    L.Delete(5, m);
    L.Traverse();

    L.Clear();

    return 0;

}

void LinkList::Init()
{
    head = new LNode;
    head->next = NULL;
}

bool LinkList::Empty()
{
    return head->next == NULL;

}

void  LinkList::Create(int n)//逆序输入n个数据，建立带头结点的单链表
{
    Init();
    for (int i = n; i > 0; i--)
    {
        LNode *p = new LNode;
        cin >> p->data;

        p->next = head->next;
        head->next = p;

    }
}

void LinkList::Traverse()//遍历单链表
{
    LNode *p = head->next;
    int cnt = 0;
    while (p)
    {
        cnt++;
        if (cnt > 1) cout << " ";
        cout << p->data;
        p = p->next;
    }
    cout << endl;
}

int LinkList::Locate(ElemType e)
{
    LNode *p = head->next;
    int i = 1;
    while (p)
    {
        if (e == p->data) break;
        i++;
        p = p->next;
    }
    if (!p) return 0;
    else return i;

}

void LinkList::InsertBefore(int i, ElemType e)
{
    LNode *p = head;
    while (p&&i>1)
    {
        p = p->next;
        i--;
    }
    if (p == NULL || i < 1)  return;
    LNode *s = new LNode;
    s->data = e;

    s->next = p->next;
    p->next= s;
}

void  LinkList::Delete(int i, ElemType &e)
{
    LNode *p = head;
    int j = 0;
    while (p->next&&j<i-1)
    {
        p = p->next;
        j++;
    }

    if (!(p->next) || j > i - 1) return;

    LNode *q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
}


void LinkList::Clear()
{
    while (head->next)
    {
        LNode *p = head->next;
        head->next = p->next;
        delete p;
    }
}