线性表的遍历操作

线性表的建立与遍历

计算机软件辅助设计

实验报告

实验名称： 线性表的建立与遍历 实验地点： 信息学院机房 实验类别：□设计型 ■验证型 □综合型 班级：电子08-1班 学号： 姓名： 成绩： 指导教师： 谢秀兰 实验时间： 2011年12月

线性表的建立与遍历

实验一 线性表的建立与遍历

一、实验目的

进一步理解线性表的逻辑结构和存储结构，掌握线性表的建立与遍历算法 二、实验题目

线性表的建立与遍历 三、实验类型

验证性 四、实验内容

1、给定一个输入序列，建立顺序表，访问输出顺序表中各结点的内容。 2、给定一个输入序列，建立线性链表，访问输出线性链表中各结点的内容。 五、实验要求

根据实验内容，用C语言编程实现，上机调试运行得出实验结果，写出实验报告。 六、实验提示

1、线性结构中的所有结点按它们之间的关系可以排成一个线性序列： k1，k2， ，kn

其中k1是开始结点，kn是终端结点，ki是ki+1的前驱结点，而ki+1是ki的后继结点(i=1，2， ，n-1)。通常把上述线性序列称为“线性表”，把线性结构中

第八小组实验报告

实验报告

实验类型__综合设计__ 实验室____________

一、 实验题目

线性表的基本操作

二、实验目的和要求

1) 掌握线性表的特点

2) 掌握线性表的顺序存储结构和链式存储结构的基本运算及应用。 3) 尽可能考虑算法的健壮性

4) 实验报告中要写出测试数据、错误分析以及收获。

三、需求分析

本演示程序用c++6.0编写，完成单链表和顺序表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。

1、输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数

2、输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置 3、程序所能达到的功能：完成能完成两种存储结构的基本运算以及二级菜单的运用

4、测试数据

1)输入2，建立一个链表

2)插入操作中依次输入11,22,33,44,55，生成一个单链表 3)查找操作中依次输入22,44，返回这,2个元素在单链表中的位置 4)删除操作中依次输入3，删除位于3的元素

数 据 结 构

实验报告

课题名称：线性表的操作算法 姓名： 班级： 学号：

一、 内容提要

1、 掌握使用cFree上机调试线性表的基本方法；

2、 分别用数组和链表作为存储结构，实现线性表的插入、删除、查找、排序、合并等操作。

二、 实验要求

1、 设计对线性表进行链式存储操作的内容； 2、 写出相应程序；

3、 保存和打印出程序的运行结果，并结合程序进行分析；

三 、实验目的

1、理解数据结构中单链表的定义和建立。 2、掌握单链表中结点结构的C语言描述。

3、熟练掌握单链表的插入、删除、查找、排序、合并等算法的设计与C语言实现。 4、将理论与实际相结合，切实提高自己的逻辑能力和动手能力。

四、算法流程图

开始

创建

实验二 线性表的基本操作

一、实验目的

1. 掌握使用VC++6.0上机调试线性表的基本方法；

2. 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构上的运算。

3. 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在链式存储结构上的运算。

二、实验要求

1. 认真阅读和掌握本实验的程序。 2. 补全程序上机调试。

3. 保存程序的运行结果和程序清单，并结合程序进行分析

三、实验内容

1. 顺序表基本操作的实现：包括顺序表的创建、插入、删除和查找，请补全程序并调试。 第1步：任务分析

完成顺序表的建立，插入，删除和查找等函数功能，有助于更好的理解顺序表的概念和使用规律。上述函数都是线性表的基本操作，根据这些基本操作，可以构成其他更复杂的操作。

第2步：程序构思

(1) 顺序表的创建：因为顺序表的结构中包括了存放数据元素的起始地址，表的容量，以及表的当前长度等部分，所以表的创建工作一方面要为这些成员赋值，而存放数据元素的空间也需要在此处进行分配，因此整个创建工作包括了空间的创建和各个成员的赋值操作。

(2) 顺序表的插入：因为顺序表中的元素是连续存放的，元素之间的关系是通过位置的相邻性来体现的。因此在顺序表

线性表的基本操作及其应用

一、实验目的

1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。

二、实验内容

约瑟夫环（**） [问题描述]

约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺

时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

[基本要求]

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的

编号。

[测试数据]

由学生任意指定。

如：m的初值为20；n的值为7；密码：3，1，7，2，4，8，4；

（正确的输出结果应为6，1，4，7，2，3，5）。 (报告上要求写出多批数据测试结果)

[实现提示]

程序运行后首先要求用户输入初始报数上限值m，人数n,(设n≤30)。

