最新课程设计报告-数据结构与算法课程设计(共35页)

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

2、评定成绩表项目分值优秀(100>x90)良好(90>x80)中等(80>x70)及格(70>x60)不及格(x<60)评分参考标准参考标准参考标准参考标准参考标准学习态度15学习态度认真，科学作风严谨，严格保证设计时间并按任务书中规定的进度开展各项工作学习态度比较认真，科学作风良好，能按期圆满完成任务书规定的任务学习态度尚好，遵守组织纪律，基本保证设计时间，按期完成各项工作学习态度尚可，能遵守组织纪律，能按期完成任务学习马虎，纪律涣散，工作作风不严谨,不能保证设计时间和进度技术水平与实际能力25设计合理、理论分析与计算正确，实验数据准确，有很强的实际动手能力、经济

3、分析能力和计算机应用能力，文献查阅能力强、引用合理、调查调研非常合理、可信设计合理、理论分析与计算正确，实验数据比较准确，有较强的实际动手能力、经济分析能力和计算机应用能力，文献引用、调查调研比较合理、可信设计合理，理论分析与计算基本正确，实验数据比较准确，有一定的实际动手能力，主要文献引用、调查调研比较可信设计基本合理，理论分析与计算无大错，实验数据无大错设计不合理，理论分析与计算有原则错误，实验数据不可靠，实际动手能力差，文献引用、调查调研有较大的问题创新10有重大改进或独特见解，有一定实用价值有较大改进或新颖的见解，实用性尚可有一定改进或新的见解有一定见解观念陈旧论文(计算书、图纸)撰写

4、质量50结构严谨，逻辑性强，层次清晰，语言准确，文字流畅，完全符合规范化要求，书写工整或用计算机打印成文；图纸非常工整、清晰结构合理，符合逻辑，文章层次分明，语言准确，文字流畅，符合规范化要求，书写工整或用计算机打印成文；图纸工整、清晰结构合理，层次较为分明，文理通顺，基本达到规范化要求，书写比较工整；图纸比较工整、清晰结构基本合理，逻辑基本清楚，文字尚通顺，勉强达到规范化要求；图纸比较工整内容空泛，结构混乱，文字表达不清，错别字较多，达不到规范化要求；图纸不工整或不清晰指导教师评定成绩：指导教师签名： 年 月 日重庆大学本科学生课程设计任务书课程设计题目回文判断学院软件学院专业软件工程年级2

5、014已知参数和设计要求：问题描述试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。学生应完成的工作：实现提示首先，序列1进栈，然后序列1出栈并与序列2比较。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列2均为空串。目前资料收集情况（含指定参考资料）：1. Robert L. Kruse编. Data Structures and Program Design in C+.

6、高等教育出版社，2001.2.数据结构严蔚敏编，清华大学出版社，2000.3.数据结构教程李春葆编，清华大学出版社，2002.课程设计的工作计划：本课题由唐天同学独立完成，第一天由其编写全部代码第二天小组测试，讨论，修改。最终完成此任务任务下达日期 2015年 11月 10日完成日期 2015年 12月 30日指导教师 （签名）学 生 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。重庆大学本科学生课程设计任务书课程设计题目推销员问题学院软件学院专业软件工程年级2014已知参数和设计要

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

8、 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日指导教师 （签名）学 生 （签名）说明：1、学院、专

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

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

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

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

13、列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）将字符串按照用户输入的顺

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

15、r *data) /出栈 （5）数据结构typedef struct char itemSTACKSIZE; int top;typedef struct QNode char data; struct QNode *next;typedef struct PQNode front,rear; （6）源程序#include <stdio.h>#include <stdlib.h>#include <string.h>#define STACKSIZE 1000typedef struct char itemSTACKSIZE; int top;SqStack

16、;typedef struct QNode char data; struct QNode *next;LQNode, *PQNode;typedef struct PQNode 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(&qu

17、ot;n栈已满，不能再进行入栈操作"); return 0; s->top+; s->items->top = data; return 1;int Pop(SqStack *s, char *data) 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)m

18、alloc(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队列为空"); return 1; else return 0;int EnQueue(LinkQueue *q, char item) PQNode p; p = (PQNode)malloc(sizeof(LQNode); if

19、(!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队列已空，不能出队"); return 0; p = q->front->next; *item = p->data; q

20、->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 !=

21、 NULL) 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); InitQu

22、eue(&lq2); InitStack(&sq);if(str1len-1='') for(i=0;i<len-1;i+) EnQueue(&lq1,str1i); PutOutQueue(lq1); for(i=0;i<len-1;i+) DeQueue(&lq1,&ch); Push(&sq,ch); EnQueue(&lq1,ch); for(i=0;i<len;i+) Pop(&sq,&ch); EnQueue(&lq2,ch); PutOutQueue(lq2); fo

23、r(i=0;i<len;i+) DeQueue(&lq1,&ch); DeQueue(&lq2,&ch1);if(ch1 != ch) count1+; elseprintf("请以结尾。");return 0; if(count1 = 0) printf("n该字符串为回文"); else printf("n该字符串不是回文"); return 0; （7）测试数据测试4组数据： 1. 123456789&987654321 2. 12+3&3-12 3. 213123&

24、23 4. abc&cba （8）测试情况该数据表示一般情况，以结尾的一般字符串该数据表示含有符号的以结尾的字符串该数据表示不以结尾的字符串该数据表示含英文字母的字符串关于推销员问题 （1）问题描述有一个推销员要到N（N>0）个城市去推销产品，他从某个城市出发，经历每个城市，且每个城市只能去一次，然后回到初始城市，以距离作为代价，他希望找出一个最佳路径。这N个城市相互都有道路可通，但距离各不相同，城市个数和各个城市的相通距离可由自行设定。 （2）基本要求：（1）可以输入城市个数（不少于10个）、输入城市信息和城市之间的距离（为整数）；（2）按照输入出发城市，根据城市的距离最短给出

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

26、达目标节点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)函数，使得搜索图中的每一个节点n，能满足h(n)<=h*(n)、称h函数取h*

