Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147113
| From | DFS <nospam@dfs.com> |
|---|---|
| Subject | Re: How to use a struct with qsort()? |
| Newsgroups | comp.lang.c |
| References | (5 earlier) <60434cb2-a003-454b-890f-f2121004bd22@googlegroups.com> <wbLqF.74859$pe2.47975@fx34.iad> <1ca42f72-9e0e-40c3-8ef0-b5002e079cef@googlegroups.com> <l5MqF.242244$iJ2.110801@fx47.iad> <07784ff9-2fee-49e6-8271-22d713294245@googlegroups.com> |
| Message-ID | <bdZqF.216192$TC2.20635@fx43.iad> (permalink) |
| Organization | blocknews - www.blocknews.net |
| Date | 2019-10-20 09:22 -0400 |
On 10/19/2019 7:32 PM, already5chosen@yahoo.com wrote:
> On Sunday, October 20, 2019 at 1:27:37 AM UTC+3, DFS wrote:
> o.k. I don't know why, but I read your code.
> Turned out, you don't have an array of records. For some reason, you decided to build an array of pointers to records. That's quite different!
> Your comparison function should take that into account and to use double indirection, like that:
>
> int comparepf(const void *p1, const void *p2)
> {
> const struct words *a = *(const struct words **)p1;
> const struct words *b = *(const struct words **)p2;
> if (a->wordpf == b->wordpf)
> return strcmp(a->word, b->word);
> return a->wordpf < b->wordpf ? -1 : 1;
> }
The qsort now works.
Thanks!
> BTW, I repeat my advice from above. Your code looks very non-idiomatic, very script-kidddish.
> Tutorial can help.
Exactly which lines look 'script-kiddish'? How would you improve them?
original code in this thread
========================================================================
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string.h>
4 #include <time.h>
5 #include <Windows.h>
6
7 //windows tcc compile
8 //tcc -o anagrams.exe anagrams.c
9
10 //usage
11 //anagrams wordlist.txt searchword
12
13 //vars
14 int i=0, j=0, k=0;
15 int primes[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
16 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
17 char *charset = "abcdefghijklmnopqrstuvwxyz";
18
19 LARGE_INTEGER frequency,start,end;
20
21 //build struct
22 struct words {char *word; double wordpf;};
23 struct words **wordrec = NULL;
24
25
26 //program timing
27 double elapsedtime(LARGE_INTEGER startingtimer)
28 {
29 QueryPerformanceCounter(&end);
30 return (end.QuadPart - startingtimer.QuadPart) /
(double)frequency.QuadPart;
31 }
32
33 //compute product of primes corresponding to the letters of the
input word
34 double calcpf(char *str, int len) {
35 double pf = 1;
36 for(i=0;i<len;i++) {
37 pf *= primes[(int)(strchr(charset, str[i]) - charset)];
38 }
39 return pf;
40 }
41
42 //trim trailing spaces
43 void righttrim(char *str, int len) {
44 while(len>0 && isspace(str[len-1])){
45 len--;
46 }
47 str[len] = '\0';
48 }
49
50 //sort structure by prime factors, then word
51 int comparepf(const void *p1, const void *p2)
52 {
53 const struct words *a = p1;
54 const struct words *b = p2;
55 //printf("%.0lf %.0lf\n",a->wordpf,b->wordpf);
56 if(a->wordpf > b->wordpf)
57 return 1;
58 else if (a->wordpf < b->wordpf)
59 return -1;
60 else
61 return 0;
62 }
63
64
65 int main(int argc, char *argv[])
66 {
67
68 QueryPerformanceFrequency(&frequency);
69
70 printf("\nloading data...");
71
72 //read in list of words, load into struct
73 int wordcnt = 0;
74 char wordin[30];
75 char *filein = argv[1];
76 char *searchword = argv[2];
77 FILE *fwords;
78
79 QueryPerformanceCounter(&start);
80 fwords = fopen(filein,"r");
81 while(fgets(wordin,sizeof(wordin),fwords)!=NULL) {
82
83 //trim trailing spaces
84 righttrim(wordin,strlen(wordin));
85
86 //memory
87 wordrec = (struct words **)realloc(wordrec,(wordcnt+1) *
sizeof(struct words *));
88 wordrec[wordcnt] = (struct words *)malloc(sizeof(struct
words));
89 wordrec[wordcnt]->word = malloc(strlen(wordin)+1);
90
91 //add entry to struct
92 strcpy(wordrec[wordcnt]->word, wordin);
93 wordrec[wordcnt]->wordpf = calcpf(wordin, strlen(wordin));
94 wordcnt++;
95 }
96 printf("\n%.4fs to load %d words\n\n",elapsedtime(start),wordcnt);
97
98 printf("Contents of struct (word, pf)\n");
99 for(i=0;i<wordcnt;i++) {
100 if(i<10 || i>(wordcnt-11)) {
101 printf("%d. %-18s %-18.0lf\n",i, wordrec[i]->word,
wordrec[i]->wordpf);
102 }
103 }
104
105
106 //for fastest search, sort the struct by prime factorization,
then word
107 //https://stackoverflow.com/search?q=sort+array+of+structs
108 printf("\nsorting by prime factor...\n");
109 QueryPerformanceCounter(&start);
110 qsort(struct wordrec, wordcnt, sizeof(struct wordrec), comparepf);
111 printf("%.4fs to qsort on prime factors\n\n",elapsedtime(start));
112
113 printf("Contents of sorted struct (word, pf)\n");
114 for(i=0;i<wordcnt;i++) {
115 if(i<10 || i>(wordcnt-11)) {
116 printf("%d. %-18s %-18.0lf\n",i, wordrec[i]->word,
wordrec[i]->wordpf);
117 }
118 }
119
120
121 //find single-word anagrams
122 //Two comparisons have to be made, but only do 2 if 1 is a match:
123 //1. compare the prime factorizations (numerical comparison)
124 //2. compare the word itself
125 printf("\nSearching for anagrams of '%s'...\n",searchword);
126 double searchpf = calcpf(searchword, strlen(searchword));
127 char *dataword = NULL;
128 j=0;
129
130 QueryPerformanceCounter(&start);
131 for(i=0;i<wordcnt;i++) {
132 if(wordrec[i]->wordpf==searchpf) {
133 dataword = malloc(strlen(wordrec[i]->word)+1);
134 strcpy(dataword,wordrec[i]->word);
135 if(strcmp(dataword,searchword)!=0)
136 {
137 printf("%s ",dataword);
138 j++;
139 }
140 }
141 }
142
143 if(j>0) {printf("\n%d anagram(s) found in
%.4fs\n",j,elapsedtime(start));}
144 if(j==0) {printf("No anagrams found\n");}
145
146
147
148
149 //finish
150 //free(wordincopy);
151 free(wordrec);
152 fclose(fwords);
153 printf("Done");
154 exit(0);
155 }
========================================================================
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 13:35 -0400
Re: How to use a struct with qsort()? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-10-19 10:22 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 14:19 -0400
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-19 19:36 +0100
Re: How to use a struct with qsort()? Melzzzzz <Melzzzzz@zzzzz.com> - 2019-10-19 18:44 +0000
Re: How to use a struct with qsort()? Barry Schwarz <schwarzb@delq.com> - 2019-10-19 10:23 -0700
Re: How to use a struct with qsort()? Ike Naar <ike@sdf.lonestar.org> - 2019-10-19 19:09 +0000
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 15:51 -0400
Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 13:09 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 16:26 -0400
Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 13:51 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 17:24 -0400
Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 14:49 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-19 18:26 -0400
Re: How to use a struct with qsort()? already5chosen@yahoo.com - 2019-10-19 16:32 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-20 09:22 -0400
Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-26 04:15 -0400
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 09:37 -0400
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-26 15:40 +0100
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-28 19:49 -0400
Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-29 01:59 -0400
Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-30 04:54 -0400
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-30 11:54 +0000
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-30 08:58 -0700
Re: How to use a struct with qsort()? Öö Tiib <ootiib@hot.ee> - 2019-11-07 01:10 -0800
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-11-07 10:51 +0000
Re: How to use a struct with qsort()? Paul <nospam@needed.invalid> - 2019-10-26 15:03 -0400
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-26 21:50 +0100
Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-04 16:02 -0800
Re: How to use a struct with qsort()? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-10-21 11:58 +0000
Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 04:51 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-19 23:25 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-19 15:38 -0700
Re: How to use a struct with qsort()? David Brown <david.brown@hesbynett.no> - 2019-10-20 14:44 +0200
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-22 15:42 -0400
Re: How to use a struct with qsort()? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-10-23 05:47 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-23 16:40 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 13:51 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-23 23:07 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 15:50 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-24 01:20 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-23 18:20 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-24 10:40 +0100
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-24 11:00 -0700
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-20 00:30 +0100
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-20 00:44 +0100
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-20 01:27 +0100
Re: How to use a struct with qsort()? Manfred <noname@add.invalid> - 2019-10-25 20:30 +0200
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-25 16:07 -0400
Re: How to use a struct with qsort()? Ike Naar <ike@sdf.lonestar.org> - 2019-10-26 07:27 +0000
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 02:11 -0700
Re: How to use a struct with qsort()? Bart <bc@freeuk.com> - 2019-10-26 11:06 +0100
Re: How to use a struct with qsort()? Manfred <noname@invalid.add> - 2019-10-26 16:58 +0200
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 18:17 -0400
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 16:08 -0700
Re: How to use a struct with qsort()? DFS <nospam@dfs.com> - 2019-10-26 21:33 -0400
Re: How to use a struct with qsort()? Keith Thompson <kst-u@mib.org> - 2019-10-26 22:10 -0700
Re: How to use a struct with qsort()? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-10-27 01:48 +0100
Re: How to use a struct with qsort()? Manfred <noname@invalid.add> - 2019-10-27 19:29 +0100
Re: How to use a struct with qsort()? Barry Schwarz <schwarzb4aarp@gmail.com> - 2019-10-27 13:09 -0700
csiph-web