《数据结构课程设计报告(00002)》由会员分享，可在线阅读，更多相关《数据结构课程设计报告(00002)（12页珍藏版）》请在金锄头文库上搜索。
1、计算机高级语言程序设计课程设计指导书数据结构程序设计课程设计报告 学 号： 班级序号： 姓名： 指导老师： 成绩： 中国地质大学（武汉）信息工程学院遥感系2016年12月实习题目一（）【题目及其需求】（，具体内容：题号及题目、问题描述、问题分析。）1.设计综合测评工具，用户输入学生课程及成绩信息，自定义综合测评公式，程序输出测评排序结果；2.用户输入信息：学生信息表,课程信息表,课程成绩单 学生信息表：学号,班级,姓名 课程信息表：名称，学分，编码 课程成绩单：学好，成绩（每门课一份）;3. 程序输出信息：测评结果（学号，姓名，综合测评排名）;4. 自选顺序表或链表完成实习内容;5. 采用动态
2、方式分配内存空间;6. 设计合理的类结构：除包含基本的学生信息外，还应考虑课程及分数，并预留出后续综合测评排序结果的位置;7. 自定义多个输入数据的先后顺序:不同先后顺序可能对算法的复杂度有影响。【实现方法及其过程】（1）思想：（，具体内容：主要的算法思想。）通过string类读取记事本中的学生信息，运用链表来存储信息template struct LinkNode /链表节点类T data; /节点的数据域 string SNumber;string Class;string Name;float *Mark;float TMark;class List /链表类，直接使用链表节点类的数据和
3、操作public:List() first = new LinkNode; List(const T& x) first = new LinkNode(x); List(List& L);List() makeEmpty();delete first;void makeEmpty() LinkNode *q;while (first-link) q = first-link;first-link = q-link;delete q;LinkNode *getHead()const return first; /获得头节点void SortAndOutput(); /排序并输出操作void in
4、put(); /输入void output(); /输出protected:LinkNode *first;string temp, SNumber, Class, Name, *SubNumber/*各科的编号*/, *Sub/*各科的名字*/, SubNumber1, Sub1, SMark1;int StuNum, SubNum;float *SMark;/*各科的学分*/;（2）实现过程：（，具体内容：子模块（过程或函数）的规格说明、关系图（描述类与类之间的关系图、各功能模块之间的关系图等）。） 学生文件学生信息 学生信息 成绩信息综合测评系统综合测评成绩【遇到的问题及其解决后的感想】
5、（，具体内容：问题是如何解决的，改进设想。） 在读取文本信息的操作中，遇到了一些麻烦，通过上网明白了读入的操作算法；运用单链表时，发现查找、搜索和排序学生信息和成绩的操作不是很了解；循环查找某节点的程序不是很懂，通过这次实习作业，让我对链表的操作有了更深刻的了解。【附录】（，具体内容：源程序清单（必须有必要的注释）、测试数据及运行结果。）实习题目二【题目及其需求】（，具体内容：题号及题目、问题描述、问题分析。）1. 在实习一综合测评工具的基础上，允许用户输入综合测评公式;2. 用户输入信息：除实习一的输入外，新增综合测评公式; 测评公式：课程编码，加权系数，运算3.程序输出信息：综合测评公式，
6、测评结果（学号，姓名，综合测评排名）;4.使用栈实现综合测评公式的中缀转后缀;5.使用栈实现中缀表达式的计算;6.选择合适的数据类型存储课程编码。【实现方法及其过程】（1）思想：（，具体内容：主要的算法思想。）计算机处理后缀表达式求值问题是比较方便的，即将遇到的操作数暂存于一个操作数栈中，凡是遇到操作数，便从栈中pop出两个操作数，并将结果存于操作数栈中，直到对后缀表达式中最后一个操作数处理完，最后压入栈中的数就是后最表达式的计算结果。中缀表达式不方便与计算机处理，通常要讲中缀表达式转换为一个与之等价的后缀表达式。等价是指两个表达式的计算顺序和计算结果完全相同。（2）实现过程：（，具体内容：子
7、模块（过程或函数）的规格说明、关系图（描述类与类之间的关系图、各功能模块之间的关系图等）。）将中缀表达式转换为等价的后缀表达式的过程要使用一个栈放“（”，具体可以按照下面的方式进行。（1） 从左到右一次扫描中缀表达式的每一个字符，如果是数字字符和圆点“.”则直接将它们写入后缀表达式中。（2） 如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。（3）如果遇到的是操作符
8、，则将该操作符和操作符栈顶元素比较： 1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入 后缀表式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级。 2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。 （4）重复上述步骤直到遇到中缀表达式的结束符标记“#”，弹出栈中的所有元素并放入后缀表达式中，转换结束。【遇到的问题及其解决后的感想】（，具体内容：问题是如何解决的，改进设想。） 在写程序的过程中，中缀转后缀时的算法有一定难度。【附录】（，具体内容：源程序清单（必须有必要的注释）、测试数据及运行结果。）class LinkNode
9、public:LinkNode()LinkNode(int x)add = x;string number;/学号或编码string name;/姓名或名称float score1;float score2;float score3;float add;/综测分或链表长度-1LinkNode*link;/指针域int Class;/班级float rank;/排名或学分;class reviewpublic:review();review();void score();/成绩单void course();/课程信息表void student();/学生信息表int found(int k);/
10、创建新的节点void calculate();/计算综测分int sort();/排序void output(ostream&out)const;/输出void look();float calcu();float show(char,LinkNode*);private:LinkNode*first;LinkNode*last;LinkNode*Course;stack Linkstack;doustack doustack;review:review()int length = 0;first = new LinkNode(length);first-link = NULL;last =
11、first;last-link = first-link;Course = new LinkNode(length);Course-link = NULL;review:review()LinkNode*next;while (first)next = first-link;delete first;first = next;实习题目三【题目及其需求】（，具体内容：题号及题目、问题描述、问题分析。） 1.将实习二的程序输出信息以密码形式输出;2.用户输入信息：综合测评结果.txt;3.程序输出信息：密码形式综合测评结果、密码本;(说明：文字和数字可以单独处理)4.统计综合测评结果文件中不同文字
12、出现的频率;5.使用哈夫曼树建立编码结构6.生成编码信息；7.输出编码信息。【实现方法及其过程】（1）思想：（，具体内容：主要的算法思想。）哈夫曼树的建立由哈夫曼最早给出的建立最优二叉树的带有一般规律的算法，俗称哈夫曼算法。描述如下： 1):初始化：根据给定的n个权值(1,2,，n)，构造n棵二叉树的森林集合F=1,2,n，其中每棵二叉树i只有一个权值为i的根节点，左右子树均为空。2) :找最小树并构造新树：在森林集合F中选取两棵根的权值最小的树做为左右子树构造一棵新的二叉树，新的二叉树的根结点为新增加的结点，其权值为左右子树的权值之和。3) :删除与插入：在森林集合F中删除已选取的两棵根的权值最小的树，同时将新构造的二叉树加入到森林集合F中。4) :重复2)和3)步骤，直至森林集合F中只含一棵树为止，这颗树便是哈夫曼树，即最优二叉树。由于2)和3)步骤每重复一次，删除掉两棵树，增加一棵树，所以2)和3)步骤重复n-1次即可获得哈夫曼树。（2）实现过程：（，具体内容：子模块（过程或函数）的规格说明、关系图（描述类与类之间的关系图、各功能模块之间的关
