pengyangxiaobai 2013-10-11 01:32 采纳率: 0%
浏览 1785

基于链表的算法分析之增删查改

  在链表描述中,集合中的元素都放在链表的节点中进行描述。链表中的节点不是一个数组元素,因此不能通过公式来映射定位某个元素。取而代之的是,每个节点中都包含了下一个节点的位置信息,链表的表头包含了第一个节点的位置信息。
  为了在集合中找到第k个元素,就必须从表头开始,遍历第1个到第k个节点。它的时间复杂度是O(k),平均时间复杂度为O(length)。
  为了在集合中删除第k个元素,就要先找到第k-1和第k个节点,使第k-1个节点的下一个节点位置信息指向第k+1个节点,然后释放第k个节点所占的空间。它的时间复杂度是O(k),平均时间复杂度为O(length)。
  插入和删除的过程很相似,首先要创建一个新的节点,然后找到第k-1个节点,在该节点的后面插入新的节点,并把第k-1个节点、新的节点的下一个节点位置信息进行适当设置。它的时间复杂度是O(k),平均时间复杂度为O(length)。
  采用数组描述方法的集合仅需要能够保存所有元素的空间以及保存集合最大尺寸所需要的空间。链表描述需要除集合元素本身的空间意外,还需要额外的空间,用例保存链接节点指向下一个节点位置的指针。但一般情况下,链表描述要比数值描述的空间利用率高得多。
  虽然数组描述、链表描述插入和删除操作的平均时间复杂度均为O(length),但由于移动元素的操作比遍历元素的操作的开销要大得多,所以采用链表描述所实现的插入和删除操作要比数组描述执行得更快。而采用数组描述可以在常数时间内访问第k个元素,而在链表中,这种操作所需要的时间是O(k)。

根据以上算法写出此算法的检索、插入和删除指定位置元素的操作的函数。(只写出一个思路也可以)

  • 写回答

1条回答

  • Heart09 2015-04-08 09:25
    关注

    其实刚开始学习变成,都是一种无从下手的感觉。多练练就好多了。这里
    手写了一个大概原型,实现了push_item_front,其它的你自己来实现吧,写完之后自己写一些测试用例测试一下。不是很难的。

    template <typename T>
    class ListT
    {
    public:
            typedef struct _ITEM
            {   
                    T data;
                    struct _ITEM *next;
            } Item;
    
    public:
            ItemListT() : n(0), m_head(NULL), m_tail(NULL)
            {   
            }   
    
            ~ItemListT()
            {   
                    clear();
            }   
    
            // push item at front, ++n, return 0 for success, -1 for failed
            int push_item_front(T &t) 
            {   
                    Item *it = new Item;
                    if(NULL == it) // new failed
                    {   
                            return -1; 
                    }   
    
                    if((NULL == m_head) && (NULL == m_tail))
                    {   
                            m_head = m_tail = it;
                    }
                    else
                    {
                            it->next = m_head;
                            m_head = it;
                    }
                                    ++n;
            }
    
            // push item at back, ++n, return 0 for success, -1 for failed
            int push_item_back(T &t);
            // pop item from front, ++n
            T pop_item_front();
            // pop item from back, ++n
            T pop_item_back();
    
            // add item at k pos, ++n, return 0 for success, -1 for failed
            int add_item_k(T &t, int k);
            // delete item at k pos, --n, return 0 for success, -1 for failed
            int del_item_k(int k);
            // get item at k pos, return 0 for success, -1 for failed
            int get_item_k(T &t, int k);
            // modify item at k pos, return 0 for success, -1 for failed
            int mod_item_k(T &t, int k);
    
            // clear all items
            void clear();
            // is empty, return true for empty, false for not empty
            bool is_empty();
    
    protected:
            // head, tail
            Item *m_head;
            Item *m_tail;
    
            // number
            int n;
    };
    
    评论

报告相同问题?

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名