课程设计报告-数据结构与算法课程设计(共36页).doc

《课程设计报告-数据结构与算法课程设计(共36页).doc》由会员分享，可在线阅读，更多相关《课程设计报告-数据结构与算法课程设计(共36页).doc（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上set talk on33. 修改本地视图使用的命令是_。一、填空（每空1分，总计30分）C. VFP基类的事件也可以由用户创建【答案】B【答案】6位【答案】C【答案】Dinput请输入第二个数： to bC. 只能根据数据库表建立视图 D. 可以根据数据库表和自由表建立视图重庆大学课程设计报告课程设计题目：数据结构与算法课程设计学院：软件学院 专业：软件工程 年级：2014级 学生：李庆（组长） 唐天 吴东 学号：（李） （唐） (吴)完成时间：2015年12月30日 成绩：指导教师：蔡斌重庆大学教务处制课程设计指导教师评定成绩表项目分值优秀(100x90)良好(9

2、0x80)中等(80x70)及格(70x60)不及格(x0）个城市去推销产品，他从某个城市出发，经历每个城市，且每个城市只能去一次，然后回到初始城市，以距离作为代价，他希望找出一个最佳路径。这N个城市相互都有道路可通，但距离各不相同，城市个数和各个城市的相通距离可由学生自己设定。学生应完成的工作：基本要求（1）可以输入城市个数（不少于10个）、输入城市信息和城市之间的距离（为整数）；（2）按照输入出发城市，根据城市的距离最短给出路径选择。（3）界面要求：有合理的提示和人机交互。目前资料收集情况（含指定参考资料）：1. Robert L. Kruse编. Data Structures and

3、Program Design in C+.高等教育出版社，2001.2.数据结构严蔚敏编，清华大学出版社，2000.3.数据结构教程李春葆编，清华大学出版社，2002.课程设计的工作计划：本课题由吴东同学独立完成。第一期(11.10-11.20)：接受课程任务，完成选题，并对任务初步了解；第二期(11.21-12.10)：收集相关资料和复习基础专业知识，初步完成设计；第三期(12.11-12.20)：对课程设计进行最终实验；第四期(12.21-12.30)：整理并完善课程设计报告。任务下达日期 2015年 11月 10日完成日期 2015年 12月 30日指导教师 （签名）学 生 （签名）说明

4、：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。专心-专注-专业重庆大学本科学生课程设计任务书课程设计题目文学研究助手学院软件学院专业软件学院年级2015已知参数和设计要求：问题描述文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。学生应完成的工作：基本要求英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计

5、。测试数据以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。实现提示设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。目前资料收集情况（含指定参考资料）：1. Robert L. Kruse编. Data Structures and Program Design in C+.高等教育出版社，2001.2.数据结构严蔚敏编，清华大学出版社，2000.3.数据结构教程李春葆编，清华大学出版社，2002.课程设计的工作计划：本课题由李庆同学独立完成，包括绘制程序逻辑图，设计算法，

6、实现算法，撰写论文。任务下达日期 2015年 11月 10日完成日期 2015年 12月 30日指导教师 （签名）学 生 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。摘要本课程设计实验报告共解决3个问题，解决过程中涉及到大部分主流数据结构算法。其中主要有栈，递归算法，串的应用，图，图实现的深度和广度遍历。1) 回文判断将字符串按照用户输入的顺序分别入栈和队列，然后二者进行比较。根据比较结果判断序列是否为回文。2）推销员问题该问题通过A*算法选择出最短路径，通过一个打开的列表，保存了

7、打开节点的一个值记为F；每次从中取最小F值的节点打开下批子节点；一个关闭列表，将已展开的节点加入其中。3）文学助手 该问题主要是利用数据结构中串和栈知识，核心思想是串的模式匹配算法，采用易于理解且设计简单的串的朴素模式匹配算法，利用堆栈存储匹配字符串的位置。关键字：程序设计，数据结构与算法，顺序栈，队列，最短路径,模式匹配，商旅问题，图论关于回文判断 （1）问题描述试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。 （2）基本要求 序列

