数据实验报告9篇

篇一 数据库实验报告

数据库实验报告

课 程 实 验 报 告

课程名称：

学 号：

v202341129

姓 名：

吴光艺

指导老师：

胡 侃

专业班级：

计算机1402班

报告日期：

2023年4月22日

计算机科学与技术学院

一．实验目的

1.通过对某个数据库管理系统的安装使用，初步了解dbms的工作环境和系统架构

2.熟悉通过sql对数据库进行操作，完成下面的sql语句

3.学习系统的备份功能，学习系统的身份、权限配置操作，了解系统的查询性能分析功能。

4.熟悉通过sql对数据进行完整性检查性控制

二．实验平台

操作系统：win7 数据库管理系统：

server2023r2 交互式查询语言：sql语言

三．实验要求

1.在rdbms中建立一个数据库，进行实验所要求的各种操作，所有的sql操作均在此建立的的新数据库进行

(转 载于: 酷猫写作范文网)

2.根据一下要求认真进行实验，记录所有的实验用例 数据定义：基本表的创建，修改和删除，视图的创建和删除。

数据操作：完成各类查询操作（单表查询，连接查询，嵌套查询，集合查询）；完成各类更新操作（插入数据，删除数据，思想汇报专题修改数据，增加数据）

视图的操作：视图的定义（创建和删除），查询，更新（注意更新的条件） 3.使用sql对数据进行完整性控制（触发器），用实例证实，当操作违反了完整性约束条件时，系统是如何处理的

四．实验内容

1．sql练习部分：

创建三个关系：

商品表商品名称、商品类型

goodsgname char（20）,gtype char（10）

主关键字为（商品名称）。商品类型为（电器、文具、服装。。。）

商场商场名称,所在地区

plazapname char（20），parea char（20）

主关键字为商场名称。所在地区为（洪山、汉口、汉阳、武昌。。。）

销售价格表商品名称、商场名称、当前销售价格、目前举办活动类型

salegname

（10）

主关键字为（商品名称、商场名称）。举办活动类型为（送券、打折），也可为空值，表示当前未举办任何活动。表中记录如（‘哈森皮靴’，‘亚贸广场’，200，‘打折’），同一商场针对不同的商品可能采取不同的促销活动。

create table goods

(

gname char(20) primary key,gtype char(10) char（20），pname char（20），price float，atype char

);

--主关键字为（商品名称）。商品类型为（电器、文具、服装。。。）

create table plaza

(

pname char(20) primary key,parea char(20)

)；---- 商场商场名称,所在地区

create table sale

(

gname char(20),pname char(20),

price float,

atype char(10),

primary key(gname,pname),foreign key(gname) references goods(gname),foreign key(pname) references plaza(pname)

--销售价格表商品名称、酷猫写作范文网商场名称、当前销售价格、目前举办活动类型 )；

insert into goods values ('电风扇','电器');

insert into goods values('电脑','电器');

insert into goods values('彩电','电器');

insert into goods values('空调','电器');

insert into goods values('热水器','电器');

insert into goods values('钢笔','文具');

insert into goods values('练习本','文具');

insert into goods values('墨水','文具');

insert into goods values('书包','文具');

insert into goods values('橡皮','文具');

insert into goods values('西装','服装');

insert into goods values('衬衣','服装');

insert into goods values('裙子','服装');

insert into goods values('内裤','服装');

insert into plaza values('苏宁','洪山');

insert into plaza values('国美','洪山');

insert into plaza values('中百','洪山');

insert into plaza values('国泰','洪山');

insert into plaza values('家乐福','汉口');

insert into plaza values('大洋百货','武昌');

insert into plaza values('武商','武昌');

insert into sale values('电风扇','苏宁',258,'打折');

insert into sale values('电风扇','国美',288,'送券');

insert into sale values('电风扇','中百',288,'');

insert into sale values('电风扇','国泰',275,'送券');

insert into sale values('电风扇','家乐福',188,'');

insert into sale values('电脑','苏宁',5000,'打折');

insert into sale values('电脑','国美',5200,'');

insert into sale values('电脑','中百',6400,'打折');

insert into sale values('电脑','国泰',5800,'送券');

insert into sale values('彩电','苏宁',2700,'打折');

insert into sale values('彩电','国美',2300,'送券');

insert into sale values('彩电','大洋百货',2900,'');

insert into sale values('热水器','苏宁',888,'打折');

insert into sale values('热水器','国美',488,'打折');

insert into sale values('热水器','中百',570,'');

insert into sale values('热水器','大洋百货',620,'送券');

insert into sale values('钢笔','中百',1,'打折');

insert into sale values('钢笔','大洋百货',5,'');

insert into sale values('钢笔','家乐福',3,'打折');

insert into sale values('练习本','中百',12,'送券');

insert into sale values('练习本','国泰',13,'');

insert into sale values('练习本','家乐福',6,'');

insert into sale values('墨水','中百',8,'送券');

insert into sale values('墨水','国泰',10,'打折');

insert into sale values('墨水','武商',15,'');

范文写作下页

数据库实验报告

insert into sale values('书包','中百',88,'打折');

insert into sale values('书包','家乐福',88,'');

insert into sale values('书包','武商',188,'打折');

insert into sale values('橡皮','中百',2,'打折');

insert into sale values('橡皮','家乐福',5,'');

insert into sale values('长裤','中百',188,'打折');

insert into sale values('长裤','家乐福',388,'打折');

insert into sale values('长裤','武商',590,'');

insert into sale values('长裤','国泰',288,'送券');

insert into sale values('短袖','中百',188,'');

insert into sale values('短袖','家乐福',459,'');

insert into sale values('短袖','武商',118,'');

insert into sale values('短袖','国泰',268,'');

insert into sale values('裙子','中百',288,'打折');

insert into sale values('裙子','家乐福',488,'');

insert into sale values('裙子','武商',588,'送券');

insert into sale values('裙子','国泰',128,'');

insert into sale values('短裤','中百',99,'');

insert into sale values('短裤','家乐福',118,'打折');

insert into sale values('短裤','武商',198,'');

insert into sale values('短裤','国泰',88,'');

update sale

set atype='null'

where atype='

';

6

table goods

table plaza

table sale

7

(转载于: 在点 网)

2．数据更新：范文top100

1）向上述表格中用sql语句完成增、删、改的操作；

2）编写一个触发器，并测试该触发器；

3）将sale表中的打折记录插入到新表sale_cheap中，并基于sale_cheap表创建一个统计每个商场各自打折商品平均价格的视图。

create table sale_cheap

8

