线性表链式存储结构的实现的使用

摘要：本文主要将单链表类进行了实现，并且进行了验证。

SimpleLinkList.h

#ifndef _SIMPLELINKLIST_
#define _SIMPLELINKLIST_
#include<stddef.h>

template<class ElemType>
struct Node   //创建节点结构体
{
    ElemType data;  //节点的数据
    Node<ElemType> *next;   //节点的指针

    Node();  //构造函数，创造一个节点
    Node(ElemType item,Node<ElemType> *link=NULL);  //有参构造，创造有个有元素并且后继指针指向link的节点
};

template<class ElemType>
class SimpleLinkList {
protected:
    Node<ElemType> *head;   //头结点指针
    Node<ElemType> *GetElemPtr(int position)const; //返回第position位置的指针
public:
    SimpleLinkList();  //构造函数
    void Mypush_back(ElemType e);   //向链表的尾部添加元素
    void Myshow();  //遍历一遍链表
    virtual ~SimpleLinkList();  //析构函数
    int Lence()const;   //计算线性表的长度
    bool Empty()const; //判断链表是否为空
    void Clear();  //清空链表
    bool GetElem(int position,ElemType &e)const;  //获取某一个位置的元素
    bool SetElem(int position, const ElemType &e);  //在某一个位置设置元素
    bool Insert(int position, const ElemType &e);  //在链表某位置插入元素/节点
    bool Delete(int position, ElemType &e);  //删除某个位置的元素，并且将删除的值用e返回
};



#endif // !_SIMPLELINKLIST_

SimpleLinkList.cpp

#include "SimpleLinkList.h"
#include<stddef.h>
#include<iostream>

using namespace std;


template<class ElemType>
Node<ElemType>::Node() {
    next = NULL;
}

template<class ElemType>
Node<ElemType>::Node(ElemType item, Node<ElemType> *link) {
    data = item;
    next = link;
}

template<class ElemType>
Node<ElemType>* SimpleLinkList<ElemType>::GetElemPtr(int position)const {
    Node<ElemType> *tmpPtr = head;
    int pos = 0;

    while (tmpPtr!=NULL && pos<position) {
        pos++;
        tmpPtr = tmpPtr->next;
    }
    if (tmpPtr!=NULL && pos==position) {
        return tmpPtr;
    }
    else
    {
        return NULL;
    }
}

template<class ElemType>
SimpleLinkList<ElemType>::SimpleLinkList() {  //创建一个新的链表
    head = new Node<ElemType>;
}

template<class ElemType>
void SimpleLinkList<ElemType>::Mypush_back(ElemType e) {  //向链表中添加元素
    Node<ElemType> *newnode = new Node<ElemType>;
    newnode->data = e;
    newnode->next = NULL;
    Node<ElemType> *ptr = new Node<ElemType>;
    ptr = head;
    while (ptr->next!=NULL)
    {
        ptr = ptr->next;
    }
    if (ptr->next==NULL) {
        ptr->next = newnode;
    }
}

template<class ElemType>
void SimpleLinkList<ElemType>::Myshow() {
    for (Node<ElemType> *p = head->next;p!=NULL;p=p->next) {
        cout << p->data << endl;
    }
}

template<class ElemType>
SimpleLinkList<ElemType>::~SimpleLinkList() {  //创建一个新的链表
    //Clear();
    delete head;
}

template<class ElemType>
int SimpleLinkList<ElemType>::Lence()const {
    int count = 0;
    for (Node<ElemType> *ptr = head->next; ptr != NULL;ptr=ptr->next) {
        count++;
    }
    return count;
}

 template<class ElemType>
 bool SimpleLinkList<ElemType>::Empty()const {
     return head->next = NULL;
 }

 template<class ElemType>
 void SimpleLinkList<ElemType>::Clear() {
     ElemType e;
     if (!Empty()) {
         Delete(1,e);  //删除第一个位置处的元素即可
     }
 }

 template<class ElemType>
 bool SimpleLinkList<ElemType>::GetElem(int position, ElemType &e)const {
     if (position<1 || position>Lence()) {
         return false;
     }
     else {
         Node<ElemType> *ptr;
         ptr = GetElemPtr(position);
         e = ptr->data;
         return true;
     }
 }

 template<class ElemType>
 bool SimpleLinkList<ElemType>::SetElem(int position, const ElemType &e) {
     if (position<1 || position>Lence()) {
         return false;
     }
     else {
         Node<ElemType> *ptr;
         ptr = GetElemPtr(position);
         ptr->data=e;
         return true;
     }
 }

 template<class ElemType>
 bool SimpleLinkList<ElemType>::Insert(int position, const ElemType &e) {
     if (position<1 || position>Lence()+1) {
         return false;
     }
     else {
         Node<ElemType> *ptr;
         ptr = GetElemPtr(position-1);
         Node<ElemType> *newptr;
         newptr = new Node<ElemType>(e,ptr->next);  //做一个新的节点，并且后继指针指向第position个节点
         ptr->next = newptr; //让原来的ptr指向新的节点
         return true;
     }
 }

 template<class ElemType>
 bool SimpleLinkList<ElemType>::Delete(int position,ElemType &e) {
     if (position<1 || position>Lence()) {
         return false;
     }
     else {
         Node<ElemType> *ptr;
         ptr = GetElemPtr(position - 1);
         Node<ElemType> *nextPtr = ptr->next;  //为了获取原链表第position+1个位置的指针
         ptr->next = nextPtr->next;  //删除节点
         e = nextPtr->data;
         delete nextPtr;
         return true;
     }
 }

main.cpp

#include<iostream>
#include "SimpleLinkList.cpp"

using namespace std;

void test() {
    SimpleLinkList<int> s;
    s.Mypush_back(10);
    s.Mypush_back(20);
    s.Mypush_back(20);
    s.Mypush_back(20);
    s.Mypush_back(40);
    s.SetElem(5,50);
    s.Myshow();
    cout << s.Lence() << endl;
    int a;
    s.Delete(2,a);
    s.Myshow();
    s.Insert(2,a);
    s.Myshow();
    s.Clear();
    cout << s.Lence() << endl;
}

int main() {
    test();
    system("pause");
    return 0;
}