使用C++实现单向链表

简介: 版权声明:您好,转载请留下本人博客的地址,谢谢 https://blog.csdn.net/hongbochen1223/article/details/44682245 不多...
版权声明:您好,转载请留下本人博客的地址,谢谢 https://blog.csdn.net/hongbochen1223/article/details/44682245

不多说了,直接上代码:

注意:其中的Exception类请参考我的《使用C++实现的线性表》

#ifndef CHAIN_H
#define CHAIN_H

#include 
#include "Exception.h"

template
class  ChainNode;

template
class ChainIterator;

template
class Chain
{
    friend class ChainIterator;
public:
    Chain(){head = 0;}
    ~Chain();
    bool isEmpty() const { return head == 0;}
    int Length() const;
    bool Find(int k,T& x) const;
    int Search(const T& x) const;
    Chain& Delete(int pos,T& x);
    Chain& Insert(int pos,const T& x);
    Chain& add(const T& x);     //在链表的尾部添加一个元素
    void clear();                  //清楚链表中的元素
    T& get(int x);              //获取在x位置的元素
    void print();
private:
    ChainNode *head;
};

template
class ChainNode{
    friend class Chain;
    friend class ChainIterator;
private:
    T data;
    ChainNode *next;
};

/**链表遍历器**/
template
class ChainIterator{
public:
    T* initialize(const Chain& c){
        location = c.head;

        if(location)
            return &(location->data);
        else
            return 0;
    }

    T* Next(){
        location = location->next;
        if(location)
            return &(location->data);
        else
            return 0;
    }

private:
    ChainNode *location;
};

template
int Chain::Length() const
{
    ChainNode *current = head;

    int i  = 0;
    while(current){
        i++;
        current = current->next;
    }

    return i;
}

template
bool Chain::Find(int k, T &x) const
{
    ChainNode* current = head;
    int index = 1;

    while(index < k && current){
        current = current->next;
        index++;
    }

    if(current){
        x = current->data;
        return true;
    }

    return false;
}

template
int Chain::Search(const T &x) const
{
    ChainNode *current = head;
    int index = 1;

    while(current && current->data != x){
        current = current->next;
        index++;
    }

    if(current){
        return index;
    }

    return -1;
}

template
Chain& Chain::Delete(int pos, T &x)
{
    if(pos <= 0 || pos > Length())
        throw OutOfBounds();

    ChainNode* p = head;

    if(pos == 1){
        head = head->next;
    }else{
        ChainNode* q = head;

        for(int i = 1;i < pos-1 && q;i++)
            q = q->next;

        if(!q || !q->next)
            throw OutOfBounds();
        p = q->next;
        q->next = p->next;
    }

    x = p->data;
    delete p;

    return *this;
}

template
Chain& Chain::Insert(int pos, const T &x)   //在第pos个元素之后添加一个元素x
{
    if(pos < 0 || pos > Length())
        throw OutOfBounds();

    ChainNode* p = head;
    for(int i = 1;i < pos && p; i++)
        p = p->next;

    if(pos > 0 && !p)
        throw OutOfBounds();

    ChainNode* temp = new ChainNode();
     temp->data = x;
     if(pos){
         temp->next = p->next;
         p->next = temp;
     }else{
        temp->next = head;
        head = temp;
     }

    return *this;
}

template
void Chain::print()
{
    ChainNode* p = head;

    while(p){
        std::cout << p->data << "   ";
        p = p->next;
    }

    std::cout << std::endl;
}

template
Chain::~Chain()
{
    while(head){
        ChainNode* temp = head;
        head = head->next;
        delete temp;
    }

    head = 0;
}

template
Chain& Chain::add(const T &x)
{
    ChainNode *added = new ChainNode();
    added->data = x;
    added->next = 0;

    ChainNode *current = head;
    ChainNode *temp = current;

    while(current){
        temp = current;
        current = current->next;
    }

    if(temp){
        temp->next = added;
    }else{
        head = added;
    }

    return *this;
}

template
void Chain::clear()
{
    ChainNode *temp;

    while(head){
        temp = head->next;
        delete head;
        head = temp;
    }

    head = 0;
}

template
T& Chain::get(int x)
{
    if(x < 0)
        throw OutOfBounds();

    ChainNode *current = head;

    for(int i = 0; i < x &&  current; i++){
        current = current->next;
    }

    if(!current)
        throw OutOfBounds();

    return current->data;
}

#endif // CHAIN_H



目录
相关文章
|
24天前
|
C++
【链表】还不会用C++实现链表?一文教会你各种链表的实现
【链表】还不会用C++实现链表?一文教会你各种链表的实现
|
1月前
【数据结构】单链表之--无头单向非循环链表
【数据结构】单链表之--无头单向非循环链表
|
20天前
|
存储 缓存 C++
C++链表常用的函数编写(增查删改)内附完整程序
C++链表常用的函数编写(增查删改)内附完整程序
|
26天前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
36 0
|
1月前
|
存储 缓存 算法
C++链表解析:从基础原理到高级应用,全面掌握链表的使用
C++链表解析:从基础原理到高级应用,全面掌握链表的使用
49 0
|
2月前
|
C语言 C++
【c++】用c++实现带头双向循环链表
【c++】用c++实现带头双向循环链表
|
2月前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
29 0
|
2月前
|
存储
数据结构 模拟实现LinkedList单向不循环链表
数据结构 模拟实现LinkedList单向不循环链表
33 0
|
2月前
|
存储 算法 C++
【数据结构】链表—C/C++实现
【数据结构】链表—C/C++实现
60 1
|
2月前
|
存储 Python
如何在Python中实现单向链表和双向链表?
如何在Python中实现单向链表和双向链表?

热门文章

最新文章