数据结构课设报告

1、课 程 设 计 报 告题目：英语单词学习助手课程名称： 数据结构 专业班级： 计算机科学与技术1208班 学 号： U 姓 名： 江振武 指导教师： 祝建华 报告日期： 2014年10月29日 计算机科学与技术学院 任务书p 设计目的：掌握线性表、串、查找表等数据结构的物理存储结构与基本算法，通过解决较复杂的实际问题，提高学生对数据结构知识综合运用的技能与实践能力。设计内容：以大学英语相关英语文章为语料素材，设计有效的数据结构及其存储结构表示英语单词表，并建立相应的倒排索引，帮助英语学习者在遇到生词时能方便找到生词的相应例句，熟悉其应用语境与地道的用法；设计有效的算法对语料进行清理与分句处理，

2、实现基于索引的快速例句搜索程序。p 设计要求：（1）输入某一个（或若干个）英语单词，要求返回相应的英语例句。（2）根据单词与语句建立倒排索引，并且索引要求物化到外存，以文件形式保存，每次启动程序时不必重新建立索引，只需将索引文件导入内存。（3）采用图形界面，便于输入单词，例句展现直观，界面布局合理。设计提示：按三步进行：（1）准备英语语料。寻找英语文章，可下载英语新闻，托福、GRE文章，或大学英语课文等。（2）处理语料。对语料进行清理、分句、索引、生成字典。需要进行取词干的操作，分句可以直接根据标点符号处理。（3）根据索引进行查询。支持一个或多个查询，基于对词干的处理，当查go、going等时

3、也能够有返回。由于查询的结果是语句，如果直接按照词与文章的关系建立索引，这样需要从文章中找句子，太多的串匹配操作可能导致查询较慢，所以要设计好索引的粒度。1、 问题描述与技术现状分析随着当前形势发展，英语现在随处可见，不管是在书籍还是各种网络上，我们都可以看到英语的踪影，但随之而来面临一个问题，许多英语单词对于初学者很陌生，因此英语单词助手对于他们来说有了莫大的帮助。随着数据结构课程的结束，我们对C语言编程有了更加深入的了解。然而通过课程设计，我们对数据结构知识有了更加深刻的理解，牢固掌握其应用方法，并合理灵活地解决一定实际问题，增强和提高综合分析问题与解决问题的能力。2、 系统总体设计 运行

4、程序，登陆gtk界面 在文章输入框内输入一篇文章， 并保存在text.txt内 对文章进行分句，并将句子的信息 保存下来，以便搜索是调用。 将文章进行词干提取，取出的 词建立链表，并且每个词与句 子建立关系。 在单词框内输入一个单词， 该单词用来搜素 在单词链表中找到单词和其对应的句 子。 在屏幕上显示例句 退出系统3、 数据结构和算法详细设计单词信息链数据结构typedef struct node char word20; int length; struct node *next; struct setences *head_setence;words;句子信息链数据结构typedef s

5、truct setences int num; struct setences *next;setence;算法设计：在算法方面主要应用倒排索引方法，即在波特算法对词干进行处理后进行分句对句子进行编号，并创建一个单词链表用来存储文章中的不同单词，然后创立一个句子链表，并且单词链表指向句子链表即单词链表中的单词指针指向有该单词的句子，最后搜索单词时只要对单词链表进行搜索然后打出该单词指向的句子链表中的拥有该单词的句子即可。4、 C语言程序实现的简要说明程序开发环境：codeblocks 12.11版本支持包：gtk+2.0函数原型与功能及调用关系（1）当检索到链表中未有的单词时香链表中添加新单词