8、1进栈，然后序列1出栈并与序列2比较。根据序列1与序列2比较结果判断序列是否为回文。 （3）算法思想1.数据结构：typedef struct char itemSTACKSIZE; int top;SqStack;使用结构体，内部定义数组模拟栈。top为栈顶指针，指向当前元素的下一个位置，itemSTACKSIZE表示栈内的元素个数。2.函数介绍：int InitStack(SqStack *S) /栈的初始化int Push(SqStack *s, char data) /入栈int Pop(SqStack *s, char *data) /出栈3.程序流程：1）将字符串按照用户输入的顺序

9、分别入栈和队列2）分别从队列和栈中取出首个字符3）比较取出的字符，若相等，继续分别从队列和栈中取首个字符；否则跳出循环，并设置标志;4）若队列和栈中的字符取完，则结束，设置标志为真;5）标志为真，表示字符从前往后和从后往前的序列完全匹配，该字符串属于回文6）标志为假，表示字符从前往后和从后往前的序列不完全匹配，该字符串不属于回文 （4）模块划分int InitStack(SqStack *S) /栈的初始化int Push(SqStack *s, char data) /入栈int Pop(SqStack *s, char *data) /出栈 （5）数据结构typedef struct ch

10、ar itemSTACKSIZE; int top;typedef struct QNode char data; struct QNode *next;typedef struct PQNode front,rear; （6）源程序#include #include #include #define STACKSIZE 1000typedef struct char itemSTACKSIZE; int top;SqStack;typedef struct QNode char data; struct QNode *next;LQNode, *PQNode;typedef struct P

11、QNode front,rear; LinkQueue;int InitStack(SqStack *S) S-top = -1; return 1;int StackEmpty(SqStack S) if(S.top = -1) return 1; else return 0;int Push(SqStack *s, char data) if(s-top = STACKSIZE - 1) printf(n栈已满，不能再进行入栈操作); return 0; s-top+; s-items-top = data; return 1;int Pop(SqStack *s, char *data)

