文档介绍：数据结构实验
第一节概述
一、实验目的
实验是对学生的一种全面综合训练,是与课堂听讲、自学和练****相辅相成的必不可少的一个教学环节。通常,实验题中的问题比平时的练****题要复杂,也更接近实际。
实验的目的是旨在使学生进一步巩固课堂上所学的理论知识;深化理解和灵活掌握教学内容;培养学生算法设计的能力和解决实际问题的程序设计的能力。
本实验指导书仅列出一个实验项目下一个实验题存储结构、算法;供其他实验题作为参考。
二、实验名称与学时分配
序号
实训名称
学时数
1
线性表的算法设计及应用
4
2
栈的算法设计与应用
4
3
基于队列的基数排序算法设计与应用
4
4
串的算法设计与应用
5
二叉树的算法设计及应用
4
6
图的算法设计与应用
4
5
查找算法设计
6
排序算法设计
三、实验考核
每次实验结束后,均应上交实验报告。实验成绩占数据结构课程结业成绩的20%。
实验报告应包括如下内容:
1、问题描述:简述题目要解决的问题是什么。
2、设计:包括存储结构设计、主要算法设计等。用类C语言或用框图描述。
3、调试报告:调试过程中遇到的问题是如何解决的;对设计和编码的讨论和分析。
4、算法分析与改进:算法的时间复杂度和空间复杂度分析;算法改进的设想。
5、经验和体会
附源程序清单和运行结果。
源程序要加注释。如果题目规定了测试数据,则结果要包含这些测试数据和运行输出,当然还可以含有其它测试数据和运行输出(有时需要多组数据)。
四、实验时间安排
16学时。
五、选题安排
实验1,5,6必做,实验2和实验3两题选作1题,实验报告上交4个实验。
其余题选作。
第二节线性表算法设计及应用
一、目的与要求
(一)目的
了解线性表及在计算机中的两类不同的存储结构;熟练掌握线性表的查找、插入和删除等算法并灵活运用这些算法。
(二)要求
用C语言编写程序,实现多项式求值或求解约瑟夫问题。
二、示例
1、题目报数问题
编号为1,2,···,n的n个人围坐在一圆桌旁,从第s个人开始报数,报到第m的人退席,下一个人又重新从1开始报数,依此重复,直至所有的人都退席。
例如,设s=1,m=4,n=8,则退席的人的编号依次为4,8,5,2,1,3,7,6。
2、存储结构
(1)以顺序表为存储结构
int p[n]; // n—常量
(2)以循环链表为存储结构
typedef struct lnode{
int data;
struct lnode *next;
} lnode;
3、算法设计
(1)void josephus_1(int p[], int m, int n) {
int i,j,t;
for(i=0;i<=n-1;i++) p[i]=i+1; //p[0]..p[n-1]:n个人
t=0; //第一次报数的位置(第一人的位置)
for(i=n;i>=1;i--) {
t=(t+m-1)%i ; // t:定位于第m人,i:当前圆桌上的人数,%:实现环(圆桌)的处理
cout<<p[t]<<" "; // 输出第m人信息(第m人报数)
for (j=t+1;j<=i-1;j++)
p[j-1]=p[