6、 void addword(words *head,char *m)（2）该函数将单词链表与句子链表联系起来 void wordtosetence(setence *head,int num)（3）该函数判断输入单词时比较单词是否相同 int ok(char *s,words *head,words *w)（4）该函数把单词转换输出并输出标点符号 void stemfile(struct stemmer * z, FILE * f)（5）该函数输出所要搜的单词以及句子 void findword(char *word,char *str) (6）该函数将链表释放空 void Tfree(wor

7、ds *head)5、 程序测试及结果分析主界面如下：添加一篇文章：搜索一个单词;查询结果：6、 复杂度分析添加文章时，分词分句都是对文章一个字符一个字符进行处理， 所以复杂度为o（n）；搜索单词， 插入单词时， 单词长度越长， 所需遍历的层级越长， 复杂度为o（n）；7、 实验总结 本次课程设计从开始布题到结束已有3个多月时间，开始接触到题目时一脸茫然，不过仔细思考后有了新的方向。把题目分为四个工作：界面，分句，取词干和倒排索引，这样之后感觉有条理了，更容易实行。不过道路也不是平坦的，首先关于界面就研究了好久GTK，还是只懂皮毛，寻求同学的帮助，只能勉强弄出界面，之后就是在网上寻找关于分句和

8、去词干方面的资料。最后就是倒排索引，几经曲折，最终还是选取了本算法。完成了本任务也算是不容易了。不过通过课程设计，对数据结构有了更深的理解。 八、主要参考文献1 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社,19972 严蔚敏, 吴伟民, 米宁. 数据结构题集（C语言版）. 北京: 清华大学出版社,19993 URL: p.lancs.ac.uk/computing/research/stemming/index.htm4 URL: /wiki/stemming5 URL: http:/www.juku

9、/index.php 6 URL: /wiki 维基百科：倒排索引 7 / 百度文库：GTK教程附录：Mian.c#include #include #include void mainwork();char str;GtkWidget *pbox=NULL;void show(char* str) GtkWidget *frame; GtkWidget *label=NULL; /*创建一个label构件*/ frame = gtk_frame_new (example:); gtk_contai

10、ner_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

11、_pack_start (GTK_BOX (pbox), frame, FALSE, FALSE, 0); /gtk_frame_set_label (GTK_FRAME (frame), GTK Frame Widget); gtk_widget_show_all(pbox);static void information (GtkWidget *wid, GtkWidget *win) GtkWidget *dialog = NULL; dialog = gtk_message_dialog_new (GTK_WINDOW (win), GTK_DIALOG_MODAL, GTK_MESS

12、AGE_INFO, GTK_BUTTONS_CLOSE, Welcome to use); gtk_window_set_position (GTK_WINDOW (dialog), GTK_WIN_POS_CENTER); gtk_dialog_run (GTK_DIALOG (dialog); gtk_widget_destroy (dialog);/*static void search(GtkWidget *wid, GtkWidget *win) return 0;*/char enter_callback( GtkWidget *widget, GtkWidget *entry )

13、 const gchar *entry_text; entry_text = gtk_entry_get_text (GTK_ENTRY (entry); printf(Entry contents: %sn, entry_text); findword(entry_text,str); show(str); return entry_text;char input_text( GtkWidget *widget, GtkWidget *entry2) const gchar *article; article = gtk_entry_get_text (GTK_ENTRY (entry2);

14、 FILE *out; out=fopen(text.txt,w); fprintf(out,%s,article); fclose(out); mainwork(); return;int main (int argc, char *argv) GtkWidget *button = NULL; GtkWidget *win = NULL; GtkWidget *vbox = NULL; GtkWidget *hbox = NULL; GtkWidget *entry=NULL; GtkWidget *entry2=NULL; GtkWidget *separator; gint tmp_p

15、os;/* Initialize GTK+*/ 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);/*Create the main window */ win = gtk_window_new (GTK_WINDOW_TOPLEVEL); gtk_container_set_border_width

16、(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);/*Create a vertical box with buttons*/ vbox = gtk_vbox_new (TRUE, 6); /创建纵向组装盒 gtk

17、_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), ); g_signal_connect (G_OBJECT (entry2), activate, G_CALLBACK (enter_callback),

18、entry2); tmp_pos = GTK_ENTRY (entry2)-text_length; gtk_editable_insert_text (GTK_EDITABLE (entry2), please input a text, -1, &tmp_pos); gtk_editable_select_region (GTK_EDITABLE (entry2),0, GTK_ENTRY (entry2)-text_length); gtk_box_pack_start (GTK_BOX (vbox), entry2, TRUE, TRUE, 0); gtk_widget_show (e

19、ntry2); button = gtk_button_new_with_label(input); g_signal_connect (G_OBJECT (button), clicked, G_CALLBACK (input_text), entry2); gtk_box_pack_start (GTK_BOX (vbox), button, TRUE, TRUE, 0); button = gtk_button_new_from_stock (GTK_STOCK_DIALOG_INFO); g_signal_connect (G_OBJECT (button), clicked, G_C

20、ALLBACK (information), (gpointer) win); gtk_box_pack_start (GTK_BOX (vbox), button, TRUE, TRUE, 0); button = gtk_button_new_from_stock (GTK_STOCK_CLOSE); g_signal_connect (button, clicked, gtk_main_quit, NULL); gtk_box_pack_start (GTK_BOX (vbox), button, TRUE, TRUE, 0); hbox = gtk_hbox_new(TRUE, 6);

21、 /创建横向组装盒 gtk_container_add (GTK_CONTAINER (vbox), hbox); separator = gtk_hseparator_new (); /分割线 gtk_box_pack_start (GTK_BOX (vbox), separator, FALSE, TRUE, 5); gtk_widget_show (separator); /*创建一个文本输入构件*/ entry=gtk_entry_new(); gtk_entry_set_max_length (GTK_ENTRY (entry), 100); g_signal_connect (G_

22、OBJECT (entry), activate, G_CALLBACK (enter_callback), entry); tmp_pos = GTK_ENTRY (entry)-text_length; gtk_editable_insert_text (GTK_EDITABLE (entry), please input a word, -1, &tmp_pos); gtk_editable_select_region (GTK_EDITABLE (entry),0, GTK_ENTRY (entry)-text_length); gtk_box_pack_start(GTK_BOX (

23、hbox), entry, TRUE, TRUE, 0); gtk_widget_show (entry); button = gtk_button_new_with_label(search); g_signal_connect (G_OBJECT (button), clicked, G_CALLBACK (enter_callback), entry); gtk_box_pack_start (GTK_BOX (hbox), button, TRUE, TRUE, 0); GtkWidget *gtk_label_new_with_mnemonic(const char *str); /

24、* Enter the main loop */ gtk_widget_show_all (win);/显示窗口 gtk_main (); return 0;Find.c#include #include #include #include stem.hwords *head=NULL;char all10001501;void Tfree(words *head) words *i,*j; setence *k,*w; for (i=*head;i;) j=i; for (k=i-head_setence;k;) w=k; k=k-next; free(w); i=i-next; free(

25、j); *head=NULL;void mainwork() FILE *in=fopen(text.txt,r); if (s!=NULL) free(s); if (head!=NULL) Tfree(&head); s=(char *)malloc(i_max+1); struct stemmer *z=create_stemmer(); stemfile(z,in); free_stemmer(z);Stem.h#include #include #include #define LETTER(ch) (isupper(ch) | islower(ch)#define TRUE 1#d

