数据结构-线性表的链式存储结构

#include <iostream>
/**
 * 线性表的链式存储实现
 */
using namespace std;
template<class DataType>
struct Node {
    DataType data;
    Node<DataType> *next;
};

template<class DataType>
class LinkList {
public:
//无参构造函数 建立只有头结点的空链表
    LinkList();

//含参构造函数，建立有N个元素的单链表
    LinkList(DataType x[], int n);

//析构函数
    ~LinkList();

//求单链表长度
    int Length();

//按位查找 在单链表中查找第i个节点的元素值
    DataType Get(int i);

//按值查找 在单链表中查找值为x的元素序号
    int Locate(DataType x);

//插入操作 在第i个位置插入元素值为x的元素
    void Insert(int i, DataType x);

//删除操作 在单链表中删除第i个节点
    DataType Delete(int i);

//遍历操作 打印链表
    void PrintList();

private:
//    单链表的头指针
    Node<DataType> *first;
};

template<class DataType>
void LinkList<DataType>::PrintList() {
    Node<DataType> *p = first->next;
    cout << "遍历单链表:" << endl;
    while (p != NULL) {
        cout << p->data << endl;
        p = p->next;
    }
}

template<class DataType>
int LinkList<DataType>::Length() {
    int count;
    Node<DataType> *p = first->next;
    while (p != NULL) {
        p = p->next;
        count++;
    }
    return count;
}

template<class DataType>
DataType LinkList<DataType>::Get(int i) {
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL && count < i) {
        p = p->next;
        count++;
    }
    if (p == NULL)
        throw "Error: 位置错误";
    else return p->data;
}

template<class DataType>
int LinkList<DataType>::Locate(DataType x) {
    Node<DataType> *p = first->next;
    int count = 1;
    while (p != NULL) {
        if (p->data == x)
            return count;
        p = p->next;
        count++;
    }
    return 0;
}

template<class DataType>
void LinkList<DataType>::Insert(int i, DataType x) {
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count < i - 1) {
        p = p->next;
        count++;
    }
    if (p == NULL)
        throw "Error: 位置错误";
    else {
        Node<DataType> *s = new Node<DataType>;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}

template<class DataType>
LinkList<DataType>::LinkList() {
    first = new Node<DataType>;
    first->next = NULL;
}

//头插法
/*template<class DataType>
LinkList<DataType>::LinkList(DataType *x, int n) {
    first = new Node<DataType>;
    first->next = NULL;
    for (int i = 0; i < n; ++i) {
        Node<DataType> *s = new Node<DataType>;
        s.data = x[i];
        s.next = first->next;
        first->next = s;
    }
}*/
//尾插法
template<class DataType>
LinkList<DataType>::LinkList(DataType *x, int n) {
    first = new Node<DataType>;
    Node<DataType> *end = first;
    for (int i = 0; i < n; ++i) {
        Node<DataType> *s = new Node<DataType>;
        s->data = x[i];
        end->next = s;
        end = s;
    }
    end->next = NULL;
}

template<class DataType>
DataType LinkList<DataType>::Delete(int i) {
    Node<DataType> *p = first;
    int count = 0;
    while (p != NULL && count < i - 1) {
        p = p->next;
        count++;
    }
    if (p == NULL || p->next == NULL)
        throw "Error: 位置异常";
    else {
        Node<DataType> *temp = p->next;
        DataType dataType = temp->data;
        p->next = temp->next;
        delete temp;
        return dataType;
    }
}

template<class DataType>
LinkList<DataType>::~LinkList() {
    while (first != NULL) {
        Node<DataType> *temp = first;
        first = first->next;
        delete temp;
    }
}

int main() {
    int x[] = {1, 2, 3, 4, 5};
    LinkList<int> linkList(x, 5);
    linkList.Insert(1, 666);
    linkList.PrintList();
    linkList.Delete(2);
    linkList.PrintList();
    cout << "获取: " << linkList.Get(1) << endl;
    cout << "长度: " << linkList.Length() << endl;
    cout << "666的位置: " << linkList.Locate(666) << endl;
}