前 言
《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。
一、实验目的
更好的理解算法的思想、培养编程能力。
二、实验要求
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 cla 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 (ilength) 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+
1 return 0;
//退出循环，说明查找失败 }
template
void SeqList::Insert(int i, T x) {
if (length>=MaxSize) throw \"上溢\";
if (ilength+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 (ilength) throw \"位置\";
x=data[i-1];
for (j=i; j
data[j-1]=data[j];
//注意此处j已经是元素所在的数组下标
length--;
return x; }
链表类定义：将该类保存在文件LinkList.h中。 template struct Node {
T data;
Node *next; //此处也可以省略
} template cla LinkList { public: LinkList( ){first=new Node; first->next=NULL;} //建立只有头结点的空链表
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 *first; //单链表的头指针 }; template
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 && jnext;
//工作指针p后移 j++; } if (!p) throw \"位置\"; else {
s=new Node; s->data=x; //向内存申请一个结点s，其数据域为x
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->data=a[i]; //为每个数组元素建立一个结点
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; s->data=a[i]; //为每个数组元素建立一个结点
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 a(r,50);
cout
a.PrintList( );
a.Delete(6);
cout
} 2．
#include
#include
void divid( LinkList &L)
{ Node *p,*q,*h;
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 List(r, 10);
cout
List.PrintList( );
divid (List);
cout
6．void Add(LinkList &A, LinkList B) { pre=A.first; p=pre->next; //工作指针p初始化，指针pre始终指向p的前驱结点 qre=B.first; q=qre->next; //工作指针q初始化，指针qre始终指向q的前驱结点 while（p&&q） {
if (p->expexp) {
//第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 cla 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 void SeqStack::Push(T x) {
if (top== StackSize-1) throw \"上溢\";
top++;
data[top]=x;
}
template T SeqStack:: Pop( ) {
if (top==-1) throw \"下溢\";
x=data[top--];
return x;
}
2． 链式栈类的定义
template cla LinkStack { public:
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 *top; //栈顶指针即链栈的头指针 };
template
void LinkStack::Push(T x)
{
s=new Node; s->data=x; //申请一个数据域为x的结点s
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 cla BothStack { public:
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 void BothStack:: Push(int i, T x ) { if (top1==top2-1) throw \"上溢\"; if (i==1) data[++top1]=x; if (i==2) data[--top2]=x; } template T BothStack:: Pop(int i) { if (i==1) {
//将栈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 cla 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 void CirQueue::EnQueue(T x)
{
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 T CirQueue::DeQueue( ) {
if (rear==front) throw \"下溢\";
front=(front+1) % QueueSize;
//队头指针在循环意义下加1
return data[front];
//读取并返回出队前的队头元素，注意队头指针 }
5.链队列类定义
template cla LinkQueue { public:
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 *front, *rear; //队头和队尾指针，分别指向头结点和终端结点 }; template
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; s->next=NULL; //创建一个头结点s
front=rear=s;
//将队头指针和队尾指针都指向头结点s
}
template
void LinkQueue::EnQueue(T x)
{
s=new Node; s->data=x; //申请一个数据域为x的结点s
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行的中间位置填
1 for (i=2; 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 struct GLNode {
Elemtag tag;
//标志域，用于区分元素结点和表结点
union
{
//元素结点和表结点的联合部分
T data;
//data是元素结点的数据域
struct
{ GLNode *hp, *tp;
//hp和tp分别指向表头和表尾
} ptr;
}; }; template cla Lists { public:
Lists( ) {ls=NULL;}
//无参构造函数，初始化为空的广义表
Lists(Lists ls1, Lists ls2);
//有参构造函数，用表头ls1和表尾ls2构造广义表
~Lists( );
//析构函数，释放广义表中各结点的存储空间
int Length( );
//求广义表的长度
int Depth(GLNode *ls);
//求广义表的深度
GLNode *Head( ); //求广义表的表头
GLNode *Tail( );
//求广义表的表尾 private:
GLNode *ls; //ls是指向广义表的头指针 }; template
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 *ls)
{ 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 GLNode * Lists::Head( )
{
return ls->ptr.hp; } 8．取广义表表尾算法Tail template GLNode *Lists::Tail( ) {
return ls-> ptr.tp; }
实验四 树和二叉树
实验类型：验证性 实验要求：必修 实验学时： 2学时
一、实验目的：
参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。
二、实验要求：
1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1．设计实现二叉树类，要求：
（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。 （2）实现二叉树层次遍历的非递归算法。 （3）编写一主函数来验证算法实现。
2.假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。 *3.设计实现二叉线索链表类，要求：
（1）编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。
（2）编写一主函数来验证算法实现。 *4.编写求二叉树高度的函数。
*5.编写创建哈夫曼树和生成哈夫曼编码的算法。
*6．假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。
*7．假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数）
四、程序样例
１．二叉树 二叉链表结点声明 template struct BiNode {
T data;
BiNode *lchild, *rchild; }; 二叉链表类声明
template cla BiTree { public:
BiTree( ){root=NULL;} //无参构造函数，初始化一棵空的二叉树
BiTree(BiNode *root); //有参构造函数，初始化一棵二叉树，其前序序列由键盘输入
~BiTree( );
//析构函数，释放二叉链表中各结点的存储空间
void PreOrder(BiNode *root);
//前序遍历二叉树
void InOrder(BiNode *root);
//中序遍历二叉树
void PostOrder(BiNode *root);
//后序遍历二叉树
void LeverOrder(BiNode *root);
//层序遍历二叉树 private:
BiNode *root;
//指向根结点的头指针
void Creat(BiNode *root);
//有参构造函数调用
void Release(BiNode *root);
//析构函数调用 }; 二叉树的层序遍历算法LeverOrder template void BiTree::LeverOrder(BiNode *root) { front=rear=0; //采用顺序队列，并假定不会发生上溢 if (root==NULL) return; Q[++rear]=root; while (front!=rear) { q=Q[++front]; coutdata;
if (q->lchild!=NULL)
Q[++rear]=q->lchild; if (q->rchild!=NULL)
Q[++rear]=q->rchild;
} } 二叉树的构造函数算法BiTree template BiTree ::BiTree(BiNode *root) {
creat(root)； } template void BiTree ::Creat(BiNode *root) {
cin>>ch;
if (ch==\'# \') root=NULL;
//建立一棵空树
else {
root=new BiNode;
//生成一个结点
root->data=ch;
Creat(root->lchild);
//递归建立左子树
Creat(root->rchild);
//递归建立右子树
} } 二叉树的后序遍历递归算法PostOrder template void BiTree::PostOrder(BiNode *root) {
if (root==NULL) return;
//递归调用的结束条件 else { PostOrder(root->lchild);
//后序递归遍历root的左子树
PostOrder(root->rchild);
//后序递归遍历root的右子树
coutdata;
//访问根结点的数据域
}
} 二叉树的后序遍历非递归算法PostOrder template void BiTree::PostOrder(BiNode *root)
{ 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;
coutdata; } if (top!= -1) {
s[top].flag=2;
root=s[top].ptr->rchild;
} } } 二叉树前序遍历递归算法PreOrder template void BiTree::PreOrder(BiNode *root)
{
if (root ==NULL)
return;
//递归调用的结束条件 else { coutdata;
//访问根结点的数据域
PreOrder(root->lchild);
//前序递归遍历root的左子树
PreOrder(root->rchild);
//前序递归遍历root的右子树
}
} 二叉树的前序遍历非递归算法PreOrder template void BiTree::PreOrder(BiNode *root)
{ top= -1;
//采用顺序栈，并假定不会发生上溢
while (root!=NULL | | top!= -1) { while (root!= NULL) {
coutdata; s[++top]=root; root=root->lchild;
} if (top!= -1) {
root=s[top--];
root=root->rchild;
}
} } 二叉树的析构函数算法BiTree template BiTree ::~BiTree(BiNode *root) {
Release(root); } void BiTree ::Release(BiNode *root) {
if (root!=NULL) {
Release(root->lchild);
//释放左子树
Release(root->rchild);
//释放右子树
delete root;
}
} 二叉树的中序遍历递归算法InOrder template void BiTree::InOrder (BiNode *root) {
if (root==NULL) return;
//递归调用的结束条件
else { InOrder(root->lchild);
//中序递归遍历root的左子树
coutdata;
//访问根结点的数据域
InOrder(root->rchild);
//中序递归遍历root的右子树
} } ２．线索链表
线索链表结点声明
enum flag {Child, Thread};
//枚举类型，枚举常量Child=0，Thread=1 template struct ThrNode {
T data;
ThrNode *lchild, *rchild;
flag ltag, rtag; }; 线索链表类声明 template cla InThrBiTree { public:
InThrBiTree(ThrNode * root);
//构造函数，建立中序线索链表
~ InThrBiTree( );
//析构函数，释放线索链表中各结点的存储空间
ThrNode *Next(ThrNode *p); //查找结点p的后继
void InOrder(ThrNode *root); //中序遍历线索链表 private:
ThrNode *root; //指向线索链表的头指针
void Creat(ThrNode *root);
//构造函数调用
void ThrBiTree(ThrNode *root);
//构造函数调用 }; 中序线索链表构造函数算法InThrBiTree template InThrBiTree::InThrBiTree(ThrNode *root)
{
Creat(root);
pre=NULL;
ThrBiTree(root); } template void InThrBiTree ::Creat(ThrNode *root) {
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 void InThrBiTree ::ThrBiTree(ThrNode *root) {
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 ThrNode *InThrBiTree::Next(ThrNode *p) {
if (p->rtag==1) q=p->rchild;
//右标志为1，可直接得到后继结点
else {
q=p->rchild;
//工作指针初始化，
while (q->ltag==0)
//查找最左下结点
q=q->lchild;
} return q; } 中序线索链表查找后继的算法Next template void InThrBiTree::InOrder(ThrNode *root) {
if (root==NULL) return; //如果线索链表为空，则空操作返回
p=root;
while (p->ltag==0)
//查找中序遍历序列的第一个结点p并访问
p=p->lchild; coutdata; while (p->rchild!=NULL)
//当结点p存在后继，依次访问其后继结点
{ p=Next(p); coutdata; } } 中序线索链表构造函数算法InThrBiTree template InThrBiTree::InThrBiTree(ThrNode *root)
{
Creat(root);
pre=NULL;
ThrBiTree(root); } template void InThrBiTree ::Creat(ThrNode *root) {
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 void InThrBiTree ::ThrBiTree(ThrNode *root) {
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
//初始化
{ 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
//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 struct VertexNode
//定义顶点表结点 {
T vertex;
ArcNode *firstedge; }; const int MaxSize=10;
//图的最大顶点数 template cla ALGraph { public:
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 ALGraph::ALGraph(T a[ ], int n, int e) { vertexNum=n; arcNum=e; for (i=0; i
//输入顶点信息，初始化顶点表 {
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 void ALGraph::DFSTraverse(int v) {
cout
p=adjlist[v].firstedge;
while (p)
//依次搜索顶点v的邻接点j { j=p->adjvex; if (visited[j]==0) DFSTraverse(j);
p=p->next;
} } template void ALGraph::BFSTraverse(int v)
{ 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 cla MGraph { public:
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 MGraph::MGraph(T a[ ], int n, int e)
{ 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[num++]= G.vertex[k];
//将新生成的终点加入集合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
{
mid=(low+high)/2;
if (kr[mid]) low=mid+1;
else return mid;
} return 0; } ４．单链表的顺序查找算法SeqSearch2 int SeqSearch2(Node *first, int k)
{
p=first->next; j=1;
while (p!=NULL && p->data!=k)
{
p=p->next;
j++;
}
if (p->data==k) return j;
else return 0; } ５．二叉排序树类声明
cla BiSortTree
//本章假定记录中只有一个整型数据项
{
public: BiSortTree(int a[ ], int n);
//建立查找集合a[n]的二叉排序树
~ BiSortTree( );
//析构函数，释放二叉排序树中所有结点，同二叉链表的析构函数 void InsertBST(BiNode *root , BiNode *s); //在二叉排序树中插入一个结点s void DeleteBST(BiNode *p, BiNode *f ); //删除结点f的左孩子结点p BiNode *SearchBST(BiNode *root, int k); //查找值为k的结点
private:
BiNode *root;
//二叉排序树（即二叉链表）的根指针
};
二叉排序树构造函数算法BiSortTree BiSortTree::BiSortTree(int r[ ], int n) { for (i=0; i; s->data=r[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 *root, BiNode *s) {
if (root==NULL) root=s;
else if (s->datadata) InsertBST(root->lchild, s);
else InsertBST(root->rchild, s); }
二叉排序树查找算法SearchBST BiNode * BiSortTree::SearchBST(BiNode *root, int k)
{
if (root==NULL) return NULL；
else if (root->data==k) return root;
else if (kdata) return SearchBST(root->lchild, k);
else return SearchBST(root->rchild, k);
}
二叉排序树的删除算法DeleteBST void BiSortTree::DeleteBST(BiNode *p, BiNode *f )
{ 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 *HashSearch2(Node *ht[ ], int m, int k) {
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->data=k;
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
//在无序区中选取最小记录
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
{
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
{ 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
//筛选还没有进行到叶子
{
if (jr[j]) break;
//根结点已经大于左右孩子中的较大者
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
{
MergePa(r, r1, n, h);
h=2*h;
MergePa(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
{
if (r[i]
//取r[i]和r[j]中较小者放入r1[k]
else r1[k++]=r[j++]; } if (i
//若第一个子序列没处理完，则进行收尾处理
r1[k++]=r[i++];
else while (j
r1[k++]=r[j++];
}
void MergePa(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
//待归并序列中只剩一个子序列
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 #include #include #define MAX 2 /*车库容量*/ #define price 0.05 /*每车每分钟费用*/ typedef struct time{ int hour; int min; }Time; /*时间结点*/ typedef struct node{ char num[10]; Time reach; Time leave; }CarNode; /*车辆信息结点*/ typedef struct NODE{ CarNode *stack[MAX+1]; int top; }SeqStackCar; /*模拟车站*/ typedef struct car{ CarNode *data; struct car *next; }QueueNode; typedef struct Node{ QueueNode *head; QueueNode *rear; }LinkQueueCar; /*模拟通道*/ void InitStack(SeqStackCar *); /*初始化栈*/ int InitQueue(LinkQueueCar *); /*初始化便道*/ int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/ void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ void List(SeqStackCar,LinkQueueCar); /*显示存车信息*/ void main() {SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; InitStack(&Enter); /*初始化车站*/ InitStack(&Temp); /*初始化让路的临时栈*/ InitQueue(&Wait); /*初始化通道*/ while(1) { printf(\"\\n1.车辆到达\"); printf(\" 2.车辆离开\"); printf(\" 3.列表显示\"); printf(\" 4.退出系统\\n\"); while(1) {scanf(\"%d\",&ch); if(ch>=1&&chtop=0; for(i=0;istack[s->top]=NULL;} int InitQueue(LinkQueueCar *Q) /*初始化便道*/ {Q->head=(QueueNode *)malloc(sizeof(QueueNode)); if(Q->head!=NULL) {Q->head->next=NULL; Q->rear=Q->head; return(1);} else return(-1);} void PRINT(CarNode *p,int room) /*打印出站车的信息*/ {int A1,A2,B1,B2; printf(\"\\n请输入离开的时间:/**:**/\"); scanf(\"%d:%d\",&(p->leave.hour),&(p->leave.min)); printf(\"\\n离开车辆的车牌号为:\"); puts(p->num); printf(\"\\n其到达时间为: %d:%d\",p->reach.hour,p->reach.min); printf(\"离开时间为: %d:%d\",p->leave.hour,p->leave.min); A1=p->reach.hour; A2=p->reach.min; B1=p->leave.hour; B2=p->leave.min; printf(\"\\n应交费用为: %2.1f元\",((B1-A1)*60+(B2-A2))*price); free(p); } int Arrival(SeqStackCar *Enter,LinkQueueCar *W) /*车辆到达*/ { CarNode *p; QueueNode *t; p=(CarNode *)malloc(sizeof(CarNode)); flushall(); printf(\"\\n请输入车牌号(例:陕A1234):\"); gets(p->num); if(Enter->toptop++; printf(\"\\n车辆在车场第%d位置.\",Enter->top); printf(\"\\n请输入到达时间:/**:**/\"); scanf(\"%d:%d\",&(p->reach.hour),&(p->reach.min)); Enter->stack[Enter->top]=p; return(1);} else /*车场已满，车进便道*/ { printf(\"\\n该车须在便道等待!\"); t=(QueueNode *)malloc(sizeof(QueueNode)); t->data=p; t->next=NULL; W->rear->next=t; W->rear=t; return(1); }} void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) { /*车辆离开*/ int i, room; CarNode *p,*t; QueueNode *q; /*判断车场内是否有车*/ if(Enter->top>0) /*有车*/ { while(1) /*输入离开车辆的信息*/ {printf(\"\\n请输入车在车场的位置/1--%d/：\",Enter->top); scanf(\"%d\",&room); if(room>=1&&roomtop) break;} while(Enter->top>room) /*车辆离开*/ {Temp->top++; Temp->stack[Temp->top]=Enter->stack[Enter->top]; Enter->stack[Enter->top]=NULL; Enter->top--; } p=Enter->stack[Enter->top]; Enter->stack[Enter->top]=NULL; Enter->top--; while(Temp->top>=1) {Enter->top++; Enter->stack[Enter->top]=Temp->stack[Temp->top]; Temp->stack[Temp->top]=NULL; Temp->top--;} PRINT(p,room); /*判断通道上是否有车及车站是否已满*/ if((W->head!=W->rear)&&Enter->tophead->next; t=q->data; Enter->top++; printf(\"\\n便道的%s号车进入车场第%d位置.\",t->num,Enter->top); printf(\"\\n请输入现在的时间/**:**/:\"); scanf(\"%d:%d\",&(t->reach.hour),&(t->reach.min)); W->head->next=q->next; if(q==W->rear) W->rear=W->head; Enter->stack[Enter->top]=t; free(q);} else printf(\"\\n便道里没有车.\\n\");} else printf(\"\\n车场里没有车.\"); /*没车*/ } void List1(SeqStackCar *S) /*列表显示车场信息*/ {int i; if(S->top>0) /*判断车站内是否有车*/ {printf(\"\\n车场:\"); printf(\"\\n 位置 到达时间 车牌号\\n\"); for(i=1;itop;i++) {printf(\" %d \",i); printf(\"%d:%d \",S->stack[i]->reach.hour,S->stack[i]->reach.min); puts(S->stack[i]->num);}} else printf(\"\\n车场里没有车\");} void List2(LinkQueueCar *W) /*列表显示便道信息*/ { QueueNode *p; p=W->head->next; if(W->head!=W->rear) /*判断通道上是否有车*/ {printf(\"\\n等待车辆的号码为:\"); while(p!=NULL) {puts(p->data->num); p=p->next;}} else printf(\"\\n便道里没有车.\"); } void List(SeqStackCar S,LinkQueueCar W) {int flag,tag; flag=1; while(flag) {printf(\"\\n请选择 1|2|3:\"); printf(\"\\n1.车场\\n2.便道\\n3.返回\\n\"); while(1) { scanf(\"%d\",&tag); if(tag>=1||tag
（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方法负责，每个窗口都由一个窗口对象表示，它描述了窗口名及其在可用窗口表中的号码。
根据以上问题写出实验报告。
