CPJ Linux Dev Engineer

3-1-1-3环形链表

2017-08-16

WELCOME TO READ ME

头文件以及宏

#include<stdio.h> /* EOF(=^Z或F6),NULL */               
#include<math.h> /* floor(),ceil(),abs() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int ElemType;
struct LNode
{
  ElemType data;
  struct LNode *next;
};
typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */

一 构造空链表函数

Status InitList_CL(LinkList *L) 
{ /* 操作结果:构造一个空的线性表L */
  *L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
  if(!*L) /* 存储分配失败 */
    exit(OVERFLOW);
  (*L)->next=*L; /* 指针域指向头结点 */
  return OK; 
} 

二 查空查长度查元素函数

Status ListEmpty_CL(LinkList L)
{ /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
  if(L->next==L) /* 空 */
    return TRUE;
  else                             
    return FALSE;
}
int ListLength_CL(LinkList L)
{ /* 初始条件:L已存在。操作结果:返回L中数据元素个数 */
  int i=0;
  LinkList p=L->next; /* p指向头结点 */
  while(p!=L) /* 没到表尾 */
  {
    i++;
    p=p->next;
  }
  return i;
}

三 插入元素

Status ListInsert_CL(LinkList *L,int i,ElemType e) /* 改变L */
{ /* 在L的第i个位置之前插入元素e */
  LinkList p=(*L)->next,s; /* p指向头结点 */
  int j=0;
  if(i<=0||i>ListLength_CL(*L)+1) /* 无法在第i个元素之前插入 */
    return ERROR;
  while(j<i-1) /* 寻找第i-1个结点 */
  {
    p=p->next;
    j++;
  }
  s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
  s->data=e; /* 插入L中 */
  s->next=p->next;
  p->next=s;
  if(p==*L) /* 改变尾结点 */
    *L=s;
  return OK;
}

四 查前驱后驱函数

Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件:线性表L已存在 */
  /* 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */
  /*           否则操作失败,pre_e无定义 */
  LinkList q,p=L->next->next; /* p指向第一个结点 */
  q=p->next;
  while(q!=L->next) /* p没到表尾 */
  {
    if(q->data==cur_e)
    {
    ¦ *pre_e=p->data;
    ¦ return TRUE;
    }
    p=q;
    q=q->next;
  }
  return FALSE;
}
Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件:线性表L已存在 */
  /* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */
  /*           否则操作失败,next_e无定义 */
  LinkList p=L->next->next; /* p指向第一个结点 */
  while(p!=L) /* p没到表尾 */
  {
    if(p->data==cur_e)
    {
    ¦ *next_e=p->next->data;
    ¦ return TRUE;
    }
    p=p->next;
  }
  return FALSE;
}

五 删除L中第i个元素,并由e返回该值

Status ListDelete_CL(LinkList *L,int i,ElemType *e) /* 改变L */
{ /* 删除L的第i个元素,并由e返回其值 */
  LinkList p=(*L)->next,q; /* p指向头结点 */
  int j=0;
  if(i<=0||i>ListLength_CL(*L)) /* 第i个元素不存在 */
    return ERROR;                                 
  while(j<i-1) /* 寻找第i-1个结点 */
  {
    p=p->next;
    j++;
  }
  q=p->next; /* q指向待删除结点 */
  p->next=q->next;
  *e=q->data;
  if(*L==q) /* 删除的是表尾元素 */
    *L=p;
  free(q); /* 释放待删除结点 */
  return OK; 
}

六 清空链表删除链表

Status DestroyList_CL(LinkList *L) 
{ /* 操作结果:销毁线性表L */
  LinkList q,p=(*L)->next; /* p指向头结点 */
  while(p!=*L) /* 没到表尾 */
  {
    q=p->next;
    free(p);
    p=q;
  }
  free(*L);
  *L=NULL;
  return OK; 
}
Status ClearList_CL(LinkList *L) /* 改变L */
{ /* 初始条件:线性表L已存在。操作结果:将L重置为空表 */
  LinkList p,q;
  *L=(*L)->next; /* L指向头结点 */
  p=(*L)->next; /* p指向第一个结点 */
  while(p!=*L) /* 没到表尾 */
  {
    q=p->next;
    free(p);
    p=q;
  }
  (*L)->next=*L; /* 头结点指针域指向自身 */
  return OK; 
}

七 仅设表尾指针循环链表的合并

void MergeList_CL(LinkList *La,LinkList Lb) 
{
  LinkList p=Lb->next;
  Lb->next=(*La)->next;
  (*La)->next=p->next;
  free(p);                                   
  *La=Lb;
}

Similar Posts

Comments