lq.c

广工--数据结构的课程设计 郑纬民教授版 图的十字链表实现 图的邻接表实现

 void DestroyList(LinkList *L)
 { /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
   LinkList p;
   while(*L) /* L不空 */
   {
     p=*L; /* p指向首元结点 */
     *L=(*L)->next; /* L指向第2个结点(新首元结点) */
     free(p); /* 释放首元结点 */
   }
 }


 int ListLength(LinkList L)
 { /* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */
   int i=0;
   LinkList p=L;
   while(p) /* p指向结点(没到表尾) */
   {
     p=p->next; /* p指向下一个结点 */
     i++;
   }
   return i;
 }


 int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
 { /* 初始条件：线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) */
   /* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
   /*           若这样的数据元素不存在，则返回值为0 */
   int i=0;
   LinkList p=L;
   while(p)
   {
     i++;
     if(compare(p->data,e)) /* 找到这样的数据元素 */
       return i;
     p=p->next;
   }
   return 0;
 }

 Status ListInsert(LinkList *L,int i,ElemType e)
 { /* 在不带头结点的单链线性表L中第i个位置之前插入元素e */
   int j=1;
   LinkList p=*L,s;
   if(i<1) /* i值不合法 */
     return ERROR;
   s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
   s->data=e; /* 给s的data域赋值 */
   if(i==1) /* 插在表头 */
   {
     s->next=*L;
     *L=s; /* 改变L */
   }
   else
   { /* 插在表的其余处 */
     while(p&&j<i-1) /* 寻找第i-1个结点 */
     {
       p=p->next;
       j++;
     }
     if(!p) /* i大于表长+1 */
       return ERROR;
     s->next=p->next;
     p->next=s;
   }
   return OK;
 }

 Status ListDelete(LinkList *L,int i,ElemType *e)
 { /* 在不带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */
   int j=1;
   LinkList p=*L,q;
   if(i==1) /* 删除第1个结点 */
   {
     *L=p->next; /* L由第2个结点开始 */
     *e=p->data;
     free(p); /* 删除并释放第1个结点 */
   }
   else
   {
     while(p->next&&j<i-1) /* 寻找第i个结点，并令p指向其前驱 */
     {
       p=p->next;
       j++;
     }
     if(!p->next||j>i-1) /* 删除位置不合理 */
       return ERROR;
     q=p->next; /* 删除并释放结点 */
     p->next=q->next;
     *e=q->data;
     free(q);
   }
   return OK;
 }

 void InitQueue(LinkQueue *Q)
 { /* 构造一个空队列Q */
   (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
   if(!(*Q).front)
     exit(OVERFLOW);
   (*Q).front->next=NULL;
 }


 Status QueueEmpty(LinkQueue Q)
 { /* 若Q为空队列，则返回TRUE，否则返回FALSE */
   if(Q.front->next==NULL)
     return TRUE;
   else
     return FALSE;
 }



 void EnQueue(LinkQueue *Q,QElemType e)
 { /* 插入元素e为Q的新的队尾元素 */
   QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
   if(!p) /* 存储分配失败 */
     exit(OVERFLOW);
   p->data=e;
   p->next=NULL;
   (*Q).rear->next=p;
   (*Q).rear=p;
 }

 Status DeQueue(LinkQueue *Q,QElemType *e)
 { /* 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR */
   QueuePtr p;
   if((*Q).front==(*Q).rear)
     return ERROR;
   p=(*Q).front->next;
   *e=p->data;
   (*Q).front->next=p->next;
   if((*Q).rear==p)
     (*Q).rear=(*Q).front;
   free(p);
   return OK;
 }



 LinkList Point(LinkList L,ElemType e,Status(*equal)(ElemType,ElemType),LinkList *p)
 { /* 查找表L中满足条件的结点。如找到，返回指向该结点的指针，p指向该结点的前驱(若该结点是 */
   /* 首元结点，则p=NULL)。如表L中无满足条件的结点，则返回NULL，p无定义。*/
   /* 函数equal()的两形参的关键字相等，返回OK；否则返回ERROR */
   int i,j;
   i=LocateElem(L,e,equal);
   if(i) /* 找到 */
   {
     if(i==1) /* 是首元结点 */
     {
       *p=NULL;
       return L;
     }
     *p=L;
     for(j=2;j<i;j++)
       *p=(*p)->next;
     return (*p)->next;
   }
   return NULL; /* 没找到 */
 }

 Status DeleteElem(LinkList *L,ElemType *e,Status(*equal)(ElemType,ElemType))
 { /* 删除表L中满足条件的结点，并返回TRUE；如无此结点，则返回FALSE。 */
   /* 函数equal()的两形参的关键字相等，返回OK；否则返回ERROR */
   LinkList p,q;
   q=Point(*L,*e,equal,&p);
   if(q) /* 找到此结点，且q指向该结点 */
   {
     if(p) /* 该结点不是首元结点，p指向其前驱 */
       ListDelete(&p,2,e); /* 将p作为头指针，删除第2个结点 */
     else /* 该结点是首元结点 */
       ListDelete(L,1,e);
     return TRUE;
   }
   return FALSE;
 }