实验2 字典排序问题

问题描述：本程序将一段以*结束的文本中的单词按字典顺序打印出来，并且打印出该单词在正文中的出现次数。 如输入： abc abc def hig ijk* 则输入： 2 abc 1 def 1 hig 1 ijk 前面的整数表示单词出现在文本中的次数，并且单词都是按字典排序以后再输出。 考虑到二叉树可以很容易地递归实现，我们使用二叉树排序树来实现文本中单词按字典排序。程序中使用二叉树存入单词，即每次从文件中读出一个单词，都将其按单词的字典顺序存入一个二叉排序树，第一个存入的单词为二叉树的根。读完文件中的单词后，中序遍历打印出二叉树中存放的各个单词。 为了使存储空间使用更加合理且能够处理任意长度的单词，程序设立了一个数组text，所有读入的单词都放在text数组中。函数getword完成读入单词的操作，并返回所读入的单词的长度。函数insert完成二叉排序树中插入一个新结点的操作并返回指向二叉树跟接点的指针。 部分代码： typedef struct node *tree; //树接点定义 struct node { char *data; int count; tree lchild; tree rchild; };

getword(char *word) //获取文本函数 { int i = 0; if(ch=='*')return (0); while (ch==' '||ch=='\t'||ch=='\n') ch = getchar(); while (ch!=' '&&ch!='\t'&&ch!='#') { word[i++] = ch; ch = getchar(); } word[i++] = 0; return (i); }

tree insert(tree rootroot x) //构建二叉排序树的函数 char *x; { tree p; int res; if(root == NULL) { p = (tree)malloc(sizeof(*p)); p -> data = x; p -> count = 1; p ->lchild = NULL; p ->rchild = NULL; return (p); } else if((res = strcmp(x,root->data))<0) root ->lchild = insert(root->lchild,x); else if(res > 0) root -> rchild = insert(root->rchild,x); else root->count ++; return (root); }

printf_tree(root) //打印函数 tree root; { if(root!=NULL) { print_tree(root->lchild); printf("%d %s \n",root->count,root->data); printf_tree(root->rchild); } }