数据结构课设报告

课程设计报告题目：英语单词学习助手课程名称：数据结构专业班级：计算机科学与技术1208班学号：U201215033姓名：江振武指导教师：祝建华报告日期：2014年10月29日计算机科学与技术学院任务书设计目的：掌握线性表、串、查找表等数据结构的物理存储结构与基本算法，通过解决较复杂的实际问题，提高学生对数据结构知识综合运用的技能与实践能力。设计内容：以大学英语相关英语文章为语料素材，设计有效的数据结构及其存储结构表示英语单词表，并建立相应的倒排索引，帮助英语学习者在遇到生词时能方便找到生词的相应例句，熟悉其应用语境与地道的用法；设计有效的算法对语料进行清理与分句处理，实现基于索引的快速例句搜索程序。设计要求：（1）输入某一个（或若干个）英语单词，要求返回相应的英语例句。（2）根据单词与语句建立倒排索引，并且索引要求物化到外存，以文件形式保存，每次启动程序时不必重新建立索引，只需将索引文件导入内存。（3）采用图形界面，便于输入单词，例句展现直观，界面布局合理。设计提示：按三步进行：（1）准备英语语料。寻找英语文章，可下载英语新闻，托福、GRE文章，或大学英语课文等。（2）处理语料。对语料进行清理、分句、索引、生成字典。需要进行取词干的操作，分句可以直接根据标点符号处理。（3）根据索引进行查询。支持一个或多个查询，基于对词干的处理，当查go、going等时也能够有返回。由于查询的结果是语句，如果直接按照词与文章的关系建立索引，这样需要从文章中找句子，太多的串匹配操作可能导致查询较慢，所以要设计好索引的粒度。一、问题描述与技术现状分析随着当前形势发展，英语现在随处可见，不管是在书籍还是各种网络上，我们都可以看到英语的踪影，但随之而来面临一个问题，许多英语单词对于初学者很陌生，因此英语单词助手对于他们来说有了莫大的帮助。随着数据结构课程的结束，我们对C语言编程有了更加深入的了解。然而通过课程设计，我们对数据结构知识有了更加深刻的理解，牢固掌握其应用方法，并合理灵活地解决一定实际问题，增强和提高综合分析问题与解决问题的能力。二、系统总体设计运行程序，登陆gtk界面在文章输入框内输入一篇文章，并保存在text.txt内对文章进行分句，并将句子的信息保存下来，以便搜索是调用。将文章进行词干提取，取出的词建立链表，并且每个词与句子建立关系。在单词框内输入一个单词，该单词用来搜素在单词链表中找到单词和其对应的句子。在屏幕上显示例句退出系统三、数据结构和算法详细设计单词信息链数据结构typedefstructnode{charword[20];intlength;structnode*next;structsetences*head_setence;}words;句子信息链数据结构typedefstructsetences{intnum;structsetences*next;}setence;算法设计：在算法方面主要应用倒排索引方法，即在波特算法对词干进行处理后进行分句对句子进行编号，并创建一个单词链表用来存储文章中的不同单词，然后创立一个句子链表，并且单词链表指向句子链表即单词链表中的单词指针指向有该单词的句子，最后搜索单词时只要对单词链表进行搜索然后打出该单词指向的句子链表中的拥有该单词的句子即可。四、C语言程序实现的简要说明程序开发环境：codeblocks12.11版本支持包：gtk+2.0函数原型与功能及调用关系（1）当检索到链表中未有的单词时香链表中添加新单词voidaddword(words**head,char*m)（2）该函数将单词链表与句子链表联系起来voidwordtosetence(setence**head,intnum)（3）该函数判断输入单词时比较单词是否相同intok(char*s,words*head,words**w)（4）该函数把单词转换输出并输出标点符号voidstemfile(structstemmer*z,FILE*f)（5）该函数输出所要搜的单词以及句子voidfindword(char*word,char*str)(6）该函数将链表释放空voidTfree(words**head)五、程序测试及结果分析主界面如下：添加一篇文章：搜索一个单词;查询结果：六、复杂度分析添加文章时，分词分句都是对文章一个字符一个字符进行处理，所以复杂度为o（n）；搜索单词，插入单词时，单词长度越长，所需遍历的层级越长，复杂度为o（n）；七、实验总结本次课程设计从开始布题到结束已有3个多月时间，开始接触到题目时一脸茫然，不过仔细思考后有了新的方向。把题目分为四个工作：界面，分句，取词干和倒排索引，这样之后感觉有条理了，更容易实行。不过道路也不是平坦的，首先关于界面就研究了好久GTK，还是只懂皮毛，寻求同学的帮助，只能勉强弄出界面，之后就是在网上寻找关于分句和去词干方面的资料。最后就是倒排索引，几经曲折，最终还是选取了本算法。完成了本任务也算是不容易了。不过通过课程设计，对数据结构有了更深的理解。八、主要参考文献1]严蔚敏,吴伟民.数据结构（C语言版）.北京:清华大学出版社,1997[2]严蔚敏,吴伟民,米宁.数据结构题集（C语言版）.北京:清华大学出版社,1999[3]URL:[4]URL:[5]URL:[6]URL:维基百科：倒排索引[7]百度文库：GTK教程附录：Mian.c#includestdio.h#includestdlib.h#includegtk/gtk.hvoidmainwork();charstr[100000];GtkWidget*pbox=NULL;voidshow(char*str){GtkWidget*frame;GtkWidget*label=NULL;/*创建一个label构件*/frame=gtk_frame_new(example:);gtk_container_add(GTK_CONTAINER(pbox),frame);gtk_frame_set_label_align(GTK_FRAME(frame),0.0,0.0);gtk_frame_set_shadow_type(GTK_FRAME(frame),GTK_SHADOW_ETCHED_OUT);label=gtk_label_new(str);gtk_container_add(GTK_CONTAINER(frame),label);gtk_label_set_line_wrap(GTK_LABEL(label),TRUE);gtk_box_pack_start(GTK_BOX(pbox),frame,FALSE,FALSE,0);//gtk_frame_set_label(GTK_FRAME(frame),GTKFrameWidget);gtk_widget_show_all(pbox);}staticvoidinformation(GtkWidget*wid,GtkWidget*win){GtkWidget*dialog=NULL;dialog=gtk_message_dialog_new(GTK_WINDOW(win),GTK_DIALOG_MODAL,GTK_MESSAGE_INFO,GTK_BUTTONS_CLOSE,Welcometouse);gtk_window_set_position(GTK_WINDOW(dialog),GTK_WIN_POS_CENTER);gtk_dialog_run(GTK_DIALOG(dialog));gtk_widget_destroy(dialog);}/*staticvoidsearch(GtkWidget*wid,GtkWidget*win){return0;}*/charenter_callback(GtkWidget*widget,GtkWidget*entry){constgchar*entry_text;entry_text=gtk_entry_get_text(GTK_ENTRY(entry));printf(Entrycontents:%s\n,entry_text);findword(entry_text,str);show(str);returnentry_text;}charinput_text(GtkWidget*widget,GtkWidget*entry2){constgchar*article;article=gtk_entry_get_text(GTK_ENTRY(entry2));FILE*out;out=fopen(text.txt,w);fprintf(out,%s,article);fclose(out);mainwork();return;}intmain(intargc,char*argv[]){GtkWidget*button=NULL;GtkWidget*win=NULL;GtkWidget*vbox=NULL;GtkWidget*hbox=NULL;GtkWidget*entry=NULL;GtkWidget*entry2=NULL;GtkWidget*separator;ginttmp_pos;/*InitializeGTK+*/g_log_set_handler(Gtk,G_LOG_LEVEL_WARNING,(GLogFunc)gtk_false,NULL);gtk_init(&argc,&argv);g_log_set_handler(Gtk,G_LOG_LEVEL_WARNING,g_log_default_handler,NULL);/*Createthemainwindow*/win=gtk_window_new(GTK_WINDOW_TOPLEVEL);gtk_container_set_border_width(GTK_CONTAINER(win),200);gtk_window_set_title(GTK_WINDOW(win),Word);gtk_window_set_position(GTK_WINDOW(win),GTK_WIN_POS_CENTER);gtk_widget_realize(win);g_signal_connect(win,destroy,gtk_main_quit,NULL);/*Createaverticalboxwithbuttons*/vbox=gtk_vbox_new(TRUE,6);//创建纵向组装盒gtk_container_add(GTK_CONTAINER(win),vbox);pbox=gtk_vbox_new(TRUE,6);//创建纵向组装盒gtk_container_add(GTK_CONTAINER(vbox),pbox);/**创建一个文本输入框功能：添加文章**/entry2=gtk_entry_new();gtk_entry_set_max_length(GTK_ENTRY(entry),1000000);g_signal_connect(G_OBJECT(entry2),activate,G_CALLBACK(enter_callback),entry2);tmp_pos=GTK_ENTRY(entry2)-text_length;gtk_editable_insert_text(GTK_EDITABLE(entry2),pleaseinputatext,-1,&tmp_pos);gtk_editable_select_region(GTK_EDITAB