第一篇:数据结构 吴亚峰 第二次作业
哈夫曼编码与解码的实现
一、设计思想
首先构建哈夫曼树,再去进行哈夫曼的译码,接着设计函数进行字符串的编码过程,最后进行哈夫曼编码的译码。
定义一个结构体,用于存放构建哈夫曼树所需要的所有变量,开辟一块地址空间,用于存放数组,数组中每个元素为之前定义的结构体。输入n个字符及其权值。
构建哈夫曼树:在上述存储结构上实现的哈夫曼算法可大致描述为:
第一步:初始化。将ht[ ]中2n-1个结点里的三个指针均置为空,权值置为0。
第二步:输入。读入n个叶子的权值存于向量的前n个分量中。它们是初始森林中n个孤立的根结点上的权值。
第三步:合并。对森林中的树共进行n-1次合并,所产生的新结点依次放入向量ht的第i个分量中。每次合并分两步: 在当前森林ht[0..i-1]的所有结点中,选取权最小和次小的两个根结点[s1]和 [s2]作为合并对象,这里0≤s1,s2≤i-1。将根为ht[s1]和ht[s2]的两棵树作为左右子树合并为一棵新的树,新树的根是新结点ht[i]。具体操作:
将ht[s1]和ht[s2]的parent置为i,将ht[i]的lchild和rchild分别置为s1和s2。新结点ht[i]的权值置为ht[s1]和ht[s2]的权值之和。
哈夫曼的编码:约定左子为0,右子为1,则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。
当用户输入字母时。就在已经找好编码的编码结构体中去查找该字母。查到该字母就打印所存的哈夫曼编码。接着就是完成用户输入0、1代码时把代码转成字母的功能。这是从树的头结点向下查找,如果当前用户输入的0、1串中是0则就走向该结点的左子。如果是1这就走向该结点的右结点,重复上面步骤。直到发现该结点属于输入了字母的结构体则打印该结构体的字母。重复上面步骤。直到找完用户输入0、1串为止。则就完成了程序所有的译码过程。
哈夫曼编码与解码的实现
三、源代码
#include
/* 数组头文件 */ #include
/* 定义长度 */ typedef struct{
/* 定义哈夫曼编码的结构数组 */
char data;
int weight;
/* 定义权值 */
int parent;
int lchild;
int rchild;}huffmannode;typedef struct{
/* 定义保存哈夫曼结构体 */
char bits[50];
int start;}huffmancode;void main(){
huffmannode ht[100];
/* 定义储存权值的空间 */
huffmancode cd[100];
char string[100];
/* 定义数组存储空间 */
char hcd[100];
int i,j,x,y,s1,s2,m1,m2,n,c,f,k;
printf(“please input the n=”);
/* 输入字符的个数 */
scanf(“%d”,&n);
printf(“n===============================n”);
for(i=0;i { getchar(); /* 获得输入的字符 */ printf(“please input the value :”); scanf(“%c”,&ht[i].data); /* 输入字符函数 */ printf(“please input the weight:”); scanf(“%d”,&ht[i].weight); } printf(“n=============================n”); for(i=0;i<2*n-1;i++) { ht[i].parent=ht[i].lchild=ht[i].rchild=-1;/* 初始化父结点,左右子结点 */ } for(i=n;i<2*n-1;i++) { s1=s2=0; /* 初始化变量 */ m1=m2=MAX; 哈夫曼编码与解码的实现 } printf(“n=============================n”); printf(“nPlease input the message:n”); scanf(“%s”,string); /* 输入字符串 */ for(i=0;string[i]!=' ';i++) { for(c=0;c<=n;c++) if(string[i]==ht[c].data)/* 寻找与输入字符相匹配的字母 */ { for(j=cd[c].start;j<=n;j++) printf(“%c”,cd[c].bits[j]); /* 输出字母代码 */ break; } } printf(“n=============================n”); printf(“Please input the HuffmanCode:n”); scanf(“%s”,hcd); /* 输入0、1代码 */ f=2*n-2; for(i=0;hcd[i]!=' ';i++) { if(hcd[i]=='0') /* 判断输入为0,寻找左子 */ f=ht[f].lchild; else if(hcd[i]=='1') f=ht[f].rchild; /* 判断输入为1,寻找右子 */ if(f { printf(“%c”,ht[f].data);/* 输出字符串 */ f=2*n-2; } } printf(“n”); getch();} 以上就是全部的源代码 哈夫曼编码与解码的实现 五、遇到的问题及解决 这部分我主要遇到了如下四个问题,其内容与解决方法如下所列: 问题1:怎样构造一棵哈夫曼树 解决方法:通过查阅书籍和资料,我知道构建哈夫曼树有以下几步: 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始化集合,就是F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步,直到集合F中只有一棵二叉树为止。问题2:怎么用哈夫曼树编码 解决方法:编码的结果就是使每一个字符的编码都与另一个字符编码的前一部分不同,不可能出现像a:00,b:001这种情况,这样就不会遇到莫棱两可的情况了。这是由二叉树的特点决定的,编码是由从根结点到一个叶子的路径决定的。不同的叶子对应的这种路径不可能出现像a:00,b:001这种情况。自己画了画二叉树图,就懂了。哈夫曼编码重要作用就是用最少的编码长度表示相同的内容,主要依据“频 率大的编码短,频率小的编码长”。问题3:如何解码的问题 解决方法:在编码时将得到的二进制码依次存入临时数组中,从叶子结点到根节点,记录0和1,每记录一次后移一位。最后就得到了二进制编码,解码时从前到后依次读取,最后就得到了字符串,也就完成了解码。问题4:for语句的使用 解决方法:在这个程序中用到了多个for语句,之前C语言学的不太到位。对for语句不能灵活运用,后来通过查阅书籍以及请教同学才使编程最后得以实现并最终能够运行。 六、心得体会 通过这次课程设计,让我对一个程序的数据结构有更全面更进一步的认识,根据不同的需求,采用不同的数据存储方式,不一定要用栈,二叉树等高级类型,有时用基本的一维数组,只要运用得当,也能达到相同的效果,甚至更佳,就如这次的课程设计,通过用for的多重循环,舍弃多余的循环,提高了程序的运行效率。在编写这个程序的过程中,我复习了之前学的基本语法,哈夫曼树最小路径的求取,哈夫曼编码及译码的应用范围,程序结构算法等一系列的问题它使我对数据结构改变了看法。当然,在这次设计过程中,跟上次一样,也遇到了很多难以解决的问题,通过看书以及请教同学才得到了解决。但是总感觉自己的基础实在是太薄弱了,之前的课程没有认真学习导致现在一个小问题都能纠结很久,这种感觉实在不好受。看着别人都轻松完成,自己却得回去看书,心里不是滋味,以后一定要更加努力更加认真才行啊。 1.(1)问题的描述:设计一个程序exp1-1.cpp,输出所有小于等于n(n为一个大于二的正整数)的素数。要求:(1)每行输出10个素数;(2)尽可能采用较优的算法。 (2)解决思想:判断一个整数n是否为素数,只需要用2~n-1之间的每一个整数去除,如果都不能被整除,那么m就是一个素数。其实可以简化,n不被被2~n-1之间的每一个整数去除,只需被2~根号n之间的每个数去除就可以了。因为如果n能被2~n-1之间任意整数整除,如果这个数大于根号m,那这个数必定对应的还有一个比根号m小的因子(3)源代码: #include cin>>n;if(n<=2) cout<<“输入错误”; else for(int i=2;i<=n;i++) { flag=0; for(int j=2;j<=(int)sqrt(i);j++) { if(i%j==0) { flag=1; break; } } if(flag==0) { cout< count++; if(count%10==0) cout< } } cout< } return 0;(4)运行结果截图 (5)心得体会:按照素数定义来判断素数时,可以进行一个较为明显的优化,即只需从2枚举到根n即可。 2.(1)问题的描述:编写一个程序exp1-2.cpp,计算任一输入的正整数的各位数字之和,并分析算法的时间复杂度。 (2)解决思想:采用递归的算法,对输入的正整数进行不断的取模运算和取商运算,即可得到该正整数的各位数字之和。时间复杂度为O(1)(3)源代码 exp1-2.cpp #include return 0;} else return n%10 + fun(n/10);} int main(){ int n; cout<<”请输入一个正整数:“; cin>>n; cout<<”各位数字之和是:“< (5)心得体会:当遇到一个复杂问题时,可以从最简单的地方着手,刚开始不知道n是几位数,感觉这个问题有点棘手,心想如果是二位数就好办了,因此脑海中浮现了“递归”的思想,把一个复杂问题转变成简单问题。即把一个正整数n边分解边累加,直到分解完毕。 3.(1)问题的描述:编写一个程序exp1-3.cpp,判断一个字符串是否为“回文”(顺读和倒读都一样的字符串称为“回文”),并分析算法的时间复杂度。 (2)解决思想:依次将字符串两端的字符进行比较,若都相同,则为回文字符串。时间复杂度为O(n)。(3)源代码: exp1-3.cpp #include int fun(char s[]){ int flag=1;int i,j,n=strlen(s); for(i=0,j=n-1;i if(s[i]!=s[j]) { flag=0; break; } return(flag);} int main(){ char s[MAX];cout<<”输入一串字符串:“;cin>>s;if(fun(s)==1) cout<<”字符串是回文“< cout<<”字符串不是回文"< (5)心得体会:如果将这题进行扩展,判断一个正整数是否为回文数,也可以采用类似的算法。将正整数的各位存到数组里,用i从左到右扫描s,用j从右到左扫描s,若s[i]与s[j]不相等,则退出循环,否则继续比较,直到i 数据结构实验报告二 题目: 用先序递归过程监理二叉树(存储结构:二叉链表) 输入数据按先序遍历输入,当某节点左子树或者右子树为空时,输入‘*’号,如输入abc**d**e**时,得到的二叉树为: 并用如下实力测试: 算法思路: 显然,建立一个二叉链表存储的二叉树,如果不考虑效率要求,考虑到程序的简介性,递归建立和递归遍历是一种很好的办法。 利用C++的类模板的方法实现建立,遍历,输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树,然后调用类模板中已经声明好的四种遍历函数,将遍历结果输出,检验建立好的二叉树是否为要求的二叉树。 初始化:利用构造函数建立二叉树。采用先序递归的调用方法,构造函数主体如下: template template root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} 构造这样的函数,可以在输入时,按先序遍历顺序每次输入一个节点的数据,可以实现任意二叉树的构造。 为了检验构造的二叉树是否为预先设想的二叉树,需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树,因此对遍历二叉树的四种常用发方法,即先序遍历,中序遍历,后续遍历,层次遍历分别实现,通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。 先序遍历:采用递归的方法建立。template xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } 中序遍历:递归方法建立: template if(root==NULL)return; //如果节点为空,则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } 后序遍历:递归方法建立: template if(root==NULL) return; //如果节点为空,返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } 层序遍历:采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列,在访问一个节点的时候,把它的左孩子和右孩子入队,并且将这个节点出队。当队列为空时,就完成了对二叉树的层序遍历。 template Q[rear++] = root;// 若节点不为空,则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空,则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时,该节点的双子入队 } } } 函数主体部分:声明一个类中的对象,调用构造函数,建立二叉树,并输出四种遍历结果,检验输出结果。 int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< 程序结构: 主函数建立一个类模板定义构造函数,析构函数,以及成员函数声明类中的一个对象调用构造函数,构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出,人工检验 源代码: #include template { T data; BiNode template { public: BiTree(); //构造函数,初始化一棵二叉树 ~BiTree(void); //析构函数,释放二叉链表中各结点的存储空间 BiNode //获得指向根结点的指针 void xianxu(BiNode //前序遍历二叉树 void zhongxu(BiNode //中序遍历二叉树 void houxu(BiNode //后序遍历二叉树 void cengxu(BiNode //层序遍历二叉树 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } } template if(root==NULL)return; //如果节点为空,则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } template if(root==NULL) return; //如果节点为空,返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历 BiNode BiNode else{ Q[rear++] = root;// 若节点不为空,则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空,则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时,该节点的双子入队 } } } template if(root!= NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< cout<<“层序遍历序列为”< 通过对结果的分析,发现输出结果与建立二叉树时的输入完全符合,说明程序的运行结果是正确的。 心得体会: 1)函数递归的方法可以在相当程度上使程序简洁,避免代码的冗长复杂。2)构造函数如果带参数,在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用,初始的根节点的数据值由键盘输入,因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见,对于构造函数的含参调用应该小心谨慎。 3)编程时,要不停得检验自己的输入与输出,必要的时候需要人工进行计算,以保证程序的运行按照预先的设想。 读《大学》八目 小议中国式传统“英才”的烙印与转变 [内容摘要] 《大学》中充当灵魂链锁式的 ‚三纲八目‛是中国传统式英才立志立德立功立言的有效途径,也是内圣外王孔儒大道的实现形式。但随着时代发展,历史的经验与教训,我们也应当辩证看待并取舍其中的观念,从而与世界接轨,让古老的中国焕发新生,屹立于世界民族之林。 [关键词 ] 修身 八条目 治国平天下 齐家 一.八条目—中国传统个体道德修为的具体步骤 《大学》云:‚古之欲明明德于天下者,先治其国,欲治其国者,先齐其家,欲齐其家者,先修其身。欲修其身者,先正其心。欲正其心者,先诚其意。欲诚其意者,先致其知,致知在格物。物格而后知至,知至而后意诚,意诚而后心正,心正而后身修,身修而后家齐,家齐而后国治,国治而后天下平。‛ 正如《形象学导论》一书中所言,我们通常把格物、致知、诚意、正心作为道德的内在修为(内修),而把修身、齐家、治国、平天下作为道德的外在修为(外治)。这里由于篇幅和学识有限,同时我个人认为格物致知是修身的起点和源泉,所以我们重点就格物致知进行浅析。《大学》中界定模糊的‚格物致知‛是历代儒学中争议最大的存在。什么是格物?向来是《大学》中最有争议的问题,可以说,在思想史上很少有那个概念能象格物这样,产生过这么多的分歧,这么多不同意见。其中较有影响的,如郑玄认为‚格,来也。物,犹事也。其知于善深则来善物,其知于恶深则来恶物。言事缘人所好来也。‛(《礼记正义》)按这种说法,‚格物‛乃‚致知‛的结果,而不是相反,显然不符合《大学》的原义。朱熹则认为‚格,至也。物,犹事也。穷至事物之理,欲其极处无不到也。‛(《大学章句》)朱熹释‚格物‛为‚穷至事物之理‛,有一定道理。不过他又认为格物的最终目的是‚推极吾之知识‛,即发明内心先天具有的理,显然又是主观发挥了。王阳明认为‚格者,正也。正其不正,以归于正也。‛‚格物如孟子‘大人格君心’之‘格’。是去其心之不正,以全其本体之正。但意念所在,即要去其不正,以全其正。‛(《传习录上》)这个解释主观性更强,离《大学》的原义也更远。 那么,格物的原义到底是什么呢?要回答这个问题,就必须回到《大学》文本中去,从上下文义的关系结构中去寻找解答。以往学者或偏重于文字训诂,或偏重于哲学阐发,都有失片面。因为‚格物‛的‚格‛,歧义颇多,不胜枚举,仅影响较大的就有‚来‛、‚至‛、‚正‛、‚度量‛(《苍颉篇》)等数义,而‚物‛乃‚大共名‛,格物一词,文献中又没有旁证,所以仅凭训诂,显然难以找到答案;同样,《大学》一些概念、命题的陈述不够明确,为后人的哲学的阐发留下了空间,对思想、学术的发展可能不无裨益,但却一定程度上模糊了人们对其原义的理解。与此不同,《大学》虽然对格物等概念缺乏明确交代,但它的结构却相当严谨,不仅三纲领与八条目自成一体,而且上下文字互相照应。所以由此出发,庶几可以找到格物的真实含义。传统文化传承至今,《现代汉语词典》给予的解释为:穷究事物的原理法则而总结为理性知识。格,至也。物,犹事也。致,推极也,知,犹识也。那么如何做到格物致知?我大致浏览《大学》后,比较赞同宋.朱熹的看法——《大学》的要害是‚格物‛,格物的要害是切己。切己是精神要求,格物是身体力行。切己方显以为格物,格物所指必归于切己。所谓‚切己‛,这里有两层意思:一是内省。如何运用内省法呢?‚子曰:‘见贤思齐焉,见不贤而内自省也。’‛‚曾子曰:‘吾日三省吾身,为人谋而不忠乎?与朋友交而不信乎?传不习乎‛二是笃行。《礼记》云:‚儒有博学而不穷。笃行而不倦。‛‚笃行‛是为学的最后阶段,就是既然学有所得,就要努力践履所学,使所学最终有所落实,做到‚知行合一‛。《说文解字》对‚笃‛字的解释有两种:一为固也,二为厚也。从这个意义出发,只要明确目标,坚定意志,坚持不懈,就能真正做到‚笃行‛。因此,对于我们而言,要格物致知,实际上就是八个字,即‚德技共举,知行合一‛。 二,对于八条目的历史与现实的思考 但随着深入阅读和理解《大学》中的这段文字,我对于正心诚意,格物致知,修身齐家,治国平天下的因果关系产生了疑问。内修和外治通过修身这一环节联系起来,那么是不是说做到了内修四目就能达到外王和兼善天下的宏愿了呢?我觉得不然。历史的声音给了我们很多矛盾的结局:先以孔丘为例,活至七十三岁,被鲁君尊为‚国老‛,在其他诸国也得到礼遇,可是其为了实现自身理念以过半百之龄周游列国,惶惶然如丧家之犬,终不得志,虽有一干门徒相随,但儿孙之福是享不到的。这样能说他‚齐家‛了么?苏武牧羊,二十年不改归汉之心;嵇康打铁,飘飘然离凡尘之外;两者都是古时君子效仿的典范,但一个妻子改嫁,一个亡于小人之讥讽,遗下弱女幼子,二者都没能‚齐家‛,但是他们修身的功夫不够么?再有,汉武帝父子相残,唐太宗弑兄篡位,明成祖叔夺侄权,三个都是不‚齐家‛的典范,可是又各自独立开创了中国封建王朝的最辉煌时代。不‚齐家‛便不能‚治国‛乎?三国时蜀相诸葛孔明,有安邦定国之才,经天纬地之能,然六出祁山而不能,只落得‚出师未捷身先死,长使英雄泪满襟‛的结局。所以诸此种种,我们看到,八条目固然是先人的宝贵财富,但是必须按照具体情况和时代背景进行取舍,否则也只能沦为一纸空谈。时至今日,有关八条目的遵循与舍弃更应当充满理性与思考,否则我们也只能在‚传统人才‛的小径上与世界潮流渐行渐远。我们必须对于传统的道德评价和利义关系进行全新的认识和转变,才能真正不负《大学》一古文盛典,不负老祖宗们的心血! 参考文献 《大学章句》朱熹,中华书局1983年版 [M].呼和浩特:远方出版社 》郑玄、吕友仁 上海古籍出版社 》许慎、徐炫 中华书局 《中庸〃大学》 《礼记正义 《说文解字 讨论与思考 1.现实的教学中,我们经常会遇到班级里的“问题学生”,那么面对班级中“问题学生”,教 师应该怎样使其融入班集体,并使其健康快乐的生活 了解这些学生之所以成为问题学生的原因,再对症下药。如果是学习长期滞后的原 因,就把他和班级里学习优秀且自控能力好的同学同桌,让同学帮助他学习,有时 候比老师教的更有效,多表扬他们。不管是哪个原因,最主要的是让问题学生一定 要能让其感受到老师对他们的关心和爱护。多让他们参加班上集体的活动,让他们 感受到集体荣誉感,团结协作的力量,使他们融入班集体。 2.请谈谈自己身边教师励志成长的故事。 我大学时的一个同学,欢妹子,来自于广西财经学院,我们都是2013年的特岗教师,记得在大四最后一年的读书兼找工作热的生涯中,那时候的我们相当的积极,努力学习之余,还不忘了上上网,投投简历,或者是去招聘会上,都想寻觅到自己理想中的一份工作。 我们班的这位欢妹子,除了考本专业的英语等级证之外,还在努力着考教师资格证,她每天一大清早就起床,不是读英语,就是读跟考教师资格有关的书籍,非常地勤快,我每次看到她,都会问,你就不想尝试着到外面的世界闯闯了,外面的世界多诱人啊,她每次都幽默地回了一句,“你看我这身材,就只能是教书的料了,但教师是一个责任重大的职业,所以我没有一天敢懈怠,所以书就成了我的伙伴了”。她每次出去找工作,都是找一些跟教师相关的工作,什么教育机构啊,说只是为了以后多攒点经验,今年的上半年,我们大家都为了工作,在各自忙着,等回来论文答辩看到她的那一刻,她更加的消瘦了,她说”她每天都在跟学生疯狂着英语,在摸索着这个教师的职业,每天的生活都丰富多彩,每天都了解着不同学生的个性,时时在挖掘着学生的闪亮点,公平地对每一位同学用心,到今天走到教师这个岗位,我才发现,我做到她这种,需花费我们很多,爱心、细心、包容心、耐心等等的心,我正朝着她努力方向在前进,平时,多跟学生聊天,了解他们的学习、生活动态,引导他们努力向上。 加德纳的多元智能理论认为每一个孩子都至少有一种优势智能,请结合自己的教学实践谈谈教师应该怎样激发学生的兴趣? 1.作为学生人生成长路上的重要角色,教师应该怎样突破种种局限,正确的引导学生健康的发展? 2.请认真反思自己教育实践中存在的问题,并与大家分享第二篇:数据结构作业
第三篇:数据结构作业——二叉树
第四篇:第二次作业
第五篇:第二次作业