发现某经典教材上的一个链表部分的小异常，不知是否是小弟我理解有误

2013-07-04

发现某经典教材上的一个链表部分的小错误，不知是否是我理解有误？最近在学数据结构，看的书是数据结构、算法

发现某经典教材上的一个链表部分的小错误，不知是否是我理解有误？
最近在学数据结构，看的书是<数据结构、算法与应用 -- C ++语言描述>，
发现程序3-15实现向链表中插入元素时，没有考虑在头结点之前插入的情况(k = 0)，代码如下：

template <typename T>
ChainList<T>& ChainList<T>::Insert(int k , const T& v)
{
if(k < 0) throw out_of_range("k < 0 是不行的");

ChainNode<T> * p = head;

for(int index  = 1 ; index < k && p; k++ )
{
p = p->link;
}
if(k > 0 && !p) throw out_of_range(" 不存在第k 个元素");

ChainNode<T> *y = new ChainNode<T>;

y->data = v;
if(k){
y->link = p->link;
p->link = y;
}else
{
y->link = head;
head = y;
}

return *this;
}

不知道是我对题目的理解有误，还是那上面真的错了，还请各位大牛指点，。另外感觉上面实现代码稍有繁琐，能不能将最后的那个if-else合并成，谢谢了。链表数据结构 C++
[解决办法]
else那里处理的不是k=0的情况么。。
而且


for(int index  = 1 ; index < k && p; k++ )//这里应该不是k++是index++吧。。

[解决办法]


//1)这里跳过了 k=0的情况----已经考虑了k=0的情况了,这一步,先不处理 k=0的情况.
for(int index  = 1 ; index < k && p; k++ )     {         p = p->link;     } 
//2 这里分别处理了k>0 和 k=0 的情况了!

if(k){         y->link = p->link;         p->link = y;     }
else    {         y->link = head;         head = y;     } //这里处理了k=0 的情况了.
//相当于 
if(k！=0){         y->link = p->link;         p->link = y;     }
else //if (k==0)    
{         y->link = head;         head = y;     }

Ps :这个处理的方法,确实很经典,不愧是教科书!!!
[解决办法]
更正：



template <typename T>
ChainList<T>& ChainList<T>::Insert(int k , const T& v)
{
    if(k < 0)
    {
        throw out_of_range("k < 0 是不行的") 
 
    }
    else if( k == 0 )
    {
        ChainNode<T> *y = new ChainNode<T>;
        y->data = v;
        y->link = head;
        head = y;
    }
    else
    {
        ChainNode<T> * p = head;

        for(int index  = 1 ; index < k && p; k++ )
        {
            p = p->link;
        }
        if(k > 0 && !p) 
        {
            throw out_of_range(" 不存在第k 个元素");
        }
        else
        {

            ChainNode<T> *y = new ChainNode<T>;

            y->data = v;
            y->link = p->link;
            p->link = y;
        }
    }

    return *this;
}

热点排行