续“上学期同学给的C语言练习”
exercise.7-3.<The C programming Language>.Page136

exercise.6-4 in <The C programming Language> ,page125

TLHL28 posted @ Tue, 24 Jun 2008 06:32:26 +0800 in C语言 with tags C语言 , 1637 readers

这个.......

  1. /* 编写一个程序,根据单词的出现频率安降序打印输入的各个不同单词,并
  2. * 在每个单词的前面标上它的出现次数。
  3. * exercise.6-4 in <The C programming Language> ,page125*/
  4. #include <stdio.h>
  5. #include <ctype.h>
  6. #include <string.h>
  7.  
  8. #define MAXWORD 100
  9.  
  10. struct tnode {    /*  树的节点      */
  11.     char *word;  /*  指向单词的指针  */
  12.     int count;    /*  单词出现的次数  */
  13.     struct tnode *left; /*  左子节点     */
  14.     struct tnode *right;/*  右子节点            */
  15.     struct snode *snode;/*  指向该单词在sort树中的节点       */
  16. };
  17.  
  18. struct snode {        /*    sort树的节点    */
  19.     struct tnode *tnode;    /*  指向该节点所放置的单词,在单词树中的节点        */
  20.     struct snode *left;     /*   左子节点    */
  21.     struct snode *right;    /*  右子节点    */
  22. };
  23.  
  24. struct tnode *addtree(struct tnode *, char *);
  25.  
  26. /*addtree_sort函数: 通过比较单词出现次数,将其放置到sort树中*/
  27. struct snode *addtree_sort(struct snode *, struct tnode *);
  28. /*sortTree函数: 对单词树(tnode)进行排序*/
  29. void sortTree(struct tnode *);
  30. void treeprint(struct snode *);
  31. int getword(char *, int);
  32.  
  33. struct tnode *talloc(void);
  34.  
  35. /*为sort树中的新节点分配空间*/
  36. struct snode *stalloc(void);
  37. char *mystrdup(char *);
  38.  
  39. struct snode *sroot = NULL;
  40. /*  单词出现频率的统计 */
  41. int main()
  42. {
  43.     struct tnode *root;
  44.     char word[MAXWORD];
  45.  
  46.     root = NULL;
  47.     while (getword(word,MAXWORD) != EOF)
  48.         if (isalpha(word[0]))
  49.                 root = addtree(root, word);
  50.     sortTree(root);
  51.     treeprint(sroot);
  52.     return 0;
  53. }
  54.  
  55.  
  56. /*  addtree函数: 在p的位置或p的下方增加一个w节点    */
  57. struct tnode *addtree(struct tnode *p, char *w)
  58. {
  59.     int cond;
  60.  
  61.     if (p == NULL) {    /*  该单词是一个新单词*/
  62.         p = talloc();   /*  创建一个新节点*/
  63.         p->word = mystrdup(w);
  64.         p->count = 1;
  65.         p->left = p->right = NULL;
  66.         p->snode = NULL;
  67.     } else if ((cond = strcmp(w, p->word)) == 0)
  68.         p->count++;
  69.     else if (cond < 0)
  70.         p->left = addtree(p->left,w);
  71.     else
  72.         p->right = addtree(p->right,w);
  73.     return p;
  74. }
  75.  
  76. /*sortTree函数: 接受单词树排序输出的节点
  77. * 然后将其节点放置到sort树中相应节点中*/
  78. void sortTree(struct tnode *p)
  79. {
  80.     if (p != NULL) {
  81.         sortTree(p->left);
  82.         sroot = addtree_sort(sroot,p);
  83.         sortTree(p->right);
  84.     }
  85. }
  86.  
  87. struct snode *addtree_sort(struct snode *ps, struct tnode *p)
  88. {
  89.     if (ps == NULL) {   /*  若sort树添加新节点*/
  90.         ps = stalloc();
  91.         ps->tnode = p; /*   记录放置在该节点的单词---在单词树中的节点*/
  92.         p->snode = ps; /*   将该节点记录到该单词节点中相应的位置*/
  93.         ps->left = ps->right = NULL;
  94.     } else if (p->count >= ps->tnode->count)
  95.         ps->right = addtree_sort(ps->right, p);
  96.     else
  97.         ps->left = addtree_sort(ps->left, p);
  98.     return ps;
  99. }
  100.  
  101. /*  treeprint函数: 排序打印sort树        */
  102. void treeprint(struct snode *ps)
  103. {
  104.     if (ps != NULL) {
  105.         treeprint(ps->left);
  106.         printf("%4d %s\n",ps->tnode->count,ps->tnode->word);
  107.         treeprint(ps->right);
  108.     }
  109. }
  110.  
  111.  
  112. #include <stdlib.h>
  113.  
  114. /*  talloc函数: 创建一个tnode     */
  115. struct tnode *talloc(void)
  116. {
  117.     return (struct tnode *) malloc(sizeof(struct tnode));
  118. }
  119.  
  120. struct snode *stalloc(void)
  121. {
  122.     return (struct snode *) malloc(sizeof(struct snode));
  123. }
  124.  
  125. char *mystrdup(char *s) /*copy s to safe place*/
  126. {
  127.     char *p;
  128.  
  129.     p = (char *) malloc(strlen(s)+1);
  130.     if (p != NULL)
  131.         strcpy(p, s);
  132.     return p;
  133. }
  134.  
  135. int getword(char *word, int lim)
  136. {
  137.     int c, getch(void);
  138.     void ungetch(int);
  139.     char *w = word;
  140.  
  141.     while (isspace(c = getch()))
  142.         ;
  143.     if (c != EOF)
  144.         *w++ = c;
  145.     if (!isalpha(c)) {
  146.         *w = '\0';
  147.         return c;
  148.     }
  149.     for ( ; --lim > 0; w++)
  150.         if (!isalnum(*w = getch())) {
  151.             ungetch(*w);
  152.             break;
  153.         }
  154.     *w = '\0';
  155.     return word[0];
  156. }
  157.  

  158. Login *


    loading captcha image...
    (type the code from the image)
    or Ctrl+Enter