线性表的两种实现 -- 顺序表和链表(C++)

系统管理员 2022-08-22 11:29 166阅读 0赞

## 线性表抽象类声明 ##

#ifndef ADT_H
    #define ADT_H
    //线性表ADT
    template <typename E>
    class List{
    private:
        void operator =(const List){}   //赋值运算符
        List(const List&){}          //复制构造函数
    public:
        List(){}            //默认构造函数
        virtual ~List(){}  //析构函数
    
        //清空所有元素
        virtual void clear() = 0;
    
        //在当前位置插入元素item
        virtual void insert(const E& item) = 0;
    
        //list尾部添加一个元素
        virtual void append(const E& item) = 0;
    
        //删除并返回当前位置的元素
        virtual E remove() = 0;
    
        //设置当前位置为list的开始位置
        virtual void moveToStart() = 0;
    
        //设置当前位置为list的末尾位置
        virtual void moveToEnd() = 0;
    
        //当前位置左移一个位置，不改变元素
        virtual void prev() = 0;
    
        //当前位置右移一个位置，不改变元素
        virtual void next() = 0;
    
        //返回元素数量--即获取长度
        virtual int length() const = 0;
    
        //返回当前元素位置
        virtual int currPos() const = 0;
    
        //设置当前位置
        virtual void moveToPos(int pos) = 0;
    
        //获取当前元素
        virtual const E& getValue() const = 0;
    };
    #endif

--------------------

## 顺序表的实现 ##

#include "ADT.h"
    
    template <typename E>
    class AList : public List<E>{
    private:
        int maxSize;        //list 最大容量
        int listSize;       //list 当前元素个数
        int curr;           //当前元素位置
        E* listArray;       //list指针
    
    public:
        AList(int size = defaultSize){          //构造函数 
            maxSize = size;
            listSize = curr = 0;
            listArray = new E[maxSize];
        }
    
        ~AList(){ delete[] listArray; }            //析构函数
    
        void clear(){                           //重新初始化list
            delete [] AList;
            listSize = 0;
            listArray = new E[maxSize];
        }
    
        //在当前位置插入 it 元素
        void insert(const E& it){
            Assert(listSize < maxSize, "List capacity exceeded");
    
            for (int i = listSize; i > curr; i--)
                listArray[i] = listArray[i - 1];
            listArray[curr] = it;
            listSize++;
        }
    
        //末尾添加元素
        void append(const E& it){
            Assert(listSize < maxSize, "List capacity exceeded");
            listArray[listSize++] = it;
        }
    
        //删除并返回当前位置的元素
        E remove(){
            Assert(listSize < maxSize, "List capacity exceeded");
            E it = listArray[curr];
            for (int i = curr; i < listSize - 1; i++)
                listArray[i] = listArray[i + 1];
            listSize--;
            return it;
        }
    
        void moveToStart(){ curr = 0; }             //位置重置为start位置
        void moveToEnd(){ curr = listSize; }        //位置重置为end位置
        void prev(){ if (curr != 0) curr--; };      //上一个元素位置
        void next(){ if (curr < listSize) curr++ }; //下一个元素位置
    
        //返回list元素个数
        int length() const { return listSize };
    
        //返回当前元素位置
        int currPos() const { return curr };
    
        //设置当前list位置为 pos
        void moveToPos(int pos){
            Assert((pos >= 0) && (pos <= listSize), "pos out of range");
            curr = pos;
        }
    
        //获取当前位置元素
        const E& getValue() const {
            Assert((curr >= 0) && (curr <= listSize), "No current element");
            return listArray[curr];
        }
    };

--------------------

## 单链表的实现 ##

