C 언어 대기 열의 체인 구조의 실현 과 데이터 구조 대기 열의 실현 과 표시

15679 단어
노동절 연 휴 에 할 일이 별로 없 었 습 니 다. 놀 러 가 거나 공 을 치 러 가 려 고 했 는데 하늘 이 도와 주지 않 았 습 니 다. 이틀 동안 날씨 가 계속 비가 와 서 사람의 마음 이 흠뻑 젖 었 습 니 다.
 어제 하루 종일 스 택 과 대기 열 을 배 웠 고 어제 오후 몇 시 에 스 택 의 프로 그래 밍 을 마 쳤 습 니 다.저녁 에는 대기 열 을 다 쓰 는 프로그램 이 어야 하 는데 저녁 에 침실 에 가서 불 을 끄 기 전에 하마터면 프로그램 이 모두 완 공 될 뻔 했 습 니 다. 그러나 항상 몇 개의 작은 bug 디 버 깅 이 지나 가지 않 습 니 다.어 쩔 수 없어, 오늘 오전 에 또 한 시간 이 걸 려 서 야 완 공 했 어.
 에, 그런데 드디어 다 썼 습 니 다. 데이터 구조의 대기 열 에 대해 더욱 신선 한 인식 을 가지 게 되 었 습 니 다.
자, 쓸데없는 소리 하지 말고 예전 처럼 코드 를 여러분 과 함께 공유 하 세 요!
코드 에 오류 가 있 으 면 아 낌 없 이 의견 을 보 내 주 십시오[email protected]최대한 빨리 답 해 드 리 겠 습 니 다.
C 언어 대기 열의 체인 구조의 실현 과 데이터 구조 대기 열의 표시 와 실현
/****************************************/
/*Description: Link Queue*/
/*Email:[email protected]*/
/*Author:yi_landry Harbin Normal University Computer Science*/
/*Date:2008-5-1*/
/*Copyright:HNU2008.cop*/
/*Environment:turbo c 2.01 English Version*/
/****************************************/
# include
# include
# define OVERFLOW 0
# define OK 1
/****************************************/
/*The node of link queue */
/****************************************/
struct LqNode
{
  int item;
  struct LqNode * next;
};

/****************************************/
/*The struct of link queue */
/****************************************/
struct LqQueue
{
  struct LqNode * front;/*the head pointer of the link queue*/
  struct LqNode * rear;/*the tail pointer of the link queue*/
  int length;/*the total number of the nodes in the queue*/
}Q;
/****************************************/
/*Initial the queue*/
/****************************************/
InitQueue(struct LqQueue * Q)
{
  Q->front=Q->rear=(struct LqNode *)malloc(sizeof(struct LqNode));
  if (!Q->front && !Q->rear) exit(OVERFLOW);
  Q->length = 0;
  printf("Initial the link queue successfully!/n");
}
/****************************************/
/*insert a node into the queue at the tail*/
/****************************************/
QueueEn(struct LqQueue * Q,int elm)
{
  struct LqNode * p,* q ;
  int count = 0;
  p = (struct LqNode *)malloc(sizeof(struct LqNode));
  q = Q->front;
  if (!p && !q) exit(OVERFLOW);
  if (Q->length == 0)
  {
    p->item = elm;
    p->next = NULL;
    Q->front=Q->rear=p;
    Q->length ++;
    printf("The new node %d was inserted into the Queue successfully!/n",elm);
  }
  else
  {
    p->item = elm;
    p->next = NULL;
    while (1)
    {
      count++;
      if (count == Q->length) break; 
      q = q->next;
    }
    q->next = Q->rear = p;
    Q->length++;
    printf("The new node %d was inserted into the Queue successfully!/n",elm);
  }
}
/****************************************/
/*Delet the first node in the queue first out*/
/****************************************/
QueueDefirst(struct LqQueue * Q)
{
  int DefirstElm=0;
  if (Q->front != NULL)
  {
    DefirstElm = Q->front->item;
  }
  if (Q->length == 0)
  {
    printf("The queue now is empty,you can not delete the first node again!/n");
  }
  else if (Q->length == 1)
  {
    Q->front = Q->rear = NULL;
    Q->length--;
    printf("Delete the first node %d  successfully!/n",DefirstElm);
  }
  else
  {
    Q->front = Q->front->next;
    Q->length--;
    printf("Delete the first node %d successfully!/n",DefirstElm);
  }
}