26、efine FALSE 0#define INC 50static int i_max = INC;char *s;char *t;struct stemmer;extern struct stemmer * create_stemmer(void);extern void free_stemmer(struct stemmer * z);extern int stem(struct stemmer * z, char * b, int k);struct stemmer char * b; int k; int j;extern struct stemmer * create_stemmer

27、(void) return (struct stemmer *) malloc(sizeof(struct stemmer);extern void free_stemmer(struct stemmer * z) free(z);static int cons(struct stemmer * z, int i) switch (z-bi) case a: case e: case i: case o: case u: return FALSE; case y: return (i = 0) ? TRUE : !cons(z, i - 1); default: return TRUE; st

28、atic int m(struct stemmer * z) int n = 0; int i = 0; int j = z-j; while(TRUE) if (i j) return n; if (! cons(z, i) break; i+; i+; while(TRUE) while(TRUE) if (i j) return n; if (cons(z, i) break; i+; i+; n+; while(TRUE) if (i j) return n; if (! cons(z, i) break; i+; i+; static int vowelinstem(struct s

29、temmer * z) int j = z-j; int i; for (i = 0; i b; if (j 1) return FALSE; if (bj != bj - 1) return FALSE; return cons(z, j);static int cvc(struct stemmer * z, int i) if (i bi; if (ch = w | ch = x | ch = y) return FALSE; return TRUE;static int ends(struct stemmer * z, char * s) int length = s0; char *

30、b = z-b; int k = z-k; if (slength != bk) return FALSE; if (length k + 1) return FALSE; if (memcmp(b + k - length + 1, s + 1, length) != 0) return FALSE; z-j = k-length; return TRUE;static void setto(struct stemmer * z, char * s) int length = s0; int j = z-j; memmove(z-b + j + 1, s + 1, length); z-k

31、= j+length;static void r(struct stemmer * z, char * s) if (m(z) 0) setto(z, s); static void step1ab(struct stemmer * z) char * b = z-b; if (bz-k = s) if (ends(z, 04 sses) z-k -= 2; else if (ends(z, 03 ies) setto(z, 01 i); else if (bz-k - 1 != s) z-k-; if (ends(z, 03 eed) if (m(z) 0) z-k-; else if (e

32、nds(z, 02 ed) | ends(z, 03 ing) & vowelinstem(z) z-k = z-j; if (ends(z, 02 at) setto(z, 03 ate); else if (ends(z, 02 bl) setto(z, 03 ble); else if (ends(z, 02 iz) setto(z, 03 ize); else if (doublec(z, z-k) z-k-; int ch = bz-k; if (ch = l | ch = s | ch = z) z-k+; else if (m(z) = 1 & cvc(z, z-k) setto

33、(z, 01 e); static void step1c(struct stemmer * z) if (ends(z, 01 y) & vowelinstem(z) z-bz-k = i;static void step2(struct stemmer * z) switch (z-bz-k-1) case a: if (ends(z, 07 ational) r(z, 03 ate); break; if (ends(z, 06 tional) r(z, 04 tion); break; break; case c: if (ends(z, 04 enci) r(z, 04 ence);

34、 break; if (ends(z, 04 anci) r(z, 04 ance); break; break; case e: if (ends(z, 04 izer) r(z, 03 ize); break; break; case l: if (ends(z, 03 bli) r(z, 03 ble); break; if (ends(z, 04 alli) r(z, 02 al); break; if (ends(z, 05 entli) r(z, 03 ent); break; if (ends(z, 03 eli) r(z, 01 e); break; if (ends(z, 0

35、5 ousli) r(z, 03 ous); break; break; case o: if (ends(z, 07 ization) r(z, 03 ize); break; if (ends(z, 05 ation) r(z, 03 ate); break; if (ends(z, 04 ator) r(z, 03 ate); break; break; case s: if (ends(z, 05 alism) r(z, 02 al); break; if (ends(z, 07 iveness) r(z, 03 ive); break; if (ends(z, 07 fulness)

36、 r(z, 03 ful); break; if (ends(z, 07 ousness) r(z, 03 ous); break; break; case t: if (ends(z, 05 aliti) r(z, 02 al); break; if (ends(z, 05 iviti) r(z, 03 ive); break; if (ends(z, 06 biliti) r(z, 03 ble); break; break; case g: if (ends(z, 04 logi) r(z, 03 log); break; static void step3(struct stemmer

37、 * z) switch (z-bz-k) case e: if (ends(z, 05 icate) r(z, 02 ic); break; if (ends(z, 05 ative) r(z, 00 ); break; if (ends(z, 05 alize) r(z, 02 al); break; break; case i: if (ends(z, 05 iciti) r(z, 02 ic); break; break; case l: if (ends(z, 04 ical) r(z, 02 ic); break; if (ends(z, 03 ful) r(z, 00 ); br

38、eak; break; case s: if (ends(z, 04 ness) r(z, 00 ); break; break; static void step4(struct stemmer * z) switch (z-bz-k-1) case a: if (ends(z, 02 al) break; return; case c: if (ends(z, 04 ance) break; if (ends(z, 04 ence) break; return; case e: if (ends(z, 02 er) break; return; case i: if (ends(z, 02

39、 ic) break; return; case l: if (ends(z, 04 able) break; if (ends(z, 04 ible) break; return; case n: if (ends(z, 03 ant) break; if (ends(z, 05 ement) break; if (ends(z, 04 ment) break; if (ends(z, 03 ent) break; return; case o: if (ends(z, 03 ion) & (z-bz-j = s | z-bz-j = t) break; if (ends(z, 02 ou)

40、 break; return; case s: if (ends(z, 03 ism) break; return; case t: if (ends(z, 03 ate) break; if (ends(z, 03 iti) break; return; case u: if (ends(z, 03 ous) break; return; case v: if (ends(z, 03 ive) break; return; case z: if (ends(z, 03 ize) break; return; default: return; if (m(z) 1) z-k = z-j;sta

41、tic void step5(struct stemmer * z) char * b = z-b; z-j = z-k; if (bz-k = e) int a = m(z); if (a 1 | (a = 1 & !cvc(z, z-k - 1) z-k-; if (bz-k = l & doublec(z, z-k) & m(z) 1) z-k-;extern int stem(struct stemmer * z, char * b, int k) if (k b = b; z-k = k; step1ab(z); step1c(z); step2(z); step3(z); step

42、4(z); step5(z); return z-k;typedef struct setences int num; struct setences *next;setence;typedef struct node char word20; int length; struct node *next; struct setences *head_setence;words;extern words *head;void addword(words *head,char *m);extern char all10001501;void wordtoseten(setence *head,int num);v