Loading...
墨滴

艾泽

2021/05/22  阅读:31  主题:默认主题

链式队列

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

typedef struct list_node list;
struct list_node{
 int data;
 list* next;
};

//bool is_segment(list* start, list* end){
// if(start == NULL) return false;
// if(start == end) return true;
// return is_segment(start -> next, end);
//}

//bool is_segment(list* start, list* end){
// list* l = start;
// while(l != NULL){
//  l = l -> next;
//  if(l == end) return true;
// }
// return false;
//}

bool is_acyclic(list* start){
 if(start == NULLreturn true;
 list* h = start -> next;
 list* t = start;
 while(h != t){
  if(h == NULL || h -> next == NULLreturn true;
  h = h -> next -> next;
  t = t -> next;
 }
 return false;
}

bool is_segment(list* start, list* end){
 for(list* p = start ; p != NULL ; p = p -> next){
  if(p == end) return true;
 }
 return false;


// queue with linked lists

typedef struct queue_header queue;
struct queue_header{
 list* front;
 list* back;
};

typedef queuequeue_t;

bool is_queue(queue* Q){
 return Q != NULL 
  && is_acyclic(Q -> front) 
  && is_segment(Q -> front, Q -> back);
}

bool queue_empty(queue* Q){
 return Q -> front == Q -> back;
}

queuequeue_new(){
 queue* Q = (queue*)malloc(sizeof(queue));
 list* dummy = (list*)malloc(sizeof(list)); 
 Q -> front = dummy;
 Q -> back = dummy;
 return Q;
}

void enq(queue* Q, int x){
 list* new_dummy = (list*)malloc(sizeof(list));
 Q -> back -> data = x;
 Q -> back -> next = new_dummy;
 Q -> back = new_dummy; 
}

int deq(queue* Q){
//@  
 assert(queue_empty(Q) == false);
 int x = Q -> front -> data;
 list* p = Q -> front -> next;
 free(Q -> front);
 Q -> front = p;
 return x;
}

void test_queue(){
 queue* Q = queue_new();
 enq(Q, 4);
 enq(Q, 2);
 enq(Q, 3);
 while(!queue_empty(Q)){
  printf("%d\n", deq(Q));
 }
}

// 怎么将队列内存依次回收? 

int main(int argc, char *argv[]){
 test_queue();
 return 0;
}

艾泽

2021/05/22  阅读:31  主题:默认主题

作者介绍

艾泽