报告.cpp

初学者个人做的数据结构课程设计

//	Trie常用功能模版
//	findWord	查找单词并输出节点message
//	Insert	添加单词
//	deleteWord	删除单词
//	freeTrie	释放Trie

#include <stdio.h>           //头文件说明
#include <string.h>
#include <stdlib.h>  
#include <ctype.h>

///////////////////////////////////////////
#define MAXCH 26	  //字母个数
#define MAXSTR 100	  //字符串最大长度
#define startch 'a'	//定义开始字符位置，现假设全是小写字母
/*********************************/
struct MESSAGE {
	char Word[40];//结点信息---单词解释
	char number[40];
	void Init ()    //信息初始化
	{ int i;
	  for(i=0;i<40;i++)
	  {
	  number[i]=NULL;
	  Word[i]=NULL;
	  return ;
	  }
	}
};

//Trie结构及其函数
struct TrieNode {
	MESSAGE msg;				//此结点保存的信息
	bool isLeaf;				//标记是否为叶子节点
	TrieNode* ptr[MAXCH];	    //指针域
	TrieNode(){                 //结点初始化，包括令子节点为空
	isLeaf = false;
	memset(ptr,NULL, sizeof(ptr));//memset函数初始化 ptr[MAXCH]全为0
	}
};
typedef TrieNode* TrieRoot;

FILE *in,*out;    //文件指针

//模块函数
char str[MAXSTR];	//输入单词
char outp=NULL;    //output()选项
void Traverse(TrieRoot root,int i)
{
    if(root->isLeaf==1)
    {
		printf("%s:%s\n",root->msg.Word,root->msg.number);
		if(outp=='c')                         //写文件
		{
		        fputs(root->msg.Word,out);		        	
				fputs(" ",out);
				fputs(root->msg.number,out);
				fputs("\n",out); 
		}
	}
    for(int j=0;j<26;j++)
    {
        if(root->ptr[j]!=NULL)
        {
           Traverse(root->ptr[j],i+1);
        }
    }
}

TrieRoot findWord(TrieRoot root, char* word)       //查找单词
{   char str[40];
	if (root==NULL)
	{
		printf("无此单词\n");
		return NULL;
	}
	if (*word=='\0')
	{                     
		if (root->isLeaf && outp=='a')                      //成功
			printf("查询成功! 意思: %s\n",root->msg.number);
		return root;
	}
	return findWord(root->ptr[*word - 'a'], word+1); // *word-'a'为计算word指针所指向的字母在字母表的位置
}

void Insert(TrieRoot root, char* word, MESSAGE &tmp) {	//插入单词和意思
	if (*word=='\0') 
	{
		root->msg = tmp;
		root->isLeaf = true;
		return;
	}		
	if (root->ptr[*word - startch]==NULL )	//如果当前节点为空，生成新节点
		root->ptr[*word - startch] = new TrieNode;
	Insert(root->ptr[*word - startch], word+1, tmp);
}

void deleteWord(TrieRoot root, char* word)	 //删除单词
{
	if (*word=='\0')
		{
			root->isLeaf = false;                //节电信息置空
			return;
		}
	deleteWord(root->ptr[*word - 'a'], word+1);
}
int check(char str[40])
{
	for(int i=0;i<strlen(str);i++)
		if(islower(str[i])==0) 
		{
			printf("%s不是一个单词.\n",str); 
			return 0;
		}
	return 1;
}

char output()
{
    printf("|--------------------------------|\n");
    printf("|------------查  询--------------|\n");
    printf("|---a--精确查询(未找到则插入)----|\n");
    printf("|---b------模 糊 查 询-----------|\n");
    printf("|--------------------------------|\n");
	printf("请选择：");
    char select[10],se=NULL;
	scanf("%s",select);
	if(strlen(select)==1)
	    return select[0];
	else return 0;
}

