Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4418509
  • 博文数量: 252
  • 博客积分: 5347
  • 博客等级: 大校
  • 技术积分: 13838
  • 用 户 组: 普通用户
  • 注册时间: 2009-09-30 10:13
文章分类
文章存档

2022年(12)

2017年(11)

2016年(7)

2015年(14)

2014年(20)

2012年(9)

2011年(20)

2010年(153)

2009年(6)

分类: C/C++

2010-07-31 13:52:37

下面是单循环链表的各种C语言实现:单循环链表的最后一个节点的Next域指向链表的头结点。

/* 功能:构建一个空的带头节点的单链表*/
Status InitList_CL (struct LNode **L)
{
  (*L) = (struct LNode *)malloc(sizeof(struct LNode)); //产生头节点

  if(!*L)
   exit(OVERFLOW);
  (*L)->next = *L;
  return OK;
}
/*销毁线性表*/
Status DestroyList_CL(struct LNode *L)
{
  struct LNode *q= L->next,*p = (L)->next;
  while(q!=(L))
  {
    q = L->next;
     free(L);
    L = q;
  }
  free(L);
  L = NULL;
  return OK;
}
/*将L重置为空表*/
Status ClearList_CL(struct LNode *L)
{
  LinkList *p,*q;
   L=L->next;
  p = L->next;
  while(p!=L)
  {
    q = p->next;
    free(p);
    p = q;
  }
  L->next = L;
  return OK;
}
/*判断链表是否为空表*/
Status ListEmpty_CL(LinkList *L)
{
  if(L->next==L)
  {
    return TRUE;
  }
  else
  {
    return FALSE;
    
  }
}
/*返回单链表中元素的个数*/
int ListLength_CL(struct LNode *L)
{
  int i=0;
  LinkList *p = L->next;
  while(p!=L)
  {
    i++;
    p = p->next;
  }
  return i;
}
/* L为带头节点的单链表的头指针,当第i个元素存在时,其值赋给e,并返回OK */
Status GetElem_CL(struct LNode *L,int i,ElemType *e)
{
  int j=1;
  LinkList *p = L->next->next;
  if(i<=0 || i>ListLength_CL(L))
     return ERROR;
  while(j<i)
  {
    p = p->next;
    j++;
  }
  *e = p->data;
  return OK;
}
/*返回L中第一个与e满足关系compare()的数据元素的位序,
 若给存在返回值为0,compare()是数据元素的判定函数*/

int LocateElem_CL(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))
{
  int i =0;
  LinkList *p = L->next->next;
  while(p!=L->next)
  {
    i++;
    if(compare(p->data,e))
      return i;
    p=p->next;
  }
  return 0;
}
/*所cur_e是L中的数据元素,且给就第一个,则用pre_e返回它的前驱*/
Status PriorElem_CL(struct LNode *L,ElemType cur_e,ElemType *pre_e)
{
  LinkList *q,*p=L->next->next;
  q = p->next;
  while(q!=L->next)
  {
    if(q->data == cur_e)
    {
      *pre_e = p->data;
      return OK;
    }
    p = q;
    q = q->next;
  }
  return INFEASIBLE;
}
/* 若cur_e是L中的数据元素,且不是最后一个,则用next_e返回它的后继*/
Status NextElem_CL(struct LNode *L,ElemType cur_e,ElemType *next_e)
{
  LinkList *p;
  p = L->next->next;
  while(p!=L)
  {
    if(p->data == cur_e)
    {
     *next_e = p->next->data;
      return OK;
    }
    p = p->next;
  }
  return INFEASIBLE;
}
/* 在带头节点的单链表L中的第i个位置之前插入元素e*/
Status ListInsert_CL(struct LNode *L,int i,ElemType e)
{
  int j =0;
  struct LNode *p=L->next,*s=NULL;
  while( j<i-1)
  {
    p=p->next;
    j++;
  }
 
  s = (struct LNode *)malloc(sizeof(struct LNode));
  if(!s)
    printf("malloc error~\n");
  // p->next = s;

  s->data = e;
  // p->next = s;

   s->next = p->next;
   p->next = s;
   if(p==L)
     L = s;
   //s->next = NULL;

  // p = s;

  return OK;
}
/*在带头节点的单链表中删除第i个元素,并有e返回其值*/
Status ListDelete_CL(LinkList *L,int i,ElemType *e)
{
 
  LinkList *p=L->next,*q;
  
   int j=0;
  while(j< i-1)
  {
    p = p->next;
    j++;
  }
  q = p->next;
  p->next = q->next;
  *e = q->data;
  if(L==q)
    L= p;
  free(q);
  return OK;
  }
/* 依次对L的每个元素调用vi(),打印输出语句*/
Status ListTraverse_CL(struct LNode *L,void (*vi)(ElemType))
{
  LinkList *p = L->next->next;
  while(p!=L->next)
  {
    vi(p->data);
    p = p->next;
  }
  printf("\n");
  return OK;
}


阅读(7528) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~