提示：点击实验名称，查看具体实验内容，再次点击，收起详细说明；
了解C++类的构成。
掌握声明类的方法，类和类的成员的概念以及定义对象的方法。
掌握成员函数的定义。
熟悉构造函数和析构函数。
了解C++的封装性。
编写一个程序，设计一个类score用于统计一个班的学生成绩，其中使用一个静态数据成员sumfs存储总分和一个静态成员函数reumfs返回该总分。
建立一个对象数组，内放5个学生的数据（学号、成绩），设计一个函数Max（），用来计算5个学生中成绩最高者，并设计一个Print（）函数输出其学号。
定义一个通讯录类，该类中有数据成员姓名、地址、电话、邮政编码等，成员函数有构造函数、ChangeName（）、Display（）函数，构造初始化每个成员，ChangeName（）函数用来修改姓名，Display（）函数把完整的数据打印出来。
类中声明的各种构造函数
class CArea
{
//…
public：
CArea（）{x = 0；y = 0；} //声明无参数的构造函数
CArea（int rx，int ry） //声明带两个整型数据的构造函数
CArea（float rr）{r = rr；} //声明带一个浮点参数的构造函数
CArea（float rr，char ra[ ]） //声明带两个参数的构造函数
}；
建立一个学生类
class Student //定义学生类
{
int Num； //存放学号
float Score； //存放成绩
public：
void Set（）； //建立信息函数
int Find（int n）； //查找函数，找到返回1，否则返回-1
void Display（）； //显示信息
}；
建立学生信息
void Student：：Set（）
{
cin >> Num >> Score；
}
输出学生信息
void Student：：Display（）
{
cout <<“学号 ：”<< Num <<“ 成绩：”<< Score << endl；
}
掌握友元的说明与定义。
掌握友元函数、友元成员、友元类的概念及设计方法。
掌握函数重载的概念和使用方法；
掌握运算符重载的方法。
掌握引用的概念和语法；
掌握用引用传递函数参数的方法。
设计一个直线类Line，其中包含三个数据成员a、b和c，一个求两直线交点的友元函数setpoint（）和显示数据成员的disp（）成员函数，并用数据进行测试。
定义一个复数类的加法与减法，重载“＋”运算符，使之能够执行下列运算：
Complex a（5，5），b（10，10），c（0，0）
C = a+b；
C = 4.1+a；
C = b+5；
编写一乘法程序，要求使用对象引用作函数参数。
友元的声明
class point
{
int x，t；
public：
point（int，int）；
friend void print（）； //声明print（）是point类的友元函数
friend class A； //声明A是point类的友元类
}；
声明重载运算符
class Complex
{
double real;
double imag;
public:
……
Complex operator+（Complex &m1）；//重载运算符“+”
//重载运算符“<<”
friend ostream & operator<<（ostream &out，Complex &m）；
//重载运算符“>>”
friend istream & operator>>（istream &in，Complex &m）；
};
使用普通变量的引用来传递参数。
#include“iostream.h”
void swap（int &x，int &y） //交换两个变量的值
{
int temp；
temp = x；
x = y；
y = temp；
}
void main（）
{
int a = 1，b = 2；
cout <<“a =”<< a <<“b =”<< b <<“\n”； //输出a，b的值
swap（a，b）； //交换a，b的值
cout <<“a =”<< a <<“b =”<< b <<“\n”；//输出交换后a，b的值
return 1；
}
掌握继承和派生类的概念。
掌握派生类对基类的继承。
了解多继承。
编写一个程序，定义一个汽车类vehicle，它具有一个需传递参数的构造函数，类中的数据成员包括：车轮个数和车的重量，它们都放在保护段中；定义轿车类car是汽车类vehicle的私有派生类，其中包含载人数；再定义卡车类truck是汽车类vehicle的私有派生类，其中包含载人数和车载重量。要求每个类都有相应的数据输出。
编写一个程序，其中有一个书类book，该类的数据成员包括：书号、书名、定价、出版社及出版时间；有一个作者类author，该类的数据成员包括：姓名、年龄和写作时间，每个类都有相应的数据输入、输出。以此两个类为基类，派生出图书查询卡card，并增加一个数据成员表示书籍系统名称，以及一个可以显示系统名称、书名、作者、作者年龄、出版时间、出版社和定价等数据的函数。
设计一个大学的类系统，学校中有学生、教师，每种人员都有自己的特性，他们之间有相同的地方（以person类为基类，有姓名、编号），又有各自不同的特性（学生：专业、平均成绩；教师：职称、工资）。利用继承机制定义这个系统中的各个类，要求输入姓名等信息后再将这些信息输出。
定义派生类
假设基类base1 、base2 是已经声明的类，下面的语句声明了一个名为dr1的派生类。
class dr1：public base1，private base2
{
public：
dr1( );
~dr1( );
}；
派生类构造函数、析构函数实例（多继承、含有子对象）。
#include“iostream.h”
class B1 //基类B1定义，构造函数有参数
{
public：
B1(int i){cout <<“constructing B1”<< i << end;}//B1的构造函数
~B1( ) {cout <<“destructing B1”<< endl;} //B1的析构函数
};
class B2 //基类B2定义，构造函数有参数
{
Public:
B2(int j){cout <<“constructing B2”<< j << endl;}//B2的构造函数
~B2( ) {cout <<“destructing B2”<< end;} //B2的析构函数
};
class B3 //基类B3定义，构造函数无参数
{
Public:
B3( ){cout <<“constructing B3 *”<< endl;} //B3的构造函数
~B3( ){cout <<“destructing B3”<< endl;} //B3的析构函数
}；
class C:public B2，public B1，public B3 //派生新类C定义
{
private：
B1 memberB1；
B2 memberB2；
B3 memberB3；
public：
C(int a，int b，int c，int d):B1(a),memberB2(d),memberB1(c),B2(b)
{ cout <<“constructing C ”<< endl；}
};
void main( )
{
C obj(1，2，3，4);
}
了解多态性在C++中的体现。
掌握虚函数的应用。
了解抽象类。
定义一个图形类为抽象类，其具有求对象的面积和周长等基本功能（Area（），Perim（）），在此基础上派生出圆形、三角形和矩形，分别求出它们的周长和面积。
设计一个程序，通过该程序能找出优秀学生（成绩在90分以上）和优秀教师（发表论文在3篇以上）。在输入一系列学生或教师的记录后（姓名 、成绩），将他们中优秀者姓名输出出来。
定义一个基类为哺乳动物类Mammal，其中有数据成员年龄、重量、品种，有成员函数move（）、speak（）等，以此表示动物的行为。由这个基类派生出狗、猫、马、猪等哺乳动物，它们有各自的行为。编程分别使各个动物表现出不同的行为。
要求如下：
从基类分别派生出各种动物类，通过虚函数实现不同动物表现出的不同行为。
今有狗CAIRN：3岁，3kg；DORE：4岁，2kg；猫CAT：2岁，4kg；马：HORSE，5岁，60kg；猪：PIG，2岁，45kg
设置一个Mammal类数组，设计一个屏幕菜单，选择不同的动物或不同的品种，则显示出动物相对应的动作，直到选择结束。
对应的动作中要先显示出动物的名称，然后显示年龄、重量、品种、叫声及其他特征。
从基类的图形类中派生出两个类。一个派生类是矩形类，在该类中，基类的x， y做作矩形的长和宽；另一个派生类是圆类，在该类中，新添加了成员是半径radius，半径的值等于x，y的坐标到原点的距离。
程序实现：
#include <iostream.h>
#include <math.h>
class Graph //定义一个图形基类
{
double x，y；
public：
Graph（double xx，double yy）
{
x = xx；
y = yy；
}
virtual double Area（）= 0； //纯虚函数
virtual void Display（）= 0；//纯虚函数
}；
class Rect：public Graph //由图形类派生出矩形类
{
double length，width；
public：
Rect（double x，double y）：Graph（x，y）
{
length = x；
width = y；
}
double Area（）
{
return length*width；
}
void Display（）{cout <<“矩形面积=”；}
}；
class Circle：public Graph //由图形类派生出圆类
{
double radius；
public：
Circle（double x，double y）：Graph（x，y）
{
radius = sqrt（x*x+y*y）；
}
double Area（）
{
return 3.1416*radius*radius；
}
void Display（）{cout <<“圆形面积=”；}
}；
掌握顺序存储结构和链式存储结构的基本思想。
掌握顺序表和单链表的基本操作。
对给定的单链表L，设计一个算法，删除L中值为x的结点的直接前驱结点。
已知单链表中各结点的元素值为整型并且有序，设计算法删除链表中所有大于3且小于10的元素，并释放被删除结点的存储空间。
已知两个单链表LA和LB分别表示两个集合，其元素递增排列，设计算法求出LA和LB的交集C，要求C同样以元素递增的单链表形式存储。
顺序表的定义
typedef struct
{
DataType data[ListSize]；
int length；
}SeqList；
结点类定义：
class ListNode
｛
friend class List； //将List类声明为友元类
private：
int data； //数据元素域
ListNode *link； //链指针域
};
链表类定义
class List
{
public：
//链表的常用操作
……
private：
ListNode *head； //链表表头指针
};
对顺序表进行建立、插入、删除、查找等操作。
#include“iostream. h”
#define MaxSize 100
typedef int DataType；
class SeqList
{
DataType list[MaxSize]；
int length；
public:
SeqList（）{length = 0；}
void SLCreat（int n）； //创建顺序表
//在顺序表L中的i位置插入数据元素x
void SLInsert（int i，DataType x）；
void SLDelete（int i）； //删除第i位置的数据元素
int SLGetLength（）{return length；}//获取长度
int SLFind（DataType x）； //查找数据元素x在表中的位置
DataType SLGet（int i）； //获取i位置元素的数值
int SLIsEmpty（）； //判断顺序表是否为空
void SLPrint（）； //将顺序表显示在屏幕上
}；
//创建顺序表
void SeqList：：SLCreat（int n）
{
DataType x；
cout<<“请输入数据元素值：”；
for（int i = 0；i < n；i++）
{
cin >> x；
list[i] = x；
length++；
}
}
//在顺序表L中的i位置插入数据元素x
void SeqList：：SLInsert（int i，DataType x）
{
int k；
if（length >= MaxSize）
cout <<“表已满，无法插入！”<<endl；
else if（i < 0 || i > length）
cout <<“参数i不合理！”<<endl；
else
{
for（k = length；k > i；k--）
{ list[k] = list [k-1]；}
list[i] = x；
length++；
}
}
//删除第i位置的数据元素
void SeqList：：SLDelete（int i）
{
int k；
if（!SLIsEmpty（））
cout <<“表已空，无法删除！”<< endl；
else if（i < 0 || i > length）
cout <<“参数i不合理！”<< endl；
else
{
for（k = i-1；k < length；k++）
list[k] = list[k+1]；
length--；
}
}
//查找数据元素x在表中的位置
int SeqList：：SLFind（DataType x）
{
int i = 0；
while（i < length && list[i]!= x） i++；
if（i >= length）return –1；
else return i+1；
}
//获取i位置元素的数值
DataType SeqList：：SLGet（int i）
{
if（i < 0 || i > length）
{
cout <<“参数i不合理！”<< endl；
return 0；
}
else
return list[i-1]；
}
//判断顺序表是否为空
int SeqList：：SLIsEmpty（）
{
if（length <= 0）return 0；
else return 1；
}
//将顺序表显示在屏幕上
void SeqList：：SLPrint（）
{
if（!SLIsEmpty（））
cout <<“空表！”<< endl；
else
for（int i = 0；i < length；i++）
cout << list[i]<<“ ”；
cout << endl；
}
掌握堆栈和队列的基本概念。
掌握堆栈和队列的基本操作。
假设以顺序栈存储结构实现一个双向栈，即在一个一维数组A [m]的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点A [ 0 ]和A [m - 1]。试构造一个类，并要求实现这个双向栈的3个基本操作：
初始化操作；
入栈操作；
出栈操作。
试编写一个算法，建立一个学生成绩栈，要求从键盘上输入N个整数，按照下列要求分别进入不同栈：
若输入的整数x小于60，则进入第一个栈；
若输入的整数x大于等于60并小于100，则进入第二个栈；
若输入的整数x大于100，则进入第三个栈；
分别输出每个栈的内容。
假设以数组A [m]存放循环队列中的元素，同时设置一个标志tag，当队头指针（front）的队尾指针（rear）相等时，tag = 1表示队满。试给出该循环队列相应的入队和出队算法。
定义一个顺序栈类
typedef int ElemType；
class SeqStack
{
unsigned height； //栈高
int top； //栈顶指针
ElemType *elements； //一维数组指针，用于存放栈中元素
int maxsize； //栈的最大栈高
public：
SeqStack(int size); //构造函数，size用来设置栈的大小
~SeqStack( ){delete []elements； //析构函数
void PushStack(ElemType x); //进栈函数，将元素x压入栈中
ElemType PopStack(ElemType x);//出栈函数，将栈顶元素值放入x
void ClearStack( ){top = -1；}//清栈函数，用于释放栈所占的内存空间
bool IsFullStack( ){return top == maxsize-1;}//判断栈是否为满
bool IsEmptyStack( ); //判断栈是否为空
void PrintStack( ); //将栈中元素输入到屏幕上
};
初始化一个空栈
SeqStack::SeqStack(int size)
{
height = 0;
top = -1;
maxsize = size; //最大栈高
elements = new ElemType[size];
}
进栈函数
void SeqStack::PushStack(ElemType x)
{
if(IsFullStack())
cout <<"栈已满！";
else
{
elements[++top] = x;
height++;
}
}
出栈函数
ElemType SeqStack::PopStack(ElemType x)
{
x = elements[top];
top--;
height--;
return x;
}
判断栈是否为空
bool SeqStack::IsEmptyStack()
{
return(height == 0)? true:false;
}
将栈中元素输入到屏幕上
void SeqStack::PrintStack()
{
while(IsEmptyStack()== false)
{
cout << elements [top] <<" ";
top--;
height--;
}
cout << endl;
}
队列类定义
#define QUENESIZE 100
class CirQueue
{
int head; //队头指针
int tail; //队尾指针
int *elements;//存放队列元素的数组
int maxsize; //队列最大可容纳的元素个数
int qsize; //队列长度
public:
CirQueue();
~CirQueue(){delete elements;}
void PushTail(int &x); //插入,将元素插入在队尾
int PopFront(int &x); //删除,从队头取一个元素
void Clear(){head = tail;} //清空队列
void Put(int x){PushTail(x);} //进队,将新元素插入在队尾
void Get(int x){PopFront(x);} //出队,从队头取一个元素
void InQueue(int &item); //插入函数
bool QueueIsFull(){return(tail+1)% maxsize == head;} //判断队列是否为满
bool QueueIsEmpty(){return head == tail;} //判断队列是否为空
void Print();
};
队列设置为空队列
CirQueue::CirQueue()
{
head = tail = 0;
maxsize = QUENESIZE;
qsize = 0;
elements = new int [maxsize]; //给队列分配内存空间
}
将元素插入在队尾
void CirQueue::PushTail(int &x)
{
if(QueueIsFull())
cout <<"队列已满!"<< endl;
else
{
tail =(tail+1)% maxsize;//尾指针加1
elements[tail] = x; //给队尾赋值
qsize++; //队长加1
}
}
从队头取一个元素
int CirQueue::PopFront(int &x)
{
if(QueueIsEmpty())
{
cout <<"队列已空!"<< endl;
return -1;
}
else
{
head =(head+1)% maxsize;//头指针加1
x = elements[head];
qsize--;
return x;
}
}
输出队列函数
void CirQueue::Print()
{
int m,s = qsize;
for(int i = 0;i < s;i++)
{
m = PopFront(elements[i]);
cout << m <<" ";
}
cout << endl;
}
判断队列是否为满
bool QueueIsFull(){return(tail+1)% maxsize == head;}
判断队列是否为空
bool QueueIsEmpty(){return head == tail;}
掌握树、森林及二叉树的基本概念。
掌握树、二叉树的存储结构。
掌握树、二叉树的遍历。
树和森林与二叉树之间的转换。
以二叉链表作为二叉树的存储结构，试利用栈的基本操作写出先序遍历的非递归形式算法。
以二叉链表作为二叉树的存储结构，求二叉树中以元素值为x的结点为根的子树的深度。
二叉树结点类的定义
class BinTreeNode //二叉树结点类的定义
{
char data; //结点的数据域
BinTreeNode *Lchild; //左孩子指针
BinTreeNode *Rchild; //右孩子指针
BinTreeNode *root;
public:
BinTreeNode(){root = NULL;}
void creattree(BinTreeNode *t,char *x); //
BinTreeNode *GetRoot(){return root;} //返回根结点指针
void Preorder(BinTreeNode *Bt);//前序遍历
void inord(BinTreeNode *Bt); //中序遍历
void postord(BinTreeNode *Bt);//后序遍历
};
建立广义表二叉树
void BinTreeNode::creattree(BinTreeNode *t,char *x)
{
BinTreeNode *s[10];
int top = -1;
BinTreeNode *p;
int k;
char ch;
ch =*x;
while(ch!='#')
{
switch(ch)
{
case '(': top++;s[top]= p;k =1;break;
case ')': top--;break;
case ',': k = 2;break;
default: p = new BinTreeNode;
p -> data = ch;p -> Lchild = p -> Rchild = NULL;
if(root == NULL)
root = p;
else
{
switch(k)
{
case 1:s[top]->Lchild = p;break;
case 2:s[top]->Rchild = p;break;
}
}
}
ch =*++x;
}
}
前序遍历
void BinTreeNode::Preorder(BinTreeNode *root)
{
if(root != NULL)
{
cout << root-> data <<" ";
Preorder(root->Lchild);
Preorder(root->Rchild);
}
}
中序遍历
void BinTreeNode::inord(BinTreeNode *Bt)
{
if(Bt!= NULL)
{
inord(Bt->Lchild);
cout << Bt->data <<" ";
inord(Bt->Rchild);
}
}
后序遍历
void BinTreeNode::postord(BinTreeNode *Bt)
{
if(Bt!= NULL)
{
postord(Bt->Lchild);
postord(Bt->Rchild);
cout << Bt->data <<" ";
}
}
返回根结点指针
BinTreeNode *GetRoot(){return root;}
掌握各种排序方法的排序过程。
了解一些排序算法的实现(如插入排序、选择排序、冒泡排序、快速排序、堆排序等)。
设计一个算法，在单链表存储结构上实现冒泡排序。
学生的考试成绩表由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生信息实现：
1）按分数高低次序，打印出每个学生在考试中的排名，分数相同的为同一名次，同一名次的学生按学号从小到大排列。
2）按照名次列出每个堂皇的名次、学号、姓名和成绩。
排序类定义
typedef int DataType;
class SeqList
{
DataType list[MaxSize];
int length;
public:
SeqList( ) {length = 0;}
void SLCreat(int n); //创建顺序表
void InsSort( ); //直接插入排序
void ShellSort( ); //希尔排序
void SelectSort( ); //简单选择排序
void BubbleSort( ); //冒泡排序
void QuickSort( ); //快速排序
void QuickSort(int low, int high); //快速排序
int partition(int i, int j);
void SLPrint( ); //将顺序表显示在屏幕上
};
创建顺序表
void SeqList::SLCreat(int n)
{
DataType x;
length = 0;
cout <<"请输入数据元素值: ";
for(int i = 0; i < n; i++)
{
cin >> x;
list[i] = x;
length++;
}
}
直接插入排序
void SeqList::InsSort( )
{
SLCreat(5);
DataType x;
int i, j;
for(i = 0; i < length; i++)
{
x = list[i];
for(j = i-1; j >= 0; j--)
if(x < list[j])
list[j+1] = list[j];
else break;
list[j+1] = x;
}
}
希尔排序
void SeqList::ShellSort( )
{
SLCreat(5);
DataType x;
int i, j, d, n;
n = length;
for(d = n/2; d >= 1; d/= 2)
{ //按不同分量进行排序
for(i = d; i < n; i++)
{ //将list[i]元素直接插入到对应分组的有序表中
x = list[i];
for(j = i-d; j >= 0; j-= d)
{ if(x < list[j])
list [j+d] = list[j];
else break;
}
list[j+d] = x;
}
}
}
简单选择排序
void SeqList::SelectSort( )
{
SLCreat(5);
DataType x;
int i, j, k;
for(i = 0; i < length; i++)
{
k = i; //用保存当前得到的最小排序码元素的下标，初值为I
for(j = i+1; j < length; j++)
{ //从当前排序区间中顺序查找出具有最小排序码的元素list[k]
if(list[j]<list[k])
k = j;
}
if(k!=i)
{ //把list[k]对调到该排序区间的第一个位置
x = list[i];
list[i] = list[k];
list[k] = x;
}
}
cout <<"简单选择排序结果: ";
SLPrint( );
}
冒泡排序
void SeqList::BubbleSort( )
{
SLCreat(5);
DataType x;
int i, j, flag;
for(i = 1; i < length-1; i++)
{
flag = 0;
for(j = length-1; j >= i; j--)
if(list[j] < list[j-1])
{
x = list[j-1];
list[j-1] = list[j];
list[j] = x;
flag = 1;
}
if(flag==0) return;
}
}
快速排序
void SeqList::QuickSort( )
{
SLCreat(5);
QuickSort(0, 4);
cout <<"快速排序结果: ";
SLPrint( );
}
void SeqList::QuickSort(int low, int high)
{
int pos;
if(low < high)
{
pos = partition(low, high);
QuickSort(low, pos-1);
QuickSort(pos+1, high);
}
}
int SeqList::partition(int i, int j)
{
DataType pivotkey;
pivotkey = list[i];
while(i < j)
{
while(i < j&&list[j] >= pivotkey) --j;
if(i < j) list[i++] = list[j];
while(i < j&&list[i] <= pivotkey) ++i;
if(i < j) list[j--] = list[i];
}
list[i] = pivotkey;
return i;
}
将顺序表显示在屏幕上
void SeqList::SLPrint( )
{
for(int i = 0; i < length; i++)
cout << list[i] <<" ";
cout << endl;
}