试写一算法,在 无头结点 的动态单链表上实现线性表操作 INSERT(L, i, b)







见到有个人是这样写的:

Status Insert(LinkList &L,int i,int b)
{//在无头结点链表L的第i个元素之前插入元素b
  p = L;
  q = (LinkList)malloc(sizeof(LNode));
  q.data = b;
  if (i == 1)
  {
    q.next = p;
    L = q;                             //插入在链表头部
  }
  else
  {
    while(--i>1)
    {
       p=p->next;
    }
    q->next = p->next;
    p->next = q;                     //插入在第i个元素的位置
  }
}//Insert




看不明白,所以我写了一个:

Status Insert(LinkList &L,int i,int b)
{                                     //在无头结点链表L的第i个元素之前插入元素b
    if (i <= 0)                        //位置不合法
    {
        return ERROR;
    }
    label = L;
    new = (LinkList)malloc(sizeof(LNode));   //给新元素结点初始化
    new->data = b;
    new->next = NULL;
    if (i == 1)                          //当插入位置在第一个元素之前时
    {
        if (L == NULL)                    //如果L此时为空表(没有首元结点)
        {
           new->next = NULL;
           L = new;
        }
        else                              //如果L此时非空(有首元结点)
        {
            new->next = label->next;
            label->next = new;
        }
    }
    else                                 //当插入位置不在第一个元素前时
    {
        j = 0;                           //按照1楼的提醒,这儿作了修改
        while (lable->next != NULL && j<i-1)
        {
            label = label->next;
            j++;
        }
        if (j != i-1) return ERROR;
                                              //不存在第i个元素,则ERROR
        new->next = label->next;
        label->next = new;           //插入在第i个元素的位置,原结点变为第i+1个
    }
    return(OK);
}//Insert



其中,

typedef struct LNode
{
  Elemtype data;
  struct LNode *next;
}LNode, *LinkList;



不知道是否两个都正确?

另:
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息
首元结点是指链表中存储线性表中第一个数据元素a1的结点。


头指针本身没有数据域,只是一个指针,不具有LNode型结点构造.L是头指针.

[此贴子已经被作者于2005-10-4 2:08:17编辑过]