生产实习目的
测量学实习是测量学教学的重要组成部分,其目的使学生巩固、扩大和加深从课堂学到的理论知识,获得实际测量工作的初步经验和基本技能,进一步掌握测量仪器的操作方法,提高计算和绘图能力,对测绘小区域大比例尺地形图的全过程有一个全面和系统的认识,会认识地形图,能够根据给定的地形图在实际中寻找到图上所示的点,并在实习的过程中增强其独立工作与团队协作意识,为今后解决实际工作中的有关测量问题打下坚实的基础。 学生通过本次实习应达到如下要求:
1. 掌握经纬仪、视距尺等测量仪器的操作方法;
2. 掌握地形测图的基本方法,能够具有初步测绘小区域大比例尺地形图的工作能力;
3. 能够根据给定的地形图在实际中寻找到图上所示的点;
4. 各小组分工明确、通过合作完成测量任务,增强独立工作能力与团队协
生产实习时间及地点
1.地形图测绘实习地点:中国地质大学北区南望山 时间:20xx年10月15日至20xx年10月16日.
2.地形图识图实习地点:九峰山 时间:20xx年10月19日
实习小组信息
组别:地空学院061113班 测量3组
指导老师:XX
组员:XX、XX、XX、XX、XX组员分工:
选点与跑尺:XX
记录与计算:XX/XX
描点与绘图:XX
实习内容
(一)大比例尺地形图的测绘:
1.地点:中国地质大学北区南望山
2. 任务:通过两天的地形图测绘实习,每小组要取得200个左右的测点数据,并根据得到的数据完成一幅比例尺1:500,等高距1m的30cmx30cm的地形图
3.内容:(1)20xx年10月14日下午,刘甜甜、鲁凯跟老师去踩点.我和其他组员到学校出版社领仪器(经纬仪),工具及用品的准备(包括测量记录手簿、2H绘图铅笔、三棱尺、半圆仪、图板、计算器、直尺等基本物品);
(2)20xx年10月14日晚上,我、XX/XX按照使测绘更加方便、有效、快捷的原则,根据测区位置,在图板上布设控制点;我先按图纸对角画两条对角线,然后等距量取四条对角边,连线,各取每10cm每条边取点连线得到30cmx30cm的图根,然后XX按比例尺计算出控制点的位置,最后XX在图上找出对应坐标位置点出控制点,最后完成了全部展点工作。
(3)过程:
测区面积有150mx 150m,中间有一座小山丘,山丘上面有一个房子、毕业墙、一个圆柱体。控制点是已知高程(海拔)的点,我们需要在这些控制点上架设经纬仪,以它们为基准来测它与其他位置点的高差,进而推算位置点的高程(海拔)。因为控制点的个数有限,尤其是位置好的控制点更是稀少,所以我们必须要有抢占有利控制点的意识与冲动。只有如此,我们的测绘才会更加高效。实习的前一天,所有人都在抢占有利控制点上做了充分准备。20xx年10月15早上因为运动会耽误了一点时间所以到中午我们组才这全部到达南望山 ,因此有利的控制点基本被占领了!但是为期两天的测量实习就这样开始了!
第一天大家都没有一点经验,我们找到了山上的房子旁边的一个控制点——43号点,XX用
他新的对中、整平方法快速对中整平了可是他说要用直尺测量房子的边长,我认为不妥!因为这就是和用经纬仪测距违背了!我提出了疑义,我们去看书不断的摸索,最后提出一个到后面才知道是错的方法!就是用两个控制点定出一个点!一天到下午测不了几个碎步点,分工也很乱!有时后我们队员都不知道做什么,后来,我们换到离43号点较近的21号点,准备测量,可是从早上到现在我们的测量方法一直在变,一直有争议,在这两个点测到得数据也不懂怎么用!到这时天色准备暗下来了!
老师看到我们组的进度缓慢就叫一个测得快的组的一名组员来帮忙,听着这名同学讲解,我们明白了整个测量的基本过程:
1:将架设好的经纬仪对准另一个控制点,调节水平度盘使读数为零。
2:让选点跑尺的组员选好碎步点,是山坡的,一般应该在大概认为同一高度选出若干个碎步点,立尺。
3:让观察者将经纬仪转向标尺读出上丝读数、中丝读数、下丝读数、水平度盘读数、竖直度盘读数,让记录员记录
4:计算者计算出上丝读数减下丝读数、用公式计算出实际距离、高程、根据比例尺算出图上距离,填入手簿,同时告诉绘图者角度、图上距离和高程。
5:绘图者根据所得到的数据用半圆仪、直尺、铅笔绘出碎步点标出高程。
明白整个过程之后我们知道之前的数据都作废了!太阳开始落山,我们赶快行动,天色真的已经很黑了,连看度盘读数都只能用手机照明才能看清!就这样在天完全黑之后我们只完成两个控制点的测量,我们托着疲惫的身体回来了,我们组设最后一组回来的,但是我们已经完全清楚明天我们该做什么、该怎么做,相信我们明天一定能完成任务!
经过昨天的教训20xx年10月16日这天早上6点我们就起床,早早的到达了北区南望山,这一天我们是第一组到达的!我们有明确的分工,明确的测量步骤,明确的测量路。我们的效率很高,第一个地点是上山的路口阶梯从6号点到22号点选择拐点....。就这样一片片山坡、山谷、低地....被我们选点、观察、记录、计算、绘图描绘出来了。
就这样到了两点我们因为早上都只吃了一个饼而体力不支了!个个脸色惨白,又不能休息,因为我们还有很多点没测。这时食堂只有面食了!我们只好轮流去吃,去了两个组员,就在这时我们发现39号点的数据全部有误,原来是所标的39号点本来就是有误的!我们很气愤,但是我们必须坚持,我们继续测到35号点终于测完了!这时我们已经累得趴在山坡上了!看看表离交仪器的时间还有一个小时,强忍着疲惫、饥饿、困意我们扛着感觉比以前重了很多的仪器到学校出版社交了,让我们感到欣慰的是还有许多组还没测完!
心得体会
1. 经过这次实习让我感受到学会理论和实际的结合是很重要且是一个循序渐进的过程。要达到实践贯通,把课本知识很好的运用到实际中是会受到许多挫折的,比如我们组在实习第一天基本没什么收获。我作为计算员我用到的公式有:....., 式中Hi是碎步点高程,Da1是测站至碎步点的水平距离,k 视距乘常数;t为(尺间距)上丝、下丝读数之差;l为中丝读数;i为仪器高;a为竖直角。可是在实际计算时不能死搬硬套公式,比如a角是竖直角当这角是90度是用计算器算时是输入0度,当这角大于90度时用这角减去90度所得的角度加上负号在输入,小于是用90度减去所得读数直接输入,还有一些简便一点的计算方法也是实际操作后才慢慢摸索出来的,同样绘图员、记录员、观察员、跑尺选点员都会遇到不一样的实际问题。所以说实习是把我们从课本学到的知识用到实际的一个过程。
2.通过这次实习也让我感受到以前的艰苦条件下做一幅全国地形图是多么的困难和来之不易啊!也为我们作为地大人能为人们作出的贡献而感到自豪和敬佩!
(二) 持图实地跑点实习:
1.地点:九峰山
2.任务:到达图上表示的指定地点中的至少5个,将实地编号标注到地图上.
3.内容:
(1)全组成员集中分析地图,确定初始路线;
(2)按照初始路线寻找指定点;
(3)过程:
20xx年10月19日晨,我们从中国地质大学出版社拿到的不再是经纬仪、三角架和视距尺,而是一张九峰山地区的地图。是一张已经泛黄的,19xx年绘成的地图,上面采用的最接近成图时间的数据是19xx年的。图上画了许多个框框,它们标注的就是我们组今天要到的地方。虽然每个小组的地图是一样的,但上面被标注的点却是不一样的。也就是说,我们的目的地可能有重合,但不会是每个目的地都一样。因此,各组之间几乎独立的,合作被限定在了组内。老师告诉我们,图上表示的一个池塘已经填掉了,变成了农田,有座桥已经不存在了,图上表示的湖北省林业科学研究所已经更改了地址。这加重了我们对这张地图的怀疑,其他的地方就没有变化吗?我们要找的点在实地被标注在电线杆、石板桥、池塘壁等地方,而且这些点上是有编号的,我们只有真正到过这些点才能知道它们的编号。按照要求,我们要把这些编号标注在地图上,我们要至少找到5个。
今天我们从地大出版社坐车出发到一个加油站下,这里就是潜力村也就是出发点。组员们捧着这张地图走向了一片未知区域。地图成了我们不会迷路的唯一保障。跟着大部队,我们翻过了第一座山,山的背后是公墓。很快我们到了第一个路口,我们要找的一个点在向东的方向,其他点在向西的方向,而且那个独立的点要翻过一座高山才会到达。分析了利弊后,我们决定放弃它。放弃它就意味着放弃大部队,我们组成了少数走向西道路的小组。对比了图上池塘的位置,我们终于找到了它,地图告诉我们,这里有地大的点。在一个田边的电线杆上,我们看到了“地大78”。这是我们的第一个成果。但是这次我们又犯了一个错误:我们把图上的点当作我们要找的点!费了很多时间在这附近找等到后来的一组来了问明之后才知道这本来就是我们要找的点!
沿着池塘边的公路,我们继续前行,过了1个比较大的村子。重新看了一遍地图,对比了实地,我们还问了当地的老乡,我们要找到一个祠堂然后找到一个村子,我们很快看到了远方我们要找的祠堂和村子。为了抄近路,我们进了稻田。秋天的稻田已是十分空旷,但湖北多湖的特点注定这里是泥泞的。选择了走农田,那么可能出现的点就只能在电线杆上。直到走出稻田,我们也没有发现要找的点。我们又经过了一个村子来到这村后一座小山,用地形图所给的正北方向结合刚升起不久的太阳代表的东边找到了有一个点就在这座村子旁的另一个村子里,确定之后我们飞奔去哪里,在途中碰上了另一个小组,我们就和并成一个组,在这个村我们顺利的找到了21号点,这点非常隐蔽而且也被破坏得很厉害.
这时我们遇到一个艰难的选择,该是北走去曹家村,还是向西走去下刘村?去了下刘村就过了几个点,可是到了下刘村就接近目的地了!经过讨论我们决定还是去了下刘村,经过下刘村是我们问水库在哪里!老乡说要经过涵洞,我们就经过了涵洞,到了一片山林,我们非常艰难的穿过这片充满荆棘的山林又到了一片长满杂草的田野,过了这片田野,我们每个人的衣服、鞋带都插有许多不知名的刺!
我们到达水库时所有的组员又累又饿,在这里即找不到点也为往哪里走而迷茫,本来一个点找不到十几分钟就应该放弃,但是由于这个错我们一直以问当地的老乡为判断所走的方向是否正确,当我们找到100号点时,已经没有时间停留了,我们奔跑在途中找到145号点,往前走就是上山的小路,这就是老师说的通往老林科所的捷径!我们继续奔跑!体力好的跑在前面但也带着重物,同时不忘告诉后面的队员往哪里走,就这样看到一条马路上标有地大CUG字符,向下走看到一只锁着的狗一直在叫,最终看到了在老林科所等待的邹蓉老师,能看到
她真的很高兴!随后队员们全部到齐!然后跟随老师到达土桥村的一个已经废弃的大加油站,在这里能看到其他组,在这里和他们交流,等了十几分钟等到学校派来的车,坐上车,大家都累了,已经没有刚来时在车上的喧闹、许多人已经在这回校的车上进入梦乡!持图实地跑点实习就这样落下帷幕。
心得体会
1. 经过这次跑点实习,是我认识到要准确看懂一幅地形图并能把它和实际地形正确符合起来确实是一件不容易的事
2.在跑点过程中队员之间一定要团结协作,不能有争执
3.在这次实习中我们除了感到累,更重要的是我们同时也感受到了运用智慧的乐趣、团结协作的快乐、成功在规定时间之内到达目的地欢喜。
误我们组失去了许多时间,最后我们终于决定往蚂蚁峰走,这时得到另一些组已经到达使我们不免有一些丧气,经过一个十字路口时,往前就有一个点,可是这是一座挖空的山,我们想碰碰运气可是终究找不到,回到十字路口,这时我们这个合并组分别往相反的方向走!当我们感觉我们走的方向是对的时,我们跑步前进,不,可以说是狂奔!过往的山中美景、田园风光都被我们忽略了,我们的目标只有一个——老林科所。
第二篇:中国地质大学(武汉)信息工程学院 数据结构实习报告
《数据结构》课程设计
学生姓名: 占 昭
班 学 号: 20111003494
指导教师: 吴 亮
中国地质大学(武汉)信息工程学院
2012 年 11 月
1.题目:
n n(n>20)的阶乘
n 【问题描述】
n 大数运算——计算n的阶乘(n>=20)。
n 【基本要求】
n (1)数据的表示和存储;
n (1.1) 累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求;
n (1.2) 试设计合适的存储结构,要求每个元素或结点最多存储数据的3位数值。
n (2)数据的操作及其实现:
n 基于设计的存储结构实现乘法操作,要求从键盘上输入n值,在屏幕上显示最终计算结果。
n 【测试数据】
n (1)n=20,n!=2432902008176640000
n (2)n=30,n!=265252859812191058636308480000000
v 【实现提示】
v 1)设计数据的存储结构:
v 介于阶乘运算的精确性以及实型数据表示的不精确性,本题不能采用实型表示累积运算的中间结果和最终的计算结果,而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制,不能表示大数阶乘的累积结果,故必须设计一个合适的数据结构实现对数据的存储,例如可以让每个元素或结点存储数据的若干位数值。
v 从问题描述不难看出n值为任意值,故为使程序尽量不受限制,应采用动态存储结构
【可采用的数据结构】
(1)采用链式存储结构实现(普通单链表,循环单链表,普通双项链表和双向循环链表中任选一种结构)。
(2)采用动态数组实现。
设计思路:
本题思路较为简单,将大数数存于一个数组里,每个元素存一个3位数,然后设计好数与数之间的乘法,已经将数存入数组的函数即可;
n 输入:(1)n=20,
n 输出:n!=2432902008176640000
n 输入:(2)n=30,
n 输出:n!=265252859812191058636308480000000
////////////////////////////////////////////////////////////////////////////////////////////
源码:
// test21.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream"
using namespace std;
int trans(int b[],int a);
int mult(int *b,int l,int *c,int n);
void OutPut(int b[],int k);
int add(int b[],int k);
int main(int argc, char* argv[])
{
int c[60];memset(c,0,60);
int i(1);int L=trans(c,i);//////将i存入c中
int b[60];memset(b,0,60);
int sum(1);int k=trans(b,sum);//////把sum存入b中
int n;cin>>n;
while(n--)
{
k=mult(b,k,c,L);//sum=i*sum
L=add(c,L);//i++
}
OutPut(b,k);
return 0;
}
int trans(int b[],int a)//////////把a存入b中
{
int i=0;
memset(b,0,60);
while(a!=0)
{
b[i++]=a%1000;
a=a/1000;
}//////////////////////////////////每三位存入数组b中
return i;////b的位数(3个3个的)
}
int mult(int *b,int l,int *c,int n)//l为b的长度
{
int s[60];memset(s,0,60);
for(int j=0;j<n;j++)/////////////////////////c
{
for(int i=0;i<l;i++)///////////////b
{
s[i+j]+=b[i]*c[j];////s【k】:b中第i+j位的数之和
}
}
int max=n+l-1;//当前长度
for(int i=0;i<max;i++)
{
b[i]=s[i];
}
for (int k=0;k<max;k++)///////////////////////进位操作
{
if (b[k]>999)
{
int s=b[k]/1000;
b[k]%=1000;
b[k+1]+=s;
}
}
if(b[max]!=0) ++max;
return max;
}
void OutPut(int b[],int k)//输出结果
{
for(int i=0;i<k;i++)
{
if(i==0) cout<<b[k-i-1];//首位不输出0
else
{
if(b[k-i-1]>=100) cout<<b[k-i-1];//三位数
else if(b[k-i-1]<100&&b[k-i-1]>9) cout<<'0'<<b[k-i-1];//两位数
else cout<<'0'<<'0'<<b[k-i-1];//一位数
}
}
cout<<endl;
}
int add(int b[],int k)
{
b[0]+=1;
int temp=0;
while(b[temp]>999)//进位,注意进位后b【i】=0的情况
{
int s=b[temp]/1000;
b[temp++]%=1000;
b[temp]+=s;
}
++temp;
return (k>temp? k:temp);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
题目2:
题目:表达式求值
v 要求:实现关键
§ 栈的使用
§ 两位数以上、负数、小数点?
v 实现方式
§ 控制台程序
§ MFC对话框
设计思路:
参照课本上把中缀表达式改为后缀表达式输出的方法,略作改进,运用两个栈,一个符号栈(char型),存储运算符,一个数字栈,存储数字(设为double型);接着解决输入的问题,本程序运用了一个二维数组,以便暂时存储double型数字和运算符(刚开始二者均为char型,主要是为了方便解决浮点中小数点的输入以及存储问题),然后取每次输入的第一个字符,若为数字,则运用atof()函数将字符串转换为浮点数,将其压人数字栈中;若为运算符,则根据isp()函数和icp()函数进行判断是将其压人字符栈中还是进行运算(从数据栈中退出2个数据,根据运算符进行运算,然后将运算结果压人栈中);重复以上步骤,直至字符栈为空,最后取数据栈内数据,此即为最终的运算结果,输出即可。
测试数据:
7.342-(3.2343+4.2323)*6/5=;
逐个输入字符,如下图
输出结果:
运行正确!!!
源码//////////////////////////////////////////////////////////////////////////////////////////////////////r.cpp
#include "stdafx.h"
#include "LinkedStack.h"
#include "iostream"
using namespace std;
int isp(char ch);
int icp(char ch);
int main(int argc, char* argv[])
{
char p[20][30];/////二维数组,p【i】(i<20)表示一个字符串
cout<<"请输入要计算的算式:"<<endl;
cin>>p[0];
int i(0);
while(p[i][0]!='=' && i<20)
{
cin>>p[++i];
}
cout<<"中缀表示为:"<<endl;
for(int j=0;j<i;j++)
{
cout<<p[j];
}
cout<<endl;
LinkedStack<char> s1;/////////////char型栈,储存运算符
LinkedStack<double> s2;///////////////double型栈,储存数字
char ch='=';///////相当于一个输入的终止符
s1.Push(ch);
char ch1,op;
int k=0;
while(s1.IsEmpty()==false )
{
ch=p[k][0];///////////////////////取输入字符串的数字符,以便判断它是数字还是运算符
if(isdigit(ch))////如果是数字,则压人double栈s2
{
double x=atof(p[k]);
s2.Push(x);
k++;/////进入下一个字符串的判断
}
else/////如果是运算符
{
s1.getTop(ch1);
if(isp(ch1)<icp(ch))
{ s1.Push(ch);k++;}
else if(isp(ch1)>icp(ch))
{
s1.Pop(op);
s2.DoOperator(op);
}
else
{
s1.Pop(op);
if(op=='(')
{
k++;
}
}
}
}
double x;
s2.getTop(x);
cout<<"最终结果为:"<<x<<endl;
return 0;
}
int isp(char ch)
{
if(ch=='=')return 0;
else if(ch=='(') return 1;
else if(ch=='*' || ch=='/' || ch=='%') return 5;
else if(ch=='+' ||ch=='-') return 3;
else if(ch==')') return 6;
else cout<<ch;
}
int icp(char ch)
{
if(ch=='=')return 0;
else if(ch=='(') return 6;
else if(ch=='*' || ch=='/' || ch=='%') return 4;
else if(ch=='+' ||ch=='-') return 2;
else if(ch==')') return 1;
else cout<<ch;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
注意到以上程序的输入比较麻烦,每输入一个数都要换行,可做一些改进,改进后运行如下:
改进后的代码如下:
// test12.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream"
using namespace std;
#include "LinkedStack.h"
int isp(char ch)
{
if(ch=='=')return 0;
else if(ch=='(') return 1;
else if(ch=='*' || ch=='/' || ch=='%') return 5;
else if(ch=='+' ||ch=='-') return 3;
else if(ch==')') return 6;
else cout<<ch;
}
int icp(char ch)
{
if(ch=='=')return 0;
else if(ch=='(') return 6;
else if(ch=='*' || ch=='/' || ch=='%') return 4;
else if(ch=='+' ||ch=='-') return 2;
else if(ch==')') return 1;
else cout<<ch;
}
int main(int argc, char* argv[])
{
char ch[50];char ch1='=',op;
LinkedStack<char> s1;/////////////char型栈,储存运算符
LinkedStack<double> s2;///////////////double型栈,储存数字
cout<<"请输入中缀表达式:";
cin>>ch;
s1.Push(ch1);
while(!s1.IsEmpty())
{
int n=strlen(ch);///////////////////为字符时可能还要用到n
if (isdigit(ch[0]))
{
double x=atof(ch);
s2.Push(x);
int i(0);
while(isdigit(ch[i]) || ch[i]=='.')//是数字就被后面的覆盖
{
for(int j(0);j<n;j++)
{
ch[j]=ch[j+1];
}
n--;
}
}
else/////如果是运算符
{
s1.getTop(ch1);
if(isp(ch1)<icp(ch[0]))
{
s1.Push(ch[0]);
for(int j(0);j<n;j++)
{
ch[j]=ch[j+1];
}
n--;
}
else if(isp(ch1)>icp(ch[0]))
{
s1.Pop(op);
s2.DoOperator(op);
}
else
{
s1.Pop(op);
if(op=='(')
{
for(int j(0);j<n;j++)
{
ch[j]=ch[j+1];
}
n--;
}
}
}
}
double x;
s2.getTop(x);
cout<<"最终结果为:"<<x<<endl;
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
考虑到为了便于操作,可用MFC程序做出来:
输入:7.324-(3.2343+4.2323)*6/5=
输出:-1.635920
验证程序如下,运行结果正确:
实现该功能的代码段如下:
/////////////////////////////////////////////////////////////////////////////////////////////////////////LinkedStack.h
以上几个程序均用到了我改进了的一个栈,代码如下:
// testDlg.cpp : implementation file
//
#include "stdafx.h"
#include "test.h"
#include "testDlg.h"
#include "LinkedStack.h"
#include "iostream"
#include "string.h"
using namespace std;
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About
class CAboutDlg : public CDialog
{
public:
CAboutDlg();
// Dialog Data
//{{AFX_DATA(CAboutDlg)
enum { IDD = IDD_ABOUTBOX };
//}}AFX_DATA
// ClassWizard generated virtual function overrides
//{{AFX_VIRTUAL(CAboutDlg)
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV support
//}}AFX_VIRTUAL
// Implementation
protected:
//{{AFX_MSG(CAboutDlg)
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
//{{AFX_DATA_INIT(CAboutDlg)
//}}AFX_DATA_INIT
}
void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CAboutDlg)
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
//{{AFX_MSG_MAP(CAboutDlg)
// No message handlers
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CTestDlg dialog
CTestDlg::CTestDlg(CWnd* pParent /*=NULL*/)
: CDialog(CTestDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CTestDlg)
// NOTE: the ClassWizard will add member initialization here
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CTestDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CTestDlg)
// NOTE: the ClassWizard will add DDX and DDV calls here
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CTestDlg, CDialog)
//{{AFX_MSG_MAP(CTestDlg)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
ON_WM_CTLCOLOR()
ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
ON_BN_CLICKED(IDC_BUTTON4, OnButton4)
ON_BN_CLICKED(IDC_BUTTON5, OnButton5)
ON_BN_CLICKED(IDC_BUTTON6, OnButton6)
ON_BN_CLICKED(IDC_BUTTON9, OnButton9)
ON_BN_CLICKED(IDC_BUTTON8, OnButton8)
ON_BN_CLICKED(IDC_BUTTON7, OnButton7)
ON_BN_CLICKED(IDC_BUTTON10, OnButton10)
ON_BN_CLICKED(IDC_BUTTON11, OnButton11)
ON_BN_CLICKED(IDC_BUTTON12, OnButton12)
ON_BN_CLICKED(IDC_BUTTON13, OnButton13)
ON_BN_CLICKED(IDC_BUTTON14, OnButton14)
ON_BN_CLICKED(IDC_BUTTON15, OnButton15)
ON_BN_CLICKED(IDC_BUTTON16, OnButton16)
ON_BN_CLICKED(IDC_BUTTON17, OnButton17)
ON_BN_CLICKED(IDC_BUTTON18, OnButton18)
ON_BN_CLICKED(IDC_BUTTON19, OnButton19)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CTestDlg message handlers
BOOL CTestDlg::OnInitDialog()
{
CDialog::OnInitDialog();
// Add "About..." menu item to system menu.
// IDM_ABOUTBOX must be in the system command range.
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX < 0xF000);
CMenu* pSysMenu = GetSystemMenu(FALSE);
if (pSysMenu != NULL)
{
CString strAboutMenu;
strAboutMenu.LoadString(IDS_ABOUTBOX);
if (!strAboutMenu.IsEmpty())
{
pSysMenu->AppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
}
}
// Set the icon for this dialog. The framework does this automatically
// when the application's main window is not a dialog
SetIcon(m_hIcon, TRUE); // Set big icon
SetIcon(m_hIcon, FALSE); // Set small icon
// TODO: Add extra initialization here
return TRUE; // return TRUE unless you set the focus to a control
}
void CTestDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
CAboutDlg dlgAbout;
dlgAbout.DoModal();
}
else
{
CDialog::OnSysCommand(nID, lParam);
}
}
// If you add a minimize button to your dialog, you will need the code below
// to draw the icon. For MFC applications using the document/view model,
// this is automatically done for you by the framework.
void CTestDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // device context for painting
SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);
// Center icon in client rectangle
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
// Draw the icon
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialog::OnPaint();
}
}
// The system calls this to obtain the cursor to display while the user drags
// the minimized window.
HCURSOR CTestDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
////////以下是我自己添加的代码,以粗体显示:
char ch[50];char ch1='=',op;
LinkedStack<char> s1;/////////////char型栈,储存运算符
LinkedStack<double> s2;///////////////double型栈,储存数字
void CTestDlg::OnButton1() ////////777777777
{
// TODO: Add your control notification handler code here
strcat(ch,"7");
SetDlgItemText(IDC_STATIC1,ch);
}
HBRUSH CTestDlg::OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor)
{
HBRUSH hbr = CDialog::OnCtlColor(pDC, pWnd, nCtlColor);
// TODO: Change any attributes of the DC here
if(nCtlColor==CTLCOLOR_STATIC)
{
pDC->SetTextColor(RGB(0,0,0));
pDC->SetBkColor(RGB(247,255,246));//文字背景色
HBRUSH b=CreateSolidBrush(RGB(247,255,246));//控件背景色return b;
}
// TODO: Return a different brush if the default is not desired
return hbr;
}
void CTestDlg::OnButton2() /////////888888888
{
// TODO: Add your control notification handler code here
strcat(ch,"8");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton3() /////9999999999
{
// TODO: Add your control notification handler code here
strcat(ch,"9");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton4() //////44444444444
{
// TODO: Add your control notification handler code here
strcat(ch,"4");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton5() /////555555555
{
// TODO: Add your control notification handler code here
strcat(ch,"5");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton6() /////////66666666
{
// TODO: Add your control notification handler code here
strcat(ch,"6");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton9() ///////11111111
{
// TODO: Add your control notification handler code here
strcat(ch,"1");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton8()///////2222222222
{
// TODO: Add your control notification handler code here
strcat(ch,"2");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton7() ///////333333333
{
// TODO: Add your control notification handler code here
strcat(ch,"3");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton10() ///000000000
{
// TODO: Add your control notification handler code here
strcat(ch,"0");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton11() //////......
{
// TODO: Add your control notification handler code here
strcat(ch,".");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton12() //////++++++
{
// TODO: Add your control notification handler code here
strcat(ch,"+");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton13() //////- -
{
// TODO: Add your control notification handler code here
strcat(ch,"-");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton14() ////////// ****
{
// TODO: Add your control notification handler code here
strcat(ch,"*");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton15() /////// /
{
// TODO: Add your control notification handler code here
strcat(ch,"/");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton16() ////////<----<--删掉char数组最后一个字符
{
// TODO: Add your control notification handler code here
int n=strlen(ch);char cht[20];
for (int i(0);i<n-1;i++)
{
cht[i]=ch[i];
}
cht[i]='\0';
strcpy(ch,cht);
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton17() //////////((((((((((((
{
// TODO: Add your control notification handler code here
strcat(ch,"(");
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnButton18() //////)))))))
{
// TODO: Add your control notification handler code here
strcat(ch,")");
SetDlgItemText(IDC_STATIC1,ch);
}
int isp(char ch)
{
if(ch=='=')return 0;
else if(ch=='(') return 1;
else if(ch=='*' || ch=='/' || ch=='%') return 5;
else if(ch=='+' ||ch=='-') return 3;
else if(ch==')') return 6;
else cout<<ch;
}
int icp(char ch)
{
if(ch=='=')return 0;
else if(ch=='(') return 6;
else if(ch=='*' || ch=='/' || ch=='%') return 4;
else if(ch=='+' ||ch=='-') return 2;
else if(ch==')') return 1;
else cout<<ch;
}
void CTestDlg::OnButton19()//////////=====
{
// TODO: Add your control notification handler code here
strcat(ch,"=");
s1.Push(ch1);
while(!s1.IsEmpty())
{
int n=strlen(ch);///////////////////为字符时可能还要用到n
if (isdigit(ch[0]))
{
double x=atof(ch);
s2.Push(x);
int i(0);
while(isdigit(ch[i]) || ch[i]=='.')//是数字就被后面的覆盖
{
for(int j(0);j<n;j++)
{
ch[j]=ch[j+1];
}
n--;
}
}
else/////如果是运算符
{
s1.getTop(ch1);
if(isp(ch1)<icp(ch[0]))
{
s1.Push(ch[0]);
for(int j(0);j<n;j++)
{
ch[j]=ch[j+1];
}
n--;
}
else if(isp(ch1)>icp(ch[0]))
{
s1.Pop(op);
s2.DoOperator(op);
}
else
{
s1.Pop(op);
if(op=='(')
{
for(int j(0);j<n;j++)
{
ch[j]=ch[j+1];
}
n--;
}
}
}
}
double x;
s2.getTop(x);
char s[20];
sprintf(s, "%f", x);
strcpy(ch,s);
SetDlgItemText(IDC_STATIC1,ch);
}
void CTestDlg::OnCancel() /////清除
{
// TODO: Add extra cleanup here
strcpy(ch,"");
SetDlgItemText(IDC_STATIC1,ch);
// CDialog::OnCancel();
}
////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H
#include "iostream"
using namespace std;
template <class T>
class LinkedNode
{
public:
T data;
LinkedNode<T> *link;
LinkedNode(LinkedNode<T> *ptr=NULL){ link=ptr;}
LinkedNode(T d,LinkedNode<T> *ptr=NULL){ data=d;link=ptr;}/////////////每次push插入操作都在表头进行
};
template <class T>
class LinkedStack
{
private:
LinkedNode<T> *top;
public:
LinkedStack():top(NULL){ }/////////////////////////空栈,附加头结点不占内存(不须new)
~LinkedStack(){ makeEmpty();}
void makeEmpty()
{
LinkedNode<T> *p;
while(top!=NULL)
{
p=top;
top=top->link;
delete p;
}
}
void Push(T x)
{
top=new LinkedNode<T>(x,top);
if(top==NULL) { cerr<<" 存储分配失败!"<<endl;}
}
bool Pop(T& x)
{
if(IsEmpty()==true) return false;
LinkedNode<T> *p=top;
x=p->data;
top=top->link;
delete p;
return true;
}
bool IsEmpty()const {return top==NULL?true:false;}
bool getTop(T &x)
{
if(top==NULL) return false;
x=top->data;
return true;
}
//////////////////////////////////////////////////////////////////////////////////////////////////
void DoOperator(char op)//////////////////////////////////一op为运算符计算,并将结果压栈
{
double left,right,value;int result;
result=get2Operands(left,right);
if(result==true)
{
switch(op)
{
case '+':
value=left+right;Push(value);
break;
case '-':
value=left-right;Push(value);
break;
case '*':
value=left*right;Push(value);
break;
case '/':
if(right==0.0)
{
cerr<<"Divide by 0!"<<endl;
Clear();
}
else
{
value=left/right;
Push(value);
}
break;
}
}
else
Clear();
}
void Clear()
{
makeEmpty();
}
bool get2Operands(double &left,double &right)//取左右操作数
{
if(IsEmpty()==true)
{
cerr<<"缺少右操作数"<<endl;return false;
}
Pop(right);
if(IsEmpty()==true)
{
cerr<<"缺少左操作数"<<endl;return false;
}
Pop(left);
return true;
}
void AddOperand(double value)//将结果压栈
{
Push(value);
}
};
#endif
///////////////////////////////////////////////////////////////////////////////////////////////////
3.题目:
v 题目:二叉树基本算法的实现
v 功能要求:
v 键盘输入二叉树结点序列,创建一棵二叉树
v 实现SwapTree方法,以根结点为参数,交换每个结点的左子树和右子树(提示:前序递归)
v 实现Find方法,查找值为key的结点,并输出该结点的所有祖先结点
v 你可以选择:
v 对BinaryTree模板进行功能扩充;
v 自己定义并实现二叉树类
v 要求键盘输入二叉树结点序列
v 结点序列可以是前序,也可以是层次
v 空结点以#表示
设计思路:
首先,运用递归的方法,按前序输入建立一棵二叉树,接着,运用类似交换两变量值的方法,交换根结点的左右子树,实现SwapTree方法;然后,通过前序遍历,找到值为key的结点,并实现parent函数,用到一个栈,实现parent结点的逆序输出,即可输出该节点的所有祖先结点。
前序输入:abdk###e##cf##g##
交换前输出:abdkecfg
交换后输出:acfgbdke
测试程序如下:
//////////////////////////////////////////////////////////////////////////////////////////////////////////////.cpp
#include "stdafx.h"
#include "BinaryTree.h"
#include "iostream"
using namespace std;
template <class T>
void CreateBinTree(BinTreeNode<T> *& subTree)///键盘输入二叉树结点序列,创建一棵二叉树
{
T item;
cin>>item;
if(item!='#')
{
subTree=new BinTreeNode<T>(item);
CreateBinTree(subTree->leftChild);
CreateBinTree(subTree->rightChild);
}
}
template <class T>
void SwapTree(BinTreeNode<T> *& subTree)///////SwapTree方法
{
BinTreeNode<T>* t;
t=subTree->rightChild;
subTree->rightChild=subTree->leftChild;
subTree->leftChild=t;
}
int main(int argc, char* argv[])
{
BinaryTree<char> b;
cout<<"前序建立一棵二叉树:"<<endl;
CreateBinTree(b.root);////////用前序遍历建立二叉树
cout<<"前序输出:";
b.preOrder();
cout<<endl;
SwapTree(b.root);///////////////////交换左右子树
cout<<"交换后前序输出:";
b.preOrder();////////////////////交换后再输出一遍,便于检验是否有误
cout<<endl;
cout<<"请输入要查找的节点:";
char ch; cin>>ch;
cout<<ch<<"的祖先节点:";
b.Find(b.root,ch);
cout<<endl;
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
源码:
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include "iostream"
#include "LinkedStack.h"
using namespace std;
template <class T>
class BinTreeNode
{
public:
T data;
BinTreeNode<T> *leftChild,*rightChild;
BinTreeNode(T d,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL):data(d),leftChild(l),rightChild(r){}
};
template <class T>
class BinaryTree
{
protected:
T RefValue;
public:
BinTreeNode<T> *root;
BinaryTree():root(NULL){}
BinaryTree(T value):RefValue(value),root(NULL){}
~BinaryTree(){ destroyTree(root);}
void preOrder(){ preOrder(root);}
bool IsEmpty(){ return root==NULL? false:true;}
void visit(BinTreeNode<T> *subTree)
{
cout<<subTree->data<<" ";
}
private:
void preOrder(BinTreeNode<T> *subTree)
{
if(subTree!=NULL)
{
cout<<subTree->data<<" ";
preOrder(subTree->leftChild);
preOrder(subTree->rightChild);
}
}
void destroyTree(BinTreeNode<T> *subTree)
{
if(subTree!=NULL)
{
destroyTree(subTree->leftChild);
destroyTree(subTree->rightChild);
delete subTree;
}
}
public:
//求父亲节点
BinTreeNode<T>* parent(BinTreeNode<T>* subTree)
{
LinkedStack<BinTreeNode<T>*> s;
BinTreeNode<T>* q=root;
s.Push(NULL);
while(q!=NULL)
{
if(q->leftChild==subTree || q->rightChild==subTree)
{
cout<<q->data<<" ";///////输出祖先结点
return q;
}
else
{
if(q->rightChild!=NULL)
s.Push(q->rightChild);
if(q->leftChild!=NULL)
q=q->leftChild;
else
s.Pop(q);
}
}
cout<<"输出不成功!"<<endl;
return NULL;
}
//找key
void Find(BinTreeNode<T>* subTree,const T& key)///用类似后序遍历的方法找到值为key的结点
{
LinkedStack<BinTreeNode<T>*> s;
BinTreeNode<T>*p=subTree;
s.Push(NULL);
while(p!=NULL)
{
if(p->data==key)
{
// cout<<"查找成功!"<<endl;
break;
}
else
{
if(p->rightChild!=NULL)
s.Push(p->rightChild);
if(p->leftChild!=NULL)
p=p->leftChild;
else
s.Pop(p);
}
}
while(p!=root)
{
p=parent(p);
}
}
};
#endif
////////////////////////////////////////////////////////////////////////////////////////
4.
v 任务:输入一棵二叉树的前序遍历序列和中序遍历序列,重构这棵二叉树
v 功能要求:
Ø 在题目一的基础之上,增加一个方法,重构这棵二叉树
Ø 要求以图示效果,层次输出这棵二叉树
设计思路:
题目要求在题目一的基础上增加一个方法,重构二叉树,可以输入二叉树的后序遍历和中序遍历,然后根据后序和中序序列建立二叉树。最后,用到一个队列,层次输出此二叉树。
后序输入:DBFCA
输出:BDACF
层次输出:ABCDF
测试程序如下:
#include "stdafx.h"
#include "BinaryTree.h"
int main(int argc, char* argv[])
{
char ch1[20],ch2[20];
cout<<"请输入后序遍历:"<<endl;
cin>>ch1;
cout<<"请输入中序中序:"<<endl;
cin>>ch2;
cout<<"建立此树:"<<endl;
BinaryTree<char> B;
int n=strlen(ch1);
B.CreateTree(B.root,ch1,ch2,n);
cout<<"前序输出:"<<endl;
B.preOrder();
cout<<endl<<"中序输出:"<<endl;
B.InOrder(B.root);
cout<<endl;
cout<<"层次输出:";
B.levelOrder();
cout<<endl;
return 0;
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include "iostream"
#include "LinkedQueue.h"
using namespace std;
template <class T>
class BinTreeNode
{
public:
T data;
BinTreeNode<T> *leftChild,*rightChild;
// BinTreeNode():leftChild(NULL),rightChild(NULL){}
BinTreeNode(T d,BinTreeNode<T> *l=NULL,BinTreeNode<T> *r=NULL):data(d),leftChild(l),rightChild(r){}
};
template <class T>
class BinaryTree
{
protected:
T RefValue;
public:
BinTreeNode<T> *root;
BinaryTree():root(NULL){}
BinaryTree(T value):RefValue(value),root(NULL){}
~BinaryTree(){ destroyTree(root);}
void preOrder(){ preOrder(root);}
bool IsEmpty(){ return root==NULL? false:true;}
private:
void preOrder(BinTreeNode<T> *subTree)
{
if(subTree!=NULL)
{
cout<<subTree->data<<" ";
preOrder(subTree->leftChild);
preOrder(subTree->rightChild);
}
}
void destroyTree(BinTreeNode<T> *subTree)
{
if(subTree!=NULL)
{
destroyTree(subTree->leftChild);
destroyTree(subTree->rightChild);
delete subTree;
}
}
public:
int Index(T key,T *y)////////返回key在中序数组y中的下标
{
int n=strlen(y);
for(int j=0;j<n;j++)
{
if(y[j]==key)
return j;
}
cout<<"查无此值!"<<endl;/////增加此句,方便调试
return 0;
}
void InOrder(BinTreeNode<T>*p)////////////////中序输出
{
if(p!=NULL)
{
InOrder(p->leftChild);
cout<<p->data<<" ";
InOrder(p->rightChild);
}
}
void levelOrder()
{
LinkedQueue<BinTreeNode<T>*> q;
BinTreeNode<T>*p=root;
q.EnQueue(p);
while(q.IsEmpty()==false)
{
q.DeQueue(p);
cout<<p->data<<" ";
if(p->leftChild!=NULL)
q.EnQueue(p->leftChild);
if(p->rightChild!=NULL)
q.EnQueue(p->rightChild);
}
}
void Insert(BinTreeNode<T> *&p,T* x,T* y,int i)//把x【i】插入树中(类似二叉树的插入)
{
if(p==NULL)
{
p=new BinTreeNode<T>(x[i]);
}
else
{
if(Index(x[i],y)<Index(p->data,y) )
{
Insert(p->leftChild,x,y,i);
}
else
{
Insert(p->rightChild,x,y,i);
}
}
}
void CreateTree(BinTreeNode<T> *&p,T* x,T* y,int n)////n为后序数组长度
{
for(int i=n-1;i>=0;i--)
{
Insert(p,x,y,i);
}
}
};
#endif
5.
//////////////////////////////////////////////////////////////////////////////////////////////////////
最优二叉树
v 基本要求:对Huffman树的方法进行扩充,实现如下功能:
v 1)键盘输入一个字符串,统计每个字符出现的频率;
v 2)输出每个字符的Huffman编码
v 3)计算并输出WPL
v 提高要求:改键盘输入为读文件(任何类型)
设计思路:
1.先建一个链表:输入一段字符串,将其放入链表中,删除重复节点(data相同)并统计各个节点频率(存入count中),将链表按各节点count的大小排序(按小到大顺序);
2.建huffman树:
(1).将链表前两元素合并,建成一颗小树(小树中,令左节点code=0,右节点code=1),删去表中前两元素,将小树根节点插入链表中(按count大小顺序)
(2).循环操作1,直至表中只剩下一个节点
3.输出编码:
根据parent指针找到节点的祖先节点,然后逆序输出其code值,此即为节点的编码
4.求WPL:
根据parent指针求节点的深度h,然后每个节点的h+1之和除以节点数即为该树的成功搜索长度
//////////////////////////////////////////////////////////////////////////////////////////////////////////////源码//////源码//////源码//////源码//////源码//////源码//////源码//////源码
#include "stdafx.h"
#include "iostream"
#include "HuffmanTree.h"
using namespace std;
int main(int argc, char* argv[])
{
char ch[30];
cout<<"请输入一段字符串:";
cin>>ch;
HuffmanTree<char> H;
H.InputHuffmanTree(ch);
H.Count();
H.Sort();
H.Frequency();
H.Output();
H.Build();
H.levelOrder();
H.levelOrder1();
H.WPL();
return 0;
}
////////************************************************************************
#ifndef HUFFMANTREE_H
#define HUFFMANTREE_H
#include "LinkedQueue.h"
#include "LinkedStack.h"
template<class T>
struct Node
{
T data;///字符
float count;//////频率
bool code;//////////编码
Node<T> *leftChild,*rightChild,*parent;
// Node(Node<T>* l=NULL,Node<T>* r=NULL,Node<T>* ptr=NULL):leftChild(l),rightChild(r),parent(ptr){}
Node(T d,float cnt=1.0,bool co=0,Node<T>* l=NULL,Node<T>* r=NULL,Node<T>* ptr=NULL):data(d),count(cnt),code(co),
leftChild(l),rightChild(r),parent(ptr){}
};
template <class T>
class HuffmanTree
{
public:
HuffmanTree(){ root=new Node<T>('#'); }
~HuffmanTree(){ makeEmpty(root);}
/////////前插法建立链表//////前插法建立链表//////前插法建立链表(尚未对其排序)
void InputHuffmanTree(T *ch)
{
int i(0),n=strlen(ch);
while(i<n)
{
Node<T> *newNode=new Node<T>(ch[i]);
if(newNode==NULL){ cerr<<"存储分配有误!"<<endl; break;}
newNode->parent=root->parent;
root->parent=newNode;
i++;
}
}
///////统计各节点的code值//统计各节点的code值//统计各节点的code值中(下一步就是根据code大小进行排序)
void Count()
{
Node<T>*p=root->parent,*q=NULL;
while(p!=NULL)
{
q=p->parent;
while(q!=NULL)
{
if(p->data==q->data)
{
p->count+=1;
Delete(q);
}
q=q->parent;
}
p=p->parent;
}
}
/////删去链表中的ptr所指向的节点(不是删除,因为在此程序中主调函数中还要用到ptr),这只是让这个节点脱离这个链表,而非广义上的删除
void Delete(Node<T>* ptr)
{
Node<T>*pre=root->parent;
while(pre->parent!=ptr)
{
pre=pre->parent;
}
pre->parent=ptr->parent;
// delete ptr;
ptr=pre;
}
/////建树///建树///建树///建树///建树///建树
void Build()
{
Node<T> *p=root->parent;
while(p->parent!=NULL)
{
merge();
p=root->parent;
}
}
void Sort()
{
Node<T> *p=root->parent,*q=p->parent,*r;
while(p!=NULL)
{
r=p;
q=p->parent;
while(q!=NULL)
{
if(r->count>q->count)
r=q;
q=q->parent;
}
if(p!=r) swap(p,r);
p=p->parent;
}
}
void Output()
{
cout<<"各字符出现的频率是:"<<endl;
Node<T>*p=root->parent;
while(p!=NULL)
{
cout<<p->data<<":"<<p->count<<endl;
p=p->parent;
}
}
void Frequency()//计算各节点出现频率
{
Node<T>* p=root->parent;int sum(0);
while(p!=NULL)
{
sum+=p->count;
p=p->parent;
}
p=root->parent;
while(p!=NULL)
{
p->count=p->count/sum;
p=p->parent;
}
}
void levelOrder1()
{
LinkedQueue<Node<T>*> Q;
Node<T>*p=root->parent;
Q.EnQueue(p);
LinkedStack<Node<T>*> s;
while(Q.IsEmpty()==false)
{
Q.DeQueue(p);
if(p->leftChild==NULL && p->rightChild==NULL)
{
cout<<p->data<<"的编码是:";
while(p->parent!=NULL)
{
// cout<<p->code;
s.Push(p);
p=p->parent;
}
while(s.IsEmpty()==false)
{
s.Pop(p);
cout<<p->code;
}
cout<<endl;
}
else///////注意到此情况与上面的情况不可能同时发生,若无此句,则由于p被上一句改变会出现错误
{
if(p->leftChild!=NULL)
Q.EnQueue(p->leftChild);
if(p->rightChild!=NULL)
Q.EnQueue(p->rightChild);
}
}
}
//*
void levelOrder()/////层次输出///使用层次输出,便于在调试时观察变化
{
cout<<"按层次输出huffman树:";
LinkedQueue<Node<T>*> Q;
Node<T>*p=root->parent;
Q.EnQueue(p);
while(Q.IsEmpty()==false)
{
Q.DeQueue(p);
cout<<p->data<<" ";
if(p->leftChild!=NULL)
Q.EnQueue(p->leftChild);
if(p->rightChild!=NULL)
Q.EnQueue(p->rightChild);
}
cout<<endl;
}
void WPL()
{
LinkedQueue<Node<T>*> Q;
Node<T>*p=root->parent;
Q.EnQueue(p);double sum(0);int n(0);
while(Q.IsEmpty()==false)
{
Q.DeQueue(p);
if(p->leftChild==NULL && p->rightChild==NULL)
{
int val(1);n++;
while(p->parent!=NULL)
{
val++;
p=p->parent;
}
sum+=val;
}
else///////注意到此情况与上面的情况不可能同时发生,若无此句,则由于p被上一句改变会出现错误
{
if(p->leftChild!=NULL)
Q.EnQueue(p->leftChild);
if(p->rightChild!=NULL)
Q.EnQueue(p->rightChild);
}
}
double d=sum/n;
cout<<"WPL值为:"<<d<<endl;
}
protected:
Node<T>* root;
void DeleteFirst()//////删去链表的第一个节点,在本程序中即值最小的节点,注意此时被删节点的parent指针所指向的仍然未变
{
Node<T> *p=root->parent;
root->parent=p->parent;
}
void Insert(Node<T>*ptr)//////之前的序列已经排好了序,从小到大(按count的大小)
{
Node<T>*p=root->parent,*pre=root;
if(p!=NULL)////注意到最后一个根节点插入时,root->parent=NULL
{
while(p->count<ptr->count)
{
pre=p;
p=p->parent;
if(p==NULL)
break;
}
}
pre->parent=ptr;
ptr->parent=p;
}
void merge()//////取前两个节点合并成树,从表中去掉这两个节点,然后将根节点按顺序大小插入入表中
{
Node<T>*p,*p1,*p2;
p1=root->parent;p2=p1->parent;
float d=p1->count+p2->count;
p=new Node<T>('#',d);
DeleteFirst();
DeleteFirst();
p1->parent=p;////勿忘此句,同时注意此句必须在DeleteFirst()语句之后
p2->parent=p;////勿忘此句,同时注意此句必须在DeleteFirst()语句之后
p->leftChild=p1;
p->rightChild=p2;
p1->code=0;
p2->code=1;
Insert(p);
}
void swap(Node<T>*p,Node<T>*r)//////注意,此处可能需要扩充////注意,此处可能需要扩充////注意,此处可能需要扩充
{
Node<T> *q=new Node<T>('#');///////////////////////////////
q->count=r->count;q->data=r->data;//q=r;
r->count=p->count;r->data=p->data;//r=p;
p->count=q->count;p->data=q->data;//p=q;
}
void makeEmpty(Node<T>* p)
{
if(p!=NULL)
{
makeEmpty(p->leftChild);
makeEmpty(p->rightChild);
delete p;
}
}
};
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////////
6.
n 要求:自己设计图并编码进行存储,同时输出图的两种遍历方式的结果。
n 实现关键
¨ 图的存储方式的选择
¨ 图的遍历算法
n 实现方式
¨ 控制台程序
¨ 输出图的两种遍历方式的结果
设计思路:
此题所要求的是图的最基本设计要求,较为简单,只需按照图的相关要求写好代码即可.
////////////////////////////////////////////////////////////////////////////////////////////////
源码:
// 图6.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream.h"
#include "Graphmtx.h"
#include "Graphlnk.h"
int main(int argc, char* argv[])
{
int i;
cout<<" 1、图的邻接矩阵存储方式 "<<endl;
cout<<" 2、图的邻接表存储方式 "<<endl;
cout<<endl;
cout<<"请输入你的选择(1或2):";
cin>>i; cout<<"请输入你的选择:";
cin>>i;
switch (i)
{
case 1:
Graphmtxcin();break;
case 2:
Graphlnkcin();break;
}
return 0;
}
*******************************************************************************
#include "stdlib.h"
template<class T,class E>
struct Edge
{
int dest;
E cost;
Edge<T, E> *link;
Edge () {}
Edge (int num, E weight)
: dest (num), weight (cost), link (NULL) { }
bool operator != (Edge<T, E>& R) const
{ return (dest != R.dest;)?true:false }
};
template <class T, class E>
struct Vertex
{
T data;
Edge<T, E> *adj;
};
template <class T, class E>
class Graphlnk
{
public:
Vertex<T, E> *NodeTable;
int getVertexPos(const T vertx)
{
for (int i = 0; i <numVertices; i++)
{
if (NodeTable[i].data == vertx)
return i;
}
return -1;
}
Graphlnk (int sz = DefaultVertices);
~Graphlnk();
T getValue (int i)
{
return (i >= 0 && i <numVertices) ?
NodeTable[i].data:0;
}
bool insertVertex (const T& vertex);
bool insertEdge (int v1, int v2, E weight);
int getFirstNeighbor (int v);
int getNextNeighbor (int v, int w);
int NumberOfEdges(){return numEdges;}
int NumberOfVertices(){return numVertices;}
int maxVertices;
int numEdges;
int numVertices;
};
template<class T, class E>
Graphlnk<T,E>::Graphlnk (int sz)
{
maxVertices = sz;
numVertices = 0; numEdges = 0;
NodeTable = new Vertex<T, E>[maxVertices];
if (NodeTable == NULL)
{ cerr<<"存储分配错!"<<endl; exit(1); }
for (int i = 0; i < maxVertices; i++)
{ NodeTable[i].adj = NULL;}
};
template <class T,class E>
Graphlnk<T,E>::~Graphlnk()
{
for (int i = 0; i < numVertices; i++ )
{
Edge<T,E> *p=NodeTable[i].adj;
while (p != NULL)
{
NodeTable[i].adj=p->link;
delete p; p=NodeTable[i].adj;
}
}
delete [ ]NodeTable;
};
template <class T,class E>
int Graphlnk<T,E>::getFirstNeighbor (int v)
{
if (v != -1)
{
Edge<T,E> *p=NodeTable[v].adj;
if (p!=NULL) return p->dest;
}
return -1;
};
template <class T, class E>
int Graphlnk<T, E>::getNextNeighbor (int v, int w)
{
if (v != -1)
{
Edge<T,E> *p=NodeTable[v].adj;
while (p != NULL && p->dest != w)
p=p->link;
if (p!=NULL&&p->link!=NULL)
return p->link->dest;
}
return -1;
};
template<class T,class E>
bool Graphlnk<T,E>::insertVertex(const T& vertex)
{
if (numVertices==maxVertices)
{
return false;
}
NodeTable[numVertices].data=vertex;
numVertices++;
return true;
};
template<class T,class E>
bool Graphlnk<T,E>::insertEdge(int v1,int v2,E weight)
{
if (v1>=0&&v1<numVertices&&v2>=0&&v2<numVertices)
{
Edge<T,E> *q,*p=NodeTable[v1].adj;
while(p!=NULL&&p->dest!=v2) p=p->link;
if (p!=NULL) return false;
p=new Edge<T,E>;q=new Edge<T,E>;
p->dest=v2;p->cost=weight;
p->link=NodeTable[v1].adj;
NodeTable[v1].adj=p;
q->dest=v1;q->cost=weight;
q->link=NodeTable[v2].adj;
NodeTable[v2].adj=q;
numEdges++;
return true;
}
return 0;
};
template<class T, class E>
void DFS(Graphlnk<T, E>& G, const T& v)
{
int i,loc,n;
n=G.NumberOfVertices();
bool *visited=new bool[n];
for (i = 0; i< n;i++) visited[i]=false;
loc=G.getVertexPos(v);
DFS (G,loc,visited);
delete [] visited;
}
template<class T, class E>
void DFS(Graphlnk<T, E>& G, int v, bool visited[])
{
cout<<G.getValue(v)<<" ";
visited[v]=true;
int w=G.getFirstNeighbor(v);
while(w!=-1)
{
if(!visited[w])
{DFS(G,w,visited);}
w=G.getNextNeighbor(v,w);
}
}
template <class T, class E>
void BFS(Graphlnk<T, E>& G, const T& v) {
int i,w;
int n = G.NumberOfVertices();
bool *visited = new bool[n];
for (i = 0; i < n; i++)
{
visited[i] = false;
}
int loc = G.getVertexPos (v);
cout << G.getValue (loc) <<" ";
visited[loc] = true;
SeqQueue<int> Q; Q.EnQueue (loc);
while (!Q.IsEmpty())
{
Q.DeQueue (loc);
w = G.getFirstNeighbor (loc);
while (w != -1)
{
if (!visited[w])
{
cout << G.getValue (w) <<" ";
visited[w] = true;
Q.EnQueue (w);
}
w = G.getNextNeighbor (loc, w);
}
}
delete [] visited;
}
void Graphlnkcin()
{
Graphlnk<char,int> G;
char a;
int i,j,k,n,m;
char e1,e2;int weight;
cout<<"请输入顶点个数:";cin>>n;
cout<<"请输入边的个数:";cin>>m;
cout<<"请输入各个顶点:";
for (i=0;i<n;i++)
{
cin>>e1;G.insertVertex(e1);
}
i=0;
cout<<"请输入两个顶点表示的边及权值:";
while(i<m)
{
cin>>e1>>e2>>weight;
cout<<" ";
j=G.getVertexPos(e1);k=G.getVertexPos(e2);
if (j==-1||k==-1)
{
cout<<"边两端信息有误,重新输入!"<<endl;
}
else
{ G.insertEdge(j,k,weight);i++; }
}
cout<<endl;
cout<<"请输入开始搜索的顶点:";
cin>>a;
cout<<"图的DFS输出:";
DFS(G,a);
cout<<endl;
cout<<"图的BFS输出:";
BFS(G,a);
cout<<endl;
}
////////////////////////////////////////////////////////////////////////////////////
实习感想
一直以来都觉得数据结构难学,难以掌握,虽然书看了很多遍,可一直感觉上面的知识都不是自己的,离开了书,自己什么都不能干.这次的实习却中,我感觉学到的课堂上的还要多,一开始感觉很累,写出来的代码要在计算机上调试一整天才能输出正确的结果,在调试的过程中,倒也总结了一点经验:
1,在把问题的各个细节想明白之前,最好不要贸然开始敲代码,这样极可能打断自己的思路,而且为后面的调试留下隐患;
2.尽量第一遍就把所有的代码完善,不要想着后面再做好,我常常因此而耗费大量时间
3.在调试过程中, 把握好程序执行的过程,先用一些简单的量模拟运行一遍,注意哪些量在变,哪些没有变,因某些量的变化会导致下一步的哪些东西的变化,这样可以提高调试的效率;
4. 每进行一次对类的对象(或指向该对象的指针)的操作时,千万要注意该对象以及该对象所处的数据结构(如顺序表size,,链表link,堆TOP指针等等)的各个成员(因此操作造成)的变化
总之,感觉自己在实习的过程中学到了很多,自己编程能力也有很大提升,希望将来学到更多的知识,而目前要做的就是脚踏实地,练好基本功,为将来做好准备.