提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

数据结构(05)_链表01（单链表、静态单链表、单向循环链表）

2023-02-18 16:41:51 时间

  1.线性表的链式存储结构1.1.链式存储的定义：

  为了表示每个数据元素与其直接后继之间的逻辑关系，数据元素除过存储本身的信息之外，还需要存储其后继元素的地址信息。

  链式存储结构的逻辑结构：

  1.2.单链表

  单链表中的节点定义：

注意：这里的struct是用来定义一个类，与class的访问属性相反，默认为public单链表的内部结构：头节点在单链表中的意义是：辅助数据元素的定位，方便插入和删除，因此，头节点不存储实际的数据。

  1.3.单链表的插入与删除：

  插入：

   node->value = e;

    node->next = current->next;
    Current->next = node;

  删除：

   toDel = current->next;

    current->next = toDel->nex;
    delete toDel;

  2.单链表的实现2.1.设计要点和实现

  类族结构：

  — 类模板，通过头节点访问后继节点— 定义内部节点的类型Node，用于描述数据域和指针域— 实现线性表的关键操作，增、删、查等。

   template < typename T >

    class LinkList : public List
    {
    protected:
        struct Node : public Object
        {
            Node * next;
            T value;
        };
        int m_length;
        mutable Node m_header;
        // 当前所找到的节点不是要直接操作的节点，要操作的是该节点的next
        Node *position(int i) const
    public:
        LinkList()
        bool insert(const T& e)
        bool insert(int index, const T& e)
        bool remove(int index)
        bool set(int index, const T& e)
        T get(int index)
        bool get(int index, T& e) const
        int length() const
        void clear()
        ~LinkList()
    };

  2.2.隐患和优化

  优化：代码中多个函数存在对操作节点的定位逻辑。可以将该段代码实现为一个函数。

   Node *position(int i) const

        {
            Node *ret = reinterpret_cast(&m_header);
            for(int p=0; pnext;
            }
            return ret;
        }

  隐患：

   L;// 抛出异常，分析为什么我们没有定义 Test 对象，但确抛出了异常原因在于单链表头节点构造时会调用泛指类型的构造函数 解决方案：头节点构造时单向循环链表，避免调用泛指类型的构造函数，也即是说要自定义头节点的类型，并且该类型是一个匿名类型

   mutable struct : public Object

        {
            char reserved[sizeof(T)];
            Node *next;
    }m_header;

注意：这里我们自定义都头结点类型和Node的内存结构上要一模一样（不要将两个成员变量的位置交换）。

  22.3 单链表的最终实现

   template

    class LinkList : public List
    {
    protected:
        int m_length;
        int m_step;
        struct Node : public Object
        {
            Node* next;
            T value;
        };
        // 游标,获取游标指向的数据元素,遍历开始前将游标指向位置为0的数据元素,通过节点中的next指针移动游标
        Node* m_current;
        // 构造头节点时，会调用泛指类型的构造函数，如果泛指类型构造函数中抛出异常，将导致构造失败
        //mutable Node m_header;
        // 为了避免调用泛指类型的构造函数，自定义头节点的类型(内存结构上要一模一样)，并且该类型是一个匿名类型（没有类型名）
        mutable struct : public Object
        {
            Node *next;
            char reserved[sizeof(T)];
        }m_header;
        Node* position(int index) const
        {
            Node* ret = reinterpret_cast(&m_header);
            for(int p=0; pnext;
            }
            return ret;
        }
        virtual Node* create()
        {
            return new Node();
        }
        virtual void destroy(Node* pNode)
        {
            delete pNode;
        }
    public:
        LinkList()
        {
            m_header.next = NULL;
            m_length = 0;
            m_step = 0;
            m_current = NULL;
        }
        int find(const T& e) const
        {
            int ret = -1;
            Node* node = m_header.next;
            for(int i=0; ivalue == e)
                {
                    ret = i;
                    break;
                }
                node = node->next;
            }
            return ret;
        }
        bool insert(const T& e)
        {
            return insert(m_length, e);
        }
        bool insert(int index, const T& e)
        {
            bool ret = (index>=0) && (indexnext = current->next;
                    current->next = node;
                    node->value =e;
                    m_length++;
                }
                else
                {
                    THROW_EXCEPTION(NoEnoughMemoryException, "no enough memory to insert node.");
                }
            }
            return ret;
        }
        bool remove(int index)
        {
            bool ret = (index>=0) && (indexnext;
                if( toDel ==  m_current)
                {
                    m_current = toDel->next;    // 确保当前元素删除后m_current指向正确的位置
                }
                current->next = toDel->next;
                destroy(toDel);
                m_length--;
            }
            return ret;
        }
        bool set(int index, const T& e)
        {
            bool ret = (index>=0) && (indexnext->value = e;
            }
            return ret;
        }
        virtual T get(int index) const
        {
            T ret;
            if(get(index, ret))
            {
                return ret;
            }
            else
            {
                THROW_EXCEPTION(IndexOutOfBoundsException, "index out of range.");
            }
        }
        bool get(int index, T& e) const
        {
            bool ret = (index>=0) && (indexnext->value;
            }
            return ret;
        }
        void traverse(void)     //O(n^2)
        {
            for(int i=0; inext = this->m_header.next;
        }
    public:
        bool insert(const T& e)
        {
            return insert(this->m_length, e);
        }
        bool insert(int index, const T& e)
        {
            bool ret = true;
            index = index % (this->m_length + 1);   // 可插入点=length+1
            ret = LinkList::insert(index, e);
            if(index == 0)
            {
                last_to_first();
            }
            return ret;
        }
        bool remove(int index)
        {
            bool ret = true;
            index = mod(index);
            if(index == 0)
            {
                Node* toDel = this->m_header.next;
                if(toDel != NULL)   // 类似于判断index是否合法
                {
                    this->m_header.next = toDel->next;
                    this->m_length--;
                    if(this->m_length > 0)
                    {
                        last_to_first();
                        if(this->m_current == toDel)
                        {
                            this->m_current = toDel->next;
                        }
                    }
                    else
                    {
                        this->m_current = NULL;
                        this->m_header.next = NULL;
                        this->m_length = 0;
                    }
                }
                else
                {
                    ret = false;
                }
            }
            else
            {
                ret = LinkList::remove(index);
            }
            return ret;
        }
        T get(int index)
        {
            return LinkList::get(mod(index));
        }
        bool get(int index, T& e)
        {
            return LinkList::get(mod(index), e);
        }
        bool set(int index, const T& e)
        {
            return LinkList::set(mod(index), e);
        }
        int find(const T& e) const
        {
            int ret = -1;
            Node* node = this->m_header.next;
            for(int i=0; im_length; i++)
            {
                if(node->value == e)
                {
                    ret = i;
                    break;
                }
                node = node->next;
            }
            return ret;
        }
        bool move(int i, int step)
        {
            return LinkList::move(mod(i), step);
        }
        bool end()
        {
            return ( (this->m_current == NULL) || (this->m_length == 0) );
        }
        void clear()
        {
            if(this->m_length > 1)
            {
                remove(1);
            }
            if(this->m_length == 1)
            {
                Node* toDel = this->m_header.next;
                this->m_current = NULL;
                this->m_header.next = NULL;
                this->m_length = 0;
                this->destroy(toDel);
            }
        }
        ~CircleLinkList()
        {
            clear();
        }
    };

本文共 629 个字数,平均阅读时长 ≈ 2分钟

相关文章