12、 if (s-top = -1) / printf(n堆栈已空，不能再进行出栈操作); return 0; *data = s-items-top; s-top-; return 1;int InitQueue(LinkQueue *q) q-front = q-rear = (PQNode)malloc(sizeof(LQNode); if(!q-front)printf(n初始化队列失败);return 0; q-front-next = NULL; return 1;int QueueEmpty(LinkQueue q) if (q.front = q.rear) printf(n队列为

13、空); return 1; else return 0;int EnQueue(LinkQueue *q, char item) PQNode p; p = (PQNode)malloc(sizeof(LQNode); if(!p) printf(n内存分配失败); return 0; p-data = item; p-next = NULL; q-rear-next = p; q-rear = p; return 1;int DeQueue(LinkQueue *q, char *item) PQNode p; if(q-front = q-rear) / printf(n队列已空，不能出队

14、); return 0; p = q-front-next; *item = p-data; q-front-next = p-next; free(p); if(q-rear = p) /*若删除的为最后一个结点，移动队尾指针*/ q-front = q-rear; return 1;int PutOutQueue(LinkQueue q) PQNode pos; if(q.front = q.rear) printf(n队列为空); return 0; pos = q.front-next; /* printf(nHere is the string:); while(pos != NUL

15、L) printf(%c, pos-data); pos = pos-next; printf(n);*/ return 1;int main(void) int i,len,count1 = 0; char str1100,ch,ch1; LinkQueue lq1,lq2; SqStack sq; printf(请输入一个字符串:); scanf(%s, &str1); len = strlen(str1); InitQueue(&lq1); InitQueue(&lq2); InitStack(&sq);if(str1len-1=) for(i=0;ilen-1;i+) EnQueue(

16、&lq1,str1i); PutOutQueue(lq1); for(i=0;ilen-1;i+) DeQueue(&lq1,&ch); Push(&sq,ch); EnQueue(&lq1,ch); for(i=0;ilen;i+) Pop(&sq,&ch); EnQueue(&lq2,ch); PutOutQueue(lq2); for(i=0;i0）个城市去推销产品，他从某个城市出发，经历每个城市，且每个城市只能去一次，然后回到初始城市，以距离作为代价，他希望找出一个最佳路径。这N个城市相互都有道路可通，但距离各不相同，城市个数和各个城市的相通距离可由自行设定。 （2）基本要求：（1）可

17、以输入城市个数（不少于10个）、输入城市信息和城市之间的距离（为整数）；（2）按照输入出发城市，根据城市的距离最短给出路径选择。（3）界面要求：有合理的提示和人机交互。 （3）算法思想：在这个问题的具体解决过程中，我们可以使用A*算法。A*算法是N.Nillson于1971年提出的一种有序搜索算法,该算法被认为是求解人工智能问题的最成功的技术理论之一。Nillson指出对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点

18、n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值，并有f*(n)=g*(n)+h*(n)。假设f函数是对f*函数的一种估计,并有f(n)=g(n)+h(n)，其中g函数是对g*的估计，h函数是对h*的一种估计。f( n)包括两个部分，其中g(n)表示到达n节点时，已付出代价的估计；而h(n)表示从n节点到达目标节点ti将要付出代价的估计。按f(n)=g*(n)+h*(n)的值来排序OPEN表的节点，f值小者优先。通常称这种算法为A算法。在A算法的基础上，进一步限制h(n)函数，使得搜索

19、图中的每一个节点n，能满足h(n)=h*(n)、称h函数取h*的下界。这种算法叫A*算法。 （4）模块划分：ttable *table_constructor()构造一个table实体void *table_destructor(ttable * table)析构一个类nodeptr _add_to_open(int i)将节点添加到OPEN表void _add_to_close(nodeptr ptr)将节点添加到CLOSE表nodeptr _remove_from_open(nodeptr ptr)将节点从OPEN表中移除，不删除nodeptr _find_least_f()在OPEN表中

20、找出最小的F节点void _move_to_close(nodeptr ptr)将节点从OPEN移到CLOSEint main()输入节点并运算void _print_path(nodeptr ptr)打印最终路径 （5）数据结构：typedef struct _node int f; /f值int g; /g值int h; /h值int level; /第几次走到这个点(important)int parent; /父城市;int city; /city num; node;使用node结构体表述每一个城市。typedef struct _list struct _list *next;st

21、ruct _list *pre;struct _list *parent; /父城市节点指针node city_node; nodelist, *nodeptr;使用nodelist, *nodeptr描述路径，城市结点与城市结点的关系。typedef struct _ttable struct _ttable *_this; /this 指针nodelist open; /open表,nodelist close; /close表,(仓库)/一些操作nodeptr(*add_to_open) (int);nodeptr(*find_least_f) (void);void(*move_to_

22、close) (nodeptr ptr);void(*print_path) (nodeptr ptr); ttable;Ttable相当一个总表，相当于面向对象的一个类，成员变量有OPEN表和CLOSE表，成员函数有nodeptr(*add_to_open) (int)、nodeptr(*find_least_f) (void)、void(*move_to_close) (nodeptr ptr)、void(*print_path) (nodeptr ptr)。 （6）源程序：#include #include #include #include #define MAX_INT typede

23、f struct _node int f;/f值int g;/g值int h;/h值int level;/第几次走到这个点(important)int parent;/父城市;int city;/city num; node;typedef struct _list struct _list *next;struct _list *pre;struct _list *parent; /父城市节点指针node city_node;nodelist, *nodeptr;nodeptr _add_to_open(int);nodeptr _find_least_f();void _print_pat

24、h(nodeptr ptr);void _move_to_close(nodeptr ptr);nodeptr _remove_from_open(nodeptr ptr);void _add_to_close(nodeptr ptr);typedef struct _ttable struct _ttable *_this;/this 指针nodelist open;/open表,nodelist close;/close表,(仓库)/一些的操作nodeptr(*add_to_open) (int);nodeptr(*find_least_f) (void);void(*move_to_cl

25、ose) (nodeptr ptr);void(*print_path) (nodeptr ptr); ttable;int map100100;int b_path100;/best_path;ttable *table = NULL;ttable *table_constructor()/构造一个table实体table = (ttable *)malloc(sizeof(ttable);memset(table, 0, sizeof(ttable);table-open.next = NULL;table-close.next = NULL;table-open.city_node.pa

26、rent = -1;table-open.city_node.city = -1;table-close.city_node.parent = -1;table-close.city_node.city = -1;table-add_to_open = _add_to_open;table-find_least_f = _find_least_f;table-move_to_close = _move_to_close;table-print_path = _print_path;table-_this = table;return table;void *table_destructor(t

27、table * table)/析构一个类if (table != NULL) nodeptr p = table-_this-open.next;nodeptr q = NULL;while (p) q = p-next;free(p);p = q;p = table-_this-close.next;while (p) q = p-next;free(p);p = q;free(table);table = NULL;nodeptr _add_to_open(int i)/添加到OPEN表/放在第一个位置nodeptr p = NULL;p = (nodeptr)malloc(sizeof(

28、nodelist);memset(p, 0, sizeof(nodelist);if (p = NULL) return p;p-next = NULL;p-parent = NULL;p-city_node.parent = -1;p-city_node.city = i;p-city_node.level = 0;p-city_node.f = 0;p-city_node.g = 0;p-city_node.h = 0;p-next = table-_this-open.next;p-pre = &table-_this-open;if (table-_this-open.next) ta

29、ble-_this-open.next-pre = p;table-_this-open.next = p;return p;void _add_to_close(nodeptr ptr)/添加到close表ptr-next = table-_this-close.next;ptr-pre = &table-_this-close;if (table-_this-close.next) table-_this-close.next-pre = ptr;table-_this-close.next = ptr;nodeptr _remove_from_open(nodeptr ptr)/从OPE

30、N表中移除，不删除ptr-pre-next = ptr-next;if (ptr-next)ptr-next-pre = ptr-pre;return ptr;nodeptr _find_least_f()/在OPEN表中找出最小的F节点int least = MAX_INT;nodeptr p, q = NULL;p = table-_this-open.next;q = p;while (p) if (p-city_node.f city_node.f;p = p-next;return q;void _move_to_close(nodeptr ptr)/从OPEN移到CLOSE_rem

31、ove_from_open(ptr);_add_to_close(ptr);int main()int num, min = MAX_INT;int i, j, k, count;int tmpf, tmph, tmpg;ttable *table = (ttable *)table_constructor(); / 构造nodeptr ptr = NULL, ptr_p = NULL, ptr_c = NULL;nodeptr l_ptr = NULL;/the pointer of last best path;/input citiesdo printf(请输入城市节点个数n,2=n=

32、99 | num = 1);printf(请输入各节点之间的距离矩阵n以第一个节点为出发城市：n);for (i = 0; i num; i+) for (j = 0; j mapij) min = mapij;/最后回到Amapnumnum = map00;for (i = 0; i add_to_open(0);while (1) ptr_p = table-find_least_f();/当前最好节点,从最好节点回退肯定是最好路径table-move_to_close(ptr_p);/move to close table and save it;if (l_ptr & l_ptr != ptr_p) /更新最好路径while (l_ptr != NULL) b_pathl_ptr-city_node.city = 0;l_ptr = l_ptr-parent;l_ptr = ptr_p;while (l_ptr != NULL) b_pathl_ptr-city_node.city = 1;l_ptr = l_ptr-parent;l_ptr = ptr_p;for (i = 0, count = 0; i = num; i