没有合适的资源?快使用搜索试试~ 我知道了~
数据结构(c++版)实验书
3星 · 超过75%的资源 需积分: 10 7 下载量 186 浏览量
2009-11-07
12:01:58
上传
评论
收藏 346KB DOC 举报
温馨提示
试读
51页
适用于数据结构c++版 , 清华大学出版的 ,王红梅, 胡明 ,王涛, 主编 , 用于书上的实验指导。
资源推荐
资源详情
资源评论
前 言
《数据结构》是计算机及相关专业的一门核心基础课程,也是很多高校考研专业课之
一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现,在此基础上介
绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良
好的程序设计习惯。通过学习,要求学生能够掌握典型算法的设计思想及程序实现,能够
根据实际问题选取合适的存储方案,设计出简洁、高效、实用的算法,为后续课程的学习
及软件开发打下良好的基础。学习这门课程,习题和实验是两个关键环节。学生理解算法 ,
上机实验是最佳的途径之一。因此,实验环节的好坏是学生能否学好《数据结构》的关键 。
为了更好地配合学生实验,特编写实验指导书。
一、实验目的
更好的理解算法的思想、培养编程能力。
二、实验要求
1、 每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数
据。
2、在指导教师的帮助下能够完成实验内容,得出正确的实验结果。
3、实验结束后总结实验内容、书写实验报告。
4、遵守实验室规章制度、不缺席、按时上、下机。
5、实验学时内必须做数据结构的有关内容,不允许上网聊天或玩游戏,如发现上述现
象,取消本次上机资格,平时成绩扣 10 分。
6、实验报告有一次不合格,扣 5 分,两次以上不合格者,平时成绩以零分记。
三、实验环境 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 <class T> //定义模板类 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 <class T>
SeqList:: SeqList(T a[ ], int n)
{
if (n>MaxSize) throw "参数非法";
for (i=0; i<n; i++)
data[i]=a[i];
length=n;
}
template <class T>
T SeqList::Get(int i)
{
if (i<1 && i>length) throw "查找位置非法";
else return data[i-1];
}
template <class T>
int SeqList::Locate(T x)
{
for (i=0; i<length; i++)
if (data[i]==x) return i+1; //下标为 i 的元素等于 x,返回其序号 i+1
return 0; //退出循环,说明查找失败
}
template <class T>
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 <class T>
T SeqList::Delete(int i)
{
if (length==0) throw "下溢";
if (i<1 | | i>length) throw "位置";
x=data[i-1];
for (j=i; j<length; j++)
data[j-1]=data[j]; //注意此处 j 已经是元素所在的数组下标
length--;
return x;
}
链表类定义:将该类保存在文件 LinkList.h 中。
template <class T>
struct Node
{
T data;
Node<T> *next; //此处<T>也可以省略
}
template <class T>
class LinkList
{
public:
LinkList( ){first=new Node<T>; 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<T> *first; //单链表的头指针
};
template <class T>
LinkList:: ~LinkList( )
{
p=first; //工作指针 p 初始化
while (p) //释放单链表的每一个结点的存储空间
{
q=p; //暂存被释放结点
p=p->next; //工作指针 p 指向被释放结点的下一个结点,使单链表不断开
delete q;
}
}
template <class T>
T LinkList::Get(int i)
{
p=first->next; j=1; //或 p=first; j=0;
while (p && j<i)
{
p=p->next; //工作指针 p 后移
j++;
}
if (!p) throw "位置";
else return p->data;
}
template <class T>
void LinkList::Insert(int i, T x)
{
p=first ; j=0; //工作指针 p 初始化
while (p && j<i-1)
{
p=p->next; //工作指针 p 后移
j++;
}
if (!p) throw "位置";
else {
s=new Node<T>; s->data=x; //向内存申请一个结点 s,其数据域为 x
剩余50页未读,继续阅读
资源评论
- odin19942013-04-29下载注意,是实验报告,不是课后题答案
bosslichuan
- 粉丝: 2
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Flume进阶-自定义拦截器jar包
- Dubins曲线算法讲解和在运动规划中的使用.pdf
- 上市公司-股票性质数据-工具变量(民企、国企、央企)2003-2022年.dta
- 上市公司-股票性质数据-工具变量(民企、国企、央企)2003-2022年.xlsx
- Reeds+Shepp曲线算法讲解和实现.pdf
- 毕业设计基于SpringBoot+MyBatisPlus+MySQL+Vue的外卖配送信息系统源代码+数据库
- 词向量(Word Embeddings)是自然语言处理(NLP)领域的一种重要技术.txt
- Surfer,线性函数
- MyBatis 的动态 SQL 是其核心特性之一.txt
- 时代的sdddsddsddsd
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功