-
Notifications
You must be signed in to change notification settings - Fork 0
/
Exercise5-14.c
154 lines (130 loc) · 3.47 KB
/
Exercise5-14.c
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/*Exercise 5-14. Modify the sort program to handle a -r flag, which indicates sorting
in reverse (decreasing) order. Be sure that -r works with -n.*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLINES 5000 /* max #lines to be sorted */
char *lineptr[MAXLINES]; /* pointers to text lines */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void my_qsort(void *lineptr[], int left, int right, int (*comp)(void *, void *), int reverse);
int numcmp(char *, char *);
/* sort input lines */
int main(int argc, char *argv[])
{
int nlines; /* number of input lines read */
int numeric = 0;/* if numeric sort */
int reverse = 0;/*reveser order*/
while (--argc>0&& **(++argv)=='-')
{
if( *(*(argv)+1)=='n')
numeric=1;
else if ( *(*(argv)+1)=='r')
reverse=1;
}
if ((nlines = readlines(lineptr, MAXLINES)) >= 0)
{
my_qsort((void**) lineptr, 0, nlines-1, (numeric ? numcmp : strcmp), reverse ? 1:0);
writelines(lineptr, nlines);
return 0;
}
else
{
printf("input too big to sort\n");
return 1;
}
}
#define MAXLEN 1000 /* max length of any input line */
size_t get_line(char *, int);
char *alloc(int);
/* readlines: read input lines */
int readlines(char *lineptr[], int maxlines)
{
int len, nlines;
char *p, line[MAXLEN];
nlines = 0;
while ((len = get_line(line, MAXLEN)) > 0)
if (nlines >= maxlines || (p = alloc(len))== NULL)
return -1;
else
{
line[len-1] = '\0'; /* delete newline */
strcpy(p, line);
lineptr[nlines++] = p;
}
return nlines;
}
/* writelines: write output lines */
void writelines(char *lineptr[], int nlines)
{
int i;
for (i = 0; i < nlines; i++)
printf("%s\n", lineptr[i]);
}
/* qsort: sort v[left]...v[right] into increasing order */
void my_qsort(void *v[], int left, int right, int (*comp)(void *, void *), int reverse)
{
int i, last;
void swap(void *v[], int, int);
if (left >= right) /* do nothing if array contains */
return; /* fewer than two elements */
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++)
if(reverse)
{
if ((*comp)(v[i], v[left]) > 0)
swap(v, ++last, i);
}else
{
if ((*comp)(v[i], v[left]) < 0)
swap(v, ++last, i);
}
swap(v, left, last);
my_qsort(v, left, last-1, comp, reverse);
my_qsort(v, last+1, right, comp, reverse);
}
/* numcmp: compare s1 and s2 numerically */
int numcmp(char *s1, char *s2)
{
double v1, v2;
v1 = atof(s1);
v2 = atof(s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
void swap(void *v[],int i, int j)
{
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE];
static char *allocp = allocbuf;
char *alloc(int n)
{
if(ALLOCSIZE + allocbuf - allocp>= n )
{
allocp += n;
return allocp - n;
}
else
return 0;
}
size_t get_line(char* f_line,int n)
{
int c;
size_t size=(size_t)f_line;
while(((size_t)f_line-size)<n && (c=getchar())!=EOF && c!='\n')
*f_line++=c;
if(c=='\n')
*(f_line++)=c;
*(f_line)='\0';
return (size_t)f_line-size;
}