北理工数据结构实验 线性表.docx

北理工数据结构实验 线性表.docx

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

北理工数据结构实验线性表

本科实验报告

实验名称：

线性表

课程名称：

数据结构

实验时间：

任课教师：

实验地点：

良乡机房

实验教师：

实验类型：

□原理验证

■综合设计

□自主创新

学生姓名：

学号/班级：

组号：

学院：

同组搭档：

专业：

成绩：

一、

实验目的

1、熟悉VC环境，学习使用C语言实现链表的存储结构。

2、通过编程、上机调试，进一步理解线性表、链表、环表的基本概念。

3、锻炼动手编程，独立思考的能力。

二、实验题目

1.采用单向环表实现约瑟夫环。

请按以下要求编程实现：

1从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。

环表中的结点编号依次为1，2，……，m。

2从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。

例如，m=10，s=3，n=4。

则输出序列为：

6，10，4，9，5，2，1，3，8，7。

2.归并顺序表。

请按以下要求编程实现：

1从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。

2将链表linka和linkb归并为linkc，linkc仍然为升序排列。

归并完成后，linka和linkb为空表。

输出linkc。

3对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。

例如：

linka输入为：

10203040500

linkb输入为：

15202530354045500

归并后的linkc为：

10152020253030354040455050

删除重复后的linkc为：

101520253035404550

三、实验基础知识

线性表、链表、环表的基本概念的熟练掌握并实际运用。

四、实验设计方法

题目一：

约瑟夫环

1、概要设计

应用单向环表寄存数字序列。

（1）、单项环表的抽象数据类型定义为：

ADTListLink{

数据对象：

D={ai|aiElemSet,i=1,…,n，n≥0}

数据关系：

R1={|ai-1,aiD,i=2,…,n}

基本操作：

Creat（&L,m）

操作结果：

构造一个有m个结点的单向环表L。

若申请空间失败返回错误信息

FindInitPostion（&L,m,s）

初始条件：

单向环表L已经存在。

操作结果：

找到单向环表L的第s个结点。

OutNum（&L,n）

初始条件：

单向环表L已经存在。

操作结果：

进行约瑟夫环的计算并输出相应编号。

}

ADTListLink

（2）、主程序流程主程序首先调用create（&L,m）函数创建含有m个结点的单向环表L，随后调用FindInitPostion（&L,m,s）函数找到初始位置第s个结点，最后调用OutNum（&L,n）函数计算结果并在屏幕上输出。

（3）、模块调用关系：

由主函数模块调用创建模块，查找模块与计算模块。

由计算模块将结果输出。

（4）、流程图

题目二：

归并顺序表

（1）、概要设计

voidMergeList（ListLa,ListLb,List&Lc）

{

//已知线性表La和Lb中的数据元素按值非递减排序

//归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列

InitList（Lc）;//实际程序中我写为了input（Lc）

i=j=1;k=0;

La_len=ListLength（La）;Lb_len=ListLength（Lb）;

while（

（2）、主程序流程（i<=La_len）&&（j<=Lb_len））{

//La和Lb非空

GetElem（La,i,ai）&&（j<=Lb_Len）;

if（ai<=bj）{ListInsert（Lc,++k,ai）;++i;}

else{ListInsert（Lc,++k,bj）;++j}

}

while（i<=La_len）{

GetElem（La,i++,ai）;

ListInsert（Lc,++k,ai）;

}

while（j<=Lb_len）{

GetElem（Lb,j++,bj）;

ListInsert（Lc,++k,bj）;

}

}//MergeList

（2）、主程序流程

先用input函数创建新的链表，用GetElem函数挨个提取La和Lb中的各个元素，比较选出较小的数，然后输入Lc中，并将相应La或者Lb中的节点后移一位

（3）、模块调用关系：

由主函数模块调用创建模块，查找模块与计算模块。

由计算模块将结果输出。

五、实验结果及数据分析

