数据结构基础(三).双链表（1）

#include <stdio.h> 
#include <malloc.h>

typedef struct dlist 
{
  int score;
  struct dlist *prev; //相对于单链表，双链表有前置节点
  struct dlist *next; 
}DL,*DP; //重命名双链节点类型为DL，双链指针类型为DP


DP createList() //创建空表
{
  DP head=NULL;
  head=(DP)malloc(sizeof(DL));
  if(NULL == head) //跟进检查，如果申请失败则提醒返回，将NULL放在左边是一种更安全的做法
  {
    printf("error:no enough memory!\n");
    return NULL;
  }
  head->score=0; //初始化头结点的score，这个地方用来存储链表中的元素个数
  head->next=NULL; 
  head->prev=NULL; //由于是空表，将前置和后继节点置空
  return head; //返回此头节点
}

int instNode(DP const head,int pos,int score) //在列表中的指定位置插入给定socre的记录
{
  DP p=NULL,r=head; //给变量进行初始化是一个好习惯，特别是指针，可以有效避免野指针的潜在隐患
  int i=0;  
  if(pos < 1) pos=1; //对插入位置进行校正，位置小于1时，定位到1位置
  if(pos > head->score + 1) pos=head->score + 1; //对插入位置进行校正，位置超出最后一个元素时，定位到末尾位置
  p=(DP)malloc(sizeof(DL)); //申请内存，创建一个节点
  if(NULL == p) //跟进检查，如果申请失败则提醒返回，将NULL放在左边是一种更安全的做法
  {
    printf("error:no enough memory!\n");
    return -1;
  }
  p->score=score; //初始化score为给定值
  for(i=0;i<pos-1;i++) r=r->next;  //定位到插入点前一个元素的位置
  p->next=r->next;
  p->prev=r; 
  if(r->next)r->next->prev=p; //对于链尾情况的特殊照顾
  r->next=p; //挂接新节点，这个过程的关键就是前置结点的next指针一定要最后再修改
  head->score++; //及时跟进最大下标
  return 0;
}
 

int ifEmptyList(const DP head) //用来判断此表是否为空，如果为空则返回0
{
  if(0 == head->score)
  {
    printf("warning:empty list!\n");
    return 0;
  }
  else return -1;
} 

int delNode(DP const head,int pos) //在列表中指定的位置删除一个节点
{
  DP r=head,p=NULL;
  int i=0;
  if(0 == ifEmptyList(head) )return -1; //删除前进行一下检查，判断此表是否为空
  if(1 > pos) pos=1; //对删除位置进行校正，位置小于1时，定位到1位置
  if(pos > r->score) pos=r->score; //对删除位置进行校正，位置超出最后一个元素时，定位到最后一个元素的位置
  for(i=0;i<pos-1;i++) r=r->next; //定位到删除点前一个元素的位置
  p=r->next; 
  if(p->next)p->next->prev=r;  //对于链尾情况的特殊照顾
  r->next=p->next; //断线此节点，这个过程的关键就是前置结点的next指针一定要最后再修改
  free(p); //释放节点空间
  head->score--; //及时更新元素个数
  return 0;
} 

int showList(const DP head) //将列表中的所有元素进行打印
{
  DP r=head;
  if(0 == ifEmptyList(head) )return -1; //操作前进行一下检查，判断此表是否为空
  for(r=head->next;r;r=r->next) printf("(%d)",r->score); //依次将各节点的score进行显示
  printf("\n");
  return 0;
}

int showNodesAbove(const DP head,int score) //将列表中大于指定分数的节点进行打印
{
  DP r=head;
  int res=-1;
  if(0 == ifEmptyList(head) )return res; //操作前进行一下检查，判断此表是否为空
  for(r=head->next;r;r=r->next)  //遍历表中所有节点
  {
    if(r->score > score) //将满足条件的节点进行打印
    {
      printf("(%d)",r->score); 
      res=0;
    }
  }
  printf("\n");
  return res;
}


int sortListDesc(const DP head) //对链表进行降序排序
{
  DP p=NULL,q=NULL;
  int tmp=0;
  if(0 == ifEmptyList(head) )return -1; //操作前进行一下检查，判断此表是否为空
  for(p=head->next;p;p=p->next) //冒泡排序的思想进行排序
  {
    for(q=p->next;q;q=q->next)
    {
      if(p->score < q->score)
      {
	tmp=p->score;
	p->score=q->score;
	q->score=tmp;
      }
    }
  }
  return 0;  
}

int sortListAsc(const DP head) //对链表进行升序排序
{
  DP p=NULL,q=NULL;
  int tmp=0;
  if(0 == ifEmptyList(head) )return -1; //操作前进行一下检查，判断此表是否为空
  for(p=head->next;p;p=p->next) //冒泡排序的思想进行排序
  {
    for(q=p->next;q;q=q->next) 
    {
      if(p->score > q->score)
      {
	tmp=p->score;
	p->score=q->score;
	q->score=tmp;
      }
    }
  }
  return 0;  
}


int filterListBelow(const DP head,int score) //删除掉小于指定分数的记录
{
  DP p=NULL,r=NULL;
  if(0 == ifEmptyList(head) )return -1; //操作前进行一次检查，判断此表是否为空
  for(r=head,p=r->next;p;) //遍历所有节点
  {
    if(p->score < score) //删除掉满足条件的节点
    {
      r->next=p->next;
      if(p->next)p->next->prev=r; //对尾节点要进行特殊处理
      free(p);
      p=r->next;
      head->score--; //及时更新元素个数
    }
    else
    {
      r=r->next;
      p=r->next;
    }
  }
  return 0;
}