链表实例：对英语文本文件单词字符出现频率统计


  1 #include    <stdio.h>
  2 #include    <string.h>
  3 #include    <stdlib.h>
  4 #include    <ctype.h>
  5 
  6 
  7 #define WORD_LEN 25
  8 
  9 
 10 typedef struct word_info{
 11     char word[WORD_LEN];
 12     struct word_info *prev;
 13     struct word_info *next;
 14     int cnt;
 15 }word_info;
 16
 17 FILE * open_file(const char *filename){　
 18     FILE *fp = NULL;
 19 
 20     fp = fopen(filename,"r");
 21     if(!fp){
 22         fprintf(stderr, "fopen %s error
", filename);
 23         return NULL;
 24     }
 25 
 26     return fp;
 27 }
 28 
 29 static word_info *Creat_node(void){
 30     word_info *pnew;
 31     pnew = (word_info *)malloc(sizeof(word_info));
 32     if(!pnew){
 33         fprintf(stderr, "malloc error");
 34         return NULL;
 35     }
 36     pnew->prev = NULL;
 37     pnew->next = NULL;
 38     pnew->cnt = 0;
 39 
 40     return pnew;
 41 }
 42 
 43 int insert_node(word_info **phead, word_info *pnew){
 44     word_info * pcur = *phead;
 45     if(!*phead){
 46         *phead = pnew;
 47         return 0;
 48     }
 49     do{
 50         if(strcasecmp(pcur->word, pnew->word) == 0){
 51             pcur->cnt++;
 52             free(pnew);
 53             return 0;
 54             }    
 55         if(pcur->next != NULL)
 56             pcur = pcur->next;
 57         else
 58             break;
 59     }while(1);
 60     
 61     pnew->prev = pcur;
 62     pcur->next = pnew;
 63 
 64     return 0;
 65 }
 66 
 67 int read_words(FILE *fp,word_info **phead){
 68     char word[WORD_LEN];
 69     word_info *pnew;
 70     int flag = 1;
 71     int i = 0;
 72     int ch;
 73 
 74     pnew = Creat_node();
 75     if(!pnew)
 76         return -1;
 77     
 78     while ((ch = fgetc(fp)) != EOF){
 79         if(isalpha(ch)){
 80             word[i++] = ch;
 81             flag  = 0;
 82         }
 83         else{
 84             if(ch == '?'){
 85                 strcpy(pnew->word, "?");
 86                 pnew->cnt++;
 87                 insert_node(phead, pnew);
 88                 pnew = Creat_node();    
 89             }
 90             if(ch == '.'){
 91                 strcpy(pnew->word, ".");
 92                 pnew->cnt++;
 93                 insert_node(phead, pnew);
 94                 pnew = Creat_node();    
 95             }
 96             if(ch == ','){
 97                 strcpy(pnew->word, ",");
 98                 pnew->cnt++;
 99                 insert_node(phead, pnew);
100                 pnew = Creat_node();    
101             }
102             if(ch == '"'){
103             strcpy(pnew->word, """);
104             pnew->cnt++;
105             insert_node(phead, pnew);
106             pnew = Creat_node();    
107             }
108             if((isblank(ch) || ch == ',' ||    ch == '!' || ch == '.' || 
109                         ch == '"' || ch == '?')    && !flag)
110             {
111                 word[i] = 0;
112                 strncpy(pnew->word, word, i+1);
113                 pnew->cnt++;
114                 insert_node(phead, pnew);
115                 pnew = Creat_node();
116                 flag = 1;
117                 i = 0;    
118             }
119         }
120     }
121     if(!i)
122         free(pnew);
123     
124     return 0;
125 }
　/*
　　　　还有就是双链表的弊端，还要判断下个节点是否为空，设置下个节点的prev。判断上一个节点是否为空
　　　（这是没有无头节点的弊端如果是带头节点，哪怕是第一个带数据节点的prev也不会为空，就不用分别处理）
　　　　设置上一个节点的next。
*/
126 void swap_node(word_info *w1, word_info *w2){
127     if(w1->next == w2){
128         if(w2->next != NULL)
129             w2->next->prev = w1;
130         if(w1->prev != NULL)
131             w1->prev->next = w2;
132         w1->next = w2->next;
133         w2->prev = w1->prev;
134         w1->prev = w2;
135         w2->next = w1;
136     }else{
137         if(w1->next != NULL){
138             w1->next->prev = w2;
139         }
140         if(w1->prev != NULL){
141             w1->prev->next = w2;
142         }
143         if(w2->next != NULL){
144             w2->next->prev = w1;
145         }
146         if(w2->prev != NULL){
147             w2->prev->next = w1;
148         }
149         word_info *w1next = w1->next;
150         word_info *w1prev = w1->prev;
151         w1->next = w2->next;
152         w1->prev = w2->prev;
153         w2->next = w1next;
154         w2->prev = w1prev;
155     }
156 }
157 
158 int sortByCnt(word_info **phead){
159     word_info *head =  *phead;
160     int flag = 1;
161 　　
162     if(head->prev != NULL)
163         head = head->prev;
164     while(head != NULL){
165         word_info *headnext = head->next;
166         while(headnext != NULL){
167             if(head->cnt < headnext->cnt){
168                 swap_node(head, headnext);
169                 word_info * tmp = head;
170                 head = headnext;
171                 headnext = head;
172             }
173             headnext = headnext->next;
174         }
175         if(flag){
176             *phead = head;
177             flag = 0;
178         }
179         head = head->next;
180     }
181     return 0;
182 }
183 
184 
185 void print_words(word_info *phead){
186 
187     word_info *pcur = phead;
188     while(pcur){
189         printf("%30s: appears %3d times
", pcur->word
190                 , pcur->cnt);
191         pcur = pcur->next;
192     }
193 }
194 
195 
196 void destroy_link(word_info *phead){
197     word_info *pcur = phead, *ptmp;
198 
199     while(pcur){
200         ptmp = pcur->next;
201         free(pcur);
202         pcur = ptmp;
203     }
204 }
205 
206 int main(int argc, char * argv[])
207 {
208     FILE *fp;
209     word_info *head = NULL;
210     int ret;
211 
212     fp = open_file(argv[1]);
213     if(!fp)
214         return -1;
215 
216     ret = read_words(fp, &head);
217     if(ret < 0)
218         fprintf(stderr, "read words error");
219     sortByCnt(&head);
220     print_words(head);
221     destroy_link(head);
222     fclose(fp);
223 
224     return 0;
225 }
这是用的双向链表，但是没有体现出双向链表的优点。基本都是正序操作。
Running Demo: