数据结构实验2.docx
- 文档编号:18204583
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:25
- 大小:20.97KB
数据结构实验2.docx
《数据结构实验2.docx》由会员分享,可在线阅读,更多相关《数据结构实验2.docx(25页珍藏版)》请在冰点文库上搜索。
数据结构实验2
数据结构实验指导书
重庆邮电大学软件工程学院
范时平
2014年10月
实验目得与要求
一、实验目得
数据结构就是软件工程学科中一门非常重要得专业基础课程。
当用计算机来解决实际问题时,就要涉及到数据得存储表示及数据得处理,而数据存储表示及数据处理正就是数据结构课程得主要研究对象,通过这两方面内容得学习,为后续课程,特别就是为软件方面得课程打下厚实得知识基础,同时也提供了必要得技能训练。
因此,数据结构在软件工程学科及相关学科专业得课程体系中具有极其重要得作用。
本课程得任务就是:
通过实践,学生对常用数据结构得基本概念及其不同得实现方法得理论得到进一步得掌握,并对在不同存储结构上实现不同得运算方式与技巧有所体会;能够快速确定数据得逻辑结构、并根据数据处理得类型与频度选择最佳得存储结构与算法组合。
二、实验要求
1.准备好上机所需要得C++程序,以提高上机效率。
对程序中自己有疑问得地方应作记号,以便在上机时给予注意或获取教师指导。
不得抄袭她人程序。
2.上机输入并调试/运行所编写程序。
3.上机结束后,提交实验报告,实验报告应包括但不限于以下内容:
(1)题目;
(2)实验目得;
(3)主要数据结构描述;
(4)算法得基本思想描述;
(5)算法时间复杂度分析;
(6)运行得结果截图;
(7)实验体会与收获;
(8)程序清单。
实验一顺序表得存储与操作
一、实验目得
1.理解线性表得逻辑结构;
2.理解顺序表得存储结构特点,掌握顺序表得存储分配要点;
3.掌握顺序表得基本操作及实现,并能正确分析其时间复杂度。
二、实验内容
1、定义顺序表得存储结构;
2、顺序表得基本操作
(1)初始化顺序表(无参与有参);
(2)求顺序表长度;
(3)按位置查找;
(4)按值查找;
(5)在位置i插入一个数据元素;
(6)删除位置i得数据元素;
(7)遍历顺序表;
(8)销毁顺序表。
三、算法思想与时间复杂度
当我们要在线性表得顺序存储结构上得第i个位置上插入一个元素时,必须先将线性表得第i个元素之后得所有元素依次后移一个位置,以便腾空一个位置,再把新元素插入到该位置。
若要删除第i个元素时,也必须把第i个元素之后得所有元素前移一个位置。
四、参考代码
1、顺序表得存储结构与操作接口
SeqList、h声明类SeqList,文件名为SeqList、h
#ifndefSeqList_H
#defineSeqList_H
constintMaxSize=100;//100只就是示例性得数据,可以根据实际问题具体定义
template
classSeqList
{
public:
SeqList();//无参构造函数
SeqList(Ta[],intn);//有参构造函数
~SeqList;//析构函数为空
intLength;//求线性表得长度
TGet(inti);//按位查找,取线性表得第i个元素
intLocate(Tx);//按值查找,求线性表中值为x得元素序号
voidInsert(inti,Tx);//在线性表中第i个位置插入值为x得元素
TDelete(inti);//删除线性表得第i个元素
voidPrintList;//遍历线性表,按序号依次输出各元素
private:
Tdata[MaxSize];//存放数据元素得数组
intlength;//线性表得长度
};
#endif
2.顺序表操作得实现
//SeqList、cpp
#include"SeqList、h"
/*
*前置条件:
顺序表不存在
*输入:
无
*功能:
构建一个顺序表
*输出:
无
*后置条件:
构建一个顺序表
*/
template
SeqList
:
SeqList()
{
length=0;
}
/*
*前置条件:
顺序表不存在
*输入:
顺序表信息得数组形式a[],顺序表长度n
*功能:
将数组a[]中元素建为长度为n得顺序表
*输出:
无
*后置条件:
构建一个顺序表
*/
template
SeqList
:
SeqList(Ta[],intn)
{
if(n>MaxSize)throw"参数非法";
for(inti=0;i data[i]=a[i]; length=n; } /* *前置条件: 无 *输入: 无 *功能: 无 *输出: 无 *后置条件: 无 */ template SeqList : ~SeqList() { } /* *前置条件: 顺序表存在 *输入: 插入元素x,插入位置i *功能: 将元素x插入到顺序表中位置i处 *输出: 无 *后置条件: 顺序表插入新元素 */ template voidSeqList : Insert(inti,Tx) { intj; if(length>=MaxSize)throw"上溢"; if(i<1||i>length+1)throw"位置"; for(j=length;j>=i;j) data[j]=data[j1];//注意第j个元素存在数组下标为j1处 data[i1]=x; length++; } /* *前置条件: 顺序表存在 *输入: 要删除元素位置i *功能: 删除顺序表中位置为i得元素 *输出: 无 *后置条件: 顺序表删除元素 */ template TSeqList : Delete(inti) { intx,j; if(length==0)throw"下溢"; if(i<1||i>length)throw"位置"; x=data[i1]; for(j=i;j data[j1]=data[j];//注意此处j已经就是元素所在得数组下标 length; returnx; } /* *前置条件: 顺序表存在 *输入: 无 *功能: 输出顺序表长度 *输出: 顺序表长度 *后置条件: 顺序表不变 */ template intSeqList : Length { returnlength; } /* *前置条件: 顺序表存在 *输入: 查询元素位置i *功能: 查找位置为i得元素并输出值 *输出: 查询元素得值 *后置条件: 顺序表不变 */ template TSeqList : Get(inti) { if(i<1&&i>length)throw"查找位置非法"; elsereturndata[i1]; } /* *前置条件: 顺序表存在 *输入: 查询元素值x *功能: 按值查找值得元素并输出位置 *输出: 查询元素得位置 *后置条件: 顺序表不变 */ template intSeqList : Locate(Tx) { for(inti=0;i if(data[i]==x) returni+1;//下标为i得元素等于x,返回其序号i+1 return0;//退出循环,说明查找失败 } /* *前置条件: 顺序表存在 *输入: 无 *功能: 顺序表遍历 *输出: 输出所有元素 *后置条件: 顺序表不变 */ template voidSeqList : PrintList { for(inti=0;i cout< } 3.顺序表得调试运行 //SeQListMain、cpp #include #include"SeqList、cpp"//引用顺序表类SeqList voidmain() { SeqList cout<<"执行插入操作: "< try { a、Insert(1,1); a、Insert(2,3); a、Insert(3,4); } catch(char*wrong) { cout< } cout<<"已经插入“1,3,4”"< cout< cout<<"顺序表a得长度为: "; cout< cout< cout<<"按位查询第二个元素: "< cout<<"第二个元素为: "; cout< (2)< cout< cout<<"按值查询3: "< cout<<"值为3得元素位置为: "; cout< cout< try { if(a、Length){ cout<<"执行删除第一个元素操作: "< cout< a、Delete (1);//删除元素1 cout<<"已删除成功,顺序表a得长度为: "; cout< } else{ cout<<"顺序表a长度为0"< } } catch(char*wrong) { cout< } cout< cout<<"顺序表a中得元素有: "< a、PrintList;//输出所有元素 intr[]={1,2,3,4,5}; SeqList cout<<"执行插入操作前顺序表b为: "< b、PrintList;//输出顺序表所有元素 cout<<"插入前顺序表b得长度为: "; cout< try { b、Insert(3,8); } catch(char*wrong) { cout< } cout<<"执行插入操作后顺序表b为: "< b、PrintList;//输出顺序表b所有元素 cout<<"插入后顺序表b得长度为: "; cout< cout< try { if(a、Length){ cout<<"执行删除第一个元素操作: "< cout< b、Delete (1);//删除b中第一个元素 cout<<"已删除成功,顺序表b得长度为: "; cout< } else{ cout<<"顺序表b长度为0"< } } catch(char*wrong) { cout< } cout<<"执行插入操作后顺序表b为: "< b、PrintList;//输出顺序表所有元素 } 实验二单链表得存储与操作 一、实验目得 1.理解线性表得逻辑结构; 2.理解单链表得存储结构特点,掌握单链表得存储分配要点; 3.掌握单链表得基本操作及实现,并能正确分析其时间复杂度。 二、实验内容 1、定义单链表得存储结构; 2、单链表得基本操作 (1)初始化单链表(无参与有参); (2)求单链表长度; (3)按位置查找; (4)按值查找; (5)在位置i插入一个数据元素; (6)删除位置i得数据元素; (7)遍历单链表; (8)销毁单链表。 三、算法思想与时间复杂度 1、按位置/值查找: 顺序查找,平均时间复杂度为O(n); 2、在位置i插入一个数据元素: 在序号为i1得结点后插入结点,平均时间复杂度为O(n); 3、删除位置i得数据元素: 删除序号为i1结点得后继结点,平均时间复杂度为O(n); 4、初始化单链表(有参): 有前插法与尾插法(注意单链表得逻辑关系应与参数数组保持一致),时间复杂度为O(n); 5、遍历单链表、求单链表长度、销毁单链表: 顺序处理,时间复杂度为O(n)。 四、参考代码 1、单链表得存储结构与操作接口 //LinkList、h声明类LinkList #ifndefLinkList_H #defineLinkList_H template structNode { Tdata; Node }; template classLinkList { public: LinkList();//建立只有头结点得空链表 LinkList(Ta[],intn);//建立有n个元素得单链表 ~LinkList;//析构函数 intLength;//求单链表得长度 TGet(inti);//取单链表中第i个结点得元素值 intLocate(Tx);//求单链表中值为x得元素序号 voidInsert(inti,Tx);//在单链表中第i个位置插入元素值为x得结点 TDelete(inti);//在单链表中删除第i个结点 voidPrintList();//遍历单链表,按序号依次输出各元素 private: Node }; #endif 2、单链表操作得实现 //LinkList、cpp #include"LinkList、h" /* *前置条件: 单链表不存在 *输入: 无 *功能: 构建一个单链表 *输出: 无 *后置条件: 构建一个单链表 */ template LinkList : LinkList() { first=newNode } /* *前置条件: 单链表不存在 *输入: 顺序表信息得数组形式a[],单链表长度n *功能: 将数组a[]中元素建为长度为n得单链表 *输出: 无 *后置条件: 构建一个单链表 */ template LinkList : LinkList(Ta[],intn) { first=newNode Node r=first;//尾指针初始化 for(inti=0;i { s=newNode r>next=s;r=s;//插入到终端结点之后 } r>next=NULL;//单链表建立完毕,将终端结点得指针域置空 } /* *前置条件: 无 *输入: 无 *功能: 无 *输出: 无 *后置条件: 无 */ template LinkList : ~LinkList { } /* *前置条件: 单链表存在 *输入: 查询元素位置i *功能: 按位查找位置为i得元素并输出值 *输出: 查询元素得值 *后置条件: 单链表不变 */ template TLinkList : Get(inti) { Node p=first>next;j=1;//或p=first;j=0; while(p&&j { p=p>next;//工作指针p后移 j++; } if(! p)throw"位置"; elsereturnp>data; } /* *前置条件: 单链表存在 *输入: 查询元素值x *功能: 按值查找值得元素并输出位置 *输出: 查询元素得位置 *后置条件: 单链表不变 */ template intLinkList : Locate(Tx) { Node p=first>next;j=1; if(p&&p>next){ while(p>data! =x) { p=p>next; j++; } returnj; } elsethrow"位置"; } /* *前置条件: 单链表存在 *输入: 插入元素x,插入位置i *功能: 将元素x插入到单链表中位置i处 *输出: 无 *后置条件: 单链表插入新元素 */ template voidLinkList : Insert(inti,Tx) { Node p=first;j=0;//工作指针p初始化 while(p&&j { p=p>next;//工作指针p后移 j++; } if(! p)throw"位置"; else{ Node s=newNode s>data=x;//向内存申请一个结点s,其数据域为x s>next=p>next;//将结点s插入到结点p之后 p>next=s; } } /* *前置条件: 单链表存在 *输入: 无 *功能: 输出单链表长度 *输出: 单链表长度 *后置条件: 单链表不变 */ template intLinkList : Length() { Node inti=0; while(p) { p=p>next; i++; } returni; } /* *前置条件: 单链表存在 *输入: 要删除元素位置i *功能: 删除单链表中位置为i得元素 *输出: 无 *后置条件: 单链表删除元素 */ template TLinkList : Delete(inti) { Node p=first;j=0;//工作指针p初始化 while(p&&j { p=p>next; j++; } if(! p||! p>next)throw"位置";//结点p不存在或结点p得后继结点不存在 else{ Node q=p>next;x=q>data;//暂存被删结点 p>next=q>next;//摘链 deleteq; returnx; } } /* *前置条件: 单链表存在 *输入: 无 *功能: 单链表遍历 *输出: 输出所有元素 *后置条件: 单链表不变 */ template voidLinkList : PrintList() { Node p=first>next; while(p) { cout< data< p=p>next; } } 3、调试运行 //LinkListMain、cpp #include #include"LinkList、cpp"//引用单链表得类 voidmain() { LinkList cout<<"执行插入操作: "< try { a、Insert(1,4); a、Insert(2,5); a、Insert(3,6); } catch(char*wrong) { cout< } cout<<"已经插入“4,5,6”"< cout<<"单链表a得长度为: "< cout< cout< cout<<"单链表a得元素为: "< a、PrintList;//显示链表中所有元素 cout< cout<<"按位查找第二个元素: "< cout<<"第二个元素为: "; cout< (2)< cout< cout<<"按值查找5"< cout<<"值为5得元素位置为: "; cout< cout< cout<<"执行删除4得操作"< a、Delete (1);//删除元素4 cout<<"已删除成功,单链表a得长度为";
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验