实习报告
学 院： 资源与环境科学学院
课 程： 水污染控制工程实习报告
班 级： 环境工程111班
学 号： 13311118
姓 名： 陈亚珍
指导老师： 陈立伟 职称：副教授
实习时间： 20##年5月26日至20##年5月29日
实习地点： 南京江心洲污水处理厂
2014 年5月31日
南京农业大学教务处制
江心洲污水处理厂实习报告
作者：陈亚珍
一、实习目的
生产实习是学生大学学习很重要的实践环节。实习是每一个大学毕业生必的必修课，它不仅让我们学到了很多在课堂上根本就学不到的知识,还使我们开阔了视野，增长了见识，为我们以后更好把所学的知识运用到实际工作中打下坚实的基础。通过生产实习使我更深入地接触专业知识，进一步了解环境保护工作的实际，了解环境治理过程中存在的问题和理论和实际相冲突的难点问题，并通过撰写实习报告，使我学会综合应用所学知识，提高分析和解决专业问题的能力。
二、实习时间及地点
实习时间：20##年5月26至20##年5月29
实习地点：南京江心洲污水处理厂
三、实习过程
5月26号，讲解了污水处理的大体流程工艺，对污水处理过程有个初步的概念，了解了安全和设备管理方面的知识。5月27到29号，我们班分成五个小组，分别去生化处理班，污泥处理班，排放泵房、变电站和预处理班实习。在生化处理班了解了A/O工艺，在污泥处理班了解了剩余污泥的处理工艺，在排放泵房了解了处理水在出厂前需经过哪些处理，在预处理班，直观的了解了现在预处理使用的技术。
四、实习内容
1. 污水厂概况
南京江心洲污水处理厂污水主要来源于城市污水收集的城市生活污水和部分工业废水，所有污水经过活性污泥法A/O工艺处理后，采用江心淹没排放方式排入长江，日排放量计划为64万吨（雨季），年平均为58万吨。该项目加氯间为密封式，加氯量按5mg/l考虑60万吨/日污水总投氯量125kg/h，设置真空加氯系统一套，59 kg/h加氯机2用1备。加氯间安装有自控报警系统。在城市发生较大范围疫情时，经防疫部门要求，环保部门批准，该厂对生化处理后的水进行加氯处理排入长江，平时处理水不加氯直接排放。该项目一期工程地面噪声源主要有格栅机、鼓风机、污泥脱水机和排放泵等。高噪声设备设有减振降噪部件，远离厂界。水下噪声源有污水潜水泵、曝气机等。该污水处理厂固体废弃物主要来自格栅沉渣和剩余污泥脱水后的泥饼。根据工艺的设计参数推算，污泥量为55.8吨/天（含水率为75％），其中格栅沉渣为20吨/天（含水率60％）。此污泥运到江宁协鑫电厂焚烧发电。
2、 污水处理工艺简介
（1）江边泵站提升提升系统
江边提升系统包括江边35KV变电站，江边泵站1号泵房、2号泵房以及夹江隧道等。
江边35KV变电站主要为江边泵站供电，两条进线，分别为“污水泵站线”及“上江线”；江边泵站主要功能是及时将城区管网的污水提升输送到厂区进行处理。设计输送污水能力为：1号江边泵站40万吨/天，共安装8台德国ABS潜水泵（6用2备），单台流量为3610m³/h，2号江边泵站24万吨/天，共安装8台飞力潜水泵（6用2备），单台流量为2160m³/h，两泵站合计64万吨/天。夹江隧道全长414米，江边泵站至厂区的污水进水压力管道近5Km。
（2）污水处理系统
污水处理系统是污水处理厂的核心部分，主要净化原理是将污水通过一系列污水处理构筑物（如沉砂池、沉淀池、生化池等），通过物理及生化的作用，将污水中的污染物从水中分离的过程。
①、格栅
主要功能：去除水中较大的漂浮物，以防对后续的处理设备造成磨损。
厂区共有两个格栅间，老厂区格栅间安装有4台回转式细格栅，栅距8mm。新厂区格栅间安装有4台转鼓式格栅（其中4台为进口德国琥珀，2台为江苏兆盛），栅距8mm。
②、曝气沉砂池
主要功能：利用污水中水与无机颗粒比重的不同，在污水快速经过沉砂池时，无机性的大颗粒将快速沉淀，从而将无机性颗粒从污水中分离出来。
A、老厂区曝气沉砂池主要参数：
池数 4组
有效长度 L=18m
水平流速 V=0.3m/s
停留时间 t=6min
有效水深 h=4m
B、新厂区曝气沉砂池主要参数：
池数 2组
设计流量 Q=2m3/s
单组设计流量 Q=1m3/s
单组尺寸 L*B*H=24*7.34*4.5
停留时间 6min
附：曝气沉砂池配备有吸砂桥和吸砂泵，吸砂泵将曝气沉砂池底部的砂水混合物抽至吸砂桥中，进行砂水分离，分离出来的砂可再利用。采用D60-81型离心鼓风机为曝气沉砂池鼓风，作用：供氧；清洗砂上有机物，砂沉降，而有机物通过后续的生化池进行处理。
存在问题：曝气沉砂池未曝气，因为如果曝气会使出水的溶解氧含量过高，不利于下一步生化班的厌氧处理。
处理效果：生活污水浓度不高，经过曝气沉砂，BOD从120mg/L降至60mg/L.
③、初沉池
经沉砂池处理过后的水进入配水井，通过分配进入初沉池。这样有利于初沉池的清淤和维护。
主要功能：是利用悬浮有机物与污水之间的比重不同，通过物理的沉淀方法进行固液分离，主要可去除水中的大部分泥渣。江心洲污水处理厂原有辐流初沉池4座，每座初沉池设计进水能力为8.64万吨/天，新建辐流初沉池2座，每座设计进水能力为8.73万吨/天，原有辐流初沉池每2座设置一配水井，新建辐流初沉池设置一配水井。采用的均为中心进水周边出水。
A、1# - 4# 辐流初沉池主要参数：
单池容量 Q=1 m³/s
表面负荷 q=1.66 m³/(m²·h)
池数 4座
直径 50m
停留时间 2h
排泥周期 4次/天
B、5# - 6# 辐流初沉池主要参数：
单池容量 Q=1.01m³/s
表面负荷 q=1.85 m³/(m²·h)
池数 2座
直径 50m
停留时间 2h
排泥周期 4次/天
④、生化池
共分为五个廊道，两段（A级、B级）。
主要功能：是依靠活性污泥（微生物）的好氧和厌氧的交替作用，降解污水中的有机物质；由于厌氧好氧的交替为微生物硝化、反硝化创造了条件，从而将污水中的氨氮等转化为氮气，达到脱氮的目的；磷的去除主要是通过活性污泥中的过磷酸菌在厌氧条件下的释磷以及好氧条件下的过量摄磷的作用，将污水中的磷富集在活性污泥系统内，通过及时排出剩余污泥而达到除磷的目的。
主要设计参数：
池数 2组，每组2池，每池4个廊道
单池设计流量 Q=4790m3/h
总水力停留时间 HRT=6.7h(其中厌氧段1.7h，好氧段5.0h)
总泥龄 8.0d
混合液污泥浓度 MLSS=2500mg/L
污泥产率 Y=0.90kgDS/kgBOD5
污泥回流比 50%--75%
⑤、二沉池
主要功能：进行混合液的泥水分离，回流污泥和排除剩余污泥。
主要设计参数：
池数 8池
单池设计流量 Q=2708m3/h
直径 48m
池深 4.6m
表面负荷 q=1.53m3/（m2·h）
沉淀时间 3.0h
处理效果：污泥浓度达到4500mg/L（水温以16℃为标准）。随着季节不同，水的温度也不同，处理效果也不同。冬季的处理效果最差。可通过水量和浓度来调节。
⑥、D60-81型离心鼓风机
主要功能：是为老厂区4组曝气沉砂池充氧，使池内水流产生离心力，把比重大的无机物颗粒甩向外层而下沉，比重较轻的有机物旋至水流的中心部位随水带走。
⑦、SG40B-CVC豪顿鼓风机
主要功能：是为生化池中的混合液提供足够的溶解氧，使混合液中的活性污泥与污水充分接触。
⑧、回流及剩余污泥泵房
主要功能：将二沉池产生的一定数量的污泥按照一定比例回流至生化池中，补充生化池降解有机物所需的活性污泥；其他剩余污泥通过剩余污泥泵送至污泥处理区进行处理。
④、一级强化处理加药间
主要功能：因为进水水质浓度偏低，如果在汛期水量较大而水质浓度严重偏低，活性污泥不容易培养时，使用一级强化处理加药处理工艺。
（3）污泥处理系统
①、污泥浓缩间
主要功能：将二沉池的活性污泥（含水率99.2%左右）经污泥浓缩机浓缩后，使污泥含水率降至95%，进入污泥消化系统进行二级中温消化，再进行脱水，使脱水后的污泥含水率在80%以下，外运填埋。
A、一级强化处理：
初沉池污泥 70.2TDS/d
含水率 98.5%
湿污泥量 4680m3/d
浓缩后含水率 95%
浓缩后污泥量 1404 m3/d
B、二级生物处理：
初沉池污泥 40TDS/d
含水率 97%
湿污泥量 1333m3/d
二沉池污泥 32TDS/d
含水率 99.2%
湿污泥量 4000m3/d
浓缩后含水率 95%
浓缩后污泥量 1404 m3/d
②、污泥控制间
主要功能：为污泥消化提供控制功能，它包括循环污泥的运行，新鲜污泥的投配，沼气罐过滤及沼气压缩，污泥增温的换热系统。
③、污泥消化池（未使用）
主要功能：浓缩后的污泥在厌氧消化池中消化，有机物得到进一步降解，并产生沼气，产生的沼气可以用于锅炉燃烧，为消化池提供热源，污泥中的病原菌在消化过程中被杀灭；消化后的污泥稳定，无害，易于脱水。
目前，该厂有6座消化池，一级消化池4座，二级消化池2座。采用二级中温厌氧消化，在一级消化过程中对污泥进行加热、搅拌、破渣，并收集污泥产生的沼气。一级消化后的污泥排入二级消化池中，在二级消化过程中不对污泥进行加热和搅拌，在一般情况下，二级消化池作为污泥存储、浓缩和调节作用，排除上清液、破渣，并收集少量沼气。考虑在雨季时，污泥量增加，一级消化池不能满足设计要求，二级消化池将作为一级消化池使用，在二级消化池内设置了作为一级消化池的设备。
目前江心洲污水处理厂有6座消化池，一级消化池4座（编号为1#，2#，3#，4#），二级消化池2座（编号为5#，6#）。池直径为D=24m，有效容积V=5010m³。
A、一级消化池
采用热交换器池外加热，即将一级消化池的污泥用循环泵抽出经加热交换器加热后再送回池中，池内控制温度33℃-35℃。泵循环量按一个池循环要8个小时设计；采用沼气搅拌时池内污泥充分混合，沼气搅拌装置共四套，每池安装一套，沼气搅拌量为400立方米/时·座，全天连续工作。
一级消化池向二级消化池的排泥采用自动排泥，一级消化池的正常设计泥位为17.5米，相应池内沼气压力位400毫米水柱，当池内压力变化时，池内泥位也有相应变化。
B、二级消化池
设有浮渣破碎系统装置，用于破碎表面浮渣，该装置定时使用如每班一次，每次10分钟，沼气释放量为3.5立方米/分米·座。
由于江心洲污水处理厂目前污泥消化系统尚未完全建成运行，因此，目前消化池只作为重力浓缩池使用。
④、污泥脱水间
每天大约可处理300t污泥量。需定时冲洗水泵和带式脱水机的带子，冲洗后的泥水再次进入生化池，循环使用。
A、带式脱水机
有2套带式污泥脱水机，3个人工混合加药罐，经技术改造后，将3个加药罐进行串联，进行自动连续加药。当污泥在消化池停留一段时间后，上清液进行充分释放，使得污泥含水率降低到92%时，进入带式机，注入浓度为2－4‰左右的阳离子聚丙烯酰胺絮凝剂，经带式脱水机滤布相互挤压，使得出泥污泥含水率小于80%。
B、离心脱水机
离心脱水机房采用贝亚雷斯离心脱水机3套，经消化后的污泥含水率降到92%时，通过进泥泵投入离心脱水机，注入浓度为2－4‰左右的阳离子聚丙烯酰胺絮凝剂，在离心机的离心力的作用下与污泥进行分离，从而使污泥含水率降低到80%以下。
（4）、排放系统
主要功能：经二沉池出来的水中富含有大量的微生物，不宜直接排放。经消毒作用，检验达标后才能排入长江中。
①、接触池
二沉池出来的水进入接触池中，加入单过硫酸氢钾、氯（必要时）消毒。呈S型构造，可起到缓冲作用。利用排放泵房混流泵向长江深水排放。
②、加氯间
向二沉池出来的水中，加氯消毒。
③、排放泵房
排放泵房的作用是将处理后的出水经提升排放至长江。主要设备有KBS混流泵8台（6用2备），单台流量为3600m³/h,设计排水能力40万吨／天。
④、新雨污泵房
主要功能：新厂区的雨水进入雨水收集系统流入雨污泵房的前池，经雨水泵提升至新排放泵前池，由新排放泵排入长江；新厂区的生活、生产污水经污水管流入污水泵房前池，经污水泵提升至新厂细格栅前进行再处理。
⑤、老排放泵房
主要功能：老排放泵房主要是排除老厂区的雨水，另在新排放设备状态不稳定，不能满足正常排水要求时，可以启动老排放泵房作为备用。老排放泵房目前共有潜水泵6台。
5、中水系统
主要功能：为了节约水资源，提高经济效益，根据测算，该厂建立2400m3/d的中水控制能力，主要用于厂区绿化用水及新厂细格栅、泥区脱水机房冲洗设备。
（附：3台进水泵，2台真空泵，2台反冲泵，2个过滤罐）
6、变配电系统
厂区35KV主要向江心洲厂区进行电力供给。为双电源供电，分为“上洲线”和“污水线”。
7、水质监测系统
江心洲污水处理厂设有专门的水质检测中心，即我们所参观的化验室，其主要功能是对厂进出水水质，泥样进行跟踪监测，执行标准为GB18918-2002一级B标准，根据检测结果及时为生产运行及工艺调控提供依据。
3.实习总结
此次在江心洲污水处理厂的实习,让我们将理论课上的知识与实践经验相结合，参观了实际处理机械，是自己对水污染控制工程这门课有了更深的了解，明白了工程学是一门需要实践的科目，并不是单纯的理论研究。这次实习也让我对污水处理厂的流程及基本操作有了一个大致了解。
第二篇：数据结构实习报告
《数据结构》 上机报告
学 号： 20131002072 班级序号： 116131-12 姓 名： 陶 剑 浩 指导老师： 吴 亮 成 绩： 中国地质大学（武汉） 信息工程学院信息工程系
20xx年12月
【实习一】 线性表及其应用
【问题描述】
大数运算——计算n的阶乘（n>=20）。
【基本要求】
（1）数据的表示和存储:
（1.1） 累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求；
（1.2）试设计合适的存储结构，要求每个元素或结点最多存储数据的3位数值。
（2）数据的操作及其实现：
基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。
【实现提示】
1）设计数据的存储结构：
介于阶乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积结果，故必须设计一个合适的数据结构实现对数据的存储，例如可以让每个元素或结点存储数据的若干位数值。
从问题描述不难看出n值为任意值，故为使程序尽量不受限制，应采用动态存储结构
【可采用的数据结构】
（1）采用链式存储结构实现（普通单链表，循环单链表，普通双项链表和双向循环链表中任选一种结构）。
（2）采用动态数组实现。
【设计思想】
使用链表形式进行处理，测试数据：
? 输入：（1）n＝20，
? 输出：n！＝24xxxxxxxxxxxx0000
? 输入：（2）n＝30，
? 输出：n！＝2652xxxxxxxxxxxx8636308480000000
【测试】
【源代码】 // 大数运算.cpp : 定义控制台应用程序的入口点。 //
#include "stdafx.h"
#include <iostream>
using namespace
std;
template<class T>
class Chain;
template<class T>
class ChainNode
{
};
template<class T>
class Chain
{
public:
};
//析构函数（删除链表的所有节点） template<class T>
Chain<T>::~Chain()
{
}
//确定链表的长度
template<class T> ChainNode<T>*next; while (first) { } next = first->link; delete first; first = next; Chain(){ first = 0; }; ~Chain(); bool IsEmpty()const{ return first == 0; } int Length()const; bool Find(int k, T&x); Chain<T>&Insert(int k, const T&x); Chain<T>& Change(int k, T x); Chain<T>& Delete(int k, T &x); Chain<T>& Search(const T&x)const; int OutPut(); ChainNode<T>*first; friend Chain<T>; T data; ChainNode<T> *link; private: private:
int Chain<T>::Length()const
{
}
//在链表中查找第K个元素
template<class T>
bool Chain<T>::Find(int k, T &x)
{
}
//向链表中插入元素
template<class T>
Chain<T>& Chain<T>::Insert(int k, const T&x) {
ChainNode<T>*p = first; for (int index = 1; index<k&&p; index++) p = p->link; ChainNode<T>*y = new ChainNode<T>; y->data = x; if (k){ } else { } y->link = first; first = y; y->link = p->link; p->link = y; ChainNode<T>*current = first; int index = 0; while (index<k&¤t) { } if (current) { x = current->data; return true; } return false; current = current->link; index++; ChainNode<T>*current = first; int len = 0; while (current) { } return len; len++; current = current->link;
}
return *this;
//改变链表第k个元素的值
template<class T>
Chain<T>& Chain<T>::Change(int k, T x) {
}
//删除链表第k个元素
template<class T>
Chain<T>&Chain<T>::Delete(int k, T &x) {
}
//搜索第k个元素
template<class T>
Chain<T>&Chain<T>::Search(const T&x)const {
ChainNode<T> *current = first; if (k = 0) { } else ChainNode<T>* p = first; ChainNode<T>* q = first; for (int index = 1; index<k - 1 && q; index++) { } q = q->link; p = q->link; q - link = p->link; x = P->data; delete p; return *this; first = first->link; ChainNode<T> *p = first; for (int index = 0; p&&index<k; index++) { } if (p) p->data = x; return *this; p = p->link;
}
int index = 1; while (current && current->data != x) { } if (current)return index; return 0; current = current->link; index++;
//倒序输出链表 template<class T>
int Chain<T>::OutPut() {
}
int main() ChainNode<T>*current = first; int index = 0; int len = 0; while (current) { } int *arry = new int[len]; current = first; while (current) { } index = index - 1; cout << arry[index]; index = index - 1; for (index; index >= 0; index--) { } cout << endl; return 0; cout.fill('0'); cout.width(3); cout << arry[index]; arry[index] = current->data; current = current->link; index++; len++; current = current->link;
{
Chain<int> A;
int n, i, j, k;
int l = 0;
A.Insert(0, 1);
cout<< "输入计算的数 :" ;
cin >> n;
for (i = 1; i <= n; i++)
{
int m = A.Length();
for (j = 0; j<m; j++)
{
A.Find(j, k);
k = i*k;
A.Change(j, k);
}
for (j = 0; j<m; j++)
{
A.Find(j, k);
if (k >= 1000)
{
if (j<m - 1)
A.Find(j + 1, l); else
{
A.Insert(j + 1, 0); l = 0;
}
l += k / 1000;
A.Change(j + 1, l); k = k % 1000;
A.Change(j, k); }
}
}
cout << n<<"!=";
A.OutPut();
return 0;
}
【实习二】
栈及队列的应用
【问题描述】 栈及队列的应用
表达式求值。
【基本要求】
实现关键
栈的使用；
两位数以上、负数、小数点；
实现方式
控制台程序；
MFC对话框；
【问题分析】
对于计算，用栈来实现，根据书上的内容，用后缀输入表达式，然后计算。通过顺序读取字符串，遇到数字直接输出，遇到运算符，先和运栈的最上面的一个运算符比较优先级，如果比其大就压入栈，比其小则弹出栈顶元素。如果相等则弹出栈的第一个元素不进行操作。
【测试】
测试数据：
3+5*（4-6/3）=13
【源代码】
// 表达式求值.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream> #include "LinkedStack.h" using namespace std;
int isp(char ch)
{
}
int icp(char ch)
{
}
int main(int argc, char* argv[]) {
char ch[40],ch1 = '=', op; LinkedStack<char> s1; //char型栈，储存运算符 LinkedStack<double> s2; //double型栈，储存数字 cout << "输入中缀表达式:"; cin >> ch; if (ch == '=') return 0; return 6; return 4; return 2; return 1; else if (ch == '(') else if (ch == '*' || ch == '/' || ch == '%') else if (ch == '+' || ch == '-') else if (ch == ')') else cout << ch; if (ch == '=') return 0; return 1; return 5; return 3; return 6; else if (ch == '(') else if (ch == '*' || ch == '/' || ch == '%') else if (ch == '+' || ch == '-') else if (ch == ')') else cout << ch;
s1.Push(ch1); while (!s1.IsEmpty()) { int n = strlen(ch); //为字符时可能还要用到n if (isdigit(ch[0])) { } else //如果是运算符 { s1.getTop(ch1); if (isp(ch1)<icp(ch[0])) { } else if (isp(ch1)>icp(ch[0])) { } else { s1.Pop(op); if (op == '(') { for (int j(0); j<n; j++) { } ch[j] = ch[j + 1]; s1.Pop(op); s2.DoOperator(op); s1.Push(ch[0]); for (int j(0); j<n; j++) { } n--; ch[j] = ch[j + 1]; double x = atof(ch); s2.Push(x); int i=0; while (isdigit(ch[i]) || ch[i] == '.')//是数字就被后面的覆盖 { } for (int j(0); j<n; j++) { } n--; ch[j] = ch[j + 1];
} } } } } n--; double x; s2.getTop(x); cout << "答案=" << x << endl; return 0;
//LinkedStack.h代码： #ifndef LINKEDSTACK_H #define LINKEDSTACK_H #include "iostream"
using namespace std;
template <class T>
class LinkedNode
{
public:
};
template <class T>
class LinkedStack
{
private:
LinkedNode<T> *top; LinkedStack() :top(NULL){ }//空栈，附加头结点不占内存（不须new） ~LinkedStack(){ makeEmpty(); } void makeEmpty() { LinkedNode<T> *p; while (top != NULL) { p = top; top = top->link; delete p; 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插入操作都在表头进行
} } void Push(T x) { } bool Pop(T& x) { } bool IsEmpty()const { return top == NULL ? true : false; } bool getTop(T &x) { } 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; value = left - right; Push(value); break; value = left*right; Push(value); break; if (right == 0.0) { if (top == NULL) return false; x = top->data; return true; if (IsEmpty() == true) return false; LinkedNode<T> *p = top; x = p->data; top = top->link; delete p; return true; top = new LinkedNode<T>(x, top); if (top == NULL) { cerr << " 存储分配失败！" << endl; } case '-': case '*': case '/':
}; } } else } } else { } cerr << "Divide by 0!" << endl; Clear(); value = left / right; Push(value); break; Clear(); void Clear() { } bool get2Operands(double &left, double &right)//取左右操作数 { } void AddOperand(double value)//将结果压栈 { } Push(value); if (IsEmpty() == true) { } Pop(right); if (IsEmpty() == true) { } Pop(left); return true; cerr << "缺少左操作数" << endl; return false; cerr << "缺少右操作数" << endl; return false; makeEmpty();
#endif
【实习三】 二叉树及其应用
题目一：二叉树基本算法的实现
【功能要求】
? 键盘输入二叉树结点序列，创建一棵二叉树
? 实现Swap方法，以根结点为参数，
交换每个结点的左子树和右子树（提示：前序递归）
? 实现Find方法，查找值为key的结点，并输出该结点的所有祖先结点
【问题分析】
（1）前序创建
按顺序读取字符串，前序递归创建，字符串值不为结束符则创建节点
（2）Swap算法
前序遍历交换左右节点即可
（3）find算法
可以调用panrent函数，先找到当前节点的父亲节点，然后通过递归一步一步找到其所有祖先节点.
【设计思想】
首先，运用递归的方法，按前序输入建立一棵二叉树，接着，运用类似交换两变量值的方法，交换根结点的左右子树，实现SwapTree方法；然后，通过前序遍历，找到值为key的结点，并实现parent函数，用到一个栈，实现parent结点的逆序输出，即可输出该节点的所有祖先结点
【测试】
测试数据：
前序：ABC##DE#G##F###
层次：AB#CD##EF#G####
【源代码】 // 二叉树基本算法.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方法 {
}
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; BinTreeNode<T>* t; t = subTree->rightChild; subTree->rightChild = subTree->leftChild; subTree->leftChild = t;
//BinaryTree.h代码
#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; 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) { } void preOrder(BinTreeNode<T> *subTree) { } void destroyTree(BinTreeNode<T> *subTree) { } //求父亲节点 BinTreeNode<T>* parent(BinTreeNode<T>* subTree) { LinkedStack<BinTreeNode<T>*> s; BinTreeNode<T>* q = root; if (subTree != NULL) { } destroyTree(subTree->leftChild); destroyTree(subTree->rightChild); delete subTree; if (subTree != NULL) { } cout << subTree->data << " "; preOrder(subTree->leftChild); preOrder(subTree->rightChild); cout << subTree->data << " "; public: private: public:
点
} s.Push(NULL); while (q != NULL) { } cout << "输出不成功！" << endl; return NULL; if (q->leftChild == subTree || q->rightChild == subTree) { } else { } if (q->rightChild != NULL) s.Push(q->rightChild); cout << q->data << " "; //输出祖return q; 先结点 if (q->leftChild != NULL) else s.Pop(q); q = q->leftChild; //找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) { } else { if (p->rightChild != NULL) s.Push(p->rightChild); cout<<"查找成功！"<<endl; break; if (p->leftChild != NULL) p = p->leftChild;
}; } } } else s.Pop(p); while (p != root) { } p = parent(p);
#endif
//LinkedStack.h代码 #ifndef LINKEDSTACK_H #define LINKEDSTACK_H #include "iostream"
using namespace std;
template <class T>
class LinkedNode
{
public:
};
template <class T>
class LinkedStack
{
private:
LinkedNode<T> *top; LinkedStack() :top(NULL){ } public: T data; LinkedNode<T> *link; LinkedNode(LinkedNode<T> *ptr = NULL) { } LinkedNode(T d, LinkedNode<T> *ptr = NULL) { } data = d; link = ptr; link = ptr;
~LinkedStack() { } void makeEmpty() { } void Push(T x) { } bool Pop(T& x) { } bool IsEmpty()const { return top == NULL ? true : false; } bool getTop(T &x) { } { double left, right, value; int result; result = get2Operands(left, right); if (result == true) { switch (op) { if (top == NULL) return false; x = top->data; return true; if (IsEmpty() == true) return false; LinkedNode<T> *p = top; x = p->data; top = top->link; delete p; return true; top = new LinkedNode<T>(x, top); if (top == NULL) { cerr << " 存储分配失败！" << endl; } LinkedNode<T> *p; while (top != NULL) { } p = top; top = top->link; delete p; makeEmpty(); void DoOperator(char op)
} } else case '+': } value = left + right; Push(value); break; value = left - right; Push(value); break; value = left*right; Push(value); break; if (right == 0.0) { } else { } break; value = left / right; Push(value); cerr << "Divide by 0!" << endl; Clear(); case '-': case '*': case '/': Clear(); void Clear() { } bool get2Operands(double &left, double &right)//取左右操作数 { } if (IsEmpty() == true) { } Pop(right); if (IsEmpty() == true) { } Pop(left); return true; cerr << "缺少左操作数" << endl; return false; cerr << "缺少右操作数" << endl; return false; makeEmpty();
}; void AddOperand(double value)//将结果压栈 { } Push(value);
#endif
题目二：确定一棵二叉树
【任务】
输入一棵二叉树的前序遍历序列和中序遍历序列，重构这棵二叉树
【功能要求】
在题目一的基础之上，增加一个方法，重构这棵二叉树
要求以图示效果，层次输出这棵二叉树
【问题分析】
添加一个中序输入和层次输出。
【测试】
【源代码】 #include "stdafx.h"
#include "BinTree.cpp" #include <iostream> using namespace std;
int _tmain(int argc, _TCHAR* argv
[]) {
} char str[20]; cout<<"请输入二叉树的前序遍历序列（AB#D##C#F##）"<<endl; cout<<"层次输出见下方："<<endl<<endl;; cin>>str; BinTreeNode<char> *mTreeNode = NULL; BinTree<char> mTree; mTree.creatTree(str,mTreeNode,NULL); mTree.print(mTree.root); return 0;
//BinTree.cpp代码 #include "StdAfx.h" #include "BinTree.h"
#include <iostream>
using namespace std;
#include <queue>
const char RefValue = '#';
template <class T>
BinTree<T>::BinTree(void){
}
template <class T>
BinTree<T>::~BinTree(void){
}
template <class T>
void BinTree<T>::deleteTree(BinTreeNode<T> *&subTree){
}
template <class T>
void BinTree<T>::creatTree(T str[], BinTreeNode<T> *&subTree, BinTreeNode<T> *parent,int depth = 1){
static int i = -1; T item; if(str[++i] != 0) } else item = str[i]; subTree = new BinTreeNode<T>; subTree->data = item; subTree->depth = depth; subTree->parent = parent; creatTree(str,subTree->leftChild,subTree,++depth); //前序遍历 depth--; //返回上一层时 creatTree(str,subTree->rightChild,subTree,++depth); depth--; if(item != RefValue){ //RefValue表示空结点 while(subTree != NULL){ } deleteTree(subTree->leftChild); deleteTree(subTree->rightChild); subTree = NULL; deleteTree(root); root = NULL;
} subTree = NULL; root = subTree;
template <class T>
void BinTree<T>::swapTree(BinTreeNode<T> *subTree){
}
//寻找key
template <class T>
void BinTree<T>::findKey(BinTreeNode<T> *subTree,T key){
}
//返回结点数
template <class T>
int BinTree<T>::getCount(BinTreeNode<T> *subTree){
static int count = 0; if(subTree != NULL){ } return count; count++; getCount(subTree->leftChild); getCount(subTree->rightChild); if(subTree != NULL){ } if(subTree->data != key){ } else while(subTree->data != firstNodeData){ } subTree = subTree->parent; cout<<subTree->data; findKey(subTree->leftChild,key); findKey(subTree->rightChild,key); static T firstNodeData = subTree->data; if(subTree != NULL){ } root = subTree; BinTreeNode<T> *temp = subTree->leftChild; subTree->leftChild = subTree->rightChild; subTree->rightChild = temp; swapTree(subTree->leftChild); swapTree(subTree->rightChild);
}
//返回二叉树高度
template <class T>
int BinTree<T>::getHeight(BinTreeNode<T> *subTree){
}
//层次输出二叉树
template <class T>
void BinTree<T>::print(BinTreeNode<T> *subTree){
}
template <class T>
void BinTree<T>::inOrder(BinTreeNode<T> *subTree){
static int x = 1; if(subTree != NULL){ inOrder(subTree->leftChild); subTree->x = x; x++; inOrder(subTree->rightChild); queue<BinTreeNode<T>* > mQueue; inOrder(subTree); mQueue.push(subTree); while(!mQueue.empty()){ } cout<<endl; BinTreeNode<T> *temp = mQueue.front(); static int n = 0; if(subTree->depth < temp->depth){ } for(int i = n+1 ;i < temp->x;i++){ } cout<<temp->data; n = n + temp->x; subTree = temp; mQueue.pop(); if(subTree->leftChild != NULL) mQueue.push(subTree->leftChild); mQueue.push(subTree->rightChild); if(subTree->rightChild != NULL) cout<<" "; n = 0; cout<<endl;
} }
//BinTree.h代码
#pragma once
template <class T>
struct BinTreeNode{
};
template <class T>
class BinTree
{
public:
void deleteTree(BinTreeNode<T> *&subTree); void creatTree(T str[], BinTreeNode<T> *&subTree, BinTreeNode<T> *parent,int depth = 1); void swapTree(BinTreeNode<T> *subTree); //交void findKey(BinTreeNode<T> *subTree,T key); //在二int getCount(BinTreeNode<T> *subTree); //返int getHeight(BinTreeNode<T> *subTree); //返void print(BinTreeNode<T> *subTree); //层次void inOrder(BinTreeNode<T> *subTree); //BinTreeNode<T> *root; //二BinTree(void); ~BinTree(void); T data; int depth; //结点深度 int x; //中序遍历时的位置 BinTreeNode<T> *leftChild; BinTreeNode<T> *rightChild; BinTreeNode<T> *parent; BinTreeNode():leftChild(NULL),rightChild(NULL),parent(NULL){} //创建二叉树 换二叉树中所以的子女节点 叉树中寻找结点为key的结点并返回它的所有祖先结点 回二叉树的结点数 回二叉树高度 输出二叉树 中序遍历二叉树 叉树的根节点
};
【实习四】 最优二叉树
最优二叉树
【问题描述】
对huaffman树的算法进行扩充。
【基本要求】
? 实现关键
? 键盘输入一个字符串，统计每个字符出现的频率；
? 输出每个字符的Huffman编码
? 计算并输出WPL
? 实现方式
? 控制台程序
? 输出图的两种遍历方式的结果
【问题分析】
1.先建一个链表：输入一段字符串，将其放入链表中，删除重复节点（data相同）并统计各
个节点频率（存入count中），将链表按各节点count的大小排序（按小
到大顺序）；
2.建huffman树：
(1).将链表前两元素合并，建成一颗小树（小树中，令左节点code=0，右节点code=1），删去表中前两元素，将小树根节点插入链表中（按count大小顺序）
(2).循环操作1，直至表中只剩下一个节点
3.输出编码：
根据parent指针找到节点的祖先节点，然后逆序输出其code值，此即为节点的
编码
4.求WPL：
根据parent指针求节点的深度h，然后每个节点的h+1之和除以节点数即为该树的成功搜索长度
【测试】
【源代码】 // 最优二叉树.cpp : 定义控制台应用程序的入口点。 //
#include "stdafx.h"
#include "HuffmanTree.h"
#include <iostream>
using namespace std;
void fun(int
count[50],char data[50],char str[50]){
for(int i = 0; str[i] != 0;i++){ if(str[i] == '#') continue; static int n = 0; count[n]++; data[n] = str[i]; for(int j = 0; str[j] != 0;j++){ } if(str[i] == str[j] && i != j){ } count[n]++; str[j] = '#';
} } data[++n] = 0;
int _tmain(int argc, _TCHAR* argv[]) {
fun(count,data,str);
} cout<<"WPL:"<<tree.getWPL()<<endl; return 0; cout<<"-----------------------------------"<<endl; cout<<"哈弗曼编码为："<<endl; tree.printCode(tree.root); HuffmanTree<char> tree(data,count,size); cout<<"字符权值为："<<endl; int size = 0; for(int i = 0; data[i] != 0; i++){ } size++; cout<<"字符："<<data[i]<<"出现次数："<<count[i]<<endl; for(int i = 0; i < 50; i++) count[i] = 0; char str [50]; cout<<"请输入字符 ："<<endl; cin>>str; cout<<"-----------------------------------"<<endl; int count[50]; char data[50];
//HuffmanTree.h代码
#pragma once
#include "MinHeap.h"
#include <iostream>
using namespace std;
template <class T>
struct HuffmanTreeNode{
T data; //数据
};
int count; //权值 int code[10]; //结点的哈弗曼编码 HuffmanTreeNode<T> *leftChild; HuffmanTreeNode<T> *rightChild; HuffmanTreeNode<T> *parent; HuffmanTreeNode():leftChild(NULL),rightChild(NULL),parent(NULL){} bool operator <=(HuffmanTreeNode &R){return count <= R.count;} bool operator >(HuffmanTreeNode &R){return count > R.count;}
template <class T>
class HuffmanTree
{
public:
};
template <class T>
HuffmanTree<T>::HuffmanTree(T data [],int w[],int n){
WPL = 0; minHeap<HuffmanTreeNode<T>> hp; HuffmanTreeNode<T> *parent, *first, *second; HuffmanTreeNode<T> *work; for(int i = 0; i < n; i++){ } for(int i = 0; i < n-1; i++){ parent = new HuffmanTreeNode<T>; work = new HuffmanTreeNode<T>; work->data = data[i]; work->count = w[i]; work->leftChild = NULL; work->rightChild = NULL; work->parent = NULL; hp.insert(*work); HuffmanTree(T data[],int w[],int n); HuffmanTree(HuffmanTree<T> &t); ~HuffmanTree(void); void copy(HuffmanTreeNode<T> *subTree, HuffmanTreeNode<T> *&newTree); void encode(HuffmanTreeNode<T> *subTree,int code[],int m = -1); void printCode(HuffmanTreeNode<T> *subTree); void calculateWPL(HuffmanTreeNode<T> *subTree,int i = 0); int getWPL(); HuffmanTreeNode<T> *root; int WPL; private:
};
} first = new HuffmanTreeNode<T>; second = new HuffmanTreeNode<T>; hp.removeMin(*first); //每次从最小堆中取出hp.removeMin(*second); parent->leftChild = first; parent->rightChild = second; parent->count = first->count + second->count; parent->data = '#'; first->parent = parent; second->parent = parent; hp.insert(*parent); 两个最小的数 root = parent; int code[10]; for(int i = 0;i < 10; i++) code[i] = -1; encode(root,code); calculateWPL(root);
template <class T>
HuffmanTree<T>::~HuffmanTree(){
}
template <class T>
void HuffmanTree<T>::copy(HuffmanTreeNode<T> *subTree, HuffmanTreeNode<T> *&newTree){
}
template <class T>
void HuffmanTree<T>::encode(HuffmanTreeNode<T> *subTree,int code[] ,int m = -1){
if(subTree != NULL){ int i; for(int j = 0;j < 10;j++){ subTree->code[j] = code[j]; newTree = new HuffmanTreeNode<T>; if(subTree != NULL){ } newTree->count = subTree->count; newTree->data = subTree->data; copy(subTree->leftChild,newTree->leftChild); copy(subTree->rightChild,newTree->rightChild);
} } } for(int j = 0;j < 10;j++){ } subTree->code[i] = m; encode(subTree->leftChild,subTree->code,0); encode(subTree->rightChild,subTree->code,1); if(code[j] == -1){ } i = j; break;
template <class T>
void HuffmanTree<T>::printCode(HuffmanTreeNode<T> *subTree){
}
template <class T>
void HuffmanTree<T>::calculateWPL(HuffmanTreeNode<T> *subTree,int i = 0){
}
template <class T>
int HuffmanTree<T>::getWPL(){
} return WPL; if(subTree != NULL){ } if(subTree->data != '#') i--; calculateWPL(subTree->rightChild,++i); i--; WPL += i*subTree->count; calculateWPL(subTree->leftChild,++i); if(subTree != NULL){ } if(subTree->data != '#'){ } printCode(subTree->leftChild); printCode(subTree->rightChild); cout<<subTree->data<<':'; for(int i = 0;i < 10;i++) if(subTree->code[i] != -1) cout<<subTree->code[i]; cout<<endl;
//MinHeap.h代码 #pragma once
#include <iostream>
using namespace std;
const int DafaultSize = 10;
template<class E>
class minHeap{
public:
};
template<class E>
minHeap<E>::minHeap(int size){
};
template<class E>
minHeap<E>::~minHeap(){
}
template<class E>
void minHeap<E>::siftDown(int start, int m){
int i = start; //初始位置 int j = 2*i+1; //j是i的左子女位置 E temp = heap[i]; while(j <= m){ if(j<m && heap[j] > heap[j+1]) //左子女大于右子女时，j指向右子女 delete heap; heap = new E[maxHeapSize]; if(heap == NULL){cout<<"堆存储分配失败"<<endl;} currentSize = 0; maxHeapSize = (DafaultSize<size)? size:DafaultSize; minHeap(int size = DafaultSize); ~minHeap(); bool insert(const E& x); bool removeMin(E& x); E *heap; int currentSize; int maxHeapSize; void siftDown(int start, int m); void siftUp(int start); private:
}; } } j++; break; heap[i] = heap[j]; i = j; j = 2*j+1; if(temp <= heap[j]) else{ //大则向上移 heap[i] = temp;
template<class E>
void minHeap<E>::siftUp(int start){
};
template<class E>
bool minHeap<E>::insert(const E& x){
};
template<class E>
bool minHeap<E>::removeMin(E& x){ if(currentSize == 0){ if(currentSize == maxHeapSize){ } heap[currentSize] = x; siftUp(currentSize); currentSize++; return true; cout<<"堆已满"<<endl; return false; int j = start; int i = (j-1)/2; //i的左子女是j E temp = heap[j]; while(j>0){ } heap[j] = temp; if(heap[i] <= temp) //父节点大 } break; heap[j] = heap[i]; j = i; i = (i-1)/2; else{ //父节点小
}; } cout<<"堆为空！！"<<endl; return false; x = heap[0]; heap[0] = heap[currentSize-1]; currentSize--; siftDown(0,currentSize-1); return true;
【实习五】 图及其应用
图的建立及其遍历
【问题描述】
自己设计图并编码进行存储，同时输出图的两种遍历方式的结果。
【基本要求】
? 实现关键
? 图的存储方式的选择
? 图的遍历算法
? 实现方式
? 控制台程序
? 输出图的两种遍历方式的结果
【问题分析】
1.
2. 图的邻接矩阵表示：首先将所有顶点的信息组织成一个顶点表，然后利用一个矩阵来表示各顶点之间的邻接关系。 图的邻接表表示：以邻接矩阵的形式储存结构时，如果出现大量零元素，就会造成存储
空间的巨大浪费，此时，可以将邻接矩阵改为邻接表。为此，需要把邻接矩阵的各行分别组织为一个单链表。在第i行的单链表中，各节点分别存放与同一节点vi关联的各条边。对于带权图，节点中还要保存该边的权值。通过在顶点表的第i个顶点信息中保存的指针adj,可以找到与顶点i对应的边链表的第一个边节点；此外，该记录还保存有该顶点的其他信息。
【测试】
【源代码】 // 图.cpp : 定义控制台应用程序的入口点。 //
#include "stdafx.h"
#include "Graph.cpp"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[]){
cout<<"广度优先遍历："<<endl; cout<<"从哪个点开始？"<<endl; cin>>v; mGraph.BFS(v); Graph<char,int> mGraph(30); mGraph.creat(); cout<<"深度优先遍历："<<endl; cout<<"从哪个点开始？"<<endl; char v; cin>>v; mGraph.DFS(v);
} return 0;
//Graph.cpp代码 #include "StdAfx.h" #include "Graph.h" #include <queue> #include <iostream> using namespace std;
template<class T,class E> Graph<T,E>::Graph(int size){
};
template<class T,class E> Graph<T,E>::~Graph(void){
};
template<class T,class E> void Graph<T,E>::creat(){
int n,m; //顶点数n，边数m T e1,e2; E weight; cout<<"创建：（输入1为有向图，0为无向图）"<<endl; cin>>type; cout<<"请输入顶点数和边数 ："<<endl; cin>>n>>m; cout<<"请输入各个顶点的数据："<<endl; for(int i = 0;i<n;i++){ } cout<<"请输入每条边的数据（顶点，顶点，权值）"<<endl; cin>>e1; insetVertex(e1); delete[] NodeTable; maxVertices = size; numVertices = 0; numEdges = 0; NodeTable = new Vertex<T,E>[maxVertices]; if(NodeTable == NULL) cout<<"存储分配错误"<<endl; NodeTable[i].adj = NULL; for(int i = 0;i < maxVertices;i++)
};
int count = 0; while(count < m){ } cin>>e1>>e2>>weight; int i = getVertexPos(e1); int j = getVertexPos(e2); if(i == -1 || j == -1){ } insetEdge(i,j,weight,type); count++; cout<<"输入边的端点错误！"<<endl;
template<class T,class E>
void Graph<T,E>::insetVertex(const T& vertex){
};
template<class T,class E>
void Graph<T,E>::insetEdge(int v1,int v2,E weight,bool type){
if(v1 >= 0 && v1< numVertices && v2 >= 0 && v2 < numVertices){ } Edge<T,E> *p = NodeTable[v1].adj; while(p != NULL && p->dest != v2) p = p->link; return ; //如果此边已经存在，跳出函数 if(p != NULL) p = new Edge<T,E>; //找不到就创建一个新的结点 p->dest = v2; p->cost = weight; p->link = NodeTable[v1].adj; NodeTable[v1].adj = p; if(!type){ //当为无向图时 } numEdges++; Edge<T,E> *q = new Edge<T,E>; q->dest = v1; q->cost = weight; q->link = NodeTable[v2].adj; NodeTable[v2].adj = q; if(numVertices == maxVertices) cout<<"表满，插入失败！"<<endl; NodeTable[numVertices].data = vertex; NodeTable[numVertices].dest = numVertices; numVertices++;
else
cout<<"插入边不合理！"<<endl; };
template<class T,class E>
int Graph<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 Graph<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>
void Graph<T,E>::DFS(const T &v){ int n = numVertices;
bool *visited = new bool[n];
for(int i = 0;i < n;i++)
visited[i] = false;
int loc = getVertexPos(v);
DFS(loc,visited);
cout<<endl;
delete[] visited;
};
template<class T,class E>
void Graph<T,E>::DFS(int v,bool visited[]){ cout<<getValue(v);
visited[v] = true;
int w = getFirstNeighbor(v);
while(w != -1){ //返回w的下一邻接顶点//邻接顶点不存在
if(visited[w] == false){
cout<<'-';
DFS(w,visited);
}
w = getNextNeighbor(v,w); }
};
template<class T,class E>
void Graph<T,E>::BFS(const T &v){ int n = numVertices;
int loc = getVertexPos(v);
bool *visited = new bool[n];
for(int i = 0;i < n;i++)
visited[i] = false;
cout<<getValue(loc);
visited[loc] = true;
queue<int> mQueue;
mQueue.push(loc);
while(!mQueue.empty()){
loc = mQueue.front();
mQueue.pop();
int w = getFirstNeighbor(loc); while(w != -1){ 跳出这次循环（遍历完一个层）
if(!visited[w]){ cout<<'-'<<getValue(w); visited[w] = true; mQueue.push(w); 中
}
w = getNextNeighbor(loc,w); }
}
cout<<endl;
delete[] visited;
};
//Graph.h代码
//loc的第一个邻接顶点 //当loc的下一个邻接点不存在时，就//如果未访问过 //访问 //设为访问过 //并把它的下一个邻接点加入队列 //loc的下一个邻接顶点
#pragma once
template<class T,class E> struct Edge{
};
template<class T,class E> struct Vertex{
};
template<class T,class E> class Graph
{
public:
Graph(int size); ~Graph(void); void insetVertex(const T& vertex); void insetEdge(int v1,int v2,E weight,bool type); int getFirstNeighbor(int v); int getNextNeighbor(int v , int w); void DFS(const T &v); void DFS(int v,bool visited[]); void BFS(const T &v); void creat(); int maxVertices; //最大顶点数 int numEdges; //当前边数 int numVertices; //当前顶点数 bool type; //是否为有向图 Vertex<T,E> *NodeTable; int getVertexPos(T vertex){ for(int i = 0;i< numVertices;i++) if(NodeTable[i].data == vertex) return i; int dest; T data; Edge<T,E> *adj; int dest; E cost; Edge<T,E> *link; Edge():link(NULL){} Edge(int num , E weight):dest(num),cost(weight),link(NULL){} private: return -1; //表示不存在
}; } T getValue(int v){ } if(v >= 0 && v <= maxVertices) return NodeTable[v].data; return NULL;
【总结】
实习题目普遍偏难。前面的题目还能运用书本的链表，栈进行应对，但对后面的图遍历等比较棘手，只能寻找参考，进行编写。用过本次实习，对本门课程，数据结构的思想有了更深的认识，让我了解了许多知识：讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。由此可见，学好数据结构很有必要！！！
20xx年12月 陶剑浩