1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_STR_LEN 81
#define MAX_NODE 255
typedef struct
{
int priority;
char string[MAX_STR_LEN];
}element;
typedef struct pqueue{
element item[MAX_NODE];
int size;
}pqueue;
// Adds a new word with given priority
int enqueuepriority(pqueue *pq, char* str, int priority)
{
int i ;
if (pq->size==MAX_NODE) {
fprintf(stderr,"The heap is full!\n");
exit(1);
}
i=++pq->size;
while (i-1&&priority<pq->item[i/2].priority)
{
pq->item[i]=pq->item[i/2];
i/=2;
}
pq->item[i].priority=priority;
strcpy(pq->item[i].string,str);
return priority;}
// Returns the string stored in the first node
char* dequeue(pqueue *pq)
{
element ele,tmp;
static char rtstr[MAX_STR_LEN];
int parent,child;
if (pq->size==0) {
fprintf(stderr,"The heap is empty!\n");
exit(1);
}
ele=pq->item[1];
tmp=pq->item[pq->size--];
parent=1;
child=2;
while (child<=pq->size)
{
if (child<pq->size && pq->item[child].priority>pq->item[child+1].priority)
child++;
if (tmp.priority<=pq->item[child].priority) break;
pq->item[parent]=pq->item[child];
parent=child;
child*=2;
}
pq->item[parent]=tmp;
strcpy(rtstr,ele.string);
return rtstr;}
void init_prt(void)
{
printf("(1) Enqueue (single)\n(2) Enqueue (multiple)\n(3) Dequeue (single)\n(4) Dequeue (all)\n(5) Quit");
printf("\nChoose an action: ");
}
void proc(pqueue *pq,const int c)
{
char str[MAX_STR_LEN];
int priority;
switch (c) {
case 1:
printf("Enter a name to save and its priority : \n");
scanf("%s%d",str,&priority);
enqueuepriority(pq,str,priority);
break;
case 2:
printf("Enter names to save and their priority. Enter “done” to quit\n");
do
{
scanf("%s",str);
if (strcmp(str,"done")) {
scanf("%d",&priority);
enqueuepriority(pq,str,priority);
}
else break;
}while (1);
break;
case 3:
printf("%s\n",dequeue(pq));
break;
case 4:
while (pq->size)
printf("%s\n",dequeue(pq));
break;
case 5: break;
default:fprintf(stderr,"input error,re-input please!\n");break;
}
}
int main(void)
{
pqueue pq={0};
int chp;
do
{
init_prt();
fflush(stdin);
scanf("%d",&chp);
proc(&pq,chp);
printf("\n++++++++++++++++++++++++++++++++\n\n");
}while (chp!=5);
return 0;
}
|
