链表节点的插入和删除

插入结点

下面我们先对插入结点这个功能具体分析一下：

1. 我们必须知道对哪个链表进行操作，所以表头指针head是必须知道的。
2. 为了确定插入位置，插入位置前的结点指针pGuard是必须是知道的。
3. 用一个newnode指针来接受新建的结点。
4. 如果要插入的位置是表头，由于操作的是表头指针而不是一个结点，所以要特殊处理。
5. 在插入结点的过程中，始终要保持所有的结点都在我们的控制范围内，保证链表的完整性。为了达到这一点，我们采用先连后断的方式：先把新结点和它的后继结点连接，再把插入位置之前的结点与后继结点断开，并与新结点连接。如下图9.6.3所示。

做完了分析，我们可以开始编写插入函数了。为了简单起见，我们规定新结点插入位置为数据是关键字的结点之后，这样就可以使用刚才编写好的search函数了。如果该结点不存在，则插入在表头。则插入函数如下：

void insert(node * &head,char keyWord,char newdata)//keyWord是查找关键字符
{
    node *newnode=new node;//新建结点
    newnode->data=newdata;//newdata是新结点的数据
    node *pGuard=search(head,keyWord);//pGuard是插入位置前的结点指针
    if (head==NULL || pGuard==NULL)//如果链表没有结点或找不到关键字结点
    {//则插入表头位置
        newnode->next=head;//先连
        head=newnode;//后断
    }
    else//否则
    {//插入在pGuard之后
        newnode->next=pGuard->next;//先连
        pGuard->next=newnode;//后断
    }
}

删除结点

与插入数据类似，数组为了保持其顺序存储的特性，在删除某个数据时，其后的数据都要依次前移。而链表中结点的删除仍然只要对结点周围小范围的操作就可以了，不必去修改其他的结点。仍然我们先要来具体分析删除结点这个功能：

1. 我们必须知道对哪个链表进行操作，所以表头指针head是必须知道的。
2. 一般来说，待删除的结点是由结点的数据确定的。然而我们还要操作待删除结点之前的结点（或指针），以连接前后两段链表。之前所写的search函数只能找到待删除的结点，却无法找到这个结点的前趋结点。所以，我们只好放弃search函数，另起炉灶。
3. 令pGuard指针为待删除结点的前趋结点指针。
4. 由于要对待删除结点作内存释放，需要有一个指针p指向待删除结点。
5. 如果待删除结点为头结点，则我们要操作表头head，作为特殊情况处理。
6. 在删除结点的过程中，仍然要始终保持所有的结点都在我们的控制范围内，保证链表的完整性。为了达到这一点，我们还是采用先连后断的方式：先把待删除结点的前趋结点和它的后继结点连接，再把待删除结点与它的后继结点断开，并释放其空间。如下图9.6.4所示。
7. 如果链表没有结点或找不到待删除结点，则给出提示信息。

由于delete是C++中的保留字，我们无法用它作为函数名，所以只好用Delete代替（C++是大小写敏感的，Delete和delete是不同的）。都准备好了，我们就可以开始写函数了：

void Delete(node * &head,char keyWord)//可能要操作表头指针，所以head是引用
{
    if (head!=NULL)//如果链表没有结点，就直接输出提示
    {
        node *p;
        node *pGuard=head;//初始化pGuard指针
        if (head->data==keyWord)//如果头结点数据符合关键字
        {
            p=head;//头结点是待删除结点
            head=head->next;//先连
            delete p;//后断
            cout <<"The deleted node is " <<keyWord <<endl;
            return;//结束函数运行
        }
        else//否则
        {
            while (pGuard->next!=NULL)//当pGuard没有达到表尾
            {
                if (pGuard->next->data==keyWord)//如果pGuard后继结点数据符合关键字
                {
                    p=pGuard->next;//pGuard后继结点是待删除结点
                    pGuard->next=p->next;//先连
                    delete p;//后断
                    cout <<"The deleted node is " <<keyWord <<endl;
                    return;//结束函数运行
                }
                pGuard=pGuard->next;//pGuard指针向后移动
            }
        }
    }
    cout <<"The keyword node is not found or the link list is empty!" <<endl;//输出提示信息
}