重庆能源职业学院

顶岗实习报告

班 级： 20112216 姓 名： 唐庆 学 号： 20112216025 指导教师： 陈丽娟 实习时间：实习地点： 重庆开源项目管理有限公司

时间： 2014 年 5 月 26

实习报告

时光如梭，如白驹过隙，转眼间三年的大学生涯将尽尾声，在理论知识积累之后，要有一个踏入社会进行实践的过程，也就是理论与实践的结合。特别是对与建筑这种实践性能非常强的一门学科更要强调实际操作技能的培养。而且这门学科在很大程度上与书本有一定程度的差异。很幸运，我于20xx年2月至20xx年5月在重庆开源项目管理有限公司，造价部实习。

实习目的：

通过多次实战练习以及领导、同事们的关爱与帮助，耐心的指导。实习能使我所掌握的理论知识得以升华，把理论与实践找到一个最好的切入点，为我所用。所以就要有一个将理论与实践相融合的机会。在实习中可以得到一些只有实践中才能得到的技术，为我以后参加工作打好基础，这就是我这次实习的目的所在。

实习内容:

这是第一次正式与社会接轨踏上工作岗位，开始与以往完全不一样的生活。每天在规定的时间上下班，上班期间要认真准时地完成自己的工作任务，不能草率敷衍了事。我们的肩上开始扛着责任，凡事得谨慎小心，否则随时可能要为一个小小的错误承担严重的后果付出巨大的代价，再也不是一句对不起和一纸道歉书所能解决。公司领导常跟我说，你所做的东西对你而言只是数字而已，但到别人那就是真金白银，所以做事一定要小心谨慎，遇到不懂或不确定的东西要多问。

我们顶岗实习的目标和要求是在造价岗位，以准员工的身份参与建筑工程的计量工作。通过顶岗实习，能全面、准确理解施工图的全部内容，掌握一般建筑的结构构造及结构特点，能熟练识读建筑施工图和结构施工图。熟悉各种定额性质和组成，掌握一般建筑物的工程量计算规则，为以后从事造价工作打基础。在实习期间，我接触最多的就是软件了，用广联达软件算量，对广联达的操作更熟练。这次实习公司给我的任务主要是用广联达计价软件算量，用软件算量之前首先要学会看图纸，熟悉图纸。1

再依据图纸把图画入软件中。

广联达软件有计价软件，图形算量软件，钢筋算量软件。钢筋算量软件是统计建筑中钢筋的量，图形算量软件是统计混凝土，砖等除了钢筋的其他所有量，而计价软件是把所有的量都套上价，所以每个环节都是必不可少的。我作图的顺序是先做钢筋算量软件然后导入图形算量。在钢筋算量软件中画构件的顺序是：柱----梁----板----其他。画楼层的顺序是先画首层在往上画直到顶层最后画基础层。 画所有构件时都是先定义在绘图。钢筋工程结束后汇总计算把工程的钢筋都计算出来。然后把所有工程导入图形算量中。在图形算量软件中主要任务是把所有构件都套定额。在这一环节要求我们熟练掌握定额。

实习总结:

思想方面：对于工作方面只能靠自己的能力来做事情，别人是帮不了自己的。俗话说得好，师傅领进门修行靠自己。因此出来实习，我的大部分时间是自己在学习研究的，只有确实没有办法做出结果或是完全不懂得时候去请教别人，而且讲解的时间是非常短暂的。而在学校大家可以互帮互助的，在遇到困难的时候可以向别人请教或者是大家一起讨论，像以前的这种思想，在我实习的这个阶段让我完全的改变了。现在让我更加深刻的理解了“人要靠自己”这句话。

工作方面：让我觉得刚入公司做好本职工作并不是一件容易的事情。刚入单位，领导很快的布置了一项以前从没这么系统做过的算量任务，要求我在20天内完成。完成这个任务是要使广联达算量软件的，但是这个软件虽然在学校接触过，但是那些都是皮毛，正真的实际操作可想而知，因此我要一边学习软件的使用，一边完成我的任务。幸运的是在软件学习方面得到了一位老师及同事们的指导，在拿到任务后的两天里，我学习了软件的操作及要点，接下来就是在似懂非懂的状态下来完成吩咐给我的任务。在做的过程中遇到不会的立刻向那位老师请教，在别人下班的时候我留下来加班，害怕自己完成不了任务。最终完成了此项任务，做完后交给那位老师检，通过修- 2 -