题目一

数据完全正确

题目二

数据完全正确

六、总结

此次编程实验，让我更清晰地了解了线性表的实际用处，并了解了其用法。

但同时我也发现了自己的一些问题，在c语言编程的时候，先确立基本模型，大的框架，基本结构没有问题，但是在编写的时候经常遇到编译通不过的问题，经过仔细检查，发现在很多地方出现字母拼写错误，变量输入错误，指针用错，函数带入错误等基本问题，导致在检查时耽误了很多时间。

在以后的编程实验中还需加强。

七、附录程序清单

题目一：

约瑟夫环

#include

#include

structnode

{

intnum;

structnode*next;

};

intmain（）

{

intm,s,n,i,j,k;

scanf（"%d%d%d",&m,&s,&n）;

structnode*head,*p,*q;

head=（structnode*）malloc（sizeof（structnode））;//建立表头节点

head->num=-1;

head->next=NULL;

for（i=m;i>0;i--）

{

p=（structnode*）malloc（sizeof（structnode））;

p->next=head->next;//插入节点

head->next=p;

p->num=i;//输入数据，记为节点号码

}

while（p->next!

=NULL）

p=p->next;//找到最后的节点

p->next=head->next;//建立环形链表

for（j=1;j

p=p->next;

for（i=0;i

{for（j=1;j

{

p=p->next;}

q=p->next;

printf（"%d",q->num）;//输出

p->next=q->next;

free（q）;//释放节点

}

}

题目二：

归并顺序表

#include

#include0

structnode

{

intn;

structnode*next;

};

voidinput（structnode*La,intnum）//链表的输入

{

structnode*p,*q;

p=（structnode*）malloc（sizeof（structnode））;//申请内存

p->next=NULL;

p->n=num;//记录数据

for（q=La;q->next!

=NULL;q=q->next）;

//将节点移动到链表最后，建立正序链表

q->next=p;//为接下来输入做准备

}

intGetElem（structnode*La,intm）

//链表中元素的提取，主要是将La和Lb中的链表数据提取出来

{

inti=0,ai;

structnode*p;

for（p=La;inext）;//到达提取数据的节点

ai=p->n;

returnai;

}

intmain（）

{

intnum=1,number=1;

inti=1,j=1,k,La_len,Lb_len,ai,bj;

structnode*La,*Lb,*Lc,*p,*q;

La=（structnode*）malloc（sizeof（structnode））;La->next=NULL;

Lb=（structnode*）malloc（sizeof（structnode））;Lb->next=NULL;

Lc=（structnode*）malloc（sizeof（structnode））;Lc->next=NULL;

while（num!

=0）//输入数据，并在输入0时结束

{scanf（"%d",&num）;

if（num!

=0）

input（La,num）;//调用输入函数

}

while（number!

=0）

{scanf（"%d",&number）;

if（number!

=0）

input（Lb,number）;

}

for（p=La,i=0;p->next!

=NULL;p=p->next,i++）;La_len=i;//计算出链表节点个数

for（p=Lb,i=0;p->next!

=NULL;p=p->next,i++）;Lb_len=i;i=1;

while（（i<=La_len）&&（j<=Lb_len））

{ai=GetElem（La,i）;bj=GetElem（Lb,j）;//提取元素

if（ai

//将较小的一个数计入Lc，并将节点后移

else{if（ai==bj）//两数一样大，记录后，在La和Lb中节点都后移

{input（Lc,bj）;++j;++i;}

else

{input（Lc,bj）;++j;}}

}

while（i<=La_len）//将较长链表剩余的计入Lc

{ai=GetElem（La,i++）;

input（Lc,ai）;

}

while（j<=Lb_len）

{bj=GetElem（Lb,j++）;

input（Lc,bj）;

}

p=Lc->next;

while（p!

=NULL）//输出

{printf（"%d",p->n）;

p=p->next;

}

}