#include "ADT.h"
    
    //单链表结点定义
    template <typename E>
    class Link{
    public:
        E element;                          //节点的值
        Link* next;                         //next
        Link(const E& elemval, Link* nextval = NULL){
            element = elemval; 
            next = nextval;
        }
        Link(Link* nextval = NULL){
            next = nextval;
        }
    };
    
    template <typename E>
    class LList: public List<E>
    {
    private:
        Link<E>* head;
        Link<E>* tail;
        Link<E>* curr;
        int cnt;
    
        //初始化
        void init(){
            curr = tail = head = new Link<E>;
            cnt = 0;
        }
    
        //清空所有元素
        void removeall(){
            while (head != NULL){
                curr = head;
                head = head->next;
                delete curr;
            }
        }
    
    public:
        LList(int size = defalueSize){ init(); }            //构造函数
        ~LList(){ removeall(); }                           //析构函数
    
        void print() const;                                 //print List
        void clear(){ removeall(); init(); }                //clear List
    
        void insert(const E& it){
            curr->next = new Link<E>(it, curr->next);
            if (tail == currr)
                tail = curr->next;
            cnt++;
        }
    
        void append(const E& it){
            tail = tail->next = new Link<E>(it, NULL);
            cnt++;
        }
    
        E remove(){
            Assert(curr->next != NULL, "No element");
            E it = curr->next->element;             //保存数据
            Link<E>* ltemp = curr->next;            //保存链表节点
            if (tail == curr->next) tail = curr;    //重置尾节点
            curr->next = curr->next->next;          //删除节点
            delete ltemp;                           //释放空间
            cnt--;                                  //cnt - 1
            return it;
        }
    
        //移动至链表开始位置
        void moveToStart(){ curr = head; }
    
        //移动至链表尾端
        void moveToEnd(){ curr = tail; }            
    
        //上一个节点
        void prev(){
            if (curr == head) return;
            Link<E>* temp = head;
            while (temp->next != curr){
                temp = temp->next;
            }
            curr = temp;
        }
    
        //下一个节点
        void next(){
            if (curr != tail)
                curr = curr->next;
        }
    
        //返回长度
        int length() const { return cnt; }
    
        //链表当前位置
        int currPos() const{
            Link<E>* temp = head;
            int i;
            for (i = 0; curr != temp; i++){
                temp = temp->next;
            }
            return i;
        }
    
        //移动至链表的pos位置
        void moveToPos(int pos){
            Assert((pos >= 0) && (pos <= cnt), "Pos out of range");
            curr = head;
            for (int i = 0; i < pos; i++)
                curr = curr->next;
        }
        //获取当前元素
        const E& getValue() const {
            Assert(curr->next != NULL, "No Value");
            return curr->next->element;
        }
    };

--------------------

## 线性表两种实现方法的比较 ##

**空间方面：**  
顺序表的缺点：大小事先固定。虽然便于分配空间，但是元素只有少数的几个时造成空间的浪费。  
链表的优点：只有实际在链表中的对象需要空间，只要存在可用的内存空间分配，链表中元素的个数没有限制。

顺序表的优点是对于表中的每一个元素没有浪费空间，而链表需要在每个节点附加上一个指针。在可以大概估计出线性表长度的情况下，顺序表比链表有更高的空间效率。

--------------------

**随机访问元素：**  
取出线性表中第i个元素这样的按位置随机访问，使用顺序表更快些；通过next和prev可以很容易调整当前位置向前或向后，这两种操作需要的时间为O(1)。  
相比之下，单链表不能直接访问前面的元素，按位置只能从表头(或者当前位置)开始，直到找到那个特定的位置。假定表中每个位置是由prev和moveToPos平均访问到的，那么访问线性表第i个元素的操作所需的平均情况下时间和最差情况下时间都是O(n)。

--------------------

**插入和删除元素：**  
给出指向链表中合适位置的指针后，insert和remove函数所需要的时间仅为O(1)。  
而顺序表必须在数组内将其余元素向前或向后移动。这种方法所需的平均情况下时间和最差时间均为O(n)。  
对于许多应用，插入和删除是最主要的操作，因此他们的时间效率是举足轻重的。仅就这个原因而言，链表往往比顺序表更好。