数据结构实验一线性表.docx

数据结构实验一线性表.docx

《数据结构实验一线性表.docx》由会员分享，可在线阅读，更多相关《数据结构实验一线性表.docx（18页珍藏版）》请在冰点文库上搜索。

数据结构实验一线性表

北京工业大学

2018-2019学年第1学期

信息学部软件学院

课程名称：

数据结构与算法I

报告性质：

□作业报告█实验报告

学号：

17081160

姓名：

艾孜尔江·艾尔斯兰

任课教师：

***

课程性质：

专业基础课

学分：

4

学时：

64

班级：

170811

成绩：

小组成员：

无

教师评语：

2018年9月24日

实验名称：

线性表操作实验日期2018.9.24

实验报告要求：

1.实验目的2.实验内容3.算法设计4.程序流程图5.运行结果6.实验体会（包括调试过程中发现的问题及解决方法）。

1.实验目的

1）熟悉并掌握线性表的逻辑结构、物理结构。

2）熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。

3）熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。

4）熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。

2.实验内容

（1）对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。

（2）求解约瑟夫问题，分别用数组的方式和链表的方式进行

3.算法设计

1）问题定义与需求分析：

该问题主要要求运用线性表的方式对一组数据的内容进行增、删、改、查等操作。

在不使用线性表的情况下，用户不得不在使用期间注意表的上限。

在使用线性表时，用户可以根据需求对于数据进行插入，分别按照位置进行插入或是按照数值进行插入。

在删除时，也能够根据自己的需求对无用数据进行移位删除。

分析：

首先建立一个带头结点的整顺序表，然后根据用户选择，能够在顺序表的任意位置插入、删除结点，以及确定某一元素在顺序表中的位置。

（1）建立顺序表功能

输入的形式和输入的范围：

输入若干整数，不用任何符号分隔；

输出的形式：

因为使用的是尾插法，故按倒序输出；

测试数据：

123456789

测试呈现：

987654321

（2）插入功能

输入索要插入的值，可以选择插入到相应位置，每插入一个数值，表长相应增加一个单位，即向后以一个单位。

测试数据：

123456

增加数值：

增加2于第三个位置中

测试结果：

1223456

例如，顺序表含有123456789这九个数字，选用按位置进行插入的方法直接将所要插入的位置向后以移，插入7于3和4之间，插入后所要显示的内容为1237456789。

（3）查找功能

有两种查找方式，分别是按照位置进行查找和按照数值进行查找。

在按照位置进行查找的过程中，系统会提示输入一个要查找的元素值，元素值必须得

是整型元素。

程序在内部做循环自加运算，知道相应的数值找到位置。

找到相应的数值后，程序将跳出该功能并呈现用户所需求的数值。

按照位置进行查找时，用户只用输入想要查看的位置即可获取上述结果。

2）数据结构与算法设计：

对问题描述中涉及的数据对象定义相应的数据结构，包括逻辑结构、存储定义和主要操作。

对主要算法要进行时间和空间复杂度分析。

算法描述：

1.如果表满了，则抛出上溢异常;

2.如果元素的插入位置不合理，则抛出位置异常;

3.将最后一个元素至第i个元素分别向后移动一个位置；

4.将元素x填入位置i处；

5.表长加1；

线性表：

每一步的时间复杂度为1，即O

（1）。

约瑟夫数组：

最高时间复杂度为n的平方，即O（n^2）

约瑟夫链表：

最高时间复杂度为n，即O（n）

3）概要设计：

本想要采用面向对象方法设计结构，定义类及类之间的关系。

约瑟夫数组用类和对象来实现，其余则经老师提示使用c语言编写将更为方便，因此在假期期间学着使用结构体进行编写。

目前系统结构合理、易于实现。

4）详细设计：

对数据结构和基本操作做进一步的求精，写出数据存储定义，用程序流程图或伪码对算法进行描述。

（一）线性表：

主体部分除了主函数外由五个功能函数组成，分别是：

voidInitList（List*l），voidSeq（Listl），

voidDelete（Listl），voidInsert（Listl），voidShow（Listl），分别实现“动态分配空间”、“尾插”、“删除”、“插入”和“呈现”五个功能。

可见，由于对函数传参的不熟练，以上均由空函数构成。

