第一篇：数据结构(c++版)实验参考书
前 言
《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。
一、实验目的
更好的理解算法的思想、培养编程能力。
二、实验要求
1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。
2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。
3、实验结束后总结实验内容、书写实验报告。
4、遵守实验室规章制度、不缺席、按时上、下机。
5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取消本次上机资格，平时成绩扣10分。
6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。
三、实验环境 Qt或 VC++6.0
四、说明
1、本实验的所有算法中元素类型可以根据实际需要选择。
2、实验题目中带＊者为较高要求，学生可自选；其余部分为基本内容，应尽量完成（至少完成70%，否则实验不合格）。
3、数据结构是很多高校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在学习过程中注意各种算法的理解，以便为考研做一定的准备。
五、实验报告的书写要求
1．明确实验的目的及要求；
2．记录实验的输入数据和输出结果；
3．说明实验中出现的问题和解决过程；
4．写出实验的体会和实验过程中没能解决的问题；
六、参考书目
《数据结构》（C++语言描述）王红梅等 清华大学出版社
《DATA STRUCTURE WITH C++》 William Ford,William Topp 清华大学出版社（影印版）
实验一 线性表的操作
实验类型：验证性 实验要求：必修 实验学时： 2学时
一、实验目的：
参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。
二、实验要求：
1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1．设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素1，2，3，„，10，然后删除数据元素6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。
2．设计一个带头结点的单链表类，要求：
(1)生成一个整数线性表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。
(2)设计一个测试主函数，实际运行验证所设计单链表类的正确性。3．设计一个不带头结点的单链表类，要求：
(1)不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。
(提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他位置插入和删除其他位置结点时的不同情况。)(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。4．设计一个带头结点的循环单链表类，实现约瑟夫环问题；
问题描述：设编号为1,2,„，n(n>0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。
测试数据：
n=7,7个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m=20 *5．设计一个带头结点的循环双向链表类，要求：
(1)带头结点循环双向链表类的成员函数包括：取数据元素个数、插入、删除、取数据元素。
(2)设计一个测试主函数，实际运行验证所设计循环双向链表类的正确性。*6．设计一个单链表实现一元多项式求和问题。要求：
（1）设计存储结构表示一元多项式；
（2）设计算法实现一元多项式相加。
四、程序样例
顺序表类定义：将该类保存在文件SeqList.h中。
const int MaxSize=100;//100只是示例性的数据，可根据实际问题具体定义 template
//定义模板类SeqList class SeqList { public:
SeqList(){length=0;}
//无参构造函数
SeqList(T a[ ], int n);
//有参构造函数
~SeqList(){ }
//析构函数为空
int Length(){return length;} //求线性表的长度
T Get(int i);
//按位查找，取线性表的第i个元素
int Locate(T x);
//按值查找，求线性表中值为x的元素序号
void Insert(int i, T x);//在线性表中第i个位置插入值为x的元素
T Delete(int i);
//删除线性表的第i个元素
void PrintList();
//遍历线性表，按序号依次输出各元素 private:
T data[MaxSize];
//存放数据元素的数组
int length;
//线性表的长度 };template
SeqList:: SeqList(T a[ ], int n){
if(n>MaxSize)throw “参数非法”;
for(i=0;i data[i]=a[i]; length=n;} template T SeqList::Get(int i){ if(i<1 && i>length)throw “查找位置非法”; else return data[i-1];} template int SeqList::Locate(T x){ for(i=0;i if(data[i]==x)return i+1;//下标为i的元素等于x，返回其序号i+return 0; //退出循环，说明查找失败 } template void SeqList::Insert(int i, T x){ if(length>=MaxSize)throw “上溢”; if(i<1 | | i>length+1)throw “位置”;for(j=length;j>=i;j--) data[j]=data[j-1]; //注意第j个元素存在数组下标为j-1处 data[i-1]=x;length++;} template T SeqList::Delete(int i){ if(length==0)throw “下溢”; if(i<1 | | i>length)throw “位置”; x=data[i-1]; for(j=i;j data[j-1]=data[j]; //注意此处j已经是元素所在的数组下标 length--; return x;} 链表类定义：将该类保存在文件LinkList.h中。template T data; Node } template LinkList(T a[ ], int n);//建立有n个元素的单链表 ~LinkList(); //析构函数 int Length(); //求单链表的长度 T Get(int i); //取单链表中第i个结点的元素值 int Locate(T x); //求单链表中值为x的元素序号 void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点 T Delete(int i); //在单链表中删除第i个结点 void PrintList(); //遍历单链表，按序号依次输出各元素 private: Node LinkList:: ~LinkList(){ p=first; //工作指针p初始化 while(p) //释放单链表的每一个结点的存储空间 { q=p; //暂存被释放结点 p=p->next;//工作指针p指向被释放结点的下一个结点，使单链表不断开 delete q; } } template T LinkList::Get(int i) { p=first->next;j=1;//或p=first;j=0; while(p && j { p=p->next; //工作指针p后移 j++; } if(!p)throw “位置”;else return p->data; } template void LinkList::Insert(int i, T x) { p=first;j=0; //工作指针p初始化 while(p && j //工作指针p后移 j++;} if(!p)throw “位置”;else { s=new Node s->next=p->next; //将结点s插入到结点p之后 p->next=s;} } template T LinkList::Delete(int i){ p=first;j=0;//工作指针p初始化 while(p && j //查找第i-1个结点 { p=p->next; j++; } if(!p | |!p->next)throw “位置”;//结点p不存在或结点p的后继结点不存在 else { q=p->next;x=q->data;//暂存被删结点 p->next=q->next;//摘链 delete q; return x;} } template LinkList:: LinkList(T a[ ], int n) { first=new Node first->next=NULL;//初始化一个空链表 for(i=0;i s=new Node s->next=first->next; //插入到头结点之后 first->next=s; } } template LinkList:: LinkList(T a[ ], int n) { first=new Node //生成头结点 r=first; //尾指针初始化 for(i=0;i { s=new Node r->next=s;r=s; //插入到终端结点之后 } r->next=NULL; //单链表建立完毕，将终端结点的指针域置空 } 1．#include #include void main() { int r[ ]={1,2,3,4,5,6,7,8,9,10}; SeqList cout<<”执行删除操作前数据为：”< a.PrintList(); a.Delete(6); cout<<”执行删除操作后数据为：”< } 2． #include #include void divid(LinkList &L) { Node h=new Node p=L.first->next;q=L.first; while(p) { if(p->data%2!=0){ q=p;p=p->next;} else {q=p;p=p->next;q-next=h.first->next;h.first->next=q;} } p=L.first->next; while(p->next!=Null) {p=p->next;} p->next= h.first->next; delete h; } void main() { int r[ ]={1,-2,3,-4,-5,6,-7,8,9,10}; LinkList cout<<”执行操作前数据为：”< List.PrintList(); divid(List); cout<<”执行操作后数据为：”< 6．void Add(LinkList if(p->exp //第1种情况 pre=p; p=p->next; } else if(p->exp>q->exp){ //第2种情况，将结点q插入到结点p之前 v=q->next; pre->next=q; q->next=p; q=v; } else { //第3种情况 p->coef =p->coef+q->coef;//系数相加 if(p->coef ==0){ //系数为0，删除结点p和结点q pre->next=p->next;//删除结点p delete p; p=pre->next; } else { //系数不为0，只删除结点q pre=p; p=p->next; } qre->next=q->next //删除结点q delete q; q=qre->next;} if(q)pre->next=q;//将结点q链接在第一个单链表的后面 delete B.first; //释放第二个单链表的头结点所占的内存 } 实验二 栈、队列、串的操作 实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的： 参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。 二、实验要求： 1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1.堆栈类测试和应用问题。要求： (1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 (2)定义数据元素的数据类型为如下形式的结构体： typedef struct { char taskname[10];//任务名 int taskno; //任务号 ｝DataType； 设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。2.队列类测试和应用问题。要求： 设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。3．设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。 *4.设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。*5.设计串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回０。并要求设计主函数进行测试。 一个测试例子为：S＝”I am a student”，T=”student”，V=”teacher “。 四、程序样例 1． 顺序栈类的定义 const int StackSize=10; //10只是示例性的数据，可以根据实际问题具体定义 template //定义模板类SeqStack class SeqStack { public: SeqStack(){top=-1;} //构造函数，栈的初始化 ~SeqStack(){ } //析构函数 void Push(T x); //将元素x入栈 T Pop(); //将栈顶元素弹出 T GetTop(){if(top!=-1)return data[top];} //取栈顶元素（并不删除） bool Empty(){top==-1? return 1: return 0;} //判断栈是否为空 private: T data[StackSize];//存放栈元素的数组 int top; //栈顶指针，指示栈顶元素在数组中的下标 };template if(top== StackSize-1)throw “上溢”; top++; data[top]=x; } template if(top==-1)throw “下溢”; x=data[top--]; return x; } 2． 链式栈类的定义 template LinkStack(){top=NULL;} //构造函数，置空链栈 ~LinkStack(); //析构函数，释放链栈中各结点的存储空间 void Push(T x); //将元素x入栈 T Pop(); //将栈顶元素出栈 T GetTop(){if(top!=NULL)return top->data;} //取栈顶元素（并不删除） bool Empty(){top==NULL? return 1: return 0;} //判断链栈是否为空栈 private: Node template void LinkStack::Push(T x) { s=new Node s->next=top;top=s; //将结点s插在栈顶 } template T LinkStack::Pop() { if(top==NULL)throw “下溢”; x=top->data; //暂存栈顶元素 p=top;top=top->next; //将栈顶结点摘链 delete p; return x; } template LinkStack::~LinkStack() { while(top){ p=top->next; delete top; top=p;} } 3．双栈类的定义 const int StackSize=100;//100只是示例数据，需根据具体问题定义 template BothStack(){top1=-1;top2=StackSize;} //构造函数，将两个栈分别初始化 ~BothStack(){ } //析构函数 void Push(int i, T x); //将元素x压入栈i T Pop(int i); //对栈i执行出栈操作 T GetTop(int i); //取栈i的栈顶元素 bool Empty(int i); //判断栈i是否为空栈 private: T data[StackSize]; //存放两个栈的数组 int top1, top2; //两个栈的栈顶指针，分别指向各自的栈顶元素在数组中的下标 };template //将栈1的栈顶元素出栈 if(top1==-1)throw “下溢”; return data[top1--]; } if(i==2){ //将栈2的栈顶元素出栈 if(top2==StackSize)throw ''下溢“; return data[top2++]; } } 4.循环队列类定义 const int QueueSize=100;//定义存储队列元素的数组的最大长度 template //定义模板类CirQueue class CirQueue { public: CirQueue(){front=rear=0;} //构造函数，置空队 ~ CirQueue(){ } //析构函数 void EnQueue(T x); //将元素x入队 T DeQueue(); //将队头元素出队 T GetQueue(); //取队头元素（并不删除） bool Empty(){front==rear? return 1: return 0;} //判断队列是否为空 private: T data[QueueSize]; //存放队列元素的数组 int front, rear; //队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置 }; template { if((rear+1)% QueueSize ==front)throw ”上溢“; rear=(rear+1)% QueueSize; //队尾指针在循环意义下加 1data[rear]=x; //在队尾处插入元素 } template T CirQueue::GetQueue() { if(rear==front)throw ”下溢“; i=(front+1)% QueueSize;//注意不要给队头指针赋值 return data[i]; } template if(rear==front)throw ”下溢“; front=(front+1)% QueueSize; //队头指针在循环意义下加1 return data[front]; //读取并返回出队前的队头元素，注意队头指针 } 5.链队列类定义 template LinkQueue(); //构造函数，初始化一个空的链队列 ~LinkQueue(); //析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue(); //将队头元素出队 T GetQueue(){if(front!=rear)return front->next->data;} //取链队列的队头元素 bool Empty(){front==rear? return 1: return 0;} //判断链队列是否为空 private: Node T LinkQueue::DeQueue(){ if(rear==front)throw ”下溢“;p=front->next;x=p->data; //暂存队头元素 front->next=p->next; //将队头元素所在结点摘链 if(p->next==NULL)rear=front;//判断出队前队列长度是否为1 delete p; return x;} template LinkQueue::LinkQueue(){ s=new Node front=rear=s; //将队头指针和队尾指针都指向头结点s } template void LinkQueue::EnQueue(T x) { s=new Node s->next=NULL; rear->next=s; //将结点s插入到队尾 rear=s;} 注意问题 1．重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。2．栈、队列的算法是后续实验的基础（树、图、查找、排序等）。实验三 多维数组和广义表的操作 实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的：参照给定的多维数组类和广义表类的程序样例，验证给出的多维数组和广义表的常见算法，并实现有关的操作。 二、实验要求： 1、掌握多维数组和广义表的特点。掌握它们的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1.设计函数建立一个n*n阶的对称矩阵。要求： （1）实现将对称矩阵用一维数组存储输出。（2）实现矩阵转置算法。（3）实现魔方阵算法。 (4)设计一个测试例子，并编写主程序进行测试。2．采用链式存储结构设计广义表类，实现以下操作： （1）创建广义表，取广义表的表头元素和表尾元素； （2）求广义表的深度。 四、程序样例 1．稀疏矩阵结构类型声明 const int MaxTerm=100; struct SparseMatrix { element data[MaxTerm]; int mu, nu, tu; //行数、列数、非零元个数 };template ruct element { int row, col; T item };2．稀疏矩阵转置算法Trans1 void Trans1(SparseMatrix A, SparseMatrix &B){ B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;//设置行数、列数、非零元素个数 if(B.tu>0){ //有非零元素则转换 pb=0; for(col=0;col //依次考察每一列 for(pa=0;pa if(A.data[pa].col==col) //处理col列元素 { B.data[pb].row= A.data[pa].col; B.data[pb].col= A.data[pa].row; B.data[pb].item= A.data[pa].item; pb++; } } } 3．稀疏矩阵转置算法Trans2 void Trans2(SparseMatrix A, SparseMatrix &B) { B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;//设置行数、列数、元素个数 if(B.tu>0){ //有非零元素则转换 for(i=0;i //A中每一列非零元素的个数初始化为0 num[i]=0; for(i=0;i { j= A.data[i].col; //取三元组的列号 num[j]++; } cpot[0]=0; //A中第0列第一个非零元素在B中的位置为0 for(i=1;i cpot[i]= cpot[i-1]+num[i-1]; for(i=0;i { j=A.data[i].col; //当前三元组的列号 k=cpot[j]; //当前三元组在B中的下标 B.data[k].row= A.data[i].col; B.data[k].col= A.data[i].row;B.data[k].item= A.data[i].item;cpot[j]++; //预置同一列的下一个三元组的下标 } } } 4．魔方阵 void Square(int a[ ][ ], int n){ p=0;q=(n-1)/2; a[0][q]=1; //在第0行的中间位置填for(i=2;i<=n*n, i++) { p=(p-1+n)% n; //求i所在行号 q=(q-1+n)% n; //求i所在列号 if(a[p][q]>0)p=(p+1)% n;//如果位置(p, q)已经有数，填入同一列下一行 a[p][q]=i; } } 5.广义表类定义 enum Elemtag {Atom, List}; //Atom=0为单元素；List=1为子表 template Elemtag tag; //标志域，用于区分元素结点和表结点 union { //元素结点和表结点的联合部分 T data; //data是元素结点的数据域 struct { GLNode *hp, *tp; //hp和tp分别指向表头和表尾 } ptr; };};template Lists(){ls=NULL;} //无参构造函数，初始化为空的广义表 Lists(Lists ls1, Lists ls2); //有参构造函数，用表头ls1和表尾ls2构造广义表 ~Lists(); //析构函数，释放广义表中各结点的存储空间 int Length(); //求广义表的长度 int Depth(GLNode //求广义表的深度 GLNode *Head();//求广义表的表头 GLNode *Tail(); //求广义表的表尾 private: GLNode Lists::Lists(Lists ls1,Lists ls2) { ls = new GLNode ls->tag = 1;ls->ptr.hp = ls1;ls->ptr.tp = ls2; } 6．求广义表深度算法Depth template int Lists::Depth(GLNode { if(ls==NULL)return 1; //空表深度为1 if(ls->tag==0)return 0; //单元素深度为0 max=0;p = ls;while(p){ dep = Depth(p->ptr.hp); //求以p->ptr.hp为头指针的子表即表头的深度 if(dep>max)max = dep; p = p->ptr.tp; //准备求表尾的深度 } return max+1; //非空表的深度是各元素的深度的最大值加1 } 7．取广义表表头算法Head template { return ls->ptr.hp;} 8．取广义表表尾算法Tail template return ls-> ptr.tp;} 实验四 树和二叉树 实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的： 参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。 二、实验要求： 1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1．设计实现二叉树类，要求： （1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）实现二叉树层次遍历的非递归算法。（3）编写一主函数来验证算法实现。 2.假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。*3.设计实现二叉线索链表类，要求： （1）编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。 （2）编写一主函数来验证算法实现。*4.编写求二叉树高度的函数。 *5.编写创建哈夫曼树和生成哈夫曼编码的算法。 *6．假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。 *7．假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数） 四、程序样例 １．二叉树 二叉链表结点声明 template T data; BiNode template BiTree(){root=NULL;} //无参构造函数，初始化一棵空的二叉树 BiTree(BiNode ~BiTree(); //析构函数，释放二叉链表中各结点的存储空间 void PreOrder(BiNode //前序遍历二叉树 void InOrder(BiNode //中序遍历二叉树 void PostOrder(BiNode //后序遍历二叉树 void LeverOrder(BiNode //层序遍历二叉树 private: BiNode //指向根结点的头指针 void Creat(BiNode //有参构造函数调用 void Release(BiNode //析构函数调用 };二叉树的层序遍历算法LeverOrder template if(q->lchild!=NULL) Q[++rear]=q->lchild;if(q->rchild!=NULL) Q[++rear]=q->rchild; } } 二叉树的构造函数算法BiTree template creat(root)； } template cin>>ch; if(ch=='# ')root=NULL; //建立一棵空树 else { root=new BiNode //生成一个结点 root->data=ch; Creat(root->lchild); //递归建立左子树 Creat(root->rchild); //递归建立右子树 } } 二叉树的后序遍历递归算法PostOrder template if(root==NULL)return; //递归调用的结束条件 else { PostOrder(root->lchild); //后序递归遍历root的左子树 PostOrder(root->rchild); //后序递归遍历root的右子树 cout< //访问根结点的数据域 } } 二叉树的后序遍历非递归算法PostOrder template { top=-1; //采用顺序栈，并假定栈不会发生上溢 while(root!=NULL | | top!=-1){ while(root!=NULL){ top++;s[top].ptr=root; s[top].flag=1;root=root->lchild; } while(top!=-1 && s[top].flag==2){ root=s[top--].ptr; cout< s[top].flag=2; root=s[top].ptr->rchild; } } } 二叉树前序遍历递归算法PreOrder template { if(root ==NULL) return; //递归调用的结束条件 else { cout< //访问根结点的数据域 PreOrder(root->lchild); //前序递归遍历root的左子树 PreOrder(root->rchild); //前序递归遍历root的右子树 } } 二叉树的前序遍历非递归算法PreOrder template { top=-1; //采用顺序栈，并假定不会发生上溢 while(root!=NULL | | top!=-1){ while(root!= NULL){ cout< } if(top!=-1){ root=s[top--]; root=root->rchild; } } } 二叉树的析构函数算法BiTree template Release(root);} void BiTree ::Release(BiNode if(root!=NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } 二叉树的中序遍历递归算法InOrder template if(root==NULL)return; //递归调用的结束条件 else { InOrder(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点的数据域 InOrder(root->rchild); //中序递归遍历root的右子树 } } ２．线索链表 线索链表结点声明 enum flag {Child, Thread}; //枚举类型，枚举常量Child=0，Thread=1 template T data; ThrNode flag ltag, rtag;};线索链表类声明 template InThrBiTree(ThrNode //构造函数，建立中序线索链表 ~ InThrBiTree(); //析构函数，释放线索链表中各结点的存储空间 ThrNode *Next(ThrNode void InOrder(ThrNode ThrNode void Creat(ThrNode //构造函数调用 void ThrBiTree(ThrNode //构造函数调用 };中序线索链表构造函数算法InThrBiTree template { Creat(root); pre=NULL; ThrBiTree(root);} template cin>>ch; if(ch=='# ')root=NULL; //建立一棵空树 else { root=new ThrNode //生成一个结点，左右标志均置0 root->data=ch;root->ltag=0;root->rtag=0; Creat(root->lchild); //递归建立左子树 Creat(root->rchild); //递归建立右子树 } } template if(root==NULL)return;ThrBiTree(root->lchild);if(!root->lchild){ //对root的左指针进行处理 root->ltag=1; root->lchild=pre;//设置pre的前驱线索 } if(!root->rchild)root->rtag=1; //对root的右指针进行处理 if(pre->rtag==1)pre->rchild=root;//设置pre的后继线索 pre=root;ThrBiTree(root->rchild);} 中序线索链表查找后继的算法Next template if(p->rtag==1)q=p->rchild; //右标志为1，可直接得到后继结点 else { q=p->rchild; //工作指针初始化，while(q->ltag==0) //查找最左下结点 q=q->lchild; } return q;} 中序线索链表查找后继的算法Next template if(root==NULL)return;//如果线索链表为空，则空操作返回 p=root; while(p->ltag==0) //查找中序遍历序列的第一个结点p并访问 p=p->lchild;cout< data;while(p->rchild!=NULL) //当结点p存在后继，依次访问其后继结点 { p=Next(p);cout< data;} } 中序线索链表构造函数算法InThrBiTree template { Creat(root); pre=NULL; ThrBiTree(root);} template cin>>ch; if(ch=='# ')root=NULL; //建立一棵空树 else { root=new ThrNode //生成一个结点，左右标志均置0 root->data=ch;root->ltag=0;root->rtag=0; Creat(root->lchild); //递归建立左子树 Creat(root->rchild); //递归建立右子树 } } template if(root==NULL)return;ThrBiTree(root->lchild);if(!root->lchild){ //对root的左指针进行处理 root->ltag=1; root->lchild=pre;//设置pre的前驱线索 } if(!root->rchild)root->rtag=1; //对root的右指针进行处理 if(pre->rtag==1)pre->rchild=root;//设置pre的后继线索 pre=root;ThrBiTree(root->rchild);} ３．哈夫曼树 void HuffmanTree(element huffTree[ ], int w[ ], int n) { for(i=0;i<2*n-1;i++) //初始化 { huffTree [i].parent=-1;huffTree [i].lchild=-1;huffTree [i].rchild=-1; } for(i=0;i //构造n棵只含有根结点的二叉树 huffTree [i].weight=w[i];for(k=n;k<2*n-1;k++) //n-1次合并 { Select(huffTree, i1, i2); //在huffTree中找权值最小的两个结点i1和i2 huffTree[i1].parent=k; //将i1和i2合并，则i1和i2的双亲是k huffTree[i2].parent=k; huffTree[k].weight= huffTree[i1].weight+huffTree[i2].weight;huffTree[k].lchild=i1; huffTree[k].rchild=i2;} } 注意问题 1．注意理解有关树的各种递归算法的执行步骤。 2．注意字符类型数据在输入时的处理。3．重点理解如何利用栈结构实现非递归算法。 实验五 图的有关操作 实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的： 参照给定的图类的程序样例，验证给出的有关图的常见算法，并实现有关的操作。 二、实验要求： 1、掌握图的特点，利用图的邻接矩阵和邻接表的存储结构实现图的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1.设计邻接矩阵图类，实现如下操作：（1）测试类中的成员函数；（2）实现拓扑排序算法；（3）实现最小生成树算法；（4）实现最短路径算法； （5）设计主函数，输入数据，测试各算法。 2.设计邻接表类，实现无向图的深度优先非递归遍历、无向图的广度优先遍历，并设计主函数输入数据进行测试。 *3.假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到顶点v的长度为l的所有简单路径。 四、程序样例： 1.图的邻接表类的定义 struct ArcNode //定义边表结点 { int adjvex;//邻接点域 ArcNode *next;};template //定义顶点表结点 { T vertex; ArcNode *firstedge;};const int MaxSize=10; //图的最大顶点数 template ALGraph(T a[ ], int n, int e); //构造函数，初始化一个有n个顶点e条边的图 ~ALGraph; //析构函数，释放邻接表中各边表结点的存储空间 T GetVex(int i); //取图中第i个顶点数据信息 void PutVex(int i, T value); //将图中第i个顶点的数据域置为value void InsertVex(int i, T value);//在图中插入一个顶点，其编号为i，值为value void DeleteVex(int i); //删除图中第i个顶点 void InsertArc(int i, int j); //在图中插入一条边，其依附的两个顶点的编号为i和j void DeleteArc(int i, int j); //在图中删除一条边，其依附的两个顶点的编号为i和j void DFSTraverse(int v); //深度优先遍历图 void BFSTraverse(int v); //广度优先遍历图 private: VertexNode adjlist[MaxSize]; //存放顶点表的数组 int vertexNum, arcNum; //图的顶点数和边数 }; template //输入顶点信息，初始化顶点表 { adjlist[i].vertex=a[i];adjlist[i].firstedge=NULL; } for(k=0;k //依次输入每一条边，并在相应边表中插入结点 { cin>>i>>j; //输入边所依附的两个顶点的序号 s=new ArcNode;s->adjvex=j;//生成一个边表结点s s->next=adjlist[i].firstedge; //将结点s插入到结点i的边表的表头 adjlist[i].firstedge=s;} } template cout< p=adjlist[v].firstedge; while(p) //依次搜索顶点v的邻接点j { j=p->adjvex;if(visited[j]==0)DFSTraverse(j); p=p->next; } } template { front=rear=-1; //初始化队列, 假设队列采用顺序存储且不会发生溢出 cout< //被访问顶点入队 while(front!=rear) { v=Q[++front]; p=adjlist[v].firstarc; //边表中的工作指针p初始化 while(p) { j= p->adjvex; if(visited[j]==0){ cout< } p=p->next;} } } 2.图的邻接矩阵类的定义 const int MaxSize=10; //图中最多顶点个数 template MGraph(T a[ ], int n, int e); //构造函数，初始化具有n个顶点e条边的图 ~MGraph(){ } //析构函数 T GetVex(int i); //取图中第i个顶点数据信息 void PutVex(int i, T value); //将图中第i个顶点的数据域置为value void InsertVex(int i, T value);//在图中插入一个顶点，其编号为i，值为value void DeleteVex(int i); //删除图中第i个顶点 void InsertArc(int i, int j); //在图中插入一条边，其依附的两个顶点的编号为i和j void DeleteArc(int i, int j); //在图中删除一条边，其依附的两个顶点的编号为i和j void DFSTraverse(int v); //深度优先遍历图 void BFSTraverse(int v); //广度优先遍历图 private: T vertex[MaxSize]; //存放图中顶点的数组 int arc[MaxSize][MaxSize];//存放图中边的数组 int vertexNum, arcNum; //图的顶点数和边数 };template { vertexNum=n;arcNum=e;for(i=0;i vertex[i]=a[i];for(i=0;i //初始化邻接矩阵 for(j=0;j arc[i][j]=0; for(k=0;k //依次输入每一条边，并修改邻接矩阵的相应元素 { cin>>i>>j; //边依附的两个顶点的序号 arc[i][j]=1; //置有边标志 arc[j][i]=1; } } 3．图的拓扑排序 void TopSort() { top=-1;count=0; //采用顺序栈S并初始化，累加器初始化； for(i=0;i //扫描顶点表，将入度为0的顶点压栈； if(adjlist[i].in==0)S[++top]=i； while(top!=-1) //当图中还有入度为0的顶点时循环 { j=S[top--]; //从栈中取出一个入度为0的顶点 cout< p=adjlist[j].firstedge;//扫描顶点表，找出顶点j的所有出边 while(p!=NULL) { k=p->adjvex; adjlist[k].in--; //将入度减1，如果为0，则将该顶点入栈 if(adjlist[k].in==0) S[++top]=k; p=p->next; } } if(count cout<<”有回路“; } 4．图的Prim算法，求图的最小生成树 void Prim(MGraph G){ for(i=1;i adjvex[i]=0;} lowcost[0]=0; //将顶点0加入集合U中 for(i=1;i cout<<”(“< //输出加入TE中的边 lowcost[k]=0; //将顶点v加入集合U中 for(j=1;j //调整数组lowcost和adjvex if G.arc[k][j] lowcost[j]=G.arc[k][j]; adjvex[j]=k; } } } 5．图的最短路径 void Dijkstra(MGraph G, int v) { for(i=0;i //初始化dist[n]、path[n] { dist[i]=G.arc[v][i]; if(dist[i]!=∞)path[i]=G.vertex[v]+G.vertex[i]; else path[i]=”“; } s[0]=G.vertex[v]; //初始化集合S dist[v]=0; //标记顶点v为源点 num=1;while(num //当数组s中的顶点数小于图的顶点数时循环 { k=0;for(i=0;i //在dist中查找最小值元素 if((dist[i] cout< //将新生成的终点加入集合S dist[k]=0; //置顶点vk为已生成终点标记 for(i=0;i //修改数组dist和path if(dist[i]>dist[k]+G.arc[k][i]){ dist[i]=dist[k]+G.arc[k][i]; path[i]=path[k]+G.vertex[i]; } } } void Floyd(MGraph G) { for(i=0;i //初始化矩阵dist和path for(j=0;j { dist[i][j]=G.arc[i][j]; if(dist[i][j]!=∞)path[i][j]=G.vertex[i]+G.vertex[j]; else path[i][j]=”“; } for(k=0;k //进行n次迭代 for(i=0;i //顶点i和j之间是否经过顶点k for(j=0;j if(dist[i][k]+dist[k][j] dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=path[i][k]+path[k][j]; } } 注意问题 １．注意理解各算法实现时所采用的存储结构。 ２．注意区别正、逆邻接矩阵。 实验六 查找 实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的： 参照各种查找算法程序样例，验证给出的查找常见算法。 二、实验要求： 1、掌握各种查找算法的特点，测试并验证查找的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1.建立有序表，采用折半查找实现某一已知的关键字的查找。 2．利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。3．建立顺序表，统计表中重复元素个数。 5.根据给定的二叉排序树类的定义,验证二叉排序树的各个成员函数。4.哈希表类设计。要求： (1)哈希函数采用除留余数法，哈希冲突解决方法采用链地址法；(2)设计一个侧试程序进行侧试。 四、程序样例： １．顺序表的顺序查找算法SeqSearch1 int SeqSearch1(int r[ ], int n, int k) { r[0]=k;i=n;while(r[i]!=k)i--;return i;} ２．折半查找递归 int BinSearch2(int r[ ], int low, int high, int k) { if(low>high)return 0;//递归的边界条件 else { mid=(low+high)/2; if(k else if(k>r[mid])return BinSearch2(r, mid+1, high, k); else return mid;} } ３．折半查找非递归 int BinSearch1(int r[ ], int n, int k){ low=1;high=n;while(low<=high) { mid=(low+high)/2; if(k else return mid; } return 0;} ４．单链表的顺序查找算法SeqSearch2 int SeqSearch2(Node { p=first->next;j=1; while(p!=NULL && p->data!=k) { p=p->next; j++; } if(p->data==k)return j; else return 0;} ５．二叉排序树类声明 class BiSortTree //本章假定记录中只有一个整型数据项 { public: BiSortTree(int a[ ], int n); //建立查找集合a[n]的二叉排序树 ~ BiSortTree(); //析构函数，释放二叉排序树中所有结点，同二叉链表的析构函数 void InsertBST(BiNode private: BiNode //二叉排序树（即二叉链表）的根指针 }; 二叉排序树构造函数算法BiSortTree BiSortTree::BiSortTree(int r[ ], int n){ for(i=0;i s->lchild=s->rchild=NULL;InsertBST(root, s);} } 二叉排序树插入算法InsertBST 1.若root是空树，则将结点s作为根结点插入；否则 2.若s->data＜root->data，则把结点s插入到root的左子树中；否则 3.把结点s插入到root的右子树中。 void BiSortTree::InsertBST(BiNode if(root==NULL)root=s; else if(s->data else InsertBST(root->rchild, s);} 二叉排序树查找算法SearchBST BiNode * BiSortTree::SearchBST(BiNode { if(root==NULL)return NULL； else if(root->data==k)return root; else if(k else return SearchBST(root->rchild, k); } 二叉排序树的删除算法DeleteBST void BiSortTree::DeleteBST(BiNode { if(!p->lchild &&!p->rchild){ //p为叶子 f->lchild= NULL;delete p;} else if(!p->rchild){ //p只有左子树 f->lchild=p->lchild; delete p;} else if(!p->lchild){ //p只有右子树 f->lchild=p->rchild; delete p; } else { //左右子树均不空 par=p;s=p->rchild; while(s->lchild!=NULL) //查找最左下结点 { par=s; s=s->lchild; } p->data=s->data; if(par==p)par->rchild=s->rchild;//处理特殊情况 else par->lchild=s->rchild; //一般情况 delete s; } //左右子树均不空的情况处理完毕 } ６．闭散列表的查找算法HashSearch1 int HashSearch1(int ht[ ], int m, int k) { j=H(k); if(ht[j]==k)return j; //没有发生冲突，比较一次查找成功 i=(j+1)% m;while(ht[i]!=Empty && i!=j) { if(ht[i]==k)return i;//发生冲突，比较若干次查找成功 i=(i+1)% m; //向后探测一个位置 } if(i==j)throw ”溢出“;else ht[i]=k; //查找不成功时插入 } ７．开散列表的查找算法HashSearch２ Node j=H(k);p=ht[j];while(p && p->data!=k)p=p->next;if(p->data= =k)return p; else { q=new Node q->next= ht[j]; ht[j]=q; } } 注意问题 1．注意理解折半查找的适用条件（链表能否实现折半查找？）。2.注意理解静态查找、动态查找概念。 3．比较各种查找算法的各自特点，能够根据实际情况选择合适的查找方法。 实验七 排序的有关操作 实验类型：验证性 实验要求：必修 实验学时： 2学时 一、实验目的： 参照各种排序算法程序样例，验证给出的排序常见算法。 二、实验要求： 1、掌握各种排序算法的特点，测试并验证排序的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 输入一组关键字序列分别实现下列排序: 1.实现简单选择排序、直接插入排序和冒泡排序。2.实现希尔排序算法。 3.实现快速排序算法（取第一个记录或中间记录作为基准记录）。4.实现堆排序算法。*5.快速排序的非递归算法。*6.实现折半插入排序。 *7.采用链式存储实现简单选择排序、直接插入排序和冒泡排序。 8.在主函数中设计一个简单的菜单，分别测试上述算法。 *9.双向起泡排序。在起泡排序中，若待排序序列为正序，只需一趟扫描，而待排序序列为反序时，需进行n-1趟扫描。对于初始序列（94，10，12，18，42，44，67）只需扫描2趟，而对于初始序列（12，18，42，44，67，94，10）就需扫描6趟。造成这种不对称的原因：每趟扫描仅能使最小数据下沉一个位置，如果改变扫描方向，情况正好相反，即每趟从后往前扫描，都能使当前无序区中最大数据上浮一个位置。为了改变上述两种情况下的不对称性，可以在排序过程中交替改变扫描方向，称之为双向起泡排序。 四、程序样例: 1.选择排序 void SelectSort(int r[ ], int n){ for(i=1;i //对n个记录进行n-1趟简单选择排序 { index=i; for(j=i+1;j<=n;j++) //在无序区中选取最小记录 if(r[j] if(index!=i)r[i]←→r[index]; } } 2．快速排序 int Partition(int r[ ], int first, int end) { i=first;j=end; //初始化 while(i { while(i //右侧扫描 if(i r[i]←→r[j]; //将较小记录交换到前面 i++; } while(i //左侧扫描 if(i r[j]←→r[i]; //将较大记录交换到后面 j--; } } retutn i; //i为轴值记录的最终位置 } void QuickSort(int r[ ], int first, int end) { if(first //递归结束 pivot=Partition(r, first, end);//一次划分 QuickSort(r, first, pivot-1);//递归地对左侧子序列进行快速排序 QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序 } } 3.起泡排序 void BubbleSort(int r[ ], int n) { exchange=n; //第一趟起泡排序的范围是r[1]到r[n] while(exchange)//仅当上一趟排序有记录交换才进行本趟排序 { bound=exchange;exchange=0； for(j=1;j //一趟起泡排序 if(r[j]>r[j+1]){ r[j]←→r[j+1]； exchange=j； //记录每一次发生记录交换的位置 } } } 4.希尔排序 void ShellSort(int r[ ], int n){ for(d=n/2;d>=1;d=d/2) //以增量为d进行直接插入排序 { for(i=d+1;i<=n;i++) { r[0]=r[i]; //暂存被插入记录 for(j=i-d;j>0 && r[0] r[j+d]=r[j]; //记录后移d个位置 r[j+d]=r[0]; } } } void InsertSort(int r[ ], int n){ for(i=2;i<=n;i++) { r[0]=r[i]; //设置哨兵 for(j=i-1;r[0] //寻找插入位置 r[j+1]=r[j]; //记录后移 r[j+1]=r[0]; } } 5.堆排序 void Sift(int r[ ], int k, int m){ i=k;j=2*i; //置i为要筛的结点，j为i的左孩子 while(j<=m) //筛选还没有进行到叶子 { if(j //根结点已经大于左右孩子中的较大者 else { r[i]←→r[j]; //将根结点与结点j交换 i=j;j=2*i; //被筛结点位于原来结点j的位置 } } } void HeapSort(int r[ ], int n){ for(i=n/2;i>=1;i--) //初始建堆，从最后一个非终端结点至根结点 Sift(r, i, n); for(i=1;i //重复执行移走堆顶及重建堆的操作 { r[1]←→r[n-i+1]; Sift(r, 1, n-i); } } 6.归并排序 void MergeSort2(int r[ ], int r1[ ], int s, int t){ if(s==t)r1[s]=r[s]; else { m=(s+t)/2; Mergesort2(r, r1, s, m); //归并排序前半个子序列 Mergesort2(r, r1, m+1, t); //归并排序后半个子序列 Merge(r1, r, s, m, t); //将两个已排序的子序列归并 } } void MergeSort1(int r[ ], int r1[ ], int n){ h=1; while(h { MergePass(r, r1, n, h); h=2*h; MergePass(r1, r, n, h); h=2*h;} } void Merge(int r[ ], int r1[ ], int s, int m, int t){ i=s;j=m+1;k=s;while(i<=m && j<=t) { if(r[i]<=r[j])r1[k++]=r[i++]; //取r[i]和r[j]中较小者放入r1[k] else r1[k++]=r[j++];} if(i<=m)while(i<=m) //若第一个子序列没处理完，则进行收尾处理 r1[k++]=r[i++]; else while(j<=t)//若第二个子序列没处理完，则进行收尾处理 r1[k++]=r[j++]; } void MergePass(int r[ ], int r1[ ], int n, int h){ i=1;while(i≤n-2h+1) //待归并记录至少有两个长度为h的子序列 { Merge(r, r1, i, i+h-1, i+2*h-1); i+=2*h;} if(i＜n-h+1)Merge(r, r1, i, i+h-1, n);//待归并序列中有一个长度小于h else for(k=i;k<=n;k++) //待归并序列中只剩一个子序列 r1[k]=r[k]; } 注意问题： 注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况选择合适的排序方法。 实验八 综合实验 实验类型：综合性 实验要求：必修 实验学时：2学时 一、实验目的： 通过该实验是学生能够综合数据结构所学的知识，自行分析、设计，学会对一个实际问题分析、综合、设计的能力。 二、实验要求 1、掌握数据结构所学的内容，分析给定实验内容并设计出程序，然后运行，同时分析几种不同方法的效率。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 设计一个简单个人电话号码查询系统 1.问题描述： 人们在日常中经常要查找某个人或某个单位的电话号码，本实验将实现一个简单的个人电话号码查询系统，根据用户输入信息（例如姓名等）进行快速查询。 2、基本要求 （1）在外存上，用文件保存电话号码信息；（2）在内存中，设计数据结构存储电话信息；（3）提供查询功能；根据姓名实现快速查询；（4）提供其他功能，例如插入、删除、修改等； 3、设计思想 由于要管理的电话号码信息很多，而且要在程序运行后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放在外存上。在系统运行时，要将电话号码信息从文件调入内存来进行查询等操作，为了接收文件中内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据： const int max = 10 struct TeleNumber { String name;String phoneNumber;String mobileNumber;String email;为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但数组中实现插入和删除操作的代价较高。如果记录频繁进行插入或删除操作，可以考虑采用} Tele[max];二叉排序数组织电话号码信息，则查询和维护都能获得较高的时间性能；另外也可以考虑直接使用哈希表表结构存储电话号码信息，请同学根据实际情况自己选择。 4、详细分析采用几种不同方法实现的效率。实验九：停车场管理（开放实验一） 实验类型：设计性 【实验内容与要求】 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。 试为停车场编制按上述要求进行管理的模拟程序。【知识要点】 综合利用栈和队列模拟停车场管理，学习利用栈和队列解决实际问题。【实现提示】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 设n=2,输入数据为：（„A‟，1，5），（„A‟，2，10），（„D‟，1，15），（„A‟，3，20），（„A‟，4，25），（„A‟，5，30），（„D‟，2，35），（„D‟，4，40），（„E‟，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，„A‟表示到达；„D‟表示离去，„E‟表示输入结束。 根据以上问题写出实验报告。【参考程序】 #include （1）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。如何处理该问题？ （2）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。如何处理该问题？ 实验十：窗口管理（开放实验二） 实验类型：设计性 【实验内容与要求】 图形用户界面（GUI）维护屏幕上的多个窗口。这些窗口按层次组织，最前面的窗口作为活动窗口。有些应用程序维护一个当前打开窗口表。从菜单中可以访问此表。用户可以选择一个窗口标题以使成为最前面的或活动的窗口。当一个底层窗口的视线被挡时，这就显得特别有用。从菜单的表中选择“Window_1”可以激活该窗口。 试为窗口编制按上述要求进行管理的模拟程序。【知识要点】 综合利用链表、排序的方法，学习利用链表和排序解决实际问题。【实现提示】 本实验中维护GUI应用的一个窗口表。应用程序支持以下的文件和表操作： New：插入名为“Untitled”的窗口。Close：删除前排窗口。 Close All：清空表以关闭所有的窗口。 Save As：将窗口的内容保存到不同的文件名中并更新窗口的标题。Quit：终止应用程序。 Menu Display：窗口菜单按层次显示每个窗口的号码和名字。用户可以输入号码并激活窗口，将它移到窗口表的最前面。 窗口表： 任一时刻所允许打开的窗口最大数目为10。每个打开的窗口都对应有一个0到9范围内的号码。关闭一个窗口时，其号码可以用于创建新的打开窗口的New操作。处理各个窗口并修改当前活动窗口由Close，Close All，Save As和Activate方法负责，每个窗口都由一个窗口对象表示，它描述了窗口名及其在可用窗口表中的号码。 根据以上问题写出实验报告。 C++/数据结构 大作业/课程设计——【校园导游咨询】【停车场管理】娃娃们可以收着以后用 绝对纯手工打造 内含类模块/一维指针数组（谨以此程序供大家参考。运行结果后面有贴图） 目录 【1】校园导游咨询 程序设计源代码 及 截图 【2】停车场管理——方案一 程序设计源代码 及 截图 【3】停车场管理——方案二 程序设计源代码 及 截图 【1】【【校园导游咨询】】 ###### (ps:该校园导游咨询系统没有输入值，所有信息是都在class MGraph的构造函数中传输的，且校园景点信息皆为【【上海电力学院】】景点信息。请大家注意，直接从文章copy到visual stutio中会出现中文字符，注意删除，推荐大家在一行语句的分号后面，点出光标，按一下delete键，然后按一下enter键，完成visual stutio的自动对齐，这样程序看起来一目了然，更易于操作和更改)【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】 (1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。【选作内容】 (6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。**************************【以下为类的定义】******************************** #include class direction;template { friend class MGraph direction dir;//存放顶点方位信息的direction类的dir。}; class direction { public: int ln;//存放在方向图中的横坐标，表示东西 int col;//存放在方向图中的纵坐标，表示南北 };template { public: MGraph(); //构造函数，初始化具有n个顶点的图 void printvexname();//显示所有景点及景点代号 void printvexinf(int i);//显示代号为i景点的名称及信息 void printroad(int i,int j);//显示景点i~j的最短路径方案信息 void printdir(int i,int j);//显示景点i到j的方向信息，如“向东100m，向南200m” VertexNode void Root(int p,int q);//递归寻找pq间的最短路径 int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度 int Line[MaxSize];//Line存放路径 int kkk;//Line[]数组的标记 private: T vertex[MaxSize];//存放图中顶点的数组 int arc[MaxSize][MaxSize];//存放图中边的数组 };*************************【以下为类的实现 即类函数的定义】*********************************** template //s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][] { int s[]={0, 1,0, 0,2,0, 0,0,2,0, 0,0,2,3,0, 0,0,0,4,2,0, 0,0,0,0,2,3,0, 0,0,0,0,2,3,1,0, 0,0,2,0,2,0,0,2,0, 4,0,2,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,2,0, 1,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,3,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0};int a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};char* b[]={“南门”,“实验楼”,“南图”,“大活”,“睿思楼”,“大礼堂”, “南4教”,“知行楼”,“国交楼”,“南3教”,“南2教”,“南1教”, “北图”,“北3教”,“北4教”,“北2教”,“北1教”,“北门”};char* c[]={“南校区正门”,“物理实验楼”,“南校区图书馆”,“大学生活动中心”, “教师办公楼、医务室及留学生公寓”,“大礼堂，用于举办各种文艺演出”,“南校区第4教学楼”,“实习基地，计算机房等”, “国际交流中心，教职工餐厅”,“南校区第3教学楼”,“南校区第2教学楼”,“南校区第1教学楼”, “北校区图书馆”,“北校区第3教学楼”,“北校区第4教学楼”,“北校区第2教学楼”, “北校区第1教学楼”,“北校区正门”};int d[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8};int e[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2};int i,j;vertexNum=18;arcNum=30; for(i=0;i for(j=0;j template cout<<“向东”< cout<<“向南”< if(Path[p][q]>0){ Root(p,Path[p][q]);Root(Path[p][q],q);} else { Line[kkk]=q;kkk++;} } template for(q=0;q Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;} cout<<“n=======n”;cout<<“从”< { int choice;cout<<“================”< 【2】【停车场管理系统【方案一 程序】】 ###### （ps：该程序有漏洞，若将要离开的车辆是停于便道上的，则对该车进行驶离操作时程序内部有错误数据，虽然做了函数完成这一功能，但因时间有限，没能及时查找更正，现在懒得改了。。大家将就看吧。不过运行是可以的）【问题描述】 设停车场是一个可停放n辆汽车的 长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【测试数据】 设n=2，输入数据为：(A，1，5)，（A，2，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。**************************【以下为类的定义】************************************* #include const double price=30;//每小时的费用 //思想：（报告第四页） //我的系统界面，输入信息为：（到达/离开/退出）；车牌号；时刻 //因此，我的停车场类分成车辆到达和车辆离开两个主要的函数实现。//车辆到达，有入栈和入队。车辆离开有出栈，出队和入栈操作。 //因此我又编写入栈的类，队的类。与parkingmanagement进行友元。 //**************************************类定义*********************************************** class car//车的信息类 { public: double time;//计费时间 int number;//车牌号 car *next;//存放car类型元素的数组初始地址 };class carstack//栈（停车场）的类 { friend class parkingmanagement;//parkingmanagement能访问carstack类中所有成员 public: carstack();//构造函数，栈的初始化 int empty();//判断栈是否为空 int full();//判断栈是否为满 car *s;//存放car类型栈元素的数组初始地址 int top;//栈顶指针 };class carqueue//队列（便道）的类 { friend class parkingmanagement;//parkingmanagement能访问carstack类中所有成员 public: carqueue();//构造函数，队列的初始化 int full();//判断队列是否为满 car *front,*rear;//存放car类型队列元素的数组初始地址 };class parkingmanagement { public: int pushstack(carstack &cs,int cnum,double ctime);//入栈,cs栈内进行调整，返回栈内位置 void popstack(carstack &cs,int cnum);//出栈，cs栈内进行调整，//根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber()//将出栈car的time赋值给double popstacktime()，无返回值！ int pushqueue(carqueue &cq,int cnum,double ctime);//入队,队内进行调整，返回队内位置 int popqueue(carqueue &cq);//出队,队内进行调整，返回汽车车牌号 void arrival(carstack &cs,carqueue &cq,int cnum,double ctime);//车辆到达，//根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 void leave(carstack &cs,carqueue &cq,int cnum,double ctime);//车辆离开，//根据输入的车牌号找到汽车，并进行出栈操作、出队操作和入栈操作； //并cout停留时间和收费情况 void deletequeue(carqueue &cq,int i);//删除cq过道中第i辆车 int popstacknumber;//专门存放出栈的时候返回的车牌号 double popstacktime;//专门存放出栈的时候返回的时刻 };**********************************【以下为类的实现】************************************ carstack::carstack()//构造函数，栈的初始化 { top=-1;s=new car[Max];//创建car类型栈元素的数组 if(s==NULL){ cout<<“栈空间分配不成功！”< cs.top++;(cs.s[cs.top]).number=cnum;//将cnum赋给栈顶位置的车的车牌号，s是car类型栈元素的数组(cs.s[cs.top]).time=ctime;//将ctime赋给栈顶位置的车的入栈时间，s是car类型栈元素的数组 return(cs.top+1);//返回栈内位置加1，即停车场内车位从1号开始 } } void parkingmanagement::popstack(carstack &cs,int cnum)//出栈，cs栈内进行调整，//根据车牌号把车弹出栈,将出栈car的number赋值给int popstacknumber //将出栈car的time赋值给double popstacktime，无返回值！{ int i;car p;carstack stemp;//定义一个carstack类型的临时存放出栈元素的栈 for(i=0;i<=cs.top;i++)if((cs.s[i]).number==cnum)break;//当要出栈的车的车牌号=栈内的车牌号元素时，跳出循环 p=cs.s[i];//将要出栈的元素赋给car类型的p存放 while(cs.top>i)stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出栈的元素数组逐个赋给临时栈 popstacknumber=p.number;//将这个车牌号信息传给int popstacknumber()popstacktime=p.time;//将该车的时间信息传给double popstacktime()cs.top--;//栈顶指针回到原来位置 while(stemp.top>=0)cs.s[++(cs.top)]=stemp.s[(stemp.top)--];//临时栈出栈的元素逐个赋给原栈，完成先退再进的工作 } int parkingmanagement::pushqueue(carqueue &cq,int cnum,double ctime)//入队,队内进行调整，返回队内位置 { car *p,*countp;int count(1);//count用于记录车在过道上的位置信息，因队列为链式的，所以进行循环累加 p=new car;//创建一个car类型的指针 p->number=cnum;p->time=ctime;p->next=NULL;//首先将指向存放car类型元素的数组初始地址置空 if(cq.front==NULL)//第一次入队要判断头结点是否为空 { cq.front=cq.rear=p;} else {//尾插法插入元素 p->next=(cq.rear)->next;(cq.rear)->next=p;cq.rear=(cq.rear)->next;} countp=(cq.front)->next;while(countp!=NULL){ count++;countp=countp->next;}//count即车在过道上的位置，【从1开始计！！】 return count;} int parkingmanagement::popqueue(carqueue &cq)//出队,队内进行调整，返回汽车车牌号 { car p;p.number=((cq.front)->next)->number;//cq队里，从cq.front开始指向下一个元素的车牌号赋给car类型的车信息 p.time=((cq.front)->next)->time;//cq队里，从cq.front开始指向下一个元素的时刻 //赋给car类型的车信息 p.next=((cq.front)->next)->next;//cq队里，从cq.front开始指向下一个元素的指针 //赋给car类型的车信息的下一个元素的指针 return p.number;cq.front=(cq.front)->next;} void parkingmanagement::arrival(carstack &cs,carqueue &cq,int cnum,double ctime)//车辆到达，根据输入的车牌号、到达时间，变更函数参数；并cout车位信息 { int pos;if(!(cs.full()))//如果栈未满，车辆停入停车场 { int fl(0),i;//定义一个从0开始的标记fl for(i=0;i<=cs.top;i++){ if(cs.s[i].number==cnum)//如果到达的车的车牌号=栈内已有车辆的车牌号 { fl=1;//fl记1 break;} } if(fl==1)//如果到达的车的车牌号!=栈内已有车辆的车牌号 cout<<“输入错误！请重新输入！”< cout<<“该停车场还有空位，请到”< { pos=pushqueue(cq,cnum,ctime);//入队，返回车位信息 cout<<“该停车场已满，请将车停到便道”< { popstack(cs,cnum);//出栈操作 hour=ctime-popstacktime;//时间计算 outcarnum=popqueue(cq);//将便道上的第一辆车出队，入栈。并将其车牌号赋给outcarnum pstack=pushstack(cs,outcarnum,ctime);//将便道上的第一辆车，入栈 cout<<“该车在本停车场内停留时间为”< { p=cq.front;while(p!=NULL){ count++;//如果在过道中找到该车，则该车的位置为过道中的第count位置（count从1开始）p=p->next;if(p->number==cnum)//在过道中找到要出去的车，则在队列中删除该car。//后面的车辆依然顺序排列，补足空位 { deletequeue(cq,count);if(count>Max){ cout<<“您的车在便道上的位置为”< car *p,*q;int j(0);p=cq.front;while(p && j ######【3】【停车场管理系统【方案二 程序】】 （ps：本方案与方案一有同样的问题，就是在对 便道上的车 进行驶离操作时，数据错误，同样的理由，没有改正。如果有细心娃娃帮忙指点改正，在此感激啦~） *************************【以下为类定义】************************************ #include struct Node//过道停车的队列所需链式结点 { T carnum;//定义车牌号类型 Node friend class carStack;public: T carnum;//车号 int cartime;//停车时间 }; template int EnQueue(T cnum);//将元素x入队,并返回其在队内的位置（从1开始）T DeQueue();//将队头链式结点出队,并返回汽车车牌号 void deletequeue(int i);//将队内低i个元素删除，即便道上i位置的汽车驶离 bool Empty();//判断链队列是否为空 Node int Popcar(T outcnum,int outctime);//将第cnum辆车出栈，并返回其停车时间（hour）bool full();//判断栈是否为满？满则返回1 carinfo s=new Node front=rear=s;} else { rear->next=s;//将结点s插入到队尾 rear=s;} p=front;while(p!=NULL){ i++;p=p->next;}//i即车在过道上的位置，【从1开始计！！】 return i;} template front=front->next;//将队头元素所在结点摘链 } return p->carnum;delete p;//将出队进栈的车从队列里删除 } template template :top(-1){//建立一个最大尺寸为size的空栈 S=new carinfo { cerr<<“动态存储失败！”< template template void outputpark()//系统功能选择页面，输入泊车信息 { cout<<“========================”< { cs.Pushcar(carnum,cartime);cout<<“请驶入停车场的”< Node 上机实验： 1、回文是指正读，反读均相同的字符序列，如“abba”和“abdba”均是回文，但是“good”不是回文，试用STACK类编写该程序。 #include int top = 1;char *cMyStack =(char *)malloc((iLen/2+1)*sizeof(char));//定位对原始数组的检测索引初始位置 cMyStack[0] = iLen/2;if(1 == iLen%2){ ++cMyStack[0];} //将原始数组的一半元素入栈 for(top=1;top<=iLen/2;top++){ cMyStack[top] = *(cScr+top-1);} //从栈顶开始依次匹配 while(*(cScr+cMyStack[0])== cMyStack[--top] && cMyStack[0]++ < iLen){} if(0 == top){//是回文数 free(cMyStack);return 1;} else {//不是回文数 free(cMyStack);return 0;} } 运行结果： 2.利用两个栈类S1、S2模拟一个队列时，编写一程序利用栈的运算实现队列的插入、删除以及判断队列空的运算。 #include template assert(!mStack2.empty());mStack2.pop();} template sq.pushBack(1);printQueue(sq);sq.pushBack(2);printQueue(sq);sq.pushBack(3);printQueue(sq);sq.popFront();printQueue(sq);sq.popFront();printQueue(sq);sq.popFront();printQueue(sq);return 0;} 运行结果： 实验2： 声明复数的类Complex,使用友元函数add实现复数的加法。 #include < iostream > using namespace std; class Complex { private: double real, image;public : Complex(){} Complex(double a,double b) { real = a;image = b;} void setRI(double a, double b){ real = a;image = b;} double getReal(){ return real;} double getImage(){ return image;} void print(){ if(image>0) cout<<“复数：”<< real <<“ + ”<< image <<“i”<< endl;if(image<0) cout<<“复数：”<< real <<“-”<< image <<“i”<< endl;} friend Complex add(Complex ,Complex);//声明友元函数 }; Complex add(Complex c1, Complex c2)//定义友元函数 { Complex c3; c3.real = c1.real + c2.real;//访问Complex类中的私有成员 c3.image = c1.image + c2.image;return c3;} void main(){ Complex c1(29, 0.634), c2, c3;c2.setRI(85,106.012);c3 = add(c1, c2); cout<<“复数一：”;c1.print();cout<<“复数二：”;c2.print();cout<<“相加后：”;c3.print();} 结果： 实验三： 7-5 定义一个基类Shape，在此基础上派生出一个Rectangle和Circle,二者都有getArea()函数计算对象的面积。使用Rectangle类创建一个派生类Square.#include public: Shape(){} double GetArea() { return 0.1;} };class Rectangle: public Shape { public: Rectangle(double w,double h) { width=w;height=h;} double GetArea(){ return width*height;} private: double width,height;};class Circle:public Shape { private: double r; public: Circle(double rr){ r=rr;} double GetArea(){ return PI*r*r;} }; int main(){ Rectangle * rec=new Rectangle(5,6); Circle * cir=new Circle(5); cout<<“RecArea:”< cout<<“CirArea:”< return 1; } 运行结果： 7-10.定义一个Object类，有数据成员weight及相应的操作函数，由此派生出Box类，增加数据成员height和width及相应的操作函数，声明一个Box对象，观察构造函数和析构函数的调用顺序。#include object(){ cout<<“构造object对象”< class box:public object { private: int Height,Width;public: box(){ cout<<“构造box对象”< 面向对象程序设计实验 Object Oriented Programming 课程编号： 学 分： 学 时：10 先修课程：计算机导论、C语言程序设计 适用专业：计算机科学与技术、软件工程 教 材：《C++程序设计教程：实验手册》，清华大学出版社，Harvery M.，Paul J.，Tem R.，2004 开课院系：计算机科学与技术系 一、实验的性质和任务 C++是一门高效实用的程序设计语言，它既可进行过程化程序设计，也可进行面向对象程序设计。随着C++逐渐成为ANSI标准，这种新的面向对象程序设计语言已经成为了程序员最广泛使用的工具。本课程是一门计算机及相关专业的重要的专业基础课，开设实验课程主要目的是使学生掌握有关C++语言的基本概念、基本语法和编程方法，理解C++语言面向对象的重要特征，促使学生理论联系实际，能够灵活应用自己所学的理论知识进行程序开发，增强学生的实践动手技能，并能够提高学生独立分析问题和解决问题的能力。 二、实验的基本内容及要求 实验 一、C++程序的运行环境、简单C++数据类型及运算（1学时）1． 实验目的 (1)熟悉VC++6.0集成开发环境；掌握简单C++程序的编辑、编译和运行 (2)熟悉和理解C＋＋语言中的数据类型、表达式；掌握简单C++程序的编写及调试方法 2． 实验内容 (1)熟悉VC++6.0集成开发环境的基本操作方法，学会独立使用该系统(2)了解在该系统上如何编辑、编译、连接和运行一个C++程序(3)通过运行一个简单的C++程序，初步了解C++源程序的特点 (4)熟悉和理解C＋＋语言中的数据类型、表达式，了解基本数据类型的字节宽度和范围表示 (5)利用学习的数据类型，编制简单的C＋＋程序实验准备(6)初步学习程序调试方法 3． 实验准备 (1)安装Visual C++编译系统 (2)熟悉Vc++6.0编译系统的使用步骤，以及简单C++程序的编辑、编译和运行过程(3)复习C++的基本数据类型，表达式(4)复习程序的上机调试过程 (5)根据实验内容要求，编写好实验程序 4． 实验步骤 (1)选择菜单“开始/程序/Microsoft Visual Studio 6.0/Microsoft Visual C++ 6.0”,得到Visual C++ 6.0启动后的用户界面；(2)创建一个新工程； (3)编写一个简单的C++源程序，并保存；(4)编译连接和运行程序 (5)输入源程序，编译、连接直到没有错误(6)运行程序，观察程序运行结果 5． 实验报告 （1）提交源程序 （2）举例说明在建立源程序、编译、连接程序时，发现的错误属于何种类型及解决办法 （3）改变所用变量的数据类型，观察程序运行结果的变化并分析原因（4）写出上机实验体会和实验报告 实验 二、数组（1学时）1．实验目的 熟练掌握一维数组和二维数组的定义、引用和初始化；掌握字符数组与字符串的关系以及字符串变量的表示，熟练字符串处理函数的应用。2.实验内容 (1)有一个数组，内放10个整数，找出最小的数和它的下标，然后把它和数组中最前面的元素对换 输入一个n×n的矩阵，求出两条对角线元素值之和 编写一程序，将两个字符串连接起来，不要strcat函数 3．实验准备 （1）复习一维数组和二维数组的定义、引用和初始化方法，进一步了解常用字符串处理函数的使用。 （2）根据实验内容要求，编写好实验程序 4．实验步骤 （1）输入源程序，编译、连接直到没有错误（2）根据实验步骤，撰写实验报告 5．实验报告 （1）结合上课内容，写出程序，并调试程序，要给出测试数据和实验结果（2）整理上机步骤，总结经验和体会（3）完成实验报告和提交源程序 实验 三、函数与编译预处理（1学时）1．实验目的 掌握函数的定义、申明和使用方法；掌握函数调用的方法；掌握全局变量、局部变量、静态变量的使用方法；掌握编译预处理的使用。2.实验内容 （1）求两正整数的最大公约数和最小公倍速数，用一个函数求最大公约数，另一个函数求最小公倍数。要求：不使用全局变量。将最大公约数和最小公倍数在主函数中输出。 （2）十进位制数转换二、八和十六进制数程序。要求： a.编写一个函数实现十进制数转换其它进制数； b.在主函数中给十进制数和转换的进位制，输出转换结果。 3．实验准备 (1)复习函数的定义、申明和使用方法，熟悉函数调用和编译预处理(2)根据实验内容要求，编写好实验程序 4．实验步骤 (1)输入源程序，编译、连接直到没有错误(2)根据实验步骤，撰写实验报告 5．实验报告 (1)结合上课内容，写出程序，并调试程序，要给出测试数据和实验结果(2)整理上机步骤，总结经验和体会(3)完成实验报告和提交源程序 实验 四、指针（2学时）1．实验目的 熟练掌握各种类型指针的定义、申明、引用和运算；掌握数组指针和指向数组的指针变量，以及字符串的指针和指向字符串的指针变量；了解指针与链表关系。2.实验内容 (1)编写程序，在堆内存中申请一个float型数组，把10个float型数据0.1、0.2、0.3„、1.0赋予该数组，然后使用float型指针输出该数组的各元素值并求出其累加和。(2)使用指针编写函数strcat()函数，即实现两个字符串的首尾连接（将字符串str2接到str1的后面，str1最后面的‘ ’被取消）。 (3)用指针变量设计一通用函数，该函数查找实型数组中最大和最小元素并输出相应元素和下标。3．实验准备 (1)复习指针的定义、申明和引用方法，以及其它各种类型指针的定义以及使用(2)根据实验内容要求，编写好实验程序 4．实验步骤 (1)输入源程序，编译、连接直到没有错误(2)根据实验步骤，撰写实验报告 5．实验报告 (1)结合上课内容，写出程序，并调试程序，要给出测试数据和实验结果(2)整理上机步骤，总结经验和体会(3)完成实验报告和提交源程序 实验 五、类和对象（2学时）1．实验目的 掌握类的定义以及类对象的定义；理解类的成员的访问控制的含义，公有、私有和保护成员的区别；掌握构造函数和析构函数的含义与作用、定义方式和实现，能够根据要求正确定义和重载构造函数，能够根据给定的要求定义类并实现类的成员函数。2.实验内容 (1)定义一个圆类，计算圆的面积和周长。要求：分别用成员函数和友元函数来求圆的面积和周长。 (2)定义一个学生类，其中有3个数据成员有学号、姓名、年龄，以及若干成员函数。同时编写主函数使用这个类，实现对学生数据的赋值和输出。要求： a)使用成员函数实现对输出的输入、输出； b)使用构造函数和析构函数实现对数据的输入、输出。 3．实验准备 (1)复习类以及对象的定义和使用 (2)复习构造函数和析构函数的作用、定义方式和实现(3)根据实验内容要求，编写好实验程序 4．实验步骤 (1)输入源程序，编译、连接直到没有错误(2)根据实验步骤，撰写实验报告 5．实验报告 (1)结合上课内容，写出程序，并调试程序，要给出测试数据和实验结果(2)整理上机步骤，总结经验和体会(3)完成实验报告和提交源程序 实验 六、继承与派生类（2学时）1．实验目的 理解继承的含义；掌握派生类的定义方法和实现；理解公有继承下基类成员对派生类成员和派生类对象的可见性，能正确地访问继承层次中的各种类成员； 理解保护成员在继承中的作用，能够在适当的时候选择使用保护成员以便派生类成员可以访问基类的部分非公开的成员；理解虚函数在类的继承层次中的作用，虚函数的引入对程序运行时的影响，能够对使用虚函数的简单程序写出程序结果。2.实验内容 1)编写一个学生和教师数据输入和显示程序，学生数据要求有编号、姓名、班号和成绩，教师数据有编号、姓名、职称和部门。要求将编号、姓名的输入和显示设计成一个类person，并作为学生数据操作类student和教师数据操作类teacher的基类，学生数据中的班号和成绩的输入和显示在student类中实现，教师数据中的职称和部门的输入和显示在teacher类中实现。最后在主函数中进行该类的测试。 2)编写一个程序计算出球、圆柱和圆锥的表面积和体积。要求： (1)定义一个基类圆，至少含有一个数据成员半径； (2)定义基类的派生类球、圆柱、圆锥，都含有求表面积和体积的成员函数和输出函数； (3)定义主函数，求球、圆柱、圆锥的和体积。 3．实验准备 (1)复习继承和派生类的定义和实现方法 (2)复习不同继承方式下，派生类成员对基类成员的访问方式(3)根据实验内容要求，编写好实验程序 4．实验步骤 (1)输入源程序，编译、连接直到没有错误(2)根据实验步骤，撰写实验报告 5．实验报告 (1)结合上课内容，写出程序，并调试程序，要给出测试数据和实验结果(2)整理上机步骤，总结经验和体会(3)完成实验报告和提交源程序 实验 七、多态性和虚函数（1学时）1．实验目的 掌握运算符重载的概念以及使用friend重载运算符的方法；掌握虚函数和纯虚函数的概念及应用 2.实验内容 1) 分别用成员函数和友元函数重载运算符，使对整型的运算符=、+、-、*、/ 适用于分数运算。要求： (1)输出结果是最简分数（可以是带分数）；(2)分母为1，只输出分子。2) 下列shape类是一个表示形状的抽象类，area()为求图形面积的函数。请从shape类派生三角形类(triangle)、圆类（circles）、并给出具体的求面积函数。#include (1)复习运算符重载的概念以及使用friend重载运算符的方法(2)根据实验内容要求，编写好实验程序 4．实验步骤 (1)输入源程序，编译、连接直到没有错误(2)根据实验步骤，撰写实验报告 5．实验报告 (1)结合上课内容，写出程序，并调试程序，要给出测试数据和实验结果(2)整理上机步骤，总结经验和体会(3)完成实验报告和提交源程序 三、参考书目 1．《C++程序设计实验指导》，清华大学出版社，钱能，2001.2.《C++大学教程实验指导书》，电子工业出版社，Harvey M., Paul J., Tem R., 2003.3.《C++程序设计实验指导与实训》，中国水利水电出版社，蔡立军，杜四春，银红霞，2004.制定人：谢永华 审定人：王新芝 批准人：顾韵华 C++ 实验总结报告 研究课题：图形编辑器 一、实验目的 1.熟悉C++的一些重要性质，利用封装、继承、虚函数和多态性等特性，通过实验学习如何对各类图元的属性和方法进行合理的封装 2.学习Microsoft的Visual C++编程工具 3.掌握MFC的相关知识 4.掌握基本的文件保存、读取以及操作封装技术 二、实验目的 设计一个简单的图形编辑器 三、实验所用仪器、设备 计算机：PentiumIII 800 以上 256M内存 操作系统：Windows 2000/XP 开发集成环境：Visual C++ 6.0 四、软件功能简介 （注：此软件是从网上下载得来） 该软件具有汉化的菜单界面（仿Windows自带画图软件），具有文件打开、编辑、保存等功能。编辑部分包括可以在编辑区域画直线、圆、矩形、曲线等矢量图形，可插入文字，可以修改线条的线型、颜色等基本属性。 五、部分代码分析 1.类的初始分析： class CDrawApp : public CWinApp { public: CDrawApp(); // Overrides virtual BOOL InitInstance(); // Implementation protected: //{{AFX_MSG(CDrawApp)afx_msg void OnAppAbout();// NOTE-the ClassWizard will add and remove member functions here.// DO NOT EDIT what you see in these blocks of generated code!//}}AFX_MSG DECLARE_MESSAGE_MAP()};学习C++我们最需要理解的就是它面向对象的设计思想。这种思想可以在类和对象上得到充分的体现。 类是面向对象程序设计的核心，它实际上是由用户定义的一种新的复杂数据类型。它是通过抽象数据类型ADT方法来实现的一种数据类型，将不同类型的数据和与这些数据相关的操作封装在一起形成一个集合体。因此，它具有更高的抽象性，实现了信息的隐藏和封装。 对象是某种类的一个实例，是类的具体体现。一个类可以有多个对象。 分析这一段代码，编程者将CDrawApp();设置为公有函数，这样做就是在整个函数的外面开了一个口，使用户可以利用这一函数处理具体问题而不必详解函数内部，是面向对象中封装特性的一个具体体现；另外，此函数中还包含了构造函数与析构函数，构造函数完成对新对象的初始化工作，析构函数是构造函数的配对物，它实现与构造函数相反的功能。另外，这段代码中还包括布尔型虚函数InitInstance()，这是函数重载，也是多态性的具体体现。 由这段代码我们可以了解关于类和对象的一些知识，为我们进一步了解面向对象程序设计的思想精髓奠定了基础。 2.对构造函数和析构函数的分析 构造函数 CCreateLine::CCreateLine(): m_begin(0,0), m_end(0,0){ m_nStep = 0;// 初始化操作步为 0 } 构造函数:C++中“类”只定义了一组对象的类型。要使用这个类还必须用“类”说明它的对象，每个对象中的数据成员还必须赋初值，这些功能都是由构造函数完成的。此造函数用初始化列表的方式对直线类的私有成员进行初始化，同时记下操作步m_nStep是直线类从指令类中继承来的成员，它在指令类中属于保护成员，在直线类中则成为私有成员。这是数据共享与数据保护两者兼顾时的一种处理方法。 析构函数 CCreateLine::~CCreateLine(){ } 它是构造函数的配对物，与构造函数一样是与类同名的成员函数，并在函数名前加上一个’~’以便与构造函数相区别。此析构函数中没有任何操作语句，但它并非没有任何操作。在任何一个对象消失时都要调用本类的析构函数进行扫尾工作。在构造对象时，构造函数分配资源给程序，在对象作用结束后，这些资源的释放就要靠析构函数。当然析构函数中也是可以有语句的，当需要在对象消失之前执行某种操作时，可以把语句写在里边。 3.继承和虚函数分析 class CDrawRect : public CDrawObj { protected: DECLARE_SERIAL(CDrawRect);CDrawRect(); public: CDrawRect(const CRect& position);//添加了对新数据成员的初始化 // Implementation public: virtual void Serialize(CArchive& ar);//添加了对新数据成员操作 virtual void Draw(CDC* pDC);//根据要求画出每个图形 virtual int GetHandleCount();//line和roundRectangle特殊处理 virtual CPoint GetHandle(int nHandle);//line和roundRectangle特殊处理 virtual HCURSOR GetHandleCursor(int nHandle);//line和roundRectangle特殊处理 virtual void MoveHandleTo(int nHandle, CPoint point, CDrawView* pView = NULL);//通过特征点来修改大小 virtual BOOL Intersects(const CRect& rect);//判断与图形是否存在相交 virtual CDrawObj* Clone(CDrawDoc* pDoc);//Clone一个新对象加入到pDoc中 protected: enum Shape { rectangle, roundRectangle, ellipse, line };Shape m_nShape;//通过枚举变量来标示属于上述四种的哪一种形状 CPoint m_roundness;// for roundRect corners friend class CRectTool;};在阅读此函数的源代码过程中，我感觉到对基类中虚函数的使用对整个程序具有着十分重要的意义。正如上段代码，它的前提是派生类CDrawRect对基类CDrawObj进行了继承，只有在对基类中的虚函数进行设置后，我们才能更加高效地处理和使用基类和派生类中的方法。所以，我感觉到在学习面向对象程序设计时，应当尤为注意基类中虚方法的创建和后期调用。 六、个人学习体会 在学习C++以前，我认为C++只是在C语言的基础上的一种延伸，认为只要学过C语言，就可以用C语言的那种设计思想来学习C++、设计C++程序。正是由于抱了这种错误的思想，使我在一开始学习C++的时候遇到了很大的困难，我没有办法体会面向对象的设计思想，我在学习这门课的时候老是想着实现这个函数功能的具体过程，而没太注意对象分类的重要性。 随着课程学习的深入，我感觉到了利用类和对象、继承、封装等一系列知识可以把我们程序中很多繁杂、重复的部分省略掉，还可以解决一些利用面向过程的设计思想无法解决的问题，我自己也试着编写一些小的C++程序，当然在这个过程中遇到了很多困难，其中调试带来的困难让我无法忘记，在调试程序的同时，我也总结出来了一些调试的小技巧，让我在C语言课程设计中也受用匪浅。 在学习这门课的过程中，我感受到了自己亲自动手编程序、调程序的重要性，我们要熟悉C++的语法、体会调试的思想，最好的一个手段就是自己动手编程、调试，这会比我们一味的看书效果好得多。 另外，我还感觉到一个好的程序编出来需要很多人的团结合作。我在检查自己编写的程序是否有BUG未被找出的时候，我会让我的同学作为一个程序使用者来找出未发现的BUG并提出改进意见，这让我们的工作更加高效。 很高兴能够了解到C++的神奇魅力和面向对象程序设计的独特思想，它为我今后的程序设计奠定了基础。感谢老师对我们的悉心教授！第二篇：C++数据结构 大作业课程设计
第三篇：C++实验
第四篇：c++实验(网络工程 ))
第五篇：C++实验总结报告
点击咨询 