实验任务书(8个).doc

目 录

实验1 顺序表的应用 2
实验2 链表的应用 5
实验3 栈的应用 6
实验4 队列的应用 7
实验5 树的应用 8
实验6 图的应用 9
实验7 图的应用 10
实验8 查找与排序 11

实验1 顺序表的应用
实验目的
1． 熟悉C语言的上机环境，掌握C语言的基本结构。
2． 会定义线性表的顺序存储结构。
3． 熟悉对顺序表的一些基本操作和具体的函数定义。
4． 掌握在线性表的顺序存储结构上的一些其它操作。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容
1、基础题：
编写应用程序（填空），实现可以在顺序表中插入任意给定数据类型（定义为抽象数据类型）数据的功能。要求在主函数中定义顺序表并对该顺序表插入若干个整数类型的数据（正整数），对它们求和并输出。请使用动态内存分配的方式申请数组空间，并把主函数设计为一个文件SeqList.cpp，其余函数设计为另一个文件SeqList.h。
请填空完成以下给出的源代码并调试通过。

（1） 文件SeqList.h:

typedef struct List{
ElemType *list;
int size;
int MaxSize;
}SeqList;

void InitList(SeqList &L)
{ //初始化线性表
…………
}

void ClearList(SeqList &L)
{ //清除线性表
………………
}

int LengthList(SeqList L)
{ //求线性表长度
………..
}

bool InsertList(SeqList &L, ElemType item, int pos)
{ //按给定条件pos向线性表插入一个元素
…….
}

ElemType GetList(SeqList L, int pos)
{ //在线性表L中求序号为pos的元素，该元素作为函数值返回
…………..
}

（2）文件SeqList.cpp：

#include <stdio.h>
#include <stdlib.h>

typedef ElemType;
#define MAXSize 10

#include "SeqList.h"

void main(void)
{
SeqList myList;
int i=1, x, sum=0, n;

InitList ( );
scanf(“%d”, &x);
while ( x!= -1 )
{
if ( InsertList (myList, , i )==0) {
printf("错误!\n");
return ;
}
i++;
scanf(“%d”, &x);
}

n = LengthList (myList);
for (i=1; i<=n; i++)
{
x=GetList(myList, i);
sum = + x;
}
printf("%d\n ", sum);

ClearList(myList);
}

2、提高部分：编写函数bool DeleteElem(SeqList &L, int min, int max) 实现从顺序表中删除其值在给定值min和max之间（min < max）的所有元素，要求把该函数添加到文件SeqList.h中，并在主函数文件SeqList.cpp中添加相应语句进行测试。

实验2 链表的应用
实验目的
1． 定义单链表的结点类型。
2． 熟悉对单链表的一些基本操作和具体的函数定义。
3． 通过单链表的定义掌握线性表的链式存储结构的特点。
4． 熟悉单链表的应用场合。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容
1、基础题：
线性表基本操作的实现(演示单链表的创建、插入、删除和查找等操作)，并请将链式存储结构的程序存放在文件link.h（基本操作函数）、link.cpp（主函数）中。（要求有简单实例测试算法的正确性）

2、提高题：
编写程序，模拟约瑟夫环（josephus）问题： n个人（编号为1，2，3，……，n (n>0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0<i<=n)，另一个为起始报数上限值m。接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，……，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。
基本要求:
人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由键盘输入。

实验3 栈的应用
实验目的
1． 会定义顺序栈和链栈的结点类型。
2． 掌握栈的插入和删除结点在操作上的特点。
3． 熟悉对栈的一些基本操作和具体的函数定义。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容
1、 基础题：
设栈采用顺序存储结构（用动态数组），请编写栈的各种基本操作的实现函数，并存放在头文件stack.h中。同时建立一个验证操作实现的主函数文件stack.cpp，编译并调试程序，直到正确运行。
提示：
⑴ 栈的动态数组顺序存储结构可定义如下：
struct Stack {
ElemType *stack ; // 存栈元素
int top; // 栈顶指示器
int MaxSize; // 栈的最大长度
};
⑵ 栈的基本操作可包括：
① void InitStack (Stack &S); //构造一个空栈 S
② int EmptyStack (Stack S); //若栈S为空栈返回1，否则返回0
③ void Push(Stack &S, ElemType item); //元素 item进栈
④ ElemType Pop(Stack &S); //栈S的栈顶元素出栈并返回
⑤ ElemType Peek(Stack S); //取栈S的当前栈顶元素并返回
⑥ void ClearStack (Stack &S); //清除栈s，使成为空栈
2、 应用题：
写一函数，判断给定的字符串是否中心对称。如字符串“abcba”、“abccba”均为中心对称，字符串“abcdba”不中心对称。要求利用stack.h中已实现的有关栈的基本操作函数来实现。请把该函数添加到文件stack.cpp中的主函数前，并在主函数中添加相应语句进行测试。函数原型如下：
int IsReverse(char *s) //判断字符串S是否中心对称，是返回1，否则返回0