改，完善！最后也没有太大的问题。土建预算做了几个工程后，但还是着手做了一个工程练习。以前在校老师教育我们“在学校里学的不是知识，而是一种叫做自学的能力”。参加工作后才能深刻体会这句话的含义。随着新的定额的推出、新价目的推出、新计算建筑面积规则的出现、预算软件的不断更新等，让我们不得不重新学习新的东西。在这个信息爆炸的时代，知识更新的速度太快了，靠原有的一点知识肯定是不行的。我们必须时时刻刻在工作中勤于动手慢慢琢磨，不断学习不断积累。遇到不懂的地方，自己先想方设法解决，实在不行可以虚心请教他人，而没有自学精神的人迟早要被企业和社会所淘汰。

通过这实习，给我的感触也颇多，学到的东西也非常的多，为我以后的工作打下了结实的基础，同时也非常感谢学校老师给我们这次实习的机会。这次实习是给我们一次理论与实践相结合的机会，我们只要把握住这次机会，我们就可以很快的融入社会，立足于社会。因此说，我非常的珍惜此次实习，利用好实习的每一分钟来充实自己，让自己很快的成长起来。当然在这段时间里，我也得到了公司领导的认可，这也是我值得骄傲的事情，同时我也知道有这么一句话：“骄兵必败”，因此我会脚踏实地的加倍努力工作，谱写以后的美好人生。

- 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

using namespace

std;

template

class Chain;

template

class ChainNode

{

};

template

class Chain

{

public:

};

//析构函数（删除链表的所有节点） template

Chain::~Chain()

{

}

//确定链表的长度

template ChainNode*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&Insert(int k, const T&x); Chain& Change(int k, T x); Chain& Delete(int k, T &x); Chain& Search(const T&x)const; int OutPut(); ChainNode*first; friend Chain; T data; ChainNode *link; private: private:

int Chain::Length()const

{

}

//在链表中查找第K个元素

template

bool Chain::Find(int k, T &x)

{

}

//向链表中插入元素

template

