实验任务书(2015) (1)

目 录

0 实验要求 .......................................... 2 实验1

实验2

实验3

实验4

实验5

实验6

实验7

实验8

线性表的顺序存储结构 ......................... 3 链表的应用 ................................... 6 栈的应用 ..................................... 9 队列的应用 .................................. 10 树的应用 .................................... 11 图的应用 .................................... 12 图的应用 .................................... 13 查找与排序 .................................. 14

0 实验要求

一、实验步骤

⒈ 问题分析

充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和

约束以及基本数据特性，数据元素之间的关系等。

⒉ 数据结构设计

针对要求解决的问题，考虑各种可能的数据结构，并且力求从中找出最佳方案(必须连

同算法一起考虑)，确定主要的数据结构及全局变量。对引入的每种数据结构和全局变量要

详细说明其功能、初值和操作特点。

⒊ 算法设计

算法设计分概要设计和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑

如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相

互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输

入、处理和输出，采用类C语言描述。

⒋ 测试用例设计

准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试

和模块集成测试。

⒌ 上机调试

对程序进行编译，纠正程序中可能出现的语法错误。测试前，先运行一遍程序看看究竟

将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。

二、实验报告

每次实验结束后，均应撰写实验报告。实验报告应包括如下内容：

1、问题描述：简述题目要解决的问题是什么。

2、设计：概要设计采用抽象数据类型描述，详细设计包括存储结构的定义、主要操作

算法设计等。用类C语言或用框图描述。

3、调试报告：调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。

4、运行结果。可以贴相应的运行结果截图。

5、算法分析与改进：算法的时间复杂度和空间复杂度分析；算法改进的设想。

6、经验和体会

所有实验做完后，上交上机实验源程序和相应的运行结果截图。源程序要加注释。如

果题目规定了测试数据，则截图结果要包含这些测试数据和运行输出，当然还可以含有其它

测试数据和运行输出（有时需要多组数据）。

三、实验学时

16学时

实验1 线性表的顺序存储结构

实验目的

1． 熟悉C语言的上机环境，掌握使用VC环境上机调试线性表的基本方法；

2． 掌握线性表的顺序存储结构及其线性表的基本操作：插入、删除、查找等。

3． 掌握线性表合并等运算在顺序存储结构上的实现。

实验要求

1． 认真阅读和掌握本实验的程序。

2． 上机运行程序，观察程序的运行结果。

3． 按照你对线性表的操作需要，重新改写主程序并运行。

实验内容（基础题必做，应用题、提高题可选）

1. 基础题：线性表基本操作的实现

这个程序中演示了顺序表的创建、插入、删除和查找，（1）请修改并记录运行结果；（2）

按照你自己对线性表测试的需要，增加新的操作，重新改写主程序并记录运行结果。

#include <stdio.h>

#include <stdlib.h>

//顺序表的定义

#define ListSize 100

typedef int ElemType;

typedef struct

{ ElemType *elem; /*存放表元素的空间基地址*/

int length; /*当前的表长度*/

int listsize; /*能容纳的最大元素个数*/

}SeqList;

void CreateList(SeqList &L,int n);

void PrintList(SeqList L,int n);

int LocateList(SeqList L,int x);

void InsertList(SeqList &L,int x,int i);

void DeleteList(SeqList &L,int i);

void main()

{

SeqList L;

int i,x;

int n=10; /*THE LENGTH OF LIST*/

L.length=0;

clrscr();

CreateList(L,n); /*CREATE THE LIST*/

PrintList(L,n); /*PRINT THE LIST*/

printf("INPUT THE SEARCH ELEMENT");

scanf("%d",&x);

i=LocateList(L,x);

printf("the search position is %d\n",i); /*顺序表查找*/

printf("input the position of insert:\n");

scanf("%d",&i);

printf("input the value of insert\n");

scanf("%d",&x);

InsertList(L,x,i); /*顺序表插入*/

PrintList(L,n); /*打印顺序表*/

printf("input the position of delete\n");

scanf("%d",&i);

DeleteList(L,i); /*顺序表删除*/

PrintList(L,n);

getch();/*打印顺序表*/

}

