实验报告二线性表的顺序存储班级: 2010XXX 姓名: HoogLe 学号: 2010XXXX 专业: XXXX
2858505197@https://www.doczj.com/doc/863867269.html,
一、实验目的:
(1)掌握顺序表的基本操作的实现方法。
(2)应用顺序表的基本算法实现集合A=AUB算法。
(3)应用顺序表的基本算法实现两有序顺序表的归并算法。
二、实验内容:
1、线性表顺序存储结构的基本操作算法实现(要求采用类模板实现)
[实现提示] (同时可参见教材p5822-p60页算法、ppt)函数、类名称等可自定义,部分变量请加上学号后3位。
库函数载和常量定义:(代码)
#include
using namespace std;
const int MaxSize=100;
(1)顺序表存储结构的定义(类的声明):(代码)
template
class SeqList
{
public:
SeqList( ); //无参构造函数
SeqList(datatype a[ ], int n); //有参构造函数
~SeqList(){}; //析构函数为空
int Length(); //求线性表的长度
datatype Get(int i); //按位查找,取线性表的第i个元素
int Locate(datatype item); //查找元素item
void Insert(int i, datatype item); //在第i个位置插入元素item
datatype Delete(int i); //删除线性表的第i个元素
void display(); //遍历线性表,按序号依次输出各元素
private:
datatype data[MaxSize]; //存放数据元素的数组
int length; //线性表的长度
};
(2)初始化顺序表算法实现(不带参数的构造函数)
/*
*输入:无
*前置条件:顺序表不存在
*功能:构建一个顺序表
*输出:无
*后置条件:表长为0
*/
实现代码:
template
SeqList
{
length=0;
}
(3)顺序表的建立算法(带参数的构造函数)
/*
*输入:顺序表信息的数组形式a[],顺序表长度n
*前置条件:顺序表不存在
*功能:将数组a[]中元素建为长度为n的顺序表
*输出:无
*后置条件:构建一个顺序表
*/
实现代码:
template
SeqList
if (n>MaxSize)
{
cout<<"数组元素个数不合法"< } for (int i=0; i data[i]=a[i]; length=n; }(4)在顺序表的第i个位置前插入元素e算法 /* *输入:插入元素e,插入位置i *前置条件:顺序表存在,i要合法 *功能:将元素e插入到顺序表中位置i处 *输出:无 *后置条件:顺序表插入新元素,表长加1 */ 实现代码: template void SeqList int j; if (length>=MaxSize) { cout<<"溢出"< } if (i<1 || i>length+1) { cout<<"i不合法!"< } for (j=length; j>=i; j--) data[j]=data[j-1]; data[i-1]=item; length++; }(5)删除线性表中第i个元素算法 /* *输入:要删除元素位置i *前置条件:顺序表存在,i要合法 *功能:删除顺序表中位置为i的元素 *输出:无 *后置条件:顺序表册除了一个元素,表长减1 */ 实现代码: template datatype SeqList { int item,j; if (length==0) { cout<<"表为空,无法删除元素!"< } if (i<1 || i>length) { cout<<"i不合法!"< } item=data[i-1];//获得要删除的元素值 for (j=i; j data[j-1]=data[j]; //注意数组下标从0记length--; return item; }(6)遍历线性表元素算法 /* *输入:无 *前置条件:顺序表存在 *功能:顺序表遍历 *输出:输出所有元素 *后置条件:无 */ 实现代码: template void SeqList { if(length==0) { cout<<"表为空,无法输出!"< } for(int i=0;i { cout< } } (7)获得线性表长度算法 /* *输入:无 *前置条件:顺序表存在 *功能:输出顺序表长度 *输出:顺序表长度 *后置条件:无 */ 实现代码: template int SeqList { return Length; } (8)在顺序线性表中查找e值,返回该元素的位序算法/* *输入:查询元素值e *前置条件:顺序表存在 *功能:按值查找值的元素并输出位置 *输出:查询元素的位置 *后置条件:无 */ 实现代码: template int SeqList { for (int i=0; i if (data[i]==item) return i+1 ; //下标为i的元素等于item,返回其序号i+1 return 0; //查找失败 } (9)获得顺序线性表第i个元素的值 /* *输入:查询元素位置i *前置条件:顺序表存在,i要合法 *功能:按位查找位置为i的元素并输出值 *输出:查询元素的值 *后置条件:无 */ 实现代码: template datatype SeqList { if (i<0||i>length) { cout<<"i不合法!"< } else return data[i-1]; } (10)判表空算法 /* *输入:无 *前置条件:无 *功能:判表是否为空 *输出:为空返回1,不为空返回0 *后置条件:无 */ 实现代码: template bool SeqList { if (length==0) { return 1; } else { return 0; } } (11)求直接前驱结点算法 /* *输入:要查找的元素e,待存放前驱结点值e1 *前置条件:无 *功能:查找该元素的所在位置,获得其前驱所在位置。*输出:返回其前驱结点的位序。 *后置条件:e1值为前驱结点的值 */ 实现代码: template int SeqList { int k=Locate(item)-1; if (k>0) return k; else { cout<<"无前驱结点!"< return 0; } } (12)求直接后继结点算法 /* *输入:要查找的元素e,待存放后继结点值e1 *前置条件:无 *功能:查找该元素的所在位置,获得其后继所在位置。*输出:返回其后继结点的位序。 *后置条件:e1值为后继结点的值 */ 实现代码: template int SeqList { int k=Locate(item)+1; if (k>length) { cout<<"无后继结点!"< return 0; } else { return k; } } 上机实现以上基本操作,写出main()程序: void main() { SeqList if(Seq.Empty()) { cout<<"线性表为空!"< Seq.Insert(1,1); Seq.Insert(2,2); Seq.Insert(3,3); Seq.Insert(4,4); Seq.Insert(5,5); //插入元素操作 cout<<"输出插入的五个元素:"< Seq.display(); //按序号依次输出各元素 cout< cout<<"2是第"< cout<<"第五个元素是:"< cout<<"线性表的长度为:"< Seq.Delete(3); //删除元素 cout<<"删除第三个元素后的线性表为:"< Seq.display(); //输出删除元素后的线性表 cout< cout<<"元素2前驱结点的位置为:"< cout<<"元素2前驱结点的数值为:"< cout<<"元素4后继结点的位置为:"< cout<<"元素4后继结点的数值为:"< } 要求对每个算法都加以测试,判断是否正确;并测试不同类型数据的操作。 粘贴测试数据及运行结果: 2、用以上基本操作算法,实现A=AUB算法。(利用函数模板实现) /* *输入:集合A,集合B *前置条件:无 *功能:实现A=AUB *输出:无 *后置条件:A中添加了B中的元素。 */ 实现代码: template SeqList if (item.Empty()) return *this; else { int k=item.Length(); int num=this->Length(); for (int i=1;i<=k;i++) { for(int j=0;j if (data[j]==item.Get(i)) { break; } else if (num-1==j&&data[num-1]!=item.Get(i)) { this->Insert(++num,item.Get(i)); } } return *this; } } void main() { SeqList cout<<"A∪B的结果是:"< A.Insert(1,1); A.Insert(2,2); A.Insert(3,3); A.Insert(4,4); A.Insert(5,5); //插入集合A中元素 B.Insert(1,2); B.Insert(2,6); B.Insert(3,1); B.Insert(4,8); B.Insert(5,9); //插入集合B中元素 A.Add(B); A.display(); cout< } 粘贴测试数据及运行结果: 3、对以上顺序表类中的基本操作算法适当加以补充,实现向一个有序的(非递减)的顺序表中插入数据元素e算法。 /* *输入:插入元素e *前置条件:顺序表已有序 *功能:将元素e插入到顺序表中适当的位置,使顺序表依然有序 *输出:无 *后置条件:有序顺序表插入了新元素,且表长加1。 */ 实现代码: template void SeqList { int num=this->Length(); for (int i=0;i { if ((data[i] { for (int k=num;k>i;k--) data[k]=data[k-1]; data[i+1]=item; length++; break; } if (data[i]>item) { for(int k=num;k>i;k--) data[k]=data[k-1]; data[i]=item; length++; break; } } } void main() { SeqList A.Insert(1,3); A.Insert(2,5); A.Insert(3,6); A.Insert(4,8); A.Insert(5,10); //插入顺序表 cout<<"原顺序表为:"< A.display(); //输出顺序表 cout< A.orderInsert(2); A.orderInsert(4); //插入元素 cout<<"插入新元素后的顺序表为:"< A.display(); //输出重新排序后的顺序表 } 粘贴测试数据及运行结果: 4、算法实现:La,Lb为非递减的有序线性表,将其归并为Lc,该线性表仍有序(未考虑相同时删除一重复值)(利用函数类板实现) MergeList: /* *输入:有序线性表La,有序线性表Lb *前置条件:顺序表已有序 *功能:将两线性表归并,不去掉相同元素 *输出:返回一个新的有序线性表Lc *后置条件:无 */ 实现代码: template SeqList { int num=Seq2.Length(); for(int i=0;i<=num;i++){ Seq1.orderInsert(Seq2.Get(i)); } return Seq1; } void main() { SeqList La.Insert(1,2); La.Insert(2,4); La.Insert(3,6); La.Insert(4,8); //插入La cout<<"La中元素为:"< La.display(); //输出La cout< Lb.Insert(1,3); Lb.Insert(2,6); Lb.Insert(3,8); //插入Lb cout<<"Lb中元素为:"< Lb.display(); //输出Lb cout< Lc=Lc.ElseAdd(La,Lb); //合并两线性表 cout<<"合并后的Lc为:"< Lc.display(); //输出合并后的线性表 cout< } 粘贴测试数据及运行结果: 三、心得体会:(含上机中所遇问题的解决办法,所使用到的编程技巧、创新点及编程 的心得) 实验项目名称:线性表的顺序存储结构上的基本运算 (所属课程:数据结构--用C语言描述) 院系:计算机科学与信息工程学院专业班级:网络工程 姓名:000000 学号:0000000000 实验日期:2016.10.20 实验地点:A-06 406 合作者:指导教师:孙高飞 本实验项目成绩:教师签字:日期: (以下为实验报告正文) 一、实验目的 本次实验的目的掌握顺序表的存储结构形式及其描述和基本运算的实现;掌握动 态链表结构及相关算法设计 实验要求:输入和验证程序例题。正确调试程序,记录程序运行结果。完成实验报 告。 二、实验条件 Windows7系统的电脑,vc++6.0软件,书本《数据结构--用c语言描述》 三、实验内容 3.1 根据41页代码,用c语言定义线性表的顺序存储结构。 3.2 根据42页算法2.1实现顺序表的按内容查找。 3.3 根据43页算法2.2实现顺序表的插入运算。 3.4 根据45页算法2.3实现顺序表的删除运算。 四、实验步骤 3.2实验步骤 (1)编写头文件,创建ElemType。 (2)根据根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。 (3)根据42页算法2.1实现顺序表的按内容查找,创建Locate函数。 (4)创建main函数,输入SeqList L的数据元素。 (5)输入要查找的数据元素的值,调用Locate函数,输出结果。 3.3实验步骤 (1)编写头文件,创建ElemType。 (2)根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。 (3)根据43页算法2.2实现顺序表的插入运算,创建InsList函数。 (4)创建printList函数,逐项输出顺序表内的元素及顺序表元素的个数。 (5)创建main函数,输入插入的元素和其位置,调用printLinst函数输出顺序表,调用IntList函数,再次调用printLinst函数输出顺序表。 3.4实验步骤 (1)编写头文件,创建ElemType。 (2)根据根据41页代码,“用c语言定义线性表的顺序存储结构”定义顺序表。 (3)根据45页算法2.3实现顺序表的删除运算,创建DelList函数。 (4)创建printList函数,逐项输出顺序表内的元素及顺序表元素的个数。 (5)创建main函数,输入删除元素的位置,调用printLinst函数输出顺序表,调用DelList函数,再次调用printLinst函数输出顺序表。 五、实验结果 (1)实验3.2顺序表的按内容查找 # include 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时) 昆明理工大学信息工程与自动化学院学生实验报告 (201 —201 学年第一学期) 课程名称:数据结构开课实验室:年月日年级、专业、班学号姓名成绩 实验项目名称线性表链式存储运算的算法实现指导教师 教 师 评语教师签名: 年月日 一.实验内容: 线性表链式存储运算的算法实现,实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。 二.实验目的: 1.掌握线性表链式存储结构的C语言描述及运算算法的实现; 2.分析算法的空间复杂度和插入和删除的时间复杂度; 3.总结比较线性表顺序存储存储与链式存储的各自特点。 三.主要程序代码分析: LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束 pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点,退出 while(q->next!=p) //p为要删除的结点,q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果: 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 .实验目的 (1 )掌握使用Visual C++ 6.0 上机调试程序的基本方法; (2 )掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 .实验要求 (1 )认真阅读和掌握和本实验相关的教材内容。 (2 )认真阅读和掌握本章相关内容的程序。 (3 )上机运行程序。 (4 )保存和打印出程序的运行结果,并结合程序进行分析。 (5 )按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表,由用户输入各结点data 域之值, // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 1.3线性表及其顺序存储结构 1.线性表的基本概念 线性表是由n个数据元素组成的一个有限序列,表中的每一个数据元素,除了每一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。即线性表或是一个空表。 显然线性表是一种线性结构,数据元素在线性表中的位置只取决于它们自己的序号,即数据元素之间的相对位置是线性的。 非空线性表有如下一些结构特征: (1)有且只有一个根结点,它无前件; (2)有且只有一个根结点,它无后件; (3)除了根结点与终端结点外,其他所有结点有且只有一个前件,也只有且只有一个后件。 2.线性表的存储结构 线性表的顺序存储结构具有以下两个特征: (1)线性表中所有元素所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 由此可以看出,在线性表的顺序存储结构中,其前件和后件两个元素在存储空间中是紧邻的,且其前件元素一定存储在后件元素的前面。 在程序设计语言中,通常定义一个一维数组来表示线性表的顺序存储看见。因为程序设计语言中的一维数组与计算机中的实际的存储空间结构是类似的,这就便于用程序设计语言对线性表进行各种运算处理。 在线性表的顺序存储结构中,可以对线性表进行各种处理。主要的运算有如下几种: (1)在线性表的指定位置处加入一个新的元素; (2)在线性表中删除指定的元素; (3)在线性表中查找某个特定的元素; (4)对线性表中的元素进行整序; (5)按要求将一个线性表分解成多个线性表; (6)按要求将多个线性表合并成一个线性表; (7)复制一个线性表; (8)逆转一个线性表等。 3.顺序表的插入运算 设长度为n的线性表为 (a1,a2,a3,a4,…,ai, …,an) 现要在线性表的第i个元素ai之前插入一个新元素b,插入后得到长度为n+1的线性表为 (a1,a2,a3,a4,…,aj,aj+1, …,an,an+1) 则插入前后的两线性表中的元素满足如下关系: a j0 数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 实验报告 题目:完成线性表ADT的顺序存储和链式存储方式的实现 一、需求分析 1、本演示程序中,线性表的数据元素类型限定为整型 2、演示程序以用户和计算机的对话方式执行,即在计算机的终端上显示“提 示信息”之后由用户在键盘上键入演示程序规定的运算命令,相应的输出 结果显示在后面。 3、程序的执行命令包括: 创建、撤销、清空、插入、修改、删除、定位等线性表ADT各项基本操作二、概要设计 为实现上述功能,我们给出线性表的抽象数据类型定义,具体的有单向链,双向 链,顺序表等,同时对于上述功能的实现还采用有/无头结点两种方式来实现 1.线性表的抽象数据类型定义为 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,…,n,n≥0} 数据关系:R1={|ai-1,ai∈D,i=2,…,n} 基本操作: InitList(&L) 操作结果:构造一个空的线性表L DestroyList(&L) 初始条件:线性表L已存在。 操作结果:销毁线性表L。 ClearList(&L) 初始条件:线性表L已存在。 操作结果:将L重置为空表。 ListEmpty(L) 初始条件:线性表L已存在。 操作结果:若L为空表,则返回TRUE,否则返回FALSE。 ListLength(L) 初始条件:线性表L已存在。 操作结果:返回L中的i个数据元素的值。 GetElem(L,i,&e) 初始条件:线性表L已存在,1≤i≤ListLength(L)。 操作结果:用e返回L中第i个数据元素的值。 LocateElem(L,e,compare()) 初始条件:线性表L已存在,compare()是数据元素判定函数 操作结果:返回L中第一个与e满足compare()的数据元素的位序。 若这样的数据元素不存在,则返回值为0. PriorElem(L,cur_e,&pre_e) 初始条件:线性表已存在 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e 返回它的前驱,否则操作失败,pre_e无定义。 南昌航空大学实验报告 课程名称:数据结构实验名称:实验一线性表的链式存储结构班级:080611 学生姓名:冯武明学号:16 指导教师评定:XXX 签名: XXX 题目:设计并实现以下算法:给出用单链表存储多项式的结构,利用后接法生成多项式的单链表结构,实现两个多项式相加的运算,并就地逆置相加后的多项式链式。 一、需求分析 ⒈先构造两个多项式链表,实现两个多项式的和及删除值为零元素的操作,不同用户输入 的多项式不同。 ⒉在演示过程序中,用户需敲击键盘输入值,即可观看结果。 ⒊程序执行的命令包括: (1)构造多项式链表A (2)构造多项式链表B (3)求两张链表的和(4)删除值为零元素,即不创建链表。 二、概要设计 ⒈为实现上述算法,需要线性表的抽象数据类型: ADT Stack { 数据对象:D={a i:|a i∈ElemSet,i=1…n,n≥0} 数据关系:R1={|a i-1,a i∈D,i=2,…n≥0} 基本操作: init(linklist *L) 操作结果: destroylist(List *L) clearlist(List *L) 初始条件:线性表L已经存在,1≤i≤ListLength(&L) 操作结果:用e返回L中第i个数据元素的值。 insfirst(link h,link s) 初始条件:数据元素e1,e2存在 操作结果:以e1,e2中的姓名项作为判定e1,e2是否相等的依据。 delfirst(link h,link *q) 初始条件:数据元素e1,e2存在 操作结果:以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有 ≤的关系。 交通大学《算法与数据结构》课程 实验报告 班级:计算机科学与技术2014级2班 实验项目名称:线性表的顺序储存结构 实验项目性质: 实验所属课程:算法与数据结构 实验室(中心): B01407 指导教师:鲁云平 实验完成时间:2016 年 3 月21 日 一、实验目的 1、实现线性表的顺序存储结构 2、熟悉C++程序的基本结构,掌握程序中的头文件、实现文件和主文件之 间的相互关系及各自的作用 3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现 二、实验容及要求 对顺序存储的线性表进行一些基本操作。主要包括: (1)插入:操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入 (2)删除:操作方式可分为删除指定元素、删除指定位置的元素等,尝试实现逻辑删除操作。 (3)显示数据 (4)查找:查询指定的元素(可根据某个数据成员完成查询操作) (5)定位操作:定位指定元素的序号 (6)更新:修改指定元素的数据 (7)数据文件的读写操作等。 其它操作可根据具体需要自行补充。 要求线性表采用类的定义,数据对象的类型自行定义。 三、实验设备及软件 VC6.0 四、设计方案 ㈠题目 线性表的顺序存储结构 ㈡设计的主要思路 1、新建SeqList.h头文件,定义SeqList模板类 2、设计类数据成员,包括:T *data(用于存放数组)、int maxSize (最大可容表项的项数)、int last(当前已存表项的最后位置) 3、设计类成员函数,主要包括: int search(T& x)const;//搜索x在表中位置,函数返回表项序号 int Locate(int i)const;//定位第i个表项,函数返回表项序号 bool getData(int i,T& x)const;//去第i个表项的值 void setData(int i,T& x)//用x修改第i个表项的值 bool Insert(int i,T& x);//插入x在第i个表项之后 bool Remove(int i,T& x); //删除第i个表项,通过x返回表项的值 bool IsEmpty();//判表空否,空则返回true;否则返回false bool IsFull();//判表满否,满则返回true;否则返回false void input(); //输入 void output();//输出 void ofile();/存储在文件中 void ifile();//读取文件并显示 ㈢主要功能 1、建立新表 2、对表进行插入(指定元素前、后以及指定位置插入)、删除(指定 元素删除及指定位置删除)、修改等操作 3、显示当前操作表的全部容 4、存储在文件中 5、从文件中读取表 五、主要代码 ㈠SeqList.h中的主要代码: 1、类成员声明部分: protected: T *data; //存放数组 int maxSize; //最大可容纳表项 图实验一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 2009级数据结构实验报告 实验名称:约瑟夫问题 学生姓名:李凯 班级:21班 班内序号:06 学号:09210609 日期:2010年11月5日 1.实验要求 1)功能描述:有n个人围城一个圆圈,给任意一个正整数m,从第一个人开始依次报数,数到m时则第m个人出列,重复进行,直到所有人均出列为止。请输出n个人的出列顺序。 2)输入描述:从源文件中读取。 输出描述:依次从显示屏上输出出列顺序。 2. 程序分析 1)存储结构的选择 单循环链表 2)链表的ADT定义 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系:R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作: ListInit(&L);//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表,若是,则返回1,否则返回0. ListLength(L); //求单链表L的长度 GetElem(L,i);//返回链表L中第i个数据元素的值; ListSort(LinkList [内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template 实验一:线性表逆置(顺序表)实验报告 (一)问题的描述: 实现顺序表的逆置算法 (二)数据结构的设计: 顺序表是线性表的顺序存储形式,因此设计如下数据类型表示线性表: typedef struct { ElemType *elem; /* 存储空间基址*/ int length; /* 当前长度*/ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList; (三)函数功能、参数说明及概要设计: 1.函数Status InitList(SqList *L) 功能说明:实现顺序表L的初始化 算法设计:为顺序表分配一块大小为LIST_INIT_SIZE的储存空间 2.函数int ListLength(SqList L) 功能说明:返回顺序表L长度 算法设计:返回顺序表中的length变量 3.函数Status ListInsert(SqList *L,int i,ElemType e) 功能说明:将元素e插入到顺序表L中的第i个节点 算法设计:判断顺序表是否已满,已满则加空间,未满则继续,将元素e插入到第i个元素之前,并将后面的元素依次往后移 4.函数Status ListTraverse(SqList L,void(*vi)(ElemType*)) 功能说明:依次对L的每个数据元素调用函数vi() 算法设计:依次对L的每个数据元素调用函数vi() 5.函数void Exchange(SqList *L) 功能说明:实现顺序表L的逆置 算法设计:用for循环将顺序表L中的第i个元素依次与第(i+length)个元素交换6.函数void print(ElemType *c) 功能说明:打印元素c 算法设计:打印元素c 2. (四)具体程序的实现 数据结构实验报告 二.程序设计相关信息 (1)实验题目:编写一个程序algo2-3.cpp,实现双链表的各种基本运算,并在此基础上设计一个主程序完成如下功能: 1.初始化双链表h; 2.依次采用尾插法插入a,b,c,d,e元素; 3.输出双链表h; 4.输出双链表h长度; 5.输出双链表h是否为空; 6.判断双链表h的第3个元素; 7.输出元素‘a’的位置; 8.在第4个元素位置上插入‘f’元素; 9.输出双链表h; 10.删除L的第3个元素; 11.输出双链表h; 12.释放双链表h。 (2)实验目的:熟悉双链表的基本操作并掌握尾插法建表。 (3)算法描述或流程图 (4)源代码 #include typedef struct DNode { char data; struct DNode *next; struct DNode *prior; }DNode,DLinkList; void initlist(DLinkList *&h) { h=(DLinkList*)malloc(sizeof(DLinkList)) ; h->next=NULL; h->prior=NULL; } void destroylist(DLinkList *&h) { DLinkList *p=h,*q=p->next; while(q!=NULL) {free(p); p=q; q=p->next; } free(p); } int getelem(DLinkList *h,int i,char &e) {int j=0; DLinkList *p=h; while(jnext; } if(p==NULL) return 0; else { e=p->data; return 1; } } int listempty(DLinkList *h) { return(h->next==NULL&&h->prior==NULL); } int listlength(DLinkList *h) { DLinkList *p=h;int n=0; while(p->next!=NULL) {n++; p=p->next; } return (n); 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境,进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21,23,14,5,56,17,31},然后在第i个位置插入元素68。 3.建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点,一维数组的机内表示就是顺序结构。因此,可用C语言的一维数组实现线性表的顺序存储。 在此,我们利用C语言的结构体类型定义顺序表: #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里,可避免在后面的参考程序中代码重复书写,另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素,在插入过程中注意溢出情况以及数组的下标与位序(顺序表中元素的次序)的区别。 3.单链表的结点结构除数据域外,还含有一个指针域。用C语言描述结点结构如下: typedef int elemtype; typedef struct node #include 数据结构实验一 1、实验目的 ?掌握线性表的逻辑特征 ?掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算 2、实验内容: 建立顺序表,完成顺序表的基本操作:初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空; 1.问题描述:利用顺序表,设计一组输入数据(假定为一组整数),能够对顺序表进行如下操作: ?创建一个新的顺序表,实现动态空间分配的初始化; ?根据顺序表结点的位置插入一个新结点(位置插入),也可以根据给定的值进行插入(值插入),形成有序顺序表; ?根据顺序表结点的位置删除一个结点(位置删除),也可以根据给定的值删除对应的第一个结点,或者删除指定值的所有结点(值删除); ?利用最少的空间实现顺序表元素的逆转; ?实现顺序表的各个元素的输出; ?彻底销毁顺序线性表,回收所分配的空间; ?对顺序线性表的所有元素删除,置为空表; ?返回其数据元素个数; ?按序号查找,根据顺序表的特点,可以随机存取,直接可以定位于第i 个结点,查找该元素的值,对查找结果进行返回; ?按值查找,根据给定数据元素的值,只能顺序比较,查找该元素的位置,对查找结果进行返回; ?判断顺序表中是否有元素存在,对判断结果进行返回; .编写主程序,实现对各不同的算法调用。 2.实现要求: ?“初始化算法”的操作结果:构造一个空的顺序线性表。对顺序表的空间进行动态管理,实现动态分配、回收和增加存储空间; ?“位置插入算法”的初始条件:顺序线性表L 已存在,给定的元素位置为i,且1≤i≤ListLength(L)+1 ; 操作结果:在L 中第i 个位置之前插入新的数据元素e,L 的长度加1; ?“位置删除算法”的初始条件:顺序线性表L 已存在,1≤i≤ListLength(L) ; 操作结果:删除L 的第i 个数据元素,并用e 返回其值,L 的长度减1 ; ?“逆转算法”的初始条件:顺序线性表L 已存在; 操作结果:依次对L 的每个数据元素进行交换,为了使用最少的额外空间,对顺序表的元素进行交换; ?“输出算法”的初始条件:顺序线性表L 已存在; 操作结果:依次对L 的每个数据元素进行输出; ?“销毁算法”初始条件:顺序线性表L 已存在; /////////////////////////////////////////////////////////// //--------------------------------------------------------- // 顺序存储结构线性表基本操作纯C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #include 2011~2012第一学期数据结构实验报告 班级:信管一班 学号:201051018 姓名:史孟晨 实验报告题目及要求 一、实验题目 设某班级有M(6)名学生,本学期共开设N(3)门课程,要求实现并修改如下程序(算法)。 1. 输入学生的学号、姓名和 N 门课程的成绩(输入提示和输出显示使用汉字系统), 输出实验结果。(15分) 2. 计算每个学生本学期 N 门课程的总分,输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次,总分相同者同名次。 二、实验要求 1.修改算法。将奇偶排序算法升序改为降序。(15分) 2.用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法;。(45分)) 3.编译、链接以上算法,按要求写出实验报告(25)。 4. 修改后算法的所有语句必须加下划线,没做修改语句保持按原样不动。 5.用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义,每种排序算法数据要求均不重复。 (1) 实验题目:《N门课程学生成绩名次排序算法实现》; (2) 实验目的:掌握各种排序算法的基本思想、实验方法和验证算法的准确性; (3) 实验要求:对算法进行上机编译、链接、运行; (4) 实验环境(Windows XP-sp3,Visual c++); (5) 实验算法(给出四种排序算法修改后的全部清单); (6) 实验结果(四种排序算法模拟运行后的实验结果); (7) 实验体会(文字说明本实验成功或不足之处)。 三、实验源程序(算法) Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 计算机系数据结构实验报告(1) 实验目的: 帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现,尤以链表的操作和应用作为重点。 问题描述: 1、构造一个空的线性表L。 2、在线性表L的第i个元素之前插入新的元素e; 3、在线性表L中删除第i个元素,并用e返回其值。 实验要求: 1、分别利用顺序和链表存储结构实现线性表的存储,并设计出在不同的存储结构中线 性表的基本操作算法。 2、在实验过程中,对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行 分析。 算法分析: 由于两种存储结构都用来创建线性结构的数据表,可采用相同的输出模式和整体结构类似的算法,如下: 实验内容和过程: 顺序存储结构线性表程序清单: //顺序存储结构线性表的插入删除 #include int len; //当前元素个数 int listsize; //当前存储最大容量 }SqList; //构造一个空的线性表L int InitList(SqList &L) { =(ElemType *)malloc(LISTSIZE*sizeof(ElemType)); if (! exit(-2); //分配空间失败 =0; =LISTSIZE; } //在顺序线性表L中第i个位置之前插入新的元素e int ListInsert(SqList &L,int i,ElemType e) { if (i<1||i>+1) return -1; //i值不合法 if >= { ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType)); //存储空间已满,增加分配 if(!newelem) exit (-2); //分配失败 =newelem; +=CREMENTSIZE; } ElemType *q=&[i-1]) ; for (ElemType *p=&[]);p>=q;--p) *(p+1)=*p; //插入位置及其后的元素后移 *q=e; ++; return 1; } //在顺序线性表L中删除第i个元素,并用e返回其值 int ListDelete(SqList &L,int i,ElemType&e) { if (i<1||i> return -1; //i值不合法线性表顺序存储结构上的基本运算
数据结构实验报告格式
数据结构实验报告 实验一 线性表链式存储运算的算法实现
(完整版)数据结构实验报告全集
3线性表及其顺序存储结构
数据结构实验报告
线性表ADT的顺序存储与链式存储实验报告
数据结构实验线性表的顺序存储结构
线性表的顺序储存结构
数据结构实验报告图实验
数据结构实验报告模板
线性表逆置(顺序表)实验报告
数据结构实验报告2
《数据结构》实验一 线性表及其应用
线性表顺序存储实现、插入、删除操作
数据结构实验一顺序表
顺序存储结构线性表基本操作 纯C语言实现
数据结构实验报告及心得体会
数据结构实验线性表及其应用