（二）约瑟夫链表

主体部分除了主函数外由两个功能模块组成，分别是：

voidInput（LinkList&a,intn）；voidJosephus（LinkList&a,ints,intm）。

前者实现为用书输入的数进行动态内存分配的功能和呈现功能，而后者则用于在约瑟夫环上根据结点进行删除和插入，移位。

（三）约瑟夫数组

使用类和对象来实现。

采用类模板。

主体部分除了主函数外还有两个功能，分别是：

voidShow_out（）和voidStart（）。

其中前者是呈现功能，而后者则是进行内部运算的功能。

5）编码与测试：

用C/C++编程实现系统，并设计测试用例对系统进行测试，修改程序中的错误，形成格式和风格良好的源程序清单。

本程序通过在编写时输入题中的信息进行测试，测试结果往往不尽如人意。

尤其是在线性表的测试过程当中碰壁不少，基本上没有能够完整的运行出来过。

尽管我尝试着按照上学期图书管理程序的课设进行编写，仍然面临了输入相应的数值后对于数据存储单元的不理解、各类定义和概念混淆等情况。

因此在编写约瑟夫问题的代码时，只要有不懂的就向周围有经验的同学询问，由于周围同学也并不能时时帮助到位，通过网络，我也学到了一些基本函数的使用方法。

相对于书本上冗长、容易令人混淆的概念和定义相比，网上的“菜鸟教程”对于我来说显得更加清晰明了。

6）设计结果分析：

对系统应用效果进行分析，评价系统的先进性、实际应用价值及存在的问题。

该程序完全是基于本次数据结构的实验进行的一次看似十分简单的代码编写。

相较于公司或企业内部的实际应用价值，起到了基础的结构作用。

线性表的插入、删除和查找等操作对于日后编写或完善类似于上学期C++课程设计中设计的图书管理程序、学生信息管理系统都起到了直接的促进作用。

本次设计结果分析得出结论：

在线性表的删除过程中，是应用了以为的删除方法，基本的思想都是一样的，在求解约瑟夫问题时，也应用了链表中像动态存储空间分配那样的基本方式。

系统的先进性体现在于改组程序的时间复杂度和空间复杂度上。

实际应用价值体现在内部的逻辑结构在日后编写程序过程当中的应用。

存在的问题体现在本程序在功能模块上设计过于简单，程序控制面板截面也并没有能够做到细致入微。

4.程序流程图

（一）线性表

（二）约瑟夫数组

（三）约瑟夫链表

5.运行结果

（一）

（二）约瑟夫数组和约瑟夫链表运行结果相同，截图如下

6.实验体会（包括调试过程中发现的问题及解决方法）。

在做本实验题时，本人对于数据结构的模糊认知逐渐褪去。

在编写该程序时，由于编程基础知识的匮乏，尤其是函数调用、类的实现方面举步维艰，深刻体会到只有每天都花一定量的时间练习编写程序才能在面临作业的时候不至于不知所措。

在编写该实验题的第一问的时候，我在看完实验视频后开始编写，因为完全不知道什么是结构体，经过网络查询也仍然对于结构体在程序中的使用方法疑惑不解，故打算使用类和对象的方法实现，然而在老师的提示下还是静下心来从网上查询了不知道的疑惑点并按照网上讲解的提示进行编写。

在编写的过程当中，之间击打键盘的舒适感和每一步都规划和分析所带来的愉悦感令人对编写代码逐渐喜爱的同时，所有代码编写完成后发现整个程序“起初无法运行，改了又改，仍无法运行，改到已经面目全非，仍然无法运行”所带来的精神痛苦接踵而来，令自己对能否在码农的道路上混口饭吃表示极度怀疑的同时，更是令我逐渐感觉到迎难而上的重要性。

迎难而上说来简单，但是当我真正做的时候才恍惚明白迎难而上需要有足够的能力。

因此，在补充自己匮乏的基础知识的同时，努力做到每一个程序能够轻松完成便成了我自始至终在程序编写的道路上矢志不渝的理想。

在程序中，有时候出现不可预知的错误，尤其是在约瑟夫问题求解的过程当中，偶尔出现不正常的运算结果。

经过推测，自认可能是因为使用了malloc函数所致。

