最近在linux了一个简单的单向链表,直接上代码

链表头文件   list.h

#ifndef _LIST_H_
#define _LIST_H_

typedef int T;

template<typename T>
class List
{
private:
    struct Node
    {
        T      data;
        Node*  next;
        Node(const T& d=T()):data(d),next(NULL){} //零初始化
    };
    Node* head;//头指针,用来保存头节点的地址
    int len;
public:
    List():head(NULL),len(0){}
    List(const List& l);
    void operator=(const List& l);
    ~List();
    T getElementAtIndex(int index)const;//取得链表中指定位置的元素值
    List<T>& push_front(const T& d);//前插
    List<T>& push_back(const T& d); //尾插
    int size()const;//获取链表中节点个数
    Node*& getptr(int pos); //在链表中找指向指定位置的指针
    List<T>& insert(const T& d,int pos); //在任意位置插入
    void travel()const; //遍历
    void clear(); //清空链表
    void erase(int pos); //删除链表中指定位置的元素
    int find(const T& d)const; //查找指定数值的元素在链表中出现的位置
    void remove(const T& d); //删除链表中指定的元素
    void set(int pos,const T& d);
    bool empty()const;
    const T& front()const;
    const T& back()const;
    void reverse();//链表元素倒置
};

#endif

链表实现文件 list.cpp

#include <iostream>
#include <string>
#include "list.h"

using namespace std;

template<typename T>
List<T>::List(const List<T>& l)
{
    len = l.len;
    Node* items[len];
    for(int i=0;i<len;i++)
    {
        items[i] = new Node(l.getElementAtIndex(i));
    }
    for(int i=0;i<len-1;i++)
    {
        items[i]->next = items[i+1];
    }
    head = items[0];
}

template<typename T>
void List<T>::operator=(const List<T>& l)
{
    clear();    
    len = l.len;
    Node* items[len];
    for(int i=0;i<len;i++)
    {
        items[i] = new Node(l.getElementAtIndex(i));
    }
    for(int i=0;i<len-1;i++)
    {
        items[i]->next = items[i+1];
    }
    head = items[0];
}

template<typename T>
List<T>::~List()
{
    clear();
}

//取得链表中指定位置的元素值
template<typename T>
T List<T>::getElementAtIndex(int index)const  
{
    if(index < 0 || index >= len) throw "索引位置越界";
    if(index == 0) return head->data;
    Node* p = head;
    for(int i=1;i<index;i++)
    {
        p = p->next;
    }
    return p->next->data;
}

//前插
template<typename T>
List<T>& List<T>::push_front(const T& d)
{
    insert(d,0);
    return *this;
}

//后插
template<typename T>
List<T>& List<T>::push_back(const T& d)
{
    insert(d,len);
    return *this;
}

//获取链表中节点个数
template<typename T>
int List<T>::size()const
{
    return len;
}
    
//在链表中找指向指定位置的指针
template<typename T>
typename List<T>::Node*& List<T>::getptr(int pos)
{
    if(pos < 0 || pos > len) pos = 0;
    if(pos == 0) return head;
    Node* p = head;
    for(int i=1;i<pos;i++)
    {
        p = p->next;
    }
    return p->next;
}

//在任意位置插入节点
template<typename T>
List<T>& List<T>::insert(const T& d,int pos)
{
    Node*& pn = getptr(pos);
    Node* p = new Node(d);
    p->next = pn;
    pn = p;
    ++len;
    return *this;
}

//遍历
template<typename T>
void List<T>::travel()const
{
    Node* p = head;
    while(p)
    {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
}

//清空链表
template<typename T>
void List<T>::clear()
{
    while(head)
    {
        Node* p = head->next;
        delete head;
        head = p;
    }
    len = 0;
}
    
//删除链表中指定位置的节点
template<typename T>
void List<T>::erase(int pos)
{
    if(pos < 0 || pos >= len) return;//有效位置为0~len-1
    Node*& pn = getptr(pos);
    Node* p = pn;
    pn = pn->next;
    delete p;
    --len;
}

//查找指定数值的节点在链表中出现的位置
template<typename T>
int List<T>::find(const T& d)const
{
    Node* p = head;
    int pos = 0;
    while(p)
    {
        if(p->data == d)
          return pos;
        else
          p = p->next;
        ++pos;
    }
    return -1;
}
    
//删除链表中指定数值的节点
template<typename T>
void List<T>::remove(const T& d)
{
    int pos;
    while((pos = find(d))!= -1)
    {
        erase(pos);
    }
}

//修改指定位置的节点数据
template<typename T>
void List<T>::set(int pos,const T& d)
{
    if(pos < 0 || pos >= len) return;
    getptr(pos)->data = d;
}

//判断链表是否为空
template<typename T>
bool List<T>::empty()const
{
    return head == NULL;
}

//取得链表中第一个节点数据
template<typename T>
const T& List<T>::front()const
{
    if(empty()) throw "空";
    return head->data;
}

//取得链表中最后一个节点数据
template<typename T>
const T& List<T>::back()const
{
    if(empty()) throw "空";
    Node* p = head;
    while(p->next)
    {
        p = p->next;
    }
    return p->data;
}

//将链表中的元素倒置
template<typename T>
void List<T>::reverse()
{
    if(head == NULL) return;
    Node *pre,*cur,*next;
    pre = head;
    cur = head->next;
    while(cur)
    {
        next = cur->next;
         cur->next = pre;
         pre = cur;
         cur = next;
     }
     head->next = NULL;
     head = pre;
}


template class List<T>; // 显式实例化

链表测试文件 listTest.cpp

#include <iostream>
#include "list.h"

//typedef int T;
using namespace std;

int main()
{
    List<T> l;
    List<T> m;
    l.push_front(5); //5
    l.push_front(8); //8 5
    l.push_front(20);// 20 8 5
    l.insert(9,2); // 20 8 9 5
    l.insert(8,100); //6 20 8 9 5
    l.insert(11,-10);//11 6 20 8 9 5
    l.insert(9,2);//11 6 1 20 8 9 5
    l.push_back(10).push_back(19);//11 8 9 20 8 9 5 10 19
    l.travel();
    l.reverse();
    l.travel();

    l.remove(8);
    l.remove(9);
    l.set(1,33);
    l.set(l.find(19),-8);

//    cout << l.front() << "      " << l.back() << endl;
    l.travel();  // 11 33 5 10 -8

//    while(!l.empty()) l.erase(0);
 //   cout << l.size() << endl;
    
 //   cout << l.getElementAtIndex(0) << endl;
    m.insert(-9,0);
    m.insert(13,1);
    m.push_front(-5);
    m.push_back(2);
    cout << "========m链表原始值======" << endl;
    m.travel();// -5 -9 13 2

    m = l;
    cout <<"==========将链表m中元素倒置==========" << endl;
    m.reverse();
    m.travel();
    cout <<"===========程序结束======" << endl;

    return 0;
}


Logo

更多推荐