C++简单实现顺序表与单链表

墨蓝 2022-06-12 07:56 180阅读 0赞

> ### 顺序表： ###

#include <assert.h>
    #include <iostream>
    using namespace std;
    
    typedef int Datatype;
    
    class SeqList
    {
    public:
        SeqList()
            :_array(NULL)
            ,_size(0)
            ,_capacity(0)
        {
        }
    
        SeqList(const SeqList& s)
        {
            _array = (Datatype*)malloc(s._size*(sizeof(Datatype)));
            memcpy(_array, s._array, s._size*(sizeof(Datatype)));
            _size = _capacity = s._size;
        }
    
        SeqList& operator=(SeqList& s)
        {
            free(_array);
            Swap(s);
            return *this;
        }
    
        void Swap(SeqList& s)
        {
            _array = s._array;
            _size = s._size;
            _capacity = s._capacity;
        }
    
        ~SeqList()
        {
            if (_array)
            {
                free(_array);
                _array = NULL;
                _size = _capacity = 0;
            }
        }
    
        void Print()
        {
            for (size_t i = 0; i < _size; i++)
            {
                cout << _array[i] << " ";
            }
            cout << endl;
        }
    
        void CheckCapcacity()
        {
            if (_size == _capacity)
            {
                _capacity = 2 * _capacity + 3;
                _array = (Datatype*)realloc(_array, _capacity*sizeof(Datatype));
                assert(_array);
            }
        }
    
        //后插
        void PushBack(Datatype x)
        {
            Insert(_size, x);
        }
    
        //前插
        void PushFront(Datatype x)
        {
            Insert(0, x);
        }
    
        //删除最后一个
        void PopBack()
        {
            Erase(_size);
        }
    
        //删除第一个
        void PopFront()
        {
            Erase(0);
        }
    
        //[]运算符重载
        Datatype& operator[](size_t pos)
        {
            assert(pos < _size);
            return _array[pos];
        }
    
        //pos位置前插入x
        void Insert(size_t pos, Datatype x)
        {
            assert(pos <= _size);
            CheckCapcacity();
            int end = (int)_size - 1;
            if (pos == 0)
            {
                while (end >= 0)
                {
                    _array[end + 1] = _array[end];
                    end--;
                }
                _array[0] = x;
            }
            else
            {
                while (end >= (int)pos)
                {
                    _array[end + 1] = _array[end];
                    end--;
                }
                _array[pos] = x;
            }
            _size++;
        }
    
        //删除pos位置的元素
        void Erase(size_t pos)
        {
            assert(pos < _size);
            //popfront的实现
            if (_size > 0)
            {
                if (pos == 0)
                {
                    int end = 0;
                    while (end < (int)_size - 1)
                    {
                        _array[end] = _array[end + 1];
                        end++;
                    }
                    _size--;
                }
                //popback的实现
                else if (pos == _size)
                {
                    _size--;
                }
                //erase
                else
                {
                    int end = pos;
                    while (end < (int)_size - 1)
                    {
                        _array[end] = _array[end + 1];
                        end++;
                    }
                    _size--;
                }
            }
            return; 
        }
    
    private:
        Datatype* _array;
        size_t  _size;
        size_t _capacity;
    };

> ### 单链表（不含头结点） ###

#include <iostream>
    #include <assert.h>
    using namespace std;
    
    typedef int DataType;
    
    struct SListNode
    {
        SListNode* _next;
        DataType _data;
    
        SListNode(DataType x)
            :_data(x)
            , _next(NULL)
        {}
    };
    
    typedef SListNode Node;
    
    class SList
    {
    public:
        SList()
            :_head(NULL)
            , _tail(NULL)
        {}
    
        SList(const SList& s)
            :_head(NULL)
            ,_tail(NULL)
        {
            Copy(s);
        }
    
        SList& operator=(const SList& s)
        {
            Destroy();
            Copy(s);
            return *this;
        }
    
        ~SList()
        {
            Destroy();
        }
    
    
        void Copy(const SList& s)
        {
            Node* cur = s._head;
            while (cur)
            {
                PushBack(cur->_data);
                cur = cur->_next;
            }
        }
    
        void Destroy()
        {
            Node* cur = _head;
            while (_head != NULL)
            {
                cur = _head;
                _head = cur->_next;
                delete cur;
            }
            _head = _tail = NULL;
        }
    
        void PushBack(DataType x)
        {
            if ((_head == NULL)&&(_tail == NULL))
            {
                _head = _tail = new Node(x);
            }
            else
            {
                _tail->_next = new Node(x);
                _tail = _tail->_next;
            }
        }
    
        void PopBack()
        {
            if (_head == NULL)
            {
                return;
            }
            else if (_head ->_next == NULL)
            {
                delete _head;
                _head = _tail = NULL;
            }
            else
            {
                Node* tmp = _head;
                while (tmp->_next->_next != NULL)
                {
                    tmp = tmp->_next;
                }
                _tail = tmp;
                tmp->_next = NULL;
            }       
        }
    
        void PushFront(DataType x)
        {
            if ((_head == NULL) && (_tail == NULL))
            {
                _head = _tail = new Node(x);
            }
            else
            {
                Node* tmp = new Node(x);
                tmp->_next = _head;
                _head = tmp;
            }
        }
    
        void PopFront()
        {
            if (_head == NULL)
            {
                return;
            }
            Node* cur = _head;
            _head = _head->_next;
            delete cur;
        }
    
        Node* Find(DataType x)
        {
            Node* tmp = _head;
            while (tmp)
            {
                if (tmp->_data == x)
                    return tmp;
                tmp = tmp->_next;
            }
            return NULL;
        }
    
        // 插入一个节点在pos的前面
        void Insert(Node* pos, DataType x)
        {
            assert(pos);
            if (pos == 0)
            {
                PushFront(x);
            }
            else
            {
                Node* cur = _head;
                while (cur->_next != pos)
                {
                    cur = cur->_next;
                }
                Node* tmp = new Node(x);
                tmp->_next = pos;
                cur->_next = tmp;
            }
        }
    
        void Erase(Node* pos)
        {
            assert(pos);
            if (pos == 0)
            {
                PopFront();
            }
            else if (pos->_next == NULL)
            {
                PopBack();
            }
            else
            {
                Node* cur = _head;
                while (cur->_next != pos)
                {
                    cur = cur->_next;
                }
                Node* tmp = cur->_next;
                cur->_next = tmp->_next;
                delete tmp;
            }
        }
    
        void Print()
        {
            Node* tmp = _head;
            while (tmp != NULL)
            {
                cout <<tmp->_data << "->";
                tmp= tmp->_next;
            }
            cout <<"NULL"<<endl;
        }
    
    private:
        Node* _head;
        Node* _tail;
    };