K&R 第六章结构

统计输入中所有单词的出现次数,使用二叉树结构

#define BUFSIZE 100
char buf[BUFSIZE];
int bufp=0;

int getch(void) //从缓冲区读取字符 
{
	return (bufp>0) ? buf[--bufp]:getchar();
}

//把字符压回共享缓存区 
void ungetch(int c)
{
	if(bufp>=BUFSIZE)
		printf("ungetch:too many characters\n");
	else
		buf[bufp++]	=c;
}


////统计输入中所有单词的出现次数,使用二叉树结构 
#include <stdio.h>
#include <ctype.h>
#include <string.h>

typedef struct tnode{
	char *word;
	int count;
	struct tnode *left;
	struct tnode *right;
}tnode;

#define MAXWORD 100
tnode* addtree(struct tnode*,char*);
void treeprint(tnode*);
int getword(char*,int);

int main()
{
	tnode *root;
	char word[MAXWORD];
	
	root=NULL;
	while(getword(word,MAXWORD) !=EOF)
		if(isalpha(word[0]))
			root =addtree(root,word);
	treeprint(root);
	return 0;
}


tnode *talloc(void);
char *strdup(char*);

tnode *addtree(tnode *p,char *w)
{
	int cond;
	
	if(p ==NULL)
	{
		p=talloc();
		p->word=strdup(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;	
}

void treeprint(tnode*p)
{
	if(p !=NULL)
	{
		treeprint(p->left);
		printf("%4d %s\n",p->count,p->word);
		treeprint(p->right);
	}
}

#include <stdlib.h>

tnode*talloc(void)
{
	return(tnode*)malloc(sizeof(tnode));
}

char *strdup(char *s)
{
	char *p;
	p=(char*)malloc(strlen(s)+1);
	if(p!=NULL)
		strcpy(p,s);
		return p;
}

#include <stdio.h>
#include <ctype.h>

int comment(void)
{
	int c;
	while((c=getch())!=EOF)
		if(c=='*')
			if((c=getch()) =='/')
				break;
			else
				ungetch(c);
	return c;			
}

//6-1 处理下划线、字符串常数、注释及预编译器控制指令 
int getword(char*word,int lim)
{
	int c,d;
	char *w=word;
	
	while(isspace(c=getch()))
			;
	if(c!=EOF)
		*w++ =c;
	if(isalpha(c) ||c=='_'||c=='#')
	{
		for(;--lim>0;w++)
			if(!isalnum(*w=getch()) &&*w!='#')
			{
				ungetch(*w);
				break;
			}
	}
	else if(c=='\'' ||c=='"')
	{
		for(;--lim>0;w++)
			if((*w=getch()) =='\\')
				*++w=getch();
			else if(*w==c)
			{
				w++;
				break;				
			}
			else if(*w==EOF)
			 break;
				
	}
	else if(c=='/')
		if((d=getch())=='*')
			c=comment();
		else
			ungetch(d);
	*w='\0';
	return c;
}

6-2 编写一个程序，用以读入一个C语言程序，并按照字符表顺序分组打印变量名，要求每一组各变量名的前6个字符相同,其余字符不同。字符串和注释中的单词不予考虑。请将6作为一个可在命令行中设定的参数

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

typedef struct tnode{
	char *word;
	int match;
	struct tnode *left;
	struct tnode *right;
}tnode;

#define MAXWORD 100
#define YES     1
#define NO      0

int compare(char*s,tnode*p,int num,int*found)
{
	int i;
	char*t=p->word;
	for(i=0;*s==*t;i++,s++,t++)
		if(*s=='\0')
			return 0;
	if(i>=num)
	{
		*found=YES;
		p->match=YES;
	}
	return *s-*t;
}

tnode*addtreex(tnode *p,char*w,int num,int *found)
{
	int cond;
	
	if(p ==NULL){
		p=talloc();
		p->word=strdup(w);
		p->match=*found;
		p->left=p->right=NULL;
	}
	else if((cond=compare(w,p,num,found))<0)
		p->left= addtreex(p->left,w,num,found);
	else if(cond>0)
		p->right=addtreex(p->right,w,num,found);
	return p;	
}

void treexprint(tnode *p)
{
	if(p !=NULL)					//中序遍历打印,完成分组打印效果 
	{
		treexprint(p->left);	
		if(p->match)
			printf("%s\n",p->word);
		treexprint(p->right);
	}
}




int main(int argc,char* argv[])
{
	tnode *root;
	char word[MAXWORD];
	int found=NO;      //YES if match was found
	int num;
	
	num=(--argc&&(*++argv)[0]== '-')?atoi(argv[0]+1):6;
	root=NULL;
	while(getword(word,MAXWORD) !=EOF){
		if(isalpha(word[0])&&strlen(word)>=num)  //单词第一个字符是字母且长度大于等于num 
			 root=addtreex(root,word,num,&found);
		found=NO;
	}
	treexprint(root);
	return 0;
}

6-3 编写一个交叉引用程序,打印文档中所有单词的列表，并且每个单词还有一个列表,记录出现过该单词的行号.对the、and等非实义单词不予考虑。

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define MAXWORD 100

struct linklist{    //linked list of line numbers
	int lnum;
	struct linklist *ptr;
};

struct tnode{
	char *word;
	struct linklist*lines;  //line numbers
	struct tnode *left;
	struct tnode *right;
};

//lalloc:make a linklist node
struct linklist *lalloc(void)
{
	return (struct linklist*)malloc(sizeof(struct linklist));
}

void addin(struct tnode*p,int linenum)
{
	struct linklist*temp;
	temp=p->lines;
	while(temp->ptr !=NULL &&temp->lnum!=linenum) //检查链表中是否存在相同的行号
		temp=temp->ptr;
	if(temp->lnum !=linenum)
	{
		temp->ptr=lalloc();
		temp->ptr->lnum=linenum;
		temp->ptr->ptr=NULL;
	}
}

struct tnode *addtreex(struct tnode*p,char*w,int linenum)
{
	int cond;
	
	if(p ==NULL)
	{
	  p=talloc();
	  p->word=strdup(w);
	  p->lines=lalloc();
	  p->lines->lnum=linenum;
	  p->lines->ptr=NULL;
	  p->left=p->right=NULL;
	}else if((cond=strcmp(w,p->word))==0)
		addin(p,linenum);
	else if(cond<0)
		p->left=addtreex(p->left,w,linenum);
	else
		p->right=addtreex(p->right,w,linenum);
	return p;	
}


void treexprint(struct tnode *p)
{
	struct linklist *temp;
	if(p!=NULL)
	{
		treexprint(p->left);
		printf("%10s:",p->word);
		for(temp=p->lines;temp!=NULL;temp=temp->ptr)
			printf("%4d",temp->lnum);
		printf("\n");
		treexprint(p->right);
	}
}



int noiseword(char *w)
{
	static char *nw[]={
	"a",
	"an",
	"are",
	"in",
	"is",
	"of",
	"or",
	"that",
	"the",
	"this",
	"to"
	};
	
	int cond,mid;
	int low=0;
	int high=sizeof(nw)/sizeof(char*)-1;
	
	while(low<=high)
	{
		mid=(low+high)/2;
		if((cond=strcmp(w,nw[mid]))<0)
			high=mid-1;
		else if(cond>0)
			low=mid+1;
		else
			return mid;	 
	}
	return -1;
	
}


int getword(char*word,int lim)
{
	int c,d;
	char *w=word;
	
	while(isspace(c=getch())&&c!='\n' ) //返回换行符 
			;
	if(c!=EOF)
		*w++ =c;
	if(isalpha(c) ||c=='_'||c=='#')
	{
		for(;--lim>0;w++)
			if(!isalnum(*w=getch()) &&*w!='#')
			{
				ungetch(*w);
				break;
			}
	}
	else if(c=='\'' ||c=='"')
	{
		for(;--lim>0;w++)
			if((*w=getch()) =='\\')
				*++w=getch();
			else if(*w==c)
			{
				w++;
				break;				
			}
			else if(*w==EOF)
			 break;
				
	}
	else if(c=='/')
		if((d=getch())=='*')
			c=comment();
		else
			ungetch(d);
	*w='\0';
	return c;
}

int main()
{
	struct tnode *root;
	char word[MAXWORD];
	int linenum=1;
	
	root=NULL;
	
	while(getword(word,MAXWORD)!=EOF)
	{
		if(isalpha(word[0]) &&noiseword(word)==-1)
			root=addtreex(root,word,linenum);
		else if(word[0]=='\n')
			 linenum++;		
	}
	treexprint(root);
	return 0;
}

6-4 编写一个程序，根据单词的出现频率按降序打印输入的各个不同单词，并在每个单词的前面标上它的出现次数。

K&R 第六章 结构

全站热榜

K&R 第六章结构