因为本人在使用该函数的时候并没有充分理解该函数的内部机理，仅仅只知道该函数是用来“干什么的”和“怎么用的”。

后来得知，malloc只负责分配内存，并不会初始化，因此其内存空间中的值可能是的随机的。

因此，在进一步探索该函数内部机理的道路上，仍然要继续深化理解。

这次实验本身对于我来说，并没有成为巩固知识的过程，而是成为了一次学习的过程，路漫漫其修远兮，吾将上下而求索。

附录：

源代码

（一）线性表

/*

姓名:

艾孜尔江·艾尔斯兰

学号:

17081160

专业:

数字媒体技术

日期:

30/09/1800:

51

*/

#include

#include

usingnamespacestd;

typedefstructpoint//使用结构体进行编写，未使用类和对象

{

chardata;//声明字符型变量

structpoint*next;//定义next是一个structpoint类型的指针

}*List;

voidInitList（List*l）

{

*l=（List）malloc（sizeof（List））;//在内存中给a动态分配node字节空间，用完自动释放

（*l）->next=NULL;//指针的存储单元指向空值

}

voidSeq（Listl）

{

point*s;//声明s指针为结点类型

charc;//声明字符型常量

inta=1;//声明并初始化a

while（a）//如果情况发生

{

c=getchar（）;//从键盘上输入一个字符并且将字符赋给c

if（c!

='\n'）//此处表示用户在输入完一组数据后用回车键结束该项的输入，按回车退出输入

{

s=（List）malloc（sizeof（List））;//在内存中给a动态分配node字节空间，用完自动释放

s->data=c;//将c的值赋给s指向的的存储单元

s->next=l->next;//将l指向的存储单元赋给s

l->next=s;

}

else{a=0;}//如果用户没有按回车键，则将a初始化为0

}

}

voidDelete（Listl）

{

point*s;

inti,j=0;

cout<

cout<<"请输入删除位置：

"<

cout<

cin>>i;

s=l;

while（j

{

if（s->next->next==NULL）//如果s从第二个开始赋为空

{

cout<<"输入位置不正确！

"<

cout<<"请输入正确的位置！

"<

cout<

}

s=s->next;

j++;

}

s->next=s->next->next;

cout<<"删除成功！

"<

cout<

}

voidInsert（Listl）

{

point*s,*r;

inti,j=0;

charc;

cout<

cout<<"请输入插入位置：

"<

cin>>i;

cout<

s=l;

while（j

{

if（s->next->next==NULL）

{

cout<<"输入位置不正确！

"<

cout<

}

s=s->next;

j++;

}

cout<

cout<<"请输入插入数据：

"<

cin>>c;

cout<

r=（List）malloc（sizeof（List））;//在内存中给a动态分配node字节空间，用完自动释放

r->data=c;

r->next=s->next;

s->next=r;

cout<<"插入成功！

"<

cout<

}

voidShow（Listl）

{

inti=1;

cout<

cout<<"结果为：

"<

while（l!

=NULL）

{

if（i==1）{}

else

cout<data;

l=l->next;

i++;

}

cout<

}

intmain（）

{

Listl;

InitList（&l）;//调用InitList函数

cout<<"请输入数据：

"<

Seq（l）;//调用Seq函数

Show（l）;//调用呈现功能

Delete（l）;//调用删除功能

Show（l）;//调用呈现功能

Insert（l）;//调用插入功能

Show（l）;//调用呈现功能

}

（二）约瑟夫数组

/*

姓名:

艾孜尔江·艾尔斯兰

学号:

17081160

专业:

数字媒体技术

日期:

29/09/1823:

59

*/

#include

#include

usingnamespacestd;

constintMax=50;//声明固定不变的最大值，用户可根据参与容量进行改写

template//类模板，该句源于《数据结构》P60及《面向对象C++》P352

classJosephus//使用类进行编写

