单链表的插入删除

按位序插入（带头结点）

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e（带头结点）

 
typedef struct LNode
{
  ElemType data;
  struct LNode* next;
}LNode,*LinkList;
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L,int i,ElemType e)
{
  if(i<1)
    return false;
  LNode *p;//指针p指向当前扫描到的结点
  int j=0;//当前p指向的是第几个结点
  p=L;//L指向头结点，头结点是第0个结点（不存数据）
  while(p!=NULL&&j<i-1)//循环找到第i-1个结点
  {
    p=p->next;
    j++;
  }
  if(p==NULL)//i值不合法
    return false;
  LNode* s=(LNode*)malloc(sizeof(LNode));
  s->data=e;
  s->next=p->next;
  p->next=s;//将结点s连到p之后
  return true;//插入成功
  
}

按位序插入（不带头结点）

ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e

• 与带头结点的区别：不存在“第0个”结点，因此i=1时需要特殊处理，因为如果不带头结点，则插入、删除第一个元素时，需要更改头指针L

bool ListInsert(LinkList& L,int i,ElemType e)
{
  if(i<1)
    return false;
  if(i==1)//插入第i个结点的操作与其他节点不同
  {
    LNode* s=(LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=L;
    L=s;//头指针指向新节点
    return true;
  }
  LNode* p;//指针p指向当前扫描到的结点
  int j=1;//当前p指向的是第几个结点
  p=L;//p指向第1个结点（注意：不是头结点）
  while(p!=NULL&&j<i-1)
  {
    //循环找到第i-1个结点
    p=p->next;
    j++;
  }
  if(p==NULL)//i值不合法
    return false;
  LNode* s=(LNode*)malloc(sizeof(LNode));
  s->data=e;
  s->next=p->next;
  p->next=s;
  return true;//插入成功
}
typedef struct LNode
{
  Elemtype data;
  struct LNode* next;
}LNode,*LinkList;

指定结点的后插操作

bool InsertNode(LNode* p,Elemtype e)
{
  if(p==NULL)
    return false;
  LNode* s=(LNode*)malloc(sizeof(LNode));
  if(s==NULL)
    return false;
  s->data=e;
  s->next=p->next;
  p->next=s;
  return true;
}
typedef struct LNode
{
  ElemType data;
  struct LNode* next;
}LNode,*LinkList;

指定结点的前插操作

//前插操作：在p结点之前插入结点s
bool InsertPriorNode(LNode* p,LNode* s)
{
  if(p==NULL||s==NULL)
    return false;
  s->next=p->next;
  p->next=s;
  ElemType temp=p->data;
  p->data=temp;
  return true;
}

按位序删除（带头结点）

ListDelet(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(LinkList& L,int i,ElemType& e)
{
  if(i<1)
    return false;
  LNode* p;
  int j=0;
  p=L;
  while(p!=NULL&&j<i-1)
  {
    p=p->next;
    j++;
  }
  if(p==NULL)
    return false;
  if(p->next==NULL)
    return false;
  LNode* p=p->next;
  free(q);
  return true;
}