云南大学软件学院数据结构实验三栈和队列及其应用.docx
- 文档编号:17408622
- 上传时间:2023-07-25
- 格式:DOCX
- 页数:30
- 大小:152.31KB
云南大学软件学院数据结构实验三栈和队列及其应用.docx
《云南大学软件学院数据结构实验三栈和队列及其应用.docx》由会员分享,可在线阅读,更多相关《云南大学软件学院数据结构实验三栈和队列及其应用.docx(30页珍藏版)》请在冰点文库上搜索。
云南大学软件学院数据结构实验三栈和队列及其应用
(本实验项目方案受“教育部人才培养模式创新实验区(X3108005)”项目资助)
实验难度:
A□B□C√
序号
学号
姓名
成绩
1
2
3
4
指导教师
(签名)
学 期:
2013秋季学期
任课教师:
张德海
实验题目:
栈和队列及其应用
小组长:
联系电话:
电子邮件:
完成提交时间:
2013年10月22日
学号:
姓名:
本人承担角色:
评分项目
评分指标
分值
得分
实验构思(10%)
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计(15%)
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整,数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现(25%)
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常,测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写(10%)
1.内容详实无缺漏,文字流畅、图表清楚
5
2.实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考
5
个人工作量(30%)
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作(10%)
1.有一定用户群
5
2.应用前景分析
5
综合得分:
(满分100分)
指导教师:
年月日
学号:
姓名:
本人承担角色:
评分项目
评分指标
分值
得分
实验构思(10%)
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计(15%)
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整,数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现(25%)
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常,测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写(10%)
1.内容详实无缺漏,文字流畅、图表清楚
5
2.实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考
5
个人工作量(30%)
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作(10%)
1.有一定用户群
5
2.应用前景分析
5
综合得分:
(满分100分)
指导教师:
年月日
学号:
姓名:
本人承担角色:
评分项目
评分指标
分值
得分
实验构思(10%)
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计(15%)
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整,数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现(25%)
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常,测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写(10%)
1.内容详实无缺漏,文字流畅、图表清楚
5
2.实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考
5
个人工作量(30%)
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作(10%)
1.有一定用户群
5
2.应用前景分析
5
综合得分:
(满分100分)
指导教师:
年月日
学号:
姓名:
本人承担角色:
评分项目
评分指标
分值
得分
实验构思(10%)
1.实验目的明确
5
2.实验内容理解透彻、对实验所涉及到的知识点分析到位
5
实验设计(15%)
1.有对基本数据结构的抽象数据类型定义
5
2.实验方案设计完整,数据结构、算法选择合理
5
3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图
5
实验实现(25%)
1.代码编写规范、风格统一、注释清楚易读
5
2.程序运行正常,测试结果正确
15
3.界面友好、易于操作、有较强的容错性
5
实验报告撰写(10%)
1.内容详实无缺漏,文字流畅、图表清楚
5
2.实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考
5
个人工作量(30%)
1.个人完成工作量
15
2.个人技术水平
10
3.团队合作精神
5
实验运作(10%)
1.有一定用户群
5
2.应用前景分析
5
综合得分:
(满分100分)
指导教师:
年月日
(注:
此表在难度为C时使用,每个成员一份。
)
(下面的内容由学生填写,格式统一为,字体:
楷体,行距:
固定行距18,字号:
小四,个人报告按下面每一项的百分比打分。
难度A满分70分,难度B满分90分)
一、【实验构思(Conceive)】(10%)
(本部分应包括:
描述实验实现的基本思路,包括所用到的离散数学、工程数学、程序设计、算法等相关知识)
基本思路:
1.将要编码/译码的文件读入缓冲区,对每个字符的ASCII码按输入的密码所求得的加密值进行变换然后重新写入新的文件,编码/译码为逆过程,加密值依赖于输入的密码。
2.先在控制台下将核心算法实现,以保证算法的正确性和准确性。
3.依据在控制台下实现的算法移植到MFC应用程序中,加上流程控制和输入控制等,最终实现窗口界面程序。
相关知识:
C++文件流操作,VC文件操作。
ASCII码字符集以及字符的基本编码知识。
二、【实验设计(Design)】(20%)
(本部分应包括:
抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系)
代码实现部分主要包括5个事件,
(1)载入文件;利用MFC/C++的CstdioFile文件对象获取到文件名后将文件载入并读入预设缓冲区,等待处理。
(2)输入密码;CstringPaswds;类型缓冲区用以存储密码;在载入文件之前不允许输入密码,而在载入文件后将等待输入密码,密码不允许为空;输入的密码载入预设缓冲区。
(3)加密值计算;依据输入的密码按一定规则对Paswds(比如取奇数位的ASCII码之和)进行计算得出一个值作为加密值;
(4)执行加密(基本操作);依据文件拓展名进行判断,是否为程序自定义的加密文件,若否则进行加密;对读入缓冲区的文件内容从头到尾依据加密值进行单字符ASCII值变换,如加上/减去加密值。
存于字符缓冲区本身,然后输出到文件(加密文件),在输出到文件之前先将源文件的大小值写入加密文件头部。
(5)执行解密(基本操作);依据文件拓展名进行判断,为程序自定义的加密文件,则先读取文件头部的数据进行对文件内容大小值的计算;然后对读入缓冲区的原加密文件内容依据加密值进行反向求解字符ASCII码值;存于缓冲区本身,然后将缓冲区中除掉文件头部的文件大小数据值后的其他内容输出到解密文件。
文件处理思路:
1.对文件进行判断是编码还是译码是依据文件的后缀名来处理的
2.由于采用的是C++的文件流读写文件,而C++文件流的如果文件名非全英文,比如包含中文的全路径文件名,则C++文件流无法正确处理,所以在处理的时候选择了将源文件先拷贝到系统临时文件夹,然后再对临时文件夹中的拷贝临时源文件****\\Templates\\FCSrcFile.***进行读取,然后编码/译码,写入同样存在于临时文件夹中的目标文件临时文件****\\Templates\\FCDestFile.***,最后将临时目标文件重新命名成与最初源文件同名的目标文件,拷贝到桌面,再将临时文件夹中的两个中间文件删除。
如下图所示:
三、【实现描述(Implement)】(30%)
(本部分应包括:
抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系,关键的程序流程图等,给出关键算法的时间复杂度分析。
)
1.程序模块说明:
主要包含两个部分,一个是对输入文件的处理,如判别拓展名,计算临时文件名和目标文件名;一个是编码/译码处理;详见如下代码:
(1).第一部分
CFileDialogFileDlg(true,TEXT("AllFile"),NULL,OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,TEXT("AllFiles(*.txt;*.c;*.cpp;*.asm;*.fct;*.fcc;*.fcp;*.fcm)|*.c;*.cpp;*.txt;*.asm;*.fct;*.fcc;*.fcp;*.fcm|CFiles(*.c)|*.c|CPPFiles(*.cpp)|*.cpp|ASMFiles(*.asm)|*.asm|TextFiles(*.txt)|*.txt|FCoderFiles(*.fct;*.fcc;*.fcp;*.fcm)|*.fct;*.fcc;*.fcp;*.fcm||"));
if(FileDlg.DoModal()==IDOK)
{
SrcFilePath=FileDlg.GetPathName();//获取完整文件名
GetDlgItem(IDC_PSWDS)->EnableWindow(true);//启用密码输入框
GetDlgItem(IDC_CHECKCHOSE)->EnableWindow(true);//启用选择框
((CButton*)GetDlgItem(IDC_BNFILEOPEN))->EnableWindow(false);//禁用浏览按钮
//判断文件拓展名
for(inti=SrcFilePath.GetLength()-1;SrcFilePath[i]!
=Oprt;i--){
Temp+=SrcFilePath[i];
tmpi=i;
}
for(inti=Temp.GetLength()-1;i>=0;i--)//获取拓展名
DevlpmtName+=Temp[i];
Oprt=_T("\\");
for(inti=tmpi-2;SrcFilePath[i]!
=Oprt;i--)
TmpSrc+=SrcFilePath[i];
Oprt=_T("");
for(inti=TmpSrc.GetLength()-1;i>=0;i--)//获取原文件名
Oprt+=TmpSrc[i];
Oprt+=_T(".");TmpSrc=Oprt;
if(SUCCEEDED(SHGetMalloc(&pShellMalloc)))if(SUCCEEDED(SHGetSpecialFolderLocation(NULL,CSIDL_TEMPLATES,&lp)))
if(SHGetPathFromIDList(lp,(LPWSTR)SrcFileName))
Temp.Format(_T("%s"),SrcFileName);
Temp+=_T("\\FCSrcFile.");
Temp+=DevlpmtName;//获得源文件名,存在于临时文件夹中
SrcTmpFile=Temp;
:
:
CopyFile(SrcFilePath,Temp,false);//复制源文件到临时文件夹
pSrc=(char*)Temp.GetString();
memset(SrcFileName,0,MAX_PATH);
ConvertToChar(pSrc,SrcFileName,Temp.GetLength());
//判断是否为加密文件bIsCoding=true;//已加密bIsCoding=false;//未加密
if(DevlpmtName.CompareNoCase(_T("fct"))==0)
{
bIsEncoding=true;//已加密
DevlpmtName=_T("txt");
}
elseif(DevlpmtName.CompareNoCase(_T("fcc"))==0)
{
bIsEncoding=true;//已加密
DevlpmtName=_T("c");
}
elseif(DevlpmtName.CompareNoCase(_T("fcp"))==0)
{
bIsEncoding=true;//已加密
DevlpmtName=_T("cpp");
}
elseif(DevlpmtName.CompareNoCase(_T("fcm"))==0)
{
bIsEncoding=true;//已加密
DevlpmtName=_T("asm");
}
elseif(DevlpmtName.CompareNoCase(_T("txt"))==0)
{
bIsEncoding=false;//未加密
DevlpmtName=_T("fct");
}
elseif(DevlpmtName.CompareNoCase(_T("c"))==0)
{
bIsEncoding=false;//未加密
DevlpmtName=_T("fcc");
}
elseif(DevlpmtName.CompareNoCase(_T("cpp"))==0)
{
bIsEncoding=false;//未加密
DevlpmtName=_T("fcp");
}
elseif(DevlpmtName.CompareNoCase(_T("asm"))==0)
{
bIsEncoding=false;//未加密
DevlpmtName=_T("fcm");
}
//依据加密状态显示按钮内容
if(bIsEncoding)
((CButton*)GetDlgItem(IDC_ENCODING))->SetWindowText(_T("开始译码"));
else
((CButton*)GetDlgItem(IDC_ENCODING))->SetWindowText(_T("开始编码"));
bOFile=true;
}
(2).第二部分(相对纸质报告改进的代码)
//======================编译码==============================
fstreamSrcFileIn(SrcFileName,ios_base:
:
in|ios_base:
:
app);//以输入和附加模式打开源文件
fstreamDesFileOut(DesFileName,ios_base:
:
out|ios_base:
:
app);//以输出和附加模式打开文件
if(!
bIsEncoding)//未编码文件,执行编码
{
SrcFileLen=-1;
while(!
SrcFileIn.eof())//统计字节数同时进行编码
{
SrcFileIn.get(Ch);
SrcFileLen++;//统计字节数,用以译码
Ch+=PSWD;//编码
DesFileOut.put(Ch);//写入目标文件
}
//字节记录
DesFileOut< PSWD=0;//统计字节数位数 for(inti=0;SrcFileLen>0;i++) { SrcFileLen/=10; PSWD++; } DesFileOut< }else{//已编码文件,执行译码 charLen[PSWMAX];//允许亿个字符 //读取源文件字节数 SrcFileIn.seekg(-1,ios_base: : end); SrcFileIn.get(Ch); SrcFileLen=Ch-48; memset(Len,0,PSWMIN); //统计字节数 for(inti=SrcFileLen-1,j=-2;i>=0;i--,j--) { SrcFileIn.seekg(j,ios_base: : end); SrcFileIn.get(Ch); Len[i]=Ch; } Len[SrcFileLen]='\0'; SrcFileLen=atoi(Len); //编码并写入文件 SrcFileIn.seekg(0,ios_base: : beg); for(inti=0;i { SrcFileIn.get(Ch); Ch-=PSWD;//译码 DesFileOut.put(Ch);//写入目标文件 } } DesFileOut.close(); SrcFileIn.close(); //=====================结束====================================== 4.算法复杂度分析: 程序中基本的操作是执行加密和解密的循环操作,由于第一次编码/译码时C++文件流会多写一个字符,所以第一次对文件进行字节统计,第二次实现编码/译码并写入目标文件;即对文件内容进行字节统计和对ASCII码值变换编码/译码是最基本操作,也是核心操作,该操作的循环次数又依赖于读入文件的内容字节数n的多少,故时间复杂度为O(2n);在空间上,因为是单字符读入内存处理然后写入文件,所以对内存空间开销是非常小的,可以忽略不计。 5.算法流程图 四、【实验总结】(10%)(本部分应包括: 自己在实验中完成的任务,注意组内的任意一位同学都必须独立完成至少一项接口的实现;对所完成实验的经验总结、心得) 负责算法的设计、前期控制台算法的正确性验证、窗口程序部分的流程控制及后期调试;实验中发现设计好了的算法,具体实现起来还是有很多困难的,并不像想象中的那么简单,所以一定要亲自动手实践,操作代码,才能够有更具体的收获,也才能懂得自己的缺陷和不足,以便及时补之。 在此次实验中,我参与了界面的设计,完成了“浏览”控件的代码实现,其中包含了对输入文件的基本计算,如判别文件后缀名,计算目标文件名,后缀名等。 完成了报告中第一、二、三部分的编写,参与了程序的部分后期调试工作;实验中再次接触MFC的操作,由于了解的不多,操作起来还是比较困难,查阅了许多资料;自己在MFC窗口编程方面的收获又增加了不少。 我参与完成了“编/译码”控件的代码实现,其中包含了基本算法的实现,完成了报告中后几部分的编写。 因对MFC提供的文件流对象不太熟悉,加之对文件处理的效果并不是预期般地理想,所以算法实现部分采用了C++的文件流编写,而不是VC提供的内部类,且实现起来比较简单,效果也较为理想。 自己在VC编程方面还是有了一些收获。 五、【项目运作描述(Operate)】(10%) (本部分应包括: 项目的成本效益分析,应用效果等的分析。 ) 程序算法设计简单,基于窗口界面,具备一定的实用性,可用来加密源代码文件等,由于设计中加密依赖于输入的密码,故比较灵活;程序开始之初总会有一些BUG,但在以后的升级版本中将会慢慢改进,争取能够把程序发布给大家共享。 六、【代码】(10%) (本部分应包括: 完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。 格式统一为,字体: Georgia,行距: 固定行距12,字号: 小五) 仅附上部分代码(完整的代码参见上传的源文件): voidCFileEncoderDlg: : OnBnClickedBnfileopen() { voidConvertToChar(char*,char*,int);//从CString转换到char[] UpdateData(true); inttmpi; char*pSrc; CStringOprt(_T(".")); LPITEMIDLISTlp;//用以获取指定文件夹位置 LPMALLOCpShellMalloc;//用以获取指定文件夹位置 CFileDialogFileDlg(true,TEXT("AllFile"),NULL,OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,TEXT("AllFiles(*.txt;*.c;*.cpp;*.asm;*.fct;*.fcc;*.fcp;*.fcm)|*.c;*.cpp;*.txt;*.asm;*.fct;*.fcc;*.fcp;*.fcm|CFiles(*.c)|*.c|CPPFiles(*.cpp)|*.cpp|ASMFiles(*.asm)|*.asm|TextFiles(*.txt)|*.txt|FCoderFiles(*.fct;*.fcc;*.fcp;*.fcm)|*.fct;*.fcc;*.fcp;*.fcm||")); if(FileDlg.DoModal()==IDOK) { SrcFilePath=FileDlg.GetPathName();//获取完整文件名 GetDlgItem(IDC_PSWDS)->EnableWindow(true);//启用密码输入框 GetDlgItem(IDC_CHECKCHOSE)->EnableWindow(true);//启用选择框 ((CButton*)GetDlgItem(IDC_BNFILEOPEN))->EnableWindow(false);//禁用浏览
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 云南大学 软件 学院 数据结构 实验 队列 及其 应用