关于list－（2） 双向list

 

1.实现双向链表删除一个节点P，在节点P后插入一个节点，写出这两个函数
答：

//假设线性表的双向链表存储结构
typedef struct DulNode{
    struct DulNode *prior;  //前驱指针
     ElemType data;    //数据
     struct DulNode *next;  //后继指针
}DulNode,*DuLinkList;

//删除操作
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e)
{
  if(!(p=GetElemP_DuL(L,i))) //此处得到i位置的节点指针，如果有需要也得写出具体函数实现
    return ERROR;
  e=p->data;
  p->prior->next=p->next;
  p->next->prior=p->pror;
  free(p);
  return OK;
}

//插入操作
Status ListInsert_DuL(DuLinkList &L,int i,ElemType &e)
{
  if(!(p=GetElemP_DuL(L,i)))
    return ERROR;
  if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) 
    return ERROR;

  s->data=e;
  s->prior=p->prior;
  p->prior->next=s;
  s->next=p;
  p->prior=s;
  return OK;
}

 

 

2. 有双向循环链表结点定义为：
struct node
{ int data;
struct node *front,*next;
};
有两个双向循环链表A，B，知道其头指针为：pHeadA,pHeadB，请写一函数将两链表中data值相同的结点删除
BOOL DeteleNode(Node *pHeader, DataType Value)
{
 if (pHeader == NULL) return;
 BOOL bRet = FALSE;
 Node *pNode = pHead;
 while (pNode != NULL)
 {
  if (pNode->data == Value)
  {
   if (pNode->front == NULL)
   {
      pHeader = pNode->next;
      pHeader->front = NULL;
   }
   else
   {
    if (pNode->next != NULL)
    {
    pNode->next->front = pNode->front;
    }
    pNode->front->next = pNode->next;
   }
   Node *pNextNode = pNode->next;
   delete pNode;
   pNode = pNextNode;
   bRet = TRUE;
   //不要break或return, 删除所有
  }
  else
  {
   pNode = pNode->next;
  }
 }
 return bRet;
}
void DE(Node *pHeadA, Node *pHeadB)
{
 if (pHeadA == NULL || pHeadB == NULL)
 {
  return;
 }
 Node *pNode = pHeadA;
 while (pNode != NULL)
 {
  if (DeteleNode(pHeadB, pNode->data))
  {
   if (pNode->front == NULL)
   {
    pHeadA = pNode->next;
    pHeadA->front = NULL;
   }
   else
   {
    pNode->front->next = pNode->next;
    if (pNode->next != NULL)
    {
     pNode->next->front = pNode->front;
    }
   }
   Node *pNextNode = pNode->next;
   delete pNode;
   pNode = pNextNode;
  }
  else
  {
   pNode = pNode->next;
  }
 }
}