Chinaunix首页 | 论坛 | 博客
  • 博客访问: 168965
  • 博文数量: 66
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 20
  • 用 户 组: 普通用户
  • 注册时间: 2016-06-23 15:21
文章分类

全部博文(66)

文章存档

2016年(66)

我的朋友

分类: LINUX

2016-05-27 14:06:52

在链表的第i个节点的后面插入一个新节点的基本算法如下:

(1)定位第i个节点。让指针q指向第i个节点,指针p指向需要插入的节点。

(2)链接后面指针。p-link = q->link。

(3)链接前面指针。q->link=p。


第一步:查找结点值(这里存在两种方法)

1:按序号查找结点值

在单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL。


按序号查找结点值的算法如下:

/*
参数:
LinkList L    头节点
int i            节点序号
*/

LNode GetElem(LinkList L,int i)
{
    //本算法取出单链表L(带头结点)中第i个位置的结点指针

    int j=1;  //计数,初始为1

    LNode *p = L->next;  //头结点指针赋给p  (此时,P就是第一个节点了

    if(i==0)
        return L;  //若i等于0,则返回头结点

    if(i<1)
        return NULL;  //若 i 无效,则返回 NULL

    //
 
       //从第1个结点开始找,查找第i个结点, 但i=1的时候,直接跳过while,返回p, 此时的p其实就是第一个节点;
      return p; //返回第i个结点的指针,如果i大于表长,p=NULL,直接返回p即可

2:按值查找表结点

从单链表第一个结点开始,由前往后依次比较表中各结点数据域的值,若某结点数据域的值等于给定值e,则返回该结点的指针。若整个单链表中没有这样的结点,则返回NULL。按值查找结点的算法如下:

LNode *LocateElem (LinkList L, ElemType e)
{
        //本算法查找单链表 L (带头结点)中数据域值等于e的结点指针,否则返回NULL
        LNode *p=L->next;

        while( p!=NULL && p->data!=e)  //从第1个结点开始查找data域为e的结点
                p=p->next;
        
        return p;  //找到后返回该结点指针,否则返回NULL
}

按值查找操作的时间复杂度为O(n)。


第二步:插入结点
  
      插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性,然后找到待插入位置的前驱结点,即第i-1个结点,再在其后插入新结点。


算法首先调用上面的按序号查找算法GetElem(L,  i-1),查找第i-1个结点。假设返回的第i-1个结点为*p,然后令新结,点*s的指针域指向*p的后继结点,再令结点*p的指针域指向新插入的结点*s。其操作过程如图所示。



                                               单链表的插入操作


实现插入结点的代码片段如下:

    p=GetElem(L, i-1) ;      // 语句①,查找插入位置的前驱结点

    s->next=p->next;       // 语句②,图中辑作步骤 1

    p->next=s;                // 语句③,图中操作步骤2

        算法中,语句②③的顺序不能颠倒,否则,当先执行p->next=s后,指向其原后继的指针就不存在了,再执行s->next = p->next时,相当于执行了 s->next=s,显然是错误的。本算法主要的时间开销在于查找第i-1个元素,时间复杂度为O(n)。若是在给定的结点后面插入新结点,则时间复杂度仅为O(1)。
阅读(5281) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~