{

private:

//声明私有成员

intn,s,m;//n为游戏总人数、s为从第s个人开始报数、m为游戏人数间隔

Tin[Max],out[Max];//声明两个数组，来分别存放进入的序列和最终出去的序列

public:

Josephus（）//此处的名称必须跟上面的类名一致

{

cout<<"求解约瑟夫问题"<

cout<<"请输入总人数：

"<

cin>>n;//用户输入总人数

cout<<"请输入起始点：

"<

cin>>s;//用户输入起始报数点

cout<<"请输入报数间隔：

"<

cin>>m;//用户输入报数间隔

for（inti=0;i

{

in[i]=i+1;//因为数组中的第一个位置从0开始，故向后移一位

}

}

voidShow_in（）//声明呈现输入的函数

{

for（inti=0;i

{

cout<

}

cout<

}

voidShow_out（）//声明呈现输出的函数

{

for（inti=0;i

{

cout<

}

cout<

}

voidStart（）//声明运算的函数

{

intcount=0,address=0,j=0;//声明并初始化计数器、地点指向和搜索器

s=s-1;//起始点应当是该数本身

while（count

{

if（in[s]!

=0）j++;//当输入的总人数不为0时，搜索器加一往后搜索

if（j==m）//如果搜索器找到间隔之后被点到的那个数

{

out[address]=in[s];

in[s]=0;//再删除该数，表示该人去世

count++;//计数器一直前进计数

address++;//地点指向一直运作

j=0;//第一步运作结束，赋0给搜索器，初始化搜索器

}

s++;//向后加一

if（s==n）s=0;//如果游戏结束，则初始化以停止游戏

}

}

};

intmain（）

{

JosephusA;//从类模板中直接调用

cout<<"开始人员序号：

";

A.Show_in（）;//调用类模板中已经写好的呈现输入的函数

A.Start（）;//调用运算函数

cout<<"最终求解得出：

";

A.Show_out（）;//调用呈现函数

}

（三）约瑟夫链表

/*

姓名:

艾孜尔江·艾尔斯兰

学号:

17081160

专业:

数字媒体技术

日期:

28/09/1817:

32

*/

#include//为下文使用malloc函数所引出该头文件

#include

usingnamespacestd;

typedefstructnode

{

intdata;

structnode*next;

}node,*LinkList;

voidInput（LinkList&a,intn）

{

a=（node*）malloc（sizeof（node））;//在内存中给a动态分配node字节空间，用完用free函数进行释放

//这里使用到malloc函数,malloc函数被调用时，

//它会沿空闲链表寻找一个可以满足需求的内存块，

//然后把所需大小的内存块分配给用户，剩下的返回到链表上。

//因为malloc返回的是不确定类型的指针，因此返回前必须经过类型的强制转换。

node*p=a,*q;//地址交换

cout<<"开始人员序号为：

";

for（inti=0;i

{

p->data=i+1;//将i+1赋给p指针所在存储单元的值

q=（node*）malloc（sizeof（node））;//把返回类型void*强制转换为node*

//（sizeof（node）获取node类型所占足空间的大小

p->next=q;//将q赋给p指向下一个存储单元的值

p=q;//交换

cout<

}

cout<<""<

p->data=n;//将n的值赋给p指针所在存储单元的值

p->next=a;//将a的值赋给p指针谁在存储单元的值

}

voidJosephus（LinkList&a,ints,intm）//插入功能

{

node*nowPoint=a,*prePoint=a;//将地址进行赋值

cout<<"最终求解得出：

";//呈现结果

while（nowPoint->next!

=nowPoint）//如果结点指向的下一个存储单元地址不是结点本身

{

for（inti=0;i

{

prePoint=nowPoint;//将现在的结点赋给先前的结点的值

nowPoint=nowPoint->next;//将现在的结点值赋给现在结点指向的下一个存储单元

}

prePoint->next=nowPoint->next;//将下一个存储单元的现时结点赋给前一个结点的位置

cout<data<<"";//呈现结点的数

free（nowPoint）;//释放内存空间，于上方的malloc相对应

nowPoint=prePoint->next;//先前的结点单元指向现时的结点

}

}

intmain（）

{

intn,m,s;//声明总人数，间隔数和其实点

LinkLista;//声明开始值

cout<<"求解约瑟夫问题"<

cout<<"请输入总人数：

"<

cin>>n;

cout<<"请输入起始点：

"<

cin>>s;

cout<<"请输入报数间隔：

"<

cin>>m;

Input（a,n）;//调用相应的输入函数

Josephus（a,s,m）;//运算后呈现求得的最终结果

return0;

}