链表的C++实现方法

链表好难啊，学了半天。>_<

#include
using namespace std;

template
class linkNode//节点类
{
public://这里可以是私有的，不过需要设置函数封装他，为了方便起见，将其设为公有
	T Data;
	linkNode* next;//下一个节点。
};


template
class linkList {
	linkNode* head;//链表的头结节点。
public:
    linkList();// 无参构造函数，建立只有头节点的空链表
    linkList(T a[], int n);// 有参构造函数，建立有n个元素的单链表
    ~linkList();// 析构函数
    int Length();// 求单链表的长度
    T Get(int i);// 查找第i个元素
    int Locate(T x);// 查找值为x的元素
    void Insert(int i, T x);// 在第i个元素处插入x
    bool Delete(int i);// 删除第i个节点
    void PrintList();// 遍历各个元素
};

template
linkList::linkList() {
    head = new linkNode;//生成头结点
    head->next = NULL;
}


template//构造函数
linkList::linkList(T a[], int n) {//尾插法：向后面一个一个插
    head = new linkNode;
    head->next = NULL;//新开辟一个空间就得初始化一下。
    linkNode* cur=head;//尾指针
    for (int i = 0; i < n; i++)
    {
        linkNode* p = new linkNode;
        p->Data = a[i];
        
        cur->next = p;//将新节点与当前链表相连，同时将上一个新加的节点的next初始化。
        cur = cur->next;//指向当前节点
    }
    cur->next = NULL;//最后还有一个cur的next元素未初始化，要特地初始化一下
}



template
linkList::~linkList() {//析构函数
    linkNode* cur = head;//记录
    linkNode* ptr = head;
    while (cur != NULL) {
        ptr = cur;
        cur = cur->next;//移向下一个
        delete ptr;
    }

}

template
int linkList::Length() {
    int sum = 0;
    linkNode* cur = head->next;
    while (cur != NULL)
    {
        sum++;
        cur = cur->next;
    }
    return sum;
}

template
T linkList::Get(int i) {
    linkNode* cur = head;
    int a = 0;
    while (cur != NULL && i != a) {
        cur = cur->next;
        a++;
    }

    if (cur == NULL)
    {
        cout << "超出范围";
        return 0;
    }
    else if (i == a)
        return cur->Data;
}

template
int linkList::Locate(T x) {
    linkNode* cur = head;
    int a = 0;
    while (cur != NULL) {
        cur = cur->next;
        a++;
        if (x == cur->Data)
            return a;


    }
    if (cur == NULL)
        return -1;
}

template
void linkList::Insert(int i, T x) {
    int count = 0;                // 计数
    linkNode* p = head;            // 将工作指针指向头节点
    while (p != NULL)
    {
        if (count == i - 1)        // 找第i-1个节点
        {
            linkNode* S = new linkNode;
            S->Data = x;
            S->next = p->next;
            p->next = S;
            
        }
        p = p->next;
        count++;
    }
}

template
bool linkList::Delete(int i)
{
    int count = 0;                // 计数
    linkNode* p = head;            // 将工作指针指向头节点
    while (p != NULL)
    {
        if (count == i - 1)
        {
            linkNode* q = p->next;// 暂存被删节点
            
            p->next = q->next;
            delete q;
            return true;
        }
        p = p->next;
        count++;
    }
    return false;
}

template
void linkList::PrintList()
{
    linkNode* p = head->next;    // 将工作指针指向第一个节点
    while (p != NULL)
    {
        cout << p->Data << " ";
        p = p->next;
    }
}

int main() {
    int a[10] = { 0,1,2,3,4,5,6,7,8,9 };

    linkList ll(a,10);
    cout << "最初链表为：";
    ll.PrintList();
    ll.Delete(2);
    cout << "n删除第二个元素后的链表为：";
    ll.PrintList();
    
    cout << "n删除后的第二个元素："<< ll.Get(2);
    ll.Insert(2, 11);
    cout << "n插入第二个元素后的链表：";
    ll.PrintList();
    cout << "n链表长度：" << ll.Length();
    cout<<"n9出现在第"< 
包括链表的方法
 
运行结果截图 

 再接再厉