linkcyc.cpp

图的创建和遍历

// 用尾指针表示的循环链表--实现队列
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <alloc.h>

typedef struct node{
  char c;
  struct node *next;
}node,*link;

void creatq(link &q){
  q=(link)malloc(sizeof(node)); q->next=q;
}

void destroyq(link &q){
  link p;
  p=q->next; q->next=NULL;
  while(p){
    q=p; p=p->next; free(q);
  }
}

void inq(link &q,char e){
  link p;
  p=(link)malloc(sizeof(node));
  p->c=e; p->next=q->next; q->next=p; q=p;
}

empty(link q){
  return (q->next==q);
}

char outq(link &q){
  link p; char ch;
  if(empty(q)){
    printf("Error! Queue is Empty!"); return '\0';
  }
  else{
    p=q->next->next; q->next->next=p->next;
    ch=p->c;
    if(p==q) q=q->next;
    free(p); return ch;
  }
}

len(link q){
  int i=0;
  link p;
  p=q->next;
  while(p!=q){p=p->next; i++;}
  return i;
}

void prtq(link q){
  link p;
  p=q->next;
  gotoxy(10,20); clreol();
  while(p!=q){
    printf("-%c",p->next->c); p=p->next;
  }
}

main(){
  int m,n,i; char ch=49;
  node *p,*q;
  creatq(q);
  clrscr();
  printf("             1.enter queue  2.out queue  3.lenth  4.Empty  0.Exit");
  window(1,2,80,25);
  while(ch!=48){
    gotoxy(36,3); printf("Chose:");
    ch=getch(); clrscr(); gotoxy(25,8);
    switch(ch){
      case '1': printf("Enter a Char as Input:");
	inq(q,getche()); break;
      case '2': printf("Dequeue: %c",outq(q)); break;
      case '3': printf("Queue's lenth:%d",len(q)); break;
      case '4':
	printf("Queue is %s",(empty(q)?"Empty":"No Empty")); break;
      case '0': destroyq(q); window(1,1,80,25); return 0;
    }
    prtq(q);
  }  return 1;
}