Chain& Chain::Insert(int k, const T&x) {

ChainNode*p = first; for (int index = 1; indexlink; ChainNode*y = new ChainNode; y->data = x; if (k){ } else { } y->link = first; first = y; y->link = p->link; p->link = y; ChainNode*current = first; int index = 0; while (indexdata; return true; } return false; current = current->link; index++; ChainNode*current = first; int len = 0; while (current) { } return len; len++; current = current->link;

}

return *this;

//改变链表第k个元素的值

template

Chain& Chain::Change(int k, T x) {

}

//删除链表第k个元素

template

Chain&Chain::Delete(int k, T &x) {

}

//搜索第k个元素

template

Chain&Chain::Search(const T&x)const {

ChainNode *current = first; if (k = 0) { } else ChainNode* p = first; ChainNode* q = first; for (int index = 1; indexlink; p = q->link; q - link = p->link; x = P->data; delete p; return *this; first = first->link; ChainNode *p = first; for (int index = 0; p&&indexdata = 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

int Chain::OutPut() {

}

int main() ChainNode*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 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

{

A.Find(j, k);

k = i*k;

A.Change(j, k);

}

for (j = 0; j

{

A.Find(j, k);

if (k >= 1000)

{

if (j

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 #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 s1; //char型栈，储存运算符 LinkedStack 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 { s1.Pop(op); if (op == '(') { for (int j(0); j

} } } } } 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 LinkedNode

{

public:

};

template

class LinkedStack

{

private:

LinkedNode *top; LinkedStack() :top(NULL){ }//空栈，附加头结点不占内存（不须new） ~LinkedStack(){ makeEmpty(); } void makeEmpty() { LinkedNode *p; while (top != NULL) { p = top; top = top->link; delete p; public: T data; LinkedNode *link; LinkedNode(LinkedNode *ptr = NULL){ link = ptr; } LinkedNode(T d, LinkedNode *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 *p = top; x = p->data; top = top->link; delete p; return true; top = new LinkedNode(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 *& subTree) //键盘输入二叉树结点序列，创建一棵二叉树 {

}

T item; cin >> item; if (item != '#') { } subTree = new BinTreeNode(item); CreateBinTree(subTree->leftChild); CreateBinTree(subTree->rightChild);

template

void SwapTree(BinTreeNode *& subTree) //SwapTree方法 {

}

int main(int argc, char* argv[])

{

} BinaryTree 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 = 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 BinTreeNode

{

public:

T data; BinTreeNode *leftChild, *rightChild; BinTreeNode(T d, BinTreeNode *l = NULL, BinTreeNode *r = NULL) :data(d),

leftChild(l), rightChild(r){} };

template class BinaryTree {

protected:

T RefValue; BinTreeNode *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 *subTree) { } void preOrder(BinTreeNode *subTree) { } void destroyTree(BinTreeNode *subTree) { } //求父亲节点 BinTreeNode* parent(BinTreeNode* subTree) { LinkedStack*> s; BinTreeNode* 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* subTree, const T& key)///用类似后序遍历的方法找到值为key的结{ LinkedStack*> s; BinTreeNode*p = subTree; s.Push(NULL); while (p != NULL) { if (p->data == key) { } else { if (p->rightChild != NULL) s.Push(p->rightChild); cout<<"查找成功！"<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 LinkedNode

{

public:

};

template

class LinkedStack

{

private:

LinkedNode *top; LinkedStack() :top(NULL){ } public: T data; LinkedNode *link; LinkedNode(LinkedNode *ptr = NULL) { } LinkedNode(T d, LinkedNode *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 *p = top; x = p->data; top = top->link; delete p; return true; top = new LinkedNode(x, top); if (top == NULL) { cerr << " 存储分配失败！" << endl; } LinkedNode *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 using namespace std;

int _tmain(int argc, _TCHAR* argv

[]) {

} char str[20]; cout<<"请输入二叉树的前序遍历序列（AB#D##C#F##）"<>str; BinTreeNode *mTreeNode = NULL; BinTree mTree; mTree.creatTree(str,mTreeNode,NULL); mTree.print(mTree.root); return 0;

//BinTree.cpp代码 #include "StdAfx.h" #include "BinTree.h"

#include

using namespace std;

#include

const char RefValue = '#';

template

BinTree::BinTree(void){

}

template

BinTree::~BinTree(void){

}

template

void BinTree::deleteTree(BinTreeNode *&subTree){

}

template

void BinTree::creatTree(T str[], BinTreeNode *&subTree, BinTreeNode *parent,int depth = 1){

static int i = -1; T item; if(str[++i] != 0) } else item = str[i]; subTree = new BinTreeNode; 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

void BinTree::swapTree(BinTreeNode *subTree){

}

//寻找key

template

void BinTree::findKey(BinTreeNode *subTree,T key){

}

//返回结点数

template

int BinTree::getCount(BinTreeNode *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<data; findKey(subTree->leftChild,key); findKey(subTree->rightChild,key); static T firstNodeData = subTree->data; if(subTree != NULL){ } root = subTree; BinTreeNode *temp = subTree->leftChild; subTree->leftChild = subTree->rightChild; subTree->rightChild = temp; swapTree(subTree->leftChild); swapTree(subTree->rightChild);

}

//返回二叉树高度

template

int BinTree::getHeight(BinTreeNode *subTree){

}

//层次输出二叉树

template

void BinTree::print(BinTreeNode *subTree){

}

template

void BinTree::inOrder(BinTreeNode *subTree){

static int x = 1; if(subTree != NULL){ inOrder(subTree->leftChild); subTree->x = x; x++; inOrder(subTree->rightChild); queue* > mQueue; inOrder(subTree); mQueue.push(subTree); while(!mQueue.empty()){ } cout< *temp = mQueue.front(); static int n = 0; if(subTree->depth < temp->depth){ } for(int i = n+1 ;i < temp->x;i++){ } cout<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<

} }

//BinTree.h代码

#pragma once

template

struct BinTreeNode{

};

template

class BinTree

{

public:

void deleteTree(BinTreeNode *&subTree); void creatTree(T str[], BinTreeNode *&subTree, BinTreeNode *parent,int depth = 1); void swapTree(BinTreeNode *subTree); //交void findKey(BinTreeNode *subTree,T key); //在二int getCount(BinTreeNode *subTree); //返int getHeight(BinTreeNode *subTree); //返void print(BinTreeNode *subTree); //层次void inOrder(BinTreeNode *subTree); //BinTreeNode *root; //二BinTree(void); ~BinTree(void); T data; int depth; //结点深度 int x; //中序遍历时的位置 BinTreeNode *leftChild; BinTreeNode *rightChild; BinTreeNode *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

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(data,count,size); cout<<"字符权值为："<>str; cout<<"-----------------------------------"<

//HuffmanTree.h代码

#pragma once

#include "MinHeap.h"

#include

using namespace std;

template

struct HuffmanTreeNode{

T data; //数据

};

int count; //权值 int code[10]; //结点的哈弗曼编码 HuffmanTreeNode *leftChild; HuffmanTreeNode *rightChild; HuffmanTreeNode *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 HuffmanTree

{

public:

};

template

HuffmanTree::HuffmanTree(T data [],int w[],int n){

WPL = 0; minHeap> hp; HuffmanTreeNode *parent, *first, *second; HuffmanTreeNode *work; for(int i = 0; i < n; i++){ } for(int i = 0; i < n-1; i++){ parent = new HuffmanTreeNode; work = new HuffmanTreeNode; 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); ~HuffmanTree(void); void copy(HuffmanTreeNode *subTree, HuffmanTreeNode *&newTree); void encode(HuffmanTreeNode *subTree,int code[],int m = -1); void printCode(HuffmanTreeNode *subTree); void calculateWPL(HuffmanTreeNode *subTree,int i = 0); int getWPL(); HuffmanTreeNode *root; int WPL; private:

};

} first = new HuffmanTreeNode; second = new HuffmanTreeNode; 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

HuffmanTree::~HuffmanTree(){

}

template

void HuffmanTree::copy(HuffmanTreeNode *subTree, HuffmanTreeNode *&newTree){

}

template

void HuffmanTree::encode(HuffmanTreeNode *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; 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

void HuffmanTree::printCode(HuffmanTreeNode *subTree){

}

template

void HuffmanTree::calculateWPL(HuffmanTreeNode *subTree,int i = 0){

}

template

int HuffmanTree::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<data<<':'; for(int i = 0;i < 10;i++) if(subTree->code[i] != -1) cout<code[i]; cout<

//MinHeap.h代码 #pragma once

#include

using namespace std;

const int DafaultSize = 10;

template

class minHeap{

public:

};

template

minHeap::minHeap(int size){

};

template

minHeap::~minHeap(){

}

template

void minHeap::siftDown(int start, int m){

int i = start; //初始位置 int j = 2*i+1; //j是i的左子女位置 E temp = heap[i]; while(j <= m){ if(j heap[j+1]) //左子女大于右子女时，j指向右子女 delete heap; heap = new E[maxHeapSize]; if(heap == NULL){cout<<"堆存储分配失败"<

}; } } j++; break; heap[i] = heap[j]; i = j; j = 2*j+1; if(temp <= heap[j]) else{ //大则向上移 heap[i] = temp;

template

void minHeap::siftUp(int start){

};

template

bool minHeap::insert(const E& x){

};

template

bool minHeap::removeMin(E& x){ if(currentSize == 0){ if(currentSize == maxHeapSize){ } heap[currentSize] = x; siftUp(currentSize); currentSize++; return true; cout<<"堆已满"<0){ } heap[j] = temp; if(heap[i] <= temp) //父节点大 } break; heap[j] = heap[i]; j = i; i = (i-1)/2; else{ //父节点小

}; } cout<<"堆为空！！"<

【实习五】 图及其应用

图的建立及其遍历

【问题描述】

自己设计图并编码进行存储，同时输出图的两种遍历方式的结果。

【基本要求】

? 实现关键

? 图的存储方式的选择

? 图的遍历算法

? 实现方式

? 控制台程序

? 输出图的两种遍历方式的结果

【问题分析】

1.

2. 图的邻接矩阵表示：首先将所有顶点的信息组织成一个顶点表，然后利用一个矩阵来表示各顶点之间的邻接关系。 图的邻接表表示：以邻接矩阵的形式储存结构时，如果出现大量零元素，就会造成存储

空间的巨大浪费，此时，可以将邻接矩阵改为邻接表。为此，需要把邻接矩阵的各行分别组织为一个单链表。在第i行的单链表中，各节点分别存放与同一节点vi关联的各条边。对于带权图，节点中还要保存该边的权值。通过在顶点表的第i个顶点信息中保存的指针adj,可以找到与顶点i对应的边链表的第一个边节点；此外，该记录还保存有该顶点的其他信息。

【测试】

【源代码】 // 图.cpp : 定义控制台应用程序的入口点。 //

#include "stdafx.h"

#include "Graph.cpp"

#include

using namespace std;

int _tmain(int argc, _TCHAR* argv[]){

cout<<"广度优先遍历："<>v; mGraph.BFS(v); Graph mGraph(30); mGraph.creat(); cout<<"深度优先遍历："<>v; mGraph.DFS(v);

} return 0;

//Graph.cpp代码 #include "StdAfx.h" #include "Graph.h" #include #include using namespace std;

template Graph::Graph(int size){

};

template Graph::~Graph(void){

};

template void Graph::creat(){

int n,m; //顶点数n，边数m T e1,e2; E weight; cout<<"创建：（输入1为有向图，0为无向图）"<>type; cout<<"请输入顶点数和边数 ："<>n>>m; cout<<"请输入各个顶点的数据："<>e1; insetVertex(e1); delete[] NodeTable; maxVertices = size; numVertices = 0; numEdges = 0; NodeTable = new Vertex[maxVertices]; if(NodeTable == NULL) cout<<"存储分配错误"<

};

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<<"输入边的端点错误！"<

template

void Graph::insetVertex(const T& vertex){

};

template

void Graph::insetEdge(int v1,int v2,E weight,bool type){

if(v1 >= 0 && v1< numVertices && v2 >= 0 && v2 < numVertices){ } Edge *p = NodeTable[v1].adj; while(p != NULL && p->dest != v2) p = p->link; return ; //如果此边已经存在，跳出函数 if(p != NULL) p = new Edge; //找不到就创建一个新的结点 p->dest = v2; p->cost = weight; p->link = NodeTable[v1].adj; NodeTable[v1].adj = p; if(!type){ //当为无向图时 } numEdges++; Edge *q = new Edge; q->dest = v1; q->cost = weight; q->link = NodeTable[v2].adj; NodeTable[v2].adj = q; if(numVertices == maxVertices) cout<<"表满，插入失败！"<

else

cout<<"插入边不合理！"<

template

int Graph::getFirstNeighbor(int v){ if(v != -1){

Edge *p = NodeTable[v].adj; if(p != NULL)

return p->dest;

}

return -1;

};

template

int Graph::getNextNeighbor(int v , int w){ if(v != -1){

Edge *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

void Graph::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<

delete[] visited;

};

template

void Graph::DFS(int v,bool visited[]){ cout<

visited[v] = true;

int w = getFirstNeighbor(v);

while(w != -1){ //返回w的下一邻接顶点//邻接顶点不存在

if(visited[w] == false){

cout<<'-';

DFS(w,visited);

}

w = getNextNeighbor(v,w); }

};

template

void Graph::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<

visited[loc] = true;

queue mQueue;

mQueue.push(loc);

while(!mQueue.empty()){

loc = mQueue.front();

mQueue.pop();

int w = getFirstNeighbor(loc); while(w != -1){ 跳出这次循环（遍历完一个层）

if(!visited[w]){ cout<<'-'<

}

w = getNextNeighbor(loc,w); }

}

cout<

delete[] visited;

};

//Graph.h代码

//loc的第一个邻接顶点 //当loc的下一个邻接点不存在时，就//如果未访问过 //访问 //设为访问过 //并把它的下一个邻接点加入队列 //loc的下一个邻接顶点

#pragma once

template struct Edge{

};

template struct Vertex{

};

template 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 *NodeTable; int getVertexPos(T vertex){ for(int i = 0;i< numVertices;i++) if(NodeTable[i].data == vertex) return i; int dest; T data; Edge *adj; int dest; E cost; Edge *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月 陶剑浩