void freeTrie(TrieRoot root) {	                         //释放Trie
	for (int i = 0; i < MAXCH; ++i)
		if (root->ptr[i])
			freeTrie(root->ptr[i]);
	free(root);
}
//////////////////////////////////////////////////////
void main ( ) 
{	
	printf("\n");
	printf("***************************英语词典单词识别与维护*******************************\n");
    printf("            设计者:陶杰         班级：网络061          学号:110612119     \n");				   ;
    printf("--------------------------------------------------------------------------------\n");
	MESSAGE temp;		//单词节点信息
    char chance[10],ch=NULL;
	TrieRoot Root = new TrieNode;        //开辟新节点
	TrieRoot root = Root;
	if((in=fopen("test.txt","r"))==NULL)
	{
		printf("单词库为空或不存在!\n");	
	}			   
	else{while(!feof(in))                    //读取文件内容建立键树
	{
		fscanf(in,"%s %40[^\n]",temp.Word,temp.number); //读取单词内容及意思
		strcpy(str,temp.Word);
		Insert(Root, str, temp);                  //插入
	}
	fclose(in);
	printf("创建成功!!\n");  
	}             //成功
do{ 
	printf("\n");                  /*功能清单输出表*/ 
    printf("|-------------------------------|\n");
    printf("|------ 英语单词辅助记忆系统 ---|\n");
	printf("|---------- 请选择 (a--d) ------|\n");
    printf("|-------------------------------|\n");
    printf("|---- a ---- 查找-插入 ---------|\n");
    printf("|---- b ------ 删除 ------------|\n");
	printf("|---- c ------ 清屏 ------------|\n");
	printf("|---- d -- 修改单词意思 --------|\n");
    printf("|---- e ------ 退出 ------------|\n");
    printf("|-------------------------------|\n");
	printf("请选择：(单词限制为小写字母)\n");
	scanf("%s",chance);
	if(strlen(chance)==1)
		ch=chance[0];
	else ch=NULL;
    switch(ch){                      //功能实现模块
	case 'a':outp=output();
			if(outp=='a')
			{
					   do{ 
						   puts("请输入你要查找的单词 \n");
	    	               scanf("%s",str);
						   if(check(str)==0)  break; 				     //判断是否为单词
							   if (findWord(Root,str)==NULL)
							   {
								   printf("确认添加单词按'Y'或'y',否则退出：\n");
								   scanf("%s",chance);
								   if(strlen(chance)==1)
								  	   ch=chance[0];
								   if(ch!='Y' && ch!='y')
								   {
									   printf("不插入单词:\n"); 
									   break;
								   }
								   strcpy(temp.Word,str);
								   puts("没有找到!\n请输入插入单词意思： ");
								   scanf("%s",(temp.number));	
								   Insert(Root, str, temp);                  //插入
							   }	
							   printf("\n按'N'或'n'退出,按其他任意键继续查找 :");
							   scanf("%s",chance);
							   if(strlen(chance)==1)
								   ch=chance[0];
					   }while(ch!='N' && ch!='n');
			}
			else if(outp=='b')
			{
				do{
				printf("请输入字符：");
			    scanf("%s",str);  
				if(check(str)==0)  break; 				     //判断是否为单词
				root=findWord(Root, str); 
				if(root==NULL) break;
				Traverse(root,0);
	    	         printf("\n按'N'或'n'退出,按其他任意键继续查找 :");	
					 scanf("%s",chance);
					 if(strlen(chance)==1)
						 ch=chance[0];
				}while(ch!='N' && ch!='n');
			}
			else printf("选择错误：\n");
		break;
	case 'b':	puts("请输入你要删除的单词 : ");               
	            scanf("%s",str);
				if(check(str)==0)  break; 				     //判断是否为单词
				if (findWord(Root, str)){              //查找单词信息
            	deleteWord(Root, str);             //在TRIE树删除单词及信息 
				printf("删除成功!\n");
					}
				else printf("没有此单词!\n");
			break;
	case 'c':system("cls");break;
    case 'd':printf("输入要改动的单词:\n");
		scanf("%s",str);
		if(check(str)==0)  break; 				     //判断是否为单词
		root=findWord(Root,str);
		if (root==NULL) 	break;
		printf("输入更改的意思:\n");
		scanf("%s",root->msg.number);  
		printf("更改成功:\n");break;
    case 'e':break;
    default:printf("请输入a、b、c、d或e:\n");break;
	}
}while(ch!='e');
outp='c';
if((out=fopen("test.txt","w+"))==NULL)      //打开文件
printf("cann't create file\n");
Traverse(Root,0);
printf("已经自动保存:\n");
scanf("%s",chance);
fclose(out);
freeTrie(Root);    //释放Trie8
}