/*顺序表的建立：*/

void CreateList(SeqList &L,int n)

{

L. elem =(ElemType *)malloc(ListSize *sizeof(ElemType));

if(!L.elem) exit(0);

L.listsize= ListSize;

int i;

printf("please input n numbers\n");

for(i=1;i<=n;i++)

{

scanf("%d",&L. elem [i]);

}

L.length=n;

}

/*顺序表的打印：*/

void PrintList(SeqList L,int n)

{int i;

printf("the sqlist is\n");

for(i=1;i<=n;i++)

printf("%d ",L.elem [i]);

}

/*顺序表的查找：*/

int LocateList(SeqList L,int x)

{int i;

for(i=1;i<=10;i++)

if((L. elem [i])==x) return(i);

else return(0);

}

/*顺序表的插入：*/

void InsertList(SeqList &L, int x, int i)

{int j;

for(j=L->length;j>=i;j--)

L-> elem [j+1]=L-> elem [j];

L-> elem [i]=x;

L.length++;

}

/*顺序表的删除：*/

void DeleteList(SeqList &L,int i)

{ int j;

for(j=i;j<=(L.length)-1;j++)

L. elem [j]=L. elem [j+1];

}

2.应用题

（1）求集合A、B的并集C。

（2）归并两个有序表La和Lb成一个新的有序表Lc。有序指值非递减。

3.提高题

（1）学生成绩管理

本题目是对学生成绩管理的简单模拟，用菜单选择方式完成下列功能：输入学生

数据；输出学生数据；学生数据查询；添加学生数据；修改学生数据；删除学生

数据。本题目的数据是一组学生的成绩信息，每条学生的成绩信息由学号、姓名

和成绩组成。

（2）考试报名管理

本项目是对考试报名管理的简单模拟，用菜单选择方式完成下列功能：输入考生

信息；输出考生信息；查询考生信息；添加考生信息；修改考生信息；删除考生

信息。本题目的数据是一组考生信息，每条考生信息由准考证号、姓名、性别、

年龄、报考类别等信息组成。

实验2 链表的应用

实验目的

1． 定义单链表的结点类型。

2． 熟悉对单链表的一些基本操作和具体的函数定义。

3． 通过单链表的定义掌握线性表的链式存储结构的特点。

4． 熟悉单链表的应用场合。

实验要求

1． 独立完成；

2． 准备好测试数据，程序调试正确，有执行结果。

实验内容（基础题必做，应用题、提高题任选）

1．基础题：

按照教材中抽象数据类型线性表的定义，演示单链表的基本操作，按照自己

的意图编写基本操作函数和主函数进行测试。

示例：这个程序演示了单链表的创建和插入操作。

程序如下：

#include <stdio.h>

#include<stdlib.h>

typedef int ElemType;

typedef struct node{

ElemType data;

struct node *next;

} NODE;

typedef NODE *LinkList;

/******************************************/

LinkList Create(){

NODE *p,*head;

int x;

head=(NODE *)malloc(sizeof(NODE));

head->next=NULL;

printf("Input data,-1 to End!\n");

scanf("%d",&x);

while(x!=-1){

p=(NODE *)malloc(sizeof(NODE));

p->data=x;

p->next=head->next;

head->next=p;

scanf("%d",&x);

}

return(head);

}

/******************************************/

void Output(LinkList head){

NODE *p;

p=head;

printf("Begin to dump the LinkList...\n");

while(p->next!=NULL){

printf("->%d",p->next->data);

p=p->next;

}

printf("\nThe LinkList ended!\n");

}

/******************************************/

int Listlen(LinkList head){

int i=0;

NODE *p=head;

while(p->next!=NULL){

i++;

p=p->next;

}

return(i);

}

