算法设计与分析课程设计报告
压缩软件课程设计书
一、问题描述：
建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。
二、算法分析及思路：
对于该问题，我们做如下分析：
（1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；
（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计；
（3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计；
（4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计；
（5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计；
（6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。
三、主要解决的设计问题：
1.写一个对txt文件压缩和解压的程序，使用动态编码。
2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树；
3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。
4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件
（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。
五、输入和输出说明：
1、数据输入：由文件input.txt提供输入需要压缩的内容；
2、结果输出：将压缩好的文件内容输出到《编码后的文件.txt》中，再由《编码后的文件.txt》解压到《译码后的文件.txt》中。
六、程序及其注解：
1、数据结构设计（即类的设计，包括类的数据成员、函数成员）
类的设计用HuffmanTree.h保存如下:
#include
#include
using namespace std;
const int MaxSize=512;
//--------------------------------------------------------------
struct element //哈夫曼树的结点
{
int str; //记录字符在数组中的位置
int weight; //字符出现频率（权值）
int lchild,rchild,parent; //哈夫曼树各个指针变量
char bits[30]; //存储哈夫曼编码的数组
};
//--------------------------------------------------------------
class HuffmanTree
{
element hufftree[MaxSize]; //存放哈夫曼树结点的数组
int num; //结点数
public:
HuffmanTree(int w[],int s[],int n);
void Select(int n,int &s1,int &s2);
void Huffmancode(char wen[]); //哈夫曼编码
void Huffmandecode(); //哈夫曼译码
};
//--------------------------------------------------------------
class Run
{
public:
void huffman(char wen[]); //将编码后的文件译成原文件
void runhuffman(char wen[]); //统计各字符频率
void compare(char wen[]); //比较逍遥游文件和译码后的文件};
//--------------------------------------------------------------
2、算法设计（类的函数成员的具体设计）
（1）算法一设计用HuffmanTree.cpp保存如下：
#include
#include"HuffmanTree.h"
using namespace std;
//-------------------------------------------------------------------
void HuffmanTree::Select(int n,int &s1,int &s2)
{
s1=-1;
s2=-1;
for(int i=0;i<=n;i++)
{
if(hufftree[i].parent==-1)
{
if(s1==-1) {s1=i;continue;}
if(s2==-1) {s2=i;continue;}
if(hufftree[i].weight s1=i; else if(hufftree[i].weight s2=i; } } } //------------------------------------------------------------------- HuffmanTree::HuffmanTree(int w[],int s[],int n) { num=n; int i1,i2; i1=i2=0; for(int i=0;i<2*num-1;i++)//外部叶子结点数为num个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*num-1. { hufftree[i].parent=-1; hufftree[i].lchild=-1; hufftree[i].rchild=-1; } for(int j=0;j { hufftree[j].weight=w[j]; hufftree[j].str=s[j]; } for(int k=num;k<2*num-1;k++) //构建哈夫曼树 { Select(k-1,i1,i2); //在hufftree中找权值最小的两个结点i1和i2 hufftree[i1].parent=k; hufftree[i2].parent=k; hufftree[k].weight=hufftree[i1].weight+hufftree[i2].weight; hufftree[k].lchild=i1; hufftree[k].rchild=i2; } } //------------------------------------------------------------------- void HuffmanTree::Huffmancode(char wen[]) { ifstream in(wen); ofstream out("编码后的文件.txt"); int start=MaxSize-1; int cha=0; char cd[MaxSize]; //存放一个编码 cd[MaxSize-1]='\0'; for(int i=0;i { start=MaxSize-1; int c,f; for(c=i,f=hufftree[i].parent;f!=-1;c=f,f=hufftree[f].parent) { if(hufftree[f].lchild==c) //置左分支编码0 cd[--start]='0'; else cd[--start]='1'; //置右分支编码1 } strcpy(hufftree[i].bits,&cd[start]);//将编码存放在相应结点存储哈夫曼 编码的数组中 } cout<<"字符在数组中的下标及其编码如下："; //输出字符在数组中的位置及其编码 for(int k=0;k { if(k%3==0) cout< cout< } cout< for(char ch;in.get(ch);) //将逍遥游文件中各个字符转变成相应的编码，写入编码后的文件中 { if((int)ch<0) cha=(int)ch+256; else cha=(int)ch; for(int j=0;j if(hufftree[j].str==cha) out< } cout<<"编码成功！"< } //------------------------------------------------------------------- void HuffmanTree::Huffmandecode() { ifstream in("编码后的文件.txt"); ofstream out("译码后的文件.txt"); int i=2*num-2; for(char b;in>>b;) { if(b=='0')i=hufftree[i].lchild; else i=hufftree[i].rchild; if(hufftree[i].lchild==-1) { out<<(char)hufftree[i].str; i=2*num-2; } } cout<<"译码成功！"< } //------------------------------------------------------------------- （2）算法二设计用HuffmanRun.cpp保存如下： #include #include"HuffmanTree.h" using namespace std; //--------------------------------------------------------- void Run::runhuffman(char wen[]) { ifstream in(wen); int w[MaxSize]; int weight[MaxSize]; //存放各个字符的频率 int str[MaxSize]; //存放逍遥游文件中各个字符在数组w中的位置(下标) int i=0; int n=0; int cha=0; for(int j=0;j w[j]=0; /*从文件逍遥游中依次读入字符，根据字符的ASCII码值将字符存入str[]数组的相应位置 而weight[]数组的相应位置则记录该字符出现的频率*/ for(char ch;in.get(ch);) { if((int)ch<0) cha=(int)ch+256; //中文的ASCII码值为负数，加上256使其可以存放在数组中 else cha=(int)ch; w[cha]++; } for(int k=0;k if(w[k]!=0) { str[n]=k; weight[n]=w[k]; n++; } cout<<"字符在数组中的下标及其权值如下："; //输出字符在数组中的位置及其权值 for(int p=0;p { if(p%6==0) cout< cout< } cout< HuffmanTree h(weight,str,n); //构造哈夫曼树 h.Huffmancode(wen); //利用哈夫曼树进行编码及译码 h.Huffmandecode(); } void Run::huffman(char wen[]) { ifstream in(wen); int weight[MaxSize]; //存放各个字符的频率 int str[MaxSize]; //存放逍遥游文件中各个字符在数组w中的位置(下标) int n=0; HuffmanTree h(weight,str,n); //构造哈夫曼树 h.Huffmandecode(); } void Run::compare(char wen[]) { ifstream ina(wen); ifstream inc("译码后的文件.txt"); char stringa[100000]; int i=0; int flag=0; char stringc[100000]; int j=0; for(char cha;ina>>cha;) //将文件逍遥游的内容读入数组stringa[] { stringa[i]=cha; i++; } stringa[i]='\0'; for(char chc;inc>>chc;) //将译码后的文件内容读入数组stringc[] { stringc[j]=chc; j++; } stringc[j]='\0'; /*比较文件逍遥游和译码后的文件内容，若相同则说明编码正确，若不同，则说明编码错误*/ for(int k=0;stringa[k]!='\0'&&stringc[k]!='\0';k++) if(stringa[k]!=stringc[k]) flag=0; if(stringa[k]=='\0'&&stringc[k]=='\0') flag=1; else flag=0; if(flag==0) cout<<"逍遥游文件与译码后的文件不相同，编码错误！"< else cout<<"逍遥游文件与译码后的文件相同，编码正确！"< } （3）实现算法设计的主程序用HaffmanMain.cpp保存如下： #include #include"HuffmanTree.h" using namespace std; void main() { char wenjian[20];int t=1; while(1) { if(t==1) {cout<<"请输入要编码的文件名："; cin>>wenjian; Run manager; manager.runhuffman(wenjian); https://www.doczj.com/doc/d211888346.html,pare(wenjian);} else {cout<<"请输入要译码的文件名："; cin>>wenjian; Run manager; manager.huffman(wenjian);} cout<<"请继续选择需要执行的功能："< cout<<"请问您是需要编码文件还是译码文件？"< cout<<"如果是要编码文件，那么请输入1；"< cout<<"如果是要译码文件，那么请输入0。"< cin>>t; } } 七、程序运行结果及分析： 该课程设计实现了哈弗曼编码及译码问题，其中有一些独到之处，同时也有很多不足之处。比如说：其中的由编码文件直接翻译成译码文件没有单独实现，也没有很好的算法直接描述，而正好该问题在实际用途中很广泛，一般都要由一些特定规则单独实现译码问题。希望在以后的进一步学习中能很好的掌握该问题的算法优化。 课程设计报告模板(） ————————————————————————————————作者: ————————————————————————————————日期： ? 课程设计（论文)任务书 软件学院软件+电商专业0９级（2）班 一、课程设计(论文)题目基本模型机设计与实现 二、课程设计（论文）工作自２01１年6月 20 日起至2011年 6月 2４日止。 三、课程设计(论文) 地点：计算机组成原理实验室(５#３0１） 四、课程设计(论文)内容要求： 1.课程设计的目的 通过课程设计的综合训练，在掌握部件单元电路实验的基础上，进一步掌握整机 概念。培养学生实际分析问题、解决问题和动手能力,最终目标是想通过课程设计的形式，帮助学生系统掌握该门课程的主要内容，更好地完成教学任务。 ２.课程设计的任务及要求 １）基本要求? （１）课程设计前必须根据课程设计题目认真查阅资料; (２）实验前准备好实验程序及调试时所需的输入数据； （３)实验独立认真完成; (4)对实验结果认真记录,并进行总结和讨论。 2）课程设计论文编写要求 (1)按照书稿的规格撰写打印课设论文 (2）论文包括目录、绪论、正文、小结、参考文献、附录等 (3）正文中要有问题描述、实验原理、设计思路、实验步骤、调试过程与遇到问题的解决方法、总结和讨论等 （4）课设论文装订按学校的统一要求完成 ３)课设考核 从以下几方面来考查: （1）出勤情况和课设态度； (2)设计思路； （３）代码实现； （４)动手调试能力； (5)论文的层次性、条理性、格式的规范性。 ４）参考文献 [１］王爱英．计算机组成与结构［M]. 北京：清华大学出版社, 200７. [2] 王爱英. 计算机组成与结构习题详解与实验指导[M]. 北京：清华大学出版社, 2007. 5)课程设计进度安排 内容天数地点 构思及收集资料１图书馆 实验与调试 3 实验室 撰写论文 1 图书馆 6）任务及具体要求 设计实现一个简单的模型机，该模型机包含若干条简单的计算机指令,其中至少包括输入、输出指令，存储器读写指令，寄存器访问指令,运算指令,程序控制指令。学生须根据要求自行设计出这些机器指令对应的微指令代码,并将其存放于控制存储器，并利用机器指令设计一段简单机器指令程序。将实验设备通过串口连接计算机,通过联机软件将机器指令程序和编写的微指令程序存入主存中,并运行此段程序,通过联机软件显示和观察该段程序的运行，验证编写的指令和微指令的执行情况是否符 合设计要求，并对程序运行结果的正、误分析其原因。 学生签名: 亲笔签名 ２０1１年6月20 日 课程设计(论文)评审意见 (1）设计思路:优( ）、良（)、中( )、一般（）、差( ); （2）代码实现：优（）、良（)、中（）、一般（）、差(）; 《编译原理》课程设计大纲 课程编号： 课程名称：编译原理/Compiler Principles 周数/学分：1周/1学分 先修课程：高级程序设计语言、汇编语言、离散数学、数据结构 适用专业：计算机科学与技术专业、软件工程专业 开课学院，系或教研室：计算机科学与技术学院 一、课程设计的目的 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。 设计时间： 开发工具： （1） DOS环境下使用Turbo C； （2） Windows环境下使用Visual C++ 。 （3） 其它熟悉语言。 二、课程设计的内容和要求 设计题一：算术表达式的语法分析及语义分析程序设计。 1.目的 通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词 法检查和分析。 2.设计内容及要求： 算术表达式的文法： 〈无符号整数〉∷＝ 〈数字〉{〈数字〉} 〈标志符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝ [＋｜－]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝ 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝ 〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝ ＋｜－ 〈乘法运算符〉∷＝ ＊｜／ （1） 分别选择递归下降法、算符优先分析法（或简单优 先法）完成以上任务，中间代码选用逆波兰式。 （2） 分别选择LL（1）、LR法完成以上任务，中间代码选 用四元式。 （3） 写出算术表达式的符合分析方法要求的文法，给出 分析方法的思想，完成分析程序设计。 （4） 编制好分析程序后，设计若干用例，上机测试并通 过所设计的分析程序。 设计题二：简单计算器的设计 1．目的 通过设计、编制、调试一个简单计算器程序，加深对语法及语 义分析原理的理解，并实现词法分析程序对单词序列的词法检 查和分析。 2.设计内容及要求 算术表达式的文法： 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 课程设计报告 ( 2013-- 2014年度第1学期) 名称：编译技术课程设计B 题目：简单编译程序的设计与实现院系：计算机系 班级：XXX 学号：XXX 学生姓名：XXX 指导教师：XXX 设计周数：XXX 成绩： 日期：XX 年XX 月 实验一．词法分析器的设计与实现 一、课程设计(综合实验)的目的与要求 1.1 词法分析器设计的实验目的 本实验是为计算机科学与技术专业的学生在学习《编译技术》课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术设计出词法分析器，了解扫描器的组成结构，不同种类单词的识别方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。 1.2 词法分析器设计的实验要求 设计一个扫描器，该扫描器是一个子程序，其输入是源程序字符串，每调用一次识别并输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设该程序设计语言中，基本字（也称关键词）不能做一般标识符用，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。 单词符号及其内部表示如表1-1所示，单词符号中标识符由一个字母后跟多个字母、数字组成，常数由多个十进制数字组成。单词符号的内部表示，即单词的输出形式为二元式：（种别编码,单词的属性值）。 表1-1 单词符号及其内部表示 二、设计（实验）正文 1.词法分析器流程图 2.词法分析器设计程序代码 // first.cpp : 定义控制台应用程序的入口点。// #include"stdafx.h" #include 模拟电子技术课程设计报告设计题目：直流稳压电源设计 专业电子信息科学与技术 班级电信092 学号 200916022230 学生姓名夏惜 指导教师王瑞 设计时间2010-2011学年上学期 教师评分 2010年月日 昆明理工大学津桥学院模拟电子技术课程设计 目录 1.概述 (2) 1.1直流稳压电源设计目的 (2) 1.2课程设计的组成部分 (2) 2.直流稳压电源设计的内容 (4) 2.1变压电路设计 (4) 2.2整流电路设计 (4) 2.3滤波电路设计 (8) 2.4稳压电路设计 (9) 2.5总电路设计 (10) 3.总结 (12) 3.1所遇到的问题，你是怎样解决这些问题的12 3.3体会收获及建议 (12) 3.4参考资料（书、论文、网络资料） (13) 4.教师评语 (13) 5.成绩 (13) 昆明理工大学津桥学院模拟电子技术课程设计 1.概述 电源是各种电子、电器设备工作的动力，是自动化不可或缺的组成部分，直流稳压电源是应用极为广泛的一种电源。直流稳压电源是常用的电子设备，它能保证在电网电压波动或负载发生变化时，输出稳定的电压。一个低纹波、高精度的稳压源在仪器仪表、工业控制及测量领域中有着重要的实际应用价值。 直流稳压电源通常由变压器、整流电路、滤波电路、稳压控制电路所组成，具有体积小，重量轻，性能稳定可等优点，电压从零起连续可调，可串联或关联使用，直流输出纹波小，稳定度高，稳压稳流自动转换、限流式过短路保护和自动恢复功能，是大专院校、工业企业、科研单位及电子维修人员理想的直流稳压电源。适用于电子仪器设备、电器维修、实验室、电解电镀、测试、测量设备、工厂电器设备配套使用。几乎所有的电子设备都需要有稳压的电压供给，才能使其处于良好的工作状态。家用电器中的电视机、音响、电脑尤其是这样。电网电压时高时低，电子设备本身耗供电造成不稳定因家。解决这个不稳定因素的办法是在电子设备的前端进行稳压。 直流稳压电源广泛应用于国防、科研、大专院校、实验室、工矿企业、电解、电镀、充电设备等的直流供电。 1.1直流稳压电源设计目的 （1）、学习直流稳压电源的设计方法； （2）、研究直流稳压电源的设计方案； （3）、掌握直流稳压电源的稳压系数和内阻测试方法。 1.2课程设计的组成部分 1.2.1 设计原理 课程设计(论文)任务书 软件学院学院软件工程专业07-1班 一、课程设计(论文)题目LL(1)分析过程模拟 二、课程设计(论文)工作自 2010 年 6 月 22日起至 2010 年 6月 28 日止。 三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．本课程设计的目的 （1）使学生掌握LL（1）模块的基本工作原理； （2）培养学生基本掌握LL（1）分析的基本思路和方法； （3）使学生掌握LL（1）的调试； （4）培养学生分析、解决问题的能力； （5）提高学生的科技论文写作能力。 2．课程设计的任务及要求 1）基本要求： （1）分析LL（1）模块的工作原理； （2）提出程序的设计方案； （3）对所设计程序进行调试。 2）创新要求： 在基本要求达到后，可进行创新设计，如改算法效率。 3）课程设计论文编写要求 （1）要按照书稿的规格打印誊写课程设计论文 （2）论文包括目录、绪论、正文、小结、参考文献、附录等 （3）课程设计论文装订按学校的统一要求完成 4）答辩与评分标准： （1）完成原理分析：20分； （2）完成设计过程（含翻译）：40分； （3）完成调试：20分； （4）回答问题：20分。 5）参考文献： （1）张素琴，吕映芝，蒋维杜，戴桂兰.编译原理（第2版）.清华大学出版社 （2）丁振凡.《Java语言实用教程》北京邮电大学出版社 6）课程设计进度安排 内容天数地点 构思及收集资料2图书馆 编程与调试4实验室 撰写论文1图书馆、实验室 学生签名： 2009 年6 月22 日 课程设计(论文)评审意见 （1）完成原理分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）；（3）完成调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）翻译能力（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（） 评阅人：职称： 年月日 课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析 1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否 编译器的设计与分析 学号： 1233050143 姓名：李博 专业：计算机科学与技术 __ 课程：编译原理 指导教师：闫红 实验目的 本实验设计的小型编译程序涉及到编译前端的三个阶段：词法分析、语法分析和语义分析生成中间代码 ((四元式），编译程序的重点放在中间代码生成阶段。编译程序的输出结果包括词法分析后的二元式序 列、变量名表；语法分析后的状态栈分析过程显示；语义分析生成中间代码后的四元式程序。整个程序 分为三个部分：（1）词法分析部分（2）语法分析、语义分析及四元式生成部分（3)输出显示部分 实验要求： 本程序仅考虑由下面产生式所定义的程序语句： S →if B then S else S | while B do S | begin L end | A L →S;L | S A →i:= E B →B∧B|B∨B|～B|(B)|I rop i|i 其中，各个非终结符的含义是： S---语句 L—语句串 A—赋值句 B---布尔表达式 E---算术表达式 各个终结符的含义： i---整型变量或常数，布尔变量或常数； rop---为六种关系运算符的代表； ；---起语句分隔作用； ：=---赋值符号 ～--逻辑非运算符； ∧----逻辑与运算符； ∨---逻辑或运算符； 规定程序是由一条语句或由begin和end嵌套起来的复合语句组成的，并且规定的语句末加上#@表示程序结束。下面是符合规定的程序示例：begin A:=A+B*C; C:=A+2; while A if M=N THEN C:=D else while A<=D do A:=D end#@ 实验内容： 第一部分：词法分析 一．词法分析的功能： 输入：所给文法的源程序字符串 输出：1.二元组（单词种别,单词符号的属性值）构成的序列 2.关键字: { (相当于Pascal语言中的begin) , if ,else , while , }(相当于 Pascal语言中的end ) 所有的关键字都是小写字母. 3.运算符: + , - , * , / , = , < , <= , == , > , >= ,<> , && ,|| , ! 4.界符: 逗号,分号,左圆括号, 右圆括号, # 5.常数: 在这里只涉及到int型常量 6.其他单词是标识符（ID）和整形常数（NUM），通过以下正规式定义： ID = letter（letter|digit）* NUM = digit digit * 7.空格由空白，制表符和换行符组成，空格一般用来分隔ID，NUM，运算符，界符和关键字，词法分析阶段通常会被过滤掉。 二．词法分析程序设计 < 摘要（三号，黑体，居中，字间空两格字符） （空二行换行） 空4格打印摘要内容（小四号宋体,行距20）。 关键词：（摘要内容后下空一行打印“关键词”三字（小四号黑体），其后为关键词（小四号宋体），每一关键词之间用分号隔开，最后一个关键词后不打标点符号。 ABSTRACT ①居中打印“ABSTRACT”，再下空二行打印英文摘要内容。②摘要内容每段开头留四个空字符。③摘要内容后下空一行打印“Key words”，其后为关键词用小写字母，每一关键词之间用分号隔开，最后一个关键词后不打标点符号。 Key words ：aaa；bbb；ccc 目录（3号，黑体，居中） （空1行，以小4号黑体设置字体及大小，行间距22、字间距标准） 1 XXXXXX………………………………………………………………………… 1.1 XXXXXX……………………………………………………………………… 1.2 XXXXXX……………………………………………………………………… ┇ 2 XXXXXX………………………………………………………………………… 2.1 XXXXXX……………………………………………………………………… 2.2 XXXXXX……………………………………………………………………… ┇ 3 4 结束语 参考文献………………………………………………………………………………. 致谢……………………………………………………………………………………附录…………………………………………………………………………………… 编译原理程序设计报告 一个简单文法的编译器的设计与实现专业班级：计算机1406班 组长姓名：宋世波 组长学号： 20143753 指导教师：肖桐 2016年12月 设计分工 组长学号及姓名：宋世波20143753 分工：文法及数据结构设计 词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成 组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0) 部分目标代码生成 组员2学号及姓名：孙何奇20143754 分工：符号表组织 部分目标代码生成 摘要 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。 一．编译器的概述 1.编译器的概念 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。 2．编译器的种类 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语 .课程设计报告撰写规范 ————————————————————————————————作者：————————————————————————————————日期： 2 江西理工大学应用科学学院信息工程系 课程设计规范 （试行） 信息工程系 二○一○年六月 第1章内容要求 第1章内容要求 课程设计报告由以下几个部分组成组成，依次为： I、统一的封面，封面之后为课设评分表及答辩记录表； II、摘要； III、目录； IV、课程设计总结报告正文； V、总结（本课题核心内容、特点和方案的优缺点、改进方向和意见）VI、按统一格式列出主要参考文献。 1 第2章格式要求 第2章格式要求 课程设计报告每部分从新的一页开始，各部分要求如下： 2．1封面 统一的封面（含课程设计课题名称、专业、班级、姓名、学号、指导教师等，详见第五部分“格式范例”） 2．2摘要 应概括地反映出本课程设计的主要内容，包括工作目的、实验研究方法、研究成果和结论，重点是本论文的主要工作。摘要力求语言精炼准确，建议500字以内。摘要中不要出现图片、图表、表格或其他插图材料。 关键词是为了便于作文献索引和检索工作而从论文中选取出来用以表示全文主题内容信息的单词或术语。 关键词在摘要内容后另起一行标明，一般3～5个，之间用“；”分开。 2．3 目录 目录由标题名称和页码组成，包括：正文（含结论）的一级、二级和三级标题和序号。具体格式见第五部分“格式范例”。 2．4 符号说明 如果课程设计报告中使用了大量的物理量符号、标志、缩略词、专门计量单位、自定义名词和术语等，应将全文中常用的这些符号及意义列出。如果上述符号和缩略词使用数量不多，可以不设专门的主要符号表，但在报告中出现时须加以说明。缩略词应列出中英文全称。 2 编译原理课程设计报告 实验名称编译原理课程设计 班级 学号 姓名 指导教师 实验成绩 2013 年06月 一、实验目的 通过设计、编写和调试，将正规式转换为不确定的有穷自动机，再将不确定的有穷自动机转换为与之等价的确定的有穷自动机，最后再将确定有穷自动机进行简化。 通过设计、编写和调试构造LR(0)项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR(0)分析表的步骤，对文法的要求，能够从文法G出发生成LR(0)分析表，并对给定的符号串进行分析。 二、实验内容 正规式——>NFA——>DFA——>MFA 1.正规式转化为不确定的有穷自动机 （1）目的与要求 通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，使学生了解Thompson算法，掌握转换过程中的相关概念和方法，NFA的表现形式可以是表格或图形。 （2）问题描述 任意给定一个正规式r（包括连接、或、闭包运算），根据Thompson算法设计一个程序，生成与该正规式等价的NFA N。 （3）算法描述 对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 步骤1：首先构造基本符号的有穷自动机。 步骤2：其次构造连接、或和闭包运算的有穷自动机。 （4）基本要求 算法实现的基本要求是： (1) 输入一个正规式r； (2) 输出与正规式r等价的NFA。（5）测试数据 输入正规式：(a|b)*(aa|bb)(a|b)* 得到与之等价的NFA N （6）输出结果 2.不确定的有穷自动机的确定化 （1）目的与要求 通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。（2）问题描述 任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFA N变换为与之等价的DFA D。 （3）算法描述 用子集法将NFA转换成接受同样语言的DFA。 步骤一：对状态图进行改造 (1) 增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结 点引ε弧到Y结点。 (2) 对状态图进一步进行如下形式的改变 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图： 2011-2012学年第二学期 《编译原理》课程设计报告 学院：计算机科学与工程学院 班级： 学生姓名：学号： 成绩： 指导教师： 时间：2012年5 月 目录 一、课程设计的目的 ---------------------------------------------------------------- - 1 - 二、课堂实验及课程设计的内容 -------------------------------------------------- - 1 - 2.1、课堂实验内容-------------------------------------------------------------- - 1 - 2.2、课程设计内容-------------------------------------------------------------- - 1 - 三、visual studio 2008 简介------------------------------------------------------- - 2 - 四、问题分析及相关原理介绍 ----------------------------------------------------- - 3 - 4.1、实验部分问题分析及相关原理介绍 ---------------------------------- - 3 - 4.1.1、词法分析功能介绍及分析------------------------------------- - 3 - 4.1.2、语法分析功能介绍及分析------------------------------------- - 3 - 4.1.3、语义分析功能介绍及分析------------------------------------- - 4 - 4.2、课程设计部分问题分析及相关原理介绍 ---------------------------- - 5 - 4.2.1、编译程序介绍 ----------------------------------------------------- - 5 - 4.2.2、对所写编译程序的源语言的描述（C语言） -------------- - 6 - 4.2.3、各部分的功能介绍及分析 -------------------------------------- - 7 - 4.3、关键算法：单词的识别-------------------------------------------------- - 8 - 4.3.1、算法思想介绍 ----------------------------------------------------- - 8 - 4.3.2、算法功能及分析 -------------------------------------------------- - 8 - 五、设计思路及关键问题的解决方法 ------------------------------------------ - 10 - 5.1、编译系统------------------------------------------------------------------ - 10 - 5.1.1、设计思路 --------------------------------------------------------- - 10 - 5.2、词法分析器总控算法--------------------------------------------------- - 12 - 5.2.1、设计思路 --------------------------------------------------------- - 12 - 5.2.2、关键问题及其解决方法 --------------------------------------- - 13 - 六、结果及测试分析-------------------------------------------------------------- - 14 - 6.1、软件运行环境及限制--------------------------------------------------- - 14 - 6.2、测试数据说明------------------------------------------------------------ - 14 - 6.3、运行结果及功能说明--------------------------------------------------- - 16 - 6.4、测试及分析说明--------------------------------------------------------- - 16 - 七、总结及心得体会 --------------------------------------------------------------- - 17 - 7.1、设计过程------------------------------------------------------------------ - 17 - 7.2、困难与收获 ------------------------------------------------------------- - 17 - 八、参考文献 ------------------------------------------------------------------------ - 18 - 算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法 位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想： 课 程 设 计 报 告 书 专 用 纸 1 引言（或绪论）（可作为正文第1章标题，用小3号黑体，加粗， 并留出上下间距为：段前0.5行，段后0.5行） ×××××××××（小4号宋体，20磅行距）××××××××××××××××××××××××××××××………… 1．1 ××××××（作为正文2级标题，用4号黑体，加粗） ×××××××××（小4号宋体，20磅行距）×××××××××××××××××××××××××××××××………… 1.1.1 ××××（作为正文3级标题，用小4号黑体，不加粗） ×××××××××（小4号宋体，20磅行距）×××××××××××××××××××××××××××………… 2 ×××××××（作为正文第2章标题，用小3号黑体，加粗， 并留出上下间距为：段前0.5行，段后0.5行） ×××××××××（小4号宋体，20磅行距）×××××××××××××××××××××××××××××××××××………… ×××××××××××××××××××………… ………… 注：1．正文中表格与插图的字体一律用5号宋体； 2．正文各页的格式请以此页为标准复制。 请留出一个汉字的空间，下同 报告中的内容仅为参考字体格式，与本次设计无关！ 题目 内部排序教学软件。 1需求分析和说明 内部排序教学软件的总体目标：在TURBO C2.0 的开发环境下，利用所学C语言和数据结构的相关知识，开发一个具有良好人机界面的内部排序教学软件，实现各种内部排序，并能使用户通过其显示结果对每种排序方法的性能有一个直观的了解，从而达到教学的目的。 1.1基本要求 （1）界面友好，易与操作。采用菜单或其它人机对话方式进行选择。 （2）实现各种内部排序。包括冒泡排序，直接插入排序，直接选择排序，希尔排序，快速排序，堆排序。 （3）待排序的元素的关键字为整数。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。 （4）演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标 的列表，以便比较各种排序的优劣。 1.2各功能模块的功能描述： 1．主函数模块 本模块的主要功能是初始化图形界面，调用各模块，实现软件功能。 2．排序功能及输出子模块 本模块的主要功能是根据用户的选择进行数组的创建，并对输入数据或者随机产生的数据使用六种排序方法进行排序并统计每种方法的移动次数和比较次数，然后输出以表格形式输出。 3．封面和结束画面子模块 本模块的主要功能是当用户打开本软件时模拟软件加载，延时数秒后关闭，并进入图形界面，在用户退出软件时显示结束画面，延时数秒后关闭程序。 4．图形界面子模块 本模块的主要功能是根据用户的选择显示不同的画面，引导用户使用软件所提供的各种功能，并在用户提供必要数据，并选择排序功能时调用排序模块，并显示结果画面。 5．输入子模块 本模块的主要功能是进行光标定位，输出提示文字，并对用户输入数据进行处理，创建数组。 6.鼠标实现模块 本模块的主要功能是为用户提供鼠标操作支持，使用户能使用鼠标进行功能的选择。2详细设计 编译原理课程设计报告 课题名称：C- Minus词法分析和语法分析设计 提交文档学生姓名：X X X 提交文档学生学号：XXXXXXXXXX 同组成员名单：X X X 指导教师姓名：X X 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2015年6月10日 1.课程设计目标 实验建立C-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。 2.分析与设计 C-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。 2.1 、扫描程序scanner部分 2.1.1系统设计思想 设计思想：根据DFA图用switch-case结构实现状态转换。 惯用词法： ①语言的关键字：else if int return void while ②专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 大写和小写字母是有区别的 ④空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM 关键字。 ⑤注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套 scanner的DFA 说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。 2.1.2程序流程图 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计：课程设计报告模板)
编译原理课程设计
算法设计与分析实验报告贪心算法
编译实验报告+源代码
课程设计报告【模板】
编译原理课程设计报告_LL(1)分析过程模拟
算法设计与分析课程设计报告样本
编译原理 C++编译器课程设计报告
EDA课程设计说明书参考格式
编译原理课程设计报告(一个完整的编译器)
课程设计报告撰写规范
(重庆理工大学计算机学院)编译原理课程设计报告
算法设计与分析课程设计报告
编译原理课程设计报告
算法设计与分析课程报告
课程设计报告书正文标准格式
CMinus词法分析和语法分析设计编译器编译原理课程设计报告书
算法设计与分析实验报告
相关主题
文本预览