(

gname char(20),pname char(20),

price float,

insert into sale_cheap(gname,pname,price,atype)

select gname,pname,price,atype

from sale

where atype='打折';

create view pxsale(pname,avg_price)

as

select pname,avg(price)

from sale_cheap

group by pname atype char(10),primary key(gname,pname),foreign key(gname) references goods(gname),foreign key(pname) references plaza(pname)

9

3．用sql语句完成下述查询需求：

1）查询所有以“打折”方式销售的商品的当前销售情况，并按照价格的降序排列；select gname,price

from sale

where atype='打折'

order by price desc;

2）查询所有没有任何活动的商品及其所在的商场，结果按照商品排序；

10

上页 下页

数据库实验报告

select gname,pname

from sale

where atype=null

order by gname;

3）查询价格在200～500元之间的商品名称、所在的商场名称、价格，结果按照商场名称排序；

select gname,pname,price

from sale

where price between 200 and 500

order by pname;

4）查询每种商品的最低价格、商品名称；

select gname,min(price)

from sale

group by gname;

5）查询以“送券”方式销售的商品总数超过30种的商场名称；

select pname

from sale

where atype='送券'

group by pname having count(*)>;15

6）查询以“送券”方式销售的商品总数超过30种的商场所在地区；

select parea

from plaza

where plaza.pname in

(

select sale.pname

from sale

where atype='送券'

group by sale.pname having count(*)>;

7）查询价格为下列取值之一的商品名称、所在商场名称、目前举办活动的类型，（88、188、288、388、488、588、888）；

select gname,pname,atype

from sale

where price in(88,188,288,388,488,588,888)

8）查询以“老”字开头的所有商品的名称；(ps:由于三个关系设计的时候没有注意题目的要求，所以没有符合的选项，故自己有另外建了一个)

create table goods

(

gname char(20) primary key,gtype char(10)

);

--主关键字为（商品名称）。商品类型为（电器、文具、服装。。。）

insert into goods values ('电风扇','电器');

insert into goods values('电视','电器');

insert into goods values('冰箱','电器');

insert into goods values('老花镜','电器');

insert into goods values('老干妈','电器');

select *

from goods

where gname like '老

%';

9）查询同时销售“剃须刀”和“电池”的商场名称；

select s1.pname

from sale s1,sale s2

where s1.pname=s2.pname and s1.gname='剃须刀'

and s2.gname='电池'

10）查询不举办任何活动的商场；

select distinct pname

from sale

except

select distinct pname

from sale

where atype is not null;

11）查询所销售的商品包含了“校园超市”所销售的所有商品的商场名称。

select distinct pname

from sale sx

where not exists

(select * from sale sy where pname='校园超市'

and not exists ( select * from sale sz where sz.pname=sx.pname and sz.gname=sy.gname));

2．软件功能学习部分

（1）学习系统的备份功能。

利用sql server本身带有的备份功能（dts）把数据库全部或者差额定时备份到某个目录，一旦备份成功，这时候在指定的备份目录下有.bak文件存在，选择sqlserver 服务器的数据库，单击鼠标右键，选择“所有任务”选“备份数据库”即可

（2）学习系统的身份、权限配置操作。

打开“ssms—sql server实例—安全性—登录名”，右键选择“新建登录名”，选择身份验证模式（身份验证模式不同，帐户类型也不一样，），输入名字，并为该用户选择一个默认数据库（比如默认为master数据库）。该账户建立好之后，建立数据库用户，以便用户可以访问数据库，对数据库进行操作。我们在建立数据库用户时，其实就是映射登录用户，所以在一般情况下，我们的登录名和数据库用户名是一致的。操作方法：打开“ssms—sql server实例—具体的数据库—安全性—数据库用户”；最后是在具体的数据库对象（比如表）上授予具体的权限，三种权限：授予、回收、拒绝。

上页 下页

数据库实验报告

（3）了解系统的查询性能分析功能。

查询优化有下面3种方法：

a建立索引，建立“适当”的索引是实现查询优化的首要前提；

b重写sql语句（即重写查询语句），sql server中有一个“查询分析优化器”，它可以计算出where子句中的搜索条件并确定哪个索引能缩小表扫描的搜索空间，也就是说，它能实现自动优化；

c其他优化方法（调整参数，建立视图，临时表等）

五．实验体会 通过数据库的多次的上机实验，使我对数据库以及sql语言有了一个更透彻的理解，对以前上课学习到的知识有了更深的认识，通过自己上机实验，对很多以前不是很清楚很明白的问题也有了更清醒的认识，在各种不同的环境中，也能够适时作出相应的调整，在某种程度上提高了自己对知识的领悟能力和学习能力。

通过这次设计，我受益非浅，亲身体验了数据库设计的全过程，在实践中了解了数据库系统设计的步骤、流程以及思路，增长了在数据库设计方面的见识，我深刻认识到以前所学的基础课程的重要性，也使我们掌握了很多新知识，特别是一些课本之外的知识，体会到了理论知识和实践相结合的重要性。

16

上页

篇二 数据库课程设计实验报告

数据库课程设计实验报告

导语：通过本课程设计，培养学生具有c/s模式的数据库应用软件系统的设计和开发能力。以下是小编为大家整理的数据库课程设计实验报告，欢迎大家阅读与借鉴！

数据库课程设计实验报告（1）

有关于数据库实验的心得体会，总的来说，受益匪浅。在这些天中，我们学到了很多东西，包括建表，导入数据，查询，插入。最重要的是我们有机会用电脑自己进行实践，没接触的时候总是觉得它比较深奥或是不可接近的新型语言，尽管自己对c语言非常感兴趣，但还是有些心理上的陌生感。学习数据库就和我们平时的其它科目学习一样感觉它有永无止境的知识，数据库是我在高中时候听过，到了大学渐渐了解了些，但就其原理性的内容还不知道，也就是根本就不清楚什么是数据库，只是知道一个所谓的中国字典里的名词。我认识它是从我接触实验运作开始的，刚开始就是建立数据库，两种验证模式，没什么东西但还觉得不错。进而就是操作语言了，紧接着就是触发器的使用，进而对数据库高级的使用，等等。 开始知道数据库的时候想学，不知道从何而起，不懂的话怎么问，从什么地方学起。后来到大三开学后有数据库原理必修课，非常高兴。当时感觉sql sever数据库管理既然是单独一门课程一定会讲的比较细，也能学到真正实用的内容。学了这门课以后发现和我想的基本是一样的，老师对学生也比较和蔼可亲，对我们要求也不是很紧。让每个人都觉得轻轻松松就能把这门课程学完，没有多么紧张的作业，也没有太苛刻的要求。

当老师在最后说这个课程结束了，回顾一下以前老师给我们讲过的东西，真的有很多是我们应该去注意的。学习完sql sever数据库后感觉可分两大块，一块是开发，一块是管理。开发主要是写写存储过程、触发器什么的，还有就是用oracle的develop工具做form。有点类似于程序员。开发还需要有较强的逻辑思维和创造能力，自己没有真正做过，但感觉应该会比较辛苦，是青春饭；管理则需要对sql sever数据库的原理有深刻的认识，有全局操纵的能力和紧密的思维，责任较大，因为一个小的失误就会弄掉整个数据库，相对前者来说，后者更看重经验。这些东西都是从老师哪里和朋友的讨论中得到的心得，也希望其他朋友能多多向老师和朋友请教，如果是个人单独靠自己来完成一个完美的数据库我觉得比较困难，现在基本上都是团队类型的，而且他们的效率高开发的周期也快。由于数据库管理的责任重大，很少公司愿意请一个刚刚接触sql sever的人去管理数据库。对于我们这些初出茅庐的新手而且电子商务的专业，个人认为可以先选择做管理，有一定经验后转型，去做数据库的开发。当然，这个还是要看人个的实际情况来定。

sql server数据库的实验学习使我对数据库的有了新的进步，以后再看到也就不至于什么也不懂，其实那么多数据库我觉得学好一门就行，只是他们的语言可能不大一样，学好一门后就可去认识其它的，这样应该有事半功倍的效果。就像我学习c语言，当时不能说是学习的棒，但不算差。所以我对以后的语言感觉都不是很困难，了解了vb、c++还有网页中用的html语言、asp语言都能看懂，起码可以对别人的东西进行了一下修改。因此，我感谢数据库老师给了我有用的知识，以便我在以后学习或认识更多的内容能有新的方法和思维，也能更加有效和快速的去消化吸收新的`东西。希望在今后中，sql server能给我更多帮助。感谢学校开设这样一门优秀使用的课程，让我对数据库有了更深的了解。

数据库课程设计实验报告（2）

由于平时接触的都是一些私人项目，这些项目大都是一些类库，其他人的交流相对可以忽略不计，因此也就不考虑规范化的文档。实际上从学习的经历来看，我们接触的知识体系都是属于比较老或比较传统的，与现在发展迅速的it行业相比很多情况已不再适用，尤其是当开源模式逐渐走近开发者后更是如此。

虽然这次是一个数据库课程设计，由于本人在选择项目的时候是本着对自己有实际应用价值的角度考虑的，所以其中也涉及到一些数据库以外的设计。对于ooa/ood的开发模式有时不免要提出一些疑问，uml是设计阶段的工具，而它基本涵盖了软件设计的方方面面，也就是说按照这一软件工程的正常流程，在动手写第一句代码之前，开发人员已经非常熟悉软件产品了，这对于相当有经验的架构师一类人说可能会很容易，但是我们作为学生，连足够的编码经验都没有，却首先被教授并要求先ooa再oop，这样直接导致的问题就是文档与编码对不上号，在修改代码的时候基本不会再去审查文档和先前的分析。甚至根本就是现有代码再有文档，即便是这种情况，代码与文档还是不对应。不可否认，在传统软件工程的详细设计之前的项目过程中还是有很多利于项目开发的部分的。所以我就一直在寻找适合我——针对探究型项目——的开发模式，这次的项目也算是一次尝试，当然这个过程并不会太短。

回到数据库设计上了，这次的数据库设计我是严格按照数据库建模的步骤来进行的，老实说我并没有感觉这样的流程对开发带来多大的帮助，反倒是觉得将思维转化为图表很浪费时间。总体上来说这次的项目也不是很大，而且在数据库的设计上比较保守，也就是说实际上数据库设计还可以再完善完善的。随着我对计算机领域的拓宽和加深，我也会静下心来思考在接触计算机之前的行为，很多次我能深切感觉到，其实我的大脑(未于别人比较)本身就是在使用一种更接近关系数据库的方式来记忆，所以我很可恨自然的设计出符合三范式的表结构来，即便我不知道这些范式的确切含义。可能就像“范式不太容易用通俗易懂的方式解释”一样，在“让工具用图标表述我的思维”时费了一番力气。

从我作为项目的提出人和实现者来看，这是个失败的项目，结合几次教学项目的的实践，发现这也已经不是第一次了。主观原因占多数，比如，尝试新的开发方式，根据设计花了太多的时间来抽象出公用的库而忽略业务逻辑。就这次项目而言，失败的原因有以下几点：

1、使用了新的开发环境(vim)，这是首次在脱离高级ide的情况下编码。

2、使用了新的开发语言(python，actionscript3)，因为我一直比较喜欢“学以致用”，而且这样的“数据驱动型”软件的整套自实现的库都已经完成了，但是由于语言本身的差异，迁移时问题很多，当发现这一点是，已没有多少有效剩余时间了。

3、编码流程的不妥，我比较喜欢从底层的库开始开发，因为一旦库测试通过，将很容易将它放到不同的表示层下。但如果库没有测试成功，将导致整个项目没有任何可视化模型，所以这次的项目无法提交“可运行的代码”。

4、实践目的的不同，我轻易不放弃锻炼的机会，事实上，有机会就一定要比以前有所突破，总是照搬以前的做法还不如就不做呢。这个前提是因为现在能完全用来的学习的时间比较多，等到工作时再这样做的可能性就很小了，因此当然要抓紧机会了。不过还有一个隐藏原因，总以为自己很了不起，其实“遇到的问题数跟人的能力是成正比的”。

5、客观原因在这里就不说了。

由于项目还未完成，暂时无法提出需要改进了地方。

篇三 access数据库实验报告

《数据库及其应用》

（课程编号：b0901000）

实验报告

（2013-2014学年第2学期）

实验成绩：

学 号：

姓 名：

专业班级：

课 堂 号：

任课教师：

完成日期： 20xx.05.27

直接启动access，或在“文件”选项卡中选择“新建”命令项，出现新建空数据库的backstage视图界面。在窗口左侧列出了可以执行的命令项。包括“打开”、“最近使用文件”、“新建”、“帮助”、“选项”等。

②已有打开数据库的backstage视图

若已打开数据库，单击“文件”选项卡，进入当前数据库的backstage视图。包括“数据库另存为”、“关闭数据库”、“信息”“打印”“保存并发布”等。

（2）观察功能区：了解组成功能区的选项卡。

①功能区主选项卡包括“文件”、“开始”、“创建”、“外部数据”和“数据库工具”。每个选项卡都包含多组相关命令。在功能区选项卡上，某些按钮提供选项样式库，而其他按钮将启动命令。4个主要命令选项卡为后四个。

②有一些选项卡属于上下文命令选项卡，根据当前的操作出现或转换。

③快速访问工具栏。出现在窗口顶部access图标右边显示的标准工具栏，它将常用操作

命令显示在这里，用户可以单击按钮进行快速操作。用户可以定制该工具栏。

④快捷键。执行命令的方法有多种。最快速、最直接的方法是使用与命令相关联的`键盘

快捷方式。在功能区中可以使用键盘快捷方式。

（3）观察导航窗格。各种对象的显示组合。

4．access选项及其设置

在backstage视图中选择“选项”命令单击，进入access选项对话框窗口。在该窗口可设置默认文件夹等。选择“当前数据库”页，在该页面可设置文档窗口显示方式、定制导航窗格、定制工具栏的项目等。

#．回答问题

（1）启动access一般有几种方法？

答：3种．

1.单击“开始”按钮，选择“所有

程序”|“microsoft office”|“microsoft access 2010”菜单项单

击。

2．双击access桌面快捷方式（若没有快捷方式可先创建）。

3．打开“计算机”窗口，找到要操作的access数据库文件，双击

（2）按键退出access，对应的键是什么？

答：alt+f4

（3）几种方式进入backstage视图？

答：2种。通过“开始”按钮或桌面access快捷方式启动进入backstage视图。

篇四 数据结构实验报告实验五

数据结构实验报告 实验五

一.实验内容：

实现哈夫曼编码的生成算法。

二.实验目的：

1、使学生熟练掌握哈夫曼树的生成算法。

2、熟练掌握哈夫曼编码的方法。

三.问题描述：

已知n个字符在原文中出现的频率，求它们的哈夫曼编码。

1、读入n个字符，以及字符的.权值，试建立一棵huffman树。

2、根据生成的huffman树，求每个字符的huffman编码。并对给定的待编码字符序列进行编码，并输出。

四.问题的实现

(1)郝夫曼树的存储表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}htnode,*huffmantree; //动态分配数组存储郝夫曼树

郝夫曼编码的存储表示

typedef char* *huffmancode;//动态分配数组存储郝夫曼编码

(2)主要的实现思路：

a.首先定义郝夫曼树的存储形式，这里使用了数组

b.用select遍历n个字符，找出权值最小的两个

c.构造郝夫曼树ht，并求出n个字符的郝夫曼编码hc

总结

1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回huffmancoding，所以把那2个序号设置成了引用。

2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长

3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把ht[i].weight=ht[s1].weight+ht[s2].weight;中的s2写成了i

附：

//动态分配数组存储郝夫曼树

typedef struct{

int weight; //字符的权值

int parent,lchild,rchild;

}htnode,*huffmantree;

//动态分配数组存储郝夫曼编码

typedef char* *huffmancode;

//选择n个(这里是k=n)节点中权值最小的两个结点

void select(huffmantree &ht,int k,int &s1,int &s2)

{ int i;

i=1;

while(i<=k && ht[i].parent!=0)i++;

//下面选出权值最小的结点，用s1指向其序号

s1=i;

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&ht[i].weight

}

//下面选出权值次小的结点，用s2指向其序号

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&i!=s1)break;

}

