实验一线性表及应用.docx
- 文档编号:3182887
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:21
- 大小:125.31KB
实验一线性表及应用.docx
《实验一线性表及应用.docx》由会员分享,可在线阅读,更多相关《实验一线性表及应用.docx(21页珍藏版)》请在冰点文库上搜索。
实验一线性表及应用
实验一线性表及应用
一、实验目的
1.复习C语言的上机环境,掌握C语言的基本结构;
2.会定义线性表的顺序存储结构和链表的存储结构;
3. 熟悉对顺序表的一些基本操作和具体的函数定义。
4.掌握顺序表和单链表的存储结构及相关运算
5.掌握顺序表和单链表的基本应用
二、实验硬软件环境
硬件环境:
赛扬433以上CPU,10GB以上硬盘,64MB以上内存
软件环境:
DOS+TurboC2.0或BorlandC++3.1以上
Windowx9X+VC++5.0以上
三、实验要求
1.认真阅读和掌握本实验内容所给的全部程序。
2.保存和打印出程序运行结果,并结合程序进行分析。
3. 按照你对顺序表操作的需要,屏幕考贝运行结果到实验报告中。
4.撰写实验报告并准时上交
四、注意事项
在做第一次“数据结构”课程实验之前,要在硬盘上建立好自己的工作目录,专门用来存储你所做的实验程序及相关信息,以后每次做实验都采用这个目录。
工作目录建议如下建立,最后注明实验作者(张三):
D:
\数据结构实验(张三)
|
+-----实验一
|
+-----实验二
|…..
+-----实验九
实验一至九的有关材料请同学在网上下载(下载网址:
),本实验设计完全由老师设计,版权限本班同学使用,勿外传。
实验材料下载到本机后,请用winrar软件释放到你的电脑磁盘的“数据结构实验(张三)”文件夹中,形成如上图的文件夹结构。
上交实验报告时,请把“实验一”的所有内容(含实验报告)用winrar打包成.rar文件后一并交上来。
上传名字为“实验一(张三).rar”
五、基本理论
线性表:
线性表(linearlist)是这样的数据对象,其实例形式为:
(e1,e2,...en),其中n是有穷自然数。
ei是表中的元素,n是表的长度。
元素可以被视为原子,因为它们本身的结构与线性表的结构无关。
当n=0时,表为空;当n>0时,e1是第一个元素,en是最后一个元素,可以认为el优先于e2,e2优先于e3,如此等等。
除了这种优先关系之外,在线性表中不再有其他的结构。
基本操作:
•创建一个线性表。
•确定线性表是否为空。
•确定线性表的长度。
•查找第k个元素。
•查找指定的元素。
•删除第k个元素。
•在第k个元素之后/之前插入一个新元素。
线性表ADT(图1):
图1线性表抽象数据类型
顺序表:
采用数组来表示一个对象的实例,数组中的每个位置被称之为单元(cell)或节点(node),每个数组单元应该足够大,以便能够容纳数据对象实例中的任意一个元素。
在某些情况下,每个实例可分别用一个独立的数组来描述,而在其他情况下,可能要使用一个数组来描述几个实例。
实例中每个元素在数组中的位置可以用一个数学公式来指明。
假定使用一个数组来描述表,需要把表中的每个元素映射到数组的具体位置上。
第一个元素在什么地方?
第二个元素在什么地方?
在公式化描述中,可用一个数学公式来确定每个元素的位置。
一个简单的映射公式如下:
location(i)=i-1(式1-1)
式1-1表明第i个元素的存储位置在数组的第i-1个位置;
如果每个元素的长度为m,则可以通过公式计算第i个元素的存储地址:
Address(i)=Address
(1)+(i-1)*m(式1-2)
Address
(1)为第1个元素的址,即数组的首地址。
特别要记住的是第1个元素保存在数组的第0个位置。
图2表性表实例
简而言之,顺序表就是把线性表的元素存储在数组中,元素之间的关系直接通过相邻元素的位置来表达。
优点:
简单,数据元素的提取速度快;
缺点:
(1)静态存储,无法预知问题规模的大小,可能空间不足,或浪费存储空间;
(2)插入元素和删除元素时间复杂度高——O(n)
链表:
在存储线性表List中的每个元素ei时,同时存储元素的下一个元素的首地址(指针)Address(i+1),通过这种方法建立起元素之间的关系,从“逻辑”上看所有元素构成了图3所示的“链”,所以称为链表。
图3一个单链表
从图3可以看出元素之间的链接关系,为了“访问”每个元素ei的,必须知道ei的首地址,而这个首地址存储在其“直接前驱”结点ei-1中,……,按此规律,可以回推到元素e1的首地址。
即要访问List中任一元素ei,都必须从第一个元素e1开始,所以,必须保存首元素e1的地址在一个变量中(first),有的书使用Head作为变量名。
图3的单链表的首元素的地址在first中,我们可以直接用“first”称呼此单链表。
List中所有元素可以占用连续的存储空间,也可以占用不连续的存储空间。
但是从“逻辑”上来看所有元素仍然满足“一对一”的关系,即:
(1)首元素没有“直接前驱”,尾元素没有“直接后继”。
(2)中间元素有且仅有一个“直接前驱”和“直接后继”
为了实现这种存储结构,可以使用C语言作如下定义:
typedefstructLnode
{
DataTypedata;
structLnode*next;/*递归定义,保存下一个元素的首地址*/
}LinkNode;
关键字“typedef”的作用把结构体类型定义成一种新的类型LinkNode,即链表中的一个结点类型(用以存储一个数据元素,这样可以定义一个结点变量存储一个数据元素:
LinkNodea;
也可定义一个“结点”指针保存某个结点的首地址:
LinkNode*p;
对于其它可能不支持动态存储分配的高级语言来说,上述LinkNode类型定义时就内部就不能使用地址,但是我们可以利用数组“模拟”链表的功能,这种链表可以这样定义:
typedefstrutnode
{
DataTypedata;
intnext;
}LinkNode;
“指针”域用一个整型变量(next)来表示,用于存储下一个元素位于数组中的“位置”,这样定义的链表如图4所示:
图4静态链表
链表还有“循环链表”(图5)和“双链表”(图6),无论多么复杂的链表,其基础都是单链表,因此,完全掌握单链表后,学习其它有关链接存储将会变得简单得多,这是本章我们的重点任务。
循环单链表,实际上是利用链表的“尾结点”的空指针来指向链表的首结点。
有循环链表后,只要知道链表中任一结点的地址,就可以访问链表中所所有结点。
注意图5b引入了一“头结点”,目的是让空链表与非空链表统一,方便操作实现。
图5循环单链表
双链表是在单链表的基础上,在数据元素中再增加一个冗余项,用以保存结点的“直接前驱”结点的地址,这样结点既可以指向“直接后继”,也可以指向“直接前驱”,实现链表的双向查找。
图6双向链表
链表最大的优点是在某个元素之后插入结点或删除结点非常方便,时间复杂度为常数O
(1)。
缺点是空间利用率低,存取指定元素效率低O(n)。
六、实验内容与过程
本实验用到的文件有(在文件夹“实验一\实验材料\”中)
Lineast.h、Lineast.cpp、LineastTest.cpp、Link.h、Link.cpp、、LinkTest.cpp
前三个文件保存在子目录“SqList”中,后三个保存在子目录“Link”中
后缀有“Test”的文件用以测试顺序表和链表的各项操作的正确性,里面包含了主函数“main”。
*.h文件中包含了数据结构的定义,对应的同名cpp文件包含了对数据结构进行的各种操作的实现。
请按以下提示完成所有实验。
(一)文件Lineast.cpp是顺序表的实现,其中有三个函数没有完全实现,请同学认真阅读整个程序,然后根据所学的知识完善,完善后编译Lineast.cpp,然后运行LineastText.CPP,屏幕出现菜单:
Lineast.CPP中需要补充的代码如下:
……
intInsertElem(SqList*L,inti,ElemType*e)/*在第i个位置插入元素,插入成功返回1*/
{
intj;
/*请在以下部分插入程序代码*/
/*插入代码结束*/
return1;
}
intDeleteElem(SqList*L,inti)/*删除第i个元素,删除成功返回1*/
{
intj;
intn=GetLength(L);
/*请在以下部分插入程序代码*/
/*插入代码结束*/
return1;
}
…..
intSearchElem(SqList*L,ElemType*e)/*查找元素*e的位置j,找到返回,失败返回-1*/
{
intj;
intn=GetLength(L);
/*请在下面插入你的代码*/
/*插入代码结束*/
returnj<=n?
j:
-1;
}
补充正确后,运行程序出现屏幕菜单如图7:
图7运行菜单
对菜单中的每个功能项进行测试,以了解程序是否按照要求完成指定工作。
按照以下步骤测试程序,观察、记录每次结果,对于异常情况,请解释原因。
(1)输入1,回车,然后输入一组数据(数之间用空格隔开,-9999)为结束标志
102030405060708090-9999
(2)输入2,回车,观察屏幕并显示结果;
屏显:
(3)输入3,回车后,根据屏幕提示输入1,回车
屏显:
(4)输入3,回车后,根据屏幕提示输入3,回车
屏显:
(5)输入3,回车后,根据屏幕提示输入7,回车
屏显:
(6)输入3,回车后,根据屏幕提示输入大等于7的数,回车
屏显:
(7)输入3,回车后,根据屏幕提示输入:
0,回车
屏显:
原因:
(8)输入3,回车后,根据屏幕提示输入小于等于0的数,回车
屏显:
原因:
(9)输入4,回车后,根据屏幕提示输入:
353,回车
屏显:
(10)输入4,回车后,根据屏幕提示输入:
101,回车
屏显:
(11)输入4,回车后,根据屏幕提示输入:
50,回车
屏显:
原因:
(12)输入4,回车后,根据屏幕提示输入:
5-1,回车
屏显:
原因:
(13)输入4,回车后,根据屏幕提示输入:
909,回车
屏显:
(13)输入4,回车后,根据屏幕提示输入:
9510,回车
屏显:
(14)输入4,回车后,根据屏幕提示输入:
10012,回车
屏显:
原因:
(15)输入5,回车
屏显:
(16)输入6,回车后,根据屏幕提入示输入:
704,回车
屏显:
(17)输入6,回车后,根据屏幕提入示输入:
50,回车
屏显:
原因:
(18)输入6,回车后,根据屏幕提入示输入:
1009,回车
屏显:
(19)输入6,回车后,根据屏幕提入示输入:
11011,回车
屏显:
原因
(20)输入7,回车后,根据屏幕提入示输入:
6,回车
屏显:
(21)输入7,回车后,根据屏幕提入示输入:
0,回车
屏显:
原因
(22)输入7,回车后,根据屏幕提入示输入:
10,回车
屏显:
原因:
(23)输入8,回车
屏显:
(24)输入2,回车
屏显:
原因:
进一步思考并回答:
(1)步骤1、2分别用来干什么?
(2)步骤2-8用来干什么?
其中步骤5-8有什么用?
(3)步骤9-14用来干什么?
其中11、12、13、14的目的是什么?
(4)步骤16-19作用是什么?
(5)步骤20-21作用是什么?
(二)单链表的操作实现放在Link.CPP中,其中有几个函数未完成(如下),请同学们认真这个文件中的所有操作的实现,在适当的地方补充完成本实验:
….
LKListFindElem(LKList*L,inti)/*查找第i个元素的操作,近到返回元素地址,找不到返回空*/
{
LKListp=*L;
intj=0;
/*以下补充代码*/
/*代码补充结束*/
returnp;
}
……….
intInsertElem(LKList*L,inti,ElemType*e)/*在第i个位置插入元素*/
{
LKListp=FindElem(L,i-1);
LNode*s;
/*构造待插入的结点*/
s=(LNode*)malloc(sizeof(LNode));
s->data=*e;
s->next=NULL;
/*以下补充代码*/
/*代码补充结束*/
return1;
}
intDeleteElem(LKList*L,inti)/*删除第i个元素,成功,返回1*/
{
LKListp,q;
if(*L==NULL)return0;
/*以下补充代码*/
/*代码补充结束*/
return1;
}
函数补充正确、编译运行后,出现运行屏幕菜单如图8:
图8链表操作菜单
屏幕出现图8菜单后,请按
(一)中的数据和操作步骤
(1)-(24)测试所有功能选项,并写出每步的显示结果并分析原因:
比对
(一)与
(二)的运行结果,你发现了什么?
你认为这说明了什么问题?
(三)请分别在顺序表与链表中添加一个作操作Reverst(),实现表元素的就地“逆置”的操作,并测试程序的正确性,每种结构有三个地方需要添加
1.线性表有三处地方需要你添加相应的代码:
(1)Lineast.h
…..
/*以下是要添加的操作:
顺序表逆置*/
/*添加结束*/
(2)Lineast.cpp
voidClearList(SqList*L)/*清除线性表*/
{
L->Length=0;
}
….
/*以下为补充顺序表逆置操作实现*/
/*补充结束*/
…
(3)LineastTest.cpp
case'8':
ClearList(&L);
if(GetLength(&L)==0)
printf("Now,youlisthasnoelement!
!
\n");
break;
/*以下补充对功能9的测试代码*/
/*补充结束*/
case'0':
…..
2.单链表需要补充的地方
(1)Link.h
….
/*以下补充单链表的逆序操作说明*/
/*补充结束*/
….
(2)Link.cpp
…
/*以下补充逆序单链表的实现*/
/*补充结束*/
….
(3)LinkTest.cpp
break;
/*以下补充测试就地逆序链表的功能选项*/
/*结束补充*/
default:
3.要求每个实验自己设计至少5组有代表性的数据测试“操作”的正确性
(1)测试顺序表结果:
用例1:
结果1:
用例2:
结果2:
…..
用例5:
结果5:
(2)测试单链表结果:
用例1:
结果1:
用例2:
结果2:
…..
用例5:
结果5:
(四)正确完成前面三项工作后,继续做顺序表的应用实验、本实验用到的三个函数分别放在“实验一\实验材料\四”文件夹中的pra1-1.cpp、pra1-2.cpp、pra1-3.cpp程序文件中:
(1)pra1-1.cpp用来合并两个“有序”顺序表A和B到另放另一个顺序表C中,结果仍保持有序,函数名Combine;文件中,Combine的实现为空,请补充完整:
/*检查一个表是否有序,有序返回1,无序返回0*/
intIsSort(SqList*L)
{
/*以下填入代码*/
/*填入代码结束*/
return0;
}
/*合并函数*/
intCombine(SqList*A,SqList*B,SqList*C)
{
/*以下填入程序代码*/
/*填入代码结束*/
return1;
}
….
本实例要求用以下9组数据测试:
用例1:
A={2,5,8,9},B=1,6,1012,13}结果:
C=
用例2:
A={},B=1,6,1012,13}结果:
C=
用例3:
A={2,5,8,9},B={}结果:
C=
用例4:
A={10},B={}结果:
C=
用例5:
A={1,2,3},B={4,5,6,7,8,9}结果:
C=
用例6:
A={4,5,6,7,8,9},B={1,2,3}结果:
C=
用例7:
A={1,3,5,7,9,11},B={2,4,6,8,10,12}结果:
C=
用例8:
A={1,2,3,4,5},B={1,2,3,4,5}结果:
C=
用例9:
A={1},B={2}结果:
C=
(2)分解一个顺序表A,所有奇数存入表A1,所有偶数存入表A2,函数名Split;程序名为pra1-2.cpp,请补充完整;
/*分解A到A1和A2中,分解以后,A置空*/
intSplit(SqList*A,SqList*A1,SqList*A2)
{
/*以下填入程序代码*/
/*填写代码结束*/
return1;
}
以下为7组测试数据,根据测试结果,把运行结果硬拷贝后,复制到你的实验报告中。
用例1:
A={1,2,3,4,5,6,7,8,9,10}
用例2:
A={1,3,5,7,9}
用例3:
A={2,4,6,8,10}
用例4:
A={1}
用例5:
A={2}
用例6:
A={}
用例7:
A={1,3,5,7,2,4,6,8,10}
(3)合并两个顺序表A和B,结果放入到另一个顺序表C,在C中A与B两个顺表中的元素“交替”顺序存放,函数名Alternate;程序文件名为pra1-3.cpp,请补充完整
/*交替合并函数,C直接使用A与B的结点*/
intAlternate(LKList*A,LKList*B,LKList*C)
{
/*以下填入程序代码*/
/*补充结束*/
return1;
}
请采用
(1)的用例测试,然后观察结果。
(五)正确完成前面三项工作后,继续做“链表”的应用实验、本实验用到的三个函数分别放在“实验一\实验材料\五”文件夹中的pra1-4.cpp、pra1-5.cpp、pra1-6.cpp程序文件中:
(1)合并两个“有序链表”A和B,结果放入到另一个“链表”C中,仍保持有序,函数名Combine;程序文件为pra1-4.cpp。
测试用例与(四)同
(2)分解一个“链表”A,所有奇数存入表A1,所有偶数存入表A2,函数名Split;程序文件为pra1-5。
测试用例与(四)同
(3)合并两个“链表”A和B,结果放入到另一个“链表”C,在C中A与B两个顺表中的元素“交替”顺序存放,函数名Alternate;放在程序文件pra1-6中
测试用例与(四)同
(六)请完成一元多项式的类型定义和实现,多项式如下:
已知多项式用链表存储,其结点包括三个域,系数、指数和指针,如下所示:
ci
d
Next
“结点”表示的项为:
ci*xd。
每个多项式用一个单链表实现。
多项式的操作如下:
(1)Polynomial()——创建一个0阶多项式。
这个多项式的阶数为0,不包含任何项。
(2)Degree()——返回多项式的阶数。
(3)Input()——读入一个多项式。
可以假定输入是由多项式的阶数和一个系数表构成,系数表中的系数按指数递增的次序排列。
(4)Output()——输出多项式。
输出格式可以与输入格式相同。
(5)Value(x)——返回按x计算出的多项式的值。
(6)Destroy(A)——销毁多项式单链表
多项式的应用如下:
(1)Add(A,B,C)——A+B->C
(2)Subtract(A,B,C)——A-B->C
(3)*Multiply(A,B,C)——A*B->C
编写要求:
(1)仿照顺序表与链表的定义完成头文件的编写(Polynomial.h)
(2)仿照顺序表与链表的实现完成操作的实现(Polynomial.cpp)
(3)编写测试程序文件(主文件)以测试多项式的数据结构和操作(PolyTest.cpp);
初始代码放在(“实验一\实验材料\六”)文件夹中
测试用例:
编写至少5组测试用例分别测试加法、减法和乘法三个应用;并写出运行结果。
六、实验总结
1.Lineast.h、Lineast.cpp、Link.h、Link.CPP中如何实现信息隐藏和数据封装?
2.如果要“重用”已经定义好的数据结构来完成一些指定“应用”,则在编写程序时怎样把做好的数据结构与实际应用“关联起来”?
3.请写出你对本实验报告的意见和建议?
(50字以内)
4.通过本实验,你觉得自己取得什么样的进步?
(300字)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验一 线性表及应用 实验 线性 应用