一学一做看视频网站营销型网站建设总结

自引用结构

任务：统计输入中所有出现单词的次数。

两种解决方法：

<1>、在读取输入中任意单词的同时，就将它放置到正确的位置，从而始终保证所有单词是按顺序排列的。

<2>、采用一种二叉树的数据结构

每个不同的单词在树中都是一个节点，每个节点包括：

一个指向该单词内容的指针

一个统计出现次数的计数值

一个指向左子树的指针

一个指向右子树的指针

任何节点最多拥有两个子树，也可能只有一个子树或一个都没有。

要点：对节点的所有操作都要保证，任何节点的左子树只包含按字典序小于该节点中单词的那些单词，右子树只包含按字典序大于该节点中单词的那些单词。

标准库函数malloc能满足对齐要求

 

#include <stdio.h>
#include<string.h>
#include<ctype.h>
#define MAXWORD 100
struct tnode {
char *word;
int count;
struct tnode *left;
struct tnode *right;
};
struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int );
int main(void)
{
struct tnode *root;
char word[MAXWORD];
root = NULL;
while (getword(word,MAXWORD) != EOF)
if (isalpha(word[0]))
root = addtree(root, word);
treeprint(root);
return 0;
}
struct tnode *talloc(void);
char *strdup1(char *);
/*
*addtree函数：在p的位置或p的下方增加一个w节点
*/
struct tnode *addtree(struct tnode *p, char *w)
{
int cond;
if (p == NULL) {
p = talloc();
p->word = strdup1(w);
p->count = 1;
p->left = p->right = NULL;
}
else if ((cond = strcmp(w, p->word)) == 0)
p->count++;
else if (cond < 0)
p->left = addtree(p->left, w);
else
p->right = addtree(p->right, w);
return p;
}
/*
*treeprint函数：按序打印树p
*/
void treeprint(struct tnode *p)
{
if (p != NULL) {
treeprint(p->left);
printf("%4d %s\n",p->count, p->word);
treeprint(p->right);
}
}
/*
*talloc函数：创建一个tnode
*/
#include <stdlib.h>
struct tnode *talloc(void)
{
return (struct tnode *)malloc(sizeof(struct tnode));
}
/*
*strdup函数：把传入的参数字符串复制到某个安全的位置
*/
char *strdup1(char *s)
{
char *p;
p = (char *)malloc(strlen(s) + 1);
if (p != NULL)
strcpy(p, s);
return p;
}
int getch1(void);
void ungetch1(int);
/*
*getword函数：从输入中读取下一个单词或字符
*/
int getword(char* word, int lim)
{
int c;
char *w = word;
while (isspace( c = getch1()))
;
if (c != EOF)
*w++ = c;
if (!isalpha(c))
{
*w = '\0';
return c;
}
for (; --lim > 0; w++)
if ( !isalnum( *w = getch1()))
{
//	printf("in the getword()");
ungetch1(*w);
break;
}
*w = '\0';
return word[0];
}
#define BUFSIZE 1000
char buf[BUFSIZE];
int bufp = 0;
int getch1(void)
{
return (bufp > 0) ?buf[--bufp] : getchar();
}
void ungetch1(int c)
{
if (bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}