#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAXLEN 256 //define the max length a string can be input
//struct
typedef struct node
{
int priority;
//any-length name
char *name;
struct node *next;
}node;
typedef struct insidequeue
{
int size;
int priority;
node *head;
node *tail;
struct insidequeue *next_queue;
}insidequeue;
typedef struct pqueue
{
int size;
struct insidequeue *head_queue;
}pqueue;
//function prototypes
char *dequeue(pqueue *pq);
void enqueuepriority(pqueue *pq, char *name, int priority);
void enterqueue_lev2(insidequeue *q, node *anode);
void initialize(insidequeue **q, int priority);
void readstr(char **str);
void readint(int *num, char *name);
void copystr(char *in, char **copy);
void show(pqueue *pq);
//main function
int main()
{
int choice,i,size;
int priority;
char *name=NULL;
char *name_returned=NULL;
pqueue *pq;
node* temp;
//initialize the priority queue pq
if(!(pq=(pqueue *)malloc(sizeof(pqueue)))){
printf("cannot allocate memory\n");
exit(1);}
pq->size=0;
pq->head_queue=NULL;
printf("(1)\tEnqueue (single)\n"
"(2)\tEnqueue (multiple)\n"
"(3)\tDequeue(single)\n"
"(4)\tDequeue(all)\n"
"(5)\tShow(all)\n"
"(6)\tQuit\n");
while(1){ //break in the case 6.
printf("\nChoose an action: ");
choice=0;
fflush(stdin);
scanf("%d",&choice);
switch(choice){
case 1:
printf("Enter a name to save and its priority\n");
fflush(stdin);
readstr(&name);//read its name
readint(&priority,name);//read ist priority
enqueuepriority(pq,name,priority);//enter the priority queue
break;
case 2:
printf("Enter names to save and their priority. Enter \"done\" to quit\n");
while(1){ //break when input "done"
fflush(stdin);
readstr(&name);
//if input is "done", end the input session
if(strcmp(name,"done")==0)
break;
readint(&priority,name);
enqueuepriority(pq,name,priority);
}
break;
case 3:
//dequeue one node
printf("%s\n",name_returned=dequeue(pq));
free(name_returned); //save space for heap
break;
case 4:
//dequeue all the nodes
size=pq->size;
for(i=1;i<=size;i++){
printf("%s\n",name_returned=dequeue(pq));
free(name_returned); //save space for heap
}
break;
case 5:
//show all the nodes with priority in the priority queue pq
show(pq);
break;
case 6:
//quit
printf("Quit\n");
return 0;
default:
//error input
printf("ERROR: plz input again\n\n");
fflush(stdin);
break;
}
}
}
//functions definition
char *dequeue(pqueue *pq)
{
//This function is to dequeue the first node in the
//first inside queue in the priority queue
node *cur;
insidequeue* temp;
char *name_returned=NULL;
//handle the situation of empty priority queue
if(pq->size==0){
printf("empty queue\n");
return NULL;
}
//move the head node out of the first inside queue
cur=pq->head_queue->head;
pq->head_queue->head=cur->next;
//copy down the name of the node
copystr(cur->name,&name_returned);
//since the first inside queue will be empty after only node is moved out, it is cleared from the priority queue
if(pq->head_queue->size==1){
temp=pq->head_queue;
pq->head_queue=pq->head_queue->next_queue;
free(temp);
}
//normal case
else
pq->head_queue->size--;
free(cur->name); //clear up the string malloc in the heap
free(cur);
pq->size--;
return name_returned;
}
void enqueuepriority(pqueue *pq, char *name, int priority)
{
//This function is to insert a node into the priority queue
node *insert;
insidequeue *q,*pre;
//initialize the node to be inserted
if(!(insert=(node *)malloc(sizeof(node)))){
printf("cannot allocate memory\n");
exit(1);}
insert->name=NULL;
copystr(name,&insert->name);
insert->priority=priority;
insert->next=NULL;
//empty priority queue
if(pq->size==0){
//initialize a inside queue
initialize(&q,priority);
//insert the node to the inside queue just created.
enterqueue_lev2(q,insert);
//insert the inside queue to the priority queue
pq->head_queue=q;
}
else{
pre=pq->head_queue;
//when the node entered is of the highest priority
if(priority<pre->priority){
initialize(&q,priority);
enterqueue_lev2(q,insert);
pq->head_queue=q;
q->next_queue=pre;
}
//enter the node into the first inside queue if fit
else if(priority==pre->priority)
enterqueue_lev2(pre,insert);
else{
//try to find the priority-fit inside queue into which the node is inserted
for(;pre->next_queue&& pre->next_queue->priority<priority ;pre=pre->next_queue);
if(pre->next_queue&&pre->next_queue->priority==priority)
enterqueue_lev2(pre->next_queue,insert);
else{
/*no priority-fit inside queue is found, then create an inside queue for the node, and
insert that inside queue to the priority queue pq*/
initialize(&q,priority);
enterqueue_lev2(q,insert);
q->next_queue=pre->next_queue;
pre->next_queue=q;
}
}
}
pq->size++;
}
void enterqueue_lev2(insidequeue *q, node *anode)
{
//This function is a standard enqueue() function defined in the lecture
//enter the node to the tail of a queue
//here the queue is the inside queue of the priority queue, that's why the function called "level 2"
node *pre;
if(q->size==0){
q->head=anode;
q->tail=anode;
}
else{
pre=q->tail;
pre->next=anode;
q->tail=anode;
}
q->size++;
}
void initialize(insidequeue **q, int priority)
{
//This function is to initialize an empty inside queue with a certain priority
if(!((*q)=(insidequeue *)malloc(sizeof(insidequeue)))){
printf("cannot allocate memory\n");
exit(1);}
(*q)->size=0;
(*q)->priority=priority;
(*q)->next_queue=NULL;
(*q)->head=NULL;
(*q)->tail=NULL;
}
void readstr(char **str)
{
//This function is to read and check the string entered
//dynamic-length string
char string[MAXLEN];
int len, i;
while(1){ //break when the string is alphabetic.
scanf("%s",string);
len=strlen(string);
for(i=0;i<=len-1;i++)
//check the string input whether it is an alphabetic string
if(!isalpha(*(string+i))){
printf("ERROR: plz input an alphabetic value for the string input\n\n");
fflush(stdin);
break;
}
//pass the test
if(i==len)
break;
}
copystr(string,str);
}
void readint(int *num, char *name)
{
//this function is to read and check the priority entered by user
while(!scanf("%d",num) || *num<=0){
printf("ERROR: plz input a positive priority for \"%s\" again\n\n%s ",name,name);
fflush(stdin);
}
}
void copystr(char *in,char **copy){
//This function is to copy the string "in" to "*copy"
if(*copy)
free(*copy); //clear up the previous value in the heap
if(!(*copy=(char *)malloc(sizeof(char)*(strlen(in)+1)))){
printf("cannot allocate memory\n");
exit(1);}
strcpy(*copy,in);
}
void show(pqueue *pq)
{
//This function is to show all the nodes' names and priorities sequentially.
node *cur_node;
insidequeue *cur_q;
printf("%-20s%-20s\n","name","priority");
printf("-------------------------------------\n");
if(pq->size==0){
printf("Nothing here\n");
printf("-------------------------------------\n");
}
else{
for(cur_q=pq->head_queue;cur_q;cur_q=cur_q->next_queue)
for(cur_node=cur_q->head;cur_node;cur_node=cur_node->next)
printf("%-20s%-20d\n",cur_node->name,cur_node->priority);
printf("-------------------------------------\n");
printf("total %d nodes\n",pq->size);
}
}
AVL.rar_基于avl
版权申诉
131 浏览量
2022-09-24
18:18:16
上传
评论
收藏 2KB RAR 举报
Kinonoyomeo
- 粉丝: 77
- 资源: 1万+
最新资源
- Yolov8改进---注意力机制:Polarized Self-Attention,效果秒杀CBAM、SE.html
- 人才网站设计-asp.net+sql-(系统源码)
- asp.net+sql人才网站设计-含系统源码
- C#应用的用户配置窗体方案
- python实现绘制爱心图形的代码
- JAVAWEB项目-校园订餐系统项目源码.zip
- flink-1.19.0-bin-scala-2.12.tgz flink-1.16.3-bin-scala-2.12.tgz
- javaWeb项目-物资管理系统项目源码.zip
- javaweb项目-物流配货项目源码.zip
- 使用C++基于颜色纹理特征的人脸活体检测实现-附项目源码.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