/****************************************/
/*Judge the queue is empty or not*/
/****************************************/
QueueEmpty(struct LqQueue * Q)
{
   if (Q->length==0)
   {
     printf("The queue now is empty!/n");
   }
   else
   {
     printf("The queue now is not empty!/n");
     PrintQueue(Q);
   }
}
/****************************************/
/*Get the length of the queue*/
/****************************************/
QueueLength(struct LqQueue * Q)
{
  printf("The length of current queue is %d/n",Q->length);
}
/****************************************/
/*Destroy the queue and free the memory distributed at first*/
/****************************************/
DestroyQueue(struct LqQueue * Q)
{
  free(Q->front);
  free(Q->rear);
  Q->length = 0;
  printf("Destroy the queue successfully!/n");
}
/****************************************/
/*Clear all the nodes in the queue*/
/****************************************/
ClearQueue(struct LqQueue * Q)
{
  free(Q->front);
  free(Q->rear);
  Q->length = 0;
  printf("Clear the queue successfully!/n");
}
/****************************************/
/*Get the node at tbe location i */
/****************************************/
GetElement(struct LqQueue * Q,int i)
{
  struct LqNode * p;
  int count = 0;
  p = Q->front;
  if (i <= 0|| i>Q->length)
  {
    printf("The location you input is not valid!/n");
  }
  while (1)
  {
    count++;
    if (count==i) break;
    p=p->next;
  }
  return p->item;
}
/****************************************/
/*Find a number if or not in the queue*/
/****************************************/
FindElement(struct LqQueue * Q,int elm)
{
    struct LqNode *p;
    int count=0,totalFind=0;
    p =Q->front;
    while (1)
    {
      if (count == Q->length) break;
      count++;
      if(p->item == elm)
      {
        totalFind++;
        printf("We find %d at the location of %d in the queue!/n",elm,count);
      }
      p = p->next;
    }
    if (totalFind == 0)
    {
     printf("We can not find %d in the queue!/n",elm);
    }
    else
    {
      printf("We totally find %d in the queue/n",totalFind,elm);
    }
}
/****************************************/
/*Get prior node of some node in the queue*/
/****************************************/
PriorElement(struct LqQueue * Q,int elm)
{
    struct LqNode *p;
    int count=0,priorNode=0,totalFind=0;
    p =Q->front;
    while (1)
    {
      if (count == Q->length) break;
      count++;
      if(p->item == elm)
      {
        if (count == 1)
        {
          printf("We can not find the prior of %d in the queue!/n",elm);
        }
        else
        {
          totalFind++;
          priorNode = GetElement(Q,count-1);
          printf("We find prior of %d is %d at the location of %d in the queue!/n",elm,priorNode,count-1);
        }
      }
      p=p->next;
    }
    if (totalFind == 0)
    printf("We can not find the prior of %d in the queue!/n",elm);
}
/****************************************/
/*Get next node of some node in the queue*/
/****************************************/
NextElement(struct LqQueue * Q,int elm)
{
  struct LqNode *p;
  int count=0,nextNode=0,totalFind=0;
    p =Q->front;
    while (1)
    {
      if (count == Q->length) break;
      count++;
      if(p->item == elm)
      {
        if (count == Q->length)
        {
          printf("We can not find the next of %d in the queue!/n",elm);
        }
        else
        {
          totalFind++;
          nextNode = GetElement(Q,count+1);
          printf("We find next of %d is %d at the location of %d in the queue!/n",elm,nextNode,count+1);
        }
      }
      p=p->next;
    }
    if (totalFind == 0)
    printf("We can not find the next of %d in the queue!/n",elm);
}