s2=i;

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&i!=s1&&ht[i].weight

}

}

//构造huffman树，求出n个字符的编码

void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)

{

int m,c,f,s1,s2,i,start;

char *cd;

if(n<=1)return;

m=2*n-1; //n个叶子n-1个结点

ht=(huffmantree)malloc((m+1)*sizeof(htnode)); //0号单元未用，预分配m+1个单元

huffmantree p=ht+1;

w++; //w的号单元也没有值，所以从号单元开始

for(i=1;i<=n;i++,p++,w++)

{

p->;weight=*w;

p->;parent=p->;rchild=p->;lchild=0;

}

for(;i<=m;++i,++p)

{

p->;weight=p->;parent=p->;rchild=p->;lchild=0;

}

for(i=n+1;i<=m;i++)

{

select(ht,i-1,s1,s2); //选出当前权值最小的

ht[s1].parent=i;

ht[s2].parent=i;

ht[i].lchild=s1;

ht[i].rchild=s2;

ht[i].weight=ht[s1].weight+ht[s2].weight;

}

//从叶子到根逆向求每个字符的郝夫曼编码

hc=(huffmancode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量

cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间

cd[n-1]='';//编码结束符

for(i=1;i<=n;i++) //逐个字符求郝夫曼编码

{

start=n-1; //编码结束符位置

for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent) //从叶子到根逆向求编码

{

if(ht[f].lchild==c)cd[--start]='0';

else

cd[--start]='1';

}

hc[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间

strcpy(hc[i],&cd[start]);//从cd复制编码到hc

}

free(cd); //释放工作空间

}

void main

{ int n,i;

int* w; //记录权值

char* ch; //记录字符

huffmantree ht;

huffmancode hc;

cout<<'请输入待编码的字符个数n=';

cin>;>;n;

w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用

ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用

cout<<'依次输入待编码的字符data及其权值weight'<

for(i=1;i<=n;i++)

{

cout<<'data['<

}

篇五 sql数据库制作考务管理系统实验报告

sql数据库制作考务管理系统实验报告

一、实验目的

1. 掌握sql server的基本用法

2. 熟悉掌握asp语言的应用

3. 掌握asp的页面结构和内置对象

4. 掌握asp与sql server数据库的连接和应用

5. 掌握asp 另外一个重要的语言——javascript,并熟悉它的应用

6.制作一个功能完善的考务管理系统

7.能够独立的完成系统策划，系统分析和程序的编写

8. 提高发现问题，解决问题的能力

二、实验内容

制作一个考务管理系统，用于从考生报名、产生准考证到录取考生和打印成绩单即对考生考试和录取全过程的考务管理，系统要实现的功能有：考生报名，按报名顺序产生报名号;产生准考证号和打印准考证;输入考生成绩和输入录取合格标准;根据合格标准录取上线考生;打印考生成绩单和录取通知书;设置系统用户和系统初始化。

三、实验环境

1、windows xp或 windows xx;

2、安装 microsoft sql server xx 个人版。

3、iis 5.0及以上版本和浏览器ie5.5及以上版本

4、macromedia dreamwezver8等相关软件

四、实验步骤

首先：配置环境，安装sql server，macromedia dreamwezver8。

第二：对要做的系统进行构思、策划、布局。

第三：建立数据库kaoshi及数据表：学生信息表(student)，用户表(yonghu)，考生表(biaozhun)。

第四：建立连接数据库的文件conn.asp,其代码如下所示：

<%

set conn=server.createobject('adodb.connection')

conn.open 'provider=sqloledb;' & 'data source=localhost;initial catalog=ksd;user id=sa;password=100200;'

%>;

第五：制作各个网页并联接所有需要联接的网页。

第六：运行整个系统，查找是否有错误，并进行修改直至整个系统运行无误。

五、实验过程与分析

(一)系统分析与总体设计

现在用计算机来进行考生的管理及考生的`录取已普遍存在。因如果用人来进行这项工作将十分烦琐，系统管理员需要划分很多的时间和精力，而且还不能保证其正确率。

而用考务管理系统可以简化管理员的工作，还会提高工作的正确率。以下将对考务管理系统进行系统分析和设计。

(1)系统的功能描述

考务管理系统包括学生报名管理、考生成绩管理系统维护三大模块。

考生报名管理 包括报名处理、产生准考证、打印准考证和退出系统等4项功能。

考生成绩管理 包括考生成绩录入、合格标准录入、录取考生、打印成绩单和打印录取通知单等5项功能。

系统维护 包括用户设置和系统初始化等2项功能。

用户通过系统菜单执行相应的操作。

(2)数据库设计

本系统以sql server xx作为数据库平台。在sql server xx中设计一个数据库kaoshi，其中包含如下数据表。

1.student表

该表用于存放所有考生记录，包括基本数据.表的结构如图2所示。

2biaozhun表

该表用于存放录取考生的合格标准，其中只有一个记录，该记录指出各门课程的最低分和总分的最低分。只有各门成绩和总分都超过这个标准的考生才能被录取。该表的结构如图3所示。

3.yonghu表

该表用于存放本系统用户的信息。包括用户的用户名、密码和级别(只分“一般操作员”和“系统管理员”两类)。该表结构如图4所示。

六、实验结果与总结

实验中的考务管理系统是经过很多次的测试、修改再测试、再修改才完成的。也就是在多次的测试修改的过程中使我学发现了很多平时上课发现不了的问题，也发现了自己学习这门课程的薄弱的地方和学的不足的地方。通过实验期间的发现问题、分析问题、查找问题原因、解决问题及进一步完善考务管理系统的过程，我的能力和水平有一定程度的提高。经过一次独立完成系统给我以后编程打下了基础，让我面对的不再是茫然和无措，而是有条不紊的思绪和完成的信心。所以这次实验对我来说是一笔极大的财富。

当然，在实验中我也有很多不足的地方，系统也有需要进一步完善的地方，这主要是我对asp与sql server数据库的连接和应用不熟悉和经验不足的原因造成的。所以我还要在以后继续学习，以求做的更好。

篇六 北邮数据结构实验报告线性表

北邮数据结构实验报告线性表

实验报告;课程名称：数据结构班级：软件工程实验成绩：;1206;实验名称：打印机队列模拟学号：20124848批;程序的设计;实验编号：实验一姓名：实验日期：2014年5月2;一、实验目的;对队列的理解;对stl中的queue的使用;实验仿真一个网络打印过程;二、实验内容与实验步骤流程图;这个任务队列的测试使用stl队列适配器;具体地说,每一行中包含的信息是

实 验 报 告

课程名称：数据结构 班级：软件工程实验成绩：

1206

实验名称：打印机队列模拟学号：20124848 批阅教师签字：

程序的设计

实验编号：实验一 姓名： 实验日期：2014年5 月 24 日

一、实验目的

对队列的理解

对stl中的queue的使用

实验仿真一个网络打印过程

二、实验内容与实验步骤流程图

这个任务队列的测试使用stl队列适配器。程序要求完成模拟的实现共享打印机。这个打印机使用先进先出队列。仿真是通过读取和处理事件数据文件的列表。一个有效的数据文件中的每一行包含信息打印作业和提交这份工作的时间。

具体地说,每一行中包含的信息是提交工作的时间(以秒为单位),和在页面的工作长及工作的计算机的名称。在模拟的开始,每个这些事件的每一个应该被程序所读，存储在继承工作负载队列。程序应该通过循环递增计数器或while-loop模拟时间的流逝。程序应该将计数器初始化为零,然后依次增加1秒。当模拟等于当前时间的打印作业的提交时间在工作队列的前面，一个打印作业完成。当这一切发生的时候,从工作队列取出这个事件,然后把它放在另一个队列对象。这个队列对象存储已完成的打印作业。当程序仿真其他的打印工作的时候，这些工作在队列等待。

win8，visual c++ 6.0

四、实验过程与分析

(1)实验主要函数及存储结构

main.cpp 包括主函数和主要的功能

simulator.h 仿真类的声明

simulator.cpp 仿真类的定义

event.h 事件类的声明

event.cpp - 事件类的定义

job.h 作业类的声明

job.cpp 作业类的.定义

arbitrary.run 包括任意打印作业数的数据文件

arbitrary.out 输出 arbitrary.run

bigfirst.run 包括打印较大作业的数据文件

bigfirst.out 输出 bigfirst.run

(2)实验代码

#ifndef fifo_h //fifo.h

#define fifo_h

#include 'simulator.h'

class fifo:public simulator{

protected:

queue waiting;

priority_queue priority_waiting;

public:

fifo(int seconds_per_page);

void simulate(string file);

};

bool operator < (event evtleft,event evtright);

#endif

#include 'fifo.h' //fifo.cpp

#include

using namespace std;

fifo::fifo(int seconds_per_page):simulator(seconds_per_page){ }

void fifo::simulate(string file){

int finish_time = 0;

float agg_latency = 0;

int totaljob =0;

event evt;

if(file.find('arbitrary')!= string::npos){

string outfile ='arbitrary.out';

ofstream osf(outfile.c_str);

loadworkload(file);

osf<<'fifo simulation '<

for(int time =1;!waiting.empty||!workload.empty;time++){ while(!workload.empty && time ==

workload.front.arrival_time){

evt= workload.front;

osf<<' arriving: '<

workload.pop;

}

if(!waiting.empty && time >;= finish_time){

totaljob ++;

evt = waiting.front;

agg_latency += time - evt.arrival_time;

osf<<' servicing: '<

finish_time = time + evt.getjob.getnumpages * seconds_per_page;

}

}

osf<<' total job '<

osf<<' aggregate latency: '<

osf<<' mean latency : '<

return;

}

if(file.find('bigfirst') != string::npos){

string outfile = 'bigfirst.out';

ofstream osf(outfile.c_str);

loadworkload(file);

osf<<'fifo simulation '<

for(int time

=1;!priority_waiting.empty||!workload.empty;time++){

while(!workload.empty && time ==

workload.front.arrival_time){

evt= workload.front;

osf<<' arriving: '<

workload.pop;

}

if(!priority_waiting.empty && time >;= finish_time){

totaljob ++;

evt = priority_waiting.top;

agg_latency += time - evt.arrival_time;

osf<<' servicing: '<

finish_time = time + evt.getjob.getnumpages * seconds_per_page; }

}

osf<<' total job '<

osf<<' aggregate latency: '<

osf<<' mean latency : '<

return;

}

cerr<<'the program don't know what algorithm to use'<

cerr<<'you should specify the file name with arbitrary or bigfirst'<

bool operator < (event evtleft,event evtright){

return evtleft.getjob.getnumpages <

evtright.getjob.getnumpages;

}

五、实验结果总结

经测试，功能较为完整。代码流程简图如下：

通过这次实验，我了解了有关队列方面的知识。掌握了队列的逻辑结构，抽象数据类型，队列的存储方式等。运用先进先出表，仿真了网络打印队列。这都使我对数据结构的学习有了新的认识与帮助。在实验过程中，我也遇到了许多困难，从开始时对队列运算的不熟悉，到逐渐查找资料，从而完成了实验;六、附录;-《数据结构与算法分析》以及网上资料;

逐渐查找资料，从而完成了实验。在今后的学习中，我将继续努力，加强对堆栈，队列等知识的学习，以达到精益求精。

六、附录

-《数据结构与算法分析》以及网上资料

篇七 c数据结构实验报告

c数据结构实验报告

数据结构(c语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____201240703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;2013年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目

数据结构(c语言版) 实验报告

专业：计算机科学与技术、软件工程

学号:____201240703061___________________

班级:_________软件二班______________

姓名:________朱海霞______________

指导教师:___刘遵仁________________

青岛大学信息工程学院

2013年10月

实验1

实验题目：顺序存储结构线性表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。

实验主要步骤：

1、分析、理解给出的示例程序。

2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。

程序代码:

#include

#include

#define ok 1

#define error 0

#define overflow -2

#define list_init_size 100

#define listincrement 10

typedef struct{

int* elem;

int length;

int listsize;

}sqlist;

int initlist_sq(sqlist &l){

l.elem=(int*)malloc(list_init_size*sizeof(int));

if(!l.elem) return -1;

l.length=0;

l.listsize=list_init_size;

return ok;

}

int listinsert_sq(sqlist&l,int i,int e){

if(i<1||i>;l.length+1) return error;

if(l.length==l.listsize){

int *newbase;

newbase=(int*)realloc(l.elem,(l.listsize+listincrement)*sizeof(int));

if(!newbase) return -1;

l.elem=newbase;

l.listsize+=listincrement;

}

int *p,*q;

q=&(l.elem[i-1]);

for(p=&(l.elem[l.length-1]);p>;=q;--p)

*(p+1)=*p;

*q=e;

++l.length;

return ok;

}

int listdelete_sq(sqlist &l,int i,int e){

int *p,*q;

if(i<1||i>;l.length)return error;

p=&(l.elem[i-1]);

e=*p;

q=l.elem+l.length-1;

for(++p;p<=q;++p)

*(p-1)=*p;

--l.length;

return ok;

}

int main{

sqlist l;

initlist_sq(l);//初始化

int i,a[]={3,-5,6,8,2,-5,4,7,-9};

for(i=1;i<10;i++)

listinsert_sq(l,i,a[i-1]);

for(i=0;i<9;i++)

printf(' %d',l.elem[i]);

printf(' ');//插入9个数

listinsert_sq(l,3,24);

for(i=0;i<10;i++)

printf(' %d',l.elem[i]);

printf(' ');//插入一个数

int e;

listdelete_sq(l,2, e);

for(i=0;i<9;i++)

printf(' %d',l.elem[i]);//删除一个数

printf(' ');

return 0;

}

实验结果：

3，-5,6,8,2，-5,4,7，-9

3，-5,24,6,8,2，-5,4,7，-9

3,24,6,8,2，-5,4,7，-9

心得体会：

顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2

实验题目：单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。

实验主要步骤：

3、分析、理解给出的示例程序。

4、调试程序，并设计输入数据(如：a，c，e，f，h，j，q，m)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。

5、修改程序：

(1) 增加插入结点的功能。

(2) 建立链表的方法有“前插”、“后插”法。

程序代码:

#include

#include

#define null 0

#define ok 1

#define error 0

typedef struct lnode{

int data;

struct lnode *next;

}lnode,*linklist;

int initlist_l(linklist &l){

l=(linklist)malloc(sizeof(lnode)); l->;next=null;

return ok;

}

int listinsert_l(linklist &l,int i,int e){ linklist p,s;

int j;

p=l;j=0;

while(p&&j

p=p->;next;++j;

}

if(!p||j>;i-1)

return error;

s=(linklist)malloc(sizeof(lnode)); s->;data=e;

s->;next=p->;next;

p->;next=s;

return ok;

}

int listdelete_l(linklist&l,int i,int &e){ linklist p,q;

int j;

p=l;j=0;

while(p->;next&&j

p=p->;next;++j;

}

if(!(p->;next)||j

return error;

q=p->;next;p->;next=q->;next; e=q->;data;free(q);

return ok;

}

int main{

linklist l,p;

char a[8]={'a','c','e','f','h','j','q','u'}; int i,j;

initlist_l(l);

for(i=1,j=0;i<=8,j<8;i++,j++) listinsert_l(l,i,a[j]);

p=l->;next;

while(p!=null){

printf('%c ',p->;data); p=p->;next;

}//插入八个字符printf(' ;实验结果：;acefhjqu;abcefhjqu;abefhjqu;心得体会：;单链表是通过扫描指针p进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：;1、掌握栈的顺序存储结构和链式存储结构，以便在实;2、掌握栈的特点，即后进先出和先进先出的原则;3、掌握栈的'基本运算，如：入栈与出栈

}

}//插入八个字符 printf(' '); i=2; int e; listinsert_l(l,i,'b'); p=l->;next; while(p!=null){ printf('%c ',p->;data); p=p->;next; }//插入一个字符 printf(' '); i=3; listdelete_l(l,i,e); p=l->;next; while(p!=null){ printf('%c ',p->;data); p=p->;next; } printf(' '); return 0;

实验结果：

a c e f h j q u

a b c e f h j q u

a b e f h j q u

心得体会：

单链表是通过扫描指针p进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。

实验3

实验题目：栈操作设计和实现

实验目的：

1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈的特点，即后进先出和先进先出的原则。

3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。

实验要求：

回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如

“abba”是回文，而“abab”不是回文。

实验主要步骤

(1)数据从键盘读入;

(2)输出要判断的字符串;

(3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“yes”，否则输出“no”。

程序代码:

#include

#include

#define true 1

#define false 0

#define ok 1

#define error 0

#define overflow -2

#define n 100

#define stack_init_size 100

#define stackincrement 10

typedef struct{

int *base; // 在栈构造之前和销毁之后，base的值为null int *top; // 栈顶指针

int stacksize; // 当前已分配的存储空间，以元素为单位

} sqstack;

int initstack(sqstack &s)

{ // 构造一个空栈s

if(!(s.base=(int *)malloc(stack_init_size*sizeof(int))))

exit(overflow); // 存储分配失败

s.top=s.base;

s.stacksize=stack_init_size;

return ok;

}

int stackempty(sqstack s)

{ // 若栈s为空栈，则返回true，否则返回false

if(s.top==s.base)

return true;

else

return false;

}

int push(sqstack &s, int e)

{ // 插入元素e为新的栈顶元素

if(s.top-s.base>;=s.stacksize) // 栈满，追加存储空间

{

s.base=(int *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(int)); if(!s.base)

exit(overflow); // 存储分配失败

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*(s.top)++=e;

return ok;

}

int pop(sqstack &s,int &e)

{ // 若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok;否则返回error if(s.top==s.base)

return error;

e=*--s.top;

return ok;

}

int main{

sqstack s;

int i,e,j,k=1;

char ch[n] = {0},*p,b[n] = {0};

if(initstack(s)) // 初始化栈成功

{

printf('请输入表达式: ');

gets(ch);

p=ch;

while(*p) // 没到串尾

push(s,*p++);

for(i=0;i

if(!stackempty(s)) {// 栈不空

pop(s,e); // 弹出栈顶元素

b[i]=e;

}

}

for(i=0;i

if(ch[i]!=b[i])

k=0;

}

if(k==0)

printf('no!');

else

printf('输出:')

printf('yes!');

}

return 0;

}

实验结果：

请输入表达式：

abcba

输出：yes!

心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。

实验4

实验题目：二叉树操作设计和实现

实验目的：

掌握二叉树的定义、性质及存储方式，各种遍历算法。

实验要求：

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

实验主要步骤：

1、分析、理解程序。

2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如abd###ce##f##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

程序代码:

实验结果：

心得体会：

实验5

实验题目：图的遍历操作

实验目的：

掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握dfs及bfs对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。

实验要求：

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的dfs和bfs操作。

实验主要步骤：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的dfs(深度优先遍历)和bfs(广度优先遍历)的操作。

1. 邻接矩阵作为存储结构

#include'stdio.h'

#include'stdlib.h'

#define maxvertexnum 100 //定义最大顶点数

typedef struct{

char vexs[maxvertexnum]; //顶点表

int edges[maxvertexnum][maxvertexnum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数n和边数e

}mgraph; //用邻接矩阵表示的图的类型

//=========建立邻接矩阵=======

void creatmgraph(mgraph *g)

{

int i,j,k;

char a;

printf('input vertexnum(n) and edgesnum(e): ');

scanf('%d,%d',&g->;n,&g->;e); //输入顶点数和边数

scanf('%c',&a);

printf('input vertex string:');

for(i=0;in;i++)

{

scanf('%c',&a);

g->;vexs[i]=a; //读入顶点信息，建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

g->;edges[i][j]=0; //初始化邻接矩阵

printf('input edges,creat adjacency matrix ');

for(k=0;ke;k++) { //读入e条边，建立邻接矩阵

scanf('%d%d',&i,&j); //输入边(vi，vj)的顶点序号

g->;edges[i][j]=1;;g->;edges[j][i]=1;//若为;//=========定义标志向量，为全局变量=;typedefenum{false,true}b;booleanvisited[maxvertex;//========dfs：深度优先遍历的递归算;voiddfsm(mgraph*g,inti);{//以vi为出发点

g->;edges[i][j]=1;

g->;edges[j][i]=1; //若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }

}

//=========定义标志向量，为全局变量=======

typedef enum{false,true} boolean;

boolean visited[maxvertexnum];

//========dfs：深度优先遍历的递归算法======

void dfsm(mgraph *g,int i)

{ //以vi为出发点对邻接矩阵表示的图g进行dfs搜索，邻接矩阵是0，1矩阵

给出你的编码

//===========bfs：广度优先遍历=======

void bfs(mgraph *g,int k)

{ //以vk为源点对用邻接矩阵表示的图g进行广度优先搜索

给出你的编码

//==========主程序main =====

void main

{

int i;

mgraph *g;

g=(mgraph *)malloc(sizeof(mgraph)); //为图g申请内存空间

creatmgraph(g); //建立邻接矩阵

printf('print graph dfs: ');

dfs(g); //深度优先遍历

printf(' ');

printf('print graph bfs: ');

bfs(g,3); //以序号为3的顶点开始广度优先遍历

printf(' ');

}

2. 邻接链表作为存储结构

#include'stdio.h'

#include'stdlib.h'

#define maxvertexnum 50 //定义最大顶点数

typedef struct node{ //边表结点

int adjvex; //邻接点域

struct node *next; //链域

}edgenode;

typedef struct vnode{ //顶点表结点

char vertex; //顶点域

edgenode *firstedge; //边表头指针

}vertexnode;

typedef vertexnode adjlist[maxvertexnum]; //adjlist是邻接表类型 typedef struct {

adjlist adjlist; //邻接表

int n,e; //图中当前顶点数和边数

} algraph; //图类型

//=========建立图的邻接表=======

void creatalgraph(algraph *g)

{

int i,j,k;

char a;

edgenode *s; //定义边表结点

printf('input vertexnum(n) and edgesnum(e): ');

scanf('%d,%d',&g->;n,&g->;e); //读入顶点数和边数

scanf('%c',&a);

printf('input vertex string:');

for(i=0;in;i++) //建立边表

{

scanf('%c',&a);

g->;adjlist[i].vertex=a; //读入顶点信息

g->;adjlist[i].firstedge=null; //边表置为空表

}

printf('input edges,creat adjacency list ');

for(k=0;ke;k++) { //建立边表

scanf('%d%d',&i,&j); //读入边(vi，vj)的顶点对序号

s=(edgenode *)malloc(sizeof(edgenode)); //生成边表结点

s->;adjvex=j; //邻接点序号为j

s->;next=g->;adjlist[i].firstedge;

g->;adjlist[i].firstedge=s; //将新结点*s插入顶点vi的边表头部

s=(edgenode *)malloc(sizeof(edgenode));

s->;adjvex=i; //邻接点序号为i

s->;next=g->;adjlist[j].firstedge;

g->;adjlist[j].firstedge=s; //将新结点*s插入顶点vj的边表头部

}

}

//=========定义标志向量，为全局变量=======

typedef enum{false,true} boolean;

boolean visited[maxvertexnum];

//========dfs：深度优先遍历的递归算法======

void dfsm(algraph *g,int i)

{ //以vi为出发点对邻接链表表示的图g进行dfs搜索

给出你的编码

//==========bfs：广度优先遍历=========

void bfs(algraph *g,int k)

{ //以vk为源点对用邻接链表表示的图g进行广度优先搜索

给出你的编码

//==========主函数===========

void main

{

int i;

algraph *g;

g=(algraph *)malloc(sizeof(algraph));

creatalgraph(g);

printf('print graph dfs: ');

dfs(g);

printf(' ');

printf('print graph bfs: ');

bfs(g,3);

printf(' ');

}

实验结果：

1. 邻接矩阵作为存储结构

2. 邻接链表作为存储结构

心得体会：

实验6

实验题目：二分查找算法的实现

实验目的：

掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。。

实验要求：

编写程序构造一个有序表l，从键盘接收一个关键字key，用二分查找法在l中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。。

实验主要步骤：

1. 建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。

2. 给出算法的递归和非递归代码;

3. 如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性?

程序代码

实验结果：

心得体会：

实验7

实验题目：排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

实验要求：

实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。

实验主要步骤：

程序代码

实验结果：

心得体会：

篇八 数据结构实验报告

数据结构实验报告

数据结构实验报告1

一.实验内容：

实现哈夫曼编码的生成算法。

二.实验目的：

1、使学生熟练掌握哈夫曼树的生成算法。

2、熟练掌握哈夫曼编码的方法。

三.问题描述：

已知n个字符在原文中出现的频率，求它们的哈夫曼编码。

1、读入n个字符，以及字符的权值，试建立一棵huffman树。

2、根据生成的huffman树，求每个字符的huffman编码。并对给定的待编码字符序列进行编码，并输出。

四.问题的实现

(1)郝夫曼树的存储表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}htnode,*huffmantree; //动态分配数组存储郝夫曼树

郝夫曼编码的存储表示

typedef char* *huffmancode;//动态分配数组存储郝夫曼编码

(2)主要的实现思路：

a.首先定义郝夫曼树的存储形式，这里使用了数组

b.用select遍历n个字符，找出权值最小的两个

c.构造郝夫曼树ht，并求出n个字符的郝夫曼编码hc

总结

1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回huffmancoding，所以把那2个序号设置成了引用。

2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长

3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把ht[i].weight=ht[s1].weight+ht[s2].weight;中的s2写成了i

附：

//动态分配数组存储郝夫曼树

typedef struct{

int weight; //字符的.权值

int parent,lchild,rchild;

}htnode,*huffmantree;

//动态分配数组存储郝夫曼编码

typedef char* *huffmancode;

//选择n个(这里是k=n)节点中权值最小的两个结点

void select(huffmantree &ht,int k,int &s1,int &s2)

{ int i;

i=1;

while(i<=k && ht[i].parent!=0)i++;

//下面选出权值最小的结点，用s1指向其序号

s1=i;

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&ht[i].weight

}

//下面选出权值次小的结点，用s2指向其序号

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&i!=s1)break;

}

s2=i;

for(i=1;i<=k;i++)

{

if(ht[i].parent==0&&i!=s1&&ht[i].weight

}

}

//构造huffman树，求出n个字符的编码

void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,int n)

{

int m,c,f,s1,s2,i,start;

char *cd;

if(n<=1)return;

m=2*n-1; //n个叶子n-1个结点

ht=(huffmantree)malloc((m+1)*sizeof(htnode)); //0号单元未用，预分配m+1个单元

huffmantree p=ht+1;

w++; //w的号单元也没有值，所以从号单元开始

for(i=1;i<=n;i++,p++,w++)

{

p->weight=*w;

p->parent=p->rchild=p->lchild=0;

}

for(;i<=m;++i,++p)

{

p->weight=p->parent=p->rchild=p->lchild=0;

}

for(i=n+1;i<=m;i++)

{

select(ht,i-1,s1,s2); //选出当前权值最小的

ht[s1].parent=i;

ht[s2].parent=i;

ht[i].lchild=s1;

ht[i].rchild=s2;

ht[i].weight=ht[s1].weight+ht[s2].weight;

}

//从叶子到根逆向求每个字符的郝夫曼编码

hc=(huffmancode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量

cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间

cd[n-1]='';//编码结束符

for(i=1;i<=n;i++) //逐个字符求郝夫曼编码

{

start=n-1; //编码结束符位置

for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent) //从叶子到根逆向求编码

{

if(ht[f].lchild==c)cd[--start]='0';

else

cd[--start]='1';

}

hc[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间

strcpy(hc[i],&cd[start]);//从cd复制编码到hc

}

free(cd); //释放工作空间

}

void main

{ int n,i;

int* w; //记录权值

char* ch; //记录字符

huffmantree ht;

huffmancode hc;

cout<<'请输入待编码的字符个数n=';

cin>>n;

w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用

ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用

cout<<'依次输入待编码的字符data及其权值weight'<

for(i=1;i<=n;i++)

{

cout<<'data['<

}

数据结构实验报告2

一、实验目的及要求

1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。

本实验训练的要点是“栈”和“队列”的观点;

二、实验内容

1) 利用栈，实现数制转换。

2) 利用栈，实现任一个表达式中的语法检查(选做)。

3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);

三、实验流程、操作步骤或核心代码、算法片段

顺序栈：

status initstack(sqstack &s)

{

s.base=(elemtype*)malloc(stack_init_size*sizeof(elemtype));

if(!s.base)

return error;

s.top=s.base;

s.stacksize=stack_init_size;

return ok;

}

status destorystack(sqstack &s)

{

free(s.base);

return ok;

}

status clearstack(sqstack &s)

{

s.top=s.base;

return ok;

}

status stackempty(sqstack s)

{

if(s.base==s.top)

return ok;

return error;

}

int stacklength(sqstack s)

{

return s.top-s.base;

}

status gettop(sqstack s,elemtype &e)

{

if(s.top-s.base>=s.stacksize)

{

s.base=(elemtype *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elemtype));

if(!s.base) return error;

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*s.top++=e;

return ok;

}

status push(sqstack &s,elemtype e)

{

if(s.top-s.base>=s.stacksize)

{

s.base=(elemtype *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(elemtype));

if(!s.base)

return error;

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*s.top++=e;

return ok;

}

status pop(sqstack &s,elemtype &e)

{

if(s.top==s.base)

return error;

e=*--s.top;

return ok;

}

status stacktraverse(sqstack s)

{

elemtype *p;

p=(elemtype *)malloc(sizeof(elemtype));

if(!p) return error;

p=s.top;

while(p!=s.base)//s.top上面一个...

{

p--;

printf('%d ',*p);

}

return ok;

}

status compare(sqstack &s)

{

int flag,ture=ok,false=error;

elemtype e,x;

initstack(s);

flag=ok;

printf('请输入要进栈或出栈的元素：');

while((x= getchar)!='#'&&flag)

{

switch (x)

{

case '(':

case '[':

case '{':

if(push(s,x)==ok)

printf('括号匹配成功! ');

break;

case ')':

if(pop(s,e)==error || e!='(')

{

printf('没有满足条件 ');

flag=false;

}

break;

case ']':

if ( pop(s,e)==error || e!='[')

flag=false;

break;

case '}':

if ( pop(s,e)==error || e!='{')

flag=false;

break;

}

}

if (flag && x=='#' && stackempty(s))

return ok;

else

return error;

}

链队列：

status initqueue(linkqueue &q)

{

q.front =q.rear=

(queueptr)malloc(sizeof(qnode));

if (!q.front) return error;

q.front->next = null;

return ok;

}

status destoryqueue(linkqueue &q)

{

while(q.front)

{

q.rear=q.front->next;

free(q.front);

q.front=q.rear;

}

return ok;

}

status queueempty(linkqueue &q)

{

if(q.front->next==null)

return ok;

return error;

}

status queuelength(linkqueue q)

{

int i=0;

queueptr p,q;

p=q.front;

while(p->next)

{

i++;

p=q.front;

q=p->next;

p=q;

}

return i;

}

status gethead(linkqueue q,elemtype &e)

{

queueptr p;

p=q.front->next;

if(!p)

return error;

e=p->data;

return e;

}

status clearqueue(linkqueue &q)

{

queueptr p;

while(q.front->next )

{

p=q.front->next;

free(q.front);

q.front=p;

}

q.front->next=null;

q.rear->next=null;

return ok;

}

status enqueue(linkqueue &q,elemtype e)

{

queueptr p;

p=(queueptr)malloc(sizeof (qnode));

if(!p)

return error;

p->data=e;

p->next=null;

q.rear->next = p;

q.rear=p; //p->next 为空

return ok;

}

status dequeue(linkqueue &q,elemtype &e)

{

queueptr p;

if (q.front == q.rear)

return error;

p = q.front->next;

e = p->data;

q.front->next = p->next;

if (q.rear == p)

q.rear = q.front; //只有一个元素时(不存在指向尾指针)

free (p);

return ok;

}

status queuetraverse(linkqueue q)

{

queueptr p,q;

if( queueempty(q)==ok)

{

printf('这是一个空队列! ');

return error;

}

p=q.front->next;

while(p)

{

q=p;

printf('%d<- ',q->data);

q=p->next;

p=q;

}

return ok;

}

循环队列：

status initqueue(sqqueue &q)

{

q.base=(qelemtype*)malloc(maxqsize*sizeof(qelemtype));

if(!q.base)

exit(owerflow);

q.front=q.rear=0;

return ok;

}

status enqueue(sqqueue &q,qelemtype e)

{

if((q.rear+1)%maxqsize==q.front)

return error;

q.base[q.rear]=e;

q.rear=(q.rear+1)%maxqsize;

return ok;

}

status dequeue(sqqueue &q,qelemtype &e)

{

if(q.front==q.rear)

return error;

e=q.base[q.front];

q.front=(q.front+1)%maxqsize;

return ok;

}

int queuelength(sqqueue q)

{

return(q.rear-q.front+maxqsize)%maxqsize;

}

status destoryqueue(sqqueue &q)

{

free(q.base);

return ok;

}

status queueempty(sqqueue q) //判空

{

if(q.front ==q.rear)

return ok;

return error;

}

status queuetraverse(sqqueue q)

{

if(q.front==q.rear)

printf('这是一个空队列!');

while(q.front%maxqsize!=q.rear)

{

printf('%d<- ',q.base[q.front]);

q.front++;

}

return ok;

}

数据结构实验报告3

《数据结构与算法》实验报告

专业 班级 姓名 学号

实验项目

实验一 二叉树的应用

实验目的

1、进一步掌握指针变量的含义及应用。

2、掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

实验内容

题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：

（1）用括号表示法输出家谱二叉树，

（2）查找某人的所有儿子，

（3）查找某人的所有祖先。

算法设计分析

（一）数据结构的定义

为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。

二叉树型存储结构定义为：

typedef struct snode

{char name[max]; //人名

struct snode *left;//指向配偶结点

struct snode *right; //指向兄弟或子女结点

}fnode;

（二）总体设计

实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。其功能描述如下：

（1）主函数：统筹调用各个函数以实现相应功能

void main

（2）家谱建立函数：与用户交互建立家族成员对应关系

void initialfamily(fnode *&head) //家谱建立函数

（3）家谱输出函数：用括号表示法输出家谱

输出形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2））

void printfamily(fnode *head) //家谱输出函数

（4）儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女

void findson(fnode *b,char p[]) //儿子查找函数

（5）祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。

int findancestor(fnode *head,char son[ ]) //祖先查找函数

（6）结点定位函数：在家谱中找到用户输入人名所对应的结点。

fnode *findnode(fnode *b,char p[]) //结点定位函数

（7）选择界面函数：为便于编写程序，将用户选择部分独立为此函数。

void print(int &n)

（三）各函数的详细设计：

void initialfamily(fnode *&head) //家谱建立函数

1：首先建立当前人的信息，将其左右结点置为空，

2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束，

3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点；

4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。

5：如无，则程序结束

void printfamily(fnode *head) //家谱输出函数

1：首先判断当前结点是否为空，如果为空则结束程序；

2：如果不为空，则输出当前结点信息，

3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。

4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”；

5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空

6：如果不为空，则输出“，”，并递归调用输出兄弟信息

7程序结束

fnode *findnode(fnode *b,char p[]) //结点定位函数

1：当前结点是否为空，为空则返回空；

2：如果和查找信息相同，则返回当前结点；

3：如不然，则先后递归访问其左结点，再不是则递归访问右结点

void findson(fnode *b,char p[]) //儿子查找函数

1：在家谱中定位到要查找的结点，如无则输出“查找不到此人”

2：判断其配偶结点与子女结点是否为空，为空则输出“无子女”

3：不为空则输出其配偶结点的所有右结点（子女结点）。

int findancestor(fnode *head,char son[ ]) //祖先查找函数

1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束

2：先将父母结点入栈，当栈为空时程序结束，

3：栈不为空时，判断栈顶元素是否已访问过，

4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素

5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点

6：栈不为空或当前所取结点不为空时，转到2；

实验测试结果及结果分析

（一）测试结果

（二）结果分析

（略）

实验总结

（略）

数据结构实验报告

篇九 北邮数据结构实验报告

北邮数据结构实验报告

北京邮电大学信息与通信工程学院

2009级数据结构实验报告

实验名称： 实验三哈夫曼编/解码器的实现

学生姓名：陈聪捷

日 期： 2010年11月28日

1.实验要求

一、实验目的：

了解哈夫曼树的思想和相关概念;

二、实验内容：

利用二叉树结构实现哈夫曼编/解码器

1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。

2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5.打印：以直观的方式打印哈夫曼树。

6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。

7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2. 程序分析

2.1 存储结构

二叉树

template

class bitree

{

public:

bitree; //构造函数，其前序序列由键盘输入

~bitree(void); //析构函数

binode* getroot; //获得指向根结点的指针

protected:

binode *root; //指向根结点的头指针

};

//声明类bitree及定义结构binode

data：

二叉树是由一个根结点和两棵互不相交的左右子树构成

哈夫曼树类的数据域，继承节点类型为int的二叉树 class huffmantree:public bitree

data:

hcode* hcodetable;//编码表

int tsize; //编码表中的总字符数

二叉树的节点结构

template

struct binode //二叉树的结点结构 {

t data; //记录数据

t lchild; //左孩子

t rchild; //右孩子

t parent; //双亲

};

编码表的节点结构

struct hcode

{

char data; //编码表中的字符

char code[100]; //该字符对应的编码

};

待编码字符串由键盘输入，输入时用链表存储，链表节点为 struct node

{

char character; //输入的字符

unsigned int count;//该字符的权值

bool used; //建立树的时候该字符是否使用过

node* next; //保存下一个节点的地址

};

示意图：

2.2 关键算法分析

1.初始化函数(void huffmantree::init(string input))

算法伪代码：

1.初始化链表的头结点

2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表

中字符的个数)

3.从字符串第2个字符开始，逐个取出字符串中的字符

3.1 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出

的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。

3.2 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入

到链表尾部，同时n++

4.tsize=n(tsize记录链表中字符总数，即哈夫曼树中叶子节点总数)

5.创建哈夫曼树

6.销毁链表

源代码：

void huffmantree::init(string input)

{

node *front=new node; //初始化链表的头结点

if(!front)

throw exception('堆空间用尽');

front->;next=null;

front->;character=null;

front->;count=0;

node *pfront=front;

char ch=input[0]; //获得第一个字符

node* new1=new node;

if(!new1)

throw exception('堆空间用尽');

new1->;character=ch; //将第一个字符插入链表

new1->;count=1;

new1->;next=pfront->;next;

pfront->;next=new1;

bool replace=0; //判断在已经写入链表的字符中是否有与当前读出的字符相同的字符 int n=1; //统计链表中字符个数

for(int i=1;i

{

ch=input[i]; //获得第i个字符

do

{

pfront=pfront->;next;

if((int)pfront->;character == (int)ch) //如果在链表中有与当前字符相同的字符，

该字符权值加1

{

pfront->;count++;

replace=1;

break;

}

}while(pfront->;next);

if(!replace) //如果在链表中没找到与当前字符相同的字符，则将该字符作为新成 员插入链表

{

node* new=new node;

if(!new)

throw exception('堆空间用尽');

new->;character=ch;

new->;count=1;

new->;next=pfront->;next;

pfront->;next=new;

n++;

}

pfront=front; //重置pfront和replace变量为默认值 replace=0;

}

tsize=n; //tsize记录的是编码表中字符个数

createhtree(front,n); //创建哈夫曼树

pfront=front;

while(pfront) //销毁整个链表

{

front=pfront;

pfront=pfront->;next;

front;

}

时间复杂度：

若输入的字符串长度为n，则时间复杂度为o(n)

2.创建哈夫曼树(void huffmantree::createcodetable(node *p))

算法伪代码：

1. 创建一个长度为2*tsize-1的三叉链表

2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tsize个结点

的data域，并将对应结点的孩子域和双亲域赋为空

3. 从三叉链表的第tsize个结点开始，i=tsize

3.1 从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其

下标x,y。

3.2 将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点

3.3 将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为

i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i

结点的双亲设置为空

4. 根据哈夫曼树创建编码表

源代码：

void huffmantree::createhtree(node *p,int n)

{

root= new binode[2*n-1]; //初始化哈夫曼树

node *front=p->;next;

if(n==0)

throw exception('没有输入字符');

for(int i=0;i

root[i].data=front->;count;

root[i].lchild=-1;

root[i].rchild=-1;

root[i].parent=-1;

front=front->;next;

}

front=p;

int new1,new2;

for(i=n;i<2*n-1;i++)

{

selectmin(new1,new2,0,i); //从0~i中选出两个权值最小的结点

root[new1].parent=root[new2].parent=i; //用两个权值最小的结点生成新结点，

新节点为其双亲

root[i].data=root[new1].data+root[new2].data;//新结点的权值为其孩子的权值的和 root[i].lchild=new1;

root[i].rchild=new2;

root[i].parent=-1;

}

createcodetable(p); //创建编码表

}

时间复杂度：

在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为o(n),故该函数

的时间复杂度为o(n^2)

3.创建编码表(void huffmantree::createcodetable(node *p))

算法伪代码：

1.初始化编码表

2.初始化一个指针，从链表的头结点开始，遍历整个链表

2.1 将链表中指针当前所指的结点包含的字符写入编码表中

2.2 得到该结点对应的哈夫曼树的叶子结点及其双亲

2.3 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0

2.4 如果不止一个叶子结点，从当前叶子结点开始判断

2.4.1 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否

则为1

2.4.2 child指针指向叶子结点的双亲，parent指针指向child指针的双亲，

重复2.4.1的操作

2.5 将已完成的编码倒序

2.6 取得链表中的下一个字符

3.输出编码表

源代码：

void huffmantree::createcodetable(node *p)

{

hcodetable=new hcode[tsize]; //初始化编码表

node *front=p->;next;

for(int i=0;i

{

hcodetable[i].data=front->;character; //将第i个字符写入编码表

int child=i; //得到第i个字符对应的叶子节点

int parent=root[i].parent; //得到第i个字符对应的叶子节点的双亲

int k=0;

if(tsize==1) //如果文本中只有一种字符，它的.编码为0

{

hcodetable[i].code[k]='0';

k++;

}

while(parent!=-1) //从第i个字符对应的叶子节点开始，寻找它到根结点的路径

{

if(child==root[parent].lchild) //如果当前结点为双亲的左孩子，则编码为0，

否则编码为1

hcodetable[i].code[k]='0';

else

hcodetable[i].code[k]='1';

k++;

child=parent;

parent=root[child].parent;

}

hcodetable[i].code[k]='';

reverse(hcodetable[i].code); //将编码逆置

front=front->;next; //得到下一个字符

}

cout<<'编码表为：'<

for(i=0;i

{

cout<

parent=root[parent].lchild;

else //编码为1则寻找右孩子

parent=root[parent].rchild;

i++;

}

if(tsize==1) //如果编码表只有一个字符，则根结点即为叶子结点 i++;

d.append(1,hcodetable[parent].data);//将叶子节点对应的字符追加到解码串中 }

cout<

}

时间复杂度：

设待解码串长度为n，则复杂度为o(n)

8. 计算哈夫曼编码的压缩比(void huffmantree::calculate(string s1,string s2)) 算法伪代码：

1. 获得编码前字符串的长度，即其占用的字节数

2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字

节数

3. 压缩比将两个相除

源代码：

void huffmantree::calculate(string s1,string s2)

{

int cal1=s1.length;

int cal2=s2.length;

cal2=ceill((float)cal2/8); //将编码串的比特数转化为字节数 cout<<'编码前的字符串长度：'<

cout<<'编码后的字符串长度：'<

cout<<'压缩比为：'<<((double)cal2/(double)cal1)*100<<'%'<

}

时间复杂度：

o(1)

9. 打印哈夫曼树(void huffmantree::printtree(int treenode,int layer) ) 算法伪代码：

1. 如果待打印结点为空，则返回

2. 递归调用函数打印当前结点的右子树

3. 根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打

印当前结点的权值

4. 递归调用函数打印当前结点的左子树

源代码：

void huffmantree::printtree(int treenode,int layer)

{

if(treenode==-1) //如果待打印结点为空，则返回 return;

else

{

printtree(root[treenode].rchild,layer+1); //先打印该结点的右子树，layer记录

的是该结点所在的层次

for(int i=0;i

空格

cout<<' ';

cout<

printtree(root[treenode].lchild,layer+1); //打印该结点的左子树

}

}

时间复杂度：

中序遍历哈夫曼树，复杂度为o(n)

10. 菜单函数(void huffmantree::menu)

算法伪代码：

1. 逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的

string变量中，直到读到回车输入符为止

2. 删除string变量末尾的回车输入符

3.利用string变量创建哈夫曼树，初始化编码表。

4. 直观打印哈夫曼树

5. 对输入的字符串进行编码

6. 对编码后的字符串进行解码

7. 计算编码前后的压缩比并输出

源代码：

void huffmantree::menu

{

cout<<'请输入你要编码的文本,按回车键确定输入'<

string input;

char letter;

do //将字符逐个读入input变量中

{

letter=cin.get;

input.append(1,letter);

}while(letter!=' ');

input.erase(input.length-1,1); //去掉input末尾的回车符

init(input); //根据输入的字符串创建哈夫曼树及其编码表 cout<<'直观打印哈夫曼树'<

printtree(2*tsize-1-1,1); //打印哈夫曼树

cout<<' '<<' ';

string d1,d2;

cout<<'编码后的字符串为'<

encode(input,d1); //编码并打印编码串

cout<<'解码后的字符串为'<

decode(d1,d2); //解码并打印解码串

cout<<'ascii码编码与huffman编码的比较'<

calculate(input,d1); //计算编码前后的压缩比

}

2.3 其他

1.由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入

的字符串，并采用string类的类成员函数来完成各项任务

2.打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。

3.为了输入空格，输入时采取逐个字符输入的方式

3. 程序运行结果

主函数流程图：

运行结果：

各函数运行正常，没有出现bug

4. 总结

经过这次实验，我了解了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了stl中string类型的用法，对c++更加熟悉