注：实验用书为 数据结构 C语言版 第2版，人民邮电出版社出版。

实验题目：学生管理系统的设计与实现

实验环境：Visual C++ 6.0或其他C++环境
一、实验目的

1、掌握二叉树的定义；

2、掌握二叉树的基本操作，如二叉树的建立、遍历、结点个数统计、树的深度计算等。
二、实验内容

（一）用递归的方法实现以下算法：

1、以二叉链表表示二叉树，建立一棵二叉树（算法5.3）；

2、输出二叉树的中序遍历结果（算法5.1）；

3、输出二叉树的前序遍历结果（见样例）；

4、输出二叉树的后序遍历结果（见样例）；

5、计算二叉树的深度（算法5.5）；

6、统计二叉树的结点个数（算法5.6）；

7、统计二叉树的叶结点个数；

8、统计二叉树的度为1的结点个数；

9、输出二叉树中从每个叶子结点到根结点的路径。

10、交换二叉树每个结点的左孩子和右孩子；

11、设计二叉树的双序遍历(DblOrderTraverse)算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。
三、测试效果如图：


四、代码如下：
#include <iostream>
using namespace std;

typedef struct Node
{//定义二叉树结构
    char data;
    struct Node *lchild,*rchild;
}*BiTree,BiTNode;