然后输入各人的密码。

三、实验前的准备工作

1、掌握线性表的逻辑结构。 2、

实验一 线性表的基本操作

一、实验目的

1、理解线形表的定义、特征和相关概念； 2、理解线形表的顺序存储结构； 3、掌握上机调试线性表的基本方法。 二、实验条件

1、PC机

2、软件Visual C++ 三、实验原理

线性表的顺序存储结构是用一组地址连续的存储单元依次存放线性表中的元素。其实现手段是数组类型。由于内存中的元素存放顺序与逻辑上的顺序相同，所以元素的地址就体现了逻辑关系，即物理相邻=逻辑相邻；在插入或者删除某一个元素时，其后的所有元素也要做相应的后移或者前移，即有可能要移动大量元素。 四、实验内容

1、利用两个线形表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B，用顺序表实现；

2、对给定的两个集合能够进行合并，并给出合并结果； 五、算法分析

void union(List &La, List Lb){ La_len = ListLength(La); Lb_len = ListLength(Lb); for (i=1; i<=Lb_len; i++){ GetElem(Lb,i, e);

If(!LocateElem(La,e,equal)) ListInsert(La, ++L

实验一 线性表基本操作的编程实现

【实验目的】

线性表基本操作的编程实现 要求：

线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结构中任选，可以完成部分主要功能，也可以用菜单进行管理完成大部分功能。还鼓励学生利用基本操作进行一些更实际的应用型程序设计。

【实验性质】

验证性实验（学时数：2H）

【实验内容】

把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。为了体现功能的正常性，至少要编制遍历数据的函数。

【注意事项】

1.开发语言：使用C。

2.可以自己增加其他功能。

【思考问题】

1. 线性表的顺序存储和链表存储的差异？优缺点分析？ 2. 那些操作引发了数据的移动？ 3. 算法的时间效率是如何体现的？

4. 链表的指针是如何后移的？如何加强程序的健壮性？

【参考代码】（以下内容，学生任意选择一个完成即可）

（一）利用顺序表完成一个班级学生课程成绩的简单管理 1、预定义以及顺序表结构类型的定义 (1) #include

#include

#define L

重庆交通大学

《算法与数据结构》课程 实

验报告

班 级：计算机科学与技术2014级2班

实验项目名称： 线性表的顺序储存结构

实验项目性质：

实验所属课程： 算法与数据结构

实验室(中心)： B01407

指 导 教 师 ： 鲁云平

实验完成时间： 2016 年 3 月 21 日

教师评阅意见：

实验成绩： 签名： 年 月 日

一、实验目的

1、实现线性表的顺序存储结构

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

3、熟悉顺序表的基本操作方式,掌握顺序表相关操作的具体实现

二、实验内容及要求

对顺序存储的线性表进行一些基本操作。主要包括：

（1）插入：操作方式为在指定元素前插入、在指定元素之后插入、在指定位置完成插入

（2）删除：操作方式可分为删除指定元素、删除指定位置的元素等，

第 2 章 线性表

课后习题讲解 1. 填空

⑴ 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（ ）个元素，具体移动元素的个数与（ ）和（ ）有关。

【解答】表长的一半，表长，该元素在表中的位置

⑵ 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ ）。 【解答】108

【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108

⑶ 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（ ）。

【解答】p->next=(p->next)->next

⑷ 单链表中设置头结点的作用是（ ）。 【解答】为了运算方便

【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸ 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（ ）。 【解答】p->next=head 【分析】如图2-8所示。

⑹ 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（ ）；删除开始结点的操作序列为（ ）。

【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->

实验1 线性表的基本操作

一、实验目的

(1) 掌握线性表的逻辑特征；

(2) 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算； (3) 熟练掌握线性表的链式存储结构定义及基本操作； (4) 理解循环链表和双链表的特点和基本运算；

(5 )加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力； 二、实验内容

1、创建有若干个元素（可以是整型数值）的顺序表，实现对顺序表的初始化，对已建立的顺序表插入操作、删除操作、遍历输出顺序表。

要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作：

（1）从键盘上依次输入21、18、30、75、42、56，创建顺序表，并输出顺序表中的各元素值。

（2）分别在单链表的第3个位置插入67，给出插入成功或失败的信息，并输出此时顺序表中的各元素值。

（3）删除顺序表中的第6个数据元素，给出删除成功或失败的信息，并输出此时顺序表中的各元素值。

（4）查找顺序表中是否有75这个元素，如果有返回该元素在顺序表中的位序。

2、创建有若干个元素（可以是整型数值）的单链表，实现对单链表的初始化，对已建立的顺序表插入操作、删除操作、