/******************************************/

void Ins(LinkList head,int i,int e){

NODE *p=head,*q;

int j=0;

while(p->next&&j<i-1){

j++;

p=p->next;

}

if(!p->next&&j>i-1) printf("Wrong position\n" );

else{

q=(NODE *)malloc(sizeof(NODE));

q->data=e;

q->next=p->next;

p->next=q;

}

}

/******************************************/

main(){

LinkList head;

int length;

int i,element;

clrscr();

head=Create();

Output(head);

length=Listlen(head);

printf("the length of the link is %d\n",length);

printf("Input the insert position and element:\n");

scanf("%d%d",&i,&element);

Ins(head,i,element);

Output(head);

getch();

}

}

2.应用题

（1）求集合A、B的并集C。

（2）归并两个有序表La和Lb成一个新的有序表Lc。有序指值非递减。

3.提高题

（1）约瑟夫生者死者游戏： 30个旅客同乘一条船，因为严重超载，加上风高

浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人

才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第

一个人开始，依次报数，数到第9人，便把他投入大海中，然后从他的下一个人

数起，数到第9人，再将他投入大海，如此循环，直到剩下15个乘客为止。问

哪些位置是将被扔下大海的位置。

本游戏的数学建模如下：假设n个旅客排成一个环形，依次顺序编号1，2，…，

n。从某个指定的第1号开始，沿环计数，每数到第m个人就让其出列，且从下

一个人开始重新计数，继续进行下去。这个过程一直进行到剩下k个旅客为止。

本游戏要求用户输入的内容包括：

1） 旅客的个数，也就是n的值；

2） 离开旅客的间隔数，也就是m的值；

3） 所有旅客的序号作为一组数据要求存放在某种数据结构中。

本游戏要求输出的内容包括

1） 离开旅客的序号；

2） 剩余旅客的序号。

（2）一元多项式求和

有两个指数递减的一元多项式，写一程序求这两个多项式的和。

提示：用带表头结点的单链表作为多项式的存储表示；要建立两个单链表；

多项式相加就是要把一个单链表中的结点插入到另一个单链表中去，要注意插

入、删除操作中指针的正确修改。

实验3 栈的应用

实验目的

1． 会定义顺序栈和链栈的类型。

2． 掌握栈的插入和删除在操作上的特点。

3． 熟悉对栈的一些基本操作和具体的函数定义。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容（基础题必做，应用题、提高题任选）

1. 基础题：

按照教材中抽象数据类型栈的定义，采用顺序存储结构（用动态数组）或链

式存储结构，编写主函数演示顺序栈/链栈的基本操作。

2. 应用题：

（1）判断给定的字符串是否中心对称。

（2）数制转换

（3）表达式括号匹配问题

3. 提高题

（1）算符优先算法为表达式求值

（2）迷宫求解

实验4 队列的应用

实验目的

1． 掌握队列的存储结构及基本操作。

2． 掌握循环队列的设置及循环队列的各种基本操作的实现。

3． 通过具体的应用实例，进一步熟悉和掌握队列的实际应用。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容（基础题必做，应用题任选）

1、基础题：

按照教材中抽象数据类型队列的定义，采用顺序存储结构（循环队列）或链

式存储结构，编写主函数演示循环队列/链队列的基本操作。

2、应用题：

舞伴问题：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队，跳

舞开始时，依次从男队和女队的队头上各出一人配成舞伴，若两队初始人数不相

同，则较长的那一队中未配对者等待下一轮舞曲。设计一个函数partner()，模拟

上述舞伴配对问题。

基本要求：

1) 由键盘输入数据，每对数据包括姓名和性别；

2) 输出结果包括配成舞伴的女士和男士的姓名，以及未配对者的队伍名称

和队头者的姓名；

实验5 树的应用

实验目的

1． 熟悉二叉树结点的结构和对二叉树的基本操作。