27、的下界。这种算法叫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表中找出最小的F节点void _move_to_close(nod

28、eptr 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;struct _list *pre;struct _list *p

29、arent; /父城市节点指针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_close) (nodeptr ptr);void(*prin

30、t_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 <stdio.h>#include <malloc.h>#include <stdlib.h>#include <me

31、mory.h>#define MAX_INT 99999999typedef 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)

32、;nodeptr _find_least_f();void _print_path(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);nodept

33、r(*find_least_f) (void);void(*move_to_close) (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;tab

34、le->close.next = NULL;table->open.city_node.parent = -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->pr

35、int_path = _print_path;table->_this = table;return table;void *table_destructor(ttable * 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(

36、table);table = NULL;nodeptr _add_to_open(int i)/添加到OPEN表/放在第一个位置nodeptr p = NULL;p = (nodeptr)malloc(sizeof(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_n

37、ode.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) table->_this->open.next->pre = p;table->_this->open.next = p;return p;void _add_to_close(nodeptr ptr)/添加到close表

38、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)/从OPEN表中移除，不删除ptr->pre->next = ptr->next;if

39、(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 < least) q = p;least = p->city_node.f;p = p->next;return q;void _move_to_close(n

40、odeptr ptr)/从OPEN移到CLOSE_remove_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 citi

41、esdo printf("请输入城市节点个数n,2<=n<99：n");scanf_s("%d", &num); while (num >= 99 | num <= 1);printf("请输入各节点之间的距离矩阵n以第一个节点为出发城市：n");for (i = 0; i < num; i+) for (j = 0; j < num; j+) scanf_s("%d", &mapij);if (i != j && min > mapij)

42、min = mapij;/最后回到Amapnumnum = map00;for (i = 0; i < num; i+) mapnumi = map0i;mapinum = mapi0;table->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) /更新

43、最好路径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+) if (b_pathi)count+;if (count = num + 1) /all city in best path,A

44、 in twice:First And Last.break;if (count = num) /left one,which ? Last A.Because we have never changed the value of b_pathnum.ptr_c = table->add_to_open(num); /把它添加进开启列表中 ptr_c->city_node.parent = ptr_p->city_node.city;/把当前作为这的父节点ptr_c->city_node.level = ptr_p->city_node.level + 1;/他是

45、父节点的下一层。ptr_c->parent = ptr_p;ptr_c->city_node.g = ptr_p->city_node.g + mapnumptr_p->city_node.city;/gptr_c->city_node.h = min * (num - ptr_c->city_node.level);/hptr_c->city_node.f = ptr_c->city_node.g + ptr_c->city_node.h;/felse for (i = 0; i < num; i+) /对邻近的路径计算if (i

46、!= ptr_p->city_node.city&& mapij != -1) if (!b_pathi) /如果它不在'最短路径'中 ptr_c = table->add_to_open(i); /把它添加进开启列表中ptr_c->city_node.parent = ptr_p->city_node.city;/把当前作为这的父节点ptr_c->city_node.level = ptr_p->city_node.level + 1;/他是父节点的下一层。ptr_c->parent = ptr_p;ptr_c->

47、;city_node.g = ptr_p->city_node.g + mapiptr_p->city_node.city; /gptr_c->city_node.h = min * (num - ptr_c->city_node.level);/hptr_c->city_node.f = ptr_c->city_node.g + ptr_c->city_node.h;/ftable->print_path(l_ptr);table_destructor(table);return 0;void _print_path(nodeptr ptr)/

48、打印路径int least;if (ptr = NULL)return;least = ptr->city_node.f;printf("The best path is :");printf("A ");ptr = ptr->parent;while (ptr) printf("%c ", ptr->city_node.city + 65);ptr = ptr->parent;printf("nThe shortest length is %dn", least); （7）测试数据： 测试

49、数据为十个城市两两之间的距离矩阵，其中设定A为初始城市：ABCDEFGHIJA0260330610770900580650770920B26005206206006906209209801160C330520043010901210880640860930D6106204300122013001180108013001370E770600109012100190500122011501400F900690121013001900700140013401590G58062088011805007000770650900H6509206401080122014007700290290I770980

50、8601300115013406502900260J92011609301370140015909002902600 （8）测试情况：1输入城市个数：2输入各城市距离矩阵：3运行结果：最佳路径为：A B F E G I J H C D A最短距离为：4520 km关于文学助手（1） 问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。 （2）基本要求：1、英文小说存放在一个文本文件中；2、待统计的额词汇集合要一次输入完毕，即统计工作必须在程序的一次运行后全部完成；3、程序的输出结果是每个词的出现次数和出现位置所在的行号；（3）算法思想：利用数据结构中串和栈知识，结合功能强大的C+语言实现文学研究助手的设计，该应用软件设计的核心思想是串的模式匹配算法，采用易于理解且设计简单的串的朴素模式匹配算法，利用堆栈存储匹配字符串的位置。开始程序逻辑图：输入文章到文件中把文件中的文章传到数组中输入单词m1m2。mnk=1k+mk和数组进行kmp匹配k<=n? Y结束 Nmain()算法流程图：HELPER()PRINT_R()Init_word (