实验4 队列的应用
实验目的
1． 掌握队列的存储结构及基本操作。
2． 掌握循环队列的设置及循环队列的各种基本操作的实现。
3． 通过具体的应用实例，进一步熟悉和掌握队列的实际应用。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容
1、 基础题：
建立头文件queue.h，定义顺序存储的循环队列存储结构，并编写循环队列的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件queue.cpp，编译并调试程序，直到正确运行。
说明：队列的基本操作可包括：
① void InitQueue (Queue &Q); //构造一个空队列 Q
② int EmptyQueue (Queue Q);
//判断队列Q是否为空，若空返回1，否则返回0
③ void EnQueue (Queue &Q, ElemType item); //元素 item 进队列Q
④ ElemType OutQueue (Queue &Q); //队头元素出队列Q，并返回其值
⑤ ElemType PeekQueue (Queue Q); //返回队头元素值
⑥ void ClearQueue (Queue &Q); //清空队列

2、 应用（选做部分）：
编写程序，实现舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求设计一个函数void partner()，模拟上述舞伴配对问题。
基本要求:
1) 由键盘输入数据，每对数据包括姓名和性别；
2) 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称和队头者的姓名；
3) 要求利用queue.h中已实现的顺序循环队列的基本操作函数来实现。函数void partner() 添加到文件queue.cpp中，在主函数中进行调用测试。

实验5 树的应用
实验目的
1． 熟悉二叉树结点的结构和对二叉树的基本操作。
2． 掌握对二叉树每一种操作的具体实现。
3． 学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
4． 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。
5． 掌握构造哈夫曼树以及哈夫曼编码的方法。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容
1、 基础题：
建立头文件tree.h，在该文件中定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件tree.cpp，编译并调试程序，直到正确运行。注意，需要用到栈和队列的有关操作，可使用已编制过的栈和队列的基本操作文件stack.h、queue.h来实现。
说明：二叉树的基本操作可包括：
(1) void InitBTree( BTreeNode *&BT ) //初始化二叉树BT
(2) void CreateBTree( BTreeNode *&BT, char *a )
//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构
(3) int EmptyBTree( BTreeNode *BT)
//检查二叉树BT是否为空，空返回1，否则返回0
(4) int DepthBTree( BTreeNode *BT) //求二叉树BT的深度并返回该值
(5) int FindBTree( BTreeNode *BT, ElemType x)
//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
2、提高部分：
(6) void PreOrder( BTreeNode *BT) //先序遍历二叉树BT
(7) void InOrder( BTreeNode *BT) //中序遍历二叉树BT
(8) void PostOrder( BTreeNode *BT) //后序遍历二叉树BT
(9) void LevelOrder( BTreeNode *BT ) //按层次遍历二叉树BT
(10) void PrintBTree( BTreeNode *BT ) //输出二叉树BT
(11) void ClearBTree( BTreeNode *&BT ) //清除二叉树BT

实验6 图的应用
实验目的
1． 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。
2． 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容（2选1）
1、 图的邻接矩阵定义及实现：
建立头文件AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件AdjM.cpp（以下图为例），编译并调试程序，直到正确运行。
0
1
2
4
6
5
3

2、图的邻接表的定义及实现：
建立头文件AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件AdjL.cpp中调用这些函数进行验证（以下图为例）。
00
11
22
33
4

实验7 图的应用
实验目的
1.掌握以邻接矩阵作为存储结构的生成图的最小生成树的普里姆算法。
2.掌握以邻接矩阵作为存储结构的生成图的最小生成树的克鲁斯卡尔算法。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容
1、 编写用邻接矩阵表示无向带权图时图的基本操作的实现函数，主要包括：①初始化邻接矩阵表示的无向带权图 void InitMatrix(adjmatrix G); ②建立邻接矩阵表示的无向带权图 void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）; ③输出邻接矩阵表示的无向带权图void PrintMatrix(adjmatrix G, int n) （即输出图的每条边）。把邻接矩阵的结构定义以及这些基本操作实现函数存放在头文件Graph1.h中。
2、 编写生成最小生成树的Prim算法函数 void Prim(adjmatrix G, edgset CT, int n) 以及输出边集数组的函数 void PrintEdge(edgeset CT, int n)。
3、 编写测试程序（即主函数），通过调用上述函数首先建立并输出无向带权图，然后生成最小生成树并输出（即输出边集）。
要求：把边集数组的结构定义、Prim算法函数、输出边集数组的函数PrintEdge以及主函数存放在文件Gragh1.cpp中。
测试数据如下：

0
1
2
3
5
4
5
8
12
3
10
7
6
2
9
6
15

实验8 查找与排序
实验目的
1． 熟悉并掌握各种查找算法
2． 掌握排序的基本概念。
3． 熟悉各种内部排序的方法。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容
编写程序，完成以下任务：
a) 通过键盘输入n个学生的考试成绩表(设计为一个线性表)，表中每个元素由姓名与分数组成；
b) 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；
c) 按名次打印出每个学生的姓名与分数。
要求：选用二种排序算法分别实现该程序中的排序要求，二种排序算法存放在头文件sort.h中。在主函数中首先输入数据，然后调用排序函数排序，并按分数高低次序打印名次与成绩表，主函数存放在文件sort.cpp中。