2． 掌握对二叉树每一种操作的具体实现。

3． 学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

4． 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。

5． 掌握构造哈夫曼树以及哈夫曼编码的方法。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容（基础题必做，应用题任选）

1. 基础题：

按照教材中抽象数据类型二叉树的定义，采用二叉链表存储结构，编写主函

数演示二叉树的基本操作（不少于5个），如：

(1) Status InitBTree( BiTree &BT ) //初始化二叉树BT

(2) Status CreateBTree(BiTree &BT, char *a )

//根据先序序列a建立二叉链表存储结构

(3)Status EmptyBTree(BiTree BT)

//检查二叉树BT是否为空，空返回Yes，否则返回No

(4) int DepthBTree(BiTree BT) //求二叉树BT的深度并返回该值

(5) Status FindBTree(BiTree BT, TElemType x)

//查找二叉树BT中值为x的结点，若查找成功返回该结点地址，否则返回

Error

(6) void PreOrder(BiTree BT) //先序遍历二叉树BT

(7) void InOrder(BiTree BT) //中序遍历二叉树BT

(8) void PostOrder(BiTree BT) //后序遍历二叉树BT

(9) void LevelOrder(BiTree BT ) //按层次遍历二叉树BT

(10) void PrintBTree(BiTree BT ) //输出二叉树BT

2．应用题

家谱管理：本题目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。

实验6 图的应用

实验目的

1． 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。 2． 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容

1、基础题（至少做一个）

（1）图的邻接矩阵定义及实现：

定义图的邻接矩阵存储结构，并编写图的初始化、建立图、深度优先/广度优先输出图、输出图的每个顶点的度等基本操作实现函数。以下图为例，建立一个验证操作实现的主函数进行测试。

（2）图的邻接表的定义及实现：

定义图的邻接表存储结构，并编写图的初始化、建立图、深度优先/广度优先输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数中调用这些函数进行验证（以下图为例）。

实验7 图的应用

实验目的

1. 掌握图的最短路径概念。

2. 掌握生成最小生成树的Prim算法（用邻接矩阵表示图）/克鲁斯卡尔算法。

3. 理解求最短路径的DijKstra算法（用邻接矩阵表示图）。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容（基础题必做，应用题任选）

1、基础题

编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，主要包括： ① 初始化邻接矩阵表示的有向带权图

② 建立邻接矩阵表示的有向带权图 （即通过输入图的每条边建立图的邻接矩阵）

③ 出邻接矩阵表示的有向带权图（即输出图的每条边）。

④ 编写求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组 path 和 dist 中。（可选）

⑤ 编写打印输出从源点到每个顶点的最短路径及长度的函数 void PrintPath(int dist[], edgenode *path[], int n)。（可选） 同时建立一个验证操作实现的主函数进行测试。

2、应用题

编写Prim算法函数 void Prim(adjmatrix G, edgset CT, int n)或者克鲁斯卡尔算法函数以及输出边集数组的函数 void PrintEdge(edgeset CT, int n)。

。

实验8 查找与排序

实验目的

1． 熟悉并掌握各种查找算法

2． 掌握排序的基本概念。

3． 熟悉各种内部排序的方法。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

实验内容（基础题必做，应用题任选）

1.基础题

实现教材中的查找和排序算法（各不少于2种）。编写主函数以菜单形式测试各个查找和排序算法。

2.应用题

编写程序，完成以下任务：

a) 通过键盘输入n个学生的考试成绩表(设计为一个线性表)，表中每个元素由学号、姓名与分数组成；

b) 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次； c) 按学号查找某个学生成绩信息；

d) 按名次打印出每个学生的姓名与分数。

要求：利用基础题中实现的排序和查找算法，在主函数中首先输入数据，然后调用查找函数查找某个给定的学号的学生成绩，然后调用排序函数排序，并按分数高低次序打印名次与成绩表。

本文来源：https://www.bwwdw.com/article/faw4.html