void CreateBiTree(BiTree &T)
{//先序创建二叉树
    char ch;
    cin>>ch;
    if(ch=='#') T=NULL;
    else{
        T=new BiTNode;
        T->data=ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}
void InOrderTraverse(BiTree T)
{//中序遍历
    if(T)
    {
        InOrderTraverse(T->lchild);
        cout<<T->data;
        InOrderTraverse(T->rchild);
    }
}
void PreOrderTraverse(BiTree T)
{//先序遍历
    if(T)
    {
        cout<<T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
void PostOrderTraverse(BiTree T)
{//后序遍历
    if(T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<<T->data;
    }
}
void Copy(BiTree T,BiTree &NewT)
{//二叉树的复制
    if(T==NULL){
        NewT=NULL;
        return;
    }else
    {
        NewT=new BiTNode;
        NewT->data=T->data;
        Copy(T->lchild,NewT->lchild);
        Copy(T->rchild,NewT->rchild);
    }
}
int Depth(BiTree T)
{//树的深度
    if(T==NULL)
        return 0;
    else
    {
        int m=Depth(T->lchild);
        int n=Depth(T->rchild);
        if(m>n) return (m+1);
        else return (n+1);
    }
}
int NodeCount(BiTree T)
{//统计二叉树中结点的个数
    if(T==NULL) return 0;
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int LeafCount(BiTree T)
{//统计二叉树中叶子结点的个数
    if(!T) return 0;
    if(!T->lchild &&!T->rchild){//如果二叉树左子树和右子树皆为空,说明该二叉树根节点为叶子节点,加1.
        return 1;
    }else{
        return LeafCount(T->lchild)+LeafCount(T->rchild);
    }
}
int Node_1_Count(BiTree T)
{//统计二叉树的度为1的结点个数
    if(!T) return 0;
    if((!T->lchild)&&(T->rchild)||(T->lchild)&&(!T->rchild))
        return 1 + Node_1_Count(T->lchild) + Node_1_Count(T->rchild);
    else
        return Node_1_Count(T->lchild) + Node_1_Count(T->rchild);
}
void PrintAllPath(BiTree T, char path[], int pathlen)
{//二叉树中从每个叶子结点到根结点的路径
  int i;
  if(T != NULL) {
    path[pathlen] = T->data; //将当前结点放入路径中
    if(T->lchild == NULL && T->rchild == NULL) {//叶子结点
        for(i = pathlen; i >= 0; i--)
            cout << path[i] << " " ;
      cout << endl;
    }else{
      PrintAllPath(T->lchild, path, pathlen + 1);
      PrintAllPath(T->rchild, path, pathlen + 1);
    }
  }
}
void ExChangeTree(BiTree &T)
{//构造函数，使用递归算法进行左右结点转换
    BiTree temp;
    if(T!=NULL){//判断T是否为空，非空进行转换，否则不转换
        temp=T->lchild;
        T->lchild=T->rchild;//直接交换节点地址
        T->rchild=temp;
        ExChangeTree(T->lchild);
        ExChangeTree(T->rchild);
    }
}
void DblOrderTraverse(BiTree T)
{//二叉树的双序遍历
    if(T)
    {
        cout<<T->data;
        DblOrderTraverse(T->lchild);
        cout<<T->data;//访问两遍
        DblOrderTraverse(T->rchild);
    }
}
int main()
{
    BiTree T;
    //测试例子AB#CD##E##F#GH###
    cout<<"先序遍历输入(以#结束):";
    CreateBiTree(T);
    cout<<"中序遍历输出:";
    InOrderTraverse(T);
    cout<<endl<<"先序遍历输出:";
    PreOrderTraverse(T);
    cout<<endl<<"后序遍历输出:";
    PostOrderTraverse(T);
    cout<<endl<<"树的深度:"<<Depth(T);
    cout<<endl<<"结点的个数:"<<NodeCount(T);
    cout<<endl<<"叶结点的个数:"<<LeafCount(T);
    cout<<endl<<"度为1的结点个数:"<<Node_1_Count(T);
    cout<<endl<<"二叉树中从每个叶子结点到根结点的所有路径："<<endl;
    char path[256];
    int pathlen=0;
    PrintAllPath(T,path,pathlen);//
    //交换二叉树每个结点的左孩子和右孩子
    BiTree tem=T;//直接复制一颗树，在不改变原树的前提下，对临时树进行交换。
    ExChangeTree(tem);
    cout<<"先序遍历输出交换后的结果:";
    PreOrderTraverse(tem);
    cout<<endl<<"双序遍历输出:";
    DblOrderTraverse(T);
    return 0;
}

五、流程图：

Proteus基本操作
    


一、概述
       Proteus软件是英国Lab Center Electronics公司出版的EDA工具软件，支持电路图设计、PCB布线和电路仿真。Proteus支持单片机应用系统的仿真和调试，使软硬件设计在制作PCB板前能够得到快速验证，不仅节省成本，还缩短了单片机应用的开发周期。Proteus 是单片机工程师必须掌握的工具之一。
      Proteus软件分为ARES和ISIS模块，ARES用来制作PCB，ISIS用来绘制电路图和进行电路仿真。 如未特别说明，本文的Proteus指的是Proteus ISIS。
      本文以一个项目为例，演示如何Proteus的基本操作，包括新建工程、添加组件、绘制电路图以及仿真。

二、Proteus基本操作
     项目需求：通过8051单片机的P1口驱动8只LED，P2.1驱动1只LED。
     电路设计思路：在最小系统的基础上，增加LED电路。由于单片机I/O驱动能力弱，每个LED采用一个限流电阻（300Ω）连接到VCC的驱动电路。在使用Proteus画电路图前，先手绘电路图如下，做到心中有数。
      根据以上电路图，需要用到的Proteus元件如下表所示：

元件
符号（Proteus）
参数
普通电容
CAP
30pF
电解电容
CAP-ELEC
10uF
晶体
CRYSTAL
12MHz
电阻
RES
10K、300
单片机
AT89C51
-
按键
BUTTON
-
LED
LED-RED
导通电压2.2V， 10mA
 下面介绍使用Proteus进行电路图设计和仿真的步骤。
1.运行Proteus，默认打开一个空白工程。界面介绍见下图：

2.选择菜单【File>Save Design】，保存工程为LEDCtrl.dsn，保存到一个新建的工程文件夹LEDCtrl里。
技巧：每个工程对应一个文件夹，方便文件管理。

3. 添加元件到元件列表库。单击切换到组件模式后，单击P按钮打开Pick Devices 对话框，在Keywords栏输入元件符号，双击搜索结果中要添加的元件即可。

4.放置元器件。放置顺序：单片机->时钟电路->复位电路->LED驱动电路，原则是由大到小，由左至右。
放置方法：在元件列表选择要放置的元件，单击画布空白区，通过鼠标移动元件到放置地单击即可，若右击则取消放置。
       
放大/缩小画布：鼠标滚轮，向前放大，向后缩小。
快速定位：单击预览区，移动鼠标，再次单击确认。
拖动元件：单击元件，拖到到新位置，再单击空白处。
5.连线。
直接连线：鼠标移动到引脚端子，出现红色虚框后左击确定连线起点，移动鼠标到另一个端子或已有连线处后单击。中间可以单击空白处添加点来确定连线路径。

标号连线：a. 鼠标移动到引脚端子，单击确定起点，双击确定终点。b.使用LBL工具给引线命名（标号）。标号相同的引线将在物理上连接在一起。


6.修改元件的属性（电阻值、电容值、晶体频率）。
示例：

画好的电路图如下图所示：



7.关联仿真程序（.hex）。
程序编写及编译过程见“Keil基本操作”。

8.仿真。
开始仿真：单击开始仿真按钮开始仿真。管脚/节点电平，红色表示高电平，蓝色表示低电平，灰色表示高阻。
暂停仿真：单击暂停仿真按钮。暂停状态可以通过Debug菜单查看单片机的特殊寄存器和内部RAM内容。
停止仿真：单击停止仿真按钮。当代码改变，重新生成.hex后，停止仿真再开始仿真即可，无需再次关联.hex文件。

本博客主要写了用C++读写txt本文的基本操作，最简单的写入和读出两个基本操作。

本程序的功能是向Test.txt文件文件写入字符串"This is a Test12!"和读取字符串"This is a Test12!"，并且将读取到的字符串存到temp变量（char型变量），且输出到控制台窗口进行显示。

 

注意：

1.1当创建ofstream对象后，可以像操作cout一样操作这个对象，也就是可以把ofstream的对象当做cout一样进行输出。

1.2当创建ifstream对象后，可以像操作cin一样操作这个对象，也就是可以把ifstream的对象当做cin一样进行输入。

 

一、用C++读写txt文件程序代码如下：

 

#include<fstream>

#include<iostream>

using namespacestd;

 

int main()

{

   // *************************写txt文件*******************************

   //ofstream OutFile;            //实例一个写文件对象

   //OutFile.open("Test1.xlsx");     //创建一个Test.txt文本，并且打开Test.txt文件

   ofstream OutFile("Test.txt"); //利用构造函数创建txt文本，并且打开该文本

   OutFile << "This is a Test12!";  //把字符串内容"This is a Test!"，写入Test.txt文件

   OutFile.close();            //关闭Test.txt文件

 

   // *************************读txt文件*******************************

   ifstream readFile("Test.txt");

   chartemp[1024] = {0};

   readFile >>temp;           //遇到空格输出停止，空格后的内容无法输出，'\0'是截止符，如图3所示

   //readFile.getline(temp, 8， 0);   //可以输出空格，遇到delim符号才截止。 最后一个参数0表示文本框遇到空字符（ASCLL码为32，文本框不可能有空字符）截止符。不加第三个参数0时，表示'\n'为截止符('\n'也是换行符)。如图4所示

   cout << temp<< endl;

   readFile .close();

 

   system("PAUSE");

   return 0;

}

 

二、程序执行结果

执行写txt文件程序后，在工程文件夹下面，将会生成一个Test文件，如图1所示。并且将字符串"This is a Test12!"写入Test.txt文本文件中，如图2所示。

执行读txt文件程序后，将从Test文本文件读取到的内容存到temp变量（char型变量）中，同时输出到控制台窗口，如图3和图4所示。图3只能输出连续字符串，遇到空格或者'/0'截止。图4将输出Test文本文件内所有内容，直到遇到delim才会截止输出。

 



图1  生成Test文本

 

 

 



图2  Test文本写入的内容

 



图3  Test文本读出的内容（'/0'是截止符）

 



图4  Test文本读出的内容（delim是截止符）

 

参考内容：

http://www.cnblogs.com/uniqueliu/archive/2011/08/03/2126545.html

前几天找实习的时候，一个面试官给我留了一个题，做一个链表demo，要求实现创建、插入、删除等操作。

链表是一种常见的数据结构，它是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

我是用C++代码来写的。首先，定义一个linklist.h文件，该文件定义了链表的结点和链表支持的方法。如下所示：

 

//linklist.h：定义链表结点和方法。
#include <string>
using namespace std;

struct Info
{
	string name;	//姓名
	int id;		//学号
};
//链表定义
struct Node
{
	Info val;
	Node *next;
	Node(Info x):val(x),next(NULL) {}
};

class LinkList
{
public:
	//构造函数
	LinkList();	
	//在链表头部插入结点
	void InsertHead(Info val);
	//插入结点
	void Insert(Info val,int pos);
	//删除结点
	void Remove(Info val);
	//得到链表长度
	int Length();
	//链表反序
	void Reverse();
	//查找结点位置
	int Find(Info val);
	//打印链表
	void Print();
	//析构函数
	~LinkList();
private:
	Node *head;
	int length;
};


 

然后，定义一个linklist.cpp文件，是链表方法的实现。如下所示：

//linklist.cpp：链表方法的实现。
 #include "stdafx.h"
#include <iostream>
#include "linklist.h"
using namespace std;

//构造函数
LinkList::LinkList()
{
	head = NULL;
	length = 0;
}

//析构函数
LinkList::~LinkList()
{
	Node *temp;
	for(int i=0;i<length;i++)
	{
		temp=head;
		head=head->next;
		delete temp;
	}
}

//得到链表长度
int LinkList::Length()
{
	return length;
}

//在链表头部插入结点
void LinkList::InsertHead(Info val)
{
	Insert(val,0);
}

//插入结点
void LinkList::Insert(Info val,int pos)
{
	if(pos<0)
	{
		cout<<"pos must be greater than zero"<<endl;
		return;
	}
	int index = 1;
	Node *temp = head;
	Node *node = new Node(val);
	if(pos == 0)
	{
		node->next = temp;
		head = node;
		length++;
		return;
	}
	while(temp!=NULL && index<pos)
	{
		temp=temp->next;
		index++;
	}
	if(temp == NULL)
	{
		cout<<"Insert failed"<<endl;
		return;
	}
	node->next = temp->next;
	temp->next = node;
	length++;
}

//删除结点
void LinkList::Remove(Info val)
{
	int pos = Find(val);
	if(pos == -1)
	{
		cout<<"Delete failed"<<endl;
		return;
	}
	if(pos == 1)
	{
		head = head->next;
		length--;
		return;
	}
	int index = 2;
	Node *temp = head;
	while(index < pos)
		temp = temp->next;
	temp->next = temp->next->next;
	length--;
}

//查找结点位置
int LinkList::Find(Info val)
{
	Node *temp = head;
	int index = 1;
	while(temp!=NULL)
	{
		if(temp->val.name == val.name && temp->val.id == val.id)
			return index;
		temp = temp->next;
		index ++;
	}
	return -1; //不存在返回-1
}

//链表反序
void LinkList::Reverse()
{
	if(head==NULL)
        return;
    Node *curNode=head,*nextNode=head->next,*temp;
    while(nextNode!=NULL)
	{
        temp=nextNode->next;
        nextNode->next=curNode;
        curNode=nextNode;
        nextNode=temp;
    }
    head->next=NULL;
    head=curNode;
}

//打印链表
void LinkList::Print()
{
	if(head == NULL)
	{
		cout<<"LinkList is empty"<<endl;
		return;
	}
	Node *temp = head;
	while(temp!=NULL)
	{
		cout<<temp->val.name<<","<<temp->val.id<<endl;
		temp=temp->next;
	}
	cout<<endl;
}


最后，定义一个main.cpp，用来测试链表功能，如下所示：

// main.cpp : 测试链表功能。
#include "stdafx.h"
#include <iostream>
#include <string>
#include "linklist.h"
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	LinkList head;
	Info val1,val2,val3,val4;
	val1.id =1,val1.name="Kevin",val2.id=2,val2.name="Cathy",val3.id=3,val3.name="Lucy",val4.id=4,val4.name="Gravin";
	
	//测试插入功能
	cout<<"Insert test:"<<endl;
	head.InsertHead(val1);
	head.Print();
	head.Insert(val2,1);
	head.Print();
	head.Insert(val3,4);
	head.Print();
	head.InsertHead(val3);
	head.Insert(val4,2);
	head.Print();
	
	//测试反序功能
	cout<<"reverse test:"<<endl;
	head.Reverse();
	cout<<"reversed linklist is:"<<endl;
	head.Print();
	
	//测试删除功能
	cout<<"remove test:"<<endl;
	cout<<"the length of linklist is:"<<endl;
	cout<<head.Length()<<endl;
	head.Remove(val4);
	head.Print();
	cout<<"the length of linklist is:"<<endl;
	cout<<head.Length()<<endl;
	head.Remove(val4);
	head.Print();
	return 0;
}


测试结果如下图：