/****************************************/
/*Print the queue */
/****************************************/
PrintQueue(struct LqQueue * Q)
{
  int count;
  count = Q->length;
  if (Q->length==0)
  {
    printf("The queue now is empty!/n");
  }
  else if (Q->length == 1)
  {
    printf("The current queue:/n");
    printf("         _______ /n");
    printf("rear -->|  %3d  |/n",Q->front->item);
    printf("front-->|_______|/n");
  }
  else
  {
      printf("The current queue:/n");
      while(1)
      {
        if(count == 0) break;
        if(count ==Q->length)
        {
          printf("         _______/n");
          printf("rear -->|  %3d  |/n",GetElement(Q,count));
          printf("        |_______|/n");
          count--;
        }
        else if (count==1)
        {
          printf("        |  %3d  |/n",GetElement(Q,count));
          printf("front-->|_______|/n");
          count--;
        }
        else
        {
          printf("        |  %3d  |/n",GetElement(Q,count));
          printf("        |_______|/n");
          count--;
        }
      }
  }
}
/****************************************/
/*Show a example to the user*/
/****************************************/
QueueExample()
{
  InitQueue(&Q);
  QueueEn(&Q,1);
  QueueEn(&Q,2);
  QueueEn(&Q,3);
  QueueEn(&Q,4);
  QueueEn(&Q,5);
  QueueEn(&Q,6);
  QueueEn(&Q,5);
  QueueEn(&Q,6);
  QueueEn(&Q,60);
  QueueEn(&Q,50);
  QueueEn(&Q,7);
  QueueEn(&Q,8);
  QueueEn(&Q,9);
  FindElement(&Q,6);
  FindElement(&Q,7);
  FindElement(&Q,10);
  PriorElement(&Q,6);
  PriorElement(&Q,10);
  NextElement(&Q,6);
  NextElement(&Q,10);
  GetElement(&Q,3);
  PrintQueue(&Q);
  QueueLength(&Q);
  DestroyQueue(&Q);
  return 0;
}
/****************************************/
/*Show the help information to the user*/
/****************************************/
void help()
{
  printf("      /*****************************************************************//n");
  printf("      /*****************************************************************//n");
  printf("      /*        The link queue Operation Version 1.0                *//n");
  printf("      /*             View the example information             1         *//n");
  printf("      /*       insert a node into the queue at the tail       2         *//n");
  printf("      /*        delete the head  number from the queue        3         *//n");
  printf("      /*          Find a number if or not in the queue        4         *//n");
  printf("      /*       Get the prior of some number from the queue    5         *//n");
  printf("      /*       Get the next  of some number from the queue    6         *//n");
  printf("      /*                Get the size of queue                 7         *//n");
  printf("      /*               Show the help information              8         *//n");
  printf("      /*             View current  queue information          9         *//n");
  printf("      /*                    Exit link  queue                  Q         *//n");
  printf("      /*****************************************************************//n");
}
main()
{
  char userInput;
  int insertItem,findItem,priorItem,nextItem;
  help();
  InitQueue(&Q);
  while(1)
  {
    printf("Slect the operation you want to do: input the correspond number!you can enter 1 to view the example ,and enter 8 to view the help./n");
    scanf("%c",&userInput);
    switch(userInput)
    {
      case '1':QueueExample();break;
      case '2':
             for(;;)
             {
              printf("Please input a integer  you want to push into the queue:/n");
                 printf("Forexample 1 . if you do not want to push a number into the queue again,you can input -1/n");
              scanf("%d",&insertItem);
                 if (insertItem == -1)
                 break;
              QueueEn(&Q,insertItem);
              PrintQueue(&Q);
              }
           break;
      case '3':
              QueueDefirst(&Q);
              PrintQueue(&Q);
           break;
      case '4':
             for(;;)
             {
              printf("Please input a integer  you want to find from the queue:/n");
                 printf("Forexample 1 . if you do not want to find a number from the queue again,you can input -1/n");
           scanf("%d",&findItem);
                 if (findItem == -1)
                 break;
              FindElement(&Q,findItem);
              PrintQueue(&Q);
              }
           break;
      case '5':
             for(;;)
             {
         printf("Please input a integer  you want to get the prior from the queue:/n");
         printf("Forexample 1. if you do not want to get the prior form the queue again,you can input -1/n");
         scanf("%d",&priorItem);
         if (priorItem == -1) break;
         PriorElement(&Q,priorItem);
            PrintQueue(&Q);
              }
           break;
      case '6':
            for(;;)
             {
         printf("Please input a integer  you want to get the next from the queue:/n");
         printf("Forexample 1. if you do not want to get the next form the queue again,you can input -1/n");
         scanf("%d",&nextItem);
         if (nextItem == -1) break;
         NextElement(&Q,nextItem);
            PrintQueue(&Q);
              }
           break;
      case '7':QueueLength(&Q);break;
      case '8':help();break;
      case '9':PrintQueue(&Q);break;
      case 'Q':break;
      case 'q':break;
    }
    if (userInput == 'q'|| userInput == 'Q')
    break;
  }
  return 0;
}


코드 에 오류 가 있 으 면 아 낌 없 이 의견 을 보 내 주 십시오[email protected]최대한 빨리 답 해 드 리 겠 습 니 다.

좋